Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems

By Gesualdo Scutari, Francisco Facchinei, Peiran Song, D. P. Palomar, Jong-Shi Pang. IEEE Transactions on Signal Processing, 2013

319 citations recorded by the source corpus.

We propose a novel decomposition framework for the distributed optimization of general nonconvex sum-utility functions arising naturally in the system design of wireless multi-user interfering systems. Our main contributions are i) the development of the first class of (inexact) Jacobi best-response algorithms with provable convergence, where all the users simultaneously and iteratively solve a suitably convexified version of the original sum-utility optimization problem; ii) the derivation of a general dynamic pricing mechanism that provides a unified view of existing pricing schemes that are based, instead, on heuristics; and iii) a framework that can be easily particularized to well-known applications, giving rise to very efficient practical (Jacobi or Gauss-Seidel) algorithms that outperform existing ad hoc methods proposed for very specific problems. Interestingly, our framework contains as special cases well-known gradient algorithms for nonconvex sum-utility problems, and many block-coordinate descent schemes for convex functions.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/d9392944772f0c6f11e9fdfaff477012137c6f5e

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

Parallel Selective Algorithms for Nonconvex Big Data Optimization (2014, unknown): “In this paper, we focus onnonconvexproblems in the form (1), and proposed a new broad, deterministicalgorithmic framework for the computation of their stationary solution s, which hinges on ideas first introduced in [21].”
Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems (2014, background): “We note that there have been many recent works proposing new algorithms to solve nonconvex and nonsmooth problems, for example, [50, 51, 52, 53, 54].”
Joint Optimization of Radio and Computational Resources for Multicell Mobile-Edge Computing (2014, background): “Many choices are possible for the step-size γ ; a practical rule satisfying (24) that we found effective in ou r experiments is [32]:”
Group sparse regularization for deep neural networks (2016, methodology): “Alternatively, we might improve the sparse behavior of (4) and (5) by iteratively solving a convex approximation to the original non-convex problem, e.g. by exploiting the techniques presented in [49], as we did in a previous work on semi-supervised support vector machines [50].”
Optimization Methods for Designing Sequences With Low Autocorrelation Sidelobes (2014, background): “Let L be ann × n Hermitian matrix andM be anothern× n Hermitian matrix such thatM L.”
Finite Rate Quantized Distributed optimization with Geometric Convergence (2018, background): “Instances of (P) that fit the above distributed setting can be widely found in many applications, including network information processing and decision making [1], resource allocation in communication networks [2], distributed spectrum sensing [3], and distributed machine learning [4].”
A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data: With applications in machine learning and signal processing (2015, methodology): “To see the convergence analysis of this algorithm and other related algorithms such as the flexible parallel algorithm, refer to [18], [99], [100], and the references therein.”
Majorization-Minimization Algorithms in Signal Processing, Communications, and Machine Learning (2017, methodology): “On the contrary, FLEXA relaxes the upperbound condition, but requires it to be strongly convex.”
On Nonconvex Decentralized Gradient Descent (2016, background): “Some typical applications include: (i) the distributed compressed sensing problems [14], [30], [39], [45], [49]; (ii) distributed consensus [9], [29], [55], [58], [61], [69]; (iii) distributed and parallel machine learning [15], [21], [33], [43], [55].”