acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

Recent results by Halbey et al. (2026a); Grimmer & Liu (2026) have established worst-case objective-error lower bounds of order after 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 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 and yields a stopping-time tail bound.

Primary area:
optimization
Keywords:
frank-wolfe, lower bounds, randomized algorithms, distributional complexity

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_N2ZoOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper contributes a new lower bound for randomized algorithms in an LMO oracle model, and this improves over existing deterministic algorithm.

Overall the contribution is solid and substantial. One concern I have is the following: A natural leap from lower bound to randomized algorithm in the span to general algorithm is via embedding in a large ambient space. This seems like the natural approach, I suggest explaining in the paper why this is not the approach taken here, and what are the technical challenges. (I also raise it as a question here for the authors).

In terms of presentation the definition of LMO is almost invisible. It's an inline in the introduction, but a central notion of this paper. It should either appear in the model setup or be better highlighted.

Also in the abstract. the authors write : "However, upon close inspection both lower bounds are somewhat brittle: " This sounds suggestive of a mistake or oversight in previous work. However, both work that are then discussed acknowledge the reported limitations. I would rephrase this to make it clear that the contribution is for existing and known limitations, not something that requires close inspection.

Critical strengths

See paper summary

Critical weaknesses

see paper summary.

Questions for authors

in paper summary, about random embedding.

2 comments

Thank you for the positive assessment and the suggestions on the model and related-work presentation; all suggestions have been implemented in the revision of the paper (uploaded here).

Why not a random embedding? We agree this is a natural alternative. A span lower bound alone does not control what unrestricted adaptive queries reveal through exact LMO answers. An embedding-based proof would need a separate argument controlling this information. We chose the uniform permutation prior because it lets us describe the posterior and bound expected one-query progress directly, in dimension d=64(T+1)d=64(T+1). We added a short explanation in the introduction.

LMO definition. We have now displayed the definition of the Linear Minimization Oracle prominently in Section 2.1, immediately before the query/answer interface.

“Brittle” wording. We agree that this wording was unfortunate in hindsight. We intended to distinguish the algorithmic scopes of the results, not to suggest an error in the prior work. We have removed “upon close inspection” and “brittle” from the abstract. The abstract now simply distinguishes the earlier method classes and states the inherited geometric coupling; the contribution opening identifies the extension to unrestricted randomized methods.

Thanks.

Reviewer_QTuyOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proves an Ω(Ldiam⁡(S)2/(T+1)2)\Omega(L\operatorname{diam}(S)^2/(T+1)^2) expected-error lower bound for randomized first-order LMO methods over strongly convex sets. The methods may use arbitrary query directions, but must return a feasible point on every instance and every seed. The construction uses a uniform distribution over the permuted hard instances of Grimmer and Liu (2026). The main new argument characterizes the conditional distribution after adaptive queries and bounds the expected decrease of a combinatorial statistic controlling optimizer variance. The paper also gives a constant-probability lower bound and a stopping-time consequence.

Critical strengths

The main technical contribution is the one-query progress bound in Section 5. Under the uniform prior, a query can reveal several ranks and exclude additional assignments through its zero coordinates, so the previous resisting-oracle argument does not directly apply. The authors interpret Δ\Delta as the degree of a swap graph and express its expected decrease through edges crossing between different numerical-answer classes. The injective counting arguments then give the 6m6m bound. I find this a useful way to handle arbitrary adaptive queries without needing a one-coordinate-per-query property.

I also like how the posterior characterization fits this argument. The authors show that the full numerical LMO answer is captured by disclosed ranks and lower bounds on the remaining ranks. The conditional distribution therefore stays uniform over permutations with nested assignment constraints. The variance bound for this constrained family lets the same statistic Δ\Delta control both query progress and remaining optimizer uncertainty. This is where the proof goes beyond applying Yao to the existing hard family.

Critical weaknesses

My main reservation is the sense in which the lower bound matches the existing convergence rate. The construction has αdiam⁡(S)=Θ(1/d)\alpha\operatorname{diam}(S)=\Theta(1/d) and d=64(T+1)d=64(T+1). Then with LL and α\alpha fixed, the threshold in Theorem 2.7 scales as L/(α2(T+1)4)L/(\alpha^2(T+1)^4). Keeping the diameter fixed instead makes the set strong-convexity parameter decrease with TT. The authors acknowledge this coupling in Section 2.4, but it affects the interpretation of the exponent, not just whether the geometric constants are sharp. The randomized extension is useful, though it leaves a gap between the stated diameter-normalized lower bound and a matching complexity characterization with the geometric parameters fixed. I would like the comparison with Garber and Hazan (GH15 ICML), and the interpretation of Corollary 2.8, to make this distinction more explicit.

