Pith. sign in

REVIEW 1 major objections 3 minor 2 cited by

Smooth Quasar-Convex Optimization with Constraints

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

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

Pith's one-line read This paper resolves an open question by showing that L-smooth γ-quasar-convex functions over a compact convex constraint set can be minimized with the same nearly optimal accelerated first-order query count as unconstrained problems, via an

desk verdict A serious paper that likely solves the named constrained quasar-convex acceleration problem, but the main theorem's proof has a real gap in the noisy line-search accounting that needs a careful fix before I'd trust it. read the letter →

arxiv 2510.01943 v3 pith:MBMZQ7NK submitted 2025-10-02 math.OC cs.LG

David Martínez-Rubio This is my paper · ORCID
classification math.OCcs.LG MSC 90C2690C2590C60
keywords quasar-convexityconstrainednonconvexoptimizationacceleratedfirst-ordermethodsinexactproximalpointMoreauenvelopeFrank-WolfeprojectedgradientdescentRiemannian
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 establishes that smooth quasar-convex functions—a broad class of benign nonconvex objectives covering linear dynamical systems, generalized linear models, and constant-curvature Riemannian problems—can be optimized at an accelerated rate even under general compact convex constraints, resolving an open problem. The main theorem gives an algorithm that finds an ε-minimizer in roughly (1/γ)√(LD²/ε) first-order oracle queries, matching, up to log factors, the unconstrained rate and the known lower bound for the larger star-convex class. The key move is an inexact accelerated proximal point method: with prox parameter λ=1/(2L), each proximal subproblem is strongly convex and cheap to solve, and the Moreau envelope inherits γ-quasar-convexity from the original objective. The paper also proves projected gradient descent and Frank-Wolfe converge at rate O(LD²/(γ²ε)) without knowing γ. If correct, the result closes the gap between affine-space and general-constraint settings and improves accelerated Riemannian optimization in constant-curvature spaces.

What carries the argument

The workhorse is the Moreau envelope M_λ(x)=min_{y∈X} f(y)+(1/(2λ))‖y−x‖² with λ=1/(2L). Its proximal subproblem is L-strongly convex and 3L-smooth, its gradient is (x−prox(x))/λ, and, by Proposition 2, it inherits γ-quasar-convexity around the original center x*. This lets the algorithm replace the constrained problem by approximate gradient steps on the envelope, all while staying feasible and retaining a descent structure. The second mechanism is the binary line search on the segment between the previous prox point and the FTRL point, designed to find a coupling point even when the envelope is only evaluated with bounded, adversarially chosen noise.

What would settle it

For the one-dimensional function f(x)=(x²+1/8)^{1/6} on [−5,5] from Example 1, compute its smoothness constant L exactly, set λ=1/(2L), and test every center x∈[−5,5] whether the prox subproblem has a unique minimizer and whether the Moreau envelope M_λ satisfies the γ=1/2 quasar-convexity inequality with center 0; a single violation would falsify Proposition 2 and with it Theorem 5.

Watch

Extended reading notes

Core claim

The central claim is that constrained smooth quasar-convex optimization is no harder than unconstrained: Theorem 5 shows that Algorithm 1 obtains an ε-minimizer in Õ(γ^{-1}√(LD²/ε)) queries to a first-order oracle for an L-smooth γ-quasar-convex function on a compact convex set of diameter D. The argument constructs an inexact accelerated proximal point method: with λ=1/(2L), the Moreau envelope is differentiable, 2L-smooth, has strongly convex proximal subproblems, and—crucially—remains γ-quasar-convex around the same center, so the algorithm can run FTRL regret control and a descent analysis on a function it only evaluates approximately. A binary line search on the segment between the prev

Load-bearing premise

The load-bearing premise is that the Moreau envelope with λ=1/(2L) inherits γ-quasar-convexity around the same center and that the noisy binary line search still finds a valid coupling point under bounded arbitrary oracle error; if either fails, or if L is unknown or underestimated so that λ is too large, the proof collapses.

Editorial extensions

If this is right

  • Constrained smooth quasar-convex optimization is effectively no harder than unconstrained: the query count matches the best unconstrained accelerated rate and the existing star-convex lower bound up to logarithmic factors.
  • The open problem of losing one degree of freedom under general convex constraints is closed; the algorithm works on any compact convex feasible set, not just affine spaces.
  • The result improves the complexity of accelerated geodesically convex optimization on constant-curvature Riemannian manifolds through the standard reduction to constrained quasar-convex problems.
  • Projected gradient descent and Frank-Wolfe both converge at rate O(LD²/(γ²ε)) in this constrained setting without knowledge of γ, providing simple robust baselines.
  • Each proximal subproblem is nearly constant-time, requiring O(log(LD²/δ)) projected gradient iterations, so the total complexity is genuinely dominated by the outer loop and implementable with first-order queries.

