Pith. sign in

REVIEW 2 major objections 4 minor 2 cited by

This paper proves that any deterministic method using a linear minimization oracle needs at least Ω(√(L·diam(S)²/ε)) iterations to reach ε-suboptimality on strongly convex constraint sets, matching the existing accelerated Frank-Wolfe upper

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Provably, no deterministic gradient-plus-linear-oracle method can beat the accelerated quadratic 1/T² rate of Frank-Wolfe over strongly convex constraint sets.

T0 review reviewed 2026-08-02 challenge →

load-bearing objection Good new LMO zero-chain machinery, but the main optimality claim does not follow from the theorem as stated because the constructed diameter shrinks with the iteration budget. the 2 major comments →

arxiv 2602.22608 v2 pith:DL5AK2RU submitted 2026-02-26 math.OC

Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets

Benjamin Grimmer , Ning Liu This is my paper
classification math.OC MSC 90C2590C60
keywords linear minimization oracleFrank-Wolfezero-chainstrongly convex setsoracle complexitylower boundprojection-free optimizationconvex optimization
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The reading

The paper establishes a lower bound on the oracle complexity of constrained convex optimization when the only access to the feasible set is a linear minimization oracle (LMO) and the objective is smooth and strongly convex. It shows that over strongly convex feasible sets, any deterministic method requires Ω(√(L·diam(S)²/ε)) iterations to reach an objective gap of ε, and that this rate is optimal up to constants because it matches the best known accelerated Frank-Wolfe guarantee. The proof constructs hard instances whose LMO reveals only one coordinate of the solution per query, a zero-chain property, and then uses an adaptive 'resisting oracle' to defeat any deterministic method, not just span-based ones. A secondary result shows that if the feasible set is only modestly smooth (β = Ω(1/√ε)), no improvement over the general convex rate is possible for span-based LMO methods.

Core claim

The central claim, stated as Theorem 1.1, is that for any iteration budget T and any L, α > 0, there exists an α-strongly convex set S and an L-smooth, L-strongly convex function f in dimension d = 2(T+1) such that every deterministic FO-LMO method initialized at zero either produces an infeasible point after T iterations or has objective gap at least (1/528)·L·diam(S)²/(T+1)². Consequently, any algorithm in this class needs Ω(√(L·diam(S)²/ε)) iterations to ensure ε-suboptimality. This matches the upper bound previously known for accelerated Frank-Wolfe in its dependence on diameter, establishing the order-optimal worst-case complexity for deterministic LMO methods over strongly convex sets.

What carries the argument

The key construction is a hard feasible set S = { x : ½∥x∥² + Σᵢ wᵢ|xᵢ| ≤ C² } with wᵢ = C√(2i). Its linear minimization oracle is an explicit soft-thresholding operator zᵢ = −sign(pᵢ)·max(0, |pᵢ|/λ − wᵢ), where λ is the KKT multiplier. Because adjacent weights satisfy wₜ₊₁² − wₜ² = 2C², a search direction that is constant on a tail of coordinates cannot cause the LMO to activate a coordinate beyond the first unassigned one without violating feasibility; this gives a zero-chain property: exactly one new coordinate is revealed per query. To handle arbitrary deterministic methods, the paper introduces a family of permuted sets and a resisting oracle that assigns the permutation online, choosin

Load-bearing premise

The entire lower bound rests on the zero-chain property of the constructed feasible set: its linear minimization oracle can activate at most one previously zero coordinate per query, and this depends on the specific weight sequence wᵢ = C√(2i) satisfying wₜ₊₁² − wₜ² = 2C²; if any valid search direction could cause the LMO to activate two new coordinates at once, the hard-instance construction would fail.

What would settle it

