NEXT: In-Network Nonconvex Optimization

TLDR

Sparsity‑inducing regularizers are commonly used to enforce structure in solutions. The paper introduces the first algorithmic framework for distributed minimization of a smooth possibly nonconvex sum‑utility plus a convex regularizer over multiagent networks with time‑varying connectivity. The framework uses successive convex approximation and dynamic consensus, with each agent solving a local convex surrogate and averaging, and is adaptable to diverse convex and nonconvex problems in signal processing, communications, networking, and machine learning. The method provably converges to stationary solutions and outperforms existing distributed algorithms on both convex and nonconvex benchmark problems.

Abstract

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.