Pith. sign in

REVIEW 4 major objections 5 minor 52 references

A function-value-only momentum scheme reaches the accelerated rate for quasar-convex optimization, matching convex acceleration up to a τ factor and the unavoidable dimension term.

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 ↗

T0 review · deepseek-v4-flash

2026-08-01 11:11 UTC pith:NFC5DIM6

load-bearing objection Plausible first accelerated zeroth-order rate for quasar-convex functions, but Theorem 3.3's explicit parameter choice violates its own inequality (4.38), so the headline result is not actually proved as stated. the 4 major comments →

arxiv 2607.19965 v1 pith:NFC5DIM6 submitted 2026-07-22 math.OC

Accelerated Stochastic Zeroth-Order Quasar-Convex Optimization

Em\'eric Gbaguidi , Julien Hermant This is my paper
classification math.OC MSC 90C1590C2690C56
keywords quasar-convex optimizationzeroth-order optimizationcontinuized accelerationstochastic oraclemirror descentBregman divergencesparse solutionshigh-probability convergence
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 paper aims to show that momentum acceleration is possible when the objective is τ-quasar-convex — a structured non-convex condition that includes star-convexity — and the optimizer only receives noisy function values. It designs a stochastic zeroth-order continuized accelerated-momentum algorithm and proves that ε-accuracy is reached in O(d√L ‖x0−x*‖₂/(τ√ε)) iterations in the Euclidean setting, and O(√d√(LV(x0,x*))/(τ√ε)) iterations with a 1-norm mirror step. This improves on the previously known O(d/ε) zeroth-order rate for this class and matches convex acceleration up to a τ factor and the dimension factor d that is unavoidable without gradients. The mirror step is added so that, when the difference between start and minimizer is sparse, the dimension dependence improves from d to √d — provided an unproved sparsity-to-Bregman bound holds. Why it matters: it broadens the class of problems where derivative-free methods can be accelerated, with consequences for settings where gradients are costly or unavailable.

Core claim

On the paper's own terms, the central discovery is Theorem 3.3: for an L-smooth τ-quasar-convex f given through a stochastic zeroth-order oracle satisfying a strong-growth condition, the ZO-NEM algorithm — a discretized version of the Poisson-driven continuized process (ZO-CNM) with mini-batch finite-difference estimates — outputs, after k(ε) = O(d(ρ+1)√(κ_d L V(x0,x*))/(δ1 τ √ε)) iterations, an ε-optimal point with probability at least 1−1/δ0−e^{−(δ1−1−log δ1)k(ε)}. The corresponding function-evaluation count is O(d/√ε) in the Euclidean setup, matching the accelerated convex zeroth-order rate up to the quasar-convexity parameter τ, and improving on the previous O(d/ε) gradient-free bound fo

What carries the argument

The engine is the continuized accelerated-momentum process (ZO-CNM), a stochastic differential equation with a drift pulling x toward z and random Poisson jumps that apply a mini-batch spherical finite-difference gradient estimate g_α, then move z by a proximal mirror step under a Bregman divergence V. Evaluating the process at exponential jump times yields the discrete ZO-NEM momentum recursion. The proof rides on the Lyapunov function φ(t,x,z)=a_t(f_α(x)−f*)+V(z,x*), where f_α is the smoothed function whose gradient g_α estimates unbiasedly; a non-smooth Itô formula handles the non-differentiable Bregman term, and the three parameters — time weight a_t, step-sizes γ and γ′ — are balanced s

Load-bearing premise

The dimension-saving part of the central claim rests on an unproved expectation, stated by the paper as 'it is expected' (Section 3 and the Table 1 caption), that for the chosen ℓ1-prox the Bregman divergence V(x0, x*) is bounded by a constant independent of d and is approximately ‖x0−x*‖₂² when x0−x* is sparse; if V actually grows with d, the √d iteration count becomes d and the advertised improvement disappears.

What would settle it

Take d from 10³ to 10⁵, x*=0, x0 with ten nonzero entries of equal magnitude, and the paper's ℓ1-prox with κ=1+1/log d; compute V(x0,x*). If V grows like d‖x0‖₂² rather than staying near ‖x0‖₂², then Theorem 3.3's k(ε) grows like d√(log d)/√ε and the sparse-dimension claim is refuted. Alternatively, run ZO-NEM on a sparse GLM at increasing d and compare function-evaluation counts to reach a fixed ε: linear-in-d growth rather than √d growth would settle it against the paper.

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