Questions for authors

Could the authors compare Theorem 2.7 with the (GH15 ICML) upper bound after substituting the parameters of the same constructed family into both bounds? In particular, which upper bound is matched in this regime once the dependence on the strong-convexity parameters is included? This would help clarify the precise optimality statement supported by the result.

2 comments

Thank you for the careful reading and for identifying the contribution of the posterior and one-query arguments. The geometric coupling you identify is inherited from Grimmer–Liu, not introduced by our randomized extension. We use their permuted sets and common quadratic, preserving the diameter-normalized order of their lower bound and the same geometric parameter regime, up to numerical constants. Our contribution removes the determinism restriction for unrestricted methods. Section 2.4 and Appendix C now compare the general Garber–Hazan estimate on this family with the error at 00, and explain why the latter gives a matching upper guarantee. The abstract and contribution opening state the inherited geometry. The theorem statements and proofs are unchanged.

Comparison with Garber–Hazan on our family. Write Dd=diam⁡(S)D_d=\operatorname{diam}(S) and n=T+1n=T+1. After the rescaling in Lemma 2.6, the parameters are

D_d=\frac{2(2-\sqrt2)}{\alpha\sqrt{d^2+d+2}}.$$ Thus Theorem 2.7 gives $$b_T=c\frac{L D_d^2}{n^2} =\frac{4c(2-\sqrt2)^2L} {\alpha^2n^2(d^2+d+2)} =\Theta \left(\frac{L}{\alpha^2n^4}\right),$$ when $L$ and $\alpha$ are fixed. Alternatively, keeping $D_d$ fixed makes the certified set strong-convexity parameter decrease as $1/n$. In our notation, Garber–Hazan (2015), Theorem 2, gives for its Frank–Wolfe method $$h_T\le \frac{\max\{(9/2)LD_d^2, 2304 L^2/(\alpha^2\mu)\}}{(T+2)^2}.$$ On the same family, $\mu=L$, so this general upper estimate is of order $L/(\alpha^2n^2)$, whereas the value of our lower bound is of order $L/(\alpha^2n^4)$. Equivalently, omitting its universal numerical constant, its geometric prefactor satisfies $$\frac{L^2/(\alpha^2\mu)}{LD_d^2} =\frac{d^2+d+2}{4(2-\sqrt2)^2} \sim 2984.15 n^2.$$ The curvature-dependent term makes this general estimate larger than our lower bound by a factor of order $n^2$. This reflects slack in the quoted estimate on this family, rather than an asymptotic gap between the best available upper and lower bounds for the family. The same geometric coupling is present in Grimmer–Liu. Returning $0$ without oracle calls already achieves an error of the same order as our lower bound on this family. Direct substitution into the common quadratic gives $$f(0)-f^\star\sim 8.00413\times10^{-4} \frac{LD_d^2}{n^2}.$$ Our lower constant is $c\approx2.31601\times10^{-7}$; the ratio of the error at $0$ to our lower bound tends to $3456$. For short-step or exact-line-search Frank–Wolfe started at $0$, the error cannot increase, so the same upper guarantee holds after $T$ iterations. Thus this initialization already provides an upper guarantee of the same order as our lower bound. Our lower bound shows that even unrestricted randomized methods using at most $T$ oracle calls cannot guarantee an improvement by more than a constant factor in worst-case expected error. The same benchmark is available on the Grimmer–Liu family. Proving the restriction on improvement against arbitrary adaptive queries requires our posterior and progress argument. **Corollary 2.8 and scope.** Its square-root expression is an inversion using the diameter of the constructed instance, rather than a characterization for arbitrary independently prescribed $L,\mu,\alpha,D$. The note after the proof now makes explicit that the diameter is that of the constructed family. Moreover, we discuss the relation between diameter and curvature in Section 2.4 and Appendix C in detail.

Thanks for the detailed response! I think the comparison with Garber–Hazan and the zero-call upper bound have answered my main questions.

My original concern still holds: the result does not establish T−2T^{-2} optimality when LL, μ\mu, α\alpha, and diam⁡(S)\operatorname{diam}(S) are all fixed independently of TT. But I appreciate that you now make this limitation clear in the paper.

I still think the extension to unrestricted randomized LMO methods is a solid contribution, especially with the posterior characterization and one-query progress bound. I will keep my rating at 3.

