Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets
Abstract
Recent results [arXiv:2602.04378, arXiv:2602.22608] have established worst-case objective-error lower bounds of order 1/T2 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 Ω(Ldiam(S)2/T2) 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.
Related
- Matching Full-Hessian Oracle Complexity for Nonconvex--Strongly-Concave Minimax Optimization
- A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
- The Price of Feasibility: Greedy Approximation Bounds for String Supermodular Optimization over Oracle-Conditioned Greedoids
- Lower Bounds for Linear-Oracle Online Learning
- Randomized and Oracle-Based Feasible Directions Methods for Nonsmooth Nonconvex Constrained Optimization
BibTeX
@misc{pokutta2026lower,
title = {{Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets}},
author = {Sebastian Pokutta},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13590},
eprint = {2610.13590},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13590},
}
RIS
TY - UNPB
TI - Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets
AU - Sebastian Pokutta
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13590
UR - https://arxiv.org/abs/2610.13590
AB - 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 Ω(Ldiam(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.
ER -