Pith. sign in

REVIEW 3 major objections 5 minor 10 references

A Linearly Convergent Projection-Free Algorithm for Smooth Convex Sets

T0 review · 3 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

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

Pith's one-line read For a smooth convex feasible set, replacing projection by one gradient and one supporting-tangent computation per iteration preserves linear convergence; with membership queries only, the tangent costs O(d log Qε) queries per step.

desk verdict The exact-tangent half is clean and genuinely new; the membership-query half leans on an external theorem that a referee should verify. read the letter →

arxiv 2608.04321 v1 pith:4VC26TMH submitted 2026-08-05 math.OC

Elad Hazan This is my paper · ORCID
classification math.OC MSC 90C2568W40
keywords projection-freeoptimizationFrank-Wolfeconditionalgradientsmoothconvexbodyrolling-ballconditionmembershiporaclelinearconvergencetangent
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper shows that when the feasible set of a strongly convex, smooth optimization problem satisfies a uniform rolling-ball condition—an interior ball of radius ρ tangent at every boundary point—the projection step of projected gradient descent can be replaced by one gradient computation and one supporting-tangent computation per iteration, with no loss of linear convergence. The worry this addresses is practical: projecting onto an arbitrary convex set can be considerably more expensive than the gradient step itself. The method attains objective error ε in O((β/α + G/(αρ)) log(H0/ε)) iterations, and if only a membership oracle is available the tangent is approximated in O(d log Qε) queries per iteration. The paper positions this as the first projection-free linear rate for smooth convex bodies that may contain flat boundary pieces, a class strictly larger than sets that are both smooth and strongly convex.

What carries the argument

The central mechanism is the certified interior tangent ball B(q - ρn, ρ), provided by the rolling-ball condition. It makes a single supporting halfspace a good local surrogate for the feasible set: optimizing over B(x,s) with that halfspace constraint is a relaxation with a closed-form solution, and projecting the relaxed point onto the certified ball repairs it to exact feasibility at quadratic cost O(s²/ρ). The second piece of machinery is the smooth squared Minkowski gauge—the squared scaling factor that reaches the boundary—whose normalized gradient at a boundary point equals the outward unit normal; membership bisection evaluates the gauge and centered finite differences recover the normal, which is what turns the tangent oracle into a membership-oracle implementation.

What would settle it

A concrete test of Lemma 2.3: fix any ρ-smooth convex body K, choose x, s, and c, compute the relaxed point p and its projection bp onto B(q - ρn, ρ), and measure ||bp - p|| and ⟨c, bp⟩ - min over K∩B(x,s). The theorem is false if these exceed 2s²/ρ and (2/ρ)||c||s², respectively. An equally direct experiment is to run the algorithm on a rounded cube K = [-1,1]^d with edge radius ρ and a quadratic objective; the promised linear rate should hold with constants matching Theorem 2.1, while the same experiment on the sharp cube (which violates the rolling-ball condition at corners) should show the Θ(s) failure the conclusion describes.

Watch

Extended reading notes

Core claim

Under the ρ-smooth rolling-ball condition on K, the paper proves that a shrinking-radius one-tangent method gives a quadratic-accuracy local linear oracle. Given x inside K, radius s, and direction c, the method finds the last feasible point q on the ray from x in direction -c, solves the relaxed linear program over B(x,s) intersected with the supporting halfspace at q, and projects the resulting p onto the certified interior tangent ball B(q - ρn, ρ). The projection moves p inward by at most 2s²/ρ, so the returned point is feasible, lies in B(x,s), and has objective gap at most (2/ρ)||c||s² relative to the true local minimum. Feeding this oracle into the shrinking-neighborhood reduction yields Theorem 2.1's linear rate with one gradient and at most one exact tangent query per iteration. Under membership access alone, the squared Minkowski gauge is shown to be smooth, its finite-difference gradient recovers the boundary normal, and the tangent is implemented to sufficient precision with O(d log Qε) membership queries.

Load-bearing premise

The entire argument relies on the feasible set satisfying the ρ-smooth rolling-ball condition, meaning an interior ball of radius ρ is tangent to the boundary at every point; if the boundary has a sharp corner, a single supporting tangent is only Θ(s)-accurate and the quadratic repair bound fails.

Editorial extensions

