Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning-Augmented Algorithms for $k$-median via Online Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the Learn-Median model, where a learning-augmented algorithm sees a sequence of k-median instances and must match the average approximation ratio of the best fixed solution in hindsight, giving deterministic O(k) and randomized O(1) competitive algorithms with sublinear regret.
Problem
Online learning-augmented k-median clustering on an evolving sequence of instances: match, in average approximation ratio, the best fixed k-median solution in hindsight when the metric space and solution space grow over time.
Approach
Reduce each k-median instance to k weighted proxy centers, then run online mirror descent on a fractional solution with a hyperbolic entropy regularizer whose domain grows as new points appear, compare against phase-wise locally optimal solutions, and round online (deterministic greedy or randomized thresholding).
Key results
- Deterministic algorithm achieves competitive ratio O(k) with sublinear regret O(k^4 Δ sqrt(T) log T log(Tk)); randomized achieves O(1) competitive ratio with regret O(k^3 Δ sqrt(T) log T log(Tk)).
- Matching lower bounds: no deterministic algorithm with ratio o(k), and no algorithm with ratio 1+ε and sublinear regret.
- Experiments show approximation ratios approaching 1 on i.i.d. instances, and in the oscillating setting the algorithm can outperform the best fixed solution in hindsight by adapting over time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the online algorithm on i.i.d. Uniform Square instances | Learn-Median deterministic and randomized algorithms · Uniform Square | approximation ratio | Helped |
| Use the online algorithm on i.i.d. Multiple Clusters instances | Learn-Median deterministic and randomized algorithms · Multiple Clusters | approximation ratio | Helped |
| Adapt center placement online as geometrically increasing batches alternate between two clusters | Learn-Median algorithm, k=1 · Oscillating Instances | cumulative approximation ratio relative to the best fixed solution | Helped |
| Introduce the origin into the instances around the 100th iteration | Learn-Median fractional algorithm, k=1 · Uniform Hypersphere | fractional mass at the origin | Helped |
| Present geometrically increasing batches from different clusters | Learn-Median fractional algorithm · Scale Changing | fractional mass in the currently presented cluster | Helped |
Surprising findings
- In the oscillating-instances experiment, the algorithm sometimes outperforms the best fixed solution in hindsight because it adapts over time.
- Pure sublinear regret with competitive ratio 1 is impossible in this setting even for k=1, unlike when the full metric space is known in advance.
Limitations
- Techniques are tailored to metric problems such as k-median and may not extend to covering-type problems.
- Regret bounds depend on k and aspect ratio Δ, and an Ω(kΔ) dependence is necessary for constant competitive ratio.
- Running time is cubic in T, with the distance matrix as bottleneck.
Experimental setup
Datasets: synthetic instances: uniform square multiple clusters oscillating instances uniform hypersphere scale changing
Benchmarks: synthetic k-median sequences (uniform square, multiple clusters, oscillating, hypersphere, scale changing)
Metrics: approximation ratio cumulative average approximation loss center locations and fractional mass over time
Baselines: best fixed k-median solution in hindsight follow the leader online gradient descent regularizer exponentiated gradient regularizer
Builds on: online mirror descent hyperbolic entropy regularizer learning-augmented algorithms with online learning of predictions
Closest papers by meaning
- Average Sensitivity of Hierarchical $k$-Median Clustering (ICML 2025 · similarity 0.88)
- Learning-Augmented Hierarchical Clustering (ICML 2025 · similarity 0.87)
- Dynamic Algorithm for Explainable $k$-medians Clustering under $\ell_p$ Norm (NeurIPS 2025 · similarity 0.87)
- Towards a Theoretical Understanding of Why Local Search Works for Clustering with Fair-Center Representation (AAAI 2024 · similarity 0.85)
- Approximately Pareto-optimal Solutions for Bi-Objective k-Clustering (NeurIPS 2024 · similarity 0.85)
- Learning-Augmented Algorithms with Explicit Predictors (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.