Pith. sign in

REVIEW 1 major objections 4 minor 56 references

Optimal Parameter-Free First-Order Methods for Convex Optimization with Unknown Growth and Smoothness

T0 review · 1 major / 4 minor · reviewed 2026-07-14 · grok-4.5

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

Pith's one-line read Anytime bundle-level methods attain optimal first-order rates for convex problems without knowing growth, smoothness, or target accuracy.

desk verdict Clean resolution of Nesterov's open question: optimal anytime rates under unknown growth and Hölder smoothness via a new affine W-certificate. read the letter →

arxiv 2607.11878 v1 pith:74X3SYVX submitted 2026-07-13 math.OC

Liwei Jiang , Ke Tang , Zhe Zhang This is my paper
classification math.OC MSC 90C2590C3065K05
keywords parameter-freeoptimizationbundle-levelmethodsquadraticgrowthHöldersmoothnessfirst-orderconvexanytimealgorithmsW-certificate
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 closes a long gap between methods that know problem parameters and methods that do not. It shows that a first-order algorithm can minimize a convex function at the best-known oracle rates without being told whether the objective is smooth or nonsmooth, how strongly it grows near the solution set, or how accurate the answer must be. The engine is an affine W-certificate: a linear lower model whose descent-slowness is large enough that, under quadratic growth, the model geometry certifies a bound on the optimality gap. That certificate is embedded in a certify-or-improve bundle subroutine and an outer search, producing BLW for nonsmooth quadratic growth and an accelerated A-BLW that matches optimal rates across Hölder smoothness regimes. The same unmodified A-BLW also recovers the best-known rates for general convex objectives and for Hölder growth of order at least two. A reader who wants black-box solvers that adapt automatically would care because the algorithm is genuinely anytime—it never takes the target accuracy as input—and still hits the classical optimal scalings, including the open nonsmooth quadratic-growth rate.

What carries the argument

The affine W-certificate: an affine minorant of the objective whose descent-slowness (distance needed per unit of descent) meets a trial threshold in the product of modulus and gap; it turns the projection geometry of a bundle model into a rigorous optimality-gap bound under quadratic growth.

What would settle it

On a family of nonsmooth Lipschitz objectives with known quadratic-growth modulus μ, count first-order oracle calls to reach accuracy ε; if the leading term grows strictly faster than a constant times M₀²/(μϵ) for small ε, or if A-BLW fails to match the rates in Table 1 when ρ and α are fixed but hidden from the algorithm, the central optimality claim is false.

Watch

Extended reading notes

Core claim

Without knowing the Hölder exponent, smoothness constant, growth modulus, or target accuracy, the accelerated bundle-level W-certificate method A-BLW attains the optimal oracle complexities for convex minimization under Hölder smoothness and quadratic growth—including O(M₀²/(μϵ)) in the nonsmooth case and the accelerated smooth linear rate—and the same algorithm without modification matches the best-known rates for general convex objectives and for α-Hölder growth with α≥2.

Load-bearing premise

Every projection subproblem onto the aggregate and retained cut half-spaces must return optimal dual multipliers that can be normalized into the next affine model; without those multipliers the aggregation that builds the certificate does not work.

Editorial extensions

If this is right

  • BLW solves nonsmooth Lipschitz problems with unknown quadratic growth at the optimal O(M₀²/(μϵ)) rate without taking μ or ε as input.
  • A-BLW matches optimal rates simultaneously in the nonsmooth, weakly smooth, and smooth regimes under quadratic growth without knowing the regime or its constants.
  • The same unmodified A-BLW recovers best-known rates for pure convex problems and for α-Hölder growth with α≥2 via a stopping-time argument.
  • The observable product of trial modulus and gap is a practical proxy for the optimality gap and can serve as a stopping criterion.
  • Accepted centers remain Fejér monotone, so the method stays inside the initial sublevel set where growth is assumed.

Reading between the lines

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

  • Because aggregation needs dual multipliers from each projection, the methods are most natural when the feasible set is simple (boxes, simplices, balls) so that those multipliers are cheap to extract.
  • The genuinely anytime design makes A-BLW a candidate drop-in solver when target accuracy is chosen online by watching the product of trial modulus and gap rather than fixed in advance.
  • The W-certificate idea is specific to deterministic first-order convex models; whether a similar descent-slowness test can certify growth in stochastic or nonconvex local settings is left open by the analysis.
  • When bundle memory exceeds the number of smooth pieces on piecewise-smooth problems, linear convergence appears in practice, suggesting polyhedral structure can beat the worst-case rates the theory guarantees.
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 / 4 minor

