Pith. sign in

REVIEW 2 major objections 4 minor 66 references

On the Effectiveness of the z-Transform Method in Quadratic Optimization

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read For quadratic objectives, a single spectral dimension fixes the exact asymptotic rate of gradient descent, Nesterov acceleration, and SGD.

desk verdict Sharp rate constants for quadratic optimization via z-transforms, but the Nesterov Tauberian verification has a genuine gap that needs repair. read the letter →

arxiv 2507.03404 v2 pith:DAS4TRUU submitted 2025-07-04 cs.LG math.OC

Francis Bach (SIERRA) This is my paper · ORCID
classification cs.LGmath.OC MSC 40E0541A6065K10
keywords z-transformTauberiantheoremsspectraldimensionasymptoticequivalentsgradientdescentNesterovaccelerationstochasticquadraticoptimization
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 argues that a classical signal-processing tool, the z-transform of a sequence, combined with Tauberian theorems, gives exact asymptotic equivalents for a broad family of quadratic optimization algorithms. For gradient descent in an infinite-dimensional Hilbert space, the convergence rate is set by one number, the spectral dimension $\omega$ of a weighted spectral measure, yielding $a_k \sim c\Gamma(\omega)/(2k)^\omega$. Nesterov acceleration with momentum $2/(k+1)$ improves this to a rate proportional to $k^{-\min\{2\omega,\omega+1\}}$, with a logarithmic case at $\omega=1$, and the same machinery handles heavier extrapolation, averaging, additive noise, and stochastic gradient descent. If these results are right, scaling laws for these methods become precise enough to compare algorithms by constants, not just by exponents.

What carries the argument

The z-transform $A(z)=\sum_{k=0}^\infty a_k z^k$ is paired with Tauberian bridge theorems of the form $\lim_{z\to 1^-}(1-z)^\alpha A^{(\mu)}(z)=\Gamma(\alpha)\lim_{k\to\infty} k^{1+\mu-\alpha}a_k$, valid under one-sided conditions, so behavior of $A$ near $z=1$ becomes an exact equivalent for the sequence. The workhorse for quadratic optimization is the Stieltjes transform $S(u)=\int d\sigma(\lambda)/(\lambda+u)$ of the weighted spectral measure, whose prescribed pure-power derivatives in Assumption (A1) are what turn $z$-transform expansions into sharp $k^{-\omega}$ laws. For accelerated and stochastic recursions, a convolution identity for z-transforms, $1/(a-uz)*1/(b-vz)=1/(ab-uvz)$, reduces rational transforms in $z$ and $\lambda$ to sums of Stieltjes transforms at shifted arguments, where the same Assumption (A1) applies.

What would settle it

Take a compact Hessian with eigenvalues $\lambda_i=i^{-\alpha}(\log(i+1))^{-2}$, initialize with coefficients spread over all modes, compute the gradient-descent function-value sequence $a_k$, and check whether $a_k k^{\omega}$ converges to the predicted constant $c\Gamma(\omega)/2^\omega$ for large $k$; divergence or oscillation would show that the pure-power Assumption (A1) is violated. Alternatively, run heavy-ball with $\omega>1$ and observe non-vanishing oscillation, the failure mode Section 4.1 predicts.

Watch

Extended reading notes

Core claim

In a separable Hilbert space, let $H$ be a compact positive semidefinite operator and let $d\sigma$ be the weighted spectral measure built from $\gamma H$ and the initial deviation; the paper shows that under Assumption (A1), all derivatives of the Stieltjes transform $S(u)=\int d\sigma(\lambda)/(\lambda+u)$ behave near $u=0$ as $c(-1)^{k-1}\Gamma(k-\omega)\Gamma(\omega)u^{\omega-k}$ for one number $\omega>0$. Then the function-value sequence $a_k$ of gradient descent satisfies $a_k \sim c\Gamma(\omega)/(2k)^\omega$. For Nesterov acceleration with momentum $2/(k+1)$, the performance obeys a law proportional to $k^{-\min\{2\omega,\omega+1\}}$, with a $\log k/k^2$ boundary at $\omega=1$; the same template gives, in one case conjecturally with a partial proof, the extended extrapolation family $k^{-\min\{2\omega,\omega+\rho\}}$, plus rates for averaging, additive-noise variance terms, and single-pass stochastic gradient descent on least squares, where the bias follows $k^{-\omega}$ up to a crossover at $\omega=2-1/\alpha$ and the variance converges to an explicit constant. Heavy-ball is the boundary case: non-vanishing oscillations make the Tauberian conversion fail, so no simple asymptotic equivalent holds there.

