PaperlayerView exact revision on arXiv

Source-linked AI summary

NEXT: In-Network Nonconvex Optimization

Paolo Di Lorenzo, Gesualdo Scutari

arXiv:1602.00591v1cs.DCeess.SYmath.OC

TL;DR

Distributed optimization over time-varying, nonsymmetric networks lacks a general way to handle nonconvex objectives with convex regularization. NEXT combines successive convex approximation with dynamic consensus and achieves asymptotic convergence to stationary solutions, while outperforming existing methods in reported numerical tests.

  • Problem

    Existing distributed methods for this problem are limited by difficult nonconvex subproblems, auxiliary stationary points, fusion centers, or restrictive network topologies.

  • Method

    NEXT combines successive convex approximation and dynamic consensus to distribute local convex optimization and information propagation over time-varying, nonsymmetric networks.

  • Results

    NEXT converges to consensual stationary solutions and is much faster than D-Gradient in the reported target-localization experiment.

  • Takeaways & Limitations

    The framework provides flexible distributed algorithms that can be customized across convex and nonconvex optimization problems and network conditions.

Abstract

from arXiv · show

We study nonconvex distributed optimization in multi-agent 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.

I. INTRODUCTION · II. A NEW IN-NETWORK OPTIMIZATION TECHNIQUE · A. Development of NEXT: A constructive approach

The paper introduces NEXT for decentralized minimization of a smooth, possibly nonconvex sum-utility plus a convex regularizer over time-varying directed networks. It combines local successive convex approximation, consensus, and dynamic gradient tracking to achieve distributed computation and convergence to stationary solutions.

  • I. INTRODUCTION: The target problem minimizes agents’ smooth sum-utility F plus a convex regularizer G, which can be nonsmooth, nonseparable, and used to promote sparsity.Applications include sensor networks, communications, multi-agent control, and distributed machine learning.
  • I. INTRODUCTION: Existing distributed methods largely address convex problems or require global information, fusion centers, or restrictive network topologies, leaving the general nonconvex formulation unresolved.The paper identifies only a few prior methods for special cases of the problem.
  • I. INTRODUCTION: NEXT provides a flexible framework whose algorithms converge to the same stationary solution while allowing problem-specific control of signaling and communication overhead.Numerical results report better practical convergence than current methods.
  • II. A NEW IN-NETWORK OPTIMIZATION TECHNIQUE: The framework operates under local-information assumptions with possibly nonconvex agent costs, a convex regularizer, and time-varying directed networks that need only satisfy suitable connectivity conditions.Agents know only their own cost, the common regularizer, and the feasible set; no knowledge of LF or LG is required.
  • A. Development of NEXT: A constructive approach: NEXT addresses nonconvexity through local SCA: each agent replaces its unavailable global objective with a strongly convex surrogate for its own cost and linearizes the other agents’ costs.The resulting local problem has a unique solution, interpreted as a fixed-point mapping linked to stationary solutions.
  • A. Development of NEXT: A constructive approach: Under conditions F1–F3, fixed points of each local mapping coincide with stationary solutions of the original problem.The surrogate is uniformly strongly convex, preserves first-order information, and has uniformly Lipschitz dependence on the expansion point.
  • A. Development of NEXT: A constructive approach: Consensus updates average neighboring local solutions using topology-compatible, possibly time-varying weights, driving all agents toward a common stationary solution.The intended asymptotic behavior is consensus on the estimates while reaching a fixed point of the local mappings.
  • A. Development of NEXT: A constructive approach: Dynamic average consensus tracks the unavailable aggregate gradient locally, enabling each agent to replace global gradient information with an asymptotically accurate estimate.The tracking error and the discrepancy between the estimated and exact gradient terms converge to zero under convergent consensual iterates.

B. The NEXT algorithm

NEXT combines local successive convex approximation with consensus updates over time-varying networks. Under the stated assumptions and step-size conditions, its average iterates approach stationary solutions while agents asymptotically reach consensus; in convex cases, solutions are globally optimal.

  • Convergence guarantees: The agents’ local estimates asymptotically agree, establishing consensus across the network.The theorem also states that the average sequence converges to the stationary-solution set while local estimates reach consensus.
  • Algorithmic steps: NEXT alternates local SCA optimization with consensus updates of each agent’s local variables and gradient-tracking quantities.Each agent computes a local approximation solution, forms a convex combination with its current estimate, and exchanges data with current neighbors.
  • Convergence guarantees: The global sequence converges to the consensus embedding of the stationary-solution set S.The limiting set is represented as {1 ⊗ x ∈ S}.
  • Convex specialization: When F is convex, NEXT converges to the set of global optimal solutions of the resulting convex problem.The broader convergence result does not require F to be convex.

