跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2610.13590 · v2

Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets

首次提交 2026-10-09 21:40
版本更新 2026-11-15 03:04
雷达观测 2026-11-17 12:06
arXiv ↗PDF ↗

摘要

Recent results [arXiv:2602.04378, arXiv:2602.22608] establish lower bounds for optimization over strongly convex sets, covering specified Frank-Wolfe updates and unrestricted deterministic first-order linear minimization oracle (LMO) methods, respectively. Neither establishes a lower bound for unrestricted randomized methods. We close this gap by proving an Ω(Ldiam⁡(S)2/T2)Ω(L\operatorname{diam}(S)^2/T^2) distributional lower bound after TT oracle calls for randomized first-order LMO methods over strongly convex sets, with final outputs required to be feasible on every instance and seed. While our construction reuses the family of [arXiv:2602.22608], our proof characterizes the conditional distribution of the hidden permutation after adaptive queries and bounds the expected decrease of a combinatorial statistic controlling optimizer variance. We also show that the same error threshold holds with probability at least 3/43/4 and yields a stopping-time tail bound. Our construction uses the same curvature-diameter coupling as [arXiv:2602.22608]. Comparisons with the upper bound [arXiv:1406.1305] must account for this coupling. Separately, we show that prescribed slow exact-line-search Frank-Wolfe trajectories can locally amplify sufficiently small initialization errors, corresponding to roughly one extra bit of initialization accuracy per iteration, and that initializations satisfying a particular eventual slow envelope have planar measure zero.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-15 03:04 · 最新观测版本

Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets

Recent results [arXiv:2602.04378, arXiv:2602.22608] establish lower bounds for optimization over strongly convex sets, covering specified Frank-Wolfe updates and unrestricted deterministic first-order linear minimization oracle (LMO) methods, respectively. Neither establishes a lower bound for unrestricted randomized methods. We close this gap by proving an Ω(Ldiam⁡(S)2/T2)Ω(L\operatorname{diam}(S)^2/T^2) distributional lower bound after TT oracle calls for randomized first-order LMO methods over strongly convex sets, with final outputs required to be feasible on every instance and seed. While our construction reuses the family of [arXiv:2602.22608], our proof characterizes the conditional distribution of the hidden permutation after adaptive queries and bounds the expected decrease of a combinatorial statistic controlling optimizer variance. We also show that the same error threshold holds with probability at least 3/43/4 and yields a stopping-time tail bound. Our construction uses the same curvature-diameter coupling as [arXiv:2602.22608]. Comparisons with the upper bound [arXiv:1406.1305] must account for this coupling. Separately, we show that prescribed slow exact-line-search Frank-Wolfe trajectories can locally amplify sufficiently small initialization errors, corresponding to roughly one extra bit of initialization accuracy per iteration, and that initializations satisfying a particular eventual slow envelope have planar measure zero.

查看此版本解读 →查看此版本原文 ↗