pith. sign in

arxiv: 2605.10595 · v2 · pith:IJQDH27Xnew · submitted 2026-05-11 · 🧮 math.OC

Curvature-Dependent Lower Bounds for Frank-Wolfe

Jannis Halbey , Christophe Roux , Sebastian Pokutta This is my paper

Pith reviewed 2026-05-20 22:06 UTC · model grok-4.3

classification 🧮 math.OC
keywords Frank-Wolfe algorithmlower boundsp-uniform convexityconvergence ratesconvex optimizationHolderian error bounds
0
0 comments X

The pith

Frank-Wolfe admits no better convergence rate than order T to the minus p over p minus 1 on p-uniformly convex sets for p at least 3.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that the Frank-Wolfe algorithm cannot converge faster than order T to the power of minus p over p minus 1 when the feasible set is p-uniformly convex and p is at least 3. This rate matches the best known upper bound, so the acceleration gained from curvature is optimal under standard step rules. The argument works by tracking how the algorithm's iterates move on a few carefully chosen low-dimensional examples. The same lower bound is shown to hold when the objective satisfies only a Holderian error bound instead of full convexity.

Core claim

By tracking the trajectory of Frank-Wolfe iterates on elementary test problems, the authors prove an Omega of T to the power of minus p over p minus 1 lower bound that matches the O of T to the power of minus p over p minus 1 upper bound for every p greater than or equal to 3. The same lower bound applies to problems whose objective satisfies a Holderian error bound.

What carries the argument

The dynamics of Frank-Wolfe iterates on simple instances that serve as worst-case examples for the class of p-uniformly convex sets.

Load-bearing premise

The simple instances analyzed are the worst-case problems for the entire class of p-uniformly convex sets.

What would settle it

A run of Frank-Wolfe with exact line search on one of the paper's simple instances that reaches a faster rate than T to the power of minus p over p minus 1 would contradict the lower bound.

Figures

Figures reproduced from arXiv: 2605.10595 by Christophe Roux, Jannis Halbey, Sebastian Pokutta.

