Fast K-Means Clustering with Anderson Acceleration
  We propose a novel method to accelerate Lloyd's algorithm for K-Means
clustering. Unlike previous acceleration approaches that reduce computational
cost per iterations or improve initialization, our approach is focused on
reducing the number of iterations required for convergence. This is achieved by
treating the assignment step and the update step of Lloyd's algorithm as a
fixed-point iteration, and applying Anderson acceleration, a well-established
technique for accelerating fixed-point solvers. Classical Anderson acceleration
utilizes m previous iterates to find an accelerated iterate, and its
performance on K-Means clustering can be sensitive to choice of m and the
distribution of samples. We propose a new strategy to dynamically adjust the
value of m, which achieves robust and consistent speedups across different
problem instances. Our method complements existing acceleration techniques, and
can be combined with them to achieve state-of-the-art performance. We perform
extensive experiments to evaluate the performance of the proposed method, where
it outperforms other algorithms in 106 out of 120 test cases, and the mean
decrease ratio of computational time is more than 33%.
