A Few Accelerated Algorithms for Convex Optimization under $(H_0,H_1)$-Smoothness

Aleksandr Lobanov

REVIEW 2 major objections 3 minor 48 references

A Few Accelerated Algorithms for Convex Optimization under $(H_0,H_1)$-Smoothness

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

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

Pith's one-line read First accelerated full-gradient and coordinate guarantees for convex $(H_0,H_1)$-smooth functions: $\tilde O(\tilde R\sqrt{H_0/\epsilon} + \tilde R\sqrt{H_1}\log(F_0/\epsilon))$ iterations, with coordinate variants paying the usual factor…

desk verdict Solid, honestly-written theory paper: first accelerated full-gradient and coordinate rates for convex (H0,H1)-smooth functions, with complete proofs; main caveat is the exact-f* requirement, which is disclosed but genuinely restrictive. read the letter →

arxiv 2608.04884 v1 pith:MDQ6QOCS submitted 2026-08-05 math.OC

Aleksandr Lobanov This is my paper · ORCID

classification math.OC MSC 90C2590C0665K05

keywords (H0H1)-smoothnessgeneralizedsmoothnessacceleratedgradientmethodcoordinatedescentnon-uniformsamplingconvexoptimizationrestartschemeoptimality-gapcurvature

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 the first accelerated optimization guarantees for convex functions whose curvature is not a global constant but shrinks as the function value approaches its minimum — the $(H_0,H_1)$-smooth class, where $\|\nabla^2 f(x)\| \le H_0 + H_1(f(x)-f^*)$. The central claim is that a restart scheme whose inner accelerated method estimates curvature from the current gap reaches accuracy $\epsilon$ in $\tilde O(\tilde R\sqrt{H_0/\epsilon} + \tilde R\sqrt{H_1}\log(F_0/\epsilon))$ full-gradient iterations, with randomized coordinate variants paying only the usual dimension factors. A careful reader should care because all prior rates for this class were non-accelerated, and the natural alternative of freezing curvature on the initial sublevel set would replace the logarithmic $H_1$-term by a $1/\epsilon$-type penalty. When $H_1 = 0$, the bound reduces to the classical Nesterov rate, so the result is a genuine generalization rather than a different model.

What carries the argument

The load-bearing mechanism is the restart meta-algorithm (Algorithm 1): a geometric schedule of certified gap levels $\Delta_s$ makes the effective curvature $H_0 + H_1\Delta_s$ that each inner phase must control decay by half each phase. The inner methods (Algorithms 2–4) are accelerated gradient schemes with small-dimensional segment relaxation; each step chooses $M_k$ in the interval between $\hat{M}_k = \max\{2(H_0 + H_1 F(y_k)), \|\nabla f(y_k)\|/r_1\}$ and $\tau C_\star(H_0 + H_1 F(y_k))$, where $r_1$ is the radius of validity of the local quadratic model and $C_\star = 19 + 12\sqrt{2}$ (Lemma 10). The accelerated potential $\Phi_k = A_k F(x_k) + \tfrac{1}{2}\|v_k - x^*\|^2$ is non-increasing (in expectation, for coordinate variants), and the weight growth $A_N \ge \theta N^2/(4\tau C_\star(H_0 + H_1\Delta))$ converts potential decay into the per-phase contraction $F(z_{s+1}) \le \Delta_s/2$ that the wrapper needs.

What would settle it

On the paper's own chain-$\cosh$ objective ($H_0=1$, $H_1=4$), Theorem 5 predicts iteration counts growing like a constant plus $\log(F_0/\epsilon)$ in the gap-dominated regime; if counts were observed to grow faster than logarithmically as the relative gap goes from $10^{-2}$ to $10^{-8}$, the rate would be wrong. A sharper test: a pure gap-curvature objective with $H_0 = 0$ (e.g., the $\cosh$-type term in Section 6 with the quadratic baseline removed) should require only $O(\tilde R\sqrt{H_1}\log(F_0/\epsilon))$ iterations — counts scaling like $1/\sqrt{\epsilon}$ would refute the claimed separation of $H_0$ and $H_1$. Separately, re-running Algorithm 1 with $f^*$ replaced by $f^* + c$ for $c > 0$ should destroy the $\Delta/2$ phase contraction, confirming that exact $f^*$ is genuinely load-bearing.