Reading between the lines

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

  • The envelope-inheritance recipe is likely transferable: any nonconvex class that is preserved under adding a sufficiently small quadratic prox term, even if it is not closed under addition generally, could receive the same constrained-acceleration treatment.
  • The line search's tolerance of bounded adversarial noise suggests the rate should survive stochastic gradient estimators with bounded variance; a high-probability stochastic version of Theorem 5 is a natural next step.
  • A concrete empirical check: on quasar-convex generalized linear models with box or simplex constraints, Algorithm 1 should show the predicted 1/√ε advantage over projected gradient descent and Frank-Wolfe, which are only 1/ε; a small benchmark would test the constants.
  • The algorithm currently requires exact knowledge of L to set λ=1/(2L); removing that requirement, for instance by a backtracking line search on the envelope, would make the method adaptive to unknown smoothness.
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

1 major / 3 minor

Summary. Summary. The paper studies minimization of an L-smooth γ-quasar-convex function f over a compact convex set X ⊂ R^d of diameter D. It claims the first accelerated first-order method for this constrained setting: Algorithm 1 combines an inexact Moreau-envelope proximal point method, FTRL over approximate envelope gradients, and a noisy binary line search, and Theorem 5 asserts an Õ(γ^{-1}√(LD²/ε)) oracle complexity. This would match the star-convex lower bound and resolve an open problem posed by Martínez-Rubio (2022) and Lezane–Langer–Koolen (2024). The paper also provides unaccelerated rates for projected gradient descent (Theorem 8) and Frank–Wolfe (Theorem 9). The main supporting lemmas are mostly correct; however, the proof of Theorem 5 contains a concrete gap in the error accounting of the line search, detailed below.

Significance. If the main theorem is correct, this is a significant contribution: it closes a notable open problem in structured nonconvex optimization and provides a template for constrained acceleration via Moreau envelopes under weakened convexity. The claimed query rate is the right one, matching the Hinder–Sidford–Sohoni lower bound up to logarithms. The unaccelerated PGD and Frank–Wolfe analyses are clean, adaptive to γ, and appear correct. The construction is original, and the proofs are largely self-contained. However, the proof of the central accelerated theorem has a repairable but real gap, so the paper needs revision before it can be accepted.

major comments (1)
  1. [Appendix B, proof of Theorem 5 (definition of E_t)] The displayed recurrence E_t is not a valid consequence of Lemma 4. With the line-search parameter used in Theorem 5, c = A_{t-1}γ/a_t, multiplying the Lemma 4 inequality by a_t/γ yields the noise term (9a_t/γ + 5A_{t-1})δ plus (a_t/γ)√(8LD²δ). The manuscript instead writes (a_t/γ)(9 + 5a_t/(γA_{t-1}))δ · I(t=1). This is undefined at t=1 because A_0=0, it inverts the ratio in c, and the indicator I(t=1) suppresses the (9+5c)δ noise for every t>1. Since Lemma 4 is invoked at every outer iteration, the potential-gap recurrence E_t is incomplete as displayed. The omitted 5A_{t-1}δ terms are small under the chosen δ = LD²/(10T^6), so the final rate may survive, but the proof as written must be re-derived and corrected before the theorem can be accepted.
minor comments (3)
  1. [Appendix B, final paragraph of Theorem 5] The text says the binary-search complexity is O(LD²/ε) by Lemma 4. Lemma 4 gives O(log(LD²/δ)) prox calls, each costing O(log(LD²/δ)) PGD iterations. Please correct this to the logarithmic (Õ(1)) per-outer-iteration bound; otherwise the displayed total query count contradicts the theorem and the earlier complexity statements.
  2. [Section 4, Algorithm 1 and Appendix B] The definitions of a_t and A_t should be stated for all t≥0 before the loop. The paper uses A_{-1}=0 in the proof but Algorithm 1's formula only defines A_t for t≥1; the ambiguity matters because the line-search parameter at t=1 is c=0.
  3. [Appendix B.1, proof of Lemma 4] The induction for the 'good interval' would benefit from an explicit statement of how the good interval survives the halving step. The proof says the check of (11) failed at the endpoints, but the algorithm only evaluates the midpoint; the case analysis appears to handle this, but it should be written out more transparently, especially because the branch decision uses h rather than the true g.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the main theorem is derived from stated assumptions with self-contained proofs.

full rationale

