Jichan Chung and Avishek Ghosh and Dong Yin and Kangwook Lee and Kannan Ramchandran

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2023-212

August 11, 2023

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-212.pdf

We address the problem of Federated Learning (FL) where users are distributed and their datapoints are partitioned into clusters. This setup captures settings where users have their own objectives (learning tasks) but by aggregating their data with others in the same cluster (same learning task), they can leverage the strength in numbers in order to perform more efficient Federated Learning. We propose a framework dubbed the Iterative Federated Clustering Algorithm (IFCA), which alternately estimates the cluster identities of the users and optimizes model parameters for the user clusters via gradient descent. We analyze the convergence rate of this algorithm first in a linear model with squared loss and then for generic strongly convex and smooth loss functions. We show that in both settings, with good initialization, IFCA converges at an exponential rate, and discuss the optimality of the statistical error rate. When the clustering structure is ambiguous, we propose to train the models by combining IFCA with the weight sharing technique in multi-task learning. In the experiments, we show that our algorithm can succeed even if we relax the requirements on initialization with random initialization and multiple restarts. We also present experimental results showing that our algorithm is efficient in non-convex problems such as neural networks. We demonstrate the benefits of IFCA over the baselines on several clustered FL benchmarks. We also develop an extension of our framework for a more general setting where statistical heterogeneity can exist across clients, named UIFCA. For synthetic data, we observe that UIFCA can correctly recover the cluster information of individual datapoints. We also provide analysis of UIFCA on MNIST dataset.

Advisors: Kannan Ramchandran

---

BibTeX citation:

@mastersthesis{Chung:EECS-2023-212,
    Author= {Chung, Jichan and Ghosh, Avishek and Yin, Dong and Lee, Kangwook and Ramchandran, Kannan},
    Title= {Efficient Clustering Frameworks for Federated Learning Systems},
    School= {EECS Department, University of California, Berkeley},
    Year= {2023},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-212.html},
    Number= {UCB/EECS-2023-212},
    Abstract= {We address the problem of Federated Learning (FL) where users are distributed and their datapoints are partitioned into clusters.
This setup captures settings where users have their own objectives (learning tasks) but by aggregating their data with others in the same cluster (same learning task), they can leverage the strength in numbers in order to perform more efficient Federated Learning.
We propose a framework dubbed the Iterative Federated Clustering Algorithm (IFCA), which alternately estimates the cluster identities of the users and optimizes model parameters for the user clusters via gradient descent.
We analyze the convergence rate of this algorithm first in a linear model with squared loss and then for generic strongly convex and smooth loss functions. We show that in both settings, with good initialization, IFCA converges at an exponential rate, and discuss the optimality of the statistical error rate. When the clustering structure is ambiguous, we propose to train the models by combining IFCA with the weight sharing technique in multi-task learning. In the experiments, we show that our algorithm can succeed even if we relax the requirements on initialization with random initialization and multiple restarts. We also present experimental results showing that our algorithm is efficient in non-convex problems such as neural networks.
We demonstrate the benefits of IFCA over the baselines on several clustered FL benchmarks.
We also develop an extension of our framework for a more general setting where statistical heterogeneity can exist across clients, named UIFCA.
For synthetic data, we observe that UIFCA can correctly recover the cluster information of individual datapoints.
We also provide analysis of UIFCA on MNIST dataset.},
}

EndNote citation:

%0 Thesis
%A Chung, Jichan 
%A Ghosh, Avishek 
%A Yin, Dong 
%A Lee, Kangwook 
%A Ramchandran, Kannan 
%T Efficient Clustering Frameworks for Federated Learning Systems
%I EECS Department, University of California, Berkeley
%D 2023
%8 August 11
%@ UCB/EECS-2023-212
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-212.html
%F Chung:EECS-2023-212