Source-linked AI summary
Distributed Nonconvex Constrained Optimization over Time-Varying Digraphs
Gesualdo Scutari, Ying Sun
TL;DR
The paper targets distributed constrained optimization for smooth, possibly nonconvex aggregate costs combined with DC regularization over time-varying directed graphs. It proposes a successive-convex-approximation framework with perturbed push-sum gradient tracking, proving sublinear rates for constant step-sizes and asymptotic stationarity for diminishing step-sizes. Numerical results compare favorably with current schemes.
Problem
The gap is the lack of distributed schemes for the composite nonconvex constrained problem over general time-varying directed graphs, including nonsmooth regularization and potentially unbounded gradients.
Method
The framework combines successive convex approximation with perturbed push-sum consensus to track the aggregate smooth gradient over directed or undirected time-varying graphs.
Results
The method converges to stationary solutions; constant step-sizes provide a sublinear convergence rate, and numerical results compare favorably with state-of-the-art algorithms.
Takeaways & Limitations
The framework enlarges the class of constrained and composite convex or nonconvex problems to which distributed algorithms have convergence guarantees.
Takeaways & Limitations
The analysis assumes strongly convex surrogate functions, although compact feasible sets allow this to be weakened to convexity; inexact subproblems require additional assumptions on G+.
Abstract
from arXiv · showhide
This paper considers nonconvex distributed constrained optimization over networks, modeled as directed (possibly time-varying) graphs. We introduce the first algorithmic framework for the minimization of the sum of a smooth nonconvex (nonseparable) function--the agent's sum-utility--plus a Difference-of-Convex (DC) function (with nonsmooth convex part). This general formulation arises in many applications, from statistical machine learning to engineering. The proposed distributed method combines successive convex approximation techniques with a judiciously designed perturbed push-sum consensus mechanism that aims to track locally the gradient of the (smooth part of the) sum-utility. Sublinear convergence rate is proved when a fixed step-size (possibly different among the agents) is employed whereas asymptotic convergence to stationary solutions is proved using a diminishing step-size. Numerical results show that our algorithms compare favorably with current schemes on both convex and nonconvex problems.
1 Introduction
The paper addresses distributed optimization of a possibly nonconvex, nonseparable composite objective over constrained, time-varying directed networks. It introduces a provably convergent framework combining successive convex approximation with perturbed push-sum gradient tracking.
- Problem setting: The problem combines smooth possibly nonconvex agent costs, a DC regularizer with nonsmooth convex part, and convex constraints.Each agent knows only its own cost function, while agents cooperate through local communications.
- Motivation: The setting covers applications including network information processing, telecommunications, multi-agent control, machine learning, and data-intensive analytics.Examples include nonlinear least squares, dictionary learning, component analysis, low-rank approximation, and matrix completion.
- Motivation: Distributed computation is motivated by scattered data whose volume and spatial or temporal disparity can make centralized processing infeasible or inefficient.Time-varying directed links naturally model mobile wireless networks and asymmetric communication conditions.
- Contributions: Constant step-sizes yield sublinear convergence, while diminishing step-sizes yield convergence to stationary solutions.The framework also permits different constant step-sizes among agents.
- Contributions: The analysis addresses nonconvexity, nonsmoothness, constraints, general directed time-varying graphs, and unbounded gradients, extending the scope of distributed methods.The paper reports preliminary numerical results comparing favorably with state-of-the-art algorithms.
- Contributions: The proposed framework is designed for arbitrary time-varying directed or undirected graphs, preserves feasibility, and requires only column-stochastic weights on directed graphs.It uses successive convex approximation and perturbed push-sum consensus to track the gradient of the smooth aggregate objective.
2 Problem Setup and Motivating Examples
The paper formulates constrained distributed optimization with smooth, possibly nonconvex agent costs and a DC regularizer over time-varying directed networks. It motivates the formulation through sparse statistical-learning problems, including nonconvex sparse regression and sparse PCA.
- Problem formulation: The problem uses a closed convex feasible set, smooth possibly nonconvex agent costs, and a DC regularizer with a convex possibly nonsmooth part.
- Problem formulation: The regularizer G can promote extra solution structure, including sparsity through convex or nonconvex surrogates of the ℓ0 function.
- Distributed information: Each agent knows only its own cost function and the shared regularizer, rather than the other agents’ cost functions.
- Network model: Agents communicate over directed, possibly time-varying graphs, with information exchanged through time-dependent in- and out-neighborhoods.
- Motivating examples: The motivating applications include nonconvex sparse linear regression and sparse PCA, both modeled as instances of the proposed problem class.
3 Preliminaries: The perturbed condensed push-sum algorithm
This section develops perturbed condensed push-sum as a constrained consensus mechanism for directed, time-varying graphs. Its auxiliary variables yield row-stochastic equivalent weights, supporting feasibility preservation, average tracking, and convergence analysis.
- Algorithmic role: The framework combines local successive convex approximation with constrained consensus and gradient-average tracking over directed graphs.
- Algorithmic role: Perturbed condensed push-sum is introduced as a reformulation better suited to integrating push-sum consensus with constrained optimization.
- Protocol structure: The auxiliary variables φ_i dynamically rebuild row stochasticity in the equivalent weight matrix, a condition used to lock consensus.
- Convergence analysis: Under column-stochastic weight matrices and B-strong connectivity, Proposition 1 establishes convergence properties for arbitrary perturbation sequences satisfying the stated conditions.
- Special cases: With zero perturbations, the protocol reduces to condensed push-sum and yields geometric convergence to weighted average consensus.
- Special cases: Because the equivalent weights are row stochastic, initializing all agent values in K preserves feasibility of every iterate.
- Special cases: The same protocol can track averages of time-varying signals when agents generate signal samples and use the prescribed perturbations.
- Convergence analysis: The convergence proof reduces consensus analysis to bounding products of row-stochastic equivalent matrices relative to a weight-averaging matrix.
4 Algorithmic Design
SONATA combines local successive convex approximation with perturbed push-sum consensus and gradient tracking for constrained composite optimization over time-varying directed graphs. Under stated step-size conditions, it achieves consensus at stationary solutions and provides asymptotic convergence and O(1/ϵ) complexity guarantees.
- Gradient tracking: Each agent maintains a local copy of the global variable and an auxiliary variable for tracking the average gradient information unavailable locally.The auxiliary variable is updated using only local information through perturbed condensed push-sum.
- Local successive convex approximation: SONATA has each agent solve a local convexification of the composite problem using a strongly convex approximation of its smooth cost and a linearized concave DC component.The local update uses a step-size α_n ∈ (0, 1).
- Surrogate assumptions: The surrogate preserves first-order properties, is uniformly strongly convex in its optimization argument, and has a uniformly Lipschitz partial gradient.These conditions support simple convex local approximations of the agents’ smooth costs.
- Information mixing: Perturbed push-sum updates mix optimization variables and auxiliary tracking variables using communication with in-neighbors and out-neighbors on directed, possibly time-varying graphs.The mechanism is designed to make local variables asymptotically consensual while tracking gradient averages.
- Distributed implementation: The algorithm is distributed: local optimization uses locally available variables, while consensus and tracking exchange information only among graph neighbors.SONATA combines the local optimization step with two information-mixing steps.
- Convergence and complexity: Under the convergence assumptions, local iterates approach a stationary solution, and with a constant step-size the first iteration attaining M(x_n) ≤ ϵ satisfies T_ϵ = O(1/ϵ).The asymptotic result gives lim_{n→∞} M(x_n) = 0; the results also extend with minor modifications to different constant agent step-sizes.
5 SONATA and special cases
SONATA provides a unifying framework that subsumes several distributed optimization algorithms as special cases under restricted problem and network settings.
- SONATA-L: The linearized SONATA-L variant results from first-order surrogates with proximal terms and can use ATC or CAA mixing protocols.
- NEXT-L: With double-stochastic mixing, the ATC-based SONATA-L updates coincide with the earlier NEXT algorithm.
- Algorithms in [30,33,49,51] are all special cases of SONATA and NEXT.
- Related algorithms: Aug-DGM and the algorithm in [33] coincide with ATC-NEXT-L under the stated equal-step-size or networking conditions.
- Related algorithms: DIGing coincides with CAA-NEXT-L, while push-DIGing coincides with ATC-SONATA-L in the cited settings.
- Related algorithms: ADD-OPT coincides with CAA-SONATA-L after the stated variable transformation.
6 Convergence Proof of SONATA
The convergence proof analyzes SONATA through weighted averages, consensus disagreement, tracking errors, and a Lyapunov-like function under the paper’s standing assumptions.
- Proof strategy: The proof studies a Lyapunov function along the weighted average, consensus disagreement, and tracking-error dynamics.
- Solution map: The error-free local solution map is Lipschitz continuous, and its fixed points coincide with d-stationary solutions of Problem (P).
- Error dynamics: The analysis establishes that consensus and tracking disagreements asymptotically vanish under the relevant conditions.
- Error dynamics: A new analysis couples consensus and tracking errors because constant step-sizes or unbounded subgradients prevent directly inferring summability from consensus-error dynamics alone.
- Lyapunov analysis: The proof constructs a Lyapunov-like function whose descent over blocks of iterations yields summability of errors and convergence of all error sequences.
- Step-sizes: The convergence argument treats constant and diminishing step-sizes separately, with constant step-sizes requiring sufficiently small values.
7 Numerical results
Numerical experiments evaluate SONATA on sparse regression and distributed PCA over time-varying digraphs, with results favoring SONATA against the tested baselines.
- Sparse regression: Sparse regression experiments use 30 agents, time-varying digraphs, 100 Monte Carlo trials, and a nonconvex logarithmic sparsity regularizer.
- Sparse regression: Both SONATA variants are much faster than distributed gradient, and SONATA-PL converges faster than SONATA-L under the same tuning.
- Distributed PCA: The distributed PCA experiments compare SONATA with gradient projection on synthetic and gene-expression data using stationarity, consensus, and NMSE measures.
- Synthetic PCA: On synthetic PCA data, SONATA efficiently finds a stationary point and the leading eigenvector, whereas the gradient algorithm progresses slowly and fails to achieve a small NMSE.
- Gene-expression PCA: On the gene-expression data set, SONATA shows behavior similar to the synthetic experiment and converges quite fast despite the massive variable dimension.
A Proof of Lemma 3
The appendix proof develops bounds for products of time-varying mixing matrices and their disagreement from weighted consensus behavior.
- Mixing bounds: Lemma 15 provides stochastic-vector and matrix-product properties used in proving the mixing result.
- Relation to prior work: The appendix states that Lemma 15 follows arguments related to prior results while requiring only the paper’s weaker graph condition.
- Proof construction: The proof analyzes each coordinate of an arbitrary stacked vector and bounds the deviation of matrix products from the weighted consensus operator.
B Proof of Lemma 11
The proof derives the stated results by recognizing both SONATA updates as instances of the perturbed condensed push-sum algorithm and applying Proposition 1.
- B Proof of Lemma 11: The SONATA x-update is identified as a special case of the perturbed condensed push-sum algorithm, with a specified perturbation.This correspondence allows Proposition 1 to be applied directly to obtain (69).
- B Proof of Lemma 11: The y-update is likewise recognized as a special case of the same algorithm, enabling the analogous argument for (70).The passage indicates that the perturbation is defined through the inverse diagonal scaling and gradient-related term shown there.
- B Proof of Lemma 11: The argument concludes after these two update correspondences and their associated applications of Proposition 1.The proof text explicitly marks completion at the end.