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

Recent results by Halbey et al. (2026a); Grimmer & Liu (2026) have established worst-case objective-error lower bounds of order $1/T^2$ after $T$ linear minimization oracle (LMO) calls, matching the upper bound of Garber & Hazan (2015) in terms of dependence on 𝑇 and by doing so, resolving a long-standing open question. However, upon close inspection both lower bounds are somewhat brittle: Halbey et al. (2026a) only applies to the standard Frank–Wolfe algorithm, and 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, as we show; Grimmer & Liu (2026) on the other hand obtain lower bounds for any deterministic LMO-based first-order method via a resisting oracle which adversarially adapts to the queries of the algorithm. In both cases it is conceivable that randomization may circumvent these lower bounds and in particular neither establishes a lower bound for unrestricted randomized first-order LMO methods. We close this gap by proving an $\Omega (L\mathrm{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 Grimmer & Liu (2026), 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/4$ and yields a stopping-time tail bound.