# Convergence Rate of Incremental Gradient and Newton Methods

arXiv: https://arxiv.org/abs/1510.08562 · HTML: https://mlsanity.com/paper/1510.08562/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2015.

## Built on by (most cited first, 27 of 27)

- [On the Convergence of Federated Averaging with Cyclic Client Participation](https://mlsanity.com/paper/2302.03109/) (2023)
- [Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms](https://mlsanity.com/paper/2106.04881/) (2021)
- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (2023)
- [Random Reshuffling with Variance Reduction: New Analysis and Better Rates](https://mlsanity.com/paper/2104.09342/) (2021)
- [GraB: Finding Provably Better Data Permutations than Random Reshuffling](https://mlsanity.com/paper/2205.10733/) (2022)
- [Permutation-Based SGD: Is Random Optimal?](https://mlsanity.com/paper/2102.09718/) (2021)
- [Convergence of Random Reshuffling Under The Kurdyka-Lojasiewicz Inequality](https://mlsanity.com/paper/2110.04926/) (2021)
- [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024)
- [Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization](https://mlsanity.com/paper/2206.02953/) (2022)
- [Coordinating Distributed Example Orders for Provably Accelerated Training](https://mlsanity.com/paper/2302.00845/) (2023)
- [On Convergence of Incremental Gradient for Non-Convex Smooth Functions](https://mlsanity.com/paper/2305.19259/) (2023)
- [Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds](https://mlsanity.com/paper/2306.12498/) (2023)
- [Reawakening knowledge: Anticipatory recovery from catastrophic interference via structured training](https://mlsanity.com/paper/2403.09613/) (2024)
- [Multi-Model Federated Learning with Provable Guarantees](https://mlsanity.com/paper/2207.04330/) (2022)
- [High Probability Guarantees for Random Reshuffling](https://mlsanity.com/paper/2311.11841/) (2023)
- [Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data](https://mlsanity.com/paper/2405.19463/) (2024)
- [Improving Classifier-Free Guidance of Flow Matching via Manifold Projection](https://mlsanity.com/paper/2601.21892/) (2026)
- [Finite-Sum Optimization: A New Perspective for Convergence to a Global Solution](https://mlsanity.com/paper/2202.03524/) (2022)
- [Understanding the Training Speedup from Sampling with Approximate Losses](https://mlsanity.com/paper/2402.07052/) (2024)
- [A Generalized Version of Chung's Lemma and its Applications](https://mlsanity.com/paper/2406.05637/) (2024)
- [Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Bounds](https://mlsanity.com/paper/2509.13628/) (2025)
- [Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothness](https://mlsanity.com/paper/2212.01848/) (2022)
- [Ordering for Non-Replacement SGD](https://mlsanity.com/paper/2306.15848/) (2023)
- [Corgi^2: A Hybrid Offline-Online Approach To Storage-Aware Data Shuffling For SGD](https://mlsanity.com/paper/2309.01640/) (2023)
- [Beyond adaptive gradient: Fast-Controlled Minibatch Algorithm for large-scale optimization](https://mlsanity.com/paper/2411.15795/) (2024)
- [Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weighting](https://mlsanity.com/paper/2506.12444/) (2025)
- [Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent](https://mlsanity.com/paper/2610.19444/) (2026)

## Abstract (arXiv)

The incremental gradient method is a prominent algorithm for minimizing a finite sum of smooth convex functions, used in many contexts including large-scale data processing applications and distributed optimization over networks. It is a first-order method that processes the functions one at a time based on their gradient information. The incremental Newton method, on the other hand, is a second-order variant which exploits additionally the curvature information of the underlying functions and can therefore be faster. In this paper, we focus on the case when the objective function is strongly convex and present fast convergence results for the incremental gradient and incremental Newton methods under the constant and diminishing stepsizes. For a decaying stepsize rule αk = Theta(1/ks) with s ∈ (0,1], we show that the distance of the IG iterates to the optimal solution converges at rate cal O(1/ks) (which translates into cal O(1/k2s) rate in the suboptimality of the objective value). For s>1/2, this improves the previous cal O(1/√k) results in distances obtained for the case when functions are non-smooth. We show that to achieve the fastest cal O(1/k) rate, incremental gradient needs a stepsize that requires tuning to the strong convexity parameter whereas the incremental Newton method does not. The results are based on viewing the incremental gradient method as a gradient descent method with gradient errors, devising efficient upper bounds for the gradient error to derive inequalities that relate distances of the consecutive iterates to the optimal solution and finally applying Chung's lemmas from the stochastic approximation literature to these inequalities to determine their asymptotic behavior. In addition, we construct examples to show tightness of our rate results.