Summary. The paper develops anytime, parameter-free first-order methods for convex minimization that adapt to unknown Hölder smoothness and growth. It introduces the affine W-certificate (Definition 2.4), which converts descent-slowness of an affine minorant into an optimality-gap bound under quadratic growth (Proposition 2.3, Corollary 2.5). The BLCI subroutine and outer BLW search (Algorithms 1–2) achieve the optimal O(M₀²/(μϵ)) complexity for nonsmooth Lipschitz objectives with quadratic growth without knowing μ or ϵ (Theorem 3.5). Replacing BLCI by accelerated A-BLCI yields A-BLW, which attains the optimal rates of Table 1 across ρ∈[0,1] under quadratic growth without knowing ρ, M_ρ, μ, or ϵ (Theorem 4.5). A stopping-time argument (Section 4.2) shows the same unmodified algorithm recovers best-known rates for general convex objectives and α-Hölder growth with α≥2. Numerical experiments on matrix games, geometric median, and conditioned quadratics illustrate practical performance.

Significance. The work closes a long-standing gap between parameter-aware and parameter-free methods for nonsmooth and weakly smooth convex optimization under quadratic growth, a direction recently highlighted by Nesterov. The affine W-certificate is a clean geometric device that yields genuine anytime optimality without target accuracy as input, improving on restart schemes that incur multiplicative overhead. Full proofs are supplied for the certificate, progress bounds, product contraction, and complexity theorems; the dual-multiplier aggregation is explicitly flagged as a computational assumption (Remark 1). The stopping-time reduction to sequential quadratic growth and the geometric-envelope sums that remove the extra log at ρ=1 are technically careful. If the claims hold, the paper provides a uniformly optimal black-box method for a broad class of convex problems with unknown regularity.

major comments (1)
  1. The dual-multiplier extraction used to form aggregates (Lemma 3.1, Line 8 of Algorithms 1 and 3, Remark 1) is a computational assumption on the representation of X and the subproblem solver, not a pure existence claim. While the paper flags this correctly and notes closed-form multipliers when X=ℝ^d and m=1, the complexity statements are stated for general closed convex X. A short clarification of the precise class of sets for which the method is fully implementable (or an alternative aggregation that avoids explicit duals) would strengthen the claim of black-box applicability.
minor comments (4)
  1. Table 1 uses O_ρ and O_α notation; a brief sentence in the caption or introduction stating that these hide factors depending only on the fixed exponents would help readers.
  2. In Algorithm 2 the initial Δ₀ = 2∥f′(x̄₀)∥²/μ₀ is natural under QG, but the two-point rule (3.12) for μ₀ could be cross-referenced more prominently in the statement of Theorem 3.5.
  3. Figure 3 reports the heuristic μΔ/ω₀ alongside the true gap; the caption already notes it is not a certified bound, but a one-sentence reminder in the text of Section 5.2 would prevent misreading.
  4. A few minor typos appear (e.g., “H¨ older” spacing, “Fej´ er”); a light copy-edit pass would clean them.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: self-contained first-order complexity arguments from standard convex analysis.

full rationale

The paper derives oracle complexities for BLW and A-BLW from first principles: affine minorants, descent-slowness s(h,x̄,Δ), the W-certificate definition (Def. 2.4), projection three-point inequalities (Lemmas 3.1, 4.1), Hölder model-error progress (Props. 3.2, 4.2), outer product contraction μ_k Δ_k = (3/4)^k μ_0 Δ_0 with μ_k ≥ μ*/4 (Props. 3.4, 4.4), and a stopping-time reduction to sequential quadratic growth (Sec. 4.2) that recovers general convex and α-Hölder rates without algorithm modification. μ_0 is an algorithmic upper estimate from two oracle calls (Eq. 3.12), not a data fit that forces the claimed rates. Dual-multiplier extraction (Remark 1) is flagged as a computational assumption on X, not a circular premise. Citations to Lan, Nesterov, and others supply background or lower-bound comparisons; none are load-bearing uniqueness theorems or ansatzes that smuggle the result. The complexity statements in Table 1 and Theorems 3.5/4.5 are therefore independent of their inputs by construction.

Assumptions & free parameters 2 free parameters · 4 assumptions · 1 invented entities

