Improved Learning-augmented Algorithms for k-means and k-medians Clustering

Thy Nguyen, Anamay Chaturvedi, Huy Le Nguyen

Abstract

Clustering is a cornerstone of data science, yet achieving optimal solutions remains computationally intensive. This paper presents novel learning-augmented algorithms for $k$-means and $k$-medians clustering that utilize noisy "advice" from machine learning predictors. By introducing a deterministic filtering approach for $k$-means and a robust "clipping" strategy for $k$-medians, the proposed methods achieve superior approximation guarantees and maintain robustness even with label error rates up to 50% ($\alpha = 1/2$). Theoretical analysis and empirical evaluations on datasets like MNIST and CIFAR-10 demonstrate significant improvements in both accuracy and scalability compared to existing state-of-the-art methods.

Introduction

Traditional clustering algorithms, such as Lloyd’s algorithm for $k$-means, often lack strong theoretical guarantees or face scalability issues on massive datasets. The emerging field of learning-augmented algorithms addresses these challenges by incorporating "advice"—such as predicted cluster labels from a pre-trained model—to guide the optimization process. However, previous approaches were limited by strict requirements on predictor accuracy (typically $\alpha < 1/7$) and cluster size constraints.

This work overcomes these limitations by developing algorithms that are robust to high noise levels. The authors identify $\alpha = 1/2$ as a fundamental threshold for label-based clustering; beyond this point, labels become inherently ambiguous as they could represent an entirely different cluster. Their algorithms are the first to remain effective up to this theoretical limit while removing constraints on minimum cluster sizes, making them applicable to highly imbalanced datasets.

Methods

The paper introduces two primary algorithmic innovations designed to handle noisy advice:

Deterministic $k$-means (Algorithm 1)

In $k$-means clustering, outliers in predicted labels can significantly distort the computed cluster centers. To mitigate this, Algorithm 1 employs a deterministic filtering mechanism. Instead of a simple average, it identifies a contiguous subset of points in each dimension that minimizes internal variance. This "densest subset" approach effectively isolates the signal from the noise without the instability inherent in randomized sampling methods.

Robust $k$-medians (Algorithm 2)

For $k$-medians, the authors implement a "clipping" strategy. The algorithm samples a reference point from the predicted cluster, removes distant points (potential outliers), and computes the geometric median of the remaining set. This process is repeated to ensure a high probability of success, refining the approximation factor from a complex biquadratic relationship to a near-linear dependence on the error rate $\alpha$.

Results and Discussion

The proposed algorithms were evaluated against the previous state-of-the-art (Ergun et al., 2022) across several dimensions: approximation factor, error tolerance, and time complexity.

Comparison of approximation factors, label error ranges, and time complexities between previous work and the proposed algorithms.

As shown in the table above, Algorithm 1 improves the $k$-means approximation factor from $(1 + 20\alpha)$ to $(1 + 7.7\alpha)$ for small error rates, while extending the tolerable error range from $1/7$ to $1/2$. Similarly, Algorithm 2 for $k$-medians provides a more robust approximation and handles significantly higher noise levels than previous work. Notably, the $k$-means algorithm maintains a nearly linear time complexity of $O(md \log m)$, ensuring high scalability.

Empirical Performance

Testing on real-world datasets—CIFAR-10, MNIST, and PHY—confirmed these theoretical gains. To simulate realistic scenarios, the authors generated noisy labels by corrupting optimal clusterings at various rates. The new algorithms consistently matched or outperformed existing methods, with the $k$-medians approach achieving the lowest clustering costs across all benchmarks. The experiments confirmed that even when the error rate $\alpha$ is high (e.g., 0.4 or 0.5), the algorithms still provide useful results, whereas older methods would fail.

Conclusion

This work significantly advances the state of learning-augmented clustering by providing algorithms that are both theoretically robust and practically efficient. By pushing the error tolerance to the 50% threshold and improving approximation factors, these methods make "advice-driven" clustering viable for a wider range of real-world applications where predictors may be imperfect. Future research could focus on automating the estimation of the error rate $\alpha$ and extending these techniques to more general metric spaces beyond Euclidean distance.

Summary updated

BibTeX
@inproceedings{nguyen2023improved,
  author = {Thy Nguyen and Anamay Chaturvedi and Huy Le Nguyen},
  title = {{Improved Learning-augmented Algorithms for k-means and k-medians Clustering}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=dCSFiAl_VO3},
}
Figure