Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent

Adam M. Oberman; Maxime Laborde

REVIEW 3 major objections 4 minor 40 references

Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read This paper derives accelerated SGD from a coupled ODE system and proves optimal last-iterate convergence rates in the convex and strongly convex cases.

desk verdict Strongly convex part looks solid; convex part is false as stated but likely repairable. read the letter →

arxiv 1908.07861 v5 pith:ZOY26A6P submitted 2019-08-21 math.OC

Maxime Laborde , Adam M. Oberman This is my paper · ORCID

classification math.OC MSC 90C2590C1565K10

keywords acceleratedstochasticgradientdescentNesterov'sLyapunovfunctionlast-iterateconvergenceconvexoptimizationstronglydecreasinglearningrateapproximation

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 tries to turn the connection between Nesterov's accelerated gradient method and differential equations into new stochastic gradient descent algorithms with proven acceleration. The authors write Nesterov's method as a coupled pair of gradient-descent-like evolutions; with a constant time step the system reproduces Nesterov's method, and with a decreasing learning rate the same system becomes an accelerated SGD algorithm. They prove that the last iterate converges at the optimal rates in both settings, with constants that improve on previously available bounds. If correct, this gives rigorous justification for the common heuristic that momentum helps stochastic gradient descent, and supplies explicit coefficient schedules that realize the improvement.

What carries the argument

The load-bearing object is the coupled first-order system in the variables $(y_k,x_k,v_k)$: $y_k = (1-w_k)x_k + w_k v_k$, $x_{k+1}-x_k = w_k(v_k-x_k) - \frac{h_k}{\sqrt{L}}(\nabla f(y_k)+e_k)$, and $v_{k+1}-v_k = w_k(x_k-v_k) - \frac{\sqrt{C_f}h_k}{\sqrt{L}}(\nabla f(y_k)+e_k)$ in the strongly convex case, with $w_k = \frac{h_k\sqrt{\mu}}{1+h_k\sqrt{\mu}}$. Alongside it sits a rate-generating Lyapunov function $E^{SC}(x,v) = f(x)-f_* + \frac{\mu}{2}\|v-x_*\|^2$, and a time-weighted analogue in the convex case. The Lyapunov function is what carries the argument: its one-step dissipation contains a stochastic error term of order $h_k^2\sigma^2$, and the learning-rate schedule is chosen so that summing these errors produces the target rate.

What would settle it

Run the strongly convex algorithm on a one-dimensional quadratic $f(x)=\mu x^2/2$ with added zero-mean noise of known variance $\sigma^2$, estimating $\mathbb{E}[f(x_k)-f_*]$ over many independent trials. If the empirical average exceeds $\frac{4\sigma^2}{\mu(k+k_0)}$ at any $k$ by more than Monte-Carlo error, the central bound is false. The convex bound can be tested the same way against the $O((1+\log k)/\sqrt{k})$ inequality.

Watch

Extended reading notes

Core claim

The central claim is that a single coupled ODE system supports both regimes. The system couples an ordinary gradient descent variable $x$ with an auxiliary variable $v$ that runs at a faster, unstable rate, joined through a convex combination $y$. Discretized with a constant step $h \leq 1/\sqrt{L}$, it is Nesterov's accelerated gradient method; discretized with the decreasing schedule $h_k = \frac{2}{\sqrt{\mu}(k+k_0)}$ in the strongly convex case, it yields $\mathbb{E}[f(x_k)-f_*] \leq \frac{4\sigma^2}{\mu(k+k_0)}$, and with the novel schedule $h_k = \frac{c}{(k+1)^{3/4}}$ in the convex case, it yields $\mathbb{E}[f(x_k)]-f_* \leq \frac{1}{\sqrt{k}}\left(\frac{E_0^C}{16c^2} + c^2\sigma^2(1+\log k)\right)$. In the two-step form the algorithm is $x_{k+1} = y_k - \alpha_k \nabla f(y_k)/L$, $y_{k+1} = x_{k+1} + \beta_k(x_{k+1}-x_k) + \gamma_k(y_k-x_k)$, where the extra $\gamma_k$ term is not present in standard momentum SGD heuristics. The proof works by showing a Lyapunov function dissipates with an error term proportional to $h_k^2\sigma^2$, then choosing $h_k$ so that the accumulated error matches the optimal last-iterate rate.