The central claim is the convergence rate of Algorithm 1 in Theorem 5, built from Proposition 2 (Moreau envelope inherits quasar convexity), Lemma 3 (descent on the inexact envelope), and Lemma 4 (noisy binary line search). Each of these is proved in the paper from the stated definitions of L-smoothness, γ-quasar convexity, the Moreau envelope, and the approximate proximal subproblem; no fitted constant is later renamed as a prediction, and the rate is not defined in terms of itself. The only self-citations to Martínez-Rubio (2022) are as a source of the open problem and as a downstream Riemannian application; neither is used to establish the upper bound. The lower-bound comparison is to the external Hinder–Sidford–Sohoni result, and the unaccelerated theorems (Theorems 8 and 9) are also derived directly from the assumptions. A possible proof issue with the noise accounting in Lemma 4 when it is used inside Theorem 5 would be a correctness or typographical concern, not circularity, because the disputed term is not assumed from the theorem being proved. Thus no specific circular step is exhibited, and the circularity score is 0.

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

No free parameters are fitted to data; all internal constants (T, δ, λ, a_t) are set by the analysis. The accelerated algorithm requires γ, L, and D as inputs — problem data, not fitted values — while the PGD and Frank-Wolfe analyses are adaptive to unknown γ. No invented entities (forces, dimensions, or mediators) are introduced. The axioms are the problem-structure assumptions (smoothness, quasar convexity, compact convex domain), standard background results (Moreau envelope calculus, FTRL regret, PGD linear convergence), and an externally cited lower bound used as the optimality benchmark.

assumptions (6)
  • domain assumption f is L-smooth (L-Lipschitz gradient) and γ-quasar convex on X with a fixed center x* ∈ X (Definition in Section 2).
    The entire rate is expressed in terms of L, γ, D; the algorithm and proofs would not run without these structural constants.
  • domain assumption X is a compact convex set of diameter D, and the initial point x0 lies in X.
    Convexity of X is used for the constrained prox, projections, FTRL steps, and the line-search segment conv{y_{t−1}, z_{t−1}}; diameter D appears in the rate.
  • standard math Convex functions (e.g., the indicator 1_X) are γ-quasar convex with respect to any minimizer for all γ ∈ (0,1].
    Used in Proposition 2 to add 1_X into the envelope inequality; follows from the first-order optimality condition ⟨∇g(x), x* − x⟩ ≤ 0.
  • standard math Moreau-envelope gradient formula ∇M(x) = (x − prox(x))/λ, with the envelope being 2L-smooth and the prox subproblem L-strongly convex and 3L-smooth when λ = 1/(2L).
    Lemma 1 and Appendix A; derived algebraically in the text (the smoothness part does not need convexity of f).
  • standard math Strong-convexity regret bound for FTRL and the O(κ log(LD²/δ)) iteration bound for projected gradient descent on strongly convex smooth subproblems.
    Used in the proof of Theorem 5 and Lemma 11; standard results (Bubeck 2015, cited in the paper).
  • domain assumption The Ω(1/(γ√ε))-type lower bound for smooth star-/quasar-convex minimization (Hinder–Sidford–Sohoni) is the correct benchmark for near-optimality.
    Invoked to justify 'nearly optimal'; the constrained-case lower bound is taken from the cited literature, not re-derived here.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Smooth Quasar-Convex Optimization with Constraints." pith.science (2026). https://pith.science/paper/MBMZQ7NK

@misc{pith2026251001943,
  author       = {Pith},
  title        = {Pith review of: Smooth Quasar-Convex Optimization with Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MBMZQ7NK}},
  note         = {Machine review of arXiv:2510.01943}
}
abstract

Quasar-convex functions form a broad nonconvex class with applications to linear dynamical systems, generalized linear models, and Riemannian optimization, among others. Current nearly optimal algorithms work only in affine spaces due to the loss of one degree of freedom when working with general convex constraints. Obtaining an accelerated algorithm that makes nearly optimal $\widetilde{O}(1/(\gamma\sqrt{\varepsilon}))$ first-order queries to a $\gamma$-quasar convex smooth function \emph{with constraints} was independently asked as an open problem in Mart\'inez-Rubio (2022); Lezane, Langer, and Koolen (2024). In this work, we solve this question by designing an inexact accelerated proximal point algorithm that we implement using a first-order method achieving the aforementioned rate and, as a consequence, we improve the complexity of the accelerated geodesically Riemannian optimization solution in Mart\'inez-Rubio (2022). We also analyze projected gradient descent and Frank-Wolfe algorithms in this constrained quasar-convex setting. To the best of our knowledge, our work provides the first analyses of first-order methods for quasar-convex smooth functions with general convex constraints.

Figures

Figures reproduced from arXiv: 2510.01943 by the authors.

