DIGEST: FAST AND COMMUNICATION EFFICIENT DECENTRALIZED LEARNING WITH LOCAL UPDATES

Peyman Gholami, Hulya Seferoglu

TL;DR

This paper introduces DIGEST, a novel asynchronous decentralized learning algorithm that combines the strengths of Gossip and random walk approaches. DIGEST significantly reduces communication overhead and improves convergence speed, especially in non-iid data settings, outperforming existing methods for both logistic regression and deep neural networks.

What Problem Does This Paper Address?

In modern applications like IoT and mobile healthcare, data is increasingly generated at the edge, making decentralized learning a necessity. Traditional decentralized methods like Gossip algorithms suffer from high communication costs, while random walk-based methods can lead to slow convergence. Existing solutions often rely on a central parameter server, which can be a bottleneck. The challenge is to design a decentralized learning system that is both communication-efficient and fast-converging, particularly when data distributions across devices are heterogeneous (non-iid).

Methods

The core innovation is DIGEST, an asynchronous decentralized learning mechanism built upon local Stochastic Gradient Descent (SGD). DIGEST aims to overcome the limitations of existing methods by:

  • Leveraging Local SGD: Each node continuously updates its local model, similar to centralized local-SGD, reducing the need for frequent global communication.
  • Sporadic Global Model Exchange: Instead of constant neighbor-to-neighbor communication (Gossip), DIGEST facilitates a more structured, albeit asynchronous, exchange of a global model. This global model is updated by each node with its local computations.
  • Combining Gossip and Random Walk Ideas: DIGEST uses a random selection of neighbors for global model transmission, inspired by random walks, but unlike pure random walk, it doesn't require nodes to wait idly. It also avoids the "diminishing updates" issue of Gossip by using a global model.
  • Single-Stream and Multi-Stream Variants:
    • Single-Stream DIGEST: A global model is propagated through the network in a stream, with updates occurring periodically (every H iterations).
  • Multi-Stream DIGEST: To further accelerate convergence, multiple independent streams of global model updates operate concurrently, often structured using a shortest-path tree. This allows for faster propagation and better handling of network dynamics.

The paper provides theoretical convergence analysis for both variants, proving they approach the optimal solution asymptotically for both iid and non-iid data.

Datasets

The paper evaluates DIGEST on the following datasets:

  • w8a: Used for logistic regression.
  • MNIST: Used for logistic regression.
  • CIFAR-10: Used for deep neural network (ResNet-20) evaluation.

The experiments consider both iid-balanced and non-iid-unbalanced data distributions.

Key Insights and Ideas

  • The "Diminishing Updates" Problem: The paper highlights how in traditional Gossip, model updates can get diluted and mixed with other nodes' models, hindering convergence, especially with non-iid data. DIGEST's global model approach mitigates this.
  • Trade-off Between Streams and Communication: Multi-stream DIGEST offers improved convergence but at the cost of potentially increased communication overhead. The paper suggests this trade-off can be tuned by adjusting parameters like H (synchronization interval).
  • Topology Independence: DIGEST is shown to be less affected by network topology compared to some other decentralized methods, meaning high-degree nodes don't necessarily introduce learning bias.
  • Effectiveness in Non-IID Settings: DIGEST demonstrates superior performance in non-iid scenarios, a common challenge in real-world decentralized learning, where other methods like Gossip struggle.

Key Results

  • Convergence: Both single- and multi-stream DIGEST are theoretically proven to converge asymptotically to the optimal solution for both iid and non-iid data.
  • Performance:
    • In iid settings, DIGEST's convergence time is comparable to or better than baselines.
  • In non-iid settings, DIGEST significantly outperforms baselines, including Gossip-based algorithms and Gradient Tracking (GT).
  • Communication Efficiency: DIGEST is designed to be communication-efficient, reducing the overhead compared to traditional Gossip algorithms.
  • Speed-up: Multi-stream DIGEST achieves near-linear speed-up with an increasing number of nodes, closely approaching the performance of centralized parallel SGD. Single-stream DIGEST shows linear speed-up up to a certain limit.
  • Deep Neural Networks: DIGEST shows competitive performance with other methods on ResNet-20 for CIFAR-10, particularly outperforming Gossip in non-iid settings.

Limitations and Future Work

  • Synchronization Interval (H): The paper notes that for larger networks, single-stream DIGEST might struggle to traverse the entire network quickly, highlighting the need for multi-stream DIGEST. The optimal choice of H for balancing convergence and communication is an area for further exploration.
  • Theoretical Assumptions: The convergence analysis relies on certain assumptions (e.g., bounded lag, L-smoothness) which might not always hold in practice.
  • Practical Implementation: While the paper provides theoretical backing and simulation results, further research into practical implementation challenges and optimizations for large-scale, heterogeneous environments could be beneficial.
  • Hyperparameter Tuning: As with most machine learning algorithms, DIGEST's performance can be sensitive to hyperparameter choices, and efficient tuning strategies for decentralized settings could be a future research direction.

Summary updated

Abstract

Decentralized learning advocates the elimination of centralized parameter servers (aggregation points) for potentially better utilization of underlying resources, de- lay reduction, and resiliency against parameter server unavailability and catas- trophic failures. Gossip based decentralized algorithms, where each node in a net- work has its own locally kept model on which it effectuates the learning by talking to its neighbors, received a lot of attention recently. Despite their potential, Gossip algorithms introduce huge communication costs. In this work, we show that nodes do not need to communicate as frequently as in Gossip for fast convergence; in fact, a sporadic exchange of a digest of a trained model is sufficient. Thus, we design a fast and communication-efficient decentralized learning mechanism; DI- GEST by particularly focusing on stochastic gradient descent (SGD). DIGEST is a decentralized algorithm building on local-SGD algorithms, which are originally designed for communication efficient centralized learning. We show through anal- ysis and experiments that DIGEST significantly reduces the communication cost without hurting convergence time for both iid and non-iid data.
BibTeX
@inproceedings{gholami2023digest,
  author = {Peyman Gholami and Hulya Seferoglu},
  title = {{DIGEST: FAST AND COMMUNICATION EFFICIENT DECENTRALIZED LEARNING WITH LOCAL UPDATES}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  doi = {10.48550/arxiv.2307.07652},
}
Figure