# A Batch-to-Online Transformation under Random-Order Model

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 27 references that are in the map.
- First posted on arXiv 12 Jun 2023.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Online k-means Clustering](https://mlsanity.com/paper/1909.06861/) (2019)
- [Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge](https://mlsanity.com/paper/2111.01602/) (2021)
- [Optimal Rates for Random Order Online Optimization](https://mlsanity.com/paper/2106.15207/) (2021)
- [Average Sensitivity of Graph Algorithms](https://mlsanity.com/paper/1904.03248/) (2019)
- [Average Sensitivity of Spectral Clustering](https://mlsanity.com/paper/2006.04094/) (2020)
- [Average Sensitivity of Dynamic Programming](https://mlsanity.com/paper/2111.02657/) (2021)
- [Sensitivity Analysis of the Maximum Matching Problem](https://mlsanity.com/paper/2009.04556/) (2020)

## Built on by (most cited first, 2 of 2)

- [Online Learning in the Random Order Model](https://mlsanity.com/paper/2510.02820/) (2025)
- [From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model](https://mlsanity.com/paper/2602.09457/) (2026)

## Abstract (arXiv)

We introduce a transformation framework that can be utilized to develop online algorithms with low ε-approximate regret in the random-order model from offline approximation algorithms. We first give a general reduction theorem that transforms an offline approximation algorithm with low average sensitivity to an online algorithm with low ε-approximate regret. We then demonstrate that offline approximation algorithms can be transformed into a low-sensitivity version using a coreset construction method. To showcase the versatility of our approach, we apply it to various problems, including online (k,z)-clustering, online matrix approximation, and online regression, and successfully achieve polylogarithmic ε-approximate regret for each problem. Moreover, we show that in all three cases, our algorithm also enjoys low inconsistency, which may be desired in some online applications.