Load-bearing premise

Everything rests on Assumption (A1): near zero, every derivative of the Stieltjes transform of the weighted spectral measure must behave like a pure power $u^{\omega-k}$, with no logarithmic factors, gaps, or competing scales; if the true spectrum has such structure, the stated $k^{-\omega}$ rates need not hold.

Editorial extensions

If this is right

  • Gradient descent on a quadratic with spectral dimension $\omega$ converges as $c\Gamma(\omega)/(2k)^\omega$; under eigenvalue and coefficient decays $\lambda_i\sim i^{-\alpha}$, $\delta_i\sim i^{-\beta/2}$, this means $\omega=(\beta-1)/\alpha+1$ and beats the classical worst-case $1/k$ whenever $\beta>1$.
  • Nesterov acceleration with momentum $2/(k+1)$ changes the exponent to $\min\{2\omega,\omega+1\}$, with a $\log k/k^2$ law at $\omega=1$; the familiar worst-case $1/k^2$ bound is only the $\omega>1$ regime.
  • The generalized extrapolation indexed by an integer $\rho$ is conjectured to give $k^{-\min\{2\omega,\omega+\rho\}}$, with $\log k/k^{2\rho}$ at $\omega=\rho$, verified symbolically for $\rho<8$ and empirically beyond.
  • Heavy-ball acceleration is a genuine counterexample to the method: its oscillating terms do not vanish for $\omega\ge1$, so Abel/Tauberian conversion breaks down and no simple equivalent holds.
  • Additive noise, averaging, and single-pass SGD inherit the same calculus: noise splits into bias and variance terms with explicit exponents, and the SGD bias recovers previously known tight rates with a more direct proof.

Reading between the lines

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

  • The convolution calculus should transfer to any linear iteration whose z-transform is rational in $z$ and in the spectral variable $\lambda$, so closed-form equivalents for Landweber iterations, gossip averaging, and Richardson extrapolation are likely to follow from the same template without a new idea.
  • The sharp logarithmic case at $\omega=1$ signals that spectral measures with slowly varying factors would produce $\log^p k$ corrections; adding such factors to Assumption (A1) would introduce a second parameter that the current single-$\omega$ statement hides.
  • The SGD crossover at $\omega=2-1/\alpha$ is a concrete testable prediction: varying the source and capacity exponents should move the observed bias rate from $k^{-\omega}$ to $k^{-(2-1/\alpha)}$ exactly at that threshold, so finite-time experiments could estimate the boundary.
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

2 major / 4 minor

Summary. The paper proposes a z-transform/Tauberian framework for deriving exact asymptotic equivalents of performance sequences arising in quadratic optimization in Hilbert spaces. Under Assumption (A1) on the weighted spectral measure, it derives rates for gradient descent (Proposition 1, a_k ~ cΓ(ω)/(2k)^ω), Nesterov acceleration with momentum 2/(k+1) (Proposition 2, with rates k^{-2ω}, k^{-1-ω}, and a logarithmic case at ω=1), heavy-ball as a case where oscillations prevent such equivalents, additive-noise variants (Propositions 3 and 4), averaged gradient descent (Proposition 5), and least-mean-squares SGD (Proposition 6, with rates k^{-ω} or k^{-(2-1/α)} plus a constant variance limit). A generalized Nesterov recursion with parameter ρ is analyzed and stated as Conjecture 1, with symbolic verification for ρ<8. The paper emphasizes the two-step z-transform method: first establish Tauberian conditions, then expand the z-transform near z=1.

