DSA: Decentralized Double Stochastic Averaging Gradient Algorithm

By Aryan Mokhtari, Alejandro Ribeiro. 2015

171 citations recorded by the source corpus.

This paper considers optimization problems where nodes of a network have access to summands of a global objective. Each of these local objectives is further assumed to be an average of a finite set of functions. The motivation for this setup is to solve large scale machine learning problems where elements of the training set are distributed to multiple computational elements. The decentralized double stochastic averaging gradient (DSA) algorithm is proposed as a solution alternative that relies on: (i) The use of local stochastic averaging gradients. (ii) Determination of descent steps as differences of consecutive stochastic averaging gradients. Strong convexity of local functions and Lipschitz continuity of local gradients is shown to guarantee linear convergence of the sequence generated by DSA in expectation. Local iterates are further shown to approach the optimal argument for almost all realizations. The expected linear convergence of DSA is in contrast to the sublinear rate characteristic of existing methods for decentralized stochastic optimization. Numerical experiments on a logistic regression problem illustrate reductions in convergence time and number of feature vectors processed until convergence relative to these other alternatives.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications, Optimization & Training, Federated & Distributed Learning

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

In Computational Mechanics

In Computer Networks and Communications

In Optimization & Training

In Federated & Distributed Learning

Citations in the corpus

Robust and Communication-Efficient Collaborative Learning (2019, methodology): “, 2016; Qu and Li, 2017), augmented Lagrangian algorithms (Shi et al., 2015a,b; Mokhtari and Ribeiro, 2016), distributed variants of the alternating direction method of multipliers (ADMM) (Schizas et al.”
COLA: Decentralized Linear Learning (2018, neutral): “In contrast, a second more recent line of work [Nedic and Ozdaglar, 2009, Duchi et al., 2012, Shi et al., 2015, Mokhtari and Ribeiro, 2016, Nedic et al., 2017, Scaman et al., 2017, 2018] considers minimization of a sum of individual local cost-functions F ( x ) = i F i ( x ) , which are potentially…”
D2: Decentralized Training over Decentralized Data (2018, methodology): “The DSA algorithm [Mokhtari and Ribeiro, 2016] applies the variance reduction similar to SAGA on strongly convex decentralized optimization problems and proved a linear convergence rate.”
Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, background): “(Mokhtari and Ribeiro, 2016) proposed a fast decentralized variance reduced algorithm for strongly convex optimization problems.”
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks (2018, background): “Many algorithms were proposed to solve the decentralized optimization of an average of functions (see for example [1, 11, 3, 4, 12, 2, 13, 5]), and a sheer amount of work was devoted to improving the convergence rate of these algorithms [5, 6].”
Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks (2017, methodology): “More recently, a number of methods with provable linear convergence rates were developed, including EXTRA [4, 11], augmented Lagrangians [6], and more recent approaches [7].”
Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication (2018, methodology): “DSA converges linearly, while the overall required complexity heavily depends on function and graph condition numbers.”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, background): “Similar connections between the EXTRA algorithm and a general primal-dual have been made in a few recent references, [35], [33], and [24].”
Variance Reduced Local SGD with Lower Communication Complexity (2019, background): “In recent years, several studies [Shi et al., 2015, Mokhtari and Ribeiro, 2016, O ( N ) NO Tang et al., 2018] have proposed to eliminate the gradient variance among workers in the decentralized setting.”
A survey of distributed optimization (2019, methodology): “The primal-dual interpretation of the EXTRA has been offered in Mokhtari and Ribeiro (2016) and Mokhtari, Shi, Ling, and Ribeiro (2016) based on the augmented Lagrangian function.”
Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks (2019, methodology): “as explicit characterization of Fenchel dual of the local objective functions, referred to as dualable setting as in Scaman et al. (2018); Uribe et al. (2018)).”
Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up (2019, background): “Since the early works [52, 53] to the more recent work [22, 34, 33, 23, 29, 30, 10, 18, 47, 31], problems in decentralised multi-agent optimisation have often been treated as a particular instance of consensus optimisation.”
Asynchronous Decentralized Online Learning (2021, background): “Learner i t receives a convex function f t from environment, and suffers the loss f t ( w i t ( t )) .”
Optimal Convergence Rates for Convex Distributed Optimization in Networks (2019, unknown): “This approach was shown to be robust against machine failures, non-uniform latencies and asynchronous or time-varying graphs, and a large body of literature extended this algorithm to distributed optimization (Nedic and Ozdaglar, 2009; Duchi et al., 2012a; Wei and Ozdaglar, 2012; Shi et al., 2015; J”
Data-Dependent Convergence for Consensus Stochastic Optimization (2016, methodology): “More sophisticated gradient averaging schemes such as that of Mokhtari and Ribeiro [17] can exploit dependence across iterations [18, 19] to improve the convergence rate; analyzing the impact of the data distribution is considerably more complex in these algorithms.”