The central claims rest on standard convex first-order assumptions plus the growth and Hölder conditions that define the problem classes. No free parameters are fitted to data; algorithmic constants (memory m, initial μ₀) do not appear in the leading complexity terms. The only invented device is the W-certificate, which is a definitional tool rather than a physical entity.

free parameters (2)
  • memory length m
    User-chosen integer ≥1; complexity bounds are independent of m, so it is not load-bearing for the rates, only for empirical speed.
  • initial modulus estimate μ₀
    Any upper bound on the true growth modulus; can be obtained from two oracle calls via (3.12). Appears only in lower-order log terms.
assumptions (4)
  • domain assumption f is closed convex, X closed convex, X* nonempty; first-order oracle returns f(x) and a subgradient.
    Standard black-box convex model stated in §1.
  • domain assumption Assumption A (Lipschitz / model-error bound with constant M) or Assumption C (Hölder smoothness with (ρ,M_ρ)).
    Defines the smoothness regimes whose optimal rates are claimed.
  • domain assumption Assumption B (quadratic growth with modulus μ* on the initial sublevel set) or the α-Hölder growth condition for α≥2.
    The growth hypothesis that the W-certificate exploits; without it the rates reduce to the classical convex ones via the stopping-time argument.
  • ad hoc to paper Projection subproblems onto polyhedral level sets of the aggregate model admit extractable optimal dual multipliers (Slater condition used in Lemma 3.1).
    Needed to form the affine aggregates that keep storage bounded; Remark 1 notes it is a computational assumption on the solver for X.
invented entities (1)
  • affine W-certificate (Definition 2.4)
    purpose: Converts descent-slowness of an affine minorant into a rigorous optimality-gap bound under quadratic growth without knowing μ*.
    Central algorithmic device introduced in §2; it is a definition, not an external physical object, and its correctness is proved from first principles.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Parameter-Free First-Order Methods for Convex Optimization with Unknown Growth and Smoothness." pith.science (2026). https://pith.science/paper/74X3SYVX

@misc{pith2026260711878,
  author       = {Pith},
  title        = {Pith review of: Optimal Parameter-Free First-Order Methods for Convex Optimization with Unknown Growth and Smoothness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/74X3SYVX}},
  note         = {Machine review of arXiv:2607.11878}
}
read the original abstract

We study deterministic first-order minimization of a convex function without prior knowledge of the objective's growth, smoothness regime, or associated parameters. We develop anytime, parameter-free bundle-level methods that adapt simultaneously to these unknown properties and attain best-known oracle complexities. For nonsmooth Lipschitz objectives satisfying quadratic growth, the proposed bundle-level W-certificate method (BLW) achieves the optimal complexity without requiring the growth modulus or target accuracy as input. We then introduce an accelerated variant, A-BLW. Without knowing the H\"older smoothness parameters, the quadratic-growth modulus, or the target accuracy, A-BLW attains the optimal rates in the nonsmooth, weakly smooth, and smooth regimes. Central to both methods is an affine W-certificate, a condition based on the descent-slowness of an affine minorant that converts the geometry of a bundle model into an optimality-gap guarantee under quadratic growth. A stopping-time analysis further shows that the same A-BLW algorithm, without modification, achieves the corresponding best-known rates for general convex objectives and for objectives satisfying H\"older growth of order at least two. Numerical experiments illustrate the practical performance of the proposed methods.

Figures

Figures reproduced from arXiv: 2607.11878 by the authors.

