# On the Convergence Rate of Incremental Aggregated Gradient Algorithms

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

## Key facts

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

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

- [Random Reshuffling with Variance Reduction: New Analysis and Better Rates](https://mlsanity.com/paper/2104.09342/) (2021)
- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orders](https://mlsanity.com/paper/2104.12112/) (2021)
- [Delay-adaptive step-sizes for asynchronous learning](https://mlsanity.com/paper/2202.08550/) (2022)
- [Random-reshuffled SARAH does not need a full gradient computations](https://mlsanity.com/paper/2111.13322/) (2021)
- [Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling](https://mlsanity.com/paper/2402.11800/) (2024)
- [Robust Distributed Optimization With Randomly Corrupted Gradients](https://mlsanity.com/paper/2106.14956/) (2021)
- [Linear Speedup of Incremental Aggregated Gradient Methods on Streaming Data](https://mlsanity.com/paper/2309.04980/) (2023)
- [Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity](https://mlsanity.com/paper/2509.22860/) (2025)
- [Cyclic Coordinate Dual Averaging with Extrapolation](https://mlsanity.com/paper/2102.13244/) (2021)
- [Temporal Predictive Coding for Gradient Compression in Distributed Learning](https://mlsanity.com/paper/2410.02478/) (2024)
- [Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shuffling](https://mlsanity.com/paper/2502.14648/) (2025)
- [Min-Max Optimization under Delays](https://mlsanity.com/paper/2307.06886/) (2023)
- [Dual-Delayed Asynchronous SGD for Arbitrarily Heterogeneous Data](https://mlsanity.com/paper/2405.16966/) (2024)
- [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)
- [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)
- [Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guarantees](https://mlsanity.com/paper/2509.04133/) (2025)
- [A Short and Unified Convergence Analysis of the SAG, SAGA, and IAG Algorithms](https://mlsanity.com/paper/2602.05304/) (2026)
- [Incremental Aggregation on the Grassmannian for Asynchronous Eigenspace Computation](https://mlsanity.com/paper/2608.04406/) (2026)

## Abstract (arXiv)

Motivated by applications to distributed optimization over networks and large-scale data processing in machine learning, we analyze the deterministic incremental aggregated gradient method for minimizing a finite sum of smooth functions where the sum is strongly convex. This method processes the functions one at a time in a deterministic order and incorporates a memory of previous gradient values to accelerate convergence. Empirically it performs well in practice; however, no theoretical analysis with explicit rate results was previously given in the literature to our knowledge, in particular most of the recent efforts concentrated on the randomized versions. In this paper, we show that this deterministic algorithm has global linear convergence and characterize the convergence rate. We also consider an aggregated method with momentum and demonstrate its linear convergence. Our proofs rely on a careful choice of a Lyapunov function that offers insight into the algorithm's behavior and simplifies the proofs considerably.