Research map / Optimization / Optimizers
SGD with memory: fundamental properties and stochastic acceleration
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces memory-M first-order algorithms for quadratic mini-batch SGD, derives a propagator expansion of the loss, and proposes a memory-1 schedule (AM1) that heuristically accelerates SGD's power-law loss exponent beyond plain SGD.
Problem
Accelerating mini-batch SGD-type algorithms on quadratic problems with power-law spectrum: Heavy Ball with Jacobi schedules accelerates noiseless GD but diverges under mini-batch noise.
Approach
Define memory-M algorithms with M auxiliary velocity vectors, show equivalence to multistep recurrences via characteristic polynomials, derive a signal/noise propagator loss expansion, and identify a memory-1 region with arbitrarily large effective learning rate that remains stable, enabling a power-law schedule.
Key results
- Stationary stable memory-M SGD keeps the plain-GD exponent zeta in signal-dominated regime, with constant C_L depending on effective learning rate.
- In memory-1 algorithms the effective learning rate can be made arbitrarily large while maintaining stability, so C_L can be made arbitrarily small.
- The proposed AM1 schedule heuristically reaches L_t = O(t^{-zeta(1+alpha_bar)}), up to O(t^{-zeta(2-1/nu)}), improving on plain SGD's O(t^{-zeta}); confirmed experimentally on MNIST and synthetic problems.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the time-dependent accelerated memory-1 (AM1) schedule instead of stationary SGD | SGD with memory on power-law quadratic problems · signal-dominated regime | loss convergence rate: O(t^{-\zeta}) -> O(t^{-\zeta(2-\frac{1}{\nu})}) | Helped |
| increase the effective learning rate while maintaining stability | stationary memory-M SGD · signal-dominated regime | loss asymptotic constant | Helped |
| use stationary memory-M algorithms rather than plain GD | SGD with memory · power-law spectrum, signal- and noise-dominated regimes | loss convergence exponent | No clear effect |
| use a nonzero gradient shift a instead of a=0 (ablation) | memory-1 SGD on quadratic problems · quadratic problems with mini-batch noise | loss convergence | No clear effect |
Surprising findings
- Nonzero shift parameter a (Nesterov/averaging-type gradient shifts) was not found useful for quadratic problems with mini-batch noise.
Limitations
- Acceleration O(t^{-zeta(2-1/nu)}) is only heuristic; rigorous proof is open.
- Analysis restricted to quadratic losses and the spectrally expressible approximation of noise covariance.
- Larger memory sizes M not explored for further improvement.
Experimental setup
Datasets: MNIST synthetic power-law quadratic problems
Benchmarks: MNIST synthetic power-law quadratic problems
Metrics: loss L_t convergence exponent
Baselines: plain SGD SGD with momentum Jacobi-scheduled Heavy Ball
Builds on: Heavy Ball Jacobi-scheduled heavy ball spectrally expressible approximation
Closest papers by meaning
- Asymptotic theory of SGD with a general learning-rate (NeurIPS 2025 · similarity 0.89)
- First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noise (NeurIPS 2019 · similarity 0.89)
- Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noise (ICLR 2024 · similarity 0.89)
- Perfect Parallelization in Mini-Batch SGD with Classical Momentum Acceleration (NeurIPS 2026 · similarity 0.88)
- Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems (ICML 2025 · similarity 0.87)
- Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.