Watch

Extended reading notes

Core claim

Under convexity and local $(H_0,H_1)$-smoothness (Assumptions 1–2), the paper claims that a restart wrapper which halves a certified gap level $\Delta_s = F_0/2^s$ each phase, driving a Nesterov-type inner method whose curvature estimate $M_k$ is pinned to the current gap $H_0 + H_1 F(y_k)$ and to the local-model radius $r_1$, reaches $F(z_S) \le \epsilon$ in $N_{tot} = O(\tilde R\sqrt{H_0/\epsilon} + \tilde R\sqrt{H_1}\log(F_0/\epsilon))$ full-gradient iterations (Theorem 5). Uniformly sampled coordinate updates pay the standard extra factor $d$ (Theorem 6), and non-uniform sampling with probabilities $p_{k,i} \propto \sqrt{H_{0,i} + H_{1,i}F(y_k)}$ replaces $d\sqrt{H_j}$ by $S^{(j)}_{1/2} = \sum_i \sqrt{H_{j,i}}$ (Theorem 8). The $H_1$ contribution enters only logarithmically in the accuracy $\epsilon$ — a strongly-convex-like dependence — instead of the $F_0/\epsilon$ penalty that freezing curvature at the initial sublevel set would cost. The paper also argues these are the first accelerated full-gradient and coordinate guarantees for this convex class.

Load-bearing premise

The load-bearing input is the exact optimum value $f^*$: the step sizes, the coordinate sampling odds, and the restart test are all computed from the gap $f(x) - f^*$, and Section 7 states that if $f^*$ is unknown the algorithms cannot compute their own parameters and its removal remains an open limitation.

Editorial extensions

If this is right

When $H_1 = 0$ the bound collapses to $O(\tilde R\sqrt{H_0/\epsilon})$, the classical Nesterov rate, so the method is a strict generalization of accelerated gradient descent.
Because the $(H_0,H_1)$ class strictly contains the convex $(L_0,L_1)$-smooth class, the results give the first accelerated guarantees for $(L_0,L_1)$-smooth convex functions as well, including functions that satisfy no finite $(L_0,L_1)$ condition.
The $H_1$-term enters only as $\sqrt{H_1}\log(F_0/\epsilon)$, a strongly-convex-like dependence: in the gap-dominated regime the phases contract geometrically, whereas freezing curvature on the initial sublevel set would incur a $\sqrt{F_0/\epsilon}$-type penalty.
Non-uniform sampling replaces the uniform factor $d\sqrt{H_j}$ by $S^{(j)}_{1/2} = \sum_i \sqrt{H_{j,i}}$, so curvature concentrated on $m \ll d$ coordinates lowers the coordinate rate from $d$ to $O(m)$-type sums.
The inexact segment relaxation with the phase-wise residual schedule from Corollary 14 preserves all three iteration bounds up to constants, with one-dimensional solver calls counted separately, so the theory supports implementable line searches.

Reading between the lines

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

An implication the authors leave implicit: whenever $H_1 F(x) \gg H_0$ along most of the trajectory, the same restart schedule makes the gap contract geometrically, so $(H_0,H_1)$-smoothness offers a curvature-fading explanation for the near-linear training curves that warm-up schedules produce in practice — a claim the paper does not make.
A testable extension: substituting a valid upper bound on $f^*$ (dual certificate, realizable-loss value, or Polyak-type estimate) into the restart test should preserve the three rates, because the proofs use $F(\cdot)$ only through upper bounds; the paper states the exact-$f^*$ requirement remains a limitation.
Remark 9's phase-frozen sampling probabilities are proven rate-equivalent, which suggests an implementation could refresh the distribution once per phase and still keep Theorem 8's complexity — worth an experiment the paper does not run beyond its own sweep.
The U-shaped cost curve in Appendix E.3 (optimal fixed residual near $10^{-6}$ on the chain-cosh problem) implies the practical bottleneck is the segment solver's stopping rule; an adaptive tolerance matching the per-phase allowance $A_{k+1}\delta_k \le A_{s,N}\Delta_s/(4N_s)$ would be the natural follow-up test.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

