PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence of a Multi-Agent Projected Stochastic Gradient Algorithm for Non-Convex Optimization

Pascal Bianchi, Jérémie Jakubowicz

arXiv:1107.2526v3math.OCcs.DCeess.SY

TL;DR

The paper investigates a distributed optimization problem of practical interest and develops a convergence-analysis framework for constrained, non-convex optimization. Its analysis models gossip weights through matrix sequences and shows consensus, with average estimates converging almost surely to the set of KKT points.

  • Problem

    The paper investigates a distributed optimization problem of practical interest.

  • Method

    The framework analyzes matrix sequences of gossip weights and an interpolated process treated as a perturbed solution.

  • Results

    The algorithm converges to consensus, while the average estimate converges almost surely to the set of KKT points.

  • Takeaways & Limitations

    The framework addresses constrained non-convex optimization and does not require double-stochastic gossip matrices, encompassing natural broadcast gossip.

Abstract

from arXiv · show

We introduce a new framework for the convergence analysis of a class of distributed constrained non-convex optimization algorithms in multi-agent systems. The aim is to search for local minimizers of a non-convex objective function which is supposed to be a sum of local utility functions of the agents. The algorithm under study consists of two steps: a local stochastic gradient descent at each agent and a gossip step that drives the network of agents to a consensus. Under the assumption of decreasing stepsize, it is proved that consensus is asymptotically achieved in the network and that the algorithm converges to the set of Karush-Kuhn-Tucker points. As an important feature, the algorithm does not require the double-stochasticity of the gossip matrices. It is in particular suitable for use in a natural broadcast scenario for which no feedback messages between agents are required. It is proved that our result also holds if the number of communications in the network per unit of time vanishes at moderate speed as time increases, allowing for potential savings of the network's energy. Applications to power allocation in wireless ad-hoc networks are discussed. Finally, we provide numerical results which sustain our claims.

I. INTRODUCTION

The paper studies constrained distributed optimization with non-convex, noisy local utilities, using local stochastic gradients and gossip-based consensus. It addresses communication and stepsize limitations in prior approaches while targeting convergence to critical or KKT points.

  • Problem setting: Each agent knows the shared compact convex constraint set but observes only its own possibly noisy utility, so cooperation is needed to minimize the global objective.The local utilities may be non-convex and continuously differentiable.
  • Prior approaches: Incremental methods circulate an estimate through the network and generally require a Hamiltonian cycle, whose discovery is NP-complete.Some relaxations still require substantial routing.
  • Proposed approach: The proposed cooperation approach combines local gradient algorithms with simultaneous communication, allowing agents to combine neighboring estimates through gossip.Each agent maintains its own estimate while the network moves toward agreement.
  • Communication model: Most prior gossip analyses assume doubly stochastic matrices, but column-stochasticity imposes feedback requirements that exclude natural broadcast schemes.Broadcast allows an agent to transmit to neighbors without expecting immediate feedback.
  • Communication model: The framework removes the double-stochasticity requirement and thereby supports broadcast-based constrained distributed optimization.This extends the applicability of gossip methods to communication settings without immediate feedback.
  • Open limitations: Compared with a prior broadcast algorithm, the paper seeks greater flexibility because that method updates only receiving agents and relies strongly on a specific stepsize.Its convergence condition requires the stepsize to vanish at speed 1/n, whereas practical use may favor leeway to avoid slow convergence.

Contributions

The paper develops a distributed projected stochastic-gradient framework for constrained non-convex optimization, combining local noisy gradient updates with gossip communication. Under stated assumptions, agent estimates asymptotically reach consensus and converge almost surely to KKT points, without requiring doubly stochastic gossip matrices.

  • Framework: The framework analyzes distributed projected stochastic-gradient algorithms for constrained optimization with continuously differentiable, possibly non-convex utility functions.The analysis does not rely on convexity properties and uses perturbed differential inclusions.
  • Algorithm: Each agent performs a projected local stochastic-gradient update followed by a gossip step using decreasing deterministic stepsizes.The stochastic direction is modeled as a negative local gradient plus martingale-difference noise, and the gossip step combines temporary estimates.
  • Convergence: Almost surely, every agent’s estimate shadows a differential variational inequality and eventually converges to the set of KKT points.The result concerns the sequence of estimates of any agent under the paper’s assumptions.
  • Communication: The assumptions allow gossip matrices that are not doubly stochastic, requiring only column stochasticity on average.This includes the natural broadcast scheme, where relaxing column stochasticity introduces a noise-like term that does not prevent convergence to KKT points.
  • Communication: The convergence result remains valid when communications per unit time vanish at a moderate speed as time increases.The setting is motivated by reducing communication overhead in wireless networks.
  • Applications: The paper applies the convergence results to power allocation in wireless networks and reports numerical results supporting its claims.The stated applications and numerical results appear after the theoretical development.

