Pith. sign in

REVIEW 3 major objections 5 minor 69 references

Power of Generalized Smoothness in Stochastic Convex Optimization: First- and Zero-Order Algorithms

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

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

Pith's one-line read Under generalized smoothness, clipping or normalizing the stochastic gradient puts a linearly decaying term into convex convergence bounds; when $L_0=0$, normalized SGD attains a full linear rate.

desk verdict The finite-minimizer results and zero-order analyses are real, but the advertised L0=0 linear rate for NSGD does not follow from the proofs as written. read the letter →

arxiv 2501.18198 v2 pith:YX3XXP7N submitted 2025-01-30 math.OC

Aleksandr Lobanov , Alexander Gasnikov This is my paper · ORCID
classification math.OC MSC 90C2590C1590C56
keywords generalizedsmoothness(L0L1)-smoothnessstochasticconvexoptimizationnormalizedSGDclippedlinearconvergenceratezero-orderbiasedgradientoracle
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

The paper asks whether stochastic gradient methods can converge at a linear — exponentially fast — rate on convex problems, a regime long believed to require strong convexity. Under the generalized $(L_0,L_1)$-smoothness assumption, in which the gradient's Lipschitz constant may grow in proportion to the gradient norm itself, the authors show that both clipping and normalization inject a linearly decaying summand $\bigl(1-\eta/R\bigr)^N (f(x_0)-f^*)$ into the convergence bound. Normalization removes the usual sublinear deterministic term outright: when $L_0=0$ — the case of logistic-type losses that approach their infimum without ever reaching it — normalized SGD needs only $N = O\bigl(L_1R\log(1/\varepsilon)\bigr)$ iterations at batch size $B = O\bigl(\sigma^2 M R^3/\varepsilon^3\bigr)$ to reach accuracy $\varepsilon$. The same mechanism carries over to derivative-free algorithms built on two-point randomized gradient estimates, and a logistic-regression experiment shows linear decay in practice. These rates, the authors argue, break the prevailing sublinear lower bounds for first-order stochastic convex optimization in the $L_0=0$ case.

What carries the argument

The load-bearing ingredient is the $(L_0,L_1)$-smoothness inequality in descent form, $f(y)-f(x) \le \langle \nabla f(x), y-x\rangle + \tfrac{L_0+L_1\|\nabla f(x)\|}{2}\|y-x\|^2$, combined with the convexity relation $f(x_k)-f^* \le \|\nabla f(x_k)\|\,R$, where $R = \|x_0-x^*\|$. From these two ingredients the proofs derive $\|\nabla f(x_k)\|^2 \le 2\bigl(L_0+L_1\|\nabla f(x_k)\|\bigr)\bigl(f(x_k)-f^*\bigr)$ and convert a per-step gradient reduction into a multiplicative contraction of the error. The mechanism that makes the contraction factor constant rather than vanishing near the solution is that the clipped or normalized update has norm at most $c$, or exactly $\eta$, independent of $\|\nabla f(x_k)\|$. For the zero-order results the same first-order proofs run on the two-point randomized gradient estimator, whose bias is bounded by $\bigl(L_0+L_1M\bigr)\gamma + d\Delta/\gamma$ via the distributional Stokes formula and whose variance is bounded via the Wirtinger–Poincaré inequality.

What would settle it

Take a convex $(0,L_1)$-smooth function that provably never attains its infimum, such as the logistic loss of the paper's Section 7 experiment, and compute $R_s = \|x_0-s\|$ minimized over points $s$ with $f(s)-f^* \le \varepsilon$ as $\varepsilon$ shrinks; then run NSGD with the paper's step size and batch size and record whether the log-error decays at the slope predicted from the constant-radius bound. If $R_s$ grows without bound while the claimed iteration count assumes a fixed $R$, the linear-rate guarantee cannot persist to small $\varepsilon$ and the error tail must turn sublinear.

Watch

Extended reading notes

Core claim

