Timezone: »

 
Spotlight
Heterogeneity for the Win: One-Shot Federated Clustering
Don Kurian Dennis · Tian Li · Virginia Smith

Tue Jul 20 05:40 PM -- 05:45 PM (PDT) @
in Optimization and Algorithms 1 »
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-used Lloyd's method for $k$-means clustering. In contrast to many supervised problems, we show that the issue of statistical heterogeneity in federated networks can in fact benefit our analysis. We analyse kfed under a center separation assumption and compare it to the best known requirements of its centralized counterpart. Our analysis shows that in heterogeneous regimes where the number of clusters per device $(k')$ is smaller than the total number of clusters over the network $k$, $(k'\le \sqrt{k})$, we can use heterogeneity to our advantage---significantly weakening the cluster separation requirements for kfed. From a practical viewpoint, kfed also has many desirable properties: it requires only round of communication, can run asynchronously, and can handle partial participation or node/network failures. We motivate our analysis with experiments on common FL benchmarks, and highlight the practical utility of one-shot clustering through use-cases in personalized FL and device sampling.
Keywords: large scale learning · Algorithms

Author Information

Don Kurian Dennis (Carnegie Mellon University)
Tian Li (Carnegie Mellon University)
Virginia Smith (Carnegie Mellon University)
Virginia Smith

Virginia Smith is an assistant professor in the Machine Learning Department at Carnegie Mellon University, and a courtesy faculty member in the Electrical and Computer Engineering Department. Her research interests span machine learning, optimization, and distributed systems. Prior to CMU, Virginia was a postdoc at Stanford University, received a Ph.D. in Computer Science from UC Berkeley, and obtained undergraduate degrees in Mathematics and Computer Science from the University of Virginia.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors