An Improved Algorithm for Clustered Federated Learning

• URL: http://arxiv.org/abs/2210.11538v1
• Date: Thu, 20 Oct 2022 19:14:36 GMT
• Title: An Improved Algorithm for Clustered Federated Learning
• Authors: Harshvardhan, Avishek Ghosh and Arya Mazumdar
• Abstract summary: This paper addresses the dichotomy between heterogeneous models and simultaneous training in Federated Learning (FL) We define a new clustering model for FL based on the (optimal) local models of the users. textttSR-FCA uses a robust learning algorithm within each cluster to exploit simultaneous training and to correct clustering errors.
• Score: 29.166363192740768
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we address the dichotomy between heterogeneous models and simultaneous training in Federated Learning (FL) via a clustering framework. We define a new clustering model for FL based on the (optimal) local models of the users: two users belong to the same cluster if their local models are close; otherwise they belong to different clusters. A standard algorithm for clustered FL is proposed in \cite{ghosh_efficient_2021}, called \texttt{IFCA}, which requires \emph{suitable} initialization and the knowledge of hyper-parameters like the number of clusters (which is often quite difficult to obtain in practical applications) to converge. We propose an improved algorithm, \emph{Successive Refine Federated Clustering Algorithm} (\texttt{SR-FCA}), which removes such restrictive assumptions. \texttt{SR-FCA} treats each user as a singleton cluster as an initialization, and then successively refine the cluster estimation via exploiting similar users belonging to the same cluster. In any intermediate step, \texttt{SR-FCA} uses a robust federated learning algorithm within each cluster to exploit simultaneous training and to correct clustering errors. Furthermore, \texttt{SR-FCA} does not require any \emph{good} initialization (warm start), both in theory and practice. We show that with proper choice of learning rate, \texttt{SR-FCA} incurs arbitrarily small clustering error. Additionally, we validate the performance of our algorithm on standard FL datasets in non-convex problems like neural nets, and we show the benefits of \texttt{SR-FCA} over baselines.

Related papers

• Fair Minimum Representation Clustering via Integer Programming [0.6906005491572401]
  Clustering is an unsupervised learning task that aims to partition data into a set of clusters. In this paper, we study the k-means and k-medians clustering problems with the additional constraint that each group must have a minimum level of representation. We present an alternating minimization algorithm, called MiniReL, that directly incorporates the fairness constraints.
  arXiv  Detail & Related papers  (2024-09-04T00:13:40Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  We propose a new deep graph clustering method termed Reinforcement Graph Clustering. In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework. In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
  arXiv  Detail & Related papers  (2023-08-13T18:12:28Z)
• Large Language Models Enable Few-Shot Clustering [88.06276828752553]
  We show that large language models can amplify an expert's guidance to enable query-efficient, few-shot semi-supervised text clustering. We find incorporating LLMs in the first two stages can routinely provide significant improvements in cluster quality.
  arXiv  Detail & Related papers  (2023-07-02T09:17:11Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  We devise an efficient algorithm that recovers clusters using the observed labels. We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• Hybrid Fuzzy-Crisp Clustering Algorithm: Theory and Experiments [0.0]
  We propose a hybrid fuzzy-crisp clustering algorithm based on a target function combining linear and quadratic terms of the membership function. In this algorithm, the membership of a data point to a cluster is automatically set to exactly zero if the data point is sufficiently'' far from the cluster center. The proposed algorithm is demonstrated to outperform the conventional methods on imbalanced datasets and can be competitive on more balanced datasets.
  arXiv  Detail & Related papers  (2023-03-25T05:27:26Z)
• Personalized Federated Learning via Convex Clustering [72.15857783681658]
  We propose a family of algorithms for personalized federated learning with locally convex user costs. The proposed framework is based on a generalization of convex clustering in which the differences between different users' models are penalized.
  arXiv  Detail & Related papers  (2022-02-01T19:25:31Z)
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
  We present a new branch-and-bound algorithm for semi-supervised MSSC. Background knowledge is incorporated as pairwise must-link and cannot-link constraints. For the first time, the proposed global optimization algorithm efficiently manages to solve real-world instances up to 800 data points.
  arXiv  Detail & Related papers  (2021-11-30T17:08:53Z)
• Neural Mixture Models with Expectation-Maximization for End-to-end Deep Clustering [0.8543753708890495]
  In this paper, we realize mixture model-based clustering with a neural network. We train the network end-to-end via batch-wise EM iterations where the forward pass acts as the E-step and the backward pass acts as the M-step. Our trained networks outperform single-stage deep clustering methods that still depend on k-means.
  arXiv  Detail & Related papers  (2021-07-06T08:00:58Z)
• Clustered Federated Learning via Generalized Total Variation Minimization [83.26141667853057]
  We study optimization methods to train local (or personalized) models for local datasets with a decentralized network structure. Our main conceptual contribution is to formulate federated learning as total variation minimization (GTV) Our main algorithmic contribution is a fully decentralized federated learning algorithm.
  arXiv  Detail & Related papers  (2021-05-26T18:07:19Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)
• An Efficient Framework for Clustered Federated Learning [26.24231986590374]
  We address the problem of federated learning (FL) where users are distributed into clusters. We propose the Iterative Federated Clustering Algorithm (IFCA) We show that our algorithm is efficient in non- partitioned problems such as neural networks.
  arXiv  Detail & Related papers  (2020-06-07T08:48:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.