If this is right

  • For any compact ρ-smooth body and β-smooth, α-strongly convex objective, the one-tangent method converges linearly from any feasible start, needing only one gradient and one tangent per iteration.
  • No projection oracle and no linear optimization oracle are required, so the method applies to feasible sets where the linear optimization subproblem is the bottleneck.
  • With exact membership queries, the tangent costs O(d log(d + R/r + R/s)) queries per iteration, giving a total membership-query bound of O(dT log Qε).
  • The class of ρ-smooth sets includes bodies with flat boundary pieces, so the result is a strict extension of previously known projection-free linear convergence.
  • The rate degrades gracefully as the interior rolling radius ρ shrinks, matching the intuition that near-corner parts of the boundary are harder for a single tangent.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: the same quadratic-accuracy local oracle should plug into the standard online conditional-gradient regret analysis, yielding O(log T) regret for strongly convex losses over ρ-smooth sets, even though the paper only states a batch-rate result.
  • Inference: the membership-query count O(d log Qε) could make the method attractive in high-dimensional settings where membership is cheap but linear optimization is expensive; a practical implementation could test the constants on matrix-norm balls or polytopes with rounded facets.
  • Inference: the constants 2/ρ and 9/ρ are likely loose; a tighter finite-difference analysis or a direct normal estimator could reduce the query count and the additive error, which would matter for small ρ.
  • Inference: for nonsmooth sets, the conclusion's suggested multi-tangent repair is a natural extension; for polytopes with a bounded number of facets, using all facet normals near the active face should recover a quadratic repair and hence a linear rate with a membership oracle.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper considers minimizing a β-smooth, α-strongly convex function over a compact convex body K satisfying a uniform interior rolling-ball condition with radius ρ (Eq. (1)). It proposes a projection-free shrinking-radius method that, per iteration, uses one gradient evaluation and one supporting-tangent computation, and proves a linear convergence rate T = O((β/α + G/(αρ)) log(H0/ε)) (Theorem 2.1). The second part of the paper implements the required tangent using only exact membership queries, via bisection on the segment and centered finite differences of the squared Minkowski gauge, yielding O(d log Q_ε) membership queries per iteration (Proposition 3.1 and Corollary 3.2). The exact-tangent half is proven in full detail; the membership half relies on an external gauge-smoothness theorem of Liu and Grimmer and contains a constants gap in a key inclusion.

Significance. If the results hold, the paper gives a notable extension of projection-free linear convergence: earlier linear rates were known for polyhedral sets or for sets that are simultaneously smooth and strongly convex, while the rolling-ball condition admits flat faces and is strictly weaker than strong convexity. The exact-tangent part is elegant and carefully proved: Lemma 2.3's quadratic repair bound is correctly argued, and the Garber–Hazan shrinking-neighborhood reduction in Appendix A is reproduced with full algebra. The membership-query implementation is original and potentially important, provided the cited gauge-smoothness theorem indeed applies to the full class of sets satisfying Eq. (1). The paper is a strong contribution after the membership-half proof is tightened.

major comments (3)
  1. [Section 3 / Appendix B, Proposition 3.1] The proof of Proposition 3.1 asserts that for every z in K, ⟨en,z−bq⟩ ≤ 2δ, and concludes K ⊆ eH. This inclusion is not established by the estimates stated in the paper. Using ∥bq−q∥ ≤ δ and ∥en−n∥ ≤ ζ = δ/(2R+ρ) from Lemma B.1, for any z in K one obtains ⟨en,z−bq⟩ = ⟨n,z−q⟩ + ⟨en−n,z−q⟩ + ⟨n,q−bq⟩ + ⟨en−n,q−bq⟩ ≤ ζ∥z−q∥ + δ + ζδ ≤ 2Rδ/(2R+ρ) + δ + δ²/(2R+ρ) ≤ 3δ, not the needed 2δ. Even if the comparison is restricted to z in K∩B(x,s), the bound becomes roughly ζ·2s + δ + ζδ ≤ 4δ, which is still larger than the halfspace margin. Since the inequality ⟨c,p⟩ ≤ min_{z∈K∩B(x,s)}⟨c,z⟩ relies on K∩B(x,s) ⊆ eH, this is a load-bearing gap in the membership-query proof. The gap is repairable by rescaling δ and ζ by an absolute constant, but the constants in Lemma B.1 and Proposition 3.1 must be corrected before the proof is valid.
  2. [Appendix B / Corollary 3.2] The entire membership-query reduction depends on the external theorem of Liu and Grimmer [8] that the squared Minkowski gauge ψ satisfies Lip(∇ψ) ≤ Lψ = (r + R²/ρ)/r³ and ∇ψ(q) = n(q)/⟨n(q),q⟩ for q in ∂K. The paper neither states the precise theorem nor proves the asserted equivalence between Eq. (1) and βLG-smoothness with βLG = 1/ρ. Because the finite-difference recovery of the normal in Lemma B.1, and hence the O(d log Q_ε) membership-query count in Corollary 3.2, relies entirely on this theorem, the authors should supply the exact statement of the external result and verify its hypotheses for the class of rolling-ball sets with flat faces. If [8] requires regularity beyond Eq. (1), the approximate normal can be biased beyond ζ, breaking the 9s²/ρ accuracy needed by Proposition 3.1. This dependency is load-bearing for the membership-query headline claim, although it does not affect the exact-tangent result of Theorem 2.1.
  3. [Section 2, Theorem 2.1 initialization] The initialization example stating that if ∇f(x0) ≠ 0, then H0 := D∥∇f(x0)∥ is invalid. For K = [0,1], f(x) = (x−10)²/2, x0 = 0, and x* = 1, the diameter is D = 1 and ∥∇f(x0)∥ = 10, but f(x0) − f* = 50, so the proposed H0 does not bound the initial gap. The standard convexity argument gives instead H0 ≤ D G with G = ∥∇f(x0)∥ + βD; the text should use H0 := D(∥∇f(x0)∥ + βD). This is a concrete but local error that does not invalidate the main rate proof.
