Research map / Optimization / Nonconvex and smooth optimization
Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
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.
Studies incremental gradient descent (IGD) in the small epoch regime (K ≲ κ) and proves lower bounds showing it can be surprisingly slow on strongly convex and especially nonconvex-component problems, plus tight bounds for large epochs and an existence result for a permutation beating with-replacement SGD.
Problem
Convergence of permutation-based SGD when the number of epochs K is smaller than the condition number κ; it is open whether permutation-based methods can beat with-replacement SGD in this small epoch regime.
Approach
Derives lower bounds for deterministic IGD under three component assumptions (shared Hessian, strongly convex components, nonconvex components with bounded gradient errors), shows nonconvex components cause exponential slowdown in K/κ, and uses herding on gradients at the optimum to construct a fixed permutation that outperforms with-replacement SGD.
Key results
- For IGD with K ≤ κ/2 and strongly convex components sharing a Hessian, the optimality gap is at least Ω(G²/(μK)) for any constant step size.
- With nonconvex components (P=3), the IGD optimality gap is lower-bounded by min{μD², (G²/L)(1+L/(2μnK))^n}, growing exponentially in κ/K.
- A herding-based fixed permutation achieves ||x_n^K − x*||² ≲ H²LG*²/(μ³n²K²), which can beat with-replacement SGD's G²/(μnK) when n ≥ H²κ²/K.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Remove the identical-Hessian assumption while keeping all component functions strongly convex | IGD in the small epoch regime · Small epoch, strongly convex components | function optimality gap lower bound: \Omega\left(\frac{G^2}{\mu K}\right) -> \Omega\left(\frac{L G^2}{\mu^2} \min\{1, \frac{L^2}{\mu^2 K^4}\}\right) | Hurt |
| Allow some component functions to be nonconvex instead of requiring strongly convex components | IGD in the small epoch regime · Small epoch, potentially nonconvex components | function optimality gap lower bound: \Omega\left(\frac{G^2}{L} \left(1 + \frac{L}{2 \mu n K}\right)^{n}\right) | Hurt |
| Allow some component functions to be nonconvex instead of requiring convex components | IGD in the large epoch regime · Large epoch, potentially nonconvex components | function optimality gap lower bound: \Omega\left(\frac{L G^2}{\mu^2 K^2}\right) -> \Omega\left(\frac{L^2 G^2}{\mu^3 K^2}\right) | Hurt |
Surprising findings
- Even with all components strongly convex, IGD's small-epoch convergence can be far slower than expected, and adding nonconvex components slows it exponentially in κ/K.
- Theory suggests IGD's small-epoch lower bound barrier can be surpassed by a well-chosen fixed permutation, unlike RR which cannot beat with-replacement SGD in this regime.
Limitations
- The herding-based permutation requires knowledge of component gradients at the optimum and is not practically implementable.
- Gap of H²κ remains between the herding upper bound and the IGD lower bound; RR tight small-epoch bounds remain open.
Experimental setup
Metrics: function optimality gap
Baselines: random reshuffling with-replacement SGD GraB single shuffling
Builds on: random reshuffling GraB herding
Closest papers by meaning
- Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective (NeurIPS 2024 · similarity 0.91)
- On Convergence of Incremental Gradient for Non-convex Smooth Functions (ICML 2024 · similarity 0.91)
- A Unified Analysis of Stochastic Gradient Descent with Arbitrary Data Permutations and Beyond (NeurIPS 2025 · similarity 0.89)
- Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime (NeurIPS 2025 · similarity 0.89)
- Gradient correlation is a key ingredient to accelerate SGD with momentum (ICLR 2025 · similarity 0.88)
- Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent (ICML 2025 · similarity 0.88)
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.