Performance of a Distributed Stochastic Approximation Algorithm

By Pascal Bianchi, Gersende Fort, Walid Hachem. 2012

117 citations recorded by the source corpus.

In this paper, a distributed stochastic approximation algorithm is studied. Applications of such algorithms include decentralized estimation, optimization, control or computing. The algorithm consists in two steps: a local step, where each node in a network updates a local estimate using a stochastic approximation algorithm with decreasing step size, and a gossip step, where a node computes a local weighted average between its estimates and those of its neighbors. Convergence of the estimates toward a consensus is established under weak assumptions. The approach relies on two main ingredients: the existence of a Lyapunov function for the mean field in the agreement subspace, and a contraction property of the random matrices of weights in the subspace orthogonal to the agreement subspace. A second-order analysis of the algorithm is also performed under the form of a central limit Theorem. The Polyak-averaged version of the algorithm is also considered.

Subfields: Artificial Intelligence, Computer Networks and Communications

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

Citations in the corpus

Communication Efficient Decentralized Training with Multiple Local Updates (2019, background): “In recent years, many decentralized algorithms have been proposed for solving the problem (1) [1, 50, 36, 3, 20, 15, 41].”
Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, background): “Bianchi et al. [2013] proposed a similar decentralized stochastic algorithm.”
Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent (2017, background): “The analysis in Bianchi et al. [2013] uses strong non-standard assumptions for a decentralized stochastic algorithm, which requires continuously increasing communication cost when we run the algorithm since the second largest eigenvalue of the averaging matrix needs to be decreasing to 0 when the…”
On the rates of convergence of parallelized averaged stochastic gradient algorithms (2017, methodology): “[4] proposes to parallelize ASGD but for a uniform distribution of the data between the machines, and so that without taking the number of data permachine into account.”
On Nonconvex Decentralized Gradient Descent (2016, background): “Note that the bounded gradient assumption is a regular assumption in the convergence analysis of decentralized gradient methods (see, [4], [5], [18], [27], [35], [36], [56], [57], [62] for example), even in the convex setting [24] and also [10], though it is not required for centralized gradient des”
Adaptive Networks (2014, methodology): “The ATC form (49b), also with an iteration-dependent sequence (cid:8) ð i Þ that decays to zero, was further employed in [121] and [122] to ensure almost-sure convergence and agreement among agents.”
Social learning and distributed hypothesis testing (2014, background): “ls study how message passing in a network can be used to achieve a pre-speciﬁed computational task such as distributed learning [16], [17], general function evaluation [18], stochastic approximations [19]. Message passing protocols may be synchronous or asynchronous (such as the “gossip” model [20]–”
Communication-Efficient Local Decentralized SGD Methods (2019, background): “D-SGD works in the following way [1, 13].”
Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents (2018, background): “One particular choice of the weights in C t that relies on only local information of the agents is known as Metropolis weights (Xiao et al., 2005; Cattivelli et al., 2008) (Boyd et al., 2006), broadcast gossip (Aysal et al., 2009), and network dropouts (Bianchi et al., 2013).”
Excess-Risk of Distributed Stochastic Learners (2013, background): “Specifically, we will show that the strategies under study achieve a better convergence rate than noncooperative algorithms, and we will also explain why diffusion strategies outperform other distributed solutions such as those relying on consensus constructions or on doublystochastic combination…”
A Coordinate Descent Primal-Dual Algorithm and Application to Distributed Asynchronous Optimization (2014, background): “Instances of this problem appear in learning applications where massive training data sets are distributed over a netw ork and processed by distinct machines [33], [34], in resource allocation problems for communication networks [21], or in statistical estimation problems by sensor networks [20], [ ”
Data-Dependent Convergence for Consensus Stochastic Optimization (2016, methodology): “[9] follows from our existing assumptions.”