This paper delivers what it promises: accelerated full-gradient and coordinate descent rates for convex functions satisfying the (H0,H1)-smoothness condition, stated in the native H0,H1 parameters. As far as I can tell from the cited literature, these are indeed the first such guarantees, and the appendices go to unusual lengths to make the proofs checkable. The restart potential arguments in Appendices B–D are detailed and internally consistent; I did not find a gap in the central complexity claims. The separation examples (H0,H1) vs (L0,L1) are correct, and Appendix G adds a genuinely useful incomparability result with general ℓ-smoothness. Credit where due: the paper is careful, honest about its limitations, and does not oversell the practical reach.

The soft spot is the one the stress-test note flags: every algorithm needs the exact value of f*. This is not a minor practical caveat. The optimality gap enters the curvature estimates, the non-uniform sampling probabilities, and the restart acceptance test. Without f* you cannot compute the phase schedule, and replacing f* by a lower bound only works if that bound is within O(epsilon) of f*, which is generally as hard as solving the problem. The authors disclose this in Section 7 and point to realizable zero-loss settings where f* is known, so the results are honest as conditional guarantees. But the condition is load-bearing: for general convex (H0,H1)-smooth problems with unknown f*, the theorems do not give implementable algorithms. I would rate this a significant limitation, not a fatal one, because the paper is explicitly framed around the known-f* case and the theory is still meaningful there.

Minor additional notes: the experiments are illustrative but ship no code or data, so the numerical claims are not independently reproducible. The exact segment minimization in the inner loop is idealized, but Appendix F.1 shows a verifiable inexact variant with logarithmic extra cost, which is a reasonable response.

Who is this for? Researchers working on generalized smoothness, warm-up theory, or coordinate methods who want to know the state of the art for (H0,H1)-convex optimization. The paper deserves a serious referee: the proofs are worth checking in detail, the contribution is real, and a good referee could push the authors to clarify the f* limitation in the abstract and introduction rather than burying it in Section 7. I would accept it for peer review with the expectation of revision, mainly to sharpen the message about the known-f* assumption.

Referee Report

2 major / 3 minor

Summary. The paper develops accelerated first-order methods for convex minimization under (H0,H1)-smoothness, a gap-dependent curvature condition in which the Hessian is bounded by H0 + H1(f(x)-f*). The main algorithmic structure is a restart meta-algorithm (Algorithm 1) combined with three inner methods: an accelerated full-gradient method with small-dimensional segment relaxation (Algorithm 2), a uniformly sampled coordinate version (Algorithm 3), and a non-uniformly sampled coordinate version (Algorithm 4). The main results, Theorems 5, 6, and 8, give iteration complexities of order eR sqrt(H0/eps) + eR sqrt(H1) log(F0/eps) for the full-gradient method, the same rate multiplied by d for uniform coordinates, and a rate governed by coordinate-wise sums S_{1/2}^{(0)}, S_{1/2}^{(1)} for non-uniform sampling. The paper also provides separation examples showing that the (H0,H1)-smooth class is strictly broader than the (L0,L1)-smooth class, numerical experiments, and appendices containing complete proofs together with extensions for inexact segment relaxation and adaptive phase lengths.

