Communication-Aware Collaborative Learning

Avrim Blum, Shelby Heinecke, Lev Reyzin

Abstract

Collaborative PAC (Probably Approximately Correct) learning enables multiple participants to jointly learn models tailored to their local data distributions. However, practical deployment is often hindered by significant communication overhead and the presence of label noise. This paper introduces communication-efficient algorithms that integrate distributed boosting techniques to achieve an exponential reduction in communication costs—moving from a linear to a logarithmic dependence on the error parameter—while maintaining optimal sample complexity and ensuring robustness against classification noise.

Introduction

In collaborative PAC learning, a central orchestrator helps multiple "players" (e.g., hospitals or institutions) learn models that perform well on their specific distributions. While theoretical models have optimized for sample complexity, two major practical hurdles remain:

  1. Communication Overhead: Transmitting large batches of raw data is often infeasible. Prior state-of-the-art algorithms required communication that scaled linearly with the inverse of the error parameter ($1/\epsilon$).
  2. Label Noise: Real-world data frequently contains errors. Achieving generalization on the "true" distribution from noisy labels is challenging, particularly when noise rates vary across participants.

This work bridges the gap between theoretical sample efficiency and these practical constraints by introducing a framework that treats communication as a primary bottleneck.

Methodology

The authors extend the "Personalized Learning" framework with several key innovations designed to minimize data transfer and handle imperfect labels.

Distributed Boosting

The primary contribution is the replacement of standard sample-gathering with a distributed version of AdaBoost. Instead of the center requesting a massive batch of samples to find a consistent hypothesis, players participate in rounds of boosting. In each round, they communicate only a small number of samples ($O(d)$), resulting in a communication cost that scales with $\log(1/\epsilon)$ rather than $1/\epsilon$.

Noise-Robust Learning via ERM and CN-TEST

To handle classification noise where a perfectly consistent hypothesis may not exist, the framework employs Empirical Risk Minimization (ERM). Furthermore, a new subroutine called CN-TEST is introduced. This procedure accounts for individual player noise rates ($\eta_i$) by scaling test sample sizes and adjusting success thresholds. This ensures that hypotheses passing the test on noisy data will generalize well to the underlying clean distribution.

Theoretical Results

The paper establishes rigorous upper bounds for both sample and communication complexity, demonstrating significant improvements over existing baselines.

Noiseless Learning

For noiseless scenarios, the proposed boosting-based approach reduces communication costs from $\tilde{O}(\frac{d \log k}{\epsilon})$ to $\tilde{O}(d \log k \log(1/\epsilon))$. This represents an exponential speedup in communication efficiency relative to the error parameter while maintaining the same sample complexity as previous state-of-the-art methods.

Comparison of sample and communication complexity for noiseless collaborative learning.

Learning under Classification Noise

The authors provide the first formal analysis for collaborative PAC learning under the classification noise model. Even with imperfect data, the algorithm maintains logarithmic overheads, though the complexity is adjusted by the noise rate factor $(1-2\eta_{MAX})^2$.

Complexity bounds for collaborative learning under classification noise.

Key Insights

  • Boosting as an Information Filter: Distributed boosting effectively "distills" information, allowing the center to learn a hypothesis by observing only a fraction of the total samples used.
  • Scalability: The sample complexity of the distributed boosting approach is independent of the number of players ($k$), making it highly scalable for large networks of devices or institutions.
  • Noise-Aware Testing: The paper demonstrates that players do not need to share their full distributions to handle noise; knowing local noise rates is sufficient to adjust the stringency of local tests.

Discussion and Future Work

While this framework provides a significant leap forward, certain constraints remain. The noise-robust analysis is currently restricted to regimes where the maximum noise rate $\eta_{MAX}$ is less than the target error $\epsilon$. Future research may explore agnostic learning settings, where the target concept may not reside within the hypothesis class, and further refine the application of these techniques to centralized learning models.

Summary updated

Abstract

Algorithms for noiseless collaborative PAC learning have been analyzed and optimized in recent years with respect to sample complexity. In this paper, we study collaborative PAC learning with the goal of reducing communication cost at essentially no penalty to the sample complexity. We develop communication efficient collaborative PAC learning algorithms using distributed boosting. We then consider the communication cost of collaborative learning in the presence of classification noise. As an intermediate step, we show how collaborative PAC learning algorithms can be adapted to handle classification noise. With this insight, we develop communication efficient algorithms for collaborative PAC learning robust to classification noise.
BibTeX
@inproceedings{blum2021communication,
  author = {Avrim Blum and Shelby Heinecke and Lev Reyzin},
  title = {{Communication-Aware Collaborative Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i8.16838},
}
Figure