Significance. If the stated results are correct, the paper provides sharp, constant-explicit scaling laws that complement non-asymptotic worst-case bounds and unify several existing analyses, including those of Berthier et al., Velikanov and Yarotsky, and Flammarion and Bach. The paper is honest about its assumptions: the spectral-dimension postulate (A1) is clearly identified as an input rather than fitted, and the general-ρ result is explicitly labeled a conjecture with only partial proof. The use of machine-checked Mathematica notebooks for the algebraic convolutions and the explicit treatment of Tauberian conditions in Propositions 1 and 2 are strengths. The paper is likely to be of interest to the optimization and signal-processing communities, provided the proof gaps discussed below are resolved.

major comments (2)
  1. [Appendix B (Eq. (29))] The Tauberian verification for Proposition 2 contains a load-bearing error. In the partial-fraction expansion (25), the oscillatory contributions to a_k are of the form ∫ (1/λ) b(λ) r(λ)^k dσ(λ) with |b(λ)|=1/4 and |r(λ)|=1-λ, and the first term is -∫ (1/(2λ))(1-λ)^k dσ(λ). However, Eq. (29) bounds |a_k - a_{k-1}| by (1/4)∫(1-λ)^k dσ(λ), dropping the 1/λ factor. For the canonical measure dσ(λ) ~ c λ^{ω-1}dλ, the true bound is of order k^{1-ω} (or k^{-ω} for the already-simplified integral), not O(k^{-ω-1}) as claimed. Consequently, the one-sided Tauberian condition required by Theorem 4, namely k^{2-α}(a_k - a_{k-1}) ≤ c, is not established. In particular, for ω ∈ (0,1), the exponent of k in the submitted estimate is positive, so the condition can fail by the written argument. The exact asymptotic equivalence stated in Proposition 2 therefore lacks a demonstrated Tauberian justification; a cancellation argument among the oscillatory terms may repair it, but none is supplied.
  2. [Section 7 / Appendix E] The proof derives the z-transform A(z) = (C(z)-D(z))/(1-B(z)) of the bias term, obtains its asymptotic expansion near z=1, and immediately concludes the sequence equivalent a_k ∼ c(1-υ)^{-1}Γ(ω)/(2k)^ω (or the k^{-(2-1/α)} rate). No Tauberian condition for the final value theorem is verified. The expected-performance sequence here is not shown to be monotone, and unlike the gradient-descent case in Proposition 1, the paper does not provide a difference bound of the form k^{2-α}(a_k - a_{k-1}) ≤ c. Since Section 2 of the paper itself emphasizes that the z-transform-to-sequence step requires such a condition, the claimed exact equivalents in Proposition 6 are not established as written. The same omission appears in Appendix E for Proposition 5, where the sequence equivalent is inferred from the z-transform expansion without an explicit Tauberian check.
minor comments (4)
  1. [Section 4.2] Conjecture 1 is explicitly labeled a conjecture and verified symbolically only for ρ<8; the text should state clearly that no Tauberian proof is provided for any ρ, including ρ=1, which is relevant in light of the gap in Proposition 2.
  2. [Section 5.2] The statement contains a typo: "Assume λ_i = γL/i^α for α > ," where the positive lower bound is missing; it should presumably read α > 1.
  3. [Section 7] The phrase "with the model defined in and the performance measure" is missing a reference (likely Eq. (22)), and the sentence "defined from from Eq. (19)" repeats "from".
  4. [Appendix B] The phrase "the (j-1)!-th order derivative" is unclear; it should be "the (j-1)-th order derivative" or "the derivative of order j-1".

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the rates are derived from the explicit spectral Assumption (A1) via z-transform and Tauberian theorems, with no fitted parameters and no load-bearing self-citations.

full rationale

