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

1 Introduction

• For smooth convex objectives over compact convex sets, Frank–Wolfe replaces projections with an LMO; strong convexity of both function and set admits an O(1/T^2) rate.Source: §1 · p. 1

Related work

• Halbey et al. [2026a] give Ω(1/t^2) trajectories only for exact-line-search or short-step Frank–Wolfe, with horizon-dependent initialization; tiny perturbations can be amplified by roughly 2^T.On the unit-disk instance, initializations with eventual slow-envelope behavior are uncountable but have planar Lebesgue measure zero.Source: Related work · p. 2
• Grimmer and Liu [2026] prove an Ω(Ldiam(S)^2/(T+1)^2) lower bound for deterministic LMO methods, but their resisting oracle adapts the hard instance to queries.Applying the construction separately to random seeds need not yield one fixed instance hard in expectation; their fixed-instance result covers only LMO-span methods.Source: Related work · p. 2

Contribution

• The paper seeks to show that randomization cannot improve the convergence order, even without restrictions on query directions or intermediate evaluation points.It uses a hard distribution and Yao’s principle to derive a randomized lower bound.Source: Contribution · p. 3
• The construction reuses Grimmer and Liu [2026]’s feasible sets and common quadratic objective, but replaces adaptive adversarial responses with a fixed uniform prior over those sets.Because answers may reveal more information under this prior, the proof must account for information disclosed by adaptive queries.Source: Contribution · p. 3
• Conditioned on the seed and query transcript, compatible hidden permutations form an exchange graph with the same number Δ_t of compatible exchanges from every vertex.The proof uses a combinatorial statistic to lower-bound conditional optimizer variance rather than mutual information or entropy.Source: Contribution · p. 3
• The potential starts quadratic in dimension while its expected per-query decrease is at most linear, so choosing dimension proportional to T leaves optimizer variance that yields optimization error.The argument permits one query to disclose several weights and does not require a span restriction.Source: Contribution · p. 3

2.1 Oracle model

• The oracle returns objective value, gradient, and an LMO answer; queries and stopping decisions may depend measurably on the full history, and only outputs must always be feasible.The method need not restrict query directions, evaluation points, computational resources, or seed size.Source: §2.1 · p. 4

2.2 The permuted hard family

• The hard family permutes coordinate weights across feasible sets while retaining a common quadratic objective and unique instance-dependent minimizers.The sets are stated to be 1-strongly convex, and the common objective places each constrained minimizer on the set boundary.Source: §2.2 · pp. 4–5

2.3 Derivation from the two main estimates

• A combinatorial statistic starts at d(d−1)/2; bounding its expected decrease and converting the remaining uncertainty into optimizer variance yields the loss bound.The derivation averages over permutations compatible with the transcript; its expected-decrease estimate is the main work.Source: §2.3 · p. 6

2.4 Main results

• After T calls, every randomized method in the stated model has expected objective gap at least cLdiam(S)^2/(T+1)^2 on the uniform hard distribution.The bound rescales to L-smooth objectives and α-strongly convex feasible sets; some fixed permutation also has at least this expected seed-averaged loss.Source: §2.4 · p. 6
• T = Ω((Ldiam(S)^2/ε)^(1/2)) queries are required to guarantee expected gap at most ε under universal final-feasibility requirements.The query-complexity corollary uses the same assumptions as the distributional lower bound.Source: §2.4 · p. 7

Some fixed permutation has probability at least 3

• A fixed permutation has probability at least 3/4 of attaining the error threshold in Theorem 2.9, and a stopping-time tail bound follows by truncation.The truncation returns the feasible point 0 if the method has not stopped by T; nontermination is included in the tail.Source: Some fixed permutation has probability… · p. 7
• The paper does not claim optimal dependence on all geometric parameters simultaneously because αdiam(S) = Θ(1/d) in this family.The fixed-permutation witnesses for the expectation and probability bounds may differ, though neither depends on the realized seed.Source: Some fixed permutation has probability… · p. 7

3.1 The exact oracle answer

• A zero query reveals no instance-dependent information, while a nonzero answer may disclose multiple coordinate-weight assignments at once.Some active-rank equalities can repeat ranks revealed by earlier answers.Source: §3.1 · pp. 7–8
• An LMO answer reveals each active coordinate’s weight rank and imposes a lower bound on the rank of each inactive coordinate; these constraints fully characterize the information in the answer.The active-rank equalities and inactive-rank inequalities also determine the answer, so its numerical values add no further restrictions.Source: §3.1 · pp. 8–9

3.2 Conditional distributions, Remaining ranks, and compatible assignments

• For a fixed algorithm seed and transcript, the hidden permutation is uniform over assignments matching earlier active-rank equalities and inactive-rank lower bounds.Adaptive queries add no other restrictions because the query is fixed by the preceding transcript and the objective’s value and gradient do not depend on the permutation.Source: §3.2 · p. 9
• After reindexing unresolved coordinates and unused ranks, the remaining constraints form nested allowed column sets on a Ferrers board, enabling the compatible assignments to be counted.The row-dependent restrictions determine each row’s allowed ranks; selecting uniformly among the currently allowed columns samples compatible assignments uniformly.Source: §3.2 · pp. 9–10