C. Illustration: Some Examples of Gossip schemes

The paper illustrates pairwise and broadcast gossip schemes on a network graph. Pairwise gossip exchanges temporary estimates between neighboring nodes, whereas broadcast gossip updates neighbors without requiring feedback from the transmitter.

  • Schemes: The paper focuses on pairwise and broadcast gossip schemes over a network represented by a nondirected graph.The graph consists of nodes and edges connecting agents, and the schemes provide corresponding sequences of gossip matrices.
  • 1) Pairwise Gossip: In pairwise gossip, a randomly selected node chooses a neighbor, and the two agents exchange temporary estimates and compute a weighted average.With β = 1/2, other nodes retain their temporary estimates.
  • 1) Pairwise Gossip: The pairwise gossip matrix is doubly stochastic, and its spectral-radius condition holds if and only if the graph is connected.The matrices form an i.i.d. sequence in this scheme.
  • 2) Broadcast Gossip: In broadcast gossip, a randomly selected node transmits its temporary update to all neighbors, which compute weighted averages with it.Nodes outside the transmitter’s neighborhood, including the transmitter itself, retain their temporary estimates.
  • 2) Broadcast Gossip: The broadcast transmitter does not expect feedback from its neighbors, making the scheme suitable for natural broadcast communication.This distinguishes broadcast gossip from the pairwise exchange procedure.
  • 2) Broadcast Gossip: Broadcast gossip matrices are not doubly stochastic, but their expectations are column stochastic; the spectral-radius condition holds exactly for connected graphs.The average column-stochasticity property is the condition used by the convergence framework.

III. CONVERGENCE W.P.1

Under the stated regularity assumptions, the algorithm achieves consensus almost surely and drives the average estimate toward KKT points through a set-valued dynamical-systems analysis.

  • Assumptions: The feasible set G is nonempty and compact, with convex continuously differentiable inequality constraints and linearly independent active gradients.The framework also assumes a regularity qualification and removes redundant constraints.
  • Main result: The average estimate converges almost surely to a connected component of the KKT-point set L.If L contains only isolated points, the average converges almost surely to one of them.
  • Main result: Consensus is achieved almost surely: the maximum pairwise disagreement |θn,i −θn,j| converges to zero.Equivalently, the disagreement vector θ⊥,n converges almost surely to zero.
  • Main result: When f is convex, the average estimate converges to the set of global solutions of the constrained minimization problem.The convergence result itself does not rely on convexity of f, so nonconvex objectives need not yield global solutions.
  • Proof strategy: The proof first establishes consensus, then analyzes the average estimate using a noisy discrete dynamical system and differential inclusions.The function f serves as a Lyapunov function for the KKT-point set under the induced dynamics.

B. Preliminaries: Useful Facts about Set-Valued Dynamical Systems

The preliminaries define perturbed differential-inclusion solutions and establish the consensus lemma needed to reduce the network analysis to the average estimate.

  • Perturbed solutions: A perturbed solution asymptotically shadows a differential inclusion over every fixed-length time window.Its perturbation terms decay appropriately, although the trajectory need not remain close to one fixed solution from an initial time.
  • Preliminary theorem: A bounded perturbed solution converges to the relevant invariant set when a Lyapunov function has an image with empty interior.This result is invoked from the cited differential-inclusion framework.
  • Agreement: Under the agreement lemma, the disagreement vector has finite expected squared-norm sum and converges almost surely to zero.This establishes asymptotic agreement among the agents.
  • Agreement proof: The consensus proof uses the invariance of the consensus subspace under the gossip matrices and bounds the projected stochastic perturbations.The argument controls the disagreement recursion through matrix products and conditional expectations.
  • Agreement: The pairwise disagreement criterion is equivalent to consensus of the agents’ local estimates.The whole-vector analysis can therefore be reduced to the average estimate after consensus is established.