Reviewer_zRUaOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proves a distributional lower bound for randomized first-order methods that access a compact strongly convex set through a linear minimization oracle (LMO). On the hard family of Grimmer & Liu (2026), with dimension d=64(T+1)d=64(T+1), a uniform prior over permutations of the coordinate weights and a common smooth strongly convex quadratic objective, every randomized method with at most TT oracle calls and a feasible output has expected error at least c Ldiam⁡(S)2/(T+1)2c\,L\operatorname{diam}(S)^2/(T+1)^2, where c=(3+22)/(6144⋅642)c=(3+2\sqrt2)/(6144\cdot64^2).

Critical strengths
  1. A randomized lower bound for unrestricted LMO methods. The hard distribution is fixed before the random seed, and the bound covers adaptive first-order LMO methods without span or other restrictions.

  2. A clean argument for controlling adaptive information. The exact posterior over compatible assignments, the conversion of optimizer variance into loss and the swap-graph bound on the one-query decrease give the expectation, constant-probability and stopping-time results from one potential.

Critical weaknesses
  1. The paper reads as unfinished. The main text stops on page 9 right after the statement of Corollary 5.4, with no conclusion, no discussion of limitations and no summary of what has been shown. The abstract announces a second result, that the slow exact-line-search trajectories of Halbey et al. (2026a) amplify initialization errors so that roughly one extra bit of initialization accuracy is needed per iteration, together with Theorem B.4 on the measure of such initializations; this result appears only in Appendices B.4–B.5, about nine pages, and is never discussed in the main text. The AI-use statement mentions verification scripts, numerical and adversarial tests, and machine-checked proofs for the results covered by a formalization, but the submission contains neither code nor formalization and does not say which results are formalized. Several typos remain ("permuation", "be be", "the the").

  2. On the hard family, the T−2T^{-2} rate reflects the scaling of the instances rather than a convergence rate. The family couples d=64(T+1)d=64(T+1) with αdiam⁡(S)=Θ(1/T)\alpha\operatorname{diam}(S)=\Theta(1/T). The point 00 is feasible for every instance (the authors use it in the proof of Corollary 2.10) and is available without any oracle call. With L=μ=α=1L=\mu=\alpha=1, its error is about 8⋅10−4diam⁡(S)2/(T+1)28\cdot10^{-4}\operatorname{diam}(S)^2/(T+1)^2 for every TT, only about 3.5⋅1033.5\cdot10^3 times the lower bound, whose constant is c≈2.3⋅10−7c\approx2.3\cdot10^{-7}. The theorem therefore shows that on this family, T≤d/64−1T\le d/64-1 calls cannot improve on the zero-call answer by more than a constant factor, while the factor (T+1)−2(T+1)^{-2} comes from diam⁡(S)∼1/T\operatorname{diam}(S)\sim1/T. In the same regime, the constant L2/(α2μ)L^2/(\alpha^2\mu) of the upper bound of Garber & Hazan (2015) is about 3⋅103 (T+1)2Ldiam⁡(S)23\cdot10^3\,(T+1)^2L\operatorname{diam}(S)^2, so the two bounds agree only in the exponent of TT, and the result does not show that T−2T^{-2} is optimal for fixed LL, μ\mu, α\alpha and diam⁡(S)\operatorname{diam}(S). The coupling is inherited from Grimmer & Liu (2026) and is acknowledged at the end of Section 2.4, but the abstract and the contribution statement ("randomization cannot improve the corresponding order of convergence") do not mention it.

Questions for authors

Is there a construction with curvature and diameter fixed independently of TT, or another argument, that would show that T−2T^{-2} is optimal for fixed LL, μ\mu, α\alpha and diam⁡(S)\operatorname{diam}(S)?

3 comments

Thank you for recognizing the unrestricted randomized lower bound and the adaptive-information argument, and for the detailed concerns about interpretation and presentation. We have incorporated the geometric clarifications and added a short conclusion in the revised paper (uploaded here).

Geometric scaling and the zero-call answer. The coupling is inherited from Grimmer–Liu's construction for deterministic methods, rather than introduced by our extension to randomization. We reuse their permuted sets and common objective, with a larger constant in the dimension/horizon relation. With d=64(T+1)d=64(T+1), our family satisfies

