A Log-Linear Time Sequential Optimal Calibration Algorithm for Quantized Isotonic L2 Regression

2022/06/01 by Kaan Gökcesu, Gokcesu, Kaan, Hakan Gökcesu +1
Engineering · Mathematics · #Advanced Control Systems Optimization #Algorithm #Calibration #Computer science #Control Systems and Identification #Fault Detection and Control Systems #Isotonic #Isotonic regression #Linear regression #Logarithm #Mathematical analysis #Mathematical optimization #Mathematics #Monotone polygon #Regression analysis #Statistics

paper · pdf · doi:10.48550/arxiv.2206.00744

openalex publication_date 2022/06/01 · openalex created_date 2022/06/13 · openalex updated_date 2026/08/05

Abstract

We study the sequential calibration of estimations in a quantized isotonic L2 regression setting. We start by showing that the optimal calibrated quantized estimations can be acquired from the traditional isotonic L2 regression solution. We modify the traditional PAVA algorithm to create calibrators for both batch and sequential optimization of the quantized isotonic regression problem. Our algorithm can update the optimal quantized monotone mapping for the samples observed so far in linear space and logarithmic time per new unordered sample.

Related

• Efficient, Anytime Algorithms for Calibration with Isotonic Regression under Strictly Convex Losses
• An analysis of binary isotonic regression: degrees of freedom and implications for calibration
• L infinity Isotonic Regression for Linear, Multidimensional, and Tree Orders
• Lipschitz Unimodal and Isotonic Regression on Paths and Trees
• Optimal Reduced Isotonic Regression