On the Convergence Rate of Incremental Aggregated Gradient Algorithms

By Mert Gurbuzbalaban, Asuman E. Ozdaglar, Pablo A. Parrilo. 2015

151 citations recorded by the source corpus.

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 we 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 pro...

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Wei Shi
2. Angelia Nedić
3. Aryan Mokhtari
4. Peter Richtárik
5. Nicolas Loizou
6. Michael G. Rabbat
7. Medhi Bennis
8. Alexander Olshevsky

In Computational Mechanics

1. Aryan Mokhtari
2. Alexander Olshevsky
3. Wei Shi
4. Angelia Nedić
5. Nicolas Loizou
6. Alejandro Ribeiro
7. Medhi Bennis
8. Peter Richtárik

Citations in the corpus

• GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, background): “• Cycle-IAG (Blatt et al., 2007; Gurbuzbalaban et al., 2017): A cyclic modified version of the incremental aggregated gradient (IAG).”
• Communication-efficient algorithms for decentralized and stochastic optimization (2017, positive): “n [60,59] has been followed by distributed incremental (sub)gradient methods and proximal methods [36,48,2,61], and more recently the incremental aggregated gradient methods and its proximal variants [18,3,26]. All of these incremental methods are not fully decentralized in a sense that they require”
• Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, methodology): “Some earlier methods include distributed incremental (sub)gradient methods [37–39,54] and incremental proximal methods [3, 68], while a more recent work includes incremental aggregated gradient methods [23] and its proximal gradient variants [4].”
• IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Rate (2017, methodology): “The work in [26] suggests a random selection of functions which leads to stochastic average gradient method (SAG), while the works in [1, 11, 17] use a cyclic scheme for choosing the functions.”
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “Thus, the convergence analysis of [77] can not be directly applied to our problem.”
• Distributed learning with compressed gradients (2018, result): “Letting α = 1 in our analysis yields a slightly better step size than the one presented in [7].”
• Coresets for Data-efficient Training of Machine Learning Models (2019, background): “However, in practice, the convergence rate of IG is known to be quite sensitive to the order of processing the functions (Bertsekas, 2015a; Gurbuzbalaban et al., 2017).”