# Efficient, Anytime Algorithms for Calibration with Isotonic Regression under Strictly Convex Losses

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 46 references that are in the map.
- First posted on arXiv 31 Oct 2021.

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

- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [Binary Classifier Calibration using an Ensemble of Near Isotonic Regression Models](https://mlsanity.com/paper/1511.05191/) (2015)
- [Sequential Outlier Detection based on Incremental Decision Trees](https://mlsanity.com/paper/1803.03674/) (2018)
- [Optimally Efficient Sequential Calibration of Binary Classifiers to Minimize Classification Error](https://mlsanity.com/paper/2108.08780/) (2021)

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

- [A Log-Linear Time Sequential Optimal Calibration Algorithm for Quantized Isotonic L2 Regression](https://mlsanity.com/paper/2206.00744/) (2022)
- [Merging Knockout and Round-Robin Tournaments: A Flexible Linear Elimination Tournament Design](https://mlsanity.com/paper/2203.12011/) (2022)
- [Robust, Nonparametric, Efficient Decomposition of Spectral Peaks under Distortion and Interference](https://mlsanity.com/paper/2204.08411/) (2022)
- [A Note On Nonlinear Regression Under L2 Loss](https://mlsanity.com/paper/2303.17745/) (2023)
- [Sequential Linearithmic Time Optimal Unimodal Fitting When Minimizing Univariate Linear Losses](https://mlsanity.com/paper/2304.02141/) (2023)

## Abstract (arXiv)

We investigate the calibration of estimations to increase performance with an optimal monotone transform on the estimator outputs. We start by studying the traditional square error setting with its weighted variant and show that the optimal monotone transform is in the form of a unique staircase function. We further show that this staircase behavior is preserved for general strictly convex loss functions. Their optimal monotone transforms are also unique, i.e., there exist a single staircase transform that achieves the minimum loss. We propose a linear time and space algorithm that can find such optimal transforms for specific loss settings. Our algorithm has an online implementation where the optimal transform for the samples observed so far are found in linear space and amortized time when the samples arrive in an ordered fashion. We also extend our results to cases where the functions are not trivial to individually optimize and propose an anytime algorithm, which has linear space and pseudo-linearithmic time complexity.