Randomized methods have provable limits in convex set optimization

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

Machine Learning

Summary

Optimizing complex problems with linear minimization oracles (LMOs) is important in machine learning and other fields. Previous work showed worst-case performance limits for certain LMO methods but didn’t fully account for randomized algorithms. The authors prove that even randomized first-order LMO methods face fundamental lower bounds on how fast they can optimize over strongly convex sets. Their findings clarify the best possible performance achievable and close gaps left by earlier results.

What this means in practice

  • For optimization algorithm developers: Know the fundamental speed limits when designing randomized LMO-based optimizers over strongly convex constraints to avoid overestimating achievable performance.
  • For machine learning engineers: Understand when introducing randomization in convex optimization routines cannot surpass certain convergence speed limits, informing practical algorithm choices.

A theory result. No direct application yet.

Authors

Sebastian Pokutta

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 $Ω(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.