# Online Isotonic Regression

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Mar 2016.

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

- [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021)
- [Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond](https://mlsanity.com/paper/2201.08905/) (2022)
- [Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms](https://mlsanity.com/paper/2305.19570/) (2023)
- [Simultaneous Swap Regret Minimization via KL-Calibration](https://mlsanity.com/paper/2502.16387/) (2025)
- [An Optimal Reduction of TV-Denoising to Adaptive Online Learning](https://mlsanity.com/paper/2101.09438/) (2021)
- [Second Order Path Variationals in Non-Stationary Online Learning](https://mlsanity.com/paper/2205.01921/) (2022)
- [Spatially Adaptive Online Prediction of Piecewise Regular Functions](https://mlsanity.com/paper/2203.16587/) (2022)
- [Robust Cell-Load Learning with a Small Sample Set](https://mlsanity.com/paper/2103.11467/) (2021)
- [Private Isotonic Regression](https://mlsanity.com/paper/2210.15175/) (2022)

## Abstract (arXiv)

We consider the online version of the isotonic regression problem. Given a set of linearly ordered points (e.g., on the real line), the learner must predict labels sequentially at adversarially chosen positions and is evaluated by her total squared loss compared against the best isotonic (non-decreasing) function in hindsight. We survey several standard online learning algorithms and show that none of them achieve the optimal regret exponent; in fact, most of them (including Online Gradient Descent, Follow the Leader and Exponential Weights) incur linear regret. We then prove that the Exponential Weights algorithm played over a covering net of isotonic functions has a regret bounded by Obig(T1/3 log2/3(T)big) and present a matching Omega(T1/3) lower bound on regret. We provide a computationally efficient version of this algorithm. We also analyze the noise-free case, in which the revealed labels are isotonic, and show that the bound can be improved to O(log T) or even to O(1) (when the labels are revealed in isotonic order). Finally, we extend the analysis beyond squared loss and give bounds for entropic loss and absolute loss.