Significance. If the results are taken as stated, the paper would provide the first accelerated full-gradient and coordinate guarantees for the convex (H0,H1)-smooth class, with a clean separation of the H0 and H1 contributions and with a natural extension to importance-sampled coordinates. The appendix supplies full proofs of the three main theorems, and the experiments are relevant to the claimed acceleration and to the gains from non-uniform sampling. The main qualification is that all proposed algorithms require the exact value f*, and this requirement is load-bearing for implementability; the theorem statements do not currently state this information assumption, so the contribution must be reframed before the claims can be accepted at face value.

major comments (2)

[Section 7 / Algorithms 2–4 / Theorem 5] All three complexity results require the exact value f*, and this is load-bearing rather than a practical caveat. The curvature M_k in line 4 of Algorithm 2 (and the analogous lines of Algorithms 3 and 4) is defined through F(y_k)=f(y_k)-f*; the sampling probabilities p_{k,i} in Algorithm 4 also depend on F(y_k); and the restart schedule Delta_s=F0/2^s, together with the acceptance test in Algorithm 1 and Algorithm 5, requires F(z_s)=f(z_s)-f*. If f* is unknown, the phase lengths N(Delta) cannot be computed and the updates cannot be executed. A valid lower bound l<f* does not resolve the issue: certifying F(z_{s+1})<=Delta/2 would require l to be within Delta/2 of f*, and for the final accuracy this is as hard as solving the problem. The theorem statements currently present unconditional 'returns a point with F(z_S)<=eps' guarantees. They should be restated explicitly as conditional on an f*-oracle, or the class of instances (for example, realizable losses with f*=0) for which the algorithms are implementable should be delimited.
[Table 1 / Section 2 / Section 4.2] The novelty claims about coordinate methods are internally inconsistent. Table 1 lists Vankov et al. (2025) as an accelerated coordinate method for convex (L0,L1)-smooth functions, with both Acceleration and CM checked, while Section 2 states that 'no previous coordinate method is both accelerated and applicable to convex (L0,L1)-smooth objectives'. Since Section 4.2's claim that Theorem 6 is the first accelerated coordinate guarantee depends on this point, the contradiction must be resolved by correcting the table or the text. Several other checkmark patterns in the same table (for example, the Nesterov & Stich and Lobanov et al. rows) also appear inconsistent with the surrounding discussion and should be checked.

minor comments (3)

[Theorems 5, 6, 8] The theorem statements say that the exact segment solve in line 3 is treated as one call per iteration, but an exact one-dimensional minimization may require an unbounded number of oracle queries in general; the paper should either define this as an idealized small-dimensional relaxation oracle or state the additional regularity needed for the logarithmic-cost inexact solver in Appendix F.1.
[Algorithm 4] The symbol M_k is used both for the individual coordinate curvatures M_{k,i} and for their normalizing sum; using a distinct symbol for the normalizer would improve readability and avoid confusion in the proofs.
[Appendix F.1 / Section 7] The claim that the inexact line search preserves the same total oracle complexity relies on an L_{seg,k}-Lipschitz assumption on the derivative of the one-dimensional restriction, which is not part of Assumptions 1 or 2; this extra condition should be stated explicitly wherever the logarithmic-cost line-search claim is made.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity found; the complexity theorems are derived from stated assumptions, and the exact-f* requirement is an explicit implementability limitation, not a circular step.

full rationale

The paper's central claims are conditional guarantees: given convexity, (H0,H1)-smoothness, valid upper bounds on H0,H1, the level-set radius eR (or a verified doubling variant), and knowledge of f*, the restart wrapper with Algorithms 2--4 contracts the optimality gap geometrically. The proofs are self-contained: Lemma 10 derives the gradient/curvature bound directly from Assumption 2; potential-function and weight-growth arguments yield one-phase estimates; the phase-length rules are then chosen algebraically so that F(z_{s+1}) <= Delta_s/2. No parameter is fitted to a subset of data and then renamed as a prediction. The external citations that are load-bearing (Alimisis et al. 2025 for the (L0,L1)-subset containment; Liu et al. 2025b Lemma 2 for the Hessian/local-model correspondence; Nesterov et al. and Vankov et al. for the small-dimensional relaxation template) are independent supporting results and do not import the target accelerated rates. Self-citations (e.g., Lobanov & Koloskova 2026) appear as contextual comparisons or experimental baselines, not as the proof's load-bearing premise. Section 7 explicitly acknowledges that all methods require the exact value f*, because the gap enters the local curvature, the non-uniform sampling probabilities, and the restart test. This is a substantial implementability limitation, but it is not circularity: f* is an assumed input to the algorithm, and knowing f* does not by itself yield an epsilon-optimal point; the guarantee remains a nontrivial conditional statement about iteration complexity. Appendix F.2 further removes prior knowledge of eR from the algorithmic inputs via verified doubling, so the main theorems are not reduced to their own conclusions. Thus no circular step is exhibited, and the appropriate score is 0.

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

