# Learning-Augmented Algorithms for k-median via Online Learning

arXiv: https://arxiv.org/abs/2603.18157 · HTML: https://mlsanity.com/paper/2603.18157/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 35 references that are in the map.
- First posted on arXiv 18 Mar 2026.

## Builds on (most cited first, 19 of 19)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017)
- [Exponentiated Gradient Meets Gradient Descent](https://mlsanity.com/paper/1902.01903/) (2019)
- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Learning Predictions for Algorithms with Predictions](https://mlsanity.com/paper/2202.09312/) (2022)
- [Online Facility Location with Predictions](https://mlsanity.com/paper/2110.08840/) (2021)
- [Online k-means Clustering](https://mlsanity.com/paper/1909.06861/) (2019)
- [Improved Learning-augmented Algorithms for k-means and k-medians Clustering](https://mlsanity.com/paper/2210.17028/) (2022)
- [Facility Location in Evolving Metrics](https://mlsanity.com/paper/1403.6758/) (2014)
- [Clustering Stream Data by Exploring the Evolution of Density Mountain](https://mlsanity.com/paper/1710.00867/) (2017)
- [Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent](https://mlsanity.com/paper/2011.02817/) (2020)
- [Dynamic Facility Location via Exponential Clocks](https://mlsanity.com/paper/1411.4476/) (2014)
- [Improved Bounds for Online Facility Location with Predictions](https://mlsanity.com/paper/2107.08277/) (2021)
- [Online Learning of Facility Locations](https://mlsanity.com/paper/2007.02801/) (2020)
- [MOStream: A Modular and Self-Optimizing Data Stream Clustering Algorithm](https://mlsanity.com/paper/2309.04799/) (2023)
- [Universal Algorithms for Clustering Problems](https://mlsanity.com/paper/2105.02363/) (2021)
- [Efficient Online Learning for Dynamic k-Clustering](https://mlsanity.com/paper/2106.04336/) (2021)

## Abstract (arXiv)

The field of learning-augmented algorithms seeks to use ML techniques on past instances of a problem to inform an algorithm designed for a future instance. In this paper, we introduce a novel model for learning-augmented algorithms inspired by online learning. In this model, we are given a sequence of instances of a problem and the goal of the learning-augmented algorithm is to use prior instances to propose a solution to a future instance of the problem. The performance of the algorithm is measured by its average performance across all the instances, where the performance on a single instance is the ratio between the cost of the algorithm's solution and that of an optimal solution for that instance. We apply this framework to the classic k-median clustering problem, and give an efficient learning algorithm that can approximately match the average performance of the best fixed k-median solution in hindsight across all the instances. We also experimentally evaluate our algorithm and show that its empirical performance is close to optimal, and also that it automatically adapts the solution to a dynamically changing sequence.