Load-bearing premise

The proofs assume every gradient estimate is unbiased with uniformly bounded variance and every learning rate satisfies $h_k \leq 1/\sqrt{L}$; if either fails, the Lyapunov error term is no longer controlled by $h_k^2\sigma^2$ and the stated rates do not follow.

Editorial extensions

If this is right

In the strongly convex case, a stochastic gradient method can reach error $O(\sigma^2/(\mu k))$ on the last iterate without averaging, with a constant independent of both the smoothness constant $L$ and the gradient bound $G^2$.
In the convex case, the last iterate reaches $O((1+\log k)/\sqrt{k})$ using the $k^{3/4}$ learning-rate schedule, with no need to fix the iteration horizon in advance.
The extra coupling term $\gamma_k(y_k-x_k)$ is part of the algorithm that makes the Lyapunov proof close; omitting it, as common momentum SGD does, forfeits the proven guarantee.
A short constant-learning-rate warm start puts the Lyapunov function below the critical value $E_{crit}$, so the algorithm can be initialized in a state where the decreasing schedule's rate applies.
The constant-learning-rate phase converges exponentially at rate $1-h\sqrt{\mu}$ to a noise-dominated neighborhood, improving on the standard $1-h\mu$ contraction of SGD.

Reading between the lines

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

One testable extension: replacing the stochastic-gradient noise model with variance-reduced gradients, the finite-sum case the paper explicitly defers, may preserve the same Lyapunov argument and yield accelerated rates with finite-sum constants.
The $\gamma_k$ term's role could be isolated empirically: running heuristic momentum SGD with and without this term on a smooth convex problem with controlled noise would show whether the proven acceleration appears in practice or only in the bound.
The ODE-discretization route suggests a recipe: any Lyapunov function with known dissipation can be coupled with a decreasing step schedule to generate new SGD variants, although the paper does not claim this generality.
The convex schedule $h_k \propto k^{-3/4}$ is unusual; if the bound is tight, it implies the optimal choice of $c$ balances initialization error and noise, which could guide step-size tuning in practice.

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

Short version: this paper is a real contribution to last-iterate SGD analysis, but the convex-case theorem is false as written. The strongly convex half holds up; the convex half needs repair, and I think the repair is doable.

The genuinely new piece is the stochastic extension: a coupled first-order ODE system, the k^{3/4} learning rate, and Lyapunov dissipations that give optimal last-iterate rates under the standard stochastic approximation model (unbiased gradients, bounded variance). The continuous-time part is a reformulation of the high-resolution ODE family from Shi et al. 2018, as the authors themselves note, but the stochastic analysis and the improved constants are not in that prior work. In the strongly convex case the proof is coherent: they set v0=x0, the dissipation (24) and the constant- and decreasing-rate results in Props 3.5 and 3.7 check out, and the 4σ²/(μ(k+k0)) bound with no L dependence is a genuine improvement over the G²-based bounds in Table 1.

The convex section is another story. Definition 5.1 does not connect v0 to x0, and at k=0 the weight in Lemma 5.3 is 2h0/t0=2, so the claimed convex combination actually has a negative coefficient on the f(xk)-f* term. The counterexample is simple: f(x)=x²/2, L=1, c=1/2, σ=0, x0=10, v0=x*=0. Then E^C_0=0, but one step of the algorithm gives E^C_1=6.25, directly contradicting the monotonicity (38) and the bound in Prop 5.4. That is a real flaw, not a technicality. The fix is plausible: impose v0=x0 and handle k=0 as a separate base case, exactly as the strongly convex section already does. There is also a false inequality in Prop 5.4: (k+1)^{1/4}-1 ≥ k^{1/4} fails for every k≥1, so the stated constant 1/(16c²) is not proven. A slightly worse constant should rescue the O(1/√k) rate.

