NEXT: In-Network Nonconvex Optimization

By P. Lorenzo, Gesualdo Scutari. IEEE Transactions on Signal and Information Processing over Networks, 2016

572 citations recorded by the source corpus.

We study nonconvex distributed optimization in multiagent networks with time-varying (nonsymmetric) connectivity. We introduce the first algorithmic framework for the distributed minimization of the sum of a smooth (possibly nonconvex and nonseparable) function-the agents' sum-utility-plus a convex (possibly nonsmooth and nonseparable) regularizer. The latter is usually employed to enforce some structure in the solution, typically sparsity. The proposed method hinges on successive convex approximation techniques while leveraging dynamic consensus as a mechanism to distribute the computation among the agents: each agent first solves (possibly inexactly) a local convex approximation of the nonconvex original problem, and then performs local averaging operations. Asymptotic convergence to (stationary) solutions of the nonconvex problem is established. Our algorithmic framework is then customized to a variety of convex and nonconvex problems in several fields, including signal processing, communications, networking, and machine learning. Numerical results show that the new method compares favorably to existing distributed algorithms on both convex and nonconvex problems.

Subfields: Computational Mechanics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/677a9e728b57eb470729774abfe611a00035bb20

How researchers see this paper

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

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

Exact Diffusion for Distributed Optimization and Learning—Part I: Algorithm Development (2017, methodology): “Also, there is one combination step in each iteration, which reduces the communication cost by about one half in comparison to recent DIGing-based works [39]–[43].”
Finite Rate Quantized Distributed optimization with Geometric Convergence (2018, methodology): “In particular, geometric convergence when each function fi is strongly convex was proved in [6] for the distributed ADMM method, while [7] for the gradient-tracking based distributed method, first introduced in [8]; a recent overview of distributed algorithms can be found in [9].”
Accelerated Distributed Nesterov Gradient Descent (2017, methodology): “For example, the EXTRA method in [23] and the class of methods in [24] and [26]–[28] can all achieve a linear convergence rate for strongly convex and smooth functions.”
Nested Distributed Gradient Methods with Adaptive Quantized Communication (2019, methodology): “The authors of [26] extend [28]; however, while gradient tracking algorithms (e.”
On Nonconvex Decentralized Gradient Descent (2016, methodology): “All these proof techniques are new and distinguish our paper from the existing works such as [4], [10], [18], [24], [35], [40], [57], [62].”
A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates (2017, unknown): “Paper [39] solves non-convex optimization problems.”
Distributed Gradient Methods for Convex Machine Learning Problems in Networks: Distributed Optimization (2020, background): “Simultaneously and independently of [29] and [30], the idea of tracking the gradients has been employed in [31], where a class of distributed algorithms have been developed for solving nonconvex problems in networks.”
Supervised Learning Under Distributed Features (2018, methodology): “The motivation for dynamic diffusion is similar to what been used before in the distributed optimization literature [40]–[42], with two main differences.”
Distributed Quantized Weight-Balancing and Average Consensus Over Digraphs (2018, background): “Weight-balanced directed graphs – digraphs wherein the sum of the weights of the edges outgoing from each node is equal to the sum of the weights of the edges incoming to the node – play a key role in a number of network applications, including distributed optimization [1], distributed flowbalancing”
A Framework for Parallel and Distributed Training of Neural Networks (2016, methodology): “…for the lack of distributed training methods for NNs is that, in principle, these methods require the solution of a distributed nonconvex optimization problem, which was tackled only in a few papers even in the optimization literature (Bianchi and Jakubowicz, 2013; Di Lorenzo and Scutari, 2016).”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, methodology): “The algorithm we will study in this paper crucially relies on tracking diﬀerences of gradients and is a minor variation of algorithms that have appeared in [73,74] and [15–17].”
A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent (2019, background): “incur noises from various sources such as approximation error and modeling and discretization errors. Problem (1.1) has been studied extensively in the literature under various distributed algorithms [42, 25, 26, 19, 15, 16, 38, 11, 34, 23, 44, 33], among which the distributed gradient descent (DGD)”
Multiagent Fully Decentralized Value Function Learning With Linear Convergence Rates (2018, background): “Several other works employ instead a gradient tracking strategy [27], [28], [33].”
Accelerating the Convergence Rates of Distributed Subgradient Methods with Adaptive Quantization (2018, methodology): “…attention during the last decade, mostly focusing on three classes of algorithms, namely, the alternating direction method of multipliers (ADMM) [1,17,33,35], distributed dual methods (mirror descent/dual averaging) [6,9,14,34,37], and distributed gradient algorithms [3–5,13,16,22,23,27,29,32,38].”