PaperlayerView exact revision on arXiv

Source-linked AI summary

Push-Pull Gradient Methods for Distributed Optimization in Networks

Shi Pu, Wei Shi, Jinming Xu, Angelia Nedić

arXiv:1810.06653v4math.OCcs.DCcs.MAcs.SI

TL;DR

The paper addresses distributed convex optimization when agents know separate local objectives and communicate over directed networks. It introduces Push-Pull methods that separately exchange decision and gradient information, including a random-gossip variant, and proves linear convergence under strongly convex and smooth objectives. The methods also unify decentralized, centralized, and semi-centralized architectures and include directed-graph gossip optimization.

  • Problem

    Agents must collaboratively minimize the sum of locally known convex cost functions while obeying network connectivity and relying on local neighbor communication.

  • Method

    Push-Pull methods maintain estimates of the decision variable and average gradient, using two graphs with gradients pushed and decision information pulled; G-Push-Pull extends this to random gossip.

  • Results

    The proposed methods converge linearly for strongly convex and smooth objectives in synchronous and asynchronous random-gossip settings over directed networks.

  • Takeaways & Limitations

    The methods support decentralized, centralized, and semi-centralized architectures and make directed-graph random-gossip optimization possible.

Abstract

from arXiv · show

In this paper, we focus on solving a distributed convex optimization problem in a network, where each agent has its own convex cost function and the goal is to minimize the sum of the agents' cost functions while obeying the network connectivity structure. In order to minimize the sum of the cost functions, we consider new distributed gradient-based methods where each node maintains two estimates, namely, an estimate of the optimal decision variable and an estimate of the gradient for the average of the agents' objective functions. From the viewpoint of an agent, the information about the gradients is pushed to the neighbors, while the information about the decision variable is pulled from the neighbors hence giving the name "push-pull gradient methods". The methods utilize two different graphs for the information exchange among agents, and as such, unify the algorithms with different types of distributed architecture, including decentralized (peer-to-peer), centralized (master-slave), and semi-centralized (leader-follower) architecture. We show that the proposed algorithms and their many variants converge linearly for strongly convex and smooth objective functions over a network (possibly with unidirectional data links) in both synchronous and asynchronous random-gossip settings. In particular, under the random-gossip setting, "push-pull" is the first class of algorithms for distributed optimization over directed graphs. Moreover, we numerically evaluate our proposed algorithms in both scenarios, and show that they outperform other existing linearly convergent schemes, especially for ill-conditioned problems and networks that are not well balanced.

I. INTRODUCTION

The paper develops distributed gradient methods for convex optimization over networked agents, targeting consensus on the minimizer using local neighbor communication. Push-Pull and G-Push-Pull address directed networks, unify multiple architectures, and establish linear convergence under synchronous and random-gossip updates.

  • Problem and motivation: Each agent knows only its own convex cost function, while the network must collaboratively minimize their sum through local communications.Local exchange is motivated by limited communication resources and the high cost of transmitting large amounts of data.
  • Proposed methods: Push-Pull uses row-stochastic mixing for decision variables and column-stochastic mixing for average-gradient tracking in directed graphs.The method supports fully decentralized and two-tier networks.
  • Random-gossip setting: G-Push-Pull activates agents through random gossip, with one agent waking uniformly at random and communicating with one or two neighbors.Gossip protocols are considered because they have low communication costs.
  • Proposed methods: The proposed methods use two graphs and unify decentralized, centralized, and semi-centralized computational and communication architectures.The architectures correspond to peer-to-peer, master-slave, and leader-follower settings.
  • Convergence results: The methods and variants converge linearly for strongly convex and smooth objectives in synchronous and asynchronous random-gossip settings.The paper identifies G-Push-Pull as the first class of gossip-type distributed optimization algorithms for directed graphs.
  • Algorithmic flexibility: Each agent may use a different nonnegative stepsize, with only one stepsize required to be positive.The paper presents this as a distinctive feature relative to existing literature.

II. A PUSH-PULL GRADIENT METHOD

Push-Pull combines row-stochastic decision-variable mixing with column-stochastic gradient tracking over directed network graphs. Its push and pull information flows are designed to satisfy the optimization optimality conditions under shared-root connectivity assumptions.

  • Algorithm design: Push-Pull uses row-stochastic mixing for decision variables and column-stochastic mixing for tracking average gradients.The algorithm splits the doubly stochastic role across matrices R and C.
  • Algorithm design: Each agent pulls decision information from in-neighbors and pushes gradient information to out-neighbors.The x-state performs consensus-based optimization, while the y-state tracks the average gradient.
  • Network assumptions: The graph assumptions require spanning trees in GR and GC⊺ with at least one common root.This is weaker than requiring both graphs to be strongly connected.
  • Network assumptions: The shared-root set RR∩RC⊺ must contain an agent with a positive stepsize.This condition ensures the effective stepsize is positive and supports the optimality argument.
  • Interpretation: Under the limiting relations, the x-state reaches consensus while the y-state tracks the average gradient, yielding the optimization optimality conditions.The limiting gradient sum is zero, and the limiting decision state satisfies consensus and stationarity.