Two smaller issues: the γ_k formula in Prop 2.2 has the wrong denominator (it should be 2√Cf+k+3, not 4+k), a typo but in an algorithm specification; and the outline promises numerical simulations in a section that never appears. The constant comparison in Table 1 is apples-to-oranges—G²-based bounds versus σ²-based bounds—so the 'better constants' claim should be nuanced, though the removal of the L dependence is still meaningful.

Who this is for: stochastic optimization researchers working on accelerated momentum schemes and Lyapunov arguments. It deserves a serious referee. The core idea is good, the strongly convex part is likely correct, and the convex part is probably salvageable. I would accept it for peer review with the clear expectation that the convex case be rewritten.

Recommendation: engage with this paper, but do not trust Prop 5.2 or Prop 5.4 in their current form. Ask the authors for the base-case fix and for a correct lower bound on t_{k-1}.

Referee Report

3 major / 4 minor

Summary. The paper proposes a coupled first-order ODE system whose forward-Euler discretization with a constant learning rate recovers Nesterov's accelerated gradient method in both the strongly convex and convex cases. The same system, discretized with decreasing learning rates, yields two new stochastic gradient descent algorithms: one for strongly convex objectives with an O(1/k) last-iterate rate and one for convex objectives with an O(log k / sqrt(k)) last-iterate rate. The proofs are based on Lyapunov functions: for the strongly convex case the dissipation inequality gives E[E_{k+1}] <= (1 - h_k sqrt(mu)) E[E_k] + h_k^2 sigma^2, and for the convex case the dissipation gives E[E_{k+1}] <= E[E_k] + h_k^2 t_k^2 sigma^2. The paper claims improved constants over prior SGD last-iterate bounds, with the smoothness constant L removed from the rate and the noise measured by variance sigma^2 rather than second-moment bound G^2.

Significance. If correct, the paper would provide a rigorous acceleration guarantee for momentum-style SGD and a clean Lyapunov-based derivation of new algorithms with better constants than existing last-iterate SGD bounds. The strongly convex section is a coherent extension of the deterministic Lyapunov approach, and the explicit coefficient formulas make the algorithms easy to implement and test. The paper also gives a useful perspective connecting Nesterov acceleration, high-resolution ODEs, and stochastic discretizations. However, the convex-case result is not established as stated: the key dissipation step fails at k=0 because the weighted combination in Lemma 5.3 is not a convex combination, and the rate proof in Proposition 5.4 uses a false numerical inequality. The strongly convex contribution is therefore sound in its main lines, but the convex contribution needs a substantial repair before the advertised claims can be accepted.

major comments (3)