D. Average Estimate

The average estimate is represented as a stochastic approximation with projection-induced errors, then connected to a perturbed differential inclusion whose perturbations vanish asymptotically.

  • Average recursion: The average recursion contains the projected-gradient drift, a stochastic noise term, a projection correction, and a remainder term.This decomposition is formalized by Proposition 1.
  • Average recursion: When the projector is inactive, the average recursion reduces asymptotically to a classical noisy approximation of gradient dynamics.The projector is inactive when the unconstrained update remains in the feasible product set.
  • Average recursion: The projection correction may persist, depends on the whole network state, and is generally discontinuous as a function of the state.These properties prevent direct application of standard stochastic-approximation arguments.
  • Technical conditions: The technical growth condition on the objective outside the feasible set is harmless here because the iterates remain restricted to the bounded set G.The paper also describes a possible redefinition outside G to enforce the condition.
  • Projection analysis: For small stepsizes and small disagreement, projection effects can be approximated by combinations of gradients of nearby active constraints.Constraint qualification and continuity properties control the approximation error as the stepsize and disagreement vanish.
  • Interpolated process: The interpolated average process is a perturbed solution of the differential inclusion, with perturbation quantities converging almost surely to zero.This follows from the vanishing stepsize, disagreement, remainder, and noise contributions.

F. Study of the Differential Inclusion Dynamics

The limiting differential inclusion evolves along feasible tangent directions, and the objective function acts as a Lyapunov function for the set of KKT points.

  • Differential inclusion: The differential inclusion selects feasible dynamics by projecting the negative gradient onto the tangent cone of G.The tangent-cone projection describes the constrained continuous-time limit.
  • Lyapunov analysis: The objective f is a Lyapunov function for the KKT-point set L under the differential-inclusion dynamics.The result is stated in Proposition 5 and identifies KKT points as the limiting set.
  • Differential inclusion: The normal and tangent cones are dual, enabling an orthogonal decomposition of the negative gradient into feasible and constraint-normal components.This decomposition underlies the Lyapunov analysis.

V. APPLICATION: POWER ALLOCATION IN AD-HOC WIRELESS NETWORKS

The paper applies its distributed constrained optimization algorithm to power allocation in ad-hoc interference networks. Destinations cooperatively estimate a global power vector while using only local channel information and communicate it to their sources.

  • Network model: The application considers an N-pair interference channel where each destination observes noise and interference from other sources.The useful received signal at destination i depends on its source's power and channel gain, while other sources contribute interference.
  • Information assumptions: Each transmitter has no CSIT, while destination i knows its incoming channel-gain vector and ignores channel gains associated with other destinations.This partitions channel knowledge across agents and supports locally computed utility functions.
  • Distributed algorithm: Destinations connected by a graph jointly estimate a power allocation vector, then each destination sends its component p_i to its corresponding source.Each agent estimates the full vector, including other users' power allocations, rather than only its own component.
  • Convergence: Under the stated assumptions, the distributed algorithm's average estimate converges to the set of KKT points.The stochastic extension accommodates destinations observing independent identically distributed random channel-gain sequences.

VI. NUMERICAL RESULTS

The numerical study compares pairwise and broadcast gossip algorithms on convex and distributed optimization scenarios. Across the reported experiments, pairwise gossip performs at least as well as the broadcast methods, while broadcast optimizers still converge in the optimization setting.

  • Experimental setup: The experiments compare pairwise and broadcast algorithms on complete and cycle graphs with N = 10 or N = 50 agents.The study uses 50 Monte-Carlo runs of 10000 iterations and evaluates deviation from the global minimizer.
  • Scenario #1: Pairwise gossip performs at least as well as both broadcast-based algorithms in the reported experiments.This contrasts with average-consensus results, where broadcast gossip can be faster but fail to reach the desired value.
  • Scenario #1: The theoretical analysis shows that broadcast-based optimizers converge to the desired value, but the example provides no clear gain from using broadcast.The analysis attributes a perturbation term to non-doubly-stochastic gossip matrices; this term vanishes for doubly-stochastic matrices.
  • Conclusion: The study concludes that meaningful comparisons between pairwise and broadcast optimizers remain an important direction.The reported behavior motivates comparing convergence and communication trade-offs across the two schemes.

