A Convergent Incremental Gradient Method with a Constant Step Size

By Doron Blatt, A. Hero, Hillel Gauchman. 2007

317 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computer Networks and Communications, Electrical and Electronic Engineering, Optimization & Training

How researchers see this paper

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

In Computational Mechanics

In Computer Networks and Communications

In Electrical and Electronic Engineering

In Optimization & Training

Citations in the corpus

Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods (2013, background): “This contrasts with the cyclic choice of subfunction in (Blatt et al., 2007), and the random choice of subfunction in (Roux et al., 2012).”
Optimization Methods for Large-Scale Machine Learning (2016, methodology): “unbiased estimator of rR n(w k), the method enjoys a linear rate of convergence. One nds that the SAG algorithm is a randomized version of the Incremental Aggregated Gradient (IAG) method proposed in [17] and analyzed in [72], where the index jof the component function updated at every iteration is ”
Minimizing finite sums with the stochastic average gradient (2013, methodology): “[5] present the most closely-related algorithm to the SAG algorithm, the IAG method.”
GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, background): “• Cycle-IAG (Blatt et al., 2007; Gurbuzbalaban et al., 2017): A cyclic modiﬁed version of the incremental aggregated gradient (IAG).”
Hybrid Deterministic-Stochastic Methods for Data Fitting (2011, background): “The works of Bertsekas [2] and Blatt, Hero, and Gauchman [6] are the closest in spirit to our proposed approach.”
A Proximal Stochastic Gradient Method with Progressive Variance Reduction (2014, methodology): “The SAG method is a randomized variant of the incremental aggregated gradient method of Blatt, Hero, and Gauchman [5] and needs to store the most recent gradient for each component function fi, which is O(nd).”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, methodology): “The method SAG [44] for smooth unconstrained convex optimization is a randomized variant of the incremental gradient descent algorithm of Blatt, Hero and Gauchman [5], where an estimate of the gradient ∇ f is incrementally updated at each iteration. optimization The method SDCA [45] for strongly con”
Fast Distributed Gradient Methods (2011, methodology): “In fact, algorithms distributed Nesterov gradient and distributed Nesterov+consensus offer two different ways to control δ k ’s. distributed Nesterov gradient does this through a diminishing step-size α k , while D–NC uses the inner consensus iterations (while using the constant step size α k = α ).”
Tracking Moving Agents via Inexact Online Gradient Descent Algorithm (2017, methodology): “Since calculating an approximate gradient is often cheap, recent years have witnessed the development of several variants, such as the incremental aggregated gradient method [25], stochastic average gradient method [26], [27], stochastic variance reduced gradient method [28], SAGA [29].”
Distributed multi-task classification: a decentralized online learning approach (2017, methodology): “Incremental methods [5,7,25] require the network to form a special ring and transmit the updated information through a cyclic trajectory one after the other, while consensus methods [14,19,23] require each node to perform two updating steps: it first aggregates the iterates from its direct neighbors”
On Analog Gradient Descent Learning Over Multiple Access Fading Channels (2019, methodology): “3) Comparison With Distributed Learning and SGD Based Algorithms: Exisitng distributed learning methods, the IAG [1] and ICAG [45], attain linear convergence rate.”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, unknown): “[13].”
Distributed learning with compressed gradients (2018, background): “Under the assumption of bounded staleness, τ ik ≤ τ for all k, i , convergence guarantees for IAG have been established for several classes of loss functions, see e.g. [6–9].”