Research map / Optimization / Nonconvex and smooth optimization
Gradient correlation is a key ingredient to accelerate SGD with momentum
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.
Shows that average positive correlation between per-sample gradients yields a tight strong growth condition constant, making stochastic Nesterov (SNAG) accelerate over SGD in convex and neural network settings.
Problem
Whether SGD with Nesterov-style momentum (SNAG) can provably accelerate over SGD under interpolation/strong growth in convex settings, given prior pessimism and the lack of characterization of the strong growth constant.
Approach
Characterizes the strong growth condition constant rho_K through the average correlation between per-sample gradients (PosCorr and the relaxed RACOGA condition), showing rho_K = N/K under positive average correlation and bounding rho_K for larger batches, which yields finite-time and asymptotic acceleration bounds for SNAG over SGD.
Key results
- On the sphere MLP, SNAG reaches 88.73% test accuracy versus 80.6% for SGD and 49.72% for GD.
- On CIFAR10 CNN, SNAG reaches 70.88% test accuracy versus 65.40% for SGD.
- Theory: under average positive gradient correlation, the strong growth constant satisfies rho_K = N/K, improving on the L_(K)/mu bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SNAG instead of SGD | MLP classifier · SPHERE | test accuracy (%): 80.6 -> 88.73 | Helped |
| Use SNAG instead of SGD | CNN classifier · CIFAR10 | test accuracy (%): 65.40 -> 70.88 | Helped |
| Use SNAG instead of ADAM | MLP classifier · SPHERE | convergence speed | Hurt |
| Use SNAG instead of RMSprop | MLP classifier · SPHERE | convergence speed | Hurt |
| Use SNAG instead of ADAM | CNN classifier · CIFAR10 | convergence speed | Helped |
| Use SNAG instead of RMSprop | CNN classifier · CIFAR10 | convergence speed | Helped |
| Increase batch size from 1 to 10 | SNAG on correlated linear-regression data · Linear regression, correlated data | convergence performance | No clear effect |
| Increase batch size from 10 to 25 | SNAG on correlated linear-regression data · Linear regression, correlated data | convergence performance | Hurt |
| Increase batch size | SNAG on uncorrelated linear-regression data · Linear regression, uncorrelated data | convergence performance | Helped |
| Use SNAG instead of SGD | Logistic regression on CIFAR10 images · CIFAR10 logistic regression, under- and over-parameterized | convergence speed | No clear effect |
Surprising findings
- Uncorrelated (isotropic) data make all stochastic methods perform poorly relative to deterministic NAG, while correlated data reverse this.
- Logistic regression on CIFAR10 shows no acceleration of SNAG over SGD because RACOGA values are small.
Limitations
- Theory covers convex sums of functions; experiments on neural networks are non-convex and outside the theoretical setting.
- The rho_K constant is hard to compute, so SNAG parameters are tuned via a lambda surrogate or grid search.
Experimental setup
Datasets: CIFAR10 MNIST FashionMNIST KMNIST EMNIST Boston housing
Benchmarks: CIFAR10 SPHERE MNIST FashionMNIST KMNIST EMNIST Boston housing
Metrics: training loss vs number of gradient evaluations test accuracy RACOGA value along optimization path
Baselines: SGD GD NAG RMSprop ADAM
Builds on: Nesterov accelerated gradient strong growth condition (Schmidt and Le Roux) Stochastic Nesterov accelerated gradient (Aybat et al.) gradient diversity gradient confusion
Closest papers by meaning
- The Marginal Value of Momentum for Small Learning Rate SGD (ICLR 2024 · similarity 0.91)
- Random Scaling and Momentum for Non-smooth Non-convex Optimization (ICML 2024 · similarity 0.90)
- Perfect Parallelization in Mini-Batch SGD with Classical Momentum Acceleration (NeurIPS 2026 · similarity 0.90)
- Nesterov acceleration in benignly non-convex landscapes (ICLR 2025 · similarity 0.89)
- Dimension-adapted Momentum Outscales SGD (NeurIPS 2025 · similarity 0.89)
- Convergence of Clipped SGD on Convex $(L_0,L_1)$-Smooth Functions (NeurIPS 2025 · similarity 0.89)
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.