The central claim is that under $(L_0,L_1)$-smoothness, a constant per-step decrease in the gradient norm translates into a constant multiplicative contraction of the function-value error, provided the step size does not depend on the gradient norm. Clipping yields this only while the gradient norm exceeds the clip radius — the factor $\bigl(1-\eta c/R\bigr)^K$ in Theorem 3.1 — whereas normalization yields it on every iteration. The main result, Theorem 4.1, states that normalized SGD with step size $\eta \le \lambda/[2(L_0+L_1\lambda)]$ and batch size $B$ obeys $\mathbb{E}[f(x_N)]-f^* \lesssim \bigl(1-\eta/R\bigr)^N (f(x_0)-f^*) + \sigma^2 M R/(B\lambda^2) + \lambda R$; in the $L_0=0$ regime the authors read off iteration complexity $N = O\bigl(L_1R\log(1/\varepsilon)\bigr)$ — a linear rate in a convex setting — at batch size $O\bigl(\sigma^2 M R^3/\varepsilon^3\bigr)$. For general $L_0>0$ they report $N = O\bigl((L_1R + L_0R^2/\varepsilon)\log(1/\varepsilon)\bigr)$, with linear behavior in the $L_1$ part and sublinear behavior in the $L_0$ part. The zero-order analogues (Theorems 5.2 and 5.4) reproduce the linear-rate summand: ZO-NSGD needs $N = \tilde{O}(R/\eta)$ iterations, $T = O\bigl(d\tilde\sigma^2 M R^4/(\varepsilon^3\eta)\bigr)$ function evaluations, and tolerates adversarial noise up to $\Delta \lesssim \varepsilon^{3/2}/\bigl(\sqrt{d}\,R^{3/2}(L_0+L_1M)\bigr)$. The $L_0=0$ regime is exactly the case where the infimum may not be attained, which the paper addresses in Remark 1.3 and Appendix F.

Load-bearing premise

The linear-rate theorems assume a minimizer $x^*$ exists at finite distance $R = \|x_0-x^*\|$ from the starting point, and for the $L_0=0$ case, where no such minimizer may exist, the paper's substitute-point argument never shows that the distance to the substitute stays bounded as the target accuracy shrinks.

Editorial extensions

If this is right

  • In the $L_0=0$ case, normalized SGD reaches $\varepsilon$-accuracy in $N = O\bigl(L_1R\log(1/\varepsilon)\bigr)$ iterations — a linear rate in a convex setting — at the price of a large batch size $B = O\bigl(\sigma^2 M R^3/\varepsilon^3\bigr)$.
  • For $L_0>0$ the methods interpolate between regimes: $N = O\bigl((L_1R + L_0R^2/\varepsilon)\log(1/\varepsilon)\bigr)$, and the $L_0$ component is where classical sublinear behavior survives.
  • Clipped SGD shows two phases — a linear one while the gradient norm stays above the clip radius $c$, then a sublinear one — and the sublinear leftover term shrinks as $c$ is reduced, which is what motivates switching to normalization.
  • The zero-order variants inherit the linear-rate summand: ZO-NSGD needs $N = \tilde{O}(R/\eta)$ iterations and $T = O\bigl(d\tilde\sigma^2 M R^4/(\varepsilon^3\eta)\bigr)$ oracle calls, paying the usual factor $d$ for gradient-free access and tolerating noise only up to $\Delta = O\bigl(\varepsilon^{3/2}/(\sqrt{d}\,R^{3/2}(L_0+L_1M))\bigr)$.
  • The biased-oracle analysis behind the zero-order results (Lemmas 5.1 and 5.3) shows how any bounded bias $\zeta$ accumulates into an error floor $\zeta^2 M R/\lambda^2$ plus a linear term $\lambda R$, a fact of independent interest for sparsified or delayed SGD.

Reading between the lines

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

  • Read strictly, the $L_0=0$ linear rate is proven only for functions whose infimum is attained; for asymptote-type losses the appendix's auxiliary point $s$ introduces an error $f(s)-f^*$ and a radius $R_s = \|x_0-s\|$ whose boundedness as $f(s)-f^* \to \varepsilon$ is not established, so the linear-rate guarantee for such losses is conditional until that gap is closed.
  • If the $L_0=0$ phenomenon survives that check, it would give a convex-theoretic justification for a common deep-learning heuristic: normalizing the update makes the effective step length independent of gradient size, so over logistic-type tails the trajectory behaves as if the objective were strongly convex along the descent path.
  • Zero-order noise tolerance trades against iteration speed: ZO-NSGD's $\Delta = O\bigl(\varepsilon^{3/2}/(\sqrt{d}\,R^{3/2}(L_0+L_1M))\bigr)$ is smaller than ZO-ClipSGD's $\Delta = O\bigl(\varepsilon/(\sqrt{d}\,R(L_0+L_1M))\bigr)$, so an adversary injecting noise between these scales would break the fast method while leaving the slower one intact.
  • A natural next experiment would be to measure the slope of $\log(f(x_N)-f^*)$ against $N$ on the paper's logistic-regression instance and compare it with the predicted $1/(2L_1R_s)$; a slope that flattens at small $\varepsilon$ would indicate the effective radius grows with the required accuracy.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper studies stochastic convex minimization under (L0,L1)-smoothness. For unbiased stochastic gradients it analyzes ClipSGD and NSGD, claiming that clipping or normalization produces a summand with a linear contraction rate in the convex setting; for L0=0 it claims NSGD needs N=O(L1R log(1/eps)) iterations with batch size B=O(sigma^2 M R^3/eps^3). For biased oracles, including the two-point zero-order estimator, it proves analogous bounds for ZO-ClipSGD and ZO-NSGD (Theorems 5.2 and 5.4) and gives numerical evidence on logistic regression. The main supporting proofs are in Appendices B-E, with an additional clarification for the L0=0 case in Appendix F.