C. Design of the free parameters

This section presents flexible design choices for NEXT’s surrogates, step sizes, and weight matrices, including structures that preserve convexity and enable distributed parallel computation. It also explains how NEXT-L differs from gradient-consensus updates.

  • Parameter design: NEXT supports a broad family of convergent algorithms through different choices of local surrogates, weight matrices W[n], and step-size sequences α[n].The framework maintains common convergence conditions across these parameter choices.
  • Surrogate functions: Proximal regularization makes the local surrogate strongly convex, while other choices preserve convex structure or use second-order approximations when fi is convex.The section also describes intermediate surrogates that preserve convex components and linearize nonconvex ones, including block-wise convex and composition structures.
  • Distributed and parallel computing: Choosing additively separable surrogates decomposes each node’s subproblem into C separate strongly convex subproblems that different cores can solve independently.This yields a method distributed across nodes and parallel inside each node.
  • Step sizes and weights: The step-size rules require no centralized coordination and mitigate practical drawbacks associated with diminishing (sub)gradient methods, although tuning may still be needed.The discussed sequence includes α[n] = α0/(n + 1)^β, with α0 > 0 and 0.5 < β ≤ 1.
  • Step sizes and weights: NEXT requires doubly stochastic weight matrices W[n], but enforcing left-stochasticity in time-varying topologies is more difficult and may require neighboring-agent coordination.Candidate rules include uniform, Laplacian, maximum-degree, Metropolis-Hastings, and least-mean-square consensus weights.
  • NEXT vs. gradient-consensus algorithms: Compared with gradient-consensus methods, NEXT-L uses exi[n] − xi[n] instead of zi[n] − xi[n], retaining inexact information about the whole sum-utility gradient through eπi.The gradient-consensus direction depends only on the local gradient of fi.

III. INEXACT NEXT

Inexact NEXT reduces the computational effort of solving local convex subproblems by allowing controlled approximation errors. Its convergence is preserved when local problems are solved with increasing accuracy under a summability condition linking errors and step sizes.

  • Motivation and mechanism: Inexact NEXT allows agents to compute local subproblem solutions inexactly, reducing per-iteration computational effort for large-scale problems.The approximation accuracy is measured by ε_i[n].
  • Algorithm: Algorithm 2, termed Inexact NEXT, replaces the exact local SCA step of Algorithm 1 with a local inexact SCA update.The remaining steps are the same as in Algorithm 1.
  • Convergence: The convergence statements of Theorem 3 continue to hold for the sequence generated by Inexact NEXT under the theorem’s step-size conditions.The result is stated after imposing the additional error-related condition in Theorem 4.
  • Convergence: Convergence requires ε_i[n] → 0 and ∑_n α[n] ε_i[n] < ∞, so the local approximated problems must be solved with increasing accuracy at a suitable rate.A sufficient example is ε_i[n] ≤ c_i α[n], with c_i any finite positive constant.

IV. APPLICATIONS AND NUMERICAL RESULTS · A. Distributed target localization

The paper instantiates NEXT across signal processing, communications, and networking, including cooperative target localization. In target localization, NEXT uses successive convex approximations and distributed averaging, with experiments showing convergence to a common stationary solution and faster progress than D-gradient.

  • IV. APPLICATIONS AND NUMERICAL RESULTS: NEXT is customized for cooperative target localization, spectrum cartography, flow control, and sparse distributed estimation across several application areas.The applications span signal processing, communications, and networking.
  • A. Distributed target localization: The localization task estimates the coordinates of multiple common targets from noisy squared-distance measurements collected by sensor nodes.Each target is represented in 2D or 3D, with target positions constrained by a compact convex geographical set.
  • A. Distributed target localization: The resulting least-squares formulation is nonconvex, making it a direct application of the proposed framework with no regularizer.The geographical constraint is modeled by a compact convex set K.
  • A. Distributed target localization: Two surrogate choices are described: preserving partial convexity by linearizing higher-order terms, or linearizing the entire local objective.The first option retains first- and second-order convex terms of the fourth-order polynomial.
  • A. Distributed target localization: The numerical study uses I = 30 nodes and NT = 3 targets randomly deployed in the unit square, with additive white Gaussian measurement noise.The target positions are specified in the experimental setup, and the noise variance is selected through a minimum-SNR condition.
  • A. Distributed target localization: NEXT-PL and NEXT-L are compared with Dist-Gradient, the only cited distributed gradient method with provable convergence for this problem.For the surrogate-based implementation, the matrix Ai + τIp is independent of the iteration index and needs inversion only once.
  • A. Distributed target localization: J[n] measures progress toward stationarity, D[n] measures consensus disagreement, and NMSE[n] evaluates localization error at the averaged estimate.J[n] equals zero exactly when the averaged iterate is stationary, while D[n] converges to zero under asymptotic agreement.
  • A. Distributed target localization: Across 500 independent noise realizations, all algorithms converged to the same consensual stationary solution, while both NEXT versions were significantly faster than D-gradient.The comparisons use communication exchanges per node, with NEXT requiring 2 · n exchanges when D-gradient uses n iterations.