The paper is not circular in the relevant sense. Assumption (A1) fixes the Stieltjes-transform behavior of the weighted spectral measure, and all the asymptotic equivalents (gradient descent, Nesterov acceleration, averaging, noisy and stochastic variants) are derived from that assumption together with standard Tauberian theorems and explicit convolution identities. The claimed exponents and constants are functions of the input quantities (spectral dimension omega, constant c, noise parameters), not quantities fitted to observed convergence curves. Self-citations to Berthier et al. (2020a), Flammarion and Bach (2015), and Bach and Moulines (2013) set conventions or provide context, but the proofs in Sections 3-7 and the appendices do not reduce to those citations: Lemmas 1-3 give self-contained sufficient conditions for Assumption (A1), and Proposition 1 and Proposition 2 are proved from Eq. (6) and Eq. (27)-(29) rather than imported from prior work. The paper honestly labels Section 4.2 as a partial proof and notes that Tauberian conditions are not proved there, which is an incompleteness, not a circularity. The Appendix B estimate at Eq. (29) has been questioned as a possible technical gap because of the handling of a 1/lambda factor, but that is a correctness concern about a bound, not an equivalence between the result and its inputs; it does not make the derivation circular. Overall, the central claims are conditional, self-contained mathematical derivations from stated assumptions, so the circularity score is 0.

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

The paper introduces no fitted parameters: omega, c, alpha, beta, and kappa are inputs describing the Hessian spectrum, initialization, noise, or data distribution. The central derivations are conditional on these stated assumptions, not on parameters tuned to reproduce the observed convergence curves. The only explicitly unproved piece is the Tauberian side of Conjecture 1, which is listed as an axiom because its validity is required for the general-rho rate to become a theorem.

assumptions (5)
  • domain assumption Assumption (A1): the weighted spectral measure sigma is supported in [0,1) and its Stieltjes transform derivatives satisfy S^{(k-1)}(u) ~ c (-1)^{k-1} Gamma(k-omega)Gamma(omega) u^{omega-k} near u=0 for all integers k > omega.
    Introduced in Section 3, Eq. (7). All asymptotic rate results are conditional on this power-law behavior of the spectral measure; it encodes eigenvalue decay and initialization alignment, but is not derived from the algorithm.
  • domain assumption Eigenvalue and coefficient decay model: lambda_i = gamma L i^{-alpha}, |<delta,u_i>| = Delta i^{-beta/2}, which yields omega = (beta-1)/alpha + 1.
    Used in Lemma 3 to translate Assumption (A1) into concrete constants for gradient descent, Nesterov acceleration, and stochastic gradient descent. This is a standard source and capacity condition in learning theory.
  • standard math Tauberian theorems from Korevaar, Theorems 3 and 4, converting (1-z)^alpha A(z) behavior as z approaches 1 from below into sequence asymptotics.
    Used throughout to justify the passage from z-transform equivalents to k-asymptotics. The required one-sided conditions are checked case by case in the proofs.
  • domain assumption SGD input model Eq. (22): x = sum_i h_i^{1/2} z_i u_i with independent z_i, E[z_i]=0, E[z_i^2]=1, E[z_i^4]=3+kappa.
    Gaussian-like high-dimensional model from Section 7.2 that makes the fourth-moment tensor tractable. It includes Gaussian inputs with kappa=0 and Rademacher inputs with kappa=-2.
  • ad hoc to paper Unproven Tauberian conditions for Conjecture 1 are assumed to hold when the general-rho Nesterov rate is used as a result.
    Section 4.2 explicitly labels this as a conjecture with only the z-transform expansion checked symbolically for rho<8 and by simulation. The status of the Tauberian half is explicitly missing.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Effectiveness of the z-Transform Method in Quadratic Optimization." pith.science (2026). https://pith.science/paper/DAS4TRUU

@misc{pith2026250703404,
  author       = {Pith},
  title        = {Pith review of: On the Effectiveness of the z-Transform Method in Quadratic Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DAS4TRUU}},
  note         = {Machine review of arXiv:2507.03404}
}
abstract

The z-transform of a sequence is a classical tool used within signal processing, control theory, computer science, and electrical engineering. It allows for studying sequences from their generating functions, with many operations that can be equivalently defined on the original sequence and its $z$-transform. In particular, the z-transform method focuses on asymptotic behaviors and allows the use of Taylor expansions. We present a sequence of results of increasing significance and difficulty for linear models and optimization algorithms, demonstrating the effectiveness and versatility of the z-transform method in deriving new asymptotic results. Starting from the simplest gradient descent iterations in an infinite-dimensional Hilbert space, we show how the spectral dimension characterizes the convergence behavior. We then extend the analysis to Nesterov acceleration, averaging techniques, and stochastic gradient descent.