minor comments (5)
  1. [Appendix A, proof of Proposition 2.2] The assertion that λ_t ≥ θ after the definition of s_t deserves a short justification: one must split into the cases s_t = D and s_t = θ√(2Δ_t/α), using ∥x_t−x*∥ ≤ D in the first case and the strong-convexity distance bound in the second. As written, the inference is not immediate.
  2. [Abstract and Section 3] The notation \widetilde O is used without definition; a parenthetical explanation would improve accessibility.
  3. [Appendix B, Lemma B.1] The finite-difference vector is written as 'eg' with no explicit definition; it should be defined as the centered difference approximation to ∇ψ(q).
  4. [References] Reference [8] is cited only as an arXiv preprint; if a published version exists, it should be cited, and the specific theorem used in Appendix B should be identified by number.
  5. [Section 4, Conclusion] The remark that a corner is Θ(s) away from its tangent is helpful, but it may be worth stating explicitly that Eq. (1) already rules out sharp corners, so this caveat concerns nonsmooth sets outside the theorem's scope.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the exact-tangent theorem is proved from stated assumptions, and the membership-query claim rests on independent external work rather than a self-citation chain.

full rationale

The derivation is self-contained for the main exact-tangent theorem. Proposition 2.2 reproduces the Garber-Hazan shrinking-neighborhood argument in full in Appendix A, Lemma 2.3 proves the O(s^2/rho) repair bound directly from the rolling-ball condition Eq. (1), and Theorem 2.1 follows by composing these proved statements. The citations that appear are not load-bearing in a circular way: [3] (Garber-Hazan) is co-authored by the present author, but the cited result is re-derived in the paper; [6] (Levy-Krause) supplies the geometric repair idea, but Lemma 2.3 gives an independent proof; and [8] (Liu-Grimmer) is an external gauge-smoothness theorem used in Appendix B for the membership-oracle implementation, not a self-citation. No parameter is fitted to produce the stated rate, and no 'prediction' reduces to an input: the linear-convergence claim is a theorem proved from the stated smoothness and strong-convexity assumptions together with the rolling-ball condition. The membership-query half of the paper does depend on the external theorem that the squared gauge is smooth with the stated Lipschitz constant; if that theorem failed for flat-sided rho-smooth bodies, Corollary 3.2 could be invalid, but that is a correctness risk, not circularity, because [8] is independent support and the present paper does not define rho-smoothness in terms of the gauge. The conclusion's acknowledgement that corner sets break the quadratic repair is a limitation statement, not a circular step. The only minor self-citations are accompanied by full proofs or are contextual, so they do not raise the circularity score above 1.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the rolling-ball geometric assumption on K, standard smoothness and strong convexity of f, an exact membership oracle with known sandwich radii, and the cited gauge-smoothness theorem of Liu and Grimmer. No free parameters are fit to data, and no new entities are introduced.

assumptions (4)
  • domain assumption K is a compact ρ-smooth convex body: for every q∈∂K and every outward supporting unit normal n, B(q - ρn, ρ) ⊆ K.
    Eq. (1) defines the rolling-ball condition. It is used in Lemma 2.3 and Prop 3.1 to guarantee the repair step stays inside K and to bound the repair distance by O(s²/ρ).
  • domain assumption f is differentiable on a neighborhood of K, has β-Lipschitz gradient, is α-strongly convex, and sup_{x∈K} ||∇f(x)|| ≤ G.
    Standard assumptions for the shrinking-neighborhood argument in Proposition 2.2 and Theorem 2.1; they define the rate constants γ and Γ.
  • domain assumption Known radii 0 < r ≤ ρ ≤ R satisfy B(0,r) ⊆ K ⊆ B(0,R), and an exact membership oracle MEM_K is available.
    Section 3 and Eq. (11) require the ball sandwich and exact membership for gauge evaluation and bisection. The finite-difference normal recovery uses the smoothness of the squared gauge.
  • domain assumption Liu-Grimmer's theorem: ψ(w) = p_K(w)²/2 has Lipschitz gradient on the relevant region and ∇ψ(q) = n(q)/⟨n(q),q⟩ with r ≤ ⟨n(q),q⟩ ≤ R for q∈∂K.
    External result [8] quoted in Appendix B; it is the basis for recovering the normal from membership queries. The paper does not prove this theorem, so it is an unverified input.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Linearly Convergent Projection-Free Algorithm for Smooth Convex Sets." pith.science (2026). https://pith.science/paper/4VC26TMH

