Collaborative Learning of Discrete Distributions under Heterogeneity and Communication Constraints

Xinmeng Huang, Donghwan Lee, Edgar Dobriban, Hamed Hassani

This paper tackles a fundamental challenge in distributed machine learning: how can multiple users collaborate to learn data distributions when their data is slightly different and their communication bandwidth is strictly limited?

The authors introduce SHIFT (Sparse Heterogeneity Inspired collaboration and Fine-Tuning), a novel two-stage algorithm that achieves minimax optimal error rates by cleverly balancing global collaboration with local personalization.

TL;DR

The SHIFT method allows distributed users to collaboratively learn high-dimensional discrete distributions even when their data is heterogeneous and communication is restricted to a few bits per sample. By using robust statistics to find a "central" distribution and then fine-tuning for individual differences, SHIFT significantly outperforms traditional methods that either ignore user differences or fail to leverage the power of the group.

What Problem Does This Paper Address?

In "Federated Analytics," a server tries to learn a global model (like a word frequency distribution for a keyboard app) by aggregating data from many users. Most existing research assumes homogeneity—the idea that every user’s data comes from the exact same distribution.

Distributed learning setup with communication constraints

In the real world, this is rarely true. Users have unique habits and vocabularies. However, if every user tries to learn their own distribution locally, they often lack enough data to be accurate, especially when they can only send a few bits of information to the server (the communication bottleneck).

The authors identify a critical gap: we need a way to pool data to gain statistical power without letting the "average" result wash out the important unique characteristics of individual users.

Methods: The SHIFT Algorithm

The authors propose a model of sparse heterogeneity. They assume there is a "central" distribution ($p^*$), and each user’s individual distribution ($p^t$) differs from that center in only a small number of entries ($s$). For example, in text data, most users use common words like "the" or "and" with similar frequencies, but a poet and a programmer will have very different frequencies for domain-specific words like "blossom" or "syntax."

The SHIFT algorithm addresses this using a two-stage approach:

  1. Collaborative Learning (Stage I): All users send hashed (compressed) versions of their data to the server. The server uses robust statistical methods (like the coordinate-wise median or trimmed mean) to estimate the central distribution. Because the differences are sparse, the median effectively filters out the "outlier" users for any given coordinate, resulting in a highly accurate global estimate.
  2. Fine-Tuning (Stage II): The server sends the central estimate back to the users. Each user then compares their local data to this central model. If the difference for a specific entry is small (below a calculated threshold), they adopt the accurate global estimate. If the difference is large, they stick with their local estimate to preserve their unique characteristics.

This approach uses a non-interactive hashing scheme, meaning users don't need to go back and forth with the server multiple times, making it highly communication-efficient.

Key Insights and Ideas

  • Robustness as a Bridge: Usually, robust statistics (like the median) are used to protect against malicious "Byzantine" actors. Here, the authors use them as a tool to handle natural diversity. The median allows the server to ignore the "unique" parts of some users to find the "common" parts shared by most.
  • The Power of Sparsity: By assuming that users are mostly the same, the math becomes tractable. This allows for a massive improvement in sample complexity—specifically, a factor of $\min\{T, d/\max\{s, 2^b\}\}$ better than previous methods.
  • Knowledge Transfer: The paper shows that a model learned from existing users can be "transferred" to a brand-new user very efficiently. The new user only needs to learn the few entries where they differ from the established center.

Datasets and Key Results

The researchers evaluated SHIFT using two primary methods:

  • Synthetic Data: They generated 300-dimensional distributions with random $s$-sparse perturbations to rigorously test the algorithm against theoretical lower bounds.
  • Shakespeare Dataset: A standard benchmark for federated learning containing dialogues from 1,129 speaking roles. The task was to estimate the frequency of $k$-grams. Each "play" was treated as a separate cluster of users to test how well the model handles natural linguistic heterogeneity.
SHIFT performance compared to baselines across varying sample sizes, clusters, and sparsity levels

Primary Findings: * Minimax Optimality: The authors mathematically proved that SHIFT is "minimax optimal," meaning no other algorithm (even interactive ones) can significantly outperform it under these specific constraints of heterogeneity and communication. * Superior Accuracy: In synthetic tests, SHIFT consistently achieved lower $\ell_2$ error than "Local" methods (which don't collaborate) and "Global" methods (which ignore differences and suffer from bias). As seen in the results, SHIFT adapts beautifully across varying sample sizes ($n$), cluster counts ($T$), and sparsity levels ($s$). * Shakespeare Performance: On the $k$-gram estimation task, SHIFT (using trimmed mean) outperformed the standard "Uniform Grouping" baseline across various bit budgets ($b=2, 4, 6, 8$). For $k=3$ grams and a 2-bit budget, SHIFT reduced the error significantly compared to local estimation.

Limitations and Future Work

  • Point-wise Optimality: The current bounds are "minimax," which look at the worst-case scenario. The authors suggest future work could look at "point-wise" optimality, which adapts to the specific shape of the distributions involved.
  • Privacy Constraints: While this paper focuses on communication, real-world federated learning often requires Local Differential Privacy (LDP). Integrating SHIFT with privacy-preserving noise is a logical next step.
  • Dense Heterogeneity: The model relies on the assumption that differences are sparse. If every single entry in a distribution changes slightly for every user (dense heterogeneity), the current SHIFT framework might need significant modification.

Summary updated

Abstract

In modern machine learning, users often have to collaborate to learn distributions that generate the data. Communication can be a significant bottleneck. Prior work has studied homogeneous users---i.e., whose data follow the same discrete distribution---and has provided optimal communication-efficient methods. However, these methods rely heavily on homogeneity, and are less applicable in the common case when users' discrete distributions are heterogeneous. Here we consider a natural and tractable model of heterogeneity, where users' discrete distributions only vary sparsely, on a small number of entries. We propose a novel two-stage method named SHIFT: First, the users collaborate by communicating with the server to learn a central distribution; relying on methods from robust statistics. Then, the learned central distribution is fine-tuned to estimate the individual distributions of users. We show that our method is minimax optimal in our model of heterogeneity and under communication constraints. Further, we provide experimental results using both synthetic data and $n$-gram frequency estimation in the text domain, which corroborate its efficiency.
BibTeX
@inproceedings{huang2022collaborative,
  author = {Xinmeng Huang and Donghwan Lee and Edgar Dobriban and Hamed Hassani},
  title = {{Collaborative Learning of Discrete Distributions under Heterogeneity and Communication Constraints}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=HuSrNIzO51J},
}
Figure