Figures

Figures reproduced from arXiv: 2507.03404 by the authors.

Figure 1
Figure 1. Nesterov acceleration (corresponding to Eq. ( [PITH_FULL_IMAGE:figures/full_fig_p014_1.png] view at source ↗
Figure 2
Figure 2. Heavy-ball acceleration: true performance [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Nesterov acceleration with multiple ρ’s with ω = 3: true performance ak vs. potential asymptotic equivalent ¯ak. Conjecture 1 (Nesterov acceleration, ρ ∈ N) Assume (A1) obtained from Lemma 3. Then for the sequence defined in Eq. (12) and in Eq. (13), we have: ak ∼ c Γ(2ρ) 2 Γ(ρ) 2 ·    Γ(ρ − ω)Γ(ω) Γ(4ρ − 1 − 2ω) Γ(2ρ − 1/2 − ω) Γ(ρ + 1/2 − ω) 2 2ρ−1 4 ω · 1 k 2ω if ω ∈ (0, ρ) 1 2 2ρ−1 log k k 2ρ if ω… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Variance term for Nesterov acceleration with addi [PITH_FULL_IMAGE:figures/full_fig_p021_4.png]
Figure 5
Figure 5. Figure 5: Least-mean-square algorithm for various spectra [PITH_FULL_IMAGE:figures/full_fig_p028_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

66 extracted references · 60 canonical work pages

  1. [1]

    Zico Kolter, and Ryan J

    Alnur Ali, J. Zico Kolter, and Ryan J. Tibshirani. A continuous-time view of early stopping for least squares regression. In International Conference on Artificial Intelligence and Statistics, 2019

    work page 2019

  2. [2]

    Acceleration by Random Stepsizes: Hedging, Equalization, and the Arcsine Stepsize Schedule

    Jason M. Altschuler and Pablo A. Parrilo. Acceleration by random stepsizes: Hedging, equalization, and the arcsine stepsize schedule. Technical Report 2412.05790, arXiv, 2024

    work page Pith review arXiv 2024

  3. [3]

    Strong Convergence of FISTA Iterates under H{\"o}lderian and Quadratic Growth Conditions

    Jean-Fran c ois Aujol, Charles Dossal, Hippolyte Labarri \`e re, and Aude Rondepierre. Strong convergence of FISTA iterates under H olderian and quadratic growth conditions. Technical Report 2407.17063, arXiv, 2024

    work page Pith review arXiv 2024

  4. [4]

    A universally optimal multistage accelerated stochastic gradient method

    Necdet Serhat Aybat, Alireza Fallah, Mert Gurbuzbalaban, and Asuman Ozdaglar. A universally optimal multistage accelerated stochastic gradient method. Advances in Neural Information Processing Systems, 32, 2019

    work page 2019

  5. [5]

    On the effectiveness of R ichardson extrapolation in data science

    Francis Bach. On the effectiveness of R ichardson extrapolation in data science. SIAM Journal on Mathematics of Data Science, 3 0 (4): 0 1251--1277, 2021

    work page 2021

  6. [6]

    High-dimensional analysis of double descent for linear regression with random projections

    Francis Bach. High-dimensional analysis of double descent for linear regression with random projections. SIAM Journal on Mathematics of Data Science, 6 0 (1): 0 26--50, 2024 a

    work page 2024

  7. [7]

    Learning Theory from First Principles

    Francis Bach. Learning Theory from First Principles. MIT Press, 2024 b

    work page 2024

  8. [8]

    Non-asymptotic analysis of stochastic approximation algorithms for machine learning

    Francis Bach and Eric Moulines. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in Neural Information Processing Systems, 2011

    work page 2011

Show all 66 references
  1. [9]

    Non-strongly-convex smooth stochastic approximation with convergence rate O (1/n)

    Francis Bach and Eric Moulines. Non-strongly-convex smooth stochastic approximation with convergence rate O (1/n) . Advances in Neural Information Processing Systems, 2013

    2013

  2. [10]

    Edward A. Bender. Asymptotic methods in enumeration. SIAM Review, 16 0 (4): 0 485--515, 1974

    1974

  3. [11]

    Modern regularization methods for inverse problems

    Martin Benning and Martin Burger. Modern regularization methods for inverse problems. Acta Numerica, 27: 0 1--111, 2018

    2018

  4. [12]

    Analysis of the normalized LMS algorithm with G aussian inputs

    Neil Bershad. Analysis of the normalized LMS algorithm with G aussian inputs. IEEE Transactions on Acoustics, Speech, and Signal Processing, 34 0 (4): 0 793--806, 1986

    1986

  5. [13]

    Acceleration of gossip algorithms through the E uler-- P oisson-- D arboux equation

    Rapha \"e l Berthier and Mufan Li. Acceleration of gossip algorithms through the E uler-- P oisson-- D arboux equation. IMA Journal of Applied Mathematics, 87 0 (6): 0 985--1009, 2022

    2022

  6. [14]

    Accelerated gossip in networks of given dimension using J acobi polynomial iterations

    Rapha \"e l Berthier, Francis Bach, and Pierre Gaillard. Accelerated gossip in networks of given dimension using J acobi polynomial iterations. SIAM Journal on Mathematics of Data Science, 2 0 (1): 0 24--47, 2020 a

    2020

  7. [15]

    Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model

    Rapha \"e l Berthier, Francis Bach, and Pierre Gaillard. Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model. Advances in Neural Information Processing Systems, 2020 b

    2020

  8. [16]

    Handelsman

    Norman Bleistein and Richard A. Handelsman. Asymptotic Expansions of Integrals. Courier Corporation, 1986

    1986

  9. [17]

    Randomized gossip algorithms

    Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52 0 (6): 0 2508--2530, 2006

    2006

  10. [18]

    Redivo Zaglia

    Claude Brezinski and M. Redivo Zaglia. Extrapolation Methods: Theory and Practice, volume 2. Elsevier, 2013

    2013

  11. [19]

    Optimal rates for the regularized least-squares algorithm

    Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7: 0 331--368, 2007

    2007

  12. [20]

    On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm''

    Antonin Chambolle and Charles Dossal. On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm''. Journal of Optimization theory and Applications, 166: 0 968--982, 2015

    2015

  13. [21]

    An Optimization Perspective on Log-Concave Sampling and Beyond

    Sinho Chewi. An Optimization Perspective on Log-Concave Sampling and Beyond. Draft, 2024

    2024

  14. [22]

    Averaged least-mean-squares: Bias-variance trade-offs and optimal sampling distributions

    Alexandre D \'e fossez and Francis Bach. Averaged least-mean-squares: Bias-variance trade-offs and optimal sampling distributions. In International Conference on Artificial Intelligence and Statistics, 2015

    2015

  15. [23]

    Harder, better, faster, stronger convergence rates for least-squares regression

    Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger convergence rates for least-squares regression. Journal of Machine Learning Research, 18 0 (101): 0 1--51, 2017

    2017

  16. [24]

    Asymptotic Expansions

    Arthur Erd \'e lyi. Asymptotic Expansions. Courier Corporation, 1956

    1956

  17. [25]

    A continuized view on N esterov acceleration for stochastic gradient descent and randomized gossip

    Mathieu Even, Rapha \"e l Berthier, Francis Bach, Nicolas Flammarion, Pierre Gaillard, Hadrien Hendrikx, Laurent Massouli \'e , and Adrien Taylor. A continuized view on N esterov acceleration for stochastic gradient descent and randomized gossip. In Advances in Neural Informat...

    2021

  18. [26]

    Dimension-adapted momentum outscales SGD

    Damien Ferbach, Katie Everett, Gauthier Gidel, Elliot Paquette, and Courtney Paquette. Dimension-adapted momentum outscales SGD . Technical Report 2505.16098, arXiv, 2025

    2025 arXiv

  19. [27]

    Convergence analysis of LMS filters with uncorrelated G aussian data

    Arie Feuer and Ehud Weinstein. Convergence analysis of LMS filters with uncorrelated G aussian data. IEEE Transactions on Acoustics, Speech, and Signal Processing, 33 0 (1): 0 222--230, 2003

    2003

  20. [28]

    Singularity analysis of generating functions

    Philippe Flajolet and Andrew Odlyzko. Singularity analysis of generating functions. SIAM Journal on Discrete Mathematics, 3 0 (2): 0 216--240, 1990

    1990

  21. [29]

    From averaging to acceleration, there is only a step-size

    Nicolas Flammarion and Francis Bach. From averaging to acceleration, there is only a step-size. In Conference on Learning Theory, 2015

    2015

  22. [30]

    Global convergence of the heavy-ball method for convex optimization

    Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. In European Control Conference, 2015

    2015

  23. [31]

    Gene H. Golub. Some modified matrix eigenvalue problems. SIAM Review, 15 0 (2): 0 318--334, 1973

    1973

  24. [32]

    Provable non-accelerations of the heavy-ball method

    Baptiste Goujaud, Adrien Taylor, and Aymeric Dieuleveut. Provable non-accelerations of the heavy-ball method. Technical Report 2307.11291, arXiv, 2023

    2023

  25. [33]

    Gower, Mark Schmidt, Francis Bach, and Peter Richt \'a rik

    Robert M. Gower, Mark Schmidt, Francis Bach, and Peter Richt \'a rik. Variance-reduced methods for machine learning. Proceedings of the IEEE, 108 0 (11): 0 1968--1983, 2020

    1968

  26. [34]

    Hardy and John E

    Godfrey H. Hardy and John E. Littlewood. Abel's theorem and its converse. Proceedings of the London Mathematical Society, 2 0 (1): 0 205--235, 1920

    1920

  27. [35]

    Horn and Charles R

    Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 2012

    2012

  28. [36]

    Horowitz and Kenneth D

    Larry L. Horowitz and Kenneth D. Senne. Performance advantage of complex LMS for controlling narrow-band adaptive arrays. IEEE Transactions on Circuits and Systems, 28 0 (6): 0 562--576, 1981

    1981

  29. [37]

    Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford

    Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Accelerating stochastic gradient descent for least squares regression. In Conference On Learning Theory, 2018

    2018

  30. [38]

    Theory and Application of the z -Transform Method

    Eliahu Ibrahim Jury. Theory and Application of the z -Transform Method. Robert E. Krieger Publishing Company, 1964

    1964

  31. [39]

    Kelley and Allan C

    Walter G. Kelley and Allan C. Peterson. Difference Equations: An Introduction with Applications. Academic Press, 2001

    2001

  32. [40]

    Donald E. Knuth. The Art of Computer Programming, volume 1: Fundamental Algorithms. Addison Wesley, 1997

    1997

  33. [41]

    Tauberian Theory: A Century of Developments

    Jacob Korevaar. Tauberian Theory: A Century of Developments. Springer, 2004

    2004

  34. [42]

    Scaling laws for gradient descent and sign descent for linear bigram models under Z ipf's law

    Frederik Kunstner and Francis Bach. Scaling laws for gradient descent and sign descent for linear bigram models under Z ipf's law. Technical Report 2505.19227, arXiv, 2025

    2025 arXiv

  35. [43]

    Complex Analysis

    Serge Lang. Complex Analysis. Springer Science & Business Media, 2013

    2013

  36. [44]

    Analysis and design of optimization algorithms via integral quadratic constraints

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

    2016

  37. [45]

    Adaptive Processing: The Least Mean Squares Approach with Applications in Transmission

    Odile Macchi. Adaptive Processing: The Least Mean Squares Approach with Applications in Transmission. Wiley West Sussex, 1995

    1995

  38. [46]

    A simplified analysis of SGD for linear regression with weight averaging

    Alexandru Meterez, Depen Morwani, Costin-Andrei Oncescu, Jingfeng Wu, Cengiz Pehlevan, and Sham Kakade. A simplified analysis of SGD for linear regression with weight averaging. Technical Report 2506.15535, arXiv, 2025

    2025 arXiv

  39. [47]

    A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach

    Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, 2020

    2020

  40. [48]

    Nemirovsky

    Arkadi S. Nemirovsky. Information-based complexity of linear operator equations. Journal of Complexity, 8 0 (2): 0 153--175, 1992

    1992

  41. [49]

    A method for solving a convex programming problem with rate of convergence O (1/k^2)

    Yurii Nesterov. A method for solving a convex programming problem with rate of convergence O (1/k^2) . Soviet Mathematics. Doklady, 269 0 (3): 0 543--547, 1983

    1983

  42. [50]

    Lectures on Convex Optimization, volume 137

    Yurii Nesterov. Lectures on Convex Optimization, volume 137. Springer, 2018

    2018

  43. [51]

    Oppenheim, Alan S

    Alan V. Oppenheim, Alan S. Willsky, and Syed Hamid Nawab. Signals and Systems. Pearson, 1996

    1996

  44. [52]

    4+3 phases of compute-optimal neural scaling laws

    Elliot Paquette, Courtney Paquette, Lechao Xiao, and Jeffrey Pennington. 4+3 phases of compute-optimal neural scaling laws. In Advances in Neural Information Processing Systems, 2024

    2024

  45. [53]

    Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes

    Loucas Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. In Advances in Neural Information Processing Systems, 2018

    2018

  46. [54]

    Polyak and Anatoli B

    Boris T. Polyak and Anatoli B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30 0 (4): 0 838--855, 1992

    1992

  47. [55]

    Integration methods and optimization algorithms

    Damien Scieur, Vincent Roulet, Francis Bach, and Alexandre d'Aspremont. Integration methods and optimization algorithms. Advances in Neural Information Processing Systems, 2017

    2017

  48. [56]

    Dirk T. M. Slock. On the convergence behavior of the LMS and the normalized LMS algorithms. IEEE Transactions on Signal processing, 41 0 (9): 0 2811--2825, 1993

    1993

  49. [57]

    Weijie Su, Stephen Boyd, and Emmanuel J. Candes. A differential equation for modeling N esterov's accelerated gradient method: Theory and insights. Journal of Machine Learning Research, 17 0 (153): 0 1--43, 2016

    2016

  50. [58]

    Taylor, Julien M

    Adrien B. Taylor, Julien M. Hendrickx, and Fran c ois Glineur. Exact worst-case performance of first-order methods for composite convex optimization. SIAM Journal on Optimization, 27 0 (3): 0 1283--1313, 2017

    2017

  51. [59]

    Van der Vaart

    Aad W. Van der Vaart. Asymptotic Statistics, volume 3. Cambridge University Press, 2000

    2000

  52. [60]

    Accelerated SGD for non-strongly-convex least squares

    Aditya Varre and Nicolas Flammarion. Accelerated SGD for non-strongly-convex least squares. In Conference on Learning Theory, 2022

    2022

  53. [61]

    Last iterate convergence of SGD for least-squares in the interpolation regime

    Aditya Vardhan Varre, Loucas Pillaud-Vivien, and Nicolas Flammarion. Last iterate convergence of SGD for least-squares in the interpolation regime. Advances in Neural Information Processing Systems, 2021

    2021

  54. [62]

    Tight convergence rate bounds for optimization under power law spectral conditions

    Maksim Velikanov and Dmitry Yarotsky. Tight convergence rate bounds for optimization under power law spectral conditions. Journal of Machine Learning Research, 25 0 (81): 0 1--78, 2024

    2024

  55. [63]

    A view of mini-batch SGD via generating functions: conditions of convergence, phase transitions, benefit from negative momenta

    Maksim Velikanov, Denis Kuznedelev, and Dmitry Yarotsky. A view of mini-batch SGD via generating functions: conditions of convergence, phase transitions, benefit from negative momenta. In International Conference on Learning Representations, 2023

    2023

  56. [64]

    Wilson, and Michael I

    Andre Wibisono, Ashia C. Wilson, and Michael I. Jordan. A variational perspective on accelerated methods in optimization. Proceedings of the National Academy of Sciences, 113 0 (47): 0 E7351--E7358, 2016

    2016

  57. [65]

    Laplace Transform

    David Vernon Widder. Laplace Transform. Princeton University Press, 1942

    1942

  58. [66]

    Herbert S. Wilf. Generatingfunctionology. CRC Press, 2005

    2005

Pith tools

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