Research map / Optimization / Nonconvex and smooth optimization
On Convergence of Incremental Gradient for Non-convex Smooth Functions
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.
Gives a new analysis of SGD under arbitrary data orderings for non-convex smooth functions, improving incremental gradient and single shuffle convergence by a factor n in the optimization term.
Problem
Convergence theory for incremental gradient and shuffle-based SGD (with fixed or permuted data orders) on non-convex smooth finite-sum objectives is weak; prior IG/SS rates scale linearly with dataset size n in the optimization term.
Approach
Introduces a sequence-correlation variance measured over adaptively sized correlated periods tau = Theta(1/(L gamma)) rather than fixed size n, which removes the stepsize restriction gamma < O(1/(Ln)) and yields O(1/eps) optimization term for IG/SS.
Key results
- For IG/SS the optimization term improves from O(n/eps) to O(1/eps), with stochastic term min{n sigma_SGD/eps, n sigma_SGD^2/eps^2}-type bound.
- With tuned stepsize, IG/SS rate O(LF_0/T + min{(LF_0 n sigma/T)^{2/3}, sqrt(LF_0 n sigma/T)}) strictly improves prior O(LF_0 n/T + (LF_0 n sigma/T)^{2/3}).
- Experiments show RR and SS outperform SGD on quadratics, logistic regression, and neural networks; on CIFAR, SS performs best.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the adaptive correlation period τ = Θ(1/(Lγ)) instead of fixing τ = n | Incremental Gradient / Single Shuffle · Non-convex smooth finite-sum optimization | iterations to achieve accuracy ε: O(n/ε) -> O(1/ε) | Helped |
| Use the proposed analysis for Incremental Gradient / Single Shuffle | Incremental Gradient / Single Shuffle · Non-convex smooth finite-sum optimization | iterations to achieve accuracy ε: L F_0 · O(n/ε + nσ_SGD/ε) -> L F_0 · O(1/ε + min{n σ_SGD/ε, n σ²_SGD/ε²}) | Helped |
| Use the proposed analysis for Random Reshuffling | Random Reshuffling · Non-convex smooth finite-sum optimization | convergence rate: O(L F_0 n/T + (L F_0 √n σ_SGD/T)^(2/3)) -> O(L F_0/T + min{(L F_0 n σ_SGD/T)^(2/3), √(L F_0 n σ_SGD/T)}) | Mixed |
| Use shuffle sampling instead of sampling with replacement | SGD · Synthetic quadratic objectives | convergence | Helped |
| Use Random Reshuffling or Single Shuffle instead of sampling with replacement | SGD · Logistic regression on LibSVM datasets | full gradient norm convergence | Helped |
| Use Random Reshuffling instead of sampling with replacement | SGD · MNIST neural network, subset of size 1000 | full gradient norm convergence | Mixed |
| Use Single Shuffle instead of sampling with replacement | SGD · CIFAR ResNet-18 | training performance | Helped |
Surprising findings
- Single-function ordering (always sampling f_1) converges to a neighbourhood of size sigma_1^2 that cannot be reduced, showing the framework is tight in that case.
Limitations
- Random reshuffling rate still has an n factor in the first optimization term, which remains open.
- Analysis uses simplified constants and assumes finite sequence variance over correlated periods.
Experimental setup
Datasets: MNIST CIFAR LibSVM (ionosphere, breast-cancer, a9a, w1a, rcv1, Australian) synthetic quadratics
Benchmarks: MNIST subset CIFAR LibSVM logistic regression datasets synthetic quadratics
Metrics: full gradient norm iterations to reach target gradient norm
Baselines: SGD with replacement Random Reshuffling Single Shuffle prior IG/SS rates (Mishchenko et al. 2020; Nguyen et al. 2021)
Builds on: SGD with random reshuffling analyses perturbed iterate analysis SGD with linearly correlated noise (differential privacy)
Closest papers by meaning
- Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems (ICML 2025 · similarity 0.91)
- Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective (NeurIPS 2024 · similarity 0.90)
- Convergence of Clipped SGD on Convex $(L_0,L_1)$-Smooth Functions (NeurIPS 2025 · similarity 0.89)
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.88)
- Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness (ICML 2025 · similarity 0.88)
- Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization (ICML 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.