[Section 5.1, Proposition 5.2 and Lemma 5.3] The dissipation inequality (38) is false as stated because the proof at k=0 uses a negative weight. In Lemma 5.3, inequalities (41) and (42) are combined with weights 1 - 2h_k/t_k and 2h_k/t_k, respectively. Since t_0 = h_0 by the definition t_k = sum_{i=0}^k h_i, the first weight is -1 at k=0, so the combination is not a convex combination and the resulting inequality is not justified. Moreover, Definition 5.1 sets E_0^C = 2|v_0 - x*|^2 without any condition relating v_0 to x_0. A concrete counterexample is f(x) = x^2/2, L=1, c=1/2 (so h_0=1/2), sigma=0, x_0=10, v_0=0=x*. Then E_0^C=0, while the update in (Per-FE-C) gives x_1=-5 and v_1=1.25, so E_1^C = t_0^2 f(x_1) + 2|v_1|^2 = 6.25, violating the claimed inequality E[E_1^C] <= E[E_0^C] + h_0^2 t_0^2 sigma^2 = 0. Consequently Proposition 5.2 and the rate bound in Proposition 5.4 are not proven, and Proposition 5.4 is false as stated for the k=1 case of this example.
[Section 5.2, Proposition 5.4 proof] The proof contains the false inequality (k+1)^{1/4} - 1 >= k^{1/4}, used to conclude t_{k-1} >= 4c k^{1/4}. For k>0 the left-hand side is strictly smaller than k^{1/4}, e.g. for k=1 it is 2^{1/4}-1 approx 0.189 < 1. Thus the lower bound on t_{k-1} and the final uniform constant in Proposition 5.4 are not established. A correct estimate would need a different lower bound, such as t_{k-1} >= 4c(k^{1/4}-1), which would weaken the stated result or require a modified argument.
[Section 2.2, Proposition 2.2] The stated formula for gamma_k is inconsistent with the derivation in the same proposition. Proposition 2.2 gives gamma_k = k/(2 sqrt(C_f) + 4 + k), but the proof obtains gamma_k = w_{k+1} * k/2 with w_{k+1} = 1/(sqrt(C_f) + 1 + (k+1)/2), which simplifies to gamma_k = k/(2 sqrt(C_f) + k + 3). The form in the Introduction and the matching derivation both give the denominator 2 sqrt(C_f) + k + 3. As written, the algorithm in Proposition 2.2 does not match the system (11)-(13) from which it is derived, so a reader implementing the stated gamma_k would not obtain the algorithm analyzed in Section 3.

minor comments (4)

[General] The manuscript refers to a final numerical simulations section with the placeholder 'Section ??', but the paper ends with the references and contains no numerical experiments. Either add the promised section or remove the reference to it.
[Section 3.2, Proposition 3.7 proof] The algebraic line in the induction writes (k+k0-1)(k+k0-1) <= (k+k0)^2, but the intended inequality is (k+k0-1)(k+k0+1) <= (k+k0)^2, which is true and needed to pass from the numerator k+k0-1 to the denominator k+k0+1. This appears to be a typographical error.
[Section 5.2, Proposition 5.4 proof] There are several typographical issues in the comparison-series steps ('obrain', 'series-intergal') and in the summation index 'sum_{i=1}^k 1/x'; these should be corrected for clarity.
[Section 5.1, Definition 5.1] The convex-case initialization is under-specified: unlike the strongly convex case, where Definition 3.1 explicitly sets v_0 = x_0, the convex section does not impose any relation between v_0 and x_0. If the published result requires an extra assumption, it should be stated and used in the proof.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence rates are derived from constructed Lyapunov dissipations, not assumed as inputs.

full rationale

The derivation chain is self-contained. The coupled ODE system (11)-(13) is discretized, the algorithm coefficients are chosen so that the one-step Lyapunov dissipations (24) and (37) hold, and the claimed last-iterate rates (Prop. 3.7 and Prop. 5.4) are obtained by summing those dissipations. The paper's statement in Section 2.2 that coefficients are chosen by 'taking the Lyapunov function and going through the dissipation proof, choosing the coefficients which make the proof go through' is transparent design-for-proof, not a circular reduction: the rates are consequences of the dissipations, and no fitted parameter is renamed as a prediction. The only self-citation (Oberman and Prazeres [2019] in the proof of Prop. 3.7) is used as a pointer to a standard induction argument, and the induction is reproduced in the paper, so it is not load-bearing. A reviewer concern about the convex-case proof (the weight 1-2h_k/t_k is negative at k=0 and no v0 = x0 condition is imposed) is a mathematical-correctness issue in the argument as stated, not a circularity, because the claimed bound is not equivalent to an input by construction. Therefore no circularity score increase is warranted.

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

No new entities are postulated. The free parameters are user-chosen algorithm constants c and k0; the proofs otherwise rely on standard smoothness, convexity and noise assumptions. The algorithms' coefficients alpha_k, beta_k and gamma_k are derived from the ODE discretization and Lyapunov analysis, not fitted to data.

free parameters (2)