=\frac{2(2-\sqrt2)}{\sqrt{d^2+d+2}}.$$ For fixed $L$ and $\alpha$, the value of our lower bound is of order $L/(\alpha^2(T+1)^4)$. For fixed diameter, the curvature parameter instead decreases with the horizon. Returning the feasible point $0$ (which does not require any oracle calls) gives error asymptotically $8.00413\times10^{-4}L\operatorname{diam}(S)^2/(T+1)^2$; its ratio to our lower bound tends to $3456$. Thus, on this family, even unrestricted randomized methods using at most $T$ oracle calls cannot guarantee more than a constant-factor improvement over the error at $0$ in worst-case expected error. This number of calls is proportional to the dimension. Garber–Hazan's general estimate applies to this family but is not tight there. For short-step or exact-line-search Frank–Wolfe started at $0$, the error cannot increase, so the bound obtained at $0$ also holds after $T$ iterations. This initialization therefore gives an upper bound of the same order as our lower bound; the discrepancy is with the quoted general upper bound estimate, not a gap between the best available bounds on this family. Section 2.4 and Appendix C now explain this comparison. **Fixed-parameter construction.** This is the same geometric question left open by the Grimmer–Liu construction for deterministic methods. We do not have a construction or argument in this work establishing $T^{-2}$ optimality for unrestricted randomized methods with $L,\mu,\alpha$ and diameter all fixed independently of the horizon. Rescaling this family does not provide one. What is established here is hardness for a fixed uniform prior, chosen before the random seed, against arbitrary adaptive query directions and universally feasible final outputs. **Completeness of the main text.** We have added a short Section 6 (Conclusion) after Corollary 5.4. It summarizes the randomized extension, identifies the inherited geometric scope and clearly separates the local-sensitivity and eventual-envelope results, whose formal statements and proofs are in the appendix because of space constraints. The abstract now uses neutral descriptions of the earlier method classes and states the inherited coupling. The previous abstract wording could be misunderstood; the revision makes these distinctions explicit. One factual clarification: page 2, lines 069–079 of the submitted paper already summarize both initialization-error amplification and the uncountable zero-area eventual slow-envelope set, with references to Appendix B.4 and Theorem B.4. Thus these results are not entirely absent from the main text, although their formal statements and proofs are in the appendix. We take the underlying point that their status and relationship to the main contribution should be clearer. More specifically, the two secondary statements concern different objects: finite-horizon, worst-case **local sensitivity near a prescribed trajectory**, and the area of starts satisfying a **particular eventual infinite slow envelope**. A measure-zero eventual set does not contradict the local sensitivity statement. Conversely, neither establishes that every continuously randomized initialization converges faster than $T^{-2}$, nor that all finite-horizon hard starts have measure zero. Neither is a correction to Halbey et al.'s finite-horizon lower bound. **Typos.** The four confirmed typographical errors are corrected in the revision.
AuthorsOpenReview ↗

regarding Lean coverage

Lean coverage

We agree that the original submission included no formalization bundle and that the AI-use statement did not identify the covered results. We had viewed the Lean development as supporting verification rather than as a separately claimed contribution, and were unsure whether to include the files. We will make the Lean sources publicly available after the final decision. If the area chair permits an earlier supplementary upload, we will provide an anonymized bundle through that channel.

The development uses Lean 4.29.1 with pinned Mathlib. For the listed results, the proof chains reach Mathlib and Lean's standard foundations under the stated model assumptions; they do not stop at project-local axioms or unproved intermediate claims.

Paper resultsFormalized coverage
Theorems 2.7 and 2.9; Corollary 2.10Expected-error and same-threshold 3/43/4 probability bounds, seed-independent fixed-instance witnesses (which may differ), and the stopping-time tail.
Main proof machineryHard-set geometry/scaling, exact numerical LMO disclosure, adaptive transcript/posterior characterization, optimizer variance and loss conversion, and the 6m6m swap-graph bound.
Proposition B.3; Theorem B.5Local initialization sensitivity along specified slow segments, and finite-horizon additive polar perturbation bounds with domain safety.
Theorem B.4; Lemmas B.6–B.8Actual unit-disk FW: infinite slow-trajectory existence, eventual-envelope characterization/asymptotics, survivor-area bounds, and the Borel, uncountable, area-zero exceptional set, including its probability-zero consequence for area-absolutely-continuous initialization laws.

The main endpoints are original_model_lower_bounds, original_model_fixed_instances and original_model_stopping_tail. They use full numerical query/answer histories and the paper's measurability and every-instance/every-seed final-feasibility assumptions; the expected/probability bounds additionally impose the stated oracle call budget. The generic minimax packaging via Yao's theorem is not separately formalized; our lower-bound endpoints do not require it. The new Appendix C comparison/zero-call calculation and empirical fits/conjectures from the plots are also outside this coverage.

Thank you for the detailed response and revision, which address my concerns. I am raising my score to 3.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.