Memory and Communication Efficient Federated Kernel k-Means.

Area of Science:

• Machine Learning
• Data Mining
• Distributed Computing

Background:

• Distributed clustering algorithms often require substantial memory and communication resources on user devices.
• Existing methods struggle to balance efficiency and accuracy in federated learning environments.

Purpose of the Study:

• To develop a federated kernel k-means (FedKKM) algorithm for low-memory, distributed clustering.
• To enhance communication efficiency in federated learning for clustering tasks.

Main Methods:

• Introduced a federated eigenvector approximation (FEA) algorithm using low-dimensional random feature vectors.
• Designed a communication-efficient Lanczos algorithm (CELA) to reduce iterative communication costs within FEA.
• Leveraged a distributed linear k-means algorithm for final clustering based on approximate vectors.

Main Results:

• FEA demonstrates a convergence rate of O(1/T).
• FedKKM's scalability is independent of dataset size due to communication cost independence from user data volume.
• FedKKM is a (1+ϵ) approximation algorithm, achieving comparable quality to centralized kernel k-means.
• Experimental results show up to 94% reduction in memory consumption and over 40% reduction in communication cost compared to state-of-the-art methods.

Conclusions:

• FedKKM offers a highly efficient solution for distributed clustering in federated learning.
• The algorithm significantly reduces on-device memory and communication overhead without compromising clustering accuracy.
• FedKKM presents a practical approach for privacy-preserving, large-scale data analysis.