If this is right

  • For smooth quasar-convex problems, noisy function values alone are enough to get the accelerated 1/√ε complexity; gradients are not needed for the stabilizing subspace-search that earlier acceleration mechanisms required.
  • The Euclidean bound is O(d√(LV)/(τ√ε)): up to τ and d, the same rate as accelerated zeroth-order convex optimization.
  • With the ℓ1 mirror step, the iteration count improves to O(√d√(LV)/(τ√ε)) whenever the Bregman divergence from start to minimizer stays bounded by a dimension-free constant, which is expected for sparse solutions.
  • The guarantee is high-probability, not just in expectation: the failure probability decays exponentially in the iteration count, up to the 1/δ0 Markov term.
  • Setting τ=1 covers star-convex functions, so the result subsumes the convex case and extends it to a broader non-convex class.

Where Pith is reading between the lines

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

  • Editorial extension: if the continuized route removes the need for subspace-search, the same idea may transfer acceleration to other derivative-free settings where gradient-based search mechanisms were the only obstacle.
  • Editorial extension: the √d saving in the prox setup is likely to show up not only for sparse differences but whenever the solution coordinates live on different scales; that is a testable prediction the paper does not pursue.
  • Editorial extension: the strong-growth assumption (ρ, σ²) covers multiplicative and bounded noise, so a natural stress test is whether the rate degrades gracefully when the condition fails, e.g. under heavy-tailed noise.

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

4 major / 5 minor

Summary. The paper studies unconstrained minimization of smooth τ-quasar-convex functions using a stochastic zeroth-order oracle. It introduces a continuized Nesterov-type process (ZO-CNM) whose discrete evaluation yields a zeroth-order Nesterov momentum algorithm with a mirror step (ZO-NEM). The main theoretical result, Theorem 3.3, claims that with appropriate choices of smoothing parameter α(ε), batch size m(ε), and iteration count k(ε), the algorithm achieves f(˜x_{k(ε)})−f* ≤ ε with high probability, giving O(d/√ε) iterations in the Euclidean setting and an improved dimension dependence in the 1-norm prox setting when the solution is sparse. The proof combines a continuous-time Lyapunov argument, optional stopping, and Gamma-type concentration inequalities.

Significance. If the central claim holds, this is a meaningful step: it provides the first accelerated zeroth-order complexity for quasar-convex minimization, extending the continuized acceleration framework beyond first-order oracles and avoiding the subspace-search mechanism used in prior quasar-convex acceleration results. The Lyapunov construction in §4 is natural and the parameter cancellation is explicit. The paper also gives comparisons with the existing zeroth-order quasar-convex result [17] and with the convex zeroth-order literature [24,25]. However, the central theorem as stated is not proved: the explicit parameter choice in Theorem 3.3 violates the proof's own inequality (4.38), and the abstract's total evaluation count is not supported by the theorem for σ²>0. These issues are repairable in principle, but they are load-bearing for the published claim.

