Distributed Asynchronous Incremental Subgradient Methods

By Angelia Nedić, Dimitri P. Bertsekas, Vivek Shripad Borkar. 2001

187 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Numerical Analysis, 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 Theory and Mathematics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, background): “[18] A Nedić, Dimitri P Bertsekas, and Vivek S Borkar.”
Deep learning with Elastic Averaging SGD (2014, methodology): “Since, as opposed to other popular approaches focusing on distributed optimization (e.g. Azadi & Sra (2014); Nedić et al. (2001)), we allow the workers to fluctuate further from the center performing the exploration of the space (as we do not split the data among the workers), the form of our…”
Optimal Distributed Online Prediction Using Mini-Batches (2010, background): “There have been extensive studies on distributed optimization with inaccurate or delayed subgradient information, but mostly without the smoothness assumption (e.g., Nedi´c et al., 2001; Nedi´c and Ozdaglar, 2009).”
Distributed delayed stochastic optimization (2011, background): “Master-worker architectures are natural for distributed computation, and other researchers have considered models similar to those in this paper [12, 10].”
Communication-efficient algorithms for decentralized and stochastic optimization (2017, positive): “recent years due to the emergence of large-scale networks. The seminal work on distributed optimization [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 variant”
On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants (2015, background): “Within asynchronous SGD algorithms, both parallel [20] and distributed [2, 16] variants are known.”
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 incremental proximal methods [ 3 , 68] , while a more recent Some distributed methods exist that do not (explicitly) use dual variables but can still converge to an exact consensual solution…”
Simultaneous routing and resource allocation via dual decomposition (2004, background): “However, asynchronous distributed algorithms exist for solving the routing and resource allocation subproblems, as well as for solving the master dual problem [30].”
A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates (2018, background): “Moving closer to our setting, [15] showed convergence for delayed gradient descent, with the result implying an √ τ/k convergence rate for convex functions.”
Distributed Asynchronous Online Learning for Natural Language Processing (2010, methodology): “An asynchronous framework may use multiple processors more efficiently and minimize idle time (Nedic et al., 2001; Langford et al., 2009).”
Asynchronous Saddle Point Algorithm for Stochastic Optimization in Heterogeneous Networks (2019, background): “Assumption 6 ensures that the delay is always bounded by τ , which holds in most wireless communications problems and autonomous multi-agent networks [45].”
A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates (2017, background): “The incremental algorithms [3,17–19,31,42] can solve (1) without the need of a “master” agent but requires that the network contains a ring structure.”
Asynchronous stochastic gradient descent for DNN training (2013, background): “A proof about the convergence of ASGD is given in [9].”
Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods (2008, methodology): “Numerous extensions and implementations including parallel and incremental versions have been proposed and analyzed (for example, see Kiwiel and Lindberg [10], Zhao, Luh and Wang [27], Ben-Tal, Margalit and Nemirovski [2], Nedić and Bertsekas [16], [17], Nedić, Bertsekas and Borkar [18]).”
A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach (2014, result): “In [4], an incremental and asynchronous gradient-based algorithm is proposed to solve a convex problem, where at each step certain outdated gradients can be used for update.”
A gossip algorithm for convex consensus optimization over networks (2010, background): “Furthermore, the algorithms mostly assume delay- and error-free communications with no quantization over directed graphs, although there are a few exceptions: [18] allowed the presence of bounded time delays, [28] considered random additive errors in subgradient evaluations, [20], [26] studied the e”
On stochastic gradient and subgradient methods with adaptive steplength sequences (2011, background): “In deterministic regimes, subgradient methods and their incremental variants have proved popular (see [26], [27], [60]), as have bundle methods [61], amongst others.”