analiza aiqbench
This paper establishes a rigorous distributional lower bound for randomized first-order linear minimization oracle methods, confirming that the $1/T^2$ convergence rate persists even when algorithms employ randomization to evade adversarial oracles. By characterizing the conditional distribution of hidden permutations under adaptive queries, the authors demonstrate that randomization cannot circumvent these fundamental limits in strongly convex optimization settings. This work solidifies the theoretical understanding of worst-case performance guarantees for randomized optimization algorithms central to modern machine learning training dynamics.
Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets
arXiv:2610.13590v1 Announce Type: cross Abstract: Recent results [arXiv:2602.04378, arXiv:2602.22608] have established worst-case objective-error lower bounds of order $1/T^2$ after $T$ linear minimization oracle (LMO) calls, matching the upper bound [arXiv:1406.1305] in its dependence on $T$ and thereby resolving a long-standing open question. Upon close inspection, however, both lower bounds are somewhat brittle. The first [arXiv:2602.04378] applies only to the standard Frank--Wolfe algorithm, and, as we show, its prescribed slow exact-line-search trajectories can amplify sufficiently small initialization errors exponentially, corresponding to roughly one additional bit of initialization accuracy per iteration. The second [arXiv:2602.22608] obtains lower bounds for any deterministic LMO-based first-order method via a resisting oracle that adversarially adapts to the queries of the algorithm. In both cases it is conceivable that randomization may circumvent these lower bounds; in particular, neither establishes a lower bound for unrestricted randomized first-order LMO methods. We close this gap by proving an $\Omega(L\operatorname{diam}(S)^2/T^2)$ distributional lower bound for randomized first-order linear minimization oracle methods over strongly convex sets. 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 further show that the same error threshold holds with probability at least $3/4$ and yields a stopping-time tail bound.
Abstract:Recent results [arXiv:2602.04378, arXiv:2602.22608] have established worst-case objective-error lower bounds of order $1/T^2$ after $T$ linear minimization oracle (LMO) calls, matching the upper bound [arXiv:1406.1305] in its dependence on $T$ and thereby resolving a long-standing open question. Upon close inspection, however, both lower bounds are somewhat brittle. The first [arXiv:2602.04378] applies only to the standard Frank--Wolfe algorithm, and, as we show, its prescribed slow exact-line-search trajectories can amplify sufficiently small initialization errors exponentially, corresponding to roughly one additional bit of initialization accuracy per iteration. The second [arXiv:2602.22608] obtains lower bounds for any deterministic LMO-based first-order method via a resisting oracle that adversarially adapts to the queries of the algorithm. In both cases it is conceivable that randomization may circumvent these lower bounds; in particular, neither establishes a lower bound for unrestricted randomized first-order LMO methods. We close this gap by proving an $\Omega(L\operatorname{diam}(S)^2/T^2)$ distributional lower bound for randomized first-order linear minimization oracle methods over strongly convex sets. 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 further show that the same error threshold holds with probability at least $3/4$ and yields a stopping-time tail bound.
Optimization and Control (math.OC); Machine Learning (cs.LG)
arXiv:2610.13590 [math.OC]
(or arXiv:2610.13590v1 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2610.13590 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 308 cuvinte
Subiecte conexe
Lattice-Based Cryptography Explained
Quantum Zeitgeist · 15 aug. 2026
On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization
arXiv · 15 oct. 2026
Productionizing TurboQuant on AMD GPUs for KV-Cache-Bound LLM Inference
AMD · 11 iun. 2026
Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank
arXiv · 9 sept. 2026