major comments (4)
  1. [§4.2.2, Eq. (4.38) and Theorem 3.3] The parameter selection in Theorem 3.3 is inconsistent with the proof. Eq. (4.38) requires α ≤ sqrt(16δ₁²τdε/(97δ₀L(d+17)k)). Substituting k(ε) from (4.35), the sharp upper bound is (4/√3880)·ε^{3/4}τδ₁^{3/2}/(δ₀^{3/4}L^{3/4}(d+17)^{1/2}(ρ+1)^{1/2}(κ_dV)^{1/4}) ≈ 0.064·B, whereas the stated α(ε) is (1/3)·B. Thus the stated α is about 5.2 times too large. Plugging the stated α and k into the left side of (4.38) gives approximately 13.5ε, not ε/2. Consequently the proof of Theorem 3.3 does not establish the claimed ε-accuracy for the stated parameter values. The result may survive with corrected constants, but the theorem as written is not proved.
  2. [Abstract, §1, and Theorem 3.3] The abstract and contributions state that the method solves the problem in O(d/√ε) function evaluations. For σ²>0 this is not what Theorem 3.3 gives. The batch size satisfies m(ε)=O(σ²/ε^{3/2}) and the iteration count k(ε)=O(1/√ε), so the total number of function evaluations is m(ε)k(ε)=O(dσ²/ε²), after cancellations. The O(d/√ε) statement is only plausible in the noiseless/interpolation case σ²=0, but then the stated m(ε) formula gives m=0. The authors should either restrict the abstract claim to σ²=0, state the σ²-dependent total complexity explicitly, or add max{1,·} to m(ε) and clarify which regime is claimed.
  3. [Section 3, Table 1, and Remark 2.2] The claimed sparse-solution dimension improvement is not established by the theorem. Theorem 3.3 is stated in terms of V(x₀,x*) with no quantitative estimate for the chosen ℓ₁-prox. The paper only says it 'is expected' that V(x₀,x*)≈‖x₀−x*‖₁² under sparsity, and Table 1 simply assumes existence of Θ_p. Without a proof or a precise reference showing that the prox function in Remark 2.2 satisfies V(x₀,x*)≤Θ₁ with Θ₁ independent of d (or depending only on sparsity), the advertised gain over the Euclidean case does not follow. If V carries an O(d) factor, the √(d log d) iteration dependence becomes d√(log d), and the dimension improvement disappears.
  4. [Appendix B, Lemma B.7] Lemma B.7 is a key variance bound: it is used in Lemma B.8 to obtain the negative ∥∇f_α(x)∥² coefficient in (4.11), and hence is essential for the cancellation of trajectory-dependent terms in Theorem 3.1. The proof is left to the reader. For a formal journal, this is not acceptable for a load-bearing lemma; the proof should be included in the revision.
minor comments (5)
  1. [Theorem 3.3] For σ²=0 the formula for m(ε) gives m=0, which is outside N*. Use m(ε)=max{1, ceil(...)} or state σ²>0 separately.
  2. [Theorem 3.2 and Proposition 2.1] The notation is confusing: Proposition 2.1 uses a constant η in the momentum coefficient (T_k/T_{k+1})^η, while Theorem 3.2 lists η_k=2/(τT_k). Also γ'_k is written as 2CT_k/τ, but the discrete update at step k from Proposition 2.1 uses γ'_{T_{k+1}^-}. Clarify the indexing or the definition of the discrete parameters.
  3. [Abstract and Table 1] The abstract states O(√d√(LV)/(τ√ε)) for the 1-norm prox setup, while Table 1 gives √(d log d). The logarithmic factor should be stated consistently, or the abstract should say 'up to logarithmic factors'.
  4. [Lemma 2.3] Lemma 2.3 is stated for p∈[1,2] with q the dual exponent, but later results use q∈[2,∞] without explicitly connecting p and q. Please state the relation clearly.
  5. [Section 5] The numerical section says parameters were tuned by grid search but gives no grid or other details. This makes the empirical claims difficult to reproduce and should be expanded.

Circularity Check

0 steps flagged

No significant circularity: the derivation is self-contained against external benchmarks; the caveats (unproven V-scaling, possible parameter-check error in (4.38)) are assumptions/correctness issues, not circularity.

full rationale

The derivation chain is essentially self-contained. Theorem 3.1's Lyapunov bound (4.27) is obtained from explicit Itô calculations, the variance inequalities (4.11)-(4.12), and the parameter choices (4.20) that are selected to cancel the trajectory-dependent terms via (4.16)-(4.19). Theorem 3.2 transfers this to ZO-NEM with the optional stopping theorem, and Theorem 3.3 merely chooses m(ε), α(ε), k(ε) to satisfy the displayed sufficient conditions (4.35), (4.37), (4.38). There is no fitted constant later renamed as a prediction and no equation whose output is its own input. The self-citations [29],[30] are used for context and as the proof template for the stopping theorem (Appendix C.2), but the proof is reproduced, so they are not load-bearing for the zeroth-order quasar-convex rate. The sparse-dimension improvement is explicitly stated as "expected" (Section 3 and Table 1), i.e., an unproven assumption on V rather than a circular reduction; the numerical experiments use grid-search tuning, not a fitted theoretical parameter. One defect is a genuine internal inconsistency: the α(ε) stated in Theorem 3.3 does not satisfy the proof's own sufficient condition (4.38) — substituting (4.35) into the bound in (4.38) gives an α about 5.2x smaller than the stated one, so the claimed ε-accuracy is not established by the given parameter choice. This is a correctness/proof gap, not a circularity, and is therefore not counted in the score.