Figure 1
Figure 1. Matrix game with n = m = 512. The plot shows oracle calls versus the optimality gap of the best point found so far. Curves are averaged over ten random seeds. 28 [PITH_FULL_IMAGE:figures/full_fig_p028_1.png] view at source ↗
Figure 2
Figure 2. shows a visible sensitivity to εtarget. On these instances, the best FGM curve among the tested inputs is not obtained by the smallest εtarget; choosing ε too small requires excessive oracle calls since the complexity of FGM for nonsmooth problems is O(ϵ −2 ) even with quadratic growth. The A-BLW curve does not use such an input accuracy and continues to reduce the best gap over the plotted oracle-call budget. 100 1… view at source ↗
Figure 3
Figure 3. Geometric median instance with d = 256, M = 512, and one cut. Solid lines show the true optimality gap of the best point found so far. Dashed lines show the heuristic scale-normalized product µ∆/ω0; they are diagnostics, not certified gap bounds. In this experiment, the normalized product decreases in tandem with the true gap and is close to it near the end of the run. This empirical agreement is useful for visualiz… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Simplex-constrained quadratic problems. The plot shows the number of oracle calls [PITH_FULL_IMAGE:figures/full_fig_p031_4.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

56 extracted references · 16 linked inside Pith

  1. [1]

    Nemirovsky and D.B

    A.S. Nemirovsky and D.B. Yudin.Problem complexity and method efficiency in optimization. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1983. Translated from the Russian and with a preface by E. R. Dawson, Wiley-Interscience Series in Discrete Mathematics

    1983

  2. [2]

    Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization.Mathematical Programming, 149(1):1–45, 2015

    Guanghui Lan. Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization.Mathematical Programming, 149(1):1–45, 2015

    2015

  3. [3]

    Universal gradient methods for convex optimization problems.Mathematical Programming, 152(1):381–404, 2015

    Yu Nesterov. Universal gradient methods for convex optimization problems.Mathematical Programming, 152(1):381–404, 2015

    2015

  4. [4]

    A simple uniformly optimal method without line search for convex optimization.Mathematical Programming, 2025

    Tianjiao Li and Guanghui Lan. A simple uniformly optimal method without line search for convex optimization.Mathematical Programming, 2025

    2025

  5. [5]

    The lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems.SIAM Journal on Optimization, 17(4):1205–1223, 2007

    J´ erˆ ome Bolte, Aris Daniilidis, and Adrian Lewis. The lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems.SIAM Journal on Optimization, 17(4):1205–1223, 2007

    2007

  6. [6]

    Convex optimization: Algorithms and complexity.Foundations and Trends®in Machine Learning, 8(3-4):231–357, 2015

    S´ ebastien Bubeck et al. Convex optimization: Algorithms and complexity.Foundations and Trends®in Machine Learning, 8(3-4):231–357, 2015

    2015

  7. [7]

    Universal complexity bounds for universal gradient methods in nonlinear optimization, 2025

    Yurii Nesterov. Universal complexity bounds for universal gradient methods in nonlinear optimization, 2025

    2025

  8. [8]

    New variants of bundle methods

    Claude Lemar´ echal, Arkadii Nemirovskii, and Yurii Nesterov. New variants of bundle methods. Mathematical programming, 69(1):111–147, 1995

    1995

Show all 56 references
  1. [9]

    Golden ratio algorithms for variational inequalities.arXiv preprint arXiv:1803.08832, 2018

    Yura Malitsky. Golden ratio algorithms for variational inequalities.arXiv preprint arXiv:1803.08832, 2018

    2018 arXiv

  2. [10]

    Adabb: Adaptive barzilai-borwein method for convex optimization.Mathematics of Operations Research, 51(1):715–745, 2026

    Danqing Zhou, Shiqian Ma, and Junfeng Yang. Adabb: Adaptive barzilai-borwein method for convex optimization.Mathematics of Operations Research, 51(1):715–745, 2026. 32

    2026

  3. [11]

    An adaptive and parameter-free nesterov’s accelerated gradient method for convex optimization.arXiv preprint arXiv:2505.11670, 2025

    Jaewook J Suh and Shiqian Ma. An adaptive and parameter-free nesterov’s accelerated gradient method for convex optimization.arXiv preprint arXiv:2505.11670, 2025

    2025 arXiv

  4. [12]

    Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliers.arXiv preprint arXiv:2410.01979, 2024

    Guanghui Lan and Tianjiao Li. Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliers.arXiv preprint arXiv:2410.01979, 2024

    2024 arXiv

  5. [13]

    Projected gradient methods for nonconvex and stochastic optimization: new complexities and auto-conditioned stepsizes.arXiv preprint arXiv:2412.14291, 2024

    Guanghui Lan, Tianjiao Li, and Yangyang Xu. Projected gradient methods for nonconvex and stochastic optimization: new complexities and auto-conditioned stepsizes.arXiv preprint arXiv:2412.14291, 2024

    2024 arXiv

  6. [14]

    Uniformly optimal and parameter-free first-order methods for convex and function-constrained optimization.INFORMS Journal on Computing, 2026

    Qi Deng, Guanghui Lan, and Zhenwei Lin. Uniformly optimal and parameter-free first-order methods for convex and function-constrained optimization.INFORMS Journal on Computing, 2026

    2026

  7. [15]

    Simple linesearch-free first-order methods for nonconvex optimization.arXiv preprint arXiv:2509.14670, 2025

    Shotaro Yagishita and Masaru Ito. Simple linesearch-free first-order methods for nonconvex optimization.arXiv preprint arXiv:2509.14670, 2025

    2025

  8. [16]

    A simple adaptive proximal gradient method for nonconvex optimization.arXiv preprint arXiv:2510.06079, 2025

    Zilong Ye, Shiqian Ma, Junfeng Yang, and Danqing Zhou. A simple adaptive proximal gradient method for nonconvex optimization.arXiv preprint arXiv:2510.06079, 2025

    2025

  9. [17]

    Auto-conditioned frank- wolfe algorithms.arXiv preprint arXiv:2605.15512, 2026

    Khanh-Hung Giang-Tran, Soroosh Shafiee, and Nam Ho-Nguyen. Auto-conditioned frank- wolfe algorithms.arXiv preprint arXiv:2605.15512, 2026

    2026 arXiv

  10. [18]

    Stochastic auto-conditioned fast gradient methods with optimal rates.arXiv preprint arXiv:2604.06525, 2026

    Yao Ji and Guanghui Lan. Stochastic auto-conditioned fast gradient methods with optimal rates.arXiv preprint arXiv:2604.06525, 2026

    2026 arXiv

  11. [19]

    Universal and parameter-free gradient sliding for composite optimization.arXiv preprint arXiv:2603.23492, 2026

    Yan Wu, Yuyuan Ouyang, Zhe Zhang, and Qi Luo. Universal and parameter-free gradient sliding for composite optimization.arXiv preprint arXiv:2603.23492, 2026

    2026 arXiv

  12. [20]

    Problem-parameter-free decentralized nonconvex stochastic optimization.arXiv preprint arXiv:2402.08821, 2024

    Jiaxiang Li, Xuxing Chen, Shiqian Ma, and Mingyi Hong. Problem-parameter-free decentralized nonconvex stochastic optimization.arXiv preprint arXiv:2402.08821, 2024

    2024 arXiv

  13. [21]

    Nesterov finds graal: Optimal and adaptive gradient method for convex optimization.arXiv preprint arXiv:2507.09823, 2025

    Ekaterina Borodich and Dmitry Kovalev. Nesterov finds graal: Optimal and adaptive gradient method for convex optimization.arXiv preprint arXiv:2507.09823, 2025

    2025 arXiv

  14. [22]

    Universal subgradient and proximal bundle methods for convex and strongly convex hybrid composite optimization

    Vincent Guigues, Jiaming Liang, and Renato DC Monteiro. Universal subgradient and proximal bundle methods for convex and strongly convex hybrid composite optimization. Journal of Optimization Theory and Applications, 208(3):112, 2026

    2026

  15. [23]

    Universal gradient methods for stochastic convex optimization.arXiv preprint arXiv:2402.03210, 2024

    Anton Rodomanov, Ali Kavis, Yongtao Wu, Kimon Antonakopoulos, and Volkan Cevher. Universal gradient methods for stochastic convex optimization.arXiv preprint arXiv:2402.03210, 2024

    2024 arXiv

  16. [24]

    Linesearch-free adaptive bregman proximal gradient for convex minimization without relative smoothness.arXiv preprint arXiv:2508.01353, 2025

    Hongjia Ou, Puya Latafat, and Andreas Themelis. Linesearch-free adaptive bregman proximal gradient for convex minimization without relative smoothness.arXiv preprint arXiv:2508.01353, 2025

    2025 arXiv

  17. [25]

    Parameter-free accelerated gradient descent for nonconvex minimization.SIAM Journal on Optimization, 34(2):2093–2120, 2024

    Naoki Marumo and Akiko Takeda. Parameter-free accelerated gradient descent for nonconvex minimization.SIAM Journal on Optimization, 34(2):2093–2120, 2024

  18. [26]

    Adaptive gradient descent without descent

    Yura Malitsky and Konstantin Mishchenko. Adaptive gradient descent without descent. In Proceedings of the 37th International Conference on Machine Learning (ICML)(2020), volume 119, 2020. 33

    2020

  19. [27]

    Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization.Mathematical Programming, 2026

    Guanghui Lan, Yuyuan Ouyang, and Zhe Zhang. Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization.Mathematical Programming, 2026

    2026

  20. [28]

    An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization.Computational Optimization and Applications, 60(3):633–674, 2015

    Qihang Lin and Lin Xiao. An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization.Computational Optimization and Applications, 60(3):633–674, 2015

    2015

  21. [29]

    Adaptive restart of accelerated gradient methods under local quadratic growth condition.IMA Journal of Numerical Analysis, 39(4):2069–2095, 2019

    Olivier Fercoq and Zheng Qu. Adaptive restart of accelerated gradient methods under local quadratic growth condition.IMA Journal of Numerical Analysis, 39(4):2069–2095, 2019

  22. [30]

    Adaptive accelerated gradient converging methods under H¨ olderian error bound condition

    Mingrui Liu and Tianbao Yang. Adaptive accelerated gradient converging methods under H¨ olderian error bound condition. InAdvances in Neural Information Processing Systems, volume 30, pages 3104–3114, 2017

    2017

  23. [31]

    Sharpness, restart, and acceleration.SIAM Journal on Optimization, 30(1):262–289, 2020

    Vincent Roulet and Alexandre d’Aspremont. Sharpness, restart, and acceleration.SIAM Journal on Optimization, 30(1):262–289, 2020

    2020

  24. [32]

    A simple nearly-optimal restart scheme for speeding- up first order methods.Foundations of Computational Mathematics, 22(1):211–256, 2022

    James Renegar and Benjamin Grimmer. A simple nearly-optimal restart scheme for speeding- up first order methods.Foundations of Computational Mathematics, 22(1):211–256, 2022

    2022

  25. [33]

    Efficient parameter-free restarted accelerated gradient methods for convex and strongly convex optimization: A

    Arnesh Sujanani and Renato DC Monteiro. Efficient parameter-free restarted accelerated gradient methods for convex and strongly convex optimization: A. sujanani, rdc monteiro. Journal of Optimization Theory and Applications, 206(2):52, 2025

    2025

  26. [34]

    Masaru Ito and Mituhiro Fukuda. Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approach.Journal of Optimization Theory and Applications, 188(3):770–804, 2021

    2021

  27. [35]

    A parameter-free restart scheme with only a parallelizable log log(1/ϵ) overhead.arXiv preprint arXiv:2605.30502, 2026

    Yue Wu and Benjamin Grimmer. A parameter-free restart scheme with only a parallelizable log log(1/ϵ) overhead.arXiv preprint arXiv:2605.30502, 2026

    2026 arXiv

  28. [36]

    Burke and Michael C

    James V. Burke and Michael C. Ferris. Weak sharp minima in mathematical programming. SIAM Journal on Control and Optimization, 31(5):1340–1359, 1993

    1993

  29. [37]

    Generic minimizing behavior in semialgebraic optimization.SIAM Journal on Optimization, 26(1):513–534, 2016

    Dmitriy Drusvyatskiy, Alexander D Ioffe, and Adrian S Lewis. Generic minimizing behavior in semialgebraic optimization.SIAM Journal on Optimization, 26(1):513–534, 2016

    2016

  30. [38]

    Dmitriy Drusvyatskiy and Adrian S. Lewis. Error bounds, quadratic growth, and linear convergence of proximal methods.Mathematics of Operations Research, 43(3):919–948, 2018

    2018

  31. [39]

    From error bounds to the complexity of first-order descent methods for convex functions.Mathematical Programming, 165(2):471–507, 2017

    J´ erˆ ome Bolte, Tien Son Nguyen, Juan Peypouquet, and Bruce W Suter. From error bounds to the complexity of first-order descent methods for convex functions.Mathematical Programming, 165(2):471–507, 2017

    2017

  32. [40]

    Linear convergence of gradient and proximal- gradient methods under the polyak- lojasiewicz condition

    Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak- lojasiewicz condition. InMachine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 1...

    2016

  33. [41]

    Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth: D

    Damek Davis, Dmitriy Drusvyatskiy, and Liwei Jiang. Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth: D. davis et al.Mathematical Programming, pages 1–66, 2025. 34

    2025

  34. [42]

    MacPhee, and Courtney Paquette

    Damek Davis, Dmitriy Drusvyatskiy, Kellie J. MacPhee, and Courtney Paquette. Subgradient methods for sharp weakly convex functions.Journal of Optimization Theory and Applications, 179(3):962–982, 2018

    2018

  35. [43]

    Stochastic algorithms with geometric step decay converge linearly on sharp functions.Mathematical Programming, 207(1):145–190, 2024

    Damek Davis, Dmitriy Drusvyatskiy, and Vasileios Charisopoulos. Stochastic algorithms with geometric step decay converge linearly on sharp functions.Mathematical Programming, 207(1):145–190, 2024

    2024

  36. [44]

    A superlinearly convergent subgradient method for sharp semismooth problems.Mathematics of Operations Research, 49(3):1678–1709, 2024

    Vasileios Charisopoulos and Damek Davis. A superlinearly convergent subgradient method for sharp semismooth problems.Mathematics of Operations Research, 49(3):1678–1709, 2024

    2024

  37. [45]

    Survey descent: A multipoint generalization of gradient descent for nonsmooth optimization.SIAM Journal on Optimization, 33(1):36–62, 2023

    XY Han and Adrian S Lewis. Survey descent: A multipoint generalization of gradient descent for nonsmooth optimization.SIAM Journal on Optimization, 33(1):36–62, 2023

    2023

  38. [46]

    A local nearly linearly convergent first-order method for nonsmooth functions with quadratic growth.Foundations of Computational Mathematics, 25(3):943–1024, 2025

    Damek Davis and Liwei Jiang. A local nearly linearly convergent first-order method for nonsmooth functions with quadratic growth.Foundations of Computational Mathematics, 25(3):943–1024, 2025

    2025

  39. [47]

    Lipschitz minimization and the goldstein modulus: S

    Siyu Kong and Adrian S Lewis. Lipschitz minimization and the goldstein modulus: S. kong, as lewis.Mathematical Programming, pages 1–30, 2025

    2025

  40. [48]

    Subgradient regularization: A descent-oriented subgradient method for nonsmooth optimization.arXiv preprint arXiv:2505.07143, 2025

    Hanyang Li and Ying Cui. Subgradient regularization: A descent-oriented subgradient method for nonsmooth optimization.arXiv preprint arXiv:2505.07143, 2025

    2025 arXiv

  41. [49]

    Linearly convergent algorithms for nonsmooth problems with unknown smooth pieces.arXiv preprint arXiv:2507.19465, 2025

    Zhe Zhang and Suvrit Sra. Linearly convergent algorithms for nonsmooth problems with unknown smooth pieces.arXiv preprint arXiv:2507.19465, 2025

    2025 arXiv

  42. [50]

    Accelerated prox-level methods for unknown piecewise-smooth optimization I: Convex optimization.arXiv preprint arXiv:2601.14680, 2026

    Zhenwei Lin and Zhe Zhang. Accelerated prox-level methods for unknown piecewise-smooth optimization I: Convex optimization.arXiv preprint arXiv:2601.14680, 2026

    2026 arXiv

  43. [51]

    Springer, 2020

    Guanghui Lan.First-order and stochastic optimization methods for machine learning, volume 1. Springer, 2020

    2020

  44. [52]

    Dual subgradient algorithms for large- scale nonsmooth learning problems.Mathematical Programming, 148(1-2):143–180, December 2014

    Bruce Cox, Anatoli Juditsky, and Arkadi Nemirovski. Dual subgradient algorithms for large- scale nonsmooth learning problems.Mathematical Programming, 148(1-2):143–180, December 2014

    2014

  45. [53]

    Springer Science & Business Media, 2003

    Yurii Nesterov.Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003

    2003

  46. [54]

    Lower complexity bounds for minimizing regularized functions.Optimization Letters, 19(9):1759–1778, 2025

    Nikita Doikov. Lower complexity bounds for minimizing regularized functions.Optimization Letters, 19(9):1759–1778, 2025

    2025

  47. [55]

    General H¨ older smooth convergence rates follow from specialized rates assuming growth bounds.arXiv preprint arXiv:2104.10196, 2023

    Benjamin Grimmer. General H¨ older smooth convergence rates follow from specialized rates assuming growth bounds.arXiv preprint arXiv:2104.10196, 2023

    2023 arXiv

  48. [56]

    Linearly convergent algorithms for nonsmooth problems with unknown smooth pieces, 2025

    Zhe Zhang and Suvrit Sra. Linearly convergent algorithms for nonsmooth problems with unknown smooth pieces, 2025. 35 A Auxiliary results A.1 A geometrically capped moment bound Lemma A.1(Geometrically capped moment bound).Letρ∈[0,1],N≥0, andB >0. Suppose thata 0, . . . , aN ∈R...

    2025

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.