Distributed Stochastic Optimization with Gradient Tracking over Time- Varying Directed Networks

Angelia Nedich, Duong Thuy Anh Nguyen, Angelia NedicAcssc 2023 · DOI

TL;DR

This paper introduces SAB-TV, a novel distributed optimization algorithm designed for networked systems with dynamic communication links. It tackles the challenge of minimizing a sum of local, noisy cost functions across agents, achieving linear convergence to the optimal solution even with imperfect information exchange. This work is crucial for enabling efficient distributed learning and control in real-world scenarios like the Internet of Things.

What Problem Does This Paper Address?

Modern systems, from sensor networks to edge computing platforms, involve numerous interconnected agents that need to collaboratively solve optimization problems. Often, these agents only have access to their local data and can only communicate with a subset of other agents. Furthermore, the communication network itself can be dynamic, with links appearing and disappearing over time, and the communication channels might be unreliable, introducing noise.

Traditional distributed optimization methods often assume static, fully connected networks or rely on synchronized communication, which are unrealistic in many practical settings. Specifically, this paper addresses the challenge of distributed optimization over time-varying directed networks where agents have access to stochastic first-order oracles (meaning they get noisy estimates of their local cost function gradients). The goal is to minimize the sum of these local cost functions across all agents, ensuring that all agents converge to a common, globally optimal solution, despite the inherent noise and network limitations.

Methods

The core innovation of this paper is the SAB-TV algorithm, which builds upon the concept of gradient tracking. Gradient tracking aims to overcome the limitations of traditional distributed methods by having each agent maintain an auxiliary variable that asymptotically tracks the global gradient. This allows agents to make progress towards the global optimum even when their local information is noisy or incomplete.

Key aspects of SAB-TV include:

  • Two-Phase Update: SAB-TV employs a two-phase update mechanism. First, agents update their local decision variables ($x_k$) by pulling information from their in-neighbors using row-stochastic weights (ensuring consensus on the decision variable). Second, agents update their gradient tracking variables ($y_k$) by pushing information to their out-neighbors using column-stochastic weights (crucial for tracking the global gradient).
  • Time-Varying Directed Graphs: The algorithm is specifically designed to handle networks that change over time and where communication is not necessarily symmetric (directed). This is achieved by using time-varying weight matrices ($A_k$ and $B_k$) that adapt to the current network topology.
  • Stochastic Gradients: The algorithm explicitly accounts for noisy gradient estimates from local cost functions, assuming they have zero mean and bounded variance.
  • Convergence Analysis: The paper provides a rigorous theoretical analysis showing that SAB-TV converges linearly to a neighborhood of the global optimum in expectation, provided a sufficiently small step-size is used. This analysis carefully accounts for the time-varying nature of the network and the stochasticity of the gradients.

Datasets

The paper uses the MNIST dataset for evaluating the performance of the proposed algorithm. Specifically, they focus on a binary classification task to distinguish between handwritten digits 3 and 7. The dataset is partitioned among agents, with each agent having a local batch of training samples.

Key Insights and Ideas

  • Gradient Tracking is Key for Noise and Network Dynamics: The paper highlights that gradient tracking is essential for achieving robust convergence in distributed optimization settings with both noisy data and dynamic, directed networks. It effectively mitigates the impact of local noise and network limitations on the global optimization process.
  • Asymmetric Weights for Different Tasks: The clever use of row-stochastic weights for decision variable updates and column-stochastic weights for gradient tracking is a critical insight. This separation allows for efficient consensus on the solution while simultaneously enabling accurate global gradient estimation.
  • Linear Convergence is Achievable: Despite the inherent challenges of stochasticity and time-varying directed graphs, the authors demonstrate that SAB-TV can achieve linear convergence. This is a significant theoretical result, implying that the algorithm scales well and can find accurate solutions efficiently.
  • Practical Implications for Edge AI: The algorithm's design and analysis are directly relevant to the growing field of edge AI and the Internet of Things, where distributed computation and learning are paramount.

Key Results

The paper presents a theoretical convergence guarantee for the SAB-TV algorithm. Under standard assumptions (smooth, strongly convex local functions, zero-mean bounded variance noise, and strongly connected time-varying directed graphs), the algorithm is shown to converge linearly to a neighborhood of the global minimizer in expectation.

The numerical simulations on the MNIST dataset demonstrate that SAB-TV outperforms the AB-Push/Pull algorithm (a non-stochastic distributed method) in terms of initial convergence speed. While both SAB-TV and a centralized stochastic gradient descent (CSGD) method converge to a vicinity of the optimal solution due to the inexact gradients, SAB-TV achieves competitive accuracy. The paper also shows that SAB-TV achieves test set accuracy of over 97% after 50 epochs.

Limitations and Future Work

  • Step-Size Sensitivity: The theoretical analysis shows that linear convergence is achieved when the step-size $\alpha$ is chosen to be sufficiently small. Determining the optimal step-size in practice and developing adaptive step-size mechanisms could be a direction for future work.
  • Assumptions on Network Connectivity: While the paper handles time-varying directed graphs, it assumes that the graphs are strongly connected at each step (or C-strongly connected over a window of C steps). Relaxing this assumption to handle more general network topologies, such as disconnected components, could be an area for future research.
  • Non-convex Optimization: The current analysis focuses on strongly convex functions. Extending the algorithm and its convergence guarantees to non-convex objective functions would broaden its applicability.
  • Communication Overhead: While SAB-TV is designed for distributed settings, the communication of gradient tracking variables can still incur significant overhead. Investigating methods to reduce communication complexity while maintaining performance would be valuable.

Summary updated

BibTeX
@inproceedings{nedich2023distributed,
  author = {Angelia Nedich and Duong Thuy Anh Nguyen and Duong Tung Nguyen and Angelia Nedic},
  title = {{Distributed Stochastic Optimization with Gradient Tracking over Time- Varying Directed Networks}},
  booktitle = {Acssc},
  year = {2023},
  doi = {10.1109/ieeeconf59524.2023.10477004},
}
Figure