An Accelerated Method For Decentralized Distributed Stochastic\n Optimization Over Time-Varying Graphs

Alexander Rogozin, Mikhail Bochko, Pavel Dvurechensky, Alexander Gasnikov, Vladislav Lukoshkin

TL;DR

This paper introduces a new accelerated algorithm for decentralized distributed stochastic optimization, achieving optimal communication and oracle complexity bounds for the first time. It also extends this to handle networks where communication links change over time, providing the first complexity bounds for such dynamic scenarios.

What Problem Does This Paper Address?

Imagine a network of many agents (like sensors or computers) that need to collectively solve an optimization problem. Each agent only knows a small piece of the overall problem (a local objective function) and can only talk to its immediate neighbors. The goal is to find a single optimal solution for the entire network by coordinating these local efforts. This is "decentralized distributed optimization."

Adding to the complexity, the data used to solve these problems is often noisy ("stochastic"), meaning we can only get approximate gradients. Furthermore, the communication links between agents might not be fixed; they can change over time, making it harder to maintain coordination and achieve fast convergence. Existing methods often struggle to achieve optimal performance in terms of both the number of times agents need to query their local functions (oracle calls) and the number of communication rounds required. This paper aims to close this gap, especially for the challenging case of time-varying communication networks.

Methods

The core of the paper is an accelerated decentralized stochastic gradient method. It builds upon Nesterov's acceleration principles, which are known to speed up optimization. The key innovation lies in how it handles the decentralized nature and the stochasticity:

  • Decentralized Consensus: Agents use a "consensus procedure" to average their local information. This is crucial for coordinating efforts across the network. The paper specifically addresses how this consensus mechanism works even when communication links change.
  • Stochastic Inexact Oracle: The algorithm is designed to work with noisy gradient information. It shows that if agents can maintain an approximate consensus, their local, noisy gradients can effectively act as a "stochastic inexact oracle" for the global objective function.
  • Time-Varying Graphs: A significant contribution is the adaptation of the algorithm to handle communication graphs that change over time. This involves analyzing the "contraction property" of the sequence of communication matrices, which quantifies how quickly information spreads and stabilizes in a dynamic network.

The algorithm combines these elements into a unified framework, aiming to achieve optimal theoretical performance.

Datasets

The paper mentions using LIBSVM datasets for their numerical experiments, specifically the "a9a" dataset. They simulate the performance of their algorithm on a random geometric graph with 20 nodes. They compare their method against DSGD (Distributed Stochastic Gradient Descent) and analyze the impact of different batch sizes and consensus iteration counts.

Key Insights and Ideas

  • Closing the Complexity Gap: The paper achieves a significant theoretical milestone by being the first to simultaneously attain optimal (up to logarithmic factors) communication and oracle complexity bounds for decentralized distributed stochastic optimization on fixed networks. This means it's as efficient as theoretically possible in terms of both local computations and inter-agent communication.
  • Handling Dynamic Networks: The development of the first accelerated algorithm for time-varying communication graphs is a major breakthrough. This addresses a more realistic scenario where network connectivity can fluctuate.
  • Tradeoff in Consensus: Numerical results highlight a clear tradeoff between the accuracy of the consensus procedure and the overall convergence speed. More consensus steps lead to better agreement among agents but can slow down the optimization process, and vice versa. This tradeoff is observed across different batch sizes.
  • Global vs. Local Conditions: The algorithm's complexity depends on global network parameters (like the sum of smoothness constants), which can be significantly better than relying on local parameters of individual agents. This is a desirable property for large-scale distributed systems.

Key Results

  • Fixed Networks: The proposed algorithm achieves optimal communication and oracle complexity bounds, which are $O(\frac{L_g}{\mu_g} \log \frac{1}{\epsilon})$ and $O(\frac{1}{\mu_g} \log \frac{1}{\epsilon})$ respectively, up to logarithmic factors. This is a significant theoretical improvement.
  • Time-Varying Networks: For dynamic networks, the algorithm provides the first upper complexity bounds. The communication complexity is shown to depend on parameters characterizing the graph's dynamics ($\tau$ and $\lambda$).
  • Numerical Performance: Experiments on L2-regularized logistic regression show that the algorithm converges effectively. The figures illustrate that increasing the number of consensus steps ($T$) improves the final accuracy but at the cost of more communication steps.

Limitations and Future Work

  • Assumptions: The paper assumes that the local objective functions are convex and smooth, and that the network is connected. The analysis also relies on specific properties of the mixing matrices for time-varying graphs.
  • Future Directions: The authors suggest that their framework can be extended to non-strongly convex and/or non-smooth functions, as well as composite optimization problems, zeroth-order optimization methods, and distributed algorithms for saddle-point problems and variational inequalities. They also believe their results can be generalized to more complex network structures.

Summary updated

Abstract

We consider a distributed stochastic optimization problem that is solved by a\ndecentralized network of agents with only local communication between\nneighboring agents. The goal of the whole system is to minimize a global\nobjective function given as a sum of local objectives held by each agent. Each\nlocal objective is defined as an expectation of a convex smooth random function\nand the agent is allowed to sample stochastic gradients for this function. For\nthis setting we propose the first accelerated (in the sense of Nesterov's\nacceleration) method that simultaneously attains optimal up to a logarithmic\nfactor communication and oracle complexity bounds for smooth strongly convex\ndistributed stochastic optimization. We also consider the case when the\ncommunication graph is allowed to vary with time and obtain complexity bounds\nfor our algorithm, which are the first upper complexity bounds for this setting\nin the literature.\n
BibTeX
@inproceedings{rogozin2021accelerated,
  author = {Alexander Rogozin and Mikhail Bochko and Pavel Dvurechensky and Alexander Gasnikov and Vladislav Lukoshkin},
  title = {{An Accelerated Method For Decentralized Distributed Stochastic\textbackslash\{\}n Optimization Over Time-Varying Graphs}},
  booktitle = {CDC},
  year = {2021},
  doi = {10.1109/cdc45484.2021.9683110},
}
Figure