Figure 1
Figure 1. Figure 1: Exact-line-search FW trajectories in the (u, w)-plane for four random initializations for the projection problem (1), i.e., minx∈Bp ∥x − e1∥ 2 with p ≥ 3. Across runs, u remains positive and controls the distance to the optimum, while w alternates sign and contracts faster. the one-step update of the scaled variable y, y ′ = Φ(u, y) def = |w ′ | (u ′) 1+α , (4) where u ′ and w ′ are the new values of u and… view at source ↗
Figure 2
Figure 2. Figure 2: Three coordinate views of FW with exact line search on Bp, p = 3, for f(x) = ∥x − e1∥ 2 2 , run from the slow-start initialization (5) with u0 = 3 4 (open circle). Left: original coordinates (x1, x2), with the optimum e1 (gold star) and ∂Bp (dashed). Middle: the recentered coordinates (u, w) = (1 − x1, x2) shift e1 to the origin and turn f into a quadratic centered at 0, but the iterates still cluster in a… view at source ↗
Figure 3
Figure 3. Figure 3: Heatmaps showing the number of FW iterations required to reach the target accuracy (10−4 ), initialized from all feasible points in the open p-unit ball in R 2 . Each panel corresponds to a different value of p. Darker colors correspond to fewer iterations. The heatmap for p = 3 shows clear strips of high iteration counts, where the widest strips contain the fixed point curve y ∗ (u). The case of p = 3.1 i… view at source ↗
Figure 4
Figure 4. Figure 4: Comparison of the primal gap f(xT ) − f(x ∗ ) versus iteration T for exact-line-search FW on the minimization problem in (1) for p ∈ {3, 5}. The solid curve uses the slow initialization (5), while the faint curves are runs from generic initializations. The dashed line shows T −p/(p−1), which matches both our lower bound from Theorem 4 and the upper bound rate of Kerdreux et al. (2021a). (see Proposition 15… view at source ↗
Figure 5
Figure 5. Figure 5: Comparison of the primal gap g(xT ) − g(x ∗ ) versus iteration T for exact-line-search FW for minimizing (9) on Bp for p ∈ {3, 5} and θ ∈ { 1 3 , 1 4 }. The solid curve uses the slow initialization (5), while the faint curves are runs from generic initializations. The dotted reference line shows the Ω [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
read the original abstract

The Frank-Wolfe algorithm achieves a convergence rate of $\mathcal{O}(1/T)$ for smooth convex optimization over compact convex domains, accelerating to $\mathcal{O}(1/T^2)$ when both the objective and the feasible set are strongly convex. This acceleration extends beyond strong convexity: Kerdreux et al. (2021a) proved rates of $\mathcal{O}(T^{-p/(p-1)})$ over $p$-uniformly convex feasible sets, a class that interpolates between strongly convex sets and more general curved domains such as $\ell_p$ balls. In this work, we establish a matching $\Omega(T^{-p/(p-1)})$ lower bound for every $p\ge 3$ under exact line search or short steps, and extend the lower bound to objectives satisfying a H\"olderian error bound. The proofs analyze the dynamics of Frank-Wolfe iterates on simple instances and hence are not limited to the high-dimensional setting, unlike information-theoretic lower bounds.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript establishes matching lower bounds of order Ω(T^{-p/(p-1)}) for the Frank-Wolfe algorithm with exact line search or short steps when the feasible set is p-uniformly convex for every p ≥ 3. The proofs proceed by constructing and analyzing the dynamics of the iterates on simple, low-dimensional instances that satisfy the required curvature condition. The work further extends the lower bound to objectives obeying a Hölderian error bound. Unlike information-theoretic arguments, the approach is not restricted to high dimensions.

Significance. If the explicit constructions are correct, the result is significant because it demonstrates tightness of the O(T^{-p/(p-1)}) upper bounds previously obtained by Kerdreich et al. (2021a) for Frank-Wolfe on the interpolated class of p-uniformly convex sets. The use of concrete, low-dimensional instances rather than abstract minimax arguments is a methodological strength: it yields constructive, verifiable lower bounds and directly exhibits the worst-case dynamics. The extension to Hölderian error bounds broadens the scope without altering the core proof technique.

minor comments (2)
  1. The abstract states that the instances are 'simple' but does not indicate their dimension; adding a brief parenthetical remark (e.g., 'in dimension 2 or 3') would help readers immediately gauge the construction's simplicity.
  2. In the statement of the Hölderian-error-bound extension, the precise relation between the Hölder exponent and the resulting rate should be written explicitly (rather than left implicit) to avoid any ambiguity when comparing with the p-uniform-convexity case.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation for minor revision. We appreciate the recognition that our constructive, low-dimensional lower-bound instances provide a verifiable and dimension-independent complement to existing upper bounds.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes matching lower bounds by directly constructing and analyzing the explicit dynamics of Frank-Wolfe iterates on simple low-dimensional instances that satisfy p-uniform convexity (p≥3) and the Hölderian error bound. This is a standard, self-contained proof technique for rate tightness that requires only existence of at least one hard instance in the class; it does not reduce any claim to a fitted parameter, self-referential definition, or load-bearing self-citation chain. The derivation relies on direct computation of iterate behavior rather than importing uniqueness or ansatz from prior self-work, making the result independent of the cited upper-bound results.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the standard definition of p-uniform convexity for p ≥ 3 and the assumption that simple constructed instances capture worst-case behavior; no free parameters or new entities are introduced.

axioms (2)
  • domain assumption Feasible set is p-uniformly convex for p ≥ 3
    This is the precise class of domains for which the lower bound is claimed.
  • domain assumption Objective is smooth and convex (or satisfies Hölderian error bound)
    Standard assumption inherited from the Frank-Wolfe setting and the cited upper-bound work.

pith-pipeline@v0.9.0 · 5702 in / 1299 out tokens · 76373 ms · 2026-05-20T22:06:35.964606+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    2026 , eprint=

    The Agentic Researcher: A Practical Guide to AI-Assisted Research in Mathematics and Machine Learning , author=. 2026 , eprint=

    work page 2026

  2. [2]

    2026 , eprint=

    Lower Bounds for Frank-Wolfe on Strongly Convex Sets , author=. 2026 , eprint=

    work page 2026

  3. [3]

    2026 , eprint=

    Frank-Wolfe Beyond 1/t Convergence , author=. 2026 , eprint=

    work page 2026

  4. [4]

    Taylor and Julien M

    Adrien B. Taylor and Julien M. Hendrickx and Fran. Smooth strongly convex interpolation and exact worst-case performance of first-order methods , url =. doi:10.1007/S10107-016-1009-3 , journal =

    work page doi:10.1007/s10107-016-1009-3

  5. [5]

    Performance of first-order methods for smooth convex minimization: a novel approach , url =

    Yoel Drori and Marc Teboulle , doi =. Performance of first-order methods for smooth convex minimization: a novel approach , url =. Math. Program. , number =

    work page

  6. [6]

    An algorithm for quadratic programming , volume =

    Frank, Marguerite and Wolfe, Philip , journal =. An algorithm for quadratic programming , volume =

    work page

  7. [7]

    Proceedings of The 26th International Conference on Artificial Intelligence and Statistics , pages =

    Acceleration of Frank-Wolfe Algorithms with Open-Loop Step-Sizes , author =. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics , pages =. 2023 , editor =

    work page 2023

  8. [8]

    Optimized projection-free algorithms for online learning: construction and worst-case analysis , year =

    Weibel, Julien and Gaillard, Pierre and Koolen, Wouter M and Taylor, Adrien , journal =. Optimized projection-free algorithms for online learning: construction and worst-case analysis , year =

    work page

  9. [9]

    Convergence theory in nonlinear programming , year =

    Wolfe, Philip , booktitle =. Convergence theory in nonlinear programming , year =

    work page

  10. [10]

    Revisiting

    Jaggi, Martin , booktitle =. Revisiting. 2013 , editor =

    work page 2013

  11. [11]

    Canon, M. D. and Cullum, C. D. , title =. SIAM Journal on Control , volume =. 1968 , doi =

    work page 1968

  12. [12]

    Performance Estimation for Smooth and Strongly Convex Sets , year =

    Alan Luner and Benjamin Grimmer , journal =. Performance Estimation for Smooth and Strongly Convex Sets , year =

    work page

  13. [13]

    The complexity of large-scale convex programming under a linear optimization oracle , year =

    Lan, Guanghui , journal =. The complexity of large-scale convex programming under a linear optimization oracle , year =

    work page

  14. [14]

    Problem Complexity and Method Efficiency in Optimization , year =

    Nemirovski, Arkadi. Problem Complexity and Method Efficiency in Optimization , year =

    work page

  15. [15]

    Proceedings of the 32nd International Conference on Machine Learning , pages =

    Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets , author =. Proceedings of the 32nd International Conference on Machine Learning , pages =. 2015 , editor =

    work page 2015

  16. [16]

    and Carderera, A

    Braun, G. and Carderera, A. and Combettes, C.W. and Hassani, H. and Karbasi, A. and Mokhtari, A. and Pokutta, S. , isbn =. Conditional Gradient Methods:

    work page

  17. [17]

    Proceedings of The 24th International Conference on Artificial Intelligence and Statistics , pages =

    Projection-Free Optimization on Uniformly Convex Sets , author =. Proceedings of The 24th International Conference on Artificial Intelligence and Statistics , pages =. 2021 , editor =

    work page 2021

  18. [18]

    Proceedings of the 38th International Conference on Machine Learning , pages =

    Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets , author =. Proceedings of the 38th International Conference on Machine Learning , pages =. 2021 , editor =

    work page 2021

  19. [19]

    Constrained minimization methods , volume =

    Levitin, Evgeny S and Polyak, Boris T , journal =. Constrained minimization methods , volume =

    work page

  20. [20]

    CoRR , title =

    Christophe Roux and Max Zimmer and Alexandre d'Aspremont and Sebastian Pokutta , doi =. CoRR , title =. 2510.13713 , eprinttype =

    work page arXiv

  21. [21]

    Faster Projection-free Convex Optimization over the Spectrahedron , url =

    Garber, Dan and Garber, Dan , booktitle =. Faster Projection-free Convex Optimization over the Spectrahedron , url =

    work page

  22. [22]

    Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm , url =

    Luise, Giulia and Salzo, Saverio and Pontil, Massimiliano and Ciliberto, Carlo , booktitle =. Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm , url =

    work page

  23. [23]

    In: 22nd International Symposium on Experimental Algorithms

    Deborah Hendrych and Mathieu Besan. Solving the Optimal Experiment Design Problem with Mixed-Integer Convex Methods , url =. 22nd International Symposium on Experimental Algorithms,. doi:10.4230/LIPICS.SEA.2024.16 , editor =

    work page doi:10.4230/lipics.sea.2024.16 2024

  24. [24]

    2026 , eprint=

    Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets , author=. 2026 , eprint=

    work page 2026

  25. [25]

    2020 , url =

    Vincent Roulet and Alexandre d'Aspremont , title =. 2020 , url =. doi:10.1137/18M1224568 , timestamp =

    work page doi:10.1137/18m1224568 2020