Source-linked AI summary
Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs
Angelia Nedich, Alex Olshevsky, Wei Shi
TL;DR
The paper asks how to achieve linear convergence for distributed optimization over time-varying undirected and directed graphs. It proposes DIGing and Push-DIGing, combining gradient tracking with consensus and push-sum ideas. Under strong convexity and sufficiently small fixed step-sizes, both methods converge geometrically, with polynomial agent scaling established for DIGing on undirected graphs.
Problem
The central gap is constructing linearly convergent distributed optimization methods for time-varying undirected or directed graphs.
Method
The paper develops DIGing for undirected graphs and Push-DIGing for directed graphs, using consensus-based gradient tracking and push-sum to handle column-stochastic mixing.
Results
Under strong convexity and sufficiently small fixed step-sizes, the algorithms achieve R-linear convergence; DIGing has polynomial iteration complexity in the number of agents on undirected graphs.
Takeaways & Limitations
The methods provide geometric convergence over time-varying graphs while requiring only bounds on network size and long-term connectivity for theorem-guaranteed step-size selection.
Takeaways & Limitations
The paper leaves improved convergence-rate estimates, especially in scaling with the number of agents, and extensions to locally constrained or coupled objectives as open directions.
Abstract
from arXiv · showhide
This paper considers the problem of distributed optimization over time-varying graphs. For the case of undirected graphs, we introduce a distributed algorithm, referred to as DIGing, based on a combination of a distributed inexact gradient method and a gradient tracking technique. The DIGing algorithm uses doubly stochastic mixing matrices and employs fixed step-sizes and, yet, drives all the agents' iterates to a global and consensual minimizer. When the graphs are directed, in which case the implementation of doubly stochastic mixing matrices is unrealistic, we construct an algorithm that incorporates the push-sum protocol into the DIGing structure, thus obtaining Push-DIGing algorithm. The Push-DIGing uses column stochastic matrices and fixed step-sizes, but it still converges to a global and consensual minimizer. Under the strong convexity assumption, we prove that the algorithms converge at R-linear (geometric) rates as long as the step-sizes do not exceed some upper bounds. We establish explicit estimates for the convergence rates. When the graph is undirected it shows that DIGing scales polynomially in the number of agents. We also provide some numerical experiments to demonstrate the efficacy of the proposed algorithms and to validate our theoretical findings.
1. Introduction.
The paper addresses the open problem of achieving linear convergence for distributed optimization over time-varying undirected or directed graphs. It develops distributed methods using consensus and gradient-tracking ideas, establishes geometric convergence under strong convexity, and shows polynomial scaling for DIGing on undirected graphs.
- Motivation: The paper targets distributed optimization over time-varying networks, where agents hold private objectives and communicate only with immediate neighbors.Such problems arise in information processing, networked coordination, distributed estimation, and learning.
- Main approach and result: The proposed algorithms use consensus ideas to estimate the global gradient and achieve R-linear convergence when at least one objective function is strongly convex.R-linear convergence is geometric but need not imply monotonic decrease of the error norm.
- Literature gap: Prior methods faced limitations including special ring-network requirements, diminishing step-sizes, or unavailable linear-convergence guarantees over time-varying graphs.The paper identifies constructing a linearly convergent method for time-varying undirected or directed graphs as an open question.
- Contributions: The paper resolves the open question by constructing linearly convergent methods for time-varying directed graphs and obtaining polynomial iteration complexity for a distributed weight choice on undirected graphs.The directed-graph result addresses the difficulty of using doubly stochastic weights in changing directed networks.
- Analysis and implementation: The convergence analysis uses the small-gain theorem, and the protocols require sufficiently small step-sizes based on bounds on network size and long-term connectivity.These requirements compare favorably with methods needing detailed spectral network information for step-size selection.
2. Distributed Optimization over Undirected Graphs.
The section motivates DIGing by showing why local gradients disrupt consensus and then replaces the unavailable global gradient average with distributed gradient tracking over time-varying undirected graphs. It presents the DIGing updates and relates them to EXTRA and primal-dual approaches.
- Motivation: Distributed gradient descent can leave a consensual global minimizer because each agent uses its local gradient, which need not vanish there.At a global solution, the summed gradients are zero, but individual gradients generally are not.
- Motivation: A centralized correction would use the average of all agents’ gradients, but that update is not distributed because it requires a central entity.The average is evaluated on agents’ local copies.
- DIGing algorithm: DIGing replaces the average gradient with a dynamically tracked approximation and replaces a static mixing matrix with W(k) for time-varying graphs.The method combines consensus mixing with gradient tracking.
- DIGing algorithm: DIGing initializes y(0)=∇f(x(0)) and iterates x(k+1)=W(k)x(k)−αy(k), y(k+1)=W(k)y(k)+∇f(x(k+1))−∇f(x(k)).Each agent maintains a local solution estimate and average-gradient estimate, exchanges both with neighbors, and uses new gradient information in the y-update.
- Connections: For static symmetric mixing, eliminating DIGing’s gradient-tracking variable yields a recursion with the two mixing matrices used in EXTRA.The paper analyzes more general time-varying W(k) directly; DIGing also has a primal-dual interpretation for static symmetric doubly stochastic matrices.
- Connections: The primal-dual connection relies on time-invariant symmetric W, whereas the paper’s primal analysis does not assume symmetry and motivates extension to directed graphs.The cited discussion identifies asymmetric W as difficult for classical primal-dual analysis.
3. Convergence Analysis for DIGing over Undirected Graphs.
DIGing’s undirected-graph analysis combines consensus contraction, gradient-tracking relations, and a small-gain argument to establish global R-linear convergence under stated mixing and strong-convexity assumptions. The resulting bounds expose dependence on network connectivity, agent count, objective conditioning, and step-size, with polynomial scalability but potentially conservative consensus estimates.
- Assumptions: The analysis assumes doubly stochastic mixing matrices with decentralized support, positive diagonals, edge utilization, non-vanishing weights, and a joint spectrum property.These assumptions encode the communication graph and guarantee suitable mixing behavior over time.
- Consensus contraction: B-step mixing contracts disagreement by a factor δ(k), establishing the consensus estimate used throughout the convergence proof.The contraction follows under the stated connectivity and mixing assumptions.
- Small-gain analysis: The proof applies a small-gain theorem in a carefully chosen metric to show that interconnected error quantities remain bounded and decay geometrically.An appropriately selected step-size makes the product of the gains less than one; boundedness then yields an O(λ^k) rate.
- Explicit rate: Theorem 10 gives an explicit DIGing rate in terms of B, n, δ, the strong-convexity and smoothness parameters, and the algorithmic step-size.The theorem’s rate parameter depends jointly on network and objective parameters rather than only on the optimization problem.
- Scalability: Under Corollary 11’s assumptions and step-size choice, DIGing converges to the unique optimizer at a global R-linear rate, with ε-accuracy complexity polynomial in n.The bound also depends on the condition number and time-varying connectivity constant B.
- Rate conservatism: The consensus bound δ ≤ 1 − τ/(2n^2) can be conservative, although graph-specific estimates based on hitting times and resistance may substantially sharpen it.For complete graphs the generic bound gives 1−δ of order 1/n^3, while the actual quantity is bounded away from zero; for line and ring graphs, the n^-2 scaling is essentially tight.
4. Distributed Optimization over Directed Graphs.
The paper addresses directed distributed optimization by replacing difficult doubly stochastic mixing with push-sum normalization. Push-DIGing combines column-stochastic communication, gradient tracking, and fixed-step updates for time-varying directed graphs.
- Motivation: Doubly stochastic matrices are costly to construct and maintain on general time-varying directed graphs because they require real-time weight balancing.This motivates the push-sum-based design.
- Push-sum protocol: Push-sum uses column-stochastic matrices and tracks scaling ratios to recover the unscaled average of agents’ states.Each agent propagates u and v, then forms x(k)=(V(k))^-1u(k).
- Push-DIGing: Push-DIGing initializes gradient tracking and updates u, v, x, and y using column-stochastic communication and local gradient differences.The gradient update accumulates the current local gradient and subtracts the previous one.
- Push-DIGing: Each agent sends scaled u_i(k)−αy_i(k), y_i(k), and v_i(k) to out-neighbors and receives corresponding messages from in-neighbors.This scaling reflects the directed graph’s asymmetric communication structure.
- Assumptions: The directed-graph analysis assumes a strongly connected time-varying graph sequence and column-stochastic matrices constructed using out-degree information.The out-degree-based choice is used to establish push-sum convergence bounds.
5. Convergence Analysis for Push-DIGing.
The convergence analysis establishes geometric convergence of Push-DIGing by combining push-sum consensus contraction with gradient-tracking recursions. A small gain argument yields explicit rate bounds under connectivity, mixing, convexity, and step-size conditions.
- Assumptions: Push-DIGing’s analysis assumes strongly connected time-varying directed graphs and out-degree-based column-stochastic mixing matrices.These assumptions support the push-sum consensus bounds used throughout the proof.
- Consensus contraction: Push-sum normalization transforms the column-stochastic recursion into a row-stochastic matrix eR(k), whose iterates contract toward consensus.The transformed matrix is row stochastic, and its products shrink distance to the consensus subspace.
- Consensus contraction: B-step consensus contraction bounds the normalized product by δ, yielding ∥a∥L≤δ∥b∥L for the relevant transformed recursion.The contraction applies for k≥B−1 under the stated connectivity and mixing assumptions.
- Proof strategy: The proof follows a cycle of bounds linking optimization error, gradient-tracking error, and consensus error, then applies the small gain theorem.The analysis avoids relying on monotonic decrease of a Lyapunov function.
- Rate result: Under the theorem’s assumptions and sufficiently small step-sizes, Push-DIGing converges to the unique optimizer at a global R-linear rate O(λ^k).The rate parameter λ is bounded through explicit constants and restrictions involving the connectivity and contraction parameters.
6. Numerical Experiments.
Experiments evaluate distributed estimation with Huber loss on time-invariant directed, time-varying undirected, and time-varying directed graphs. The observed convergence patterns support the paper’s geometric-rate claims and highlight communication and implementation trade-offs.
- Setup: The experiments use Huber loss in a decentralized estimation problem with noisy local observations, allowing both sublinear and linear convergence to be observed.The Huber loss is selected for robustness to outliers.
- Graph settings: The study covers time-invariant directed, time-varying undirected, and time-varying directed communication graphs.The directed base graph has 12 vertices and 24 arcs and is strongly connected; the undirected graph has 23 edges.
- Observed convergence: DIGing and its variants show R-linear rates, whereas push-gradient remains sublinear even for smooth strongly convex objectives.The experiments use hand-optimized step-sizes because the theoretical worst-case bounds are often conservative.
- Undirected comparison: For undirected graphs, EXTRA has a convergence curve almost identical to DIGing at the same step-size, while DIGing-ATC is faster in iteration count.The comparison is reported for the time-varying undirected experiment.
- Communication and directed graphs: Push-DIGing can match DIGing-ATC in iterations on undirected graphs while using half the communication cost per iteration.For time-varying directed graphs, only Push-DIGing is plotted because DIGing variants require impractical real-time graph balancing.
7. Conclusion.
The paper concludes by identifying unresolved directions for its distributed optimization method. These concern sharper agent-count convergence estimates and broader optimization models.
- Improved convergence-rate estimates remain an open question, particularly regarding scaling with the number of agents, n.
- The paper identifies local constraints as a target for extending its optimization models.
- Couplings among agents in the objectives are another proposed direction for future extensions.