c (convex learning-rate constant) = user-chosen, c ≤ 1/sqrt(L)
Appears in h_k = c/(k+1)^{3/4} (Proposition 5.4). The rate bound contains E0/(16c²) and c²σ², so c trades off initial error and noise terms; the proof requires c ≤ 1/sqrt(L).
k0 (strongly convex schedule offset) = k0 = max{2*sqrt(C), 4σ²/(μ E0^SC)}
Shifts h_k = 2/(sqrt(μ)(k+k0)) (Proposition 3.7). It is determined by the condition number, noise variance and initial Lyapunov value, not fitted to samples.

assumptions (4)

domain assumption f is L-smooth and μ-strongly convex in Sections 2-3, and convex and L-smooth in Sections 4-5, with finite minimum.
Used in all smoothness and convexity inequalities, e.g., Lemmas 3.3, 3.4, 5.3.
domain assumption Stochastic gradients satisfy E[ĝ]=∇f and Var(ĝ) ≤ σ², equivalently E[e]=0 and E[|e|²] ≤ σ² (equations (1)-(2)).
Controls the error terms beta_k in Propositions 3.2 and 5.2; the finite-sum case is deferred in Section 1.1.
domain assumption Learning rates satisfy h_k ≤ 1/sqrt(L), and c ≤ 1/sqrt(L) in the convex schedule.
Needed for the |∇f|² and |x_k-y_k|² coefficients in the Lyapunov dissipations to be non-positive.
standard math Optimal last-iterate rates Ω(1/k) and Ω(1/sqrt(k)) from Agarwal et al. 2009.
Cited in Section 1.2 to justify calling the rates optimal; not derived in this paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent." pith.science (2026). https://pith.science/paper/ZOY26A6P

@misc{pith2026190807861,
  author       = {Pith},
  title        = {Pith review of: Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZOY26A6P}},
  note         = {Machine review of arXiv:1908.07861}
}

abstract

We present a coupled system of ODEs which, when discretized with a constant time step/learning rate, recovers Nesterov's accelerated gradient descent algorithm. The same ODEs, when discretized with a decreasing learning rate, leads to novel stochastic gradient descent (SGD) algorithms, one in the convex and a second in the strongly convex case. In the strongly convex case, we obtain an algorithm superficially similar to momentum SGD, but with additional terms. In the convex case, we obtain an algorithm with a novel order $k^{3/4}$ learning rate. We prove, extending the Lyapunov function approach from the full gradient case to the stochastic case, that the algorithms converge at the optimal rate for the last iterate of SGD, with rate constants which are better than previously available.

Figures

Figures reproduced from arXiv: 1908.07861 by the authors.

**Figure 1.** Illustration of the role of the variables x, v, y in the algorithm. Notice that (9) leads to (10) 1 − w w = p Cf Next, collect the vk term in (8) and and eliminate the gradient term using (AGD1), to obtain vk+1 = (1 − w)vk + wxk + p Cf (xk+1 − yk) = (1 − w)vk + wxk + 1 − w w (xk+1 − yk), by (10) Eliminate the variables vk+1 and vk using (6) applied at k and k + 1, respectively, to obtain 1 w (yk+1 − (1 − w)xk+1) = 1… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 29 canonical work pages

[1]

Agarwal, M

A. Agarwal, M. J. Wainwright, P. L. Bartlett, and P. K. Ravikumar. Information-theoretic lower bounds on the oracle complexity of convex optimization. In Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems 22, pages 1--9. Curran Associates, Inc., 2009. URL http://papers.ni...

work page 2009
[2]

Allen-Zhu

Z. Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 1200--1205. ACM, 2017

work page 2017
[3]

Alvarez, H

F. Alvarez, H. Attouch, J. Bolte, and P. Redont. A second-order gradient-like dissipative dynamical system with hessian-driven damping.-application to optimization and mechanics. Journal de math \'e matiques pures et appliqu \'e es , 81 0 (8): 0 747--780, 2002

work page 2002
[4]

Assran and M

M. Assran and M. Rabbat. On the convergence of nesterov's accelerated gradient method in stochastic settings, 2020