Compute the LMO on the paper's set S with a search direction p that is zero on coordinate 1 and equal to a constant σ on coordinates 2, 3, and 4, choosing σ so that the soft-threshold formula (2.9) returns positive values for coordinates 2 and 3 simultaneously; if such a query exists, the zero-chain lemma is false. Alternatively, exhibit a concrete deterministic FO-LMO method that, on the specific constructed instance with d = 2(T+1), produces a feasible point with objective gap below (1/528)·L·diam(S)²/(T+1)² in T iterations, which would directly contradict Theorem 1.1.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • The accelerated Frank-Wolfe rate O(√(L·diam(S)²/ε)) is optimal up to constants for all deterministic first-order methods using a linear minimization oracle over strongly convex sets.
  • Strong convexity of the feasible set does not enable linear convergence for LMO-based methods, even when the objective is a perfectly conditioned quadratic.
  • Away-step, pairwise, fully corrective, and other Frank-Wolfe variants cannot beat the Ω(1/T²) rate in the worst case over strongly convex sets.
  • For span-based LMO methods, feasible sets whose smoothness is only modest (β = Ω(1/√ε)) yield no improvement over the general convex-set complexity, so acceleration requires stronger smoothness.
  • The lower bound applies to all deterministic FO-LMO methods, not just those whose iterates lie in the convex hull of previous LMO points.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The one-coordinate-per-query mechanism suggests that the rate is fundamentally tied to how many extreme points an LMO can expose in one call; methods that make several LMO queries per iteration or use a projection oracle may circumvent this bound, but they fall outside the paper's model.
  • The resisting-oracle technique could likely be adapted via Yao's principle to give lower bounds for randomized LMO methods by placing a uniform distribution over permutations, although the paper only treats deterministic methods.
  • The slack between the lower bound constant 1/528 and the known upper bound constant 9/2 leaves room for tightening the exact minimax constant, perhaps through performance-estimation techniques similar to those used in unconstrained optimization.
  • The smooth-set extension indicates that the boundary smoothness needed to accelerate strongly convex problems scales with the target accuracy; if β ≫ 1/√ε, the lower bound becomes vacuous, leaving open the possibility of better rates for very smooth sets.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies deterministic first-order methods that use a Linear Minimization Oracle (FO-LMO) for constrained convex optimization over strongly convex sets. Its main claimed contribution is a lower bound of Ω(√(L diam(S)²/ε)) iterations for any such method, matching the accelerated Frank–Wolfe upper bound of Garber and Hazan. The construction is a zero-chain hard instance built from a strongly convex set S of the form {x : ½‖x‖² + Σ w_i|x_i| ≤ C²}, with objective f(x)=½‖x−ν1‖². Section 2 proves a lower bound for span-based LMO methods; Section 3 extends the argument to all deterministic FO-LMO methods via a resisting oracle that assigns coordinates to a permutation adaptively; Section 4 gives extensions to modestly smooth sets using Minkowski smoothing.

Significance. The paper contains a technically interesting and novel element: the soft-thresholding LMO formula (2.9) and the zero-chain argument (Lemmas 2.4 and 3.2) are correct and carefully verified. The idea of constructing a strongly convex feasible set whose LMO reveals only one coordinate per query is a valuable contribution to the lower-bound toolbox. The explicit constants and the transparent proof style are also strengths. However, the advertised optimality claim is not supported by the construction as it stands, for reasons detailed below. If a fixed-diameter version of this construction existed, the result would be a major advance; the current paper does not provide it.

major comments (2)
  1. [Theorem 1.1 and Lemma 2.2] The lower bound is stated as (1/528) L diam(S)²/(T+1)², but diam(S) is not independent of T. From (2.7) and Lemma 2.2, C = 1/√(d²+d+2) and diam(S)=2C(2−√2)=Θ(1/d). Since Theorem 1.1 sets d=2(T+1), we have diam(S_T)=Θ(1/T), so the lower bound is Θ(L/T⁴), not Ω(L/T²). The 'Consequently' bound T ≥ √(L diam(S)²/(528ε)) is self-referential: substituting diam(S_T)~1/T gives T=Ω(ε^{-1/4}), not Ω(ε^{-1/2}). Meanwhile the Garber–Hazan upper bound on these same instances is O(L(diam²+1/α²)/T²)=O(L/T²) for L=α=1. Thus the lower bound does not contradict any method achieving the alleged optimal rate. The caveat after Theorem 1.1 admits this, but the abstract and introduction still claim a matching optimal bound. This is a load-bearing gap.
  2. [Section 3.3, Theorem 1.1] The theorem is stated as ∃(S,f) such that every FO-LMO method fails. However, the proof uses a resisting oracle that selects the permutation π in response to the algorithm's queries. The final permutation π⋆ (and therefore S) depends on the method. The proof establishes the standard ∀method ∃instance form, not the stated ∃instance ∀method form. As written, the theorem is false: for a fixed (S,f), a method can output the minimizer after one oracle call (e.g., query z₁ and set x₁=x⋆). The quantification should be restated in the conventional way, or the model must explicitly forbid instance-dependent methods.