Significance. If the L0=0 linear-rate claim held, this would be a striking result: it would break the usual stochastic convex lower-bound picture and would be the first such guarantee for zero-order methods under generalized smoothness. The finite-minimizer derivations in Sections 3-5 are detailed and appear internally coherent, and the biased-oracle lemmas may be independently useful. However, the headline claim for L0=0 is not established by the supplied proofs because the analysis requires a finite minimizer x* while the L0=0 examples highlighted in Remark 1.3 do not attain their infimum. The paper's significance is therefore conditional on repairing this gap or explicitly restricting the claims to functions with attained minimizers.

major comments (3)
  1. [Theorem 4.1, Appendix C, Appendix F, Remark 1.3] The L0=0 linear-convergence claim is not established for functions without a minimizer. The proof of Theorem 4.1 repeatedly uses f(x_k)-f* <= ||grad f(x_k)|| R with R=||x0-x*||, e.g., in Appendix C equations (27), (29), (32), (34), and (36), so it requires a finite minimizer x*. Remark 1.3 states that the L0=0 class includes functions that converge to an asymptote and do not reach their infimum, for which R is infinite. Appendix F replaces x* by an auxiliary point s and proves f(x_N)-f* <= (1-eta/(4R_s))^N (f(x0)-f*) + f(s)-f*, with R_s=||x0-s||. To make f(s)-f* <= eps/2, s must approach the infimum; for the canonical example f(x)=e^{-x} with L1=1 and x0=0, R_s is of order log(1/eps), so the bound gives N=O(L1 log^2(1/eps)), not the claimed fixed-R rate N=O(L1R log(1/eps)). No argument shows that the rate is uniform as f(s)-f* tends to zero. Since the same reasoning underlies Theorem 5.4 and the abstract's headline complexity, this is a load-bearing gap for the central claim.
  2. [Theorem 4.1, Assumption 1.5, Section 6] The advertised batch size B=O(sigma^2 M R^3/eps^3) depends on M, a uniform bound on gradient norms, but no standing assumption guarantees such an M. Assumption 1.5 bounds only the variance of the stochastic gradient; Section 6 explicitly defers proving that M is bounded to future work. Appendix C uses M in the variance term, e.g., equation (28), replacing ||grad f(x_k)|| by M. Without an explicit assumption on M, the iteration-vs-batch-size trade-off in Theorem 4.1 is conditional on an unquantified quantity. Please state M as an explicit assumption or derive a bound on it from (L0,L1)-smoothness and the noise assumptions.
  3. [Theorem 3.1, Appendix B] The definition of K in Theorem 3.1 is inconsistent with the proof. The theorem says K is the number of iterations for which ||grad f(x_k)|| <= c/2, whereas Appendix B defines T1 as the set with ||grad f(x_k, xi_k)|| >= c/2 and T2 as the set with ||grad f(x_k)|| < c/2. The proof's case analysis yields contraction factors such as 1-eta c/(4R) and 1-eta c/(2R) before combining, not the stated (1-eta c/R)^K. This mismatch should be corrected because K is the quantity that separates the linear and sublinear regimes in the final bound.
minor comments (5)
  1. [Notation, Remark 1.3] The notation f* is introduced as f(x*) with x* a minimizer, but Remark 1.3 uses f* as an infimum that may not be attained; please use f^*=inf f and state explicitly wherever a finite minimizer x* is assumed.
  2. [Section 7] The numerical experiments do not connect the logistic-regression setup to the theoretical conditions: please state whether the w1a dataset is separable (so the empirical loss is an L0=0 function without attained infimum) and explain how the step size eta=1/||A||_1 relates to the theoretical step-size condition eta <= lambda/[2(L0+L1 lambda)].
  3. [Throughout] There are repeated typos, including 'Batch parallization' in Sections 6 and 8 and 'Lipshitz' in the appendix; these should be corrected in a revision.
  4. [References] Reference [5] is listed as 'Authors Anonymous'; if this is a self-citation of a paper under review, it should be clearly marked as such.
  5. [Table 1] Table 1 uses the symbol R both for the radius ||x0-x*|| and for the shorthand (eta + MR/c^2 + R/c), which risks confusing the reader; please use distinct symbols for these two quantities.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence proofs are self-contained algebraic derivations from stated assumptions, and the L0=0 issue is a correctness gap, not circular reasoning.

full rationale