work page 2020
[5]

Attouch, J

H. Attouch, J. Peypouquet, and P. Redont. Fast convex optimization via inertial dynamics with hessian driven damping. Journal of Differential Equations, 261 0 (10): 0 5734--5783, 2016

work page 2016
[6]

Beck and M

A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences, 2 0 (1): 0 183--202, 2009

2009
[7]

Bengio, N

Y. Bengio, N. Boulanger-Lewandowski, and R. Pascanu. Advances in optimizing recurrent networks. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 8624--8628. IEEE, 2013

work page 2013
[8]

Bottou, F

L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. arXiv preprint arXiv:1606.04838, 2016

arXiv 2016

Show all 40 references

[9]

Bottou, F

L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60 0 (2): 0 223--311, 2018

2018
[10]

S. Bubeck . Convex Optimization: Algorithms and Complexity . ArXiv e-prints, May 2014

2014
[11]

Defazio and L

A. Defazio and L. Bottou. On the ineffectiveness of variance reduced optimization for deep learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alch\' e -Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 1755--1765. Curra...

2019
[12]

Defazio, F

A. Defazio, F. Bach, and S. Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Sys...

2014
[13]

Flammarion and F

N. Flammarion and F. Bach. From averaging to acceleration, there is only a step-size. In Conference on Learning Theory, pages 658--695, 2015

2015
[14]

Frostig, R

R. Frostig, R. Ge, S. Kakade, and A. Sidford. Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization. In ICML, volume 37 of JMLR Workshop and Conference Proceedings, pages 2540--2548. JMLR.org, 2015

2015
[15]

P. Jain, S. M. Kakade, R. Kidambi, P. Netrapalli, and A. Sidford. Accelerating stochastic gradient descent for least squares regression. In S. Bubeck, V. Perchet, and P. Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machi...

2018
[16]

P. Jain, D. Nagaraj, and P. Netrapalli. Making the last iterate of sgd information theoretically optimal. In Proceedings of the Annual Conference On Learning Theory (COLT), pages 1752--1755, 2019

2019
[17]

Johnson and T

R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 26, pages 315--323. Curran Associat...

2013
[18]

Kidambi, P

R. Kidambi, P. Netrapalli, P. Jain, and S. Kakade. On the insufficiency of existing momentum schemes for stochastic optimization. In 2018 Information Theory and Applications Workshop (ITA), pages 1--9. IEEE, 2018

2018
[19]

Kingma and J

D. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014

2014 arXiv
[20]

Krichene, A

W. Krichene, A. Bayen, and P. L. Bartlett. Accelerated mirror descent in continuous and discrete time. In Advances in Neural Information Processing Systems 28, pages 2845--2853. Curran Associates, Inc., 2015

2015
[21]

Lacoste-Julien, M

S. Lacoste-Julien, M. Schmidt, and F. 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
[22]

Lessard, B

L. Lessard, B. Recht, and A. Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 26 0 (1): 0 57--95, 2016

2016
[23]

H. Lin, J. Mairal, and Z. Harchaoui. A universal catalyst for first-order optimization. In Advances in Neural Information Processing Systems 28, pages 3384--3392. Curran Associates, Inc., 2015

2015
[24]

Nemirovski, A

A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19 0 (4): 0 1574--1609, 2009

2009
[25]

Nesterov

Y. Nesterov. A method of solving a convex programming problem with convergence rate o (1/k2)
[26]

Nesterov

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

2013
[27]

A. M. Oberman and M. Prazeres . Stochastic Gradient Descent with Polyak's Learning Rate . arXiv e-prints, art. arXiv:1903.08688, Mar 2019

1903 arXiv
[28]

B. T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4 0 (5): 0 1--17, 1964

1964
[29]

B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM J. Control Optim., 30 0 (4): 0 838--855, July 1992. ISSN 0363-0129. doi:10.1137/0330046. URL https://doi.org/10.1137/0330046

1992 doi
[30]