B. Scenario #2

This scenario evaluates distributed power allocation on a 2 × 2 interference channel with fixed and time-varying channel gains. Both gossip schemes converge to the desired allocation, while pairwise trajectories are smoother and faster in the reported cases.

  • Fixed-channel experiment: The fixed-channel experiment uses maximum powers P_1 = P_2 = 10 and minimizes weighted error probabilities with β_1 = 2/3 and β_2 = 1/3.The channel gains are A_1,1 = A_2,2 = 2, A_1,2 = A_2,1 = 1, with noise variances σ_1^2 = σ_2^2 = 0.1.
  • Fixed-channel experiment: The objective has a unique minimum at (p_1, p_2) = (10, 5.4).The objective surface is plotted using 10 log_10 p_1 and 10 log_10 p_2 as the two axes.
  • Fixed-channel experiment: Pairwise convergence is smoother, whereas broadcast convergence is more erratic because its gossip matrices are not doubly stochastic.The paper identifies the induced artificial noise term as the main cause of the broadcast trajectory's erratic shape.
  • Time-varying channels: With Rician fading and random time-varying channel gains, both distributed algorithms converge, but the pairwise case converges faster.The trajectories are averaged over 50 Monte-Carlo runs.

APPENDIX I

The appendix establishes the stochastic and variational ingredients supporting convergence. It controls martingale noise and perturbation terms, proves asymptotic consensus, and connects limit points to KKT conditions.

  • Consensus: The disagreement between the average estimate and each agent's estimate converges almost surely to zero.Uniform continuity of the gradients then implies that the associated perturbation term r_n also converges almost surely to zero.
  • Noise control: The proof shows that the martingale sequence has uniformly bounded second moments and converges almost surely to a finite random variable.This uses conditional independence, bounded noise moments, and the stated assumptions on the gossip and observation processes.
  • Variational analysis: The proof analyzes the smallest eigenvalue of Q(θ)^TQ(θ) using lower semicontinuity, compactness, and active-set continuity.These properties establish a strictly positive lower bound under the relevant regularity assumption.
  • Perturbation analysis: A decomposition of the gradient error into s_γ(θ), t_γ(θ), and u_γ(θ) controls the effects of projection, disagreement, and gradient variation.The argument uses continuity, compactness, and tightness of the noise distributions to show the resulting error terms vanish.
  • Conclusion: The appendix completes the convergence proof by combining the vanishing perturbations with the differential variational inequality framework.The resulting limit characterization supports convergence to the KKT set under the paper's assumptions.

APPENDIX IV

Appendix IV establishes that approximate active-constraint sets converge to exact constraint sets on the compact feasible region. It also shows that limit points satisfying vanishing constraint residuals belong to the target set.

  • The contradiction argument proves δ(ϵ)→0 by extracting a recurring subset E from the finitely many constraint subsets.The proof excludes the empty-set case because its Hausdorff distance would be zero.
  • The sequence (θ_n) lies in compact G, so it has a convergent subsequence with limit θ⋆∈G.
  • Continuity of q_j and ϵ_n↓0 imply q_j(θ⋆)=0, placing θ⋆ in T.
  • The proof uses Lipschitz continuity of each convex q_j on compact G to control constraint-residual changes.
  • For sufficiently small ϵ, each θ∈G has a nearby θ′ whose exact active-constraint set contains A(θ,ϵ).The distance is bounded by δ(ϵ), and δ(ϵ) tends to zero as ϵ↓0.
  • For any E with a sequence of vanishing residual tolerances, every limit point of the associated approximate sets satisfies the corresponding exact constraints.
Loading 1107.2526v3…