minor comments (4)
  1. [Section 2.1] The rescaling notation is slightly confusing: if s̃=(1/α)S, then for x∈s̃ one needs αx∈S; this is true but should be stated explicitly for clarity.
  2. [Section 4.1] The simplex construction relies on an adversarial LMO that returns the attaining basis vector with minimal index, but this oracle is not formally specified. A brief definition would improve reproducibility.
  3. [Theorem 4.1] The bound (4.1) contains the term diam(Sβ)−2/β, which can be negative for large β; the max{0,·} makes the bound vacuous in that regime. It may be worth emphasizing that the meaningful regime is β=Ω(1/√ε), as the text already notes.
  4. [Throughout] There are a few minor typos and notational inconsistencies (e.g., the proof of Lemma 2.4 uses 'strict inequality... contradicting feasibility' without explicitly summing all coordinates). These are easy to fix and do not affect the technical results.

Circularity Check

0 steps flagged

No significant circularity: the zero-chain lower-bound construction is self-contained and the Garber–Hazan comparison is external framing. The main caveat is that diam(S) is tied to the dimension/T, so the fixed-diameter iteration claim is weaker than stated, but this is a quantifier/strength issue, not a circular reduction.

full rationale

The core derivation is not circular. The hard set S in (2.6)-(2.7) and objective f in Section 2.1 are defined by explicit formulas (C, w_i, the boundary root nu in (2.8) and rho in (3.3)); Lemmas 2.1-2.4 and 3.1-3.2 prove strong convexity, diameter, and the zero-chain property directly from those formulas. The final lower bounds in Theorems 2.1 and 1.1 follow by substitution (e.g., (2.10) plus the bound on nu^2), with no parameter fitted to the quantity being predicted. Garber-Hazan [1] is used only as an external upper-bound benchmark after the lower bound is proved, so the matching claim is framing rather than an input. Self-citations ([4], [20], [25], [26], [29]) occur in related-work/context and in the secondary smoothing section ([4, Lemma 9] for Minkowski-sum calculus); they are not the source of the main construction and are not load-bearing for Theorem 1.1. One limitation is explicitly stated after Theorem 1.1: 'it does not allow a free selection of diam(S)... diam(S) = Theta(1/alpha d).' Because d=2(T+1), the 'Consequently' bound T >= sqrt(L diam(S)^2/(528 epsilon)) - 1 has T on both sides after substituting diam(S)=Theta(1/T), so it yields only T=Omega((L/epsilon)^{1/4}) for these instances rather than a fixed-diameter Omega(sqrt(L D^2/epsilon)) complexity. This is a substantive strength/quantifier caveat, but it is not circular: the theorem's per-instance lower bound is derived independently and remains valid as stated.

Axiom & Free-Parameter Ledger

4 free parameters · 7 axioms · 2 invented entities

The central lower bound is a construction, not a fit: every numeric constant (C, w_i, ν, ρ) is determined by closed-form equations or explicit formulas whose only role is to produce a single hard instance; the theorem then quantifies over all methods. The proof imports standard tools (KKT/Slater, intersection-preservation of set strong convexity [3], the NY resisting-oracle paradigm [14], variance identities) and two results from the authors' own prior work ([4] Minkowski-sum set calculus in §4; [20] PEP survey used only as motivation). No parameter is fitted to Garber–Hazan's rate; the lower bound would stand even if GH were unknown.

free parameters (4)
  • weight sequence w_i = C√(2i) = w_i = C√(2i), i = 1..d
    Hand-designed so adjacent squared weights differ by exactly 2C², producing the one-coordinate-per-query zero-chain contradiction in Lemmas 2.4/3.2; also makes S an intersection of unit balls. Construction choice, not a fit to the target result.
  • normalization constant C = C = 1/√(d²+d+2)
    Chosen so the shifted-ball representation has radius 1 (Lemma 2.1) and so Σw_i² = C²(d²+d); it sets the diam(S) scale (Lemma 2.2) and enters the final constant. Normalization choice.
  • scalar ρ (permuted family) = unique root of (3.3), bounded below by 2/d²
    Determined by the feasibility/boundary equation (3.3), not fitted; controls the minimizer x*_i = ρ(w_d − w_π(i)).
  • ν (unpermuted minimizer shift) = unique positive root of (2.8)
    Determined by the boundary equation (2.8); only its lower bound ν ≥ 9C²/(8(d+2)³) is used.