Axiom & Free-Parameter Ledger

8 free parameters · 7 axioms · 0 invented entities

All algorithmic parameters are hand-chosen inside the proof to force cancellation of trajectory-dependent terms; they are not fitted to data. The load-bearing domain assumptions are quasar-convexity, stochastic smoothness, and the strong-growth condition. No new entities are introduced. The one ad hoc assumption is the boundedness of V in the ℓ₁ setup, which supports the sparsity dimension-claim but is not proven.

free parameters (8)
  • momentum schedule η_s = 2/(sτ)
    Chosen to cancel the Lyapunov time-derivative term Eq. (4.16); depends on unknown τ.
  • gradient step size γ_s = m/(4dL(ρ+m−1))
    Minimizer of the quadratic in ‖∇f_α‖² in Eq. (4.18); depends on unknown L and ρ.
  • mirror step size γ'_s = 2Cs/τ
    Set by a_s η_s − γ'_s = 0 Eq. (4.17).
  • Lyapunov constant C = τ²m²/(384d²Lκ_d(ρ+m)(ρ+m−1))
    Chosen to zero the ‖∇f_α‖² coefficient Eq. (4.19).
  • smoothing parameter α(ε) = (1/3)(ε³τ⁴δ1⁶/((d+17)²(ρ+1)²δ0³L³))^(1/4) (κ_d V(x0,x*))^(−1/4)
    Theorem 3.3; tuned to force the α²k term below ε/2.
  • batch size m(ε) = ⌈80σ²(ρ+1)/τ sqrt(δ0³κ_d V/(δ1⁶ε³L))⌉
    Theorem 3.3; controls the σ² variance term; equals 0 if σ²=0.
  • iteration count k(ε) = ⌈40d(ρ+1)/(δ1τ) sqrt(δ0κ_dLV/ε)⌉
    Theorem 3.3; set to make the optimization error ≤ε/4.
  • confidence parameters δ0, δ1 = δ0>1, δ1∈(0,1]
    User-chosen high-probability constants.
axioms (7)
  • domain assumption f is τ-quasar-convex (Assumption 1.1)
    Used for the gradient inequality in Lemma B.3; the entire analysis relies on it.
  • domain assumption Stochastic L-smoothness with E[L(ξ)^2] ≤ L² (Assumption 2.5)
    Basis of smoothing lemmas B.1/B.2 and variance bounds.
  • domain assumption Strong growth condition E‖∇f(x,ξ)‖²≤ρ‖∇f(x)‖²+σ² (Assumption 2.6)
    Used in Lemma B.5 and variance control for the estimator.
  • standard math Moment bounds of uniform-on-sphere vectors (Lemma 2.3)
    Imported from Gorbunov et al. [25]; needed for the q-norm variance bound.
  • domain assumption The prox function h is 1-strongly convex w.r.t. ℓ_p, and the explicit ℓ_1 prox of Remark 2.2 is valid
    Needed for the Bregman divergence and mirror step; cited from [3].
  • ad hoc to paper Θ_p exists with V(x0,x*)≤Θ_p, and V≈‖x0−x*‖₁² under sparsity
    Underlies the sparse dimension-improvement claim; not proved here.
  • standard math Itô formula for non-smooth Lyapunov functions (Proposition C.1)
    Justifies the stochastic derivative of the Bregman term; proof sketched in Appendix C.

pith-pipeline@v1.3.0-alltime-deepseek · 24710 in / 25031 out tokens · 214913 ms · 2026-08-01T11:11:32.125118+00:00 · methodology

0 comments
read the original abstract

We consider unconstrained minimization of smooth quasar-convex functions when only noisy function evaluations are accessible through a stochastic zeroth-order oracle. For these non-convex functions, the standard acceleration method relies on subspace-search mechanisms that require first-order information, being therefore unavailable in zeroth-order regimes. In contrast, the alternative and less conventional continuized method enable to avoid such mechanisms. In this work, we design a zeroth-order continuized algorithm, leading to accelerated convergence guarantees that parallel those of smooth convex optimization up to a quasar-convexity parameter. Our method incorporates a mirror step, improving the dimension dependence when there exists sparse solution.

discussion (0)

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

Reference graph

Works this paper leans on

