Research map / Learning theory and algorithms / Clustering

New Algorithms for the Learning-Augmented k-means Problem

ICLR 2025 · Learning theory and algorithms › Clustering · approach: k-means++ seeding analysis

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies learning-augmented k-means where a predicted-label oracle with error rate α guides clustering, proposing new algorithms with improved guarantees.

Problem

Clustering (k-means) in the learning-augmented setting, where a noisy oracle provides predicted labels with error rate α of false positives/negatives.

Approach

Uses predicted labels from an oracle with bounded error rate α as auxiliary information to improve k-means clustering performance, extending prior learning-augmented clustering work.

Closest papers by meaning

• Improved Learning-augmented Algorithms for k-means and k-medians Clustering (ICLR 2023 · similarity 0.93)
• Learning-Augmented $k$-means Clustering (ICLR 2022 · similarity 0.92)
• Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High Dimensions (AAAI 2026 · similarity 0.92)
• Learning-Augmented Algorithms for $k$-median via Online Learning (NeurIPS 2025 · similarity 0.90)
• Learning-Augmented Hierarchical Clustering (ICML 2025 · similarity 0.88)
• Near-Linear Time Approximation Algorithms for k-means with Outliers (ICML 2024 · similarity 0.86)