B. Distributed spectrum cartography in CR networks

NEXT is evaluated for convex spectrum cartography in cognitive-radio networks, where distributed agents estimate the space/frequency power distribution from local measurements under source-power constraints. In a 30-node experiment, NEXT converges faster than several distributed baselines and performs similarly to ADMM while supporting time-varying topologies.

  • Problem formulation: The spectrum-cartography problem estimates primary-source power over spatial and frequency bases from local received-power measurements in a cognitive-radio network.The formulation uses a basis-expansion model, with source powers constrained by K and regularization parameter λ > 0.
  • Problem formulation: The convex instance minimizes local least-squares fitting errors plus the regularizer G(x) = λ 1T x over the constrained source-power vector.The surrogate choice preserves convexity, with τ any positive constant.
  • Numerical example: The experiment uses a time-invariant connected network of I = 30 randomly deployed nodes over a 100 square meter area, with Ns = 2 active transmitters.Each node scans Nb = 10 frequency basis functions and Nf = 30 frequency channels between 15 and 30 MHz.
  • Numerical example: NEXT is compared with D-Gradient, distributed ADMM, D-Nesterov, and distributed ADMM+ using stationarity, consensus disagreement, and NMSE curves averaged over 200 noise realizations.The tested methods are evaluated against the number of local information exchanges.
  • Results: All algorithms converge to the globally optimal solution of (35), while NEXT is significantly faster than D-Gradient, D-Nesterov, and ADMM+ and performs similarly to ADMM.The proposed approach also handles time-varying network topologies, unlike standard ADMM and D-Nesterov as stated in the passage.

C. Flow Control in Communication Networks … V. CONCLUSIONS

The paper applies NEXT to nonconvex flow control, sparse distributed maximum-likelihood estimation, and other networked applications. It concludes that successive convex approximation and dynamic consensus support distributed optimization over time-varying, nonsymmetric networks.

  • C. Flow Control in Communication Networks: Flow control models unidirectional links with fixed capacities and sources transmitting rates within source-specific minimum and maximum bounds.Each source uses a path-specific utility function, while aggregate rates must respect link capacities.
  • C. Flow Control in Communication Networks: Realtime applications such as video streaming and voice over IP produce inelastic traffic modeled by nonconcave utilities, unlike elastic sources’ strictly concave utilities.This distinction motivates treating the flow-control problem as nonconvex.
  • C. Flow Control in Communication Networks: Problem (37) is nonconvex, so standard primal/dual decomposition is inapplicable because of a positive duality gap and parallel SCA requires a fully connected network.NEXT applies because Problem (37) is a special case of the paper’s general formulation.
  • C. Flow Control in Communication Networks: NEXT constructs local flow-control surrogates by retaining the concave component and linearizing the convex component around each source’s current local-copy iterate.The local copy contains transmission-rate variables, including the source’s own rate.
  • D. Sparse Distributed Maximum Likelihood Estimation: Sparse distributed maximum-likelihood estimation combines local log-likelihood terms with an ℓ1 regularizer under a Laplacian prior.The formulation is an instance of the general framework with fi(x) = log pΦ/X(ϕi/x) and G(x) = λ∥x∥1.
  • D. Sparse Distributed Maximum Likelihood Estimation: Unlike classical distributed estimation formulations, the conditional observation densities need not be log-concave in x, yielding generally nonconvex optimization problems.This application therefore extends distributed estimation beyond the log-concave setting.
  • E. Other Applications: NEXT also applies to network localization, multiple vehicle coordination, and resource allocation over vector Gaussian interference channels.The framework’s convergence guarantee holds under weaker conditions than cited prior work, including time-varying topology and networks that are not fully connected.
  • V. CONCLUSIONS: The conclusions characterize NEXT as a best-response-based framework combining successive convex approximation with dynamic consensus in time-varying, nonsymmetric multi-agent networks.Dynamic consensus distributes computation and propagates the information needed across the network.