A. Unifying Different Distributed Computational Architecture

Push-Pull can represent decentralized, centralized, and semi-centralized computation by assigning separate information-flow graphs to decision and gradient exchanges. Its convergence theorem establishes linear convergence under stated stepsize conditions.

  • Architecture unification: Push-Pull unifies decentralized, centralized, and semi-centralized architectures through two information-exchange graphs.The paper identifies this cross-architecture property as a main contribution.
  • Centralized architecture: In a star network, the center receives pulled decision information from the network and receives pushed gradient information from the peripheral nodes.This makes the method operate as a centralized master-slave algorithm for the peripheral objectives.
  • Semi-centralized architecture: Replacing individual star nodes with subnets yields semi-centralized architectures with decentralized subnet structure and master-slave relations between layers.Follower information is diffused toward the leader layer, while leader information reaches follower layers.
  • Convergence: Theorem 1 states that the optimization, consensus, and gradient-tracking errors converge linearly at rate O(ρ(A)^k) with ρ(A)<1.The result applies when the listed assumptions and stepsize conditions hold.
  • Caveat: The stepsize upper bound may be conservative because the proof uses a small-gain-style argument, although simulations report a large feasible stepsize region.The paper leaves tighter analytical upper bounds open.
  • Convergence: For sufficiently small stepsizes, Push-Pull has convergence behavior comparable to centralized gradient descent, with speed determined by agents in RR∩RC⊺.The effective stepsize is α′ = 1/n Σ_i u_i v_i α_i.

A. Preliminary Analysis

The preliminary analysis reduces convergence to a coupled system controlling optimization error, consensus disagreement, and gradient-tracking error. Linear convergence follows when the associated transition matrix has spectral radius below one.

  • Error bounds: Gradient smoothness bounds the average-gradient tracking error and gradient magnitude using the optimization and consensus errors.The supplied inequalities involve the smoothness constant L and √n.
  • Matrix contraction: The disagreement dynamics of R and C contract because their disagreement spectral radii satisfy ρR<1 and ρC<1.Special matrix norms are chosen with induced contraction factors close to these spectral radii.
  • Error variables: The analysis tracks optimization error, decision consensus error, and gradient-tracking error as three coupled quantities.These are bounded through a linear system of inequalities.
  • Spectral-radius criterion: All three error quantities converge linearly at rate O(ρ(A)^k) when the transition matrix satisfies ρ(A)<1.The spectral-radius condition is the central criterion for the subsequent convergence proof.

C. Proof of Theorem 1

The proof establishes convergence by enforcing diagonal contraction and a positive determinant condition for the irreducible transition matrix. The section also introduces the generalized random-gossip Push-Pull setting and its stochastic update structure.

  • Proof conditions: The proof obtains a quadratic stepsize inequality and combines it with the diagonal bounds to derive an upper bound on the maximum stepsize.Irreducibility of A completes the spectral-radius argument.
  • Random-gossip extension: G-Push-Pull is a generalized random-gossip algorithm in which randomly selected agents communicate with one or two neighbors.The gossip mechanism can activate isolated depth-1 trees and permits push-only or pull-only network structures.
  • Random-gossip extension: The illustrated gossip update lets an activated agent send its decision state while sharing portions of its gradient-tracking state with selected neighbors.The example shows pulled x-information and partial y-information aggregation.
  • Random-gossip extension: In G-Push-Pull, Rk is row-stochastic and Ck is column-stochastic, preserving the push-pull separation in the time-varying updates.The random matrix Qk records the agents involved in an activation.

V. CONVERGENCE ANALYSIS FOR G-PUSH-PULL

The G-Push-Pull analysis transforms the network dynamics into spectral and norm-based relations, then establishes linear convergence through a system of inequalities.

  • Convergence framework: G-Push-Pull convergence is reduced to bounding optimization error, consensus disagreement, and gradient-tracking disagreement through linear combinations of prior values.The proof uses specific norms and a linear system of inequalities.
  • Convergence result: The analysis establishes sufficient spectral conditions for the transition matrix to yield linear convergence of all three error quantities.The condition is ρ(B) < 1, where B is the transition matrix defined in the theorem.
  • Spectral properties: The averaged matrices have a unique zero eigenvalue, while all remaining eigenvalues lie inside the unit circle centered at (−1, 0).This property follows from row-stochasticity and the existence of a spanning tree.
  • Matrix decomposition: The matrices are decomposed into similarity transforms whose first rows are the relevant left eigenvectors.Rescaling generalized eigenvectors makes the superdiagonal entries arbitrarily close to zero.

B. Supporting Lemmas

