A Log-Linear Time Sequential Optimal Calibration Algorithm for Quantized Isotonic L2 Regression
This work addresses efficient sequential calibration in regression for applications requiring quantized outputs, but it is incremental as it builds on existing isotonic regression methods.
The paper tackles the problem of sequential calibration for quantized isotonic L2 regression by modifying the PAVA algorithm to achieve optimal quantized monotone mappings, resulting in an algorithm that updates in linear space and logarithmic time per new sample.
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.