axioms (7)
  • standard math KKT conditions and Slater's condition hold for the LMO subproblem min{⟨p,x⟩ : h(x) ≤ C²} (Lemma 2.3)
    Justifies the soft-thresholding form (2.9); h is nonsmooth (l1 term) but subgradient KKT is standard.
  • standard math Strong convexity of sets is preserved under arbitrary intersections (Vial [3, Prop. 2])
    Used in Lemma 2.1 to show S is an intersection of shifted unit balls.
  • domain assumption The deterministic FO-LMO oracle model: exact gradients, exact LMO selections, one pair of calls per iteration, iterates may be infeasible
    Defines the scope of Theorem 1.1 (Section 1); randomized or adaptive-noise oracles are out of scope.
  • domain assumption The resisting-oracle paradigm: an online adversary may complete the instance (permutation π) as a function of the method's queries (Nemirovski–Yudin [14])
    Engine of Section 3; yields the ∀method∃instance form actually proven.
  • domain assumption Set-calculus for Minkowski smoothing: S+B(0,1/β) is β-smooth, and LMO_{S+B} = LMO_S − p/(β‖p‖) (Liu–Grimmer [4, Lemma 9])
    Basis of Section 4; imported from the authors' own prior work (self-citation), an external standard result.
  • standard math Variance identities: Var of m contiguous integers is (m²−1)/12, and Var{√k} ≥ (m²−1)/(48d) via (√i−√j)² ≥ (i−j)²/(4d)
    Final averaging argument of §3.3; algebra verified.
  • domain assumption The simplex zero-chain property of Lan [12] (each LMO query on the simplex reveals at most one extreme point)
    Imported for Theorem 4.1's smoothed-simplex construction.
invented entities (2)
  • resisting LMO adversary (runtime permutation assignment) no independent evidence
    purpose: Defines the hard instance online so that every deterministic FO-LMO method learns at most one coordinate per query; removes the span restriction.
    A standard adversarial proof device in the Nemirovski–Yudin tradition, not a physical postulate; it commits to a method-dependent instance, which is the source of the ∃∀/∀∃ quantifier subtlety.
  • zero-chain strongly convex constraint set S = {x : ½‖x‖² + Σ w_i|x_i| ≤ C²} no independent evidence
    purpose: The constructed hard feasible region whose LMO is exact soft-thresholding, leaking one coordinate per query.
    A mathematical construction with explicit parameters (2.6)–(2.7); its validity is verified by Lemmas 2.1–2.2.

reviewed 2026-08-02 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets." pith.science (2026). https://pith.science/paper/DL5AK2RU

@misc{pith2026260222608,
  author       = {Pith},
  title        = {Pith review of: Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DL5AK2RU}},
  note         = {Machine review of arXiv:2602.22608}
}
Share X Bluesky LinkedIn Reddit HN
abstract

We consider the oracle complexity of constrained convex optimization given access to a Linear Minimization Oracle (LMO) for the constraint set and a gradient oracle for the $L$-smooth, $L$-strongly convex objective. This model includes Frank-Wolfe methods and their many variants. Over the problem class of $\alpha$-strongly convex constraint sets $S$, we demonstrate that one can construct hard ``zero-chain'' instances in the classical style of Nemirovski and Yudin. From our new approach to adversarial oracle construction, we prove that no such deterministic method can guarantee a final objective gap less than $\varepsilon$ in fewer than $\Omega(\sqrt{L\, \mathrm{diam}(S)^2/\varepsilon})$ iterations. Our lower bound partly matches the accelerated Frank-Wolfe theory of Garber and Hazan (2015) of $O(\sqrt{L(\mathrm{diam}(S)^2+1/\alpha^2)/\varepsilon})$. Second, we consider optimization over $\beta$-smooth sets, finding that in the modestly smooth regime of $\beta=\Omega(1/\sqrt{\varepsilon})$, no complexity improvement for span-based LMO methods is possible against either compact convex sets or strongly convex sets.