@misc{pith2026260804321,
  author       = {Pith},
  title        = {Pith review of: A Linearly Convergent Projection-Free Algorithm for Smooth Convex Sets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4VC26TMH}},
  note         = {Machine review of arXiv:2608.04321}
}
abstract

We consider minimizing a smooth, strongly convex function over a convex set. Projected gradient descent is known to converge linearly in this setting, but each iteration requires a projection onto the feasible set, which may be computationally expensive. We show that when the feasible set is smooth, projection can be replaced by one gradient computation and a single supporting-tangent computation per iteration, while preserving linear convergence. Moreover, the required tangent can be approximated to sufficient accuracy using $\widetilde O(d)$ membership-oracle queries, where $d$ is the ambient dimension. Previously, projection-free linear convergence was known only for polyhedral sets or for sets that are both smooth and strongly convex.

Figures

Figures reproduced from arXiv: 2608.04321 by the authors.

Figure 1
Figure 1. A ρ-smooth body K has an interior tangent ball of radius ρ at every supporting pair (q, n). A useful example is a parallel body K = C + ρB(0, 1), where C is compact and convex. Flat sides are allowed and show that the rolling-ball condition is strictly weaker than strong convexity. 1.1 Related work For an extensive review of the Frank Wolfe method and its extensions, see the recent text [1], and in the context of on… view at source ↗
Figure 2
Figure 2. Geometry of Lemma 2.3. The boundary point q lies on the ray from x in direction −c, so q − x is a nonnegative multiple of −c. The relaxed minimizer p lies in the supporting hyperplane, and hence ⟨n, p − q⟩ = 0. Projecting p onto the certified interior tangent ball Bq = B(q − ρn, ρ) produces pb. The projection moves p inward by only O(∥p − q∥ 2/ρ) while keeping pb inside B(x, s). Lemma 2.3 (Exact tangent accuracy). T… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 8 canonical work pages

  1. [8]

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

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

    arXiv 2025

  2. [1]

    G´ abor Braun, Alejandro Carderera, Cyrille W. Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Sebastian Pokutta.Conditional Gradient Methods: From Core Principles to AI Applications, volume 35 ofMOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2025

    work page 2025

  3. [2]

    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

    work page 1956

  4. [3]

    Dan Garber and Elad Hazan. A linearly convergent variant of the conditional gradient algorithm under strong convexity, with applications to online and stochastic optimization.SIAM Journal on Optimization, 26(3):1493–1528, 2016. Preliminary version: arXiv:1301.4666, 2013

    work page Pith review arXiv 2016

  5. [4]

    Now Publishers, 2016

    Elad Hazan.Introduction to Online Convex Optimization, volume 2 ofFoundations and Trends in Optimization. Now Publishers, 2016. Also available as arXiv:1909.05207

    arXiv 2016

  6. [5]

    Yin Tat Lee, Aaron Sidford, and Santosh S. Vempala. Efficient convex optimization with membership oracles. InProceedings of the Thirty-First Conference on Learning Theory (COLT), volume 75 ofProceedings of Machine Learning Research, pages 1292–1294, 2018

    work page 2018

  7. [6]

    Levy and Andreas Krause

    Kfir Y. Levy and Andreas Krause. Projection free online learning over smooth sets. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics (AISTATS), volume 89 ofProceedings of Machine Learning Research, pages 1458– 1466, 2019

    work page 2019

  8. [7]

    Fast projection-free approach (without optimization oracle) for optimization over compact convex set

    Chang Liu, Eric Liang, and Mo Chen. Fast projection-free approach (without optimization oracle) for optimization over compact convex set. InAdvances in Neural Information Processing Systems, volume 38, 2025

    work page 2025

Show all 10 references
  1. [9]

    Efficient projection-free online convex optimization with membership oracle

    Zakaria Mhammedi. Efficient projection-free online convex optimization with membership oracle. InProceedings of the Thirty-Fifth Conference on Learning Theory (COLT), volume 178 ofProceedings of Machine Learning Research, pages 5314–5390, 2022

    2022

  2. [10]

    Local LMO: Constrained gradient optimization via a local linear minimization oracle, 2026

    Peter Richt´ arik, Katarzyna Gruntkowska, and Honglin Li. Local LMO: Constrained gradient optimization via a local linear minimization oracle, 2026. A The additive local-oracle reduction Proof of Proposition 2.2.Write κ:= β α , b:= aG α , and set θ:= 1 4(1 +b) , η:= 1 +b 1 +b+...

    2026

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.