Optimal Distributed Convex Optimization on Slowly Time-Varying Graphs

Alexander Rogozin, César A. Uribe, Alexander V. Gasnikov, Nikolay Malkovsky, Angelia NedicIEEE Trans. Control. Netw. Syst 2020 · DOI

TL;DR

This paper tackles the challenge of distributed optimization in networks where communication links can change over time, a common issue in real-world scenarios like agent malfunctions. The authors propose an accelerated gradient method that achieves optimal convergence rates, provided these network changes are infrequent, offering a theoretical guarantee for such "slowly time-varying" scenarios.

What Problem Does This Paper Address?

In many modern applications, such as large-scale machine learning or sensor networks, optimization problems are solved collaboratively by multiple agents communicating over a network. The goal is to minimize a global objective function, often a sum of local functions held by each agent. A key challenge arises when the network's connectivity (i.e., which agents can communicate with whom) changes over time. This can happen due to agent failures, network congestion, or dynamic task assignments. Traditional distributed optimization algorithms often assume a fixed network topology. This paper addresses the problem of achieving optimal convergence rates for distributed optimization when the underlying communication graph is not static but changes over time, specifically focusing on scenarios where these changes are infrequent.

Methods

The paper leverages the concept of dual optimization to analyze the problem. By reformulating the distributed optimization problem into its dual form, the authors can study the convergence properties of standard optimization algorithms like gradient descent and Nesterov's fast gradient method in the context of time-varying functions.

A core contribution is the development of a potential function-based analysis for Nesterov's method. This allows them to derive convergence guarantees even when the objective function changes at each iteration. The key novelty lies in establishing a sufficient condition for achieving optimal convergence rates. This condition relates the rate of convergence to the frequency of network changes, specifically requiring that the number of changes is a small fraction of the total number of iterations. They introduce the concept of "slowly time-varying graphs" to characterize these scenarios.

The proposed algorithm is an accelerated distributed Nesterov method that operates on the dual problem. The theoretical analysis provides an explicit upper bound on the number of network changes allowed to guarantee optimal convergence.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and provides numerical experiments on synthetic datasets.

Key Insights and Ideas

  • Dualization is powerful for time-varying networks: By switching to the dual problem, the authors can analyze algorithms that are robust to changes in the network structure, as the dual function's properties (like strong convexity) can be maintained under certain conditions.
  • Infrequent changes are key to optimality: The paper demonstrates that optimal convergence rates are achievable if the network topology changes "slowly." This means the number of topology changes must be a small fraction of the total iterations. This is a crucial insight for practical deployment.
  • Nesterov's method adapts well to slow changes: The analysis shows that Nesterov's accelerated method, when applied to the dual problem, can maintain its efficiency even with a limited number of function (and thus network) changes.
  • Trade-off between network and function conditioning: The convergence rate depends on both the condition number of the objective function and the condition number of the sequence of communication graphs.

Key Results

  • The paper provides a sufficient condition for achieving optimal convergence rates for distributed optimization over slowly time-varying graphs.
  • They derive an iteration complexity bound for a distributed Nesterov method that depends on the condition number of the objective function, the worst-case condition number of the communication graphs, and the fraction of network changes.
  • The proposed method achieves convergence rates that are optimal up to logarithmic terms with respect to network and function parameters, provided the network changes are infrequent.
  • Numerical experiments on synthetic datasets (ridge regression and logistic regression) demonstrate that the proposed method performs comparably to other state-of-the-art algorithms, especially when network changes are infrequent.

Limitations and Future Work

  • Sufficient but not necessary condition: The paper provides a sufficient condition for optimal convergence rates. Whether this condition is also necessary for achieving such rates remains an open question.
  • "Slowly time-varying" assumption: The theoretical guarantees are tied to the assumption of infrequent network changes. The performance of the algorithm when changes are rapid or frequent is not fully characterized, and the paper notes that in such cases, other algorithms might perform better.
  • Dual-friendly functions: The analysis assumes that the dual functions are "dual-friendly," meaning the maximization step in the dual problem is computationally tractable. Relaxing this assumption is suggested for future work.
  • Exploration of restarts and other acceleration schemes: The authors suggest exploring restarts and other acceleration techniques to potentially improve convergence rates, especially for scenarios with more frequent changes.
  • Generalization to non-convex problems: The current work focuses on convex optimization. Extending these results to non-convex settings would be a valuable future direction.

Summary updated

BibTeX
@article{rogozin2020optimal,
  author = {Alexander Rogozin and César A. Uribe and Alexander V. Gasnikov and Nikolay Malkovsky and Angelia Nedic},
  title = {{Optimal Distributed Convex Optimization on Slowly Time-Varying Graphs}},
  journal = {IEEE Trans. Control. Netw. Syst.},
  year = {2020},
  doi = {10.1109/tcns.2019.2949439},
}
Figure