Federated K-Means Clustering via Dual Decomposition-based Distributed Optimization
This work addresses the challenge of distributed machine learning for clustering tasks, which is incremental as it adapts existing optimization techniques to a specific problem.
The paper tackles the problem of training K-means clustering models in a distributed or federated setting, where data is split across nodes for privacy or efficiency, by applying dual decomposition-based optimization methods. It evaluates subgradient, bundle trust, and quasi-Newton dual ascent algorithms on benchmark problems, noting that while the mixed-integer formulation has weak relaxations, the approach could enable efficient solutions in the future.
The use of distributed optimization in machine learning can be motivated either by the resulting preservation of privacy or the increase in computational efficiency. On the one hand, training data might be stored across multiple devices. Training a global model within a network where each node only has access to its confidential data requires the use of distributed algorithms. Even if the data is not confidential, sharing it might be prohibitive due to bandwidth limitations. On the other hand, the ever-increasing amount of available data leads to large-scale machine learning problems. By splitting the training process across multiple nodes its efficiency can be significantly increased. This paper aims to demonstrate how dual decomposition can be applied for distributed training of $ K $-means clustering problems. After an overview of distributed and federated machine learning, the mixed-integer quadratically constrained programming-based formulation of the $ K $-means clustering training problem is presented. The training can be performed in a distributed manner by splitting the data across different nodes and linking these nodes through consensus constraints. Finally, the performance of the subgradient method, the bundle trust method, and the quasi-Newton dual ascent algorithm are evaluated on a set of benchmark problems. While the mixed-integer programming-based formulation of the clustering problems suffers from weak integer relaxations, the presented approach can potentially be used to enable an efficient solution in the future, both in a central and distributed setting.