The central claim rests on convexity with a bounded solution set, the (H0,H1) local model with known constants, knowledge of f*, and the availability of one-dimensional segment minimization (later relaxed). None of these are fitted; they are inputs to the theorems.

assumptions (5)

domain assumption Convexity and nonempty bounded solution set for f (Assumption 1 and Lemma 11).
Used to guarantee y_k segment minimization, potential inequalities, finite eR, and geometric restart contraction.
domain assumption (H0,H1)-smooth local quadratic model holds within radius r1 (Assumption 2), with valid H0,H1 known.
Core curvature model; the algorithms and all phase-length rules are built on it. The coordinate extension uses Assumption 7.
domain assumption Exact knowledge of f* and F0, and valid upper bounds on H0,H1 (or H0,i,H1,i) as algorithm inputs.
Stated in Section 7 as required: the gap F(yk) enters curvature, sampling probabilities, and restart tests. Without f* the algorithms cannot run.
domain assumption Exact minimizer of the one-dimensional segment problem is computable (or a delta-relaxed point via bisection, Appendix F.1).
Main theorems count the exact segment solve as one call; the inexact variant changes O to O-tilde and is verified in the appendix.
standard math Standard analytical inequalities: convexity, Cauchy-Schwarz, Jensen, and tower property for expectations.
Used in Appendix proofs; uncontroversial background.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Few Accelerated Algorithms for Convex Optimization under $(H_0,H_1)$-Smoothness." pith.science (2026). https://pith.science/paper/MDQ6QOCS

@misc{pith2026260804884,
  author       = {Pith},
  title        = {Pith review of: A Few Accelerated Algorithms for Convex Optimization under $(H_0,H_1)$-Smoothness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MDQ6QOCS}},
  note         = {Machine review of arXiv:2608.04884}
}

abstract

We develop accelerated algorithms for convex $(H_0,H_1)$-smooth optimization, where $\|\nabla^2 f(x)\|\le H_0+H_1(f(x)-f^*)$. This class generalizes standard smoothness and contains the $(L_0,L_1)$-smooth class. Combining a Nesterov-type accelerated gradient scheme with small-dimensional relaxation and phase restarts, we obtain a full-gradient method with iteration complexity $\widetilde O(\sqrt{H_0\widetilde R^2/\varepsilon}+\sqrt{H_1\widetilde R^2}\log(F_0/\varepsilon))$. We extend the same approach to randomized coordinate optimization, obtaining a coordinate method with uniform sampling whose iteration complexity carries the standard factor $d$, and a coordinate method with non-uniform sampling whose iteration complexity is governed by $S_{1/2}^{(j)}=\sum_i\sqrt{H_{j,i}}$. These results provide, to our knowledge, the first accelerated full-gradient and coordinate guarantees for this convex class. We also provide practical implementation recommendations. Experiments confirm the predicted acceleration, gains from non-uniform sampling, and the viability of inexact relaxation.

Figures

Figures reproduced from arXiv: 2608.04884 by the authors.