4 Conditional variance and optimization error

• The variance-to-loss argument requires more careful averaging because the conditional assignment family has row-dependent restrictions.The estimate is designed to account for those restrictions.Source: §4 · p. 10
• The statistic Δ(ℓ) is m(m−1)/2 for an unrestricted permutation and 0 for a unique assignment.The unique-assignment case includes the empty assignment.Source: §4 · p. 10
• Under nested lower bounds, the rank-variance lemma considers a permutation drawn uniformly from the compatible family ℱ(ℓ).The proof conditions on assignments to later rows and uses the remaining allowed columns to bound variance.Source: §4 · p. 10
• At a final transcript with unresolved assignments, any point feasible on every compatible instance has conditional optimization error tied to the variation among their optimizers.The proof compares a fixed feasible point with the optimizer that may differ across compatible instances.Source: §4 · pp. 10–11

5 Expected decrease in one query

• The expected decrease in Δ is bounded by counting compatible swaps that produce different answers, using pairs newly excluded by the query.The analysis first reduces the count to newly excluded pairs and then bounds their expected number linearly in the number of unresolved rows.Source: §5 · pp. 11–13
• The query analysis represents compatible assignments as vertices connected by allowed swaps, with every vertex having the same number of outgoing edges.Swapping two ranks preserves compatibility when the lower rank is accepted by its row and the other row moves upward.Source: §5 · p. 11
• An answer class is the set of compatible assignments producing the same numerical LMO answer, and it is represented by the updated family ℱ(ℓ+).Swaps remaining within an answer class are allowed swaps under the updated bounds.Source: §5 · p. 11
• For each compatible assignment, at most 2m newly excluded pairs are counted, including pairs at the threshold boundary.The strict-inequality pairs contribute at most m in expectation, and there is at most one remaining pair per row.Source: §5 · p. 13
• The one-query decrease result applies to every adaptive transcript.Its proof controls expected progress over assignments compatible with the transcript rather than assuming one rank is disclosed per query.Source: §5 · p. 13

AI use statement

• Generative AI tools assisted with mathematical arguments, verification and plotting scripts, formalization, and manuscript editing; the authors say they independently verified all claims.The authors take responsibility for the final content and artifacts.Source: AI use statement · p. 13

A Detailed comparison with existing lower bounds

• Lower-bound implications for randomization depend on the algorithm class, horizon-dependent data, and when the instance is fixed relative to the seed.The comparison examines two recent 1/T^2 lower bounds.Source: A Detailed comparison with existing… · p. 16

A.1 Distributional and randomized values

• Yao’s principle equates the distributional and randomized values under closure of the deterministic class under arbitrary mixtures.The proof uses bounded measurable loss and finite-dimensional minimax reasoning.Source: §A.1 · p. 16
• A lower bound for one fixed prior suffices for the distributional argument.The method may know the prior but not the sampled instance.Source: §A.1 · p. 16

A.2 Further related work

• The related-work discussion contrasts the paper’s exact conditional distributions and combinatorial statistic with entropy-based information measures, and notes a different oracle and geometry in Hazan [2026].The Hazan result uses membership-based supporting-tangent computations and a uniform interior rolling-ball condition.Source: §A.2 · p. 16

A.3 [Grimmer and Liu, 2026]: deterministic and randomized quantifiers

• For randomized LMO-span methods, Grimmer and Liu [2026]’s lower bound holds for every fixed seed on one ordered instance, but it does not cover general randomized LMO-based methods.The span class includes standard Frank–Wolfe variants, while general methods may use query directions outside the observed span.Source: §A.3 · p. 17
• Coordinate queries can identify the permutation and recover the optimizer on a specified instance, but this example lies outside the LMO-span class.The recovered optimizer is outside the convex hull of the query atoms.Source: §A.3 · pp. 17–18
• A specified-instance separation between algorithm classes is not an o(T^-2) worst-case algorithm.The text distinguishes such separations from the deterministic resisting-oracle theorem and this paper’s randomized distributional theorem.Source: §A.3 · p. 18
• The resisting-oracle argument completes hidden coordinate ranks after observing a deterministic transcript, whereas fixing seeds separately only yields a potentially different hard instance for each seed.A randomized lower bound needs one instance that remains hard after averaging over seeds.Source: §A.3 · p. 18
• A sufficient distributional statement fixes the prior before the method runs, allowing knowledge of the distribution but not its realization.The paper uses a uniform prior over the coordinate permutations in the cited feasible-set family.Source: §A.3 · p. 18

Prescribed trajectories

• Halbey et al. [2026a] construct horizon-dependent initializations giving Θ(1/t^2) objective gap over long segments for exact-line-search or short-step Frank–Wolfe.This establishes sharpness for those updates, not a lower bound for unrestricted LMO methods.Source: §A.4 · p. 18

Scope of the sensitivity analysis

