Federated K-Means Clustering via Dual Decomposition-based Distributed
  Optimization
Vassilios Yfantis Achim Wagner Martin Ruskowski
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.