Heterogeneity for the Win: One-Shot Federated Clustering

Don Kurian Dennis, Tian Li, Virginia Smith

TL;DR

$k$-FED is a one-shot federated clustering algorithm that turns the "curse" of statistical heterogeneity into a theoretical and practical advantage. By requiring only a single round of communication, it achieves clustering quality comparable to iterative methods while significantly weakening the data separation requirements needed for success in non-IID environments.

The Challenge of Unsupervised Federated Learning

Federated Learning (FL) typically focuses on supervised tasks, but unsupervised learning—specifically clustering—is a vital first step for data exploration, client selection, and model personalization. However, clustering in a federated setting faces three major hurdles:

  1. Communication Constraints: Standard iterative algorithms like $k$-means require many rounds of synchronization, which is costly and slow over mobile networks.
  2. Systems Heterogeneity: Devices frequently drop out (failures) or lag (stragglers), breaking iterative loops.
  3. Statistical Heterogeneity: Data is non-identically distributed (non-IID) across devices. In supervised FL, this is usually a major drawback that slows down convergence and hurts model accuracy.

The authors ask a counterintuitive question: Can we design a clustering algorithm that is robust to these issues and perhaps even benefits from the way data is naturally partitioned across a network?

Introducing $k$-FED

The authors introduce $k$-FED, a one-shot communication scheme based on the classical Lloyd’s heuristic for $k$-means. The process works in two distinct stages:

  • Local Stage: Each participating device independently runs a variant of Lloyd’s algorithm on its local data to find a set of local cluster centers. Crucially, each device only needs to find the number of clusters present in its own data ($k^{(z)}$), which is often much smaller than the total number of clusters in the entire network ($k$).
  • Global Stage: Devices send their local centers to a central server. The server then aggregates these points using a "farthest-point" initialization followed by a single round of Lloyd’s to produce the final $k$ global cluster centers.

The core of their theoretical contribution is analyzing $k$-FED under a center-separation assumption. They distinguish between "active" cluster pairs (those that appear together on at least one device) and "inactive" pairs (those that never share a device).

Key Insights: Why Heterogeneity Helps

  • Heterogeneity for the Win: The most striking finding is that statistical heterogeneity actually helps. If each device only sees a small subset of the total clusters (specifically $k' \le \sqrt{k}$), the separation required to distinguish between clusters is significantly lower than in a centralized setting.
  • The "Inactive" Advantage: When two clusters never appear on the same device (an inactive pair), the local clustering task is simplified. The server then only needs to distinguish between these "pre-cleaned" local centers, which is easier than clustering the raw, noisy data points.
  • One-Shot is Enough: You don't need dozens of rounds of back-and-forth. A single round of local clustering followed by global aggregation is sufficient to recover the underlying structure of the data.
  • Robustness by Design: Because $k$-FED is one-shot and can run asynchronously, it is naturally immune to the "straggler" problem. If a device fails, the server simply proceeds with the centers it has received, provided enough devices have participated to cover all $k$ target clusters.

Key Results

The researchers evaluated $k$-FED using a mix of synthetic and real-world federated benchmarks, including Gaussian mixtures, FEMNIST, Shakespeare, and Rotated MNIST.

Theoretical Efficiency: In heterogeneous regimes, $k$-FED handles cluster pairs with a weaker $\Omega(k^{1/4})$ separation requirement, compared to the $\Omega(\sqrt{k})$ required in centralized settings.

Accuracy on Synthetic Data: $k$-FED achieves near 100% accuracy on Gaussian mixtures even when the separation constant $c$ is small, far below the theoretical requirement of $c \ge 100$.

Impact of separation constant on accuracy

Real-World Performance: On datasets like FEMNIST, $k$-FED produces a $k$-means cost much closer to the "oracle" (perfect) clustering when the data is partitioned heterogeneously ($k'$ is small) compared to random IID partitions.

Benefits of structured partitions on FEMNIST

Communication Savings & Personalization: $k$-FED matches the clustering quality of naive distributed $k$-means while using only a single communication round. Furthermore, when used as a pre-processing step for personalized FL, $k$-FED matches or exceeds the accuracy of more complex iterative methods like IFCA, while being significantly faster and more communication-efficient.

Limitations and Future Work

While promising, the approach has a few limitations:

  • Privacy: While one-shot communication reduces the attack surface compared to iterative methods, the paper does not formally integrate differential privacy or secure multi-party computation, which are standard in many FL applications.
  • Hyperparameter Sensitivity: The algorithm assumes the total number of clusters $k$ and local clusters $k^{(z)}$ are known or can be accurately estimated.
  • Generative Assumptions: The most detailed theoretical results rely on data being somewhat well-separated, which may not hold for highly overlapping or non-spherical clusters in high-dimensional space.

The authors suggest that exploring other unsupervised tasks where heterogeneity might be beneficial—such as dimensionality reduction or density estimation—is a promising direction for future federated learning research.

Summary updated

Abstract

In this work, we explore the unique challenges—and opportunities—of unsupervised federated learning (FL). We develop and analyze a one-shot federated clustering scheme, kfed, based on the widely-us...
BibTeX
@inproceedings{dennis2021heterogeneity,
  author = {Don Kurian Dennis and Tian Li and Virginia Smith},
  title = {{Heterogeneity for the Win: One-Shot Federated Clustering}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=NsTIswey0n5},
}
Figure