• The sensitivity analysis applies only to exact-line-search segments satisfying the slow-envelope condition at every step, not to portions outside that condition.The slow segments have residual distance r_t = Θ(1/t).Source: §A.4 · p. 19

Initialization sensitivity

• A transverse perturbation changes sign and approximately doubles in one slow step, while the tangent direction has eigenvalue 1.The limiting Jacobian has transverse eigenvalue −2; variation across steps contributes only a polynomial factor to the amplification estimate.Source: §A.4 · pp. 19–20
• log2 σ_T = T + O(log T): along a prescribed slow segment, initialization sensitivity grows exponentially, with roughly one additional binary digit needed per iteration.The estimate is worst-case and linearized; it does not imply that every lower-precision run fails.Source: §A.4 · pp. 19–20

Eventual slow trajectories

• The set of initializations whose trajectories never reach the optimizer and eventually satisfy the slow-envelope condition has measure zero, though it is uncountable.An initialization distribution absolutely continuous with respect to area assigns this set probability zero; the result concerns infinite trajectories, not a prescribed finite horizon.Source: §A.4 · pp. 20–21

Measure of hard initializations

• The measure of all hard initializations remains unresolved: the finite-horizon argument gives positive measure at fixed accuracies but no uniform lower bound as accuracy tends to zero.The limit of the hard-initialization probability is unknown; settling it would require a global estimate on escape or on inverse histories that remain hard.Source: §A.4 · p. 21

A.5.1 Exact polar dynamics

• The polar state (r, θ) records distance to the optimizer and residual orientation, and exact line search yields a two-dimensional recurrence for its evolution.For the stated noncollinear slow-construction states, the step size lies in (0, 1), so clipping to the Frank–Wolfe segment has no effect.Source: §A.5.1 · pp. 21–22

A.5.2 The slow curve and its Jacobian

• r_t = Θ((t + 1)^−1) along the slow curve, whose leading angular coefficient is 1/3.The slow-curve substitution gives s = 1 + O(r), s_r = −2 + O(r), and s_θ = 2 + O(r).Source: §A.5.2 · pp. 22–23

A.5.3 Products of the varying Jacobians

• The limiting Jacobian has tangent eigenvalue 1 and transverse eigenvalue −2, and the varying Jacobians preserve a cone around the transverse direction.Products of the transverse expansion factors give sensitivity growth 2^T times polynomial factors.Source: §A.5.3 · pp. 23–24
• A radius-u initialization uncertainty has worst-case first-order trajectory error uΛ_T, yielding a linearized precision requirement of T + O(log T) binary digits for fixed or polynomially shrinking tolerance.The same leading exponent holds in Cartesian coordinates; coordinate conversion changes the required digits by O(log T).Source: §A.5.3 · p. 24

A.5.4 Nonlinear bounds for additive state perturbations

• Theorem A.5 considers a finite-horizon trajectory with additive errors in the polar state coordinates and guarantees that every perturbed state remains in the polar-map domain under its stated conditions.The theorem’s constants are independent of T, but the supplied passage does not specify the bound’s full formula.Source: §A.5.4 · pp. 24–25
• The constants need not remain uniform as the starting radius tends to zero independently of T; at time zero, the allowed error is ηr_0^3.The result is a sufficient bound for the displayed additive-error model, not a necessary threshold.Source: §A.5.4 · p. 26

A.5.5 Zero area for the eventual slow envelope

• The exact recurrence identifies eventual membership in the envelope with the stated slow condition, enabling the area argument through shrinking preimage sets.The envelope’s surviving area decreases geometrically under iteration.Source: §A.5.5 · p. 27
• The set of initializations whose trajectories never reach the optimizer and eventually satisfy the slow envelope has two-dimensional Lebesgue measure zero, yet is uncountable.Every sufficiently small positive initial radius admits such a trajectory, and its asymptotic scaled objective satisfies t^2 f(x_t) → 9/16.Source: §A.5.5 · pp. 27, 29

B Example of compatible assignments and swaps

• In the d = 5 example, two LMO answers leave four compatible reduced permutations after revealing two assignments and imposing one lower bound.The second answer adds Π(4) ≥ 2 even though its only active coordinate is already known.Source: B Example of compatible assignments… · p. 29
• Figure 1 distinguishes the generating assignment from the full compatible set; the shaded cell is excluded by the second answer.Columns show reduced indices and original ranks, while rows show coordinate indices and their compressed bounds.Source: B Example of compatible assignments… · p. 29, Figure 1 · p. 30

• The four compatible reduced permutations form a swap graph with two outgoing exchanges per vertex, for eight directed edges total.Source: §B.1 · p. 30
• Querying p=e3 yields three distinct numerical answers, so answer classes are determined exactly by the first reduced column.Source: §B.1 · p. 30
• After the query, k=1 leaves two compatible assignments, whereas k=3 or 5 leaves one, even though two coordinates remain inactive.Source: §B.1 · p. 30
• Under the conditional uniform law, k=1, 3, and 5 occur with probabilities 1/2, 1/4, and 1/4; six of eight directed edges cross answer classes, giving an average decrease of 6/4=3/2.Source: §B.1 · p. 31