Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs

Angelia Nedic, Alex Olshevsky, Wei ShiSIAM J. Optimization 2017 · OpenReview

TL;DR

This paper introduces two novel distributed optimization algorithms, DIGing and Push-DIGing, that achieve geometric convergence rates even when the communication network between agents changes over time and is directed. These algorithms are crucial for enabling efficient, large-scale distributed learning and control in dynamic network environments.

What Problem Does This Paper Address?

In many real-world applications, such as sensor networks, robotics, and machine learning, multiple agents need to collaboratively solve an optimization problem. Traditionally, this has been done assuming a fixed and well-behaved communication network. However, in many practical scenarios, the network connectivity can change dynamically (time-varying graphs) and may not be symmetric (directed graphs). Existing distributed optimization methods often struggle with these dynamic and directed network conditions, either requiring diminishing step-sizes (leading to slow convergence) or failing to converge to the exact optimal solution. This paper tackles the challenge of designing distributed algorithms that guarantee fast, geometric convergence even under these complex and realistic network conditions.

Methods

The authors propose two main algorithms:

  • DIGing: For undirected, time-varying graphs, DIGing combines a distributed inexact gradient method with a "gradient tracking" technique. This gradient tracking mechanism allows agents to estimate the average gradient of the global objective function, overcoming a key limitation of simpler distributed gradient descent methods. DIGing uses doubly stochastic mixing matrices and fixed step-sizes.
  • Push-DIGing: For directed, time-varying graphs, where doubly stochastic matrices are difficult to implement, the authors adapt DIGing by incorporating the "push-sum" protocol. This protocol allows agents to achieve average consensus using column stochastic matrices, which are easier to construct in directed networks. Push-DIGing also uses fixed step-sizes.

A key technical innovation is the use of the small-gain theorem from control theory to analyze the convergence of these algorithms. This theorem provides a powerful framework for proving stability and convergence in interconnected systems, which is adapted here to analyze the cyclic dependencies between different error terms in the distributed optimization process.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses synthetic experiments for evaluation.

Key Insights and Ideas

  • Gradient Tracking is Key: The core idea of DIGing is to accurately track the average gradient across all agents, even when communication is limited and dynamic. This allows for faster convergence than methods that only use local gradients.
  • Push-Sum for Directed Graphs: The push-sum protocol is a clever way to achieve consensus in directed networks, enabling the extension of DIGing's principles to a broader class of communication topologies.
  • Small-Gain Theorem for Optimization: Applying the small-gain theorem from control theory to analyze distributed optimization algorithms is a novel approach. It allows for bounding the convergence of various error terms in a cyclic manner, leading to geometric convergence guarantees.
  • Geometric Convergence is Achievable: The paper demonstrates that even with time-varying and directed graphs, and using fixed step-sizes, R-linear (geometric) convergence rates can be achieved under strong convexity assumptions. This is a significant theoretical advancement.
  • Polynomial Scaling with Network Size: For undirected graphs, the DIGing algorithm exhibits polynomial scaling in the number of agents, meaning the number of iterations required to reach a certain accuracy grows polynomially with the network size, which is desirable for large-scale systems.

Key Results

  • DIGing Algorithm: Achieves R-linear convergence for distributed optimization over time-varying undirected graphs with fixed step-sizes. The convergence rate scales polynomially with the number of agents.
  • Push-DIGing Algorithm: Achieves R-linear convergence for distributed optimization over time-varying directed graphs with fixed step-sizes.
  • Theoretical Guarantees: Explicit estimates for the convergence rates are derived, showing dependence on network parameters (connectivity, size) and objective function properties (strong convexity, smoothness).
  • Numerical Validation: Experiments demonstrate the efficacy of the proposed algorithms, showing faster convergence compared to baseline methods like gradient-push, especially in dynamic network settings.

Limitations and Future Work

  • Strong Convexity Assumption: The R-linear convergence results are proven under the assumption of strong convexity for the objective functions. Extending these results to general convex functions (sublinear convergence) or non-convex functions remains an open area.
  • Step-Size Selection: While the algorithms use fixed step-sizes, selecting these step-sizes requires knowledge of certain network parameters (e.g., upper bounds on network size and connectivity). The paper discusses how these parameters can be estimated but notes that this adds a preprocessing step.
  • Communication Overhead: While DIGing and Push-DIGing achieve geometric convergence, the exact communication cost per iteration is not explicitly minimized. Future work could explore strategies to further reduce communication while maintaining fast convergence.
  • More Complex Models: The authors suggest extending the framework to handle more complex optimization models, such as those with local constraints or couplings among agents' objectives.

Summary updated

Abstract

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 the Push-DIGing algorithm. 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.
BibTeX
@article{nedic2017achieving,
  author = {Angelia Nedic and Alex Olshevsky and Wei Shi},
  title = {{Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs}},
  journal = {SIAM J. Optimization},
  year = {2017},
  url = {https://openreview.net/forum?id=P5c7eZyWtwc},
}
Figure