52 extracted references · 9 linked inside Pith

  1. [1]

    Agarwal, O

    A. Agarwal, O. Dekel, and L. Xiao , Optimal algorithms for online convex optimization with multi-point bandit feedback. , in Colt, 2010, pp. 28--40

    2010

  2. [2]

    Bartlett, V

    P. Bartlett, V. Dani, T. Hayes, S. Kakade, A. Rakhlin, and A. Tewari , High-probability regret bounds for bandit online linear optimization , in Proceedings of the 21st annual conference on learning theory-COLT 2008, Omnipress, 2008, pp. 335--342

    2008

  3. [3]

    Ben-Tal and A

    A. Ben-Tal and A. Nemirovski , Lectures on modern convex optimization: analysis, algorithms, and engineering applications , SIAM, 2001

    2001

  4. [4]

    A. S. Berahas, L. Cao, K. Choromanski, and K. Scheinberg , A theoretical and empirical comparison of gradient approximations in derivative-free optimization , Foundations of Computational Mathematics, 22 (2022), pp. 507--560

    2022

  5. [5]

    Bhojanapalli, B

    S. Bhojanapalli, B. Neyshabur, and N. Srebro , Global optimality of local search for low rank matrix recovery , Advances in Neural Information Processing Systems, 29 (2016)

    2016

  6. [6]

    E. J. Candes, J. K. Romberg, and T. Tao , Stable signal recovery from incomplete and inaccurate measurements , Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 59 (2006), pp. 1207--1223

    2006

  7. [7]

    Carmon, J

    Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford , Lower bounds for finding stationary points i , Mathematical Programming, 184 (2020), pp. 71--120

    2020

  8. [8]

    Cevher and B

    V. Cevher and B. C. Vu , On the linear convergence of the stochastic gradient method with constant step-size , Optimization Letters, 13 (2019), pp. 1177--1187

    2019

  9. [9]

    Chafa \" , Ph \'e nom \'e nes de grande dimension , Djalil CHAFAI, 2026

    D. Chafa \" , Ph \'e nom \'e nes de grande dimension , Djalil CHAFAI, 2026

    2026

  10. [10]

    X. Chen, S. Liu, K. Xu, X. Li, X. Lin, M. Hong, and D. Cox , Zo-adamm: Zeroth-order adaptive momentum method for black-box optimization , in Neural Information Processing Systems, 2019, https://api.semanticscholar.org/CorpusID:202777327

    2019

  11. [11]

    Choromanski, M

    K. Choromanski, M. Rowland, V. Sindhwani, R. Turner, and A. Weller , Structured evolution with compact architectures for scalable policy optimization , in International Conference on Machine Learning, PMLR, 2018, pp. 970--978

    2018

  12. [12]

    Y. N. Dauphin, R. Pascanu, C. Gulcehre, K. Cho, S. Ganguli, and Y. Bengio , Identifying and attacking the saddle point problem in high-dimensional non-convex optimization , Advances in neural information processing systems, 27 (2014)

    2014

  13. [13]

    D. L. Donoho , Compressed sensing , IEEE Transactions on information theory, 52 (2006), pp. 1289--1306

    2006

  14. [14]

    J. C. Duchi, P. L. Bartlett, and M. J. Wainwright , Randomized smoothing for stochastic optimization , SIAM Journal on Optimization, 22 (2012), pp. 674--701

    2012

  15. [15]

    J. C. Duchi, M. I. Jordan, M. J. Wainwright, and A. Wibisono , Optimal rates for zero-order convex optimization: The power of two function evaluations , IEEE Transactions on Information Theory, 61 (2015), pp. 2788--2806

    2015

  16. [16]

    M. Even, R. Berthier, F. Bach, N. Flammarion, H. Hendrikx, P. Gaillard, L. Massouli \'e , and A. Taylor , Continuized accelerations of deterministic and stochastic gradient descents, and of gossip algorithms , Advances in Neural Information Processing Systems, 34 (2021), pp. 28054--28066

    2021

  17. [17]

    A. A. Farzin, Y.-M. Pun, and I. Shames , Minimisation of quasar-convex functions using random zeroth-order oracles , arXiv preprint arXiv:2505.02281, (2025)

    Pith/arXiv arXiv 2025

  18. [18]

    A. A. Farzin and I. Shames , Minimisation of polyak- ojasewicz functions using random zeroth-order oracles , in 2024 European Control Conference (ECC), IEEE, 2024, pp. 3207--3212

    2024

  19. [19]

    A. D. Flaxman, A. T. Kalai, and H. B. McMahan , Online convex optimization in the bandit setting: gradient descent without a gradient , arXiv preprint cs/0408007, (2004)

    Pith/arXiv arXiv 2004

  20. [20]

    Q. Fu, D. Xu, and A. C. Wilson , Accelerated stochastic optimization methods under quasar-convexity , in International Conference on Machine Learning, PMLR, 2023, pp. 10431--10460

    2023

  21. [21]

    Gautam, Y

    T. Gautam, Y. Park, H. Zhou, P. Raman, and W. Ha , Variance-reduced zeroth-order methods for fine-tuning language models , arXiv preprint arXiv:2404.08080, (2024)

    Pith/arXiv arXiv 2024

  22. [22]

    R. Ge, C. Jin, and Y. Zheng , No spurious local minima in nonconvex low rank problems: A unified geometric analysis , in International conference on machine learning, PMLR, 2017, pp. 1233--1242

    2017

  23. [23]

    Ghadimi and G

    S. Ghadimi and G. Lan , Stochastic first-and zeroth-order methods for nonconvex stochastic programming , SIAM journal on optimization, 23 (2013), pp. 2341--2368

    2013

  24. [24]

    Gorbunov, A

    E. Gorbunov, A. Bibi, O. Sener, E. H. Bergou, and P. Richt \'a rik , A stochastic derivative free optimization method with momentum , arXiv preprint arXiv:1905.13278, (2019)

    Pith/arXiv arXiv 1905

  25. [25]

    Gorbunov, P

    E. Gorbunov, P. Dvurechensky, and A. Gasnikov , An accelerated method for derivative-free smooth stochastic convex optimization , SIAM Journal on Optimization, 32 (2022), pp. 1210--1238

    2022

  26. [26]

    Gower, O

    R. Gower, O. Sebbouh, and N. Loizou , Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation , in International Conference on Artificial Intelligence and Statistics, PMLR, 2021, pp. 1315--1323

    2021

  27. [27]

    Griewank and A

    A. Griewank and A. Walther , Evaluating derivatives: principles and techniques of algorithmic differentiation , SIAM, 2008

    2008

  28. [28]

    Hardt, T

    M. Hardt, T. Ma, and B. Recht , Gradient descent learns linear dynamical systems , Journal of Machine Learning Research, 19 (2018), pp. 1--44

    2018

  29. [29]

    Hermant, J.-F

    J. Hermant, J.-F. Aujol, C. Dossal, L. Huang, and A. Rondepierre , Continuized nesterov acceleration for non-convex optimization , arXiv preprint arXiv:2512.16533, (2025)

    arXiv 2025

  30. [30]

    Hermant, J.-F

    J. Hermant, J.-F. Aujol, C. Dossal, L. Huang, A. Rondepierre, and I. Waldspurger , Continuized nesterov momentum achieves the o( ^ -7/4 ) complexity without additional mechanisms , 2026, https://arxiv.org/abs/2602.05504, https://arxiv.org/abs/2602.05504

    Pith/arXiv arXiv 2026

  31. [31]

    Hinder, A

    O. Hinder, A. Sidford, and N. Sohoni , Near-optimal methods for minimizing star-convex functions and beyond , in Conference on learning theory, PMLR, 2020, pp. 1894--1938

    2020

  32. [32]

    Huang, S

    F. Huang, S. Gao, J. Pei, and H. Huang , Accelerated zeroth-order and first-order momentum methods from mini to minimax optimization , Journal of Machine Learning Research, 23 (2022), pp. 1--70

    2022

  33. [33]

    K. Ji, Z. Wang, Y. Zhou, and Y. Liang , Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization , in International Conference on Machine Learning, 2019, https://api.semanticscholar.org/CorpusID:174800372

    2019

  34. [34]

    Lara and C

    F. Lara and C. Vega , Delayed feedback in online non-convex optimization: a non-stationary approach with applications , Numerical Algorithms, (2025), pp. 1--42

    2025

  35. [35]

    J. C. Lee and P. Valiant , Optimizing star-convex functions , in 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2016, pp. 603--614

    2016

  36. [36]

    Lezane, S

    C. Lezane, S. Langer, and W. M. Koolen , Accelerated mirror descent for non-euclidean star-convex functions , arXiv preprint arXiv:2405.18976, (2024)

    Pith/arXiv arXiv 2024

  37. [37]

    Liu, P.-Y

    S. Liu, P.-Y. Chen, X. Chen, and M. Hong , signsgd via zeroth-order oracle , in International Conference on Learning Representations, 2019, https://api.semanticscholar.org/CorpusID:108298677

    2019

  38. [38]

    S. Ma, R. Bassily, and M. Belkin , The power of interpolation: Understanding the effectiveness of sgd in modern over-parametrized learning , in International Conference on Machine Learning, PMLR, 2018, pp. 3325--3334

    2018

  39. [39]

    Malladi, T

    S. Malladi, T. Gao, E. Nichani, A. Damian, J. D. Lee, D. Chen, and S. Arora , Fine-tuning language models with just forward passes , Advances in Neural Information Processing Systems, 36 (2023), pp. 53038--53075

    2023

  40. [40]

    Mart \' nez-Rubio , Smooth quasar-convex optimization with constraints , arXiv preprint arXiv:2510.01943, (2025)

    D. Mart \' nez-Rubio , Smooth quasar-convex optimization with constraints , arXiv preprint arXiv:2510.01943, (2025)

    Pith/arXiv arXiv 2025

  41. [41]

    A. S. Nemirovskij and D. B. Yudin , Problem complexity and method efficiency in optimization , (1983)

    1983

  42. [42]

    Nesterov , A method for solving the convex programming problem with convergence rate o (1/k2) , in Dokl akad nauk Sssr, vol

    Y. Nesterov , A method for solving the convex programming problem with convergence rate o (1/k2) , in Dokl akad nauk Sssr, vol. 269, 1983, p. 543

    1983

  43. [43]

    Nesterov , Introductory lectures on convex optimization

    Y. Nesterov , Introductory lectures on convex optimization. applied optimization , 2004

    2004

  44. [44]

    Nesterov, A

    Y. Nesterov, A. Gasnikov, S. Guminov, and P. Dvurechensky , Primal--dual accelerated gradient methods with small-dimensional relaxation oracle , Optimization Methods and Software, 36 (2021), pp. 773--810

    2021

  45. [45]

    Nesterov and V

    Y. Nesterov and V. Spokoiny , Random gradient-free minimization of convex functions , Foundations of Computational Mathematics, 17 (2017), pp. 527--566

    2017

  46. [46]

    Pun and I

    Y.-M. Pun and I. Shames , Online non-stationary stochastic quasar-convex optimization , arXiv preprint arXiv:2407.03601, (2024)

    Pith/arXiv arXiv 2024

  47. [47]

    W. Shi, H. Gao, and B. Gu , Gradient-free method for heavily constrained nonconvex optimization , in International Conference on Machine Learning, 2024, https://api.semanticscholar.org/CorpusID:250340939

    2024

  48. [48]

    Tang and N

    Y. Tang and N. Li , Distributed zero-order algorithms for nonconvex multi-agent optimization , 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), (2019), pp. 781--786, https://api.semanticscholar.org/CorpusID:201698248

    2019

  49. [49]

    Vaswani, F

    S. Vaswani, F. Bach, and M. Schmidt , Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron , in The 22nd international conference on artificial intelligence and statistics, PMLR, 2019, pp. 1195--1204

    2019

  50. [50]

    Wang and A

    J.-K. Wang and A. Wibisono , Continuized acceleration for quasar convex functions in non-convex optimization , 2023, https://arxiv.org/abs/2302.07851, https://arxiv.org/abs/2302.07851

    Pith/arXiv arXiv 2023

  51. [51]

    P. Yue, C. Fang, and Z. Lin , On the lower bound of minimizing P olyak- ojasiewicz functions , in The Thirty Sixth Annual Conference on Learning Theory, PMLR, 2023, pp. 2948--2968

    2023

  52. [52]

    Y. Zhou, J. Yang, H. Zhang, Y. Liang, and V. Tarokh , SGD converges to global minimum in deep learning via star-convex path , in International Conference on Learning Representations, 2019, https://openreview.net/forum?id=BylIciRcYQ

    2019