Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization

By Sundhar Srinivasan Ram, Angelia Nedić, Venugopal V. Veeravalli. 2008

876 citations recorded by the source corpus.

We consider a distributed multi-agent network system where the goal is to minimize a sum of convex objective functions of the agents subject to a common convex constraint set. Each agent maintains an iterate sequence and communicates the iterates to its neighbors. Then, each agent combines weighted averages of the received iterates with its own iterate, and adjusts the iterate by using subgradient information (known with stochastic errors) of its own function and by projecting onto the constraint set.The goal of this paper is to explore the effects of stochastic subgradient errors on the convergence of the algorithm. We first consider the behavior of the algorithm in mean, and then the convergence with probability 1 and in mean square. We consider general stochastic errors that have uniformly bounded second moments and obtain bounds on the limiting performance of the algorithm in mean for diminishing and non-diminishing stepsizes. When the means of the errors diminish, we prove that there is mean consensus between the agents and mean convergence to the optimum function value for diminishing stepsizes. When the mean errors diminish sufficiently fast, we strengthen the results to consensus and convergence of the iterates to an optimal solution with probability 1 and in mean square.

Subfields: Artificial Intelligence, Computer Networks and Communications, Mathematical Optimization

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 Computer Networks and Communications

In Mathematical Optimization

Citations in the corpus

Central Server Free Federated Learning over Single-sided Trust Social Networks (2019, background): “Such a requirement is quite restrictive, because not all networks admit a doubly stochastic matrix (Gharesifard and Cort´es 2010), and relinquishing double stochasticity can introduce bias in optimization (Ram et al., 2010; Tsianos and Rab-bat, 2012).”
D2: Decentralized Training over Decentralized Data (2018, methodology): “The D-PSGD algorithm [Nedic and Ozdaglar, 2009, Ram et al., 2010a,b] requires each worker to compute a stochastic gradient and exchange its local model with neighbors.”
Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, background): “1 Decentralized algorithms are mainly studied as consensus optimization problems by the control community [Ram et al., 2010, Yan et al., 2013, Yuan et al., 2016] for the application scenario where only a decentralized network is available.”
Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “…and Nedic, 2011, Sundhar Ram et al., 2010] or implicitly indicate that decentralized algorithms were much worse than centralized algorithms in terms of computational complexity and total communication complexity [Aybat et al., 2015, Lan et al., 2017, Ram et al., 2010, Zhang and Kwok, 2014].”
Personalized and Private Peer-to-Peer Machine Learning (2017, background): “Most of the work in fully decentralized learning and optimization has focused on the distributed consensus problem, where the goal is to find a single global model which minimizes the sum of the local loss functions (Nedic and Ozdaglar, 2009; Ram et al., 2010; Duchi et al., 2012; Wei and Ozdaglar, 2”
Decentralized Collaborative Learning of Personalized Models over Networks (2016, methodology): “Several peer-to-peer algorithms have been developed for decentralized averaging (Kempe et al., 2003; Boyd et al., 2006; Colin et al., 2015) and optimization (Nedic and Ozdaglar, 2009; Ram et al., 2010; Duchi et al., 2012; Wei and Ozdaglar, 2012, 2013; Iutzeler et al., 2013; Colin et al., 2016).”
Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions (2016, neutral): “The most popular algorithms are based on (sub)gradient descent (Johansson et al., 2010; Nedić & Ozdaglar, 2009; Ram et al., 2010; Bianchi & Jakubowicz, 2013), ADMM (Wei & Ozdaglar, 2012; 2013; Iutzeler et al.”
Differentially Private Distributed Optimization (2014, background): “Categories and Subject Descriptors D.1.3 [Software]: Concurrent Programming—Distributed programming General Terms Algorithm Keywords Distributed Optimization, Differential Privacy, Iterative Consensus”
Distributed delayed stochastic optimization (2011, background): “More recent work has studied problems in which each processor or node i in a network has a local function fi, and the goal is to minimize the sum f(x) = 1 n ∑n i=1 fi(x) [12, 13, 17, 7].”
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling (2010, neutral): “Our final set of experiments compares the distributed dual averaging method (DDA) that we present to the Markov incremental gradient descent (MIGD) method [11] and the distributed projected gradient method [10].”
On the Convergence of Decentralized Gradient Descent (2013, methodology): “The rate of the mean solution is obtained by analyzing an inexact gradient descent iteration, somewhat similar to [8, 11, 20, 25].”
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, background): “When (1.1) has additional constraints that force x in a bounded set, which also leads to bounded (sub)gradients and Hessian, projected ﬁrst-order algorithms are applicable [27,37].”
On the Linear Convergence of the ADMM in Decentralized Consensus Optimization (2013, methodology): “The analysis provide guidelines for networking strategies, objective-function splitting strategies, and algorithm parameter settings to achieve faster convergence.”
Distributed optimization over time-varying directed graphs (2013, methodology): “Finally, we remark that previous research [13], [17], [4] has studied the case when the matrices A(t) (defined in the statement of Theorem 2) are doubly stochastic; this occurs when the directed graph sequence {G(t)} is regular, and in that case our polynomial bounds essentially match previously kno”
Fast Distributed Gradient Methods (2011, neutral): “2298712 also [9]–[11]); [12] (see also [13]); [14] (see also [3], [15]); and [16].”
On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers (2013, methodology): “sus step).3 Several follow-up papers considered variants of this method for problems with local and global constraints [26], [36] randomly varying networks [29], [30], [31] and random gradient errors [42], [34]. A different distributed algorithm that relies on Nesterov’s dual averaging algorithm [37”
Distributed Multi-Task Learning (2015, background): “The consensus problem has also been studied in the stochastic setting [10], in which each machine receives stochastic estimates of its local objective.”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, background): “To handle a more general (possibly time-varying) networks, distributed subgradient algorithm was proposed in [47], while its stochastic variant was studied in [56] and its asynchronous variant in [36] with provable convergence rates.”