**Figure 2.** Full-gradient methods on the capped-exponential covtype.binary objective: relative gap versus (a) outer iterations and (b) total first-order oracle calls, and (c) runtime. The horizontal line marks the desired relative gap 10−4 ; runtime bars show medians and interquartile ranges over ten runs on an NVIDIA A100 80GB GPU. Discussion. The initial portions of the convergence curves in Figures 2(a)–(b) are approximately… view at source ↗

**Figure 3.** Our uniform and non-uniform coordinate methods on the anisotropic capped-cosh objective: relative gap versus (a) coordinate-gradient calls and (b) coordinate-gradient plus function-value calls. Segment relaxation uses only function comparisons. Curves and bands show medians and interquartile ranges over 20 seeds. Discussion. Both curves exhibit an approximately linear initial segment on the semilogarithmic scale, a… view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Iteration, primitive-query, runtime, and potential diagnostics as a function of the requested [PITH_FULL_IMAGE:figures/full_fig_p040_4.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

48 extracted references · 29 canonical work pages

[1]

, title =

Nesterov, Yurii E. , title =. Doklady Akademii Nauk SSSR , volume =

work page
[2]

Nesterov, Yurii , title =
[3]

2006 , publisher=

Numerical optimization , author=. 2006 , publisher=

2006
[4]

SIAM Journal on Optimization , volume =

Nesterov, Yurii , title =. SIAM Journal on Optimization , volume =

work page
[5]

Mathematical Programming , volume =

Richtarik, Peter and Takac, Martin , title =. Mathematical Programming , volume =

work page
[6]

SIAM Journal on Optimization , volume =

Fercoq, Olivier and Richtarik, Peter , title =. SIAM Journal on Optimization , volume =

work page
[7]

Proceedings of the 33rd International Conference on Machine Learning , year =

Allen-Zhu, Zeyuan and Qu, Zheng and Richtarik, Peter and Yuan, Yang , title =. Proceedings of the 33rd International Conference on Machine Learning , year =

work page
[8]

Optimization Methods for Large-Scale Machine Learning , journal =

Bottou, L. Optimization Methods for Large-Scale Machine Learning , journal =

Show all 48 references

[9]

Journal of Machine Learning Research , volume =

Duchi, John and Hazan, Elad and Singer, Yoram , title =. Journal of Machine Learning Research , volume =
[10]

and Ba, Jimmy , title =

Kingma, Diederik P. and Ba, Jimmy , title =. International Conference on Learning Representations , year =
[11]

International Conference on Learning Representations , year =

Loshchilov, Ilya and Hutter, Frank , title =. International Conference on Learning Representations , year =
[12]

arXiv preprint arXiv:2502.16982 , year=

Muon is scalable for llm training , author=. arXiv preprint arXiv:2502.16982 , year=

arXiv
[13]

Proceedings of the 30th International Conference on Machine Learning , pages =

Pascanu, Razvan and Mikolov, Tomas and Bengio, Yoshua , title =. Proceedings of the 30th International Conference on Machine Learning , pages =
[14]

arXiv preprint arXiv:1706.02677 , year=

Accurate, large minibatch sgd: Training imagenet in 1 hour , author=. arXiv preprint arXiv:1706.02677 , year=

arXiv
[15]

and Kaiser, Lukasz and Polosukhin, Illia , title =

Vaswani, Ashish and Shazeer, Noam and Parmar, Niki and Uszkoreit, Jakob and Jones, Llion and Gomez, Aidan N. and Kaiser, Lukasz and Polosukhin, Illia , title =. Advances in Neural Information Processing Systems , year =
[16]

Brown, Tom B. and Mann, Benjamin and Ryder, Nick and Subbiah, Melanie and Kaplan, Jared and Dhariwal, Prafulla and Neelakantan, Arvind and Shyam, Pranav and Sastry, Girish and Askell, Amanda and Agarwal, Sandhini and Herbert-Voss, Ariel and Krueger, Gretchen and Henighan, Tom ...
[17]

International Conference on Learning Representations , year =

Zhang, Jingzhao and He, Tianxing and Sra, Suvrit and Jadbabaie, Ali , title =. International Conference on Learning Representations , year =
[18]

Advances in Neural Information Processing Systems , year =

Zhang, Bohang and Jin, Jikai and Fang, Cong and Wang, Liwei , title =. Advances in Neural Information Processing Systems , year =
[19]

Advances in Neural Information Processing Systems , year =

Crawshaw, Michael and Liu, Mingrui and Orabona, Francesco and Zhang, Wei and Zhuang, Zhenxun , title =. Advances in Neural Information Processing Systems , year =
[20]

International Conference on Machine Learning , year =

Chen, Ziyi and Zhou, Yi and Liang, Yingbin and Lu, Zhaosong , title =. International Conference on Machine Learning , year =
[21]

Conference on Learning Theory , year =

Wang, Bohan and Zhang, Huishuai and Ma, Zhiming and Chen, Wei , title =. Conference on Learning Theory , year =
[22]

, title =

Koloskova, Anastasia and Hendrikx, Hadrien and Stich, Sebastian U. , title =. International Conference on Machine Learning , year =
[23]

Advances in Neural Information Processing Systems , year =

Li, Haochuan and Rakhlin, Alexander and Jadbabaie, Ali , title =. Advances in Neural Information Processing Systems , year =
[24]

Parameter-Agnostic Optimization under Relaxed Smoothness , booktitle =

H. Parameter-Agnostic Optimization under Relaxed Smoothness , booktitle =
[25]

Advances in Neural Information Processing Systems , year =

Takezawa, Yuki and Bao, Han and Sato, Ryoma and Niwa, Kento and Yamada, Makoto , title =. Advances in Neural Information Processing Systems , year =
[26]

International Conference on Learning Representations , volume=

Methods for convex (l\_0, l\_1) -smooth optimization: Clipping, acceleration, and adaptivity , author=. International Conference on Learning Representations , volume=
[27]

Advances in Neural Information Processing Systems , volume=

Convex and non-convex optimization under generalized smoothness , author=. Advances in Neural Information Processing Systems , volume=
[28]

, title =

Vankov, Daniil and Rodomanov, Anton and Nedic, Angelia and Sankar, Lalitha and Stich, Sebastian U. , title =. International Conference on Learning Representations , year =
[29]

Optimization Methods and Software , volume =

Nesterov, Yurii and Gasnikov, Alexander and Guminov, Sergey and Dvurechensky, Pavel , title =. Optimization Methods and Software , volume =
[30]

arXiv preprint arXiv:2412.11773 , year=

Toward a unified theory of gradient descent under generalized smoothness , author=. arXiv preprint arXiv:2412.11773 , year=

arXiv
[31]

Advances in Neural Information Processing Systems , volume=

Convergence of clipped SGD on convex (l\_0, l\_1) -smooth functions , author=. Advances in Neural Information Processing Systems , volume=
[32]

Advances in Neural Information Processing Systems , volume=

Acceleration exists! optimization problems when oracle can only compare objective function values , author=. Advances in Neural Information Processing Systems , volume=
[33]

and Leike, Jan and Brown, Tom and Martic, Miljan and Legg, Shane and Amodei, Dario , title =

Christiano, Paul F. and Leike, Jan and Brown, Tom and Martic, Miljan and Legg, Shane and Amodei, Dario , title =. Advances in Neural Information Processing Systems , year =
[34]

Ouyang, Long and Wu, Jeff and Jiang, Xu and Almeida, Diogo and Wainwright, Carroll L. and Mishkin, Pamela and Zhang, Chong and Agarwal, Sandhini and Slama, Katarina and Ray, Alex and Schulman, John and Hilton, Jacob and Kelton, Fraser and Miller, Luke and Simens, Maddie and As...
[35]

arXiv preprint arXiv:2509.07972 , year=

Theoretical analysis on how learning rate warmup accelerates convergence , author=. arXiv preprint arXiv:2509.07972 , year=

arXiv
[36]

arXiv preprint arXiv:2503.00229 , year=

Armijo line-search can make (stochastic) gradient descent provably faster , author=. arXiv preprint arXiv:2503.00229 , year=
[37]

arXiv preprint arXiv:2510.03164 , year=

Why do we need warm-up? a theoretical perspective , author=. arXiv preprint arXiv:2510.03164 , year=

arXiv
[38]

arXiv preprint arXiv:2605.30648 , year=

Convergence of Steepest Descent and Adam under Non-Uniform Smoothness , author=. arXiv preprint arXiv:2605.30648 , year=

arXiv
[39]

arXiv preprint arXiv:2605.14800 , year=

Avoiding Bias in Clipped SGD for Overparameterized Models under Generalized Smoothness , author=. arXiv preprint arXiv:2605.14800 , year=

arXiv
[40]

SIAM Journal on Optimization , volume=

Efficiency of the accelerated coordinate descent method on structured optimization problems , author=. SIAM Journal on Optimization , volume=. 2017 , publisher=

2017
[41]

Computational Optimization and Applications , volume=

A flexible coordinate descent method , author=. Computational Optimization and Applications , volume=. 2018 , publisher=

2018
[42]

arXiv preprint arXiv:2412.17050 , year=

Linear Convergence Rate in Convex Setup is Possible! Gradient Descent Method Variants under (L\_0, L\_1) -Smoothness , author=. arXiv preprint arXiv:2412.17050 , year=

arXiv
[43]

ACM Transactions on Intelligent Systems and Technology , volume =

Chang, Chih-Chung and Lin, Chih-Jen , title =. ACM Transactions on Intelligent Systems and Technology , volume =
[44]

and Nocedal, Jorge , title =

Liu, Dong C. and Nocedal, Jorge , title =. Mathematical Programming , volume =
[45]

and Sekhari, Ayush and Shamir, Ohad and Srebro, Nathan and Sridharan, Karthik and Woodworth, Blake , title =

Foster, Dylan J. and Sekhari, Ayush and Shamir, Ohad and Srebro, Nathan and Sridharan, Karthik and Woodworth, Blake , title =. Proceedings of the Thirty-Second Conference on Learning Theory , series =
[46]

arXiv preprint arXiv:2501.18198 , year=

Power of generalized smoothness in stochastic convex optimization: First-and zero-order algorithms , author=. arXiv preprint arXiv:2501.18198 , year=

arXiv
[47]

International Conference on Learning Representations , volume=

Nesterov finds GRAAL: Optimal and adaptive gradient method for convex optimization , author=. International Conference on Learning Representations , volume=
[48]

arXiv preprint arXiv:2508.06884 , year=

Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and (L\_0, L\_1) -Smoothness , author=. arXiv preprint arXiv:2508.06884 , year=

arXiv

Pith tools

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

[1] [1]

, title =

Nesterov, Yurii E. , title =. Doklady Akademii Nauk SSSR , volume =

work page

[2] [2]

Nesterov, Yurii , title =

[3] [3]

2006 , publisher=

Numerical optimization , author=. 2006 , publisher=

2006

[4] [4]

SIAM Journal on Optimization , volume =

Nesterov, Yurii , title =. SIAM Journal on Optimization , volume =

work page

[5] [5]

Mathematical Programming , volume =

Richtarik, Peter and Takac, Martin , title =. Mathematical Programming , volume =

work page

[6] [6]

SIAM Journal on Optimization , volume =

Fercoq, Olivier and Richtarik, Peter , title =. SIAM Journal on Optimization , volume =

work page

[7] [7]

Proceedings of the 33rd International Conference on Machine Learning , year =

Allen-Zhu, Zeyuan and Qu, Zheng and Richtarik, Peter and Yuan, Yang , title =. Proceedings of the 33rd International Conference on Machine Learning , year =

work page

[8] [8]

Optimization Methods for Large-Scale Machine Learning , journal =

Bottou, L. Optimization Methods for Large-Scale Machine Learning , journal =