Supporting lemmas control the transformed norms, stochastic perturbations, and transition dynamics needed to prove G-Push-Pull’s linear convergence.

  • Norm construction: The proof uses norms induced by the similarity matrices S and D, together with constants relating those norms to the Euclidean norm.The norm equivalence constants are supplied by Lemma 15.
  • Supporting bounds: The perturbation matrices satisfy ˜R_k = γ˜T_k and ˜C_k = γ˜E_k, linking random deviations to the stepsize.These relations support the subsequent norm bounds.
  • Supporting bounds: For sufficiently small γ, the transformed consensus factors satisfy σ̄_R < 1 and σ̄_C < 1.The corresponding thresholds are γ̄_R and γ̄_C.
  • Transition system: Under Assumptions 1–3, the error quantities obey a component-wise linear system whose transition matrix B is used in the main convergence theorem.The matrix entries are specified separately in the supporting result.

C. Proof of Theorem 2

The proof of Theorem 2 shows that suitably chosen stepsizes make the transition matrix contractive, yielding the required spectral-radius condition.

  • Contractivity condition: A sufficient condition for ρ(B) < 1 requires b11, b22, and b33 to be below one and det(I − B) > 0.The determinant is expanded into diagonal and coupling terms.
  • Stepsize selection: The stepsize α is selected to satisfy inequalities that bound diagonal entries of B using σ̄_R, σ̄_C, and problem constants.These inequalities are used to control the three error components.
  • Stepsize selection: The remaining sufficient inequality is rewritten as c4α^2 + c5α − c6 < 0, with c6 > 0.This scalar inequality completes the stepsize argument.

VI. SIMULATIONS

Simulations on directed sensor networks compare Push-Pull and G-Push-Pull with existing methods in fixed and asynchronous random-gossip settings.

  • Experimental setup: The sensor-fusion experiment uses a randomly generated directed sensor network with n = 20, p = 20, s = 1, and λ_i = 0.01.The local costs are described as ill-conditioned, motivating coordination among agents.
  • Fixed directed network: In the fixed directed-network experiment, Push-Pull permits much larger stepsizes and converges faster than Push-DIGing and Xi-Row.Stepsizes are hand-optimized for each method to make the comparison fair.
  • Asynchronous random gossip: In asynchronous random gossip, G-Push-Pull is compared with Push-DIGing using randomly activated links and results averaged over 20 runs.The setting uses Bernoulli link activation and push-notification or pull-notification wakeups.
  • Asynchronous random gossip: G-Push-Pull allows much larger stepsizes, avoids the spikes observed for Push-DIGing, and converges linearly and steadily to the optimum.The passage attributes Push-DIGing’s spikes to division operations whose divisors can scale badly.

APPENDIX A PROOFS FOR PUSH-PULL

The appendix establishes positivity and spectral properties of network matrices, then bounds optimization, consensus, and gradient-tracking errors to support convergence analysis.

  • Eigenvector properties: The left and right Perron eigenvectors are positive on the relevant root and cabal vertex sets, yielding u^T v > 0.The proof uses irreducibility, Perron-Frobenius theory, and the assumption that the two sets intersect.
  • Error bounds: The gradient-tracking discrepancy is bounded by L√n times the primal consensus error.The bound follows from Lipschitz continuity of the agents' gradients.
  • Error bounds: The gradient magnitude is bounded by L times the distance between the network average and the optimizer.This relates the average gradient estimate to optimization error.
  • Spectral contraction: The nontrivial spectral radii satisfy σ_R < 1 and σ_C < 1.The proof uses Perron-Frobenius properties and excludes the unit eigenvector from the relevant disagreement subspaces.
  • Coupled recursions: The recursion bounds primal disagreement using σ_R and gradient-tracking disagreement using σ_C, with coupling through optimization and consensus errors.These inequalities form the contraction estimates for the push-pull dynamics.

APPENDIX B PROOFS FOR G-PUSH-PULL

The appendix develops conditional-expectation bounds for the random-gossip analysis by decomposing gradient errors and controlling their interaction with optimization error.

  • Stochastic recursion: The random-gossip analysis takes conditional expectations of the one-step error relation.This converts the stochastic update into an expected recursion.
  • Stochastic recursion: The inner-product term is decomposed into the average optimization error and the gradient-estimation discrepancy.The resulting bound uses strong convexity for the optimization component.
  • Error decomposition: The squared gradient term is bounded by twice the squared tracking discrepancy plus twice the squared average-gradient norm.This follows from splitting the gradient estimate into tracking error and average gradient.

B. Proof of Lemma 16

The proof of Lemma 16 derives successive inequalities from earlier lemmas and assumptions to bound the remaining terms in the convergence recursion.

  • Proof steps: The first inequality follows directly from Lemmas 14 and 15.The proof invokes these lemmas without introducing an additional estimate.
  • Proof steps: The second inequality is obtained from relation (25).The argument applies the previously established inner-product bound.
  • Proof steps: The final inequality combines relation (26) with Lemma 13.This controls the last terms in the recursive estimate.
  • Proof steps: Relation (22) and Assumption 1 are used to bound the combined squared norms of the tracking and averaged-gradient terms.The resulting expression contains 2(∥y_k − v̄y_k∥_2^2 + ∥v̄y_k∥_2^2).
Loading 1810.06653v4…