X. Qian, P. Richtarik, R. Gower, A. Sailanbayev, N. Loizou, and E. Shulgin. Sgd with arbitrary sampling: General analysis and improved rates. In International Conference on Machine Learning, pages 5200--5209, 2019

2019
[31]

Rakhlin, O

A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML'12, pages 1571--1578, Madison, WI, USA, 2012. Omnipres...

2012
[32]

Schmidt, N

M. Schmidt, N. L. Roux, and F. Bach. Convergence rates of inexact proximal-gradient methods for convex optimization. In Proceedings of the 24th International Conference on Neural Information Processing Systems, NIPS'11, pages 1458--1466, Red Hook, NY, USA, 2011. Curran Associa...

2011
[33]

Schmidt, N

M. Schmidt, N. Le Roux, and F. Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162 0 (1-2): 0 83--112, 2017

2017
[34]

Serhat Aybat , A

N. Serhat Aybat , A. Fallah , M. Gurbuzbalaban , and A. Ozdaglar . Robust Accelerated Gradient Methods for Smooth Strongly Convex Functions . arXiv e-prints, art. arXiv:1805.10579, May 2019

2019 arXiv
[35]

Shamir and T

O. Shamir and T. Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International Conference on Machine Learning, pages 71--79, 2013

2013
[36]

B. Shi, S. S. Du, M. I. Jordan, and W. J. Su. Understanding the acceleration phenomenon via high-resolution differential equations. arXiv preprint arXiv:1810.08907, 2018

2018 arXiv
[37]

W. Su, S. Boyd, and E. Candes. A differential equation for modeling nesterov's accelerated gradient method: Theory and insights. In Advances in Neural Information Processing Systems, pages 2510--2518, 2014

2014
[38]

Wibisono, A

A. Wibisono, A. C. Wilson, and M. I. Jordan. A variational perspective on accelerated methods in optimization. Proceedings of the National Academy of Sciences, page 201614734, 2016

2016
[39]

Wilson , L

A. Wilson , L. Mackey , and A. Wibisono . Accelerating Rescaled Gradient Descent: Fast Optimization of Smooth Functions . arXiv e-prints, art. arXiv:1902.08825, Feb 2019

1902 arXiv
[40]

A. C. Wilson, B. Recht, and M. I. Jordan. A lyapunov analysis of momentum methods in optimization. arXiv preprint arXiv:1611.02635, 2016

2016 arXiv

Pith tools

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

[1] [1]

Agarwal, M

A. Agarwal, M. J. Wainwright, P. L. Bartlett, and P. K. Ravikumar. Information-theoretic lower bounds on the oracle complexity of convex optimization. In Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems 22, pages 1--9. Curran Associates, Inc., 2009. URL http://papers.ni...

work page 2009

[2] [2]

Allen-Zhu

Z. Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 1200--1205. ACM, 2017

work page 2017

[3] [3]

Alvarez, H

F. Alvarez, H. Attouch, J. Bolte, and P. Redont. A second-order gradient-like dissipative dynamical system with hessian-driven damping.-application to optimization and mechanics. Journal de math \'e matiques pures et appliqu \'e es , 81 0 (8): 0 747--780, 2002

work page 2002

[4] [4]

Assran and M

M. Assran and M. Rabbat. On the convergence of nesterov's accelerated gradient method in stochastic settings, 2020

work page 2020

[5] [5]

Attouch, J

H. Attouch, J. Peypouquet, and P. Redont. Fast convex optimization via inertial dynamics with hessian driven damping. Journal of Differential Equations, 261 0 (10): 0 5734--5783, 2016

work page 2016

[6] [6]

Beck and M

A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences, 2 0 (1): 0 183--202, 2009

2009

[7] [7]

Bengio, N

Y. Bengio, N. Boulanger-Lewandowski, and R. Pascanu. Advances in optimizing recurrent networks. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 8624--8628. IEEE, 2013

work page 2013

[8] [8]

Bottou, F

L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. arXiv preprint arXiv:1606.04838, 2016

arXiv 2016