The paper's convergence bounds are derived directly from Assumptions 1.2, 1.4, and 1.5 via explicit one-step smoothness inequalities and convexity, without assuming the final rate. The linear-rate summands in Theorems 3.1, 4.1, 5.2, and 5.4 emerge from the inequality f(xk)-f* <= ||grad f(xk)|| R using the finite radius R = ||x0-x*||, and the constants in the bounds are problem parameters or algorithm hyperparameters, not fitted quantities. The L0=0 case is genuinely problematic: functions in that class need not attain their infimum, so R may be infinite, and Appendix F replaces x* with an auxiliary point s, yielding an additive f(s)-f* term and a radius R_s that is not shown to remain bounded as f(s)-f* goes to epsilon. This is a missing derivation or correctness gap, not circular reasoning, because the paper does not define the claimed rate in terms of a fitted parameter or rename its input as its output. Self-citations, e.g., to [44] for the possibility of linear convergence in the deterministic convex setting, are contextual motivation and are not load-bearing: the theorems proved here are self-contained and do not invoke [44] as a proof ingredient. No uniqueness theorem, ansatz, or fitted prediction is smuggled in through self-citation. Overall, the central derivation is independent and self-contained, with no step reducing by construction to its own inputs.

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

The central claims rest on standard smoothness, variance, bias, and convexity assumptions, plus a bounded-gradient constant M that is not proven. The L0=0 linear-rate claim additionally assumes a finite minimizer; the appendix's attempt to relax this introduces an auxiliary point s without a quantitative bound on R_s, which is the most fragile part of the paper.

free parameters (4)
  • clipping radius c = user-specified; c = 10^-1 in experiments
    Algorithm hyperparameter. The convergence bound and the split between K and N-K depend on c; the L0=0 ClipSGD complexity is improved by small c, but then the linear-rate phase shrinks.
  • normalization threshold lambda = lambda = eps/R in complexity statements
    Algorithm hyperparameter. The NSGD bound has a lambda R error term and a batch-size term sigma^2 M R/(B lambda^2), so lambda is set to eps/R to achieve eps accuracy.
  • smoothing parameter gamma (zero-order) = gamma = eps/(R(L0+L1 M)) for ZO-ClipSGD; gamma = eps^{3/2}/((L0+L1 M) sqrt(M) R^{3/2}) for ZO-NSGD
    Chosen to balance bias and variance of the two-point gradient estimator; the maximum allowed noise level Delta depends on this choice.
  • auxiliary point distance R_s = not specified; user-chosen hyperparameter
    Introduced in Appendix F to handle the L0=0 no-minimizer case. The convergence bound contains f(s)-f* and the contraction rate depends on R_s; the paper does not quantify the tradeoff between R_s and the desired accuracy.
assumptions (6)
  • domain assumption Assumption 1.2: (L0,L1)-smoothness holds
    Central model used in every descent lemma and in the zero-order bias estimate.
  • domain assumption Assumption 1.5: bounded variance of stochastic gradients
    Standard heavy-tailed noise assumption; controls noise terms in all theorems.
  • domain assumption Assumption 1.4: bounded bias (zeta) in the biased-oracle lemmas
    Controls bias accumulation in Lemmas 5.1 and 5.3; for the two-point estimator zeta is derived from (L0,L1,M,gamma,Delta).
  • domain assumption f is convex
    Used to relate function suboptimality to gradient norm times distance R, e.g., f(xk)-f* <= ||grad f(xk)|| R, in every proof.
  • domain assumption M: uniform upper bound on gradient norm
    Required in zero-order bias and variance estimates and in final noise-level bounds. The paper states in Section 6 that proving M bounded remains future work, so this is a load-bearing assumption without independent support.
  • domain assumption Finite minimizer x* at distance R from x0 in Theorems 3.1 and 4.1
    The convexity-gradient inequality uses x* and R=||x0-x*||. Appendix F shows that when L0=0 the infimum may not be attained, so the main theorems do not directly cover that regime.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Power of Generalized Smoothness in Stochastic Convex Optimization: First- and Zero-Order Algorithms." pith.science (2026). https://pith.science/paper/YX3XXP7N

@misc{pith2026250118198,
  author       = {Pith},
  title        = {Pith review of: Power of Generalized Smoothness in Stochastic Convex Optimization: First- and Zero-Order Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YX3XXP7N}},
  note         = {Machine review of arXiv:2501.18198}
}
abstract

This paper is devoted to the study of stochastic optimization problems under the generalized smoothness assumption. By considering the unbiased gradient oracle in Stochastic Gradient Descent, we provide strategies to achieve in bounds the summands describing linear rate. In particular, in the case $L_0 = 0$, we obtain in the convex setup the iteration complexity: $N = \mathcal{O}\left(L_1R \log\frac{1}{\varepsilon} + \frac{L_1 c R^2}{\varepsilon}\right)$ for Clipped Stochastic Gradient Descent and $N = \mathcal{O}\left(L_1R \log\frac{1}{\varepsilon}\right)$ for Normalized Stochastic Gradient Descent. Furthermore, we generalize the convergence results to the case with a biased gradient oracle, and show that the power of $(L_0,L_1)$-smoothness extends to zero-order algorithms. Finally, we demonstrate the possibility of linear convergence in the convex setup through numerical experimentation, which has aroused some interest in the machine learning community.

