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

Sebastian Pokutta

math.OCOct 9, 2026

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

Authors: Sebastian Pokutta

Organizations: Zuse Institute Berlin and TU Berlin

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.

Figures & tables

Result	Method class	Randomization covered?	Data chosen	Rate
[ Halbey et al., 2026a ]	Exact-line-search or short-step Frank–Wolfe	Not an unrestricted-method result	Horizon-dependent initialization	$T^{-2}$
[ Grimmer and Liu, 2026 ] , span	LMO-span methods	Yes, for every fixed seed	One fixed ordered instance	$T^{-2}$
[ Grimmer and Liu, 2026 ] , resisting	Unrestricted first-order LMO	Deterministic only	Permutation completed from the transcript	$T^{-2}$
This paper	Unrestricted first-order LMO with feasible final output on every instance and seed	Yes	Uniform prior fixed before the seed	$T^{-2}$

Table 1: Comparison of the lower bounds. The rate is objective error after

T

oracle calls.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 1: The example’s allowed assignments. Columns show both reduced indices

j

and original ranks

r_{j}

; rows show both

i

and

\iota(i)

. The shaded cell is excluded by the second answer. Dots mark the generating assignment

\sigma=(1,3,2)

(in the reduced coordinates), not the only compatible assignment.

Figure 2: Vertices are the four compatible reduced permutations. Each double-headed connection represents two directed swap edges. Equal colors indicate equal numerical answers to

p=e_{3}

. Dashed connections cross answer classes; only the top pair remains together.

LMO Methods

See all 13 papers

Sep 29, 2026

Lower Bounds for Linear-Oracle Online Learning

Can a constant number of linear minimizations per round improve on the

T^{3/4}

regret rate of online Frank-Wolfe on general convex sets? Weibel et al. conjectured that fixed-coefficient methods cannot. We prove their conjecture and extend the lower bound to every deterministic learner in an oracle-only model. The learner receives an initial feasible point and a diameter bound, and must remain feasible on every domain consistent with its oracle replies. For

T

rounds, at most

b

calls between decisions, diameter bound

D

, and gradient norm bound

L

, we construct an instance in dimension

d=2b(T-1)+1

with regret at least

2^{-1/4}LDb^{-1/4}T^{3/4}

. The adversary fixes the domain, initial point, deterministic tie rule and linear losses before play. The vertices form a path on which every point available before a decision has zero current loss, while the final vertex has negative loss on every round. For constant

b

, the result matches the known upper rate for dimension-independent guarantees. For one-call fixed schedules with a nonzero coefficient on the newest gradient, a second construction gives regret at least

3LDT^{3/4}/4

with unique minimizers at every issued query. Exact-arithmetic certificates for the tuned schedule of Weibel et al. closely match their finite-horizon numerical worst cases, with unique oracle replies.

Mohit Sinha

Online Convex Optimization Information-Theoretic Lower Bounds LMO Methods

Ask PDF

Oct 1, 2026

Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization

We establish complexity lower bounds for stochastic first-order algorithms in nonconvex--concave minimax optimization, allowing algorithms to use variance reduction. Our main contribution is a lower bound for a zero-respecting algorithm class that permits variance reduction, extending beyond the algorithmic restrictions imposed by some existing lower bounds. We consider objectives with an

L

-Lipschitz continuous joint gradient, a compact convex dual domain of Euclidean radius at most

D_Y

, and a primal value function, defined by maximizing the objective over the dual variable, with initial suboptimality at most

Δ

. The target accuracy

\varepsilon

is measured by the gradient norm of the Moreau envelope of the constrained primal value function with parameter

1/(2L)

. Under an unbiased stochastic first-order oracle with variance at most

σ^2

and mean-square smoothness, we prove the lower bound

Ω\!\left(L^2D_YΔ\varepsilon^{-3}+L^3D_Y^2Δσ^2\varepsilon^{-6}\right)

. This result quantifies the dependence on accuracy, dual-domain radius, and oracle noise even when variance reduction is allowed. We also establish complementary lower bounds for nonconvex--strongly-concave minimax optimization. With dual strong-concavity parameter

μ>0

and condition number

κ:=L/μ

, we obtain

Ω\!\left(LΔ\sqrtκ\,\varepsilon^{-2}+LΔκσ^2\varepsilon^{-4}\right)

under the bounded-variance oracle model. Under the additional mean-square smoothness condition with constant

\bar L

, we obtain

Ω\!\left(LΔ\sqrtκ\,\varepsilon^{-2}+Δ\bar Lσκ^{3/2}\varepsilon^{-3}\right)

. Together, these results identify complexity barriers across the concave and strongly concave regimes, with the main nonconvex--concave bound remaining valid for algorithms that use variance reduction.

Jiayi Song, Zi Xu

Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China

Min-Max Optimization

Ask PDF

Jul 21, 2026

Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

We prove two lower bounds for the first order oracle complexity of minimizing a

d

-dimensional

1

-Lipschitz convex function over the unit ball with

m

bits of memory. We first show that any such (possibly randomized) algorithm must make

\tildeΩ(\frac{d^2}{\sqrt{m}})

oracle queries. For deterministic optimization algorithms, we show that

\tildeΩ(\min\{d^{1.6},\frac{d^{8/3}}{m^{2/3}}\})

queries are required. For all memory regimes of interest, these improves upon the previous best known lower bounds of

\tildeΩ(\max\{\frac{d^{8/3}}{m^{4/3}},\frac{d^{4/3}}{m^{1/6}}\})

and

\tildeΩ(\frac{d^{5/3}}{m^{1/3}})

for randomized and deterministic algorithms respectively. Notably, due to existing upper bounds, our lower bound for deterministic algorithms is the first to show a sharp oracle complexity phase transition around

m\approx d^2

, where a polylogarithmic change in memory leads to a

\mathsf{poly}(d)

change in the number of required oracle calls. Further, when the suboptimality is polynomially small in

d

, our lower bound randomized algorithms is the first to show that

\tildeΩ(d^2)

memory is necessary to nearly match the optimal query complexity among algorithms without memory constraints. Previously, such a result was only known for the regime where the suboptimality is quasipolynomially small in

d

Michael Menart, Aleksandar Nikolov, Ohad Shamir

Department of Computer Science, University of Toronto, Vector Institute · Department of Computer Science, University of Toronto · Weizmann Institute of Science and University of Toronto +1

Query Complexity Oracle Complexity Memory-Efficient Optimization Constrained Optimization

Ask PDF

Abstract

LMO Methods

Explore similar work

Lower Bounds for Linear-Oracle Online Learning

Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization

Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory