Convergence of a Multi-Agent Projected Stochastic Gradient Algorithm for Non-Convex Optimization

By Pascal Bianchi, Jérémie Jakubowicz. 2011

268 citations recorded by the source corpus.

We introduce a new framework for the convergence analysis of a class of distributed constrained non-convex optimization algorithms in multi-agent systems. The aim is to search for local minimizers of a non-convex objective function which is supposed to be a sum of local utility functions of the agents. The algorithm under study consists of two steps: a local stochastic gradient descent at each agent and a gossip step that drives the network of agents to a consensus. Under the assumption of decreasing stepsize, it is proved that consensus is asymptotically achieved in the network and that the algorithm converges to the set of Karush-Kuhn-Tucker points. As an important feature, the algorithm does not require the double-stochasticity of the gossip matrices. It is in particular suitable for use in a natural broadcast scenario for which no feedback messages between agents are required. It is proved that our results also holds if the number of communications in the network per unit of time vanishes at moderate speed as time increases, allowing potential savings of the network's energy. Applications to power allocation in wireless ad-hoc networks are discussed. Finally, we provide numerical results which sustain our claims.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering

How researchers see this paper

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

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

Asynchronous distributed optimization using a randomized alternating direction method of multipliers (2013, methodology): “The first one is based on the simultaneous use of a local first-order optimization algorithm (subgradient algorithm [2], [3], [4], Nesterov-like method [5], [6]) and a gossip process which drives the”
On Nonconvex Decentralized Gradient Descent (2016, methodology): “Another difference is that Proj SGD of [4] uses adaptive-then-combine (ATC) and Prox-DGD of this paper does combine-then-adaptive (CTA).”
A Framework for Parallel and Distributed Training of Neural Networks (2016, methodology): “However, in the specific case where the regularization function r satisfies assumption B1, we can easily adapt the framework introduced in Bianchi and Jakubowicz (2013), resulting in a simple method that we denote as the distributed gradient (DistGrad) algorithm.”
A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent (2019, methodology): “A projected stochastic gradient algorithm was considered in [32] for solving nonconvex optimization problems by combining a local stochastic gradient update and a gossip step.”
Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization (2018, background): “On the contrary, only recently there have been some work addressing the more challenging problems without assuming convexity of fi’s; see recent developments in [3,4,26,27].”
Distributed off-Policy Actor-Critic Reinforcement Learning with Policy Consensus (2019, methodology): “If the function F (θ̄) is the gradient of the function f(θ̄), then we can directly use Proposition 4 in [21] to get the desired result.”
NEXT: In-Network Nonconvex Optimization (2016, methodology): “Consider a network composed of I autonomous agents aiming to cooperatively and distributively solve Problem (1).”
Prox-PDA: The Proximal Primal-Dual Algorithm for Fast Distributed Nonconvex Optimization and Learning Over Networks (2017, background): “In (Bianchi & Jakubowicz, 2013) a stochastic projection algorithm using diminishing stepsizes has been proposed.”
Distributed Distillation for On-Device Learning (2020, background): “The theoretical basis for these D-SGD algorithms is the seminal works on distributed optimization [11–13], which were later generalized to non-convex cost functions in [14, 15].”
Primal-Dual Algorithm for Distributed Reinforcement Learning: Distributed GTD (2018, methodology): “, GTD [1], [2] or the residual method [12], algorithms from [10], [11] can be applied.”
A Non-Asymptotic Analysis of Network Independence for Distributed Stochastic Gradient Descent (2019, background): “Recently, distributed implementation of stochastic gradient algorithms has received considerable interest [37, 41, 12, 3, 5, 42, 6, 7, 22, 17, 18, 30, 31, 38, 40, 14, 33, 29, 44, 1].”
A review of cooperative multi-agent deep reinforcement learning (2019, background): “In recent years, there has been a flurry of research on designing optimization algorithms for solving complex problems including nonconvex and nonsmooth optimization problems for multi-agent and distributed systems [14, 33, 48].”