Figure 1
Figure 1. Example 1; a (1/2)-quasar convex function f(x) def = (x 2 + 1/8)1/6 in [−5, 5] (left) and its proximal subproblem g(x) def = f(x)+ 1 2λ (x−x0) 2 , for λ = 50 and x0 ≈ −12.23 (right). The latter has a local maximizer at x = −2 and a local minimizer near x = 0 and so it cannot be quasar convex in [−5, 5]. The considerations above are negative results in the general case regarding combining functions for classes weaker… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. Accelerated Stochastic Zeroth-Order Quasar-Convex Optimization

    math.OC 2026-07 conditional novelty 6.0 of 10

    A continuized zeroth-order Nesterov method achieves O(d/√ε) function-evaluation complexity for smooth quasar-convex minimization, with improved dimension dependence under a 1-norm mirror step when the solution is sparse.

  2. Mirror Descent Methods for Quasar Convex Optimization Problems With Non-Smooth Inequality Constraints

    math.OC 2026-05 reject novelty 4.0 of 10

    Extends mirror descent with productive/non-productive steps to quasar-convex objectives with nonsmooth constraints, but the convergence claims are only partially proven.

Reference graph

Works this paper leans on

5 extracted references · cited by 2 Pith papers

  1. [2]

    Thus, if we detect that y satisfies∥∇F (y)∥2≤ √ 2Lδ, then we have F (y)−F (y∗)≤ δ

    (6) For the function we consider, it is ˜µ← L and˜L← 3L. Thus, if we detect that y satisfies∥∇F (y)∥2≤ √ 2Lδ, then we have F (y)−F (y∗)≤ δ. At the same time, we have this gradient norm guarantee whene ver F (y)−F (y∗)≤ δ/3, by the first inequality above. Since PGD starting at y0 takes at most O( ˜L ˜µ log( ˜L∥y0−y∗∥ 2 2 ˆδ )) iterations to obtain a ˆδ-minim...

    2015

  2. [3]

    Since the condition number of F (yk) is O(1), we can do so with PGD in ˜O(log( LD2 δ )) iterations, cf

    For δ > 0 to be chosen later, assume that we optimize Fk so that ∥yk− y∗ k∥2≤ δ1, and so F (yk)− δ2≤ F (y∗ k) = M(xk)≤ F (yk), where y∗ k = arg min y Fk(y) = prox λ(xk) for δ2 = δ. Since the condition number of F (yk) is O(1), we can do so with PGD in ˜O(log( LD2 δ )) iterations, cf. Lemma 11 . We denote our approximation of ∇M(xk) by ˜∇M(xk) def = 1 λ (x...

  3. [4]

    We denote by I(A) the event indicator that is 1 if A holds true Smooth Quasar-Convex Optimization with Constraints and 0 otherwise. AtGt− At−1Gt−1− I(t = 1) 1 2∥x0− x∗∥2 2 1 ≤ At(˜M(yt)−˜M(xt)) + ✘✘✘✘at˜M(xt) + At−1(˜M(xt)−˜M(yt−1)) − ( ✟✟✟✟✟✟t∑ i=1 ai˜M(xi) + t−1∑ i=1 ai γ⟨˜∇M(xi), zt− xi⟩ +∥zt− x0∥2 2 2 ) + Atδ + AtD γ √ 8Lδ− at γ⟨˜∇M(xt), zt− xt⟩ + ( ✟...

  4. [5]

    Indeed: |g′(α1)− g′(α2)|≤∥∇ M(vα1 )−∇ M(vα2 )∥2∥yt−1− zt−1∥2≤ 2L∥yt−1− zt−1∥2 2, where in the last inequality we used the 2L-smoothness of M , cf. Lemma 1 . We will use h(α) def = ˜M(vα) def = f (wα) + 1 2λ∥wα− vα∥2 2, for wα def ∈ arg minδ w{f (w) + 1 2λ∥w− vα∥2 2}, and ˆ h(α) def = ⟨˜∇M(vα), yt−1− zt−1⟩ def = ⟨1 λ (vα− wα), yt−1− zt−1⟩ in order to imple...

  5. [6]

    (15) For any x, define x+ def = arg min z∈X Qx(z) as the resulting point from taking a projected gradient desc ent step from x, cf. (2). Note that Qx is (1/η)-strongly convex. Thus, for all y∈X , we have f (x)+⟨∇f (x), x+− x⟩ + 1 2η∥x+− x∥2 2 + 1 2η∥x+− y∥2 2 = Qx(x+) + 1 2η∥x+− y∥2 2 ≤ Qx(y) = f (x) +⟨∇f (x), y− x⟩ + 1 2η∥y− x∥2 2. Or equivalently, ⟨∇f (x...

Pith tools

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