discussion (0)

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

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Local LMO: Constrained Gradient Optimization via a Local Linear Minimization Oracle

    math.OC 2026-05 unverdicted novelty 8.0

    Local LMO is a new projection-free method that achieves the convergence rates of projected gradient descent for constrained optimization by using local linear minimization oracles over small balls.

  2. A conditional-gradient-based single-loop augmented Lagrangian method for inequality constrained optimization

    math.OC 2026-05 unverdicted novelty 5.0

    A conditional-gradient single-loop augmented Lagrangian method achieves optimal convergence rates for minimizing a Lipschitz differentiable convex f plus convex h subject to smooth convex inequalities.

Reference graph

Works this paper leans on

29 extracted references · 3 linked inside Pith · cited by 2 Pith papers

  1. [1]

    Faster rates for the Frank-Wolfe method over strongly-convex sets

    Dan Garber and Elad Hazan. Faster rates for the Frank-Wolfe method over strongly-convex sets. In Proceedings of the 32nd International Conference on Machine Learning, volume 37, pages 541–549. PMLR, 2015

    2015

  2. [2]

    Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Sebastian Pokutta.Conditional gradient methods: From core principles to AI applications

    Gábor Braun, Alejandro Carderera, Cyrille W. Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Sebastian Pokutta.Conditional gradient methods: From core principles to AI applications. MOS-SIAM Series on Optimization. SIAM, 2025

    2025

  3. [3]

    Strong convexity of sets and functions.Journal of Mathematical Economics, 9(1-2):187–205, 1982

    Jean-Philippe Vial. Strong convexity of sets and functions.Journal of Mathematical Economics, 9(1-2):187–205, 1982

    1982

  4. [4]

    Gauges and accelerated optimization over smooth and/or strongly convex sets, 2023

    Ning Liu and Benjamin Grimmer. Gauges and accelerated optimization over smooth and/or strongly convex sets, 2023. arXiv:2303.05037

    arXiv 2023

  5. [5]

    On the global linear convergence of Frank-Wolfe optimization variants.Advances in neural information processing systems, 28, 2015

    Simon Lacoste-Julien and Martin Jaggi. On the global linear convergence of Frank-Wolfe optimization variants.Advances in neural information processing systems, 28, 2015

    2015

  6. [6]

    Linearly convergent away-step conditional gradient for non-strongly convex functions.Mathematical Programming, 164(1):1–27, 2017

    Amir Beck and Shimrit Shtern. Linearly convergent away-step conditional gradient for non-strongly convex functions.Mathematical Programming, 164(1):1–27, 2017

    2017

  7. [7]

    Pairwise conditional gradients without swap steps and sparser kernel herding

    Kazuma K Tsuji, Ken’ichiro Tanaka, and Sebastian Pokutta. Pairwise conditional gradients without swap steps and sparser kernel herding. InInternational Conference on Machine Learning, pages 21864–21883. PMLR, 2022

    2022

  8. [8]

    An extension of the Frank and Wolfe method of feasible directions.Mathematical Programming, 6(1):14–27, 1974

    Charles A Holloway. An extension of the Frank and Wolfe method of feasible directions.Mathematical Programming, 6(1):14–27, 1974

    1974

  9. [9]

    Blended conditional gradients

    Gábor Braun, Sebastian Pokutta, Dan Tu, and Stephen Wright. Blended conditional gradients. In International conference on machine learning, pages 735–743. PMLR, 2019. 16

    2019

  10. [10]

    An algorithm for quadratic programming.Naval research logistics quarterly, 3(1-2):95–110, 1956

    Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming.Naval research logistics quarterly, 3(1-2):95–110, 1956

    1956

  11. [11]

    Revisiting Frank-Wolfe: Projection-free sparse convex optimization

    Martin Jaggi. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. InInternational conference on machine learning, pages 427–435. PMLR, 2013

    2013

  12. [12]

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

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

  13. [13]

    Lower bounds for Frank-Wolfe on strongly convex sets, 2026

    Jannis Halbey, Daniel Deza, Max Zimmer, Christophe Roux, Bartolomeo Stellato, and Sebastian Pokutta. Lower bounds for Frank-Wolfe on strongly convex sets, 2026. arXiv:2602.04378

    Pith/arXiv arXiv 2026

  14. [14]

    Wiley-Interscience Series in Discrete Mathematics

    Arkadij Semenovič Nemirovski and David Borisovich Yudin.Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Chichester, 1983

    1983

  15. [15]

    Performance of first-order methods for smooth convex minimization: a novel approach.Mathematical Programming, 145(1):451–482, 2014

    Yoel Drori and Marc Teboulle. Performance of first-order methods for smooth convex minimization: a novel approach.Mathematical Programming, 145(1):451–482, 2014

    2014

  16. [16]

    Smooth strongly convex interpolation and exact worst-case performance of first-order methods.Mathematical Programming, 161:307–345, 2017

    Adrien Taylor, Julien Hendrickx, and François Glineur. Smooth strongly convex interpolation and exact worst-case performance of first-order methods.Mathematical Programming, 161:307–345, 2017

    2017

  17. [17]

    Exact worst-case performance of first-order methods for composite convex optimization.SIAM Journal on Optimization, 27(3):1283–1313, 2017

    Adrien Taylor, Julien Hendrickx, and François Glineur. Exact worst-case performance of first-order methods for composite convex optimization.SIAM Journal on Optimization, 27(3):1283–1313, 2017

    2017

  18. [18]

    Optimized first-order methods for smooth convex minimization

    Donghwan Kim and Jeffrey A Fessler. Optimized first-order methods for smooth convex minimization. Mathematical programming, 159(1):81–107, 2016

    2016

  19. [19]

    The exact information-based complexity of smooth convex minimization.Journal of Complexity, 39:1–16, 2017

    Yoel Drori. The exact information-based complexity of smooth convex minimization.Journal of Complexity, 39:1–16, 2017

    2017

  20. [20]

    Performance estimation for smooth and strongly convex sets, 2024

    Alan Luner and Benjamin Grimmer. Performance estimation for smooth and strongly convex sets, 2024. arXiv:2410.14811

    Pith/arXiv arXiv 2024

  21. [21]

    Javier F. Peña. Affine invariant convergence rates of the conditional gradient method.SIAM Journal on Optimization, 33(4):2654–2674, 2023

    2023

  22. [22]

    Accelerated affine-invariant convergence rates of the Frank–Wolfe algorithm with open-loop step-sizes.Mathematical Programming, 214(1–2):201–245, 2025

    Elias Wirth, Javier Peña, and Sebastian Pokutta. Accelerated affine-invariant convergence rates of the Frank–Wolfe algorithm with open-loop step-sizes.Mathematical Programming, 214(1–2):201–245, 2025

    2025

  23. [23]

    Fast convergence of Frank-Wolfe algorithms on polytopes.Mathematics of Operations Research, 2025

    Elias Wirth, Javier Peña, and Sebastian Pokutta. Fast convergence of Frank-Wolfe algorithms on polytopes.Mathematics of Operations Research, 2025

    2025

  24. [24]

    Efficient

    James Renegar. “Efficient” Subgradient Methods for General Convex Optimization.SIAM Journal on Optimization, 26(4):2649–2676, 2016

    2016

  25. [25]

    Radial duality part i: foundations.Mathematical Programming, 205(1–2):33–68, 2024

    Benjamin Grimmer. Radial duality part i: foundations.Mathematical Programming, 205(1–2):33–68, 2024

    2024

  26. [26]

    Radial duality part ii: applications and algorithms.Mathematical Programming, 205(1–2):69–105, 2023

    Benjamin Grimmer. Radial duality part ii: applications and algorithms.Mathematical Programming, 205(1–2):69–105, 2023

    2023

  27. [27]

    Efficient projection-free online convex optimization with membership oracle

    Zakaria Mhammedi. Efficient projection-free online convex optimization with membership oracle. In Po-Ling Loh and Maxim Raginsky, editors,Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 ofProceedings of Machine Learning Research, pages 5314–5390, London, UK, 2022. PMLR

    2022

  28. [28]

    Projection-free adaptive regret with membership oracles

    Zhou Lu, Nataly Brukhim, Paula Gradu, and Elad Hazan. Projection-free adaptive regret with membership oracles. In Shipra Agrawal and Francesco Orabona, editors,International Conference on Algorithmic Learning Theory, February 20-23, 2023, Singapore, volume 201 ofProceedings of Machine Learning Research, pages 1055–1073, Singapore, 2023. PMLR

    2023

  29. [29]

    Scalable projection-free optimization methods via multira- dial duality theory, 2024

    Thabo Samakhoana and Benjamin Grimmer. Scalable projection-free optimization methods via multira- dial duality theory, 2024. arXiv:2403.13688. 17

    Pith/arXiv arXiv 2024

This paper was first reviewed by deepseek-v4-flash on August 2, 2026.