Figures

Figures reproduced from arXiv: 2501.18198 by the authors.

Figure 1
Figure 1. Changing regimes demonstration Linear convergence. Historically [45], stochastic optimization first- and zero-order algorithms have achieved the desired accuracy with a linear rate of convergence only in strongly convex case and under assumption of standard smoothness. However, the work of [44] showed that if the generalized smooth￾ness assumption is satisfied in a deterministic convex optimization problem, then gra… view at source ↗
Figure 2
Figure 2. Linear convergence demonstration [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

69 extracted references · 44 canonical work pages

  1. [1]

    Optimal algorithms for online convex optimization with multi-point bandit feedback

    Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Colt, pages 28–40. Citeseer, 2010

    2010

  2. [2]

    Distributed zero-order optimization under adversarial noise

    Arya Akhavan, Massimiliano Pontil, and Alexandre Tsybakov. Distributed zero-order optimization under adversarial noise. Advances in Neural Information Processing Systems, 34:10209–10220, 2021

    work page 2021

  3. [3]

    A gradient estimator via l1-randomization for online zero-order optimization with two point feedback

    Arya Akhavan, Evgenii Chzhen, Massimiliano Pontil, and Alexandre Tsybakov. A gradient estimator via l1-randomization for online zero-order optimization with two point feedback. Advances in Neural Information Processing Systems, 35:7685–7696, 2022

    work page 2022

  4. [4]

    The convergence of sparsified gradient methods

    Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. Advances in Neural Information Processing Systems, 31, 2018

    2018

  5. [5]

    Maximum noise level as third optimality criterion in black-box optimization problem, 2025

    Authors Anonymous. Maximum noise level as third optimality criterion in black-box optimization problem, 2025

    work page 2025

  6. [6]

    Highly-smooth zero-th order online optimization

    Francis Bach and Vianney Perchet. Highly-smooth zero-th order online optimization. In Conference on Learning Theory, pages 257–283. PMLR, 2016

    2016

  7. [7]

    Neural optimizer search with reinforcement learning

    Irwan Bello, Barret Zoph, Vijay Vasudevan, and Quoc V Le. Neural optimizer search with reinforcement learning. In International Conference on Machine Learning, pages 459–468. PMLR, 2017

    work page 2017

  8. [8]

    Learning long-term dependencies with gradient descent is difficult

    Yoshua Bengio, Patrice Simard, and Paolo Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE transactions on neural networks, 5(2):157–166, 1994

    work page 1994

Show all 69 references
  1. [9]

    Learning supervised pagerank with gradient- based and gradient-free optimization methods

    Lev Bogolubsky, Pavel Dvurechenskii, Alexander Gasnikov, Gleb Gusev, Yurii Nesterov, Andrei M Raigorodskii, Aleksey Tikhonov, and Maksim Zhukovskii. Learning supervised pagerank with gradient- based and gradient-free optimization methods. Advances in neural information process...

    2016

  2. [10]

    Online algorithms and stochastic approximations

    Léon Bottou. Online algorithms and stochastic approximations. Online learning in neural networks, 1998

    1998

  3. [11]

    Optimization methods for large-scale machine learning

    Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223–311, 2018

    2018

  4. [13]

    Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization

    Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization. In International Conference on Machine Learning, pages 5396–5427. PMLR, 2023

    2023

  5. [14]

    Momentum improves normalized sgd

    Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. In International conference on machine learning, pages 2260–2268. PMLR, 2020

    2020

  6. [15]

    Large scale distributed deep networks.Advances in neural information processing systems, 25, 2012

    Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc’aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks.Advances in neural information processing systems, 25, 2012

    2012

  7. [16]

    A guide through the zoo of biased sgd

    Yury Demidovich, Grigory Malinovsky, Igor Sokolov, and Peter Richtárik. A guide through the zoo of biased sgd. Advances in Neural Information Processing Systems, 36:23158–23171, 2023

    2023

  8. [17]

    Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization

    Olivier Devolder. Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization. Candidate’s Dissertation (CORE UCLouvain Louvain-la-Neuve, Belgium), 2013

    2013

  9. [18]

    Grawa: Gradient-based weighted averaging for distributed training of deep learning models

    Tolga Dimlioglu and Anna Choromanska. Grawa: Gradient-based weighted averaging for distributed training of deep learning models. In International Conference on Artificial Intelligence and Statistics , pages 2251–2259. PMLR, 2024

    2024

  10. [19]

    Beyond uniform smoothness: A stopped analysis of adaptive sgd

    Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smoothness: A stopped analysis of adaptive sgd. In The Thirty Sixth Annual Conference on Learning Theory, pages 89–160. PMLR, 2023

    2023

  11. [20]

    Convergence of clipped sgd on convex(l_0, l_1)-smooth functions

    Ofir Gaash, Kfir Yehuda Levy, and Yair Carmon. Convergence of clipped sgd on convex(l_0, l_1)-smooth functions. arXiv preprint arXiv:2502.16492, 2025. 10

    2025 arXiv

  12. [21]

    The power of first-order smooth optimization for black-box non-smooth problems

    Alexander Gasnikov, Anton Novitskii, Vasilii Novitskii, Farshed Abdukhakimov, Dmitry Kamzolov, Aleksandr Beznosikov, Martin Takac, Pavel Dvurechensky, and Bin Gu. The power of first-order smooth optimization for black-box non-smooth problems. In International Conference on Mac...

    2022

  13. [22]

    Randomized gradient-free methods in convex optimization

    Alexander Gasnikov, Darina Dvinskikh, Pavel Dvurechensky, Eduard Gorbunov, Aleksandr Beznosikov, and Alexander Lobanov. Randomized gradient-free methods in convex optimization. In Encyclopedia of Optimization, pages 1–15. Springer, 2023

    2023

  14. [23]

    Highly smooth zeroth-order methods for solving opti- mization problems under the pl condition

    A V Gasnikov, A V Lobanov, and FS Stonyakin. Highly smooth zeroth-order methods for solving opti- mization problems under the pl condition. Computational Mathematics and Mathematical Physics, 64(4): 739–770, 2024

    2024

  15. [24]

    Deep learning, 2016

    Ian Goodfellow. Deep learning, 2016

    2016

  16. [25]

    Stochastic optimization with heavy-tailed noise via accelerated gradient clipping

    Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. Advances in Neural Information Processing Systems, 33:15042– 15053, 2020

    2020

  17. [26]

    Methods for convex (l_0, l_1)-smooth optimization: Clipping, acceleration, and adaptivity

    Eduard Gorbunov, Nazarii Tupitsa, Sayantan Choudhury, Alen Aliev, Peter Richtárik, Samuel Horváth, and Martin Takáˇc. Methods for convex (l_0, l_1)-smooth optimization: Clipping, acceleration, and adaptivity. arXiv preprint arXiv:2409.14989, 2024

    2024 arXiv

  18. [27]

    Beyond convexity: Stochastic quasi-convex optimization

    Elad Hazan, Kfir Levy, and Shai Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex optimization. Advances in neural information processing systems, 28, 2015

    2015

  19. [28]

    Predictive entropy search for efficient global optimization of black-box functions.Advances in neural information processing systems, 27, 2014

    José Miguel Hernández-Lobato, Matthew W Hoffman, and Zoubin Ghahramani. Predictive entropy search for efficient global optimization of black-box functions.Advances in neural information processing systems, 27, 2014

    2014

  20. [29]

    On convergence of adam for stochastic optimization under relaxed assump- tions

    Yusu Hong and Junhong Lin. On convergence of adam for stochastic optimization under relaxed assump- tions. arXiv preprint arXiv:2402.03982, 2024

    2024 arXiv

  21. [30]

    From gradient clipping to normalization for heavy tailed sgd

    Florian Hübler, Ilyas Fatkhullin, and Niao He. From gradient clipping to normalization for heavy tailed sgd. arXiv preprint arXiv:2410.13849, 2024

    2024 arXiv

  22. [31]

    Parameter-agnostic optimization under relaxed smoothness

    Florian Hübler, Junchi Yang, Xiang Li, and Niao He. Parameter-agnostic optimization under relaxed smoothness. In International Conference on Artificial Intelligence and Statistics, pages 4861–4869. PMLR, 2024

    2024

  23. [32]

    First order methods for nonsmooth convex large-scale optimization, i: General purpose methods

    Anatoli B Juditsky and Arkadii S Nemirovski. First order methods for nonsmooth convex large-scale optimization, i: General purpose methods. Optimization for Machine Learning, pages 1–28, 2010

    2010

  24. [33]

    Advances and open problems in federated learning

    Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and trends® in machine learning, 14(1–...

    2021

  25. [34]

    Revisiting gradient clipping: Stochastic bias and tight convergence guarantees

    Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference on Machine Learning, pages 17343– 17363. PMLR, 2023

    2023

  26. [35]

    Accelerated zeroth-order method for non-smooth stochastic convex optimization problem with infinite variance

    Nikita Kornilov, Ohad Shamir, Aleksandr Lobanov, Darina Dvinskikh, Alexander Gasnikov, Innokentiy Shibaev, Eduard Gorbunov, and Samuel Horváth. Accelerated zeroth-order method for non-smooth stochastic convex optimization problem with infinite variance. Advances in Neural Info...

    2023

  27. [36]

    A simpler approach to obtaining an o (1/t) convergence rate for the projected stochastic subgradient method

    Simon Lacoste-Julien, Mark Schmidt, and Francis Bach. A simpler approach to obtaining an o (1/t) convergence rate for the projected stochastic subgradient method. arXiv preprint arXiv:1212.2002, 2012

    2002 arXiv

  28. [37]

    An optimal method for stochastic composite optimization

    Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133(1):365–397, 2012

    2012

  29. [38]

    Improved regret for zeroth-order stochastic convex bandits

    Tor Lattimore and Andras Gyorgy. Improved regret for zeroth-order stochastic convex bandits. In Conference on Learning Theory, pages 2938–2964. PMLR, 2021

    2021

  30. [39]

    Plastic: Improving input and label plasticity for sample efficient reinforcement learning

    Hojoon Lee, Hanseul Cho, Hyunseung Kim, Daehoon Gwak, Joonkee Kim, Jaegul Choo, Se-Young Yun, and Chulhee Yun. Plastic: Improving input and label plasticity for sample efficient reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024. 11

    2024

  31. [40]

    Convex and non-convex optimization under generalized smoothness

    Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non-convex optimization under generalized smoothness. Advances in Neural Information Processing Systems , 36: 40238–40271, 2023

    2023

  32. [41]

    Convergence of adam under relaxed assumptions

    Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie. Convergence of adam under relaxed assumptions. Advances in Neural Information Processing Systems, 36:52166–52196, 2023

    2023

  33. [42]

    overparametrization

    Aleksandr Lobanov and Alexander Gasnikov. Accelerated zero-order sgd method for solving the black box optimization problem under “overparametrization” condition. In International Conference on Optimization and Applications, pages 72–83. Springer, 2023

    2023

  34. [43]

    black-box

    Aleksandr Lobanov, Nail Bashirov, and Alexander Gasnikov. The “black-box” optimization problem: Zero-order accelerated stochastic method via kernel approximation. Journal of Optimization Theory and Applications, pages 1–36, 2024

    2024

  35. [44]

    Linear convergence rate in convex setup is possible! gradient descent method variants under (l_0, l_1)-smoothness

    Aleksandr Lobanov, Alexander Gasnikov, Eduard Gorbunov, and Martin Takác. Linear convergence rate in convex setup is possible! gradient descent method variants under (l_0, l_1)-smoothness. arXiv preprint arXiv:2412.17050, 2024

    2024 arXiv

  36. [45]

    Lectures on convex optimization, volume 137

    Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018

    2018

  37. [46]

    Random gradient-free minimization of convex functions

    Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Founda- tions of Computational Mathematics, 17(2):527–566, 2017

    2017

  38. [47]

    Stochastic zeroth-order functional constrained optimization: Oracle complexity and applications

    Anthony Nguyen and Krishnakumar Balasubramanian. Stochastic zeroth-order functional constrained optimization: Oracle complexity and applications. INFORMS Journal on Optimization, 2022

    2022

  39. [48]

    On the difficulty of training recurrent neural networks

    Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning , volume 28 of Proceedings of Machine Learning Rese...

    2013

  40. [49]

    Distributed online and bandit convex optimization

    Kumar Kshitij Patel, Aadirupa Saha, Lingxiao Wang, and Nathan Srebro. Distributed online and bandit convex optimization. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022

    2022

  41. [50]

    Fast training of support vector machines using sequential minimal optimization

    John C Platt. Fast training of support vector machines using sequential minimal optimization. Advances in Kernel Methods - Support Vector Learning, MIT Press, 1998

    1998

  42. [51]

    Introduction to optimization

    Boris T Polyak. Introduction to optimization. Optimization Software, Inc. Publications Division, New York, 1987

    1987

  43. [52]

    An optimal algorithm for bandit and zero-order convex optimization with two-point feedback

    Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. The Journal of Machine Learning Research, 18(1):1703–1713, 2017

    2017

  44. [53]

    The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication

    Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication. arXiv preprint arXiv:1909.05350, 2019

    1909 arXiv

  45. [54]

    Parameter-free clipped gradient descent meets polyak

    Yuki Takezawa, Han Bao, Ryoma Sato, Kenta Niwa, and Makoto Yamada. Parameter-free clipped gradient descent meets polyak. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

    2024

  46. [55]

    Optimizing (l_0, l_1)-smooth functions by gradient methods

    Daniil Vankov, Anton Rodomanov, Angelia Nedich, Lalitha Sankar, and Sebastian U Stich. Optimizing (l_0, l_1)-smooth functions by gradient methods. arXiv preprint arXiv:2410.10800, 2024

    2024 arXiv

  47. [56]

    Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions

    Bohan Wang, Huishuai Zhang, Zhiming Ma, and Wei Chen. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions. In The Thirty Sixth Annual Conference on Learning Theory, pages 161–190. PMLR, 2023

    2023

  48. [57]

    On the conver- gence of adam under non-uniform smoothness: Separability from sgdm and beyond

    Bohan Wang, Huishuai Zhang, Qi Meng, Ruoyu Sun, Zhi-Ming Ma, and Wei Chen. On the conver- gence of adam under non-uniform smoothness: Separability from sgdm and beyond. arXiv preprint arXiv:2403.15146, 2024

    2024 arXiv

  49. [58]

    The min-max complexity of distributed stochastic convex optimization with intermittent communication

    Blake E Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. In Conference on Learning Theory, pages 4386–4437. PMLR, 2021

    2021

  50. [59]

    Trust region methods for nonconvex stochastic optimization beyond lipschitz smoothness

    Chenghan Xie, Chenxi Li, Chuwen Zhang, Qi Deng, Dongdong Ge, and Yinyu Ye. Trust region methods for nonconvex stochastic optimization beyond lipschitz smoothness. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 16049–16057, 2024. 12

    2024

  51. [60]

    Federated accelerated stochastic gradient descent

    Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. Advances in Neural Information Processing Systems, 33:5332–5344, 2020

    2020

  52. [61]

    Improved analysis of clipping algorithms for non-convex optimization

    Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 33:15511–15521, 2020

    2020

  53. [62]

    Why gradient clipping accelerates training: A theoretical justification for adaptivity

    Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2019

    2019

  54. [63]

    Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33:15383–15393, 2020

    Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33:15383–15393, 2020

    2020

  55. [64]

    Deep learning with elastic averaging sgd

    Sixin Zhang, Anna E Choromanska, and Yann LeCun. Deep learning with elastic averaging sgd. Advances in neural information processing systems, 28, 2015

    2015

  56. [65]

    On the convergence and improvement of stochastic normalized gradient descent

    Shen-Yi Zhao, Yin-Peng Xie, and Wu-Jun Li. On the convergence and improvement of stochastic normalized gradient descent. Science China Information Sciences, 64:1–13, 2021

    2021

  57. [66]

    Stochastic normalized gradient descent with momentum for large-batch training

    Shen-Yi Zhao, Chang-Wei Shi, Yin-Peng Xie, and Wu-Jun Li. Stochastic normalized gradient descent with momentum for large-batch training. Science China Information Sciences, 67(11):212101, 2024

    2024

  58. [67]

    Mathematical analysis II, volume 220

    Vladimir Antonovich Zorich and Octavio Paniagua. Mathematical analysis II, volume 220. Springer, 2016. 13 APPENDIX Power of Generalized Smoothness in Stochastic Convex Optimization: First- and Zero-Order Algorithms A Auxiliary Results In this section we provide auxiliary mater...

    2016

  59. [68]

    Throughout this paper, we assume that the (L0, L1)- smoothness condition (Assumption 1.2) is satisfied

    (7) Generalized-Lipschitz-smoothness. Throughout this paper, we assume that the (L0, L1)- smoothness condition (Assumption 1.2) is satisfied. This inequality can be represented in the equivalent form for any x, y∈ Rd: f (y) − f (x) ≤ ⟨∇f (x), y− x⟩ + L0 + L1 ∥∇f (x)∥ 2 ∥y − x∥...

  60. [69]

    λ ∥∇f (xk, ξk)∥ − 1 2 ∇f (xk, ξk) 2 # + η2(L0 + L1 ∇f (xk) ) 2 ≤ −η 2λ ∇f (xk) 2 + η 2λ E

    Using this in (25), we have the following with ηk ≤ ∥∇f (xk)∥ 2(L0+L1∥∇f (xk)∥): E f (xk+1) − f (xk) (24) ≤ −η ∇f (xk), E G(xk, ξk) + η2(L0 + L1 ∇f (xk) ) 2 E h G(xk, ξk) 2i (25) ≤ −η 2 ∇f (xk) − η 2α E h G(xk, ξk) 2i + η 2λ2α E h ∇f (xk, ξ) − ∇f (xk) 2i + η2(L0 + L1 ∇f (xk) )...

  61. [70]

    λ ∥g(xk, ξk)∥ − 1 2 g(xk, ξk) 2 # + η λ b(xk) 2 + η2(L0 + L1 ∇f (xk) ) 2 ≤ −η 2λ ∇f (xk) 2 + η 2λ E

    Using this in (58), we have the following with ηk ≤ ∥∇f (xk)∥ 2(L0+L1∥∇f (xk)∥): E f (xk+1) − f (xk) (57) ≤ −η ∇f (xk), E G(xk, ξk) + η2(L0 + L1 ∇f (xk) ) 2 E h G(xk, ξk) 2i (58) ≤ −η 2 ∇f (xk) − η 2α E h G(xk, ξk) 2i + η 2λ2α E h g(xk, ξk) − ∇f (xk) 2i + η2(L0 + L1 ∇f (xk) ) ...

Pith tools

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