mlsanityData to 14 Oct 2026

Learning-Augmented k-means Clustering

arXiv 2110.14094 ↗First posted 27 Oct 2021cs.LG cs.DScited by 26

Not on the map. Why?

Abstract (arXiv)

k-means clustering is a well-studied problem due to its wide applicability. Unfortunately, there exist strong theoretical limits on the performance of any algorithm for the k-means problem on worst-case inputs. To overcome this barrier, we consider a scenario where "advice" is provided to help perform clustering. Specifically, we consider the k-means problem augmented with a predictor that, given any point, returns its cluster label in an approximately optimal clustering up to some, possibly adversarial, error. We present an algorithm whose performance improves along with the accuracy of the predictor, even though na"ively following the accurate predictor can still lead to a high clustering cost. Thus if the predictor is sufficiently accurate, we can retrieve a close to optimal clustering with nearly optimal runtime, breaking known computational barriers for algorithms that do not have access to such advice. We evaluate our algorithms on real datasets and show significant improvements in the quality of clustering.

Key facts. Cited by 26 papers in the map (data through 14 Oct 2026). Builds on 31 of its 74 references that are in the map. First posted on arXiv 27 Oct 2021.

Builds on

31 of 74 references.

References · 31

  1. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  2. 2017Compressed Sensing using Generative Modelscited by 339
  3. 2018Competitive caching with machine learned advicecited by 195
  4. 2017The Case for Learned Index Structurescited by 188
  5. 2020Algorithms with Predictionscited by 153
  6. 2018Spreading vectors for similarity searchcited by 118
  7. 2019A Model for Learned Bloom Filters, and Optimizing by Sandwichingcited by 64
  8. 2021Faster Matchings via Learned Dualscited by 56
  9. 2016Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithmscited by 54
  10. 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
  11. 2018Approximate Nearest Neighbor Search in High Dimensionscited by 47
  12. 2015A Deep Learning Approach to Structured Signal Recoverycited by 43
19 more
  1. 2015Learning to Hash for Indexing Big Data - A Surveycited by 39
  2. 2016Geometric Median in Nearly Linear Timecited by 39
  3. 2017Training Gaussian Mixture Models at Scale via Coresetscited by 38
  4. 2017Clustering with Noisy Queriescited by 34
  5. 2016Clustering with Same-Cluster Queriescited by 29
  6. 2015Improved and Simplified Inapproximability for k-meanscited by 22
  7. 2021Learning-based Support Estimation in Sublinear Timecited by 16
  8. 2013Local algorithms for interactive clusteringcited by 14
  9. 2021Dimensionality Reduction for Wasserstein Barycentercited by 13
  10. 2019A Unified Approach to Robust Mean Estimationcited by 11
  11. 2019Same-Cluster Querying for Overlapping Clusterscited by 11
  12. 2016Interactive Bayesian Hierarchical Clusteringcited by 9
  13. 2019Scalable Learning-Based Sampling Optimization for Compressive Dynamic MRIcited by 9
  14. 2018Query K-means Clustering and the Double Dixie Cup Problemcited by 8
  15. 2017Approximate Clustering with Same-Cluster Queriescited by 7
  16. 2015k-center Clustering under Perturbation Resiliencecited by 6
  17. 2017Relaxed Oracles for Semi-Supervised Clusteringcited by 4
  18. 2018Semi-Supervised Algorithms for Approximately Optimal and Accurate Clusteringcited by 4
  19. 2017Improved Clustering with Augmented k-meanscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 4; 2023: 3; 2024: 6; 2025: 7; 2026: 6.

26 papers.

Sort:

  1. 2023Sorting with Predictionscited by 14
  2. 2024Algorithms for Caching and MTS with reduced number of predictionscited by 12
  3. 2022Learning-Augmented Algorithms for Online Linear and Semidefinite Programmingcited by 11
  4. 2024Learning-augmented Maximum Independent Setcited by 11
  5. 2022Paging with Succinct Predictionscited by 10
  6. 2022Improved Learning-augmented Algorithms for k-means and k-medians Clusteringcited by 10
  7. 2023Improved Frequency Estimation Algorithms with and without Predictionscited by 10
  8. 2024Online Classification with Predictionscited by 5
  9. 2024Learning-Augmented Search Data Structurescited by 4
  10. 2025Improved Approximations for Hard Graph Problems using Predictionscited by 4
  11. 2022On the Power of Learning-Augmented Search Treescited by 3
  12. 2023Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster L-/L^natural-Convex Function Minimizationcited by 3
14 more
  1. 2026Learning-Augmented Moment Estimation on Time-Decay Modelscited by 2
  2. 2024On Approximability of ℓ22 Min-Sum Clusteringcited by 1
  3. 2025Learning-Augmented Algorithms for Boolean Satisfiabilitycited by 1
  4. 2025Optimizing Health Coverage in Ethiopia: A Learning-augmented Approach and Persistent Proportionality Under an Online Budgetcited by 1
  5. 2025Learning-Augmented Streaming Algorithms for Correlation Clusteringcited by 1
  6. 2025Learning-Augmented Ski Rental with Discrete Distributions: A Bayesian Approachcited by 1
  7. 2026Learning-augmented smooth integer programs with PAC-learnable oraclescited by 1
  8. 2024A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectivescited by 0
  9. 2025Learning Augmented Graph k-Clusteringcited by 0
  10. 2025Transductive and Learning-Augmented Online Regressioncited by 0
  11. 2026Metric k-clustering using only Weak Comparison Oraclescited by 0
  12. 2026Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completioncited by 0
  13. 2026Learning-Augmented Algorithms for k-median via Online Learningcited by 0
  14. 2026Robust and Consistent Ski Rental with Distributional Advicecited by 0