APPENDIX

The appendix introduces definitions and intermediate results used to prove Theorems 3 and 4, focusing on the evolution of Algorithm 2. It notes that similar results apply to Algorithm 1 as a special case.

  • The appendix develops definitions and intermediate results instrumental to proving Theorems 3 and 4.
  • The analysis proceeds by considering the evolution of Algorithm 2.
  • Similar results apply to Algorithm 1 as a special case.

A. Notation and preliminary results

This section establishes the notation and preliminary convergence tools used to analyze Algorithm 2. It characterizes consensus-error decay, best-response properties, transition-matrix behavior, and iterate evolution.

  • Consensus error dynamics: The consensus error ∥x_i[n] − x̄_i[n]∥ asymptotically vanishes, providing a key ingredient for proving Theorems 3 and 4.The result concerns the distance between agents’ variables and their average-consensus counterparts.
  • Properties of bxi(•): Under Assumption A and F1–F3, each best-response map bxi(•) is Lipschitz continuous on K.The proposition states that a positive constant bLi exists for each map.
  • Properties of bxi(•): The fixed points of bxi(•) coincide with the stationary solutions of Problem (1), and bxi(z) has a fixed point.These fixed-point properties are part of Proposition 5.
  • Transition matrices and their properties: Transition matrices P[n, l] and bP[n, l] describe the evolution of Algorithm 2’s agent variables under time-varying mixing matrices W[n].The matrices are defined through products of W[n] and c W[n], respectively.
  • Transition matrices and their properties: Under topology assumptions B1–B2, P[n, l] − 1/I 11^T decays geometrically, enabling consensus among agent variables.This is the conclusion of Lemma 6.
  • On the iterates x[n] and x̄[n]: Combining Algorithm 2 relations S.2(b) and S.3(a) yields a compact recursion for x[n], while the average vector x̄[n] has a corresponding evolution.These recursions are used in forthcoming proofs.

B. Consensus Achievement

Proposition 9 establishes the convergence properties underlying Algorithm 2: bounded disagreement, asymptotic agreement among agents’ estimates, vanishing tracking error, and agreement on best-responses. These results connect the agents’ estimate sequence to the centralized best-response behavior needed for convergence.

  • Proposition 9: The agents’ estimate disagreements remain bounded for all iterations.This is the proposition’s bounded-disagreement property.
  • Proposition 9: The agents asymptotically agree on their estimates, with inter-agent disagreement vanishing as n →∞.The proof uses the disagreement component x⊥[n] and shows its norm converges to zero.
  • Proposition 9: Each agent’s tracking error asymptotically vanishes.The proposition establishes this property for the relevant local tracking quantities, with the proof relying on bounded disagreement and consensus arguments.
  • Proposition 9: The agents asymptotically agree on their best-responses.The proof derives this from estimate consensus together with bounds on the best-response and tracking discrepancies.

C. Proof of Theorems 3 and 4

The proof establishes Theorem 4 through descent and summability arguments, with Theorem 3 obtained as a special case. The iterates’ surrogate gaps vanish asymptotically, and every limit point is a stationary solution of Problem (1).

  • Theorem 4 is proved directly, while Theorem 3 follows as a special case.
  • Applying Lemma 8 shows that U(¯x[n]) converges to a finite value and that the weighted surrogate-gap sequence is summable.The proof uses n=1 Z[n] < ∞ and coercivity of U(¯x[n]).
  • The surrogate gaps vanish asymptotically: lim n→∞ ∥bxi(¯x[n]) −¯x[n]∥= 0 for every agent i.This conclusion follows from the summability result together with (12).
  • Because {¯x[n]}n is bounded, it has a limit point ¯x∞∈K, and continuity of bxi(•) transfers the vanishing-gap property to that point.Boundedness follows from A6 and convergence of {U(¯x[n])}n.
  • By Proposition 5(b), ¯x∞ is a stationary solution of Problem (1), proving statement (a); statement (b) follows from (62).
Loading 1602.00591v1…