Abstract
Accurately estimating uncertainty is an essential component of decision-making and forecasting in machine learning. However, existing uncertainty estimation methods may fail when data no longer follows the distribution seen during training. Here, we introduce online uncertainty estimation algorithms that are guaranteed to be reliable on arbitrary streams of data points, including data chosen by an adversary. Specifically, our algorithms perform post-hoc recalibration of a black-box regression model and produce outputs that are provably calibrated -- i.e., an 80% confidence interval will contain the true outcome 80% of the time -- and that have low regret relative to the learning objective of the base model. We apply our algorithms in the context of Bayesian optimization, an online model-based decision-making task in which the data distribution shifts over time, and observe accelerated convergence to improved optima. Our results suggest that robust uncertainty quantification has the potential to improve online decision-making.
Introduction
Standard machine learning models are typically designed to minimize point-estimate error metrics, such as Mean Squared Error. However, in high-stakes applications like medical diagnostics or power grid management, point estimates are insufficient. Decision-makers require reliable uncertainty quantification—knowing how certain a model is about its predictions.
Calibration ensures that a model's probabilistic forecasts are trustworthy; for example, an "80% confidence interval" should contain the true value 80% of the time. Traditional calibration methods often assume that data is Independent and Identically Distributed (IID). In real-world scenarios, data distributions frequently shift over time or may be subject to adversarial manipulation. This research introduces a framework for online calibrated regression that maintains both calibration and low regret (performance parity with a baseline) even under adversarial conditions.
Methodology: Online Recalibration
The proposed approach, Algorithm 1: Online Recalibration, acts as a post-hoc wrapper for any black-box regression model. It refines the model's outputs through several key mechanisms:
- Discretization and Experts: The probability space $[0, 1]$ is partitioned into $M$ intervals. Each interval is assigned a binary calibration subroutine (such as the Foster & Vohra algorithm) that acts as an "expert" for that specific range.
- Proper Loss Functions: To ensure that recalibration does not degrade the model's predictive accuracy, the authors utilize the Continuous Ranked Probability Score (CRPS). As a "proper loss," CRPS is minimized only by the true probability distribution, allowing the model to remain "sharp" while becoming calibrated.
- Randomization: The algorithm incorporates randomization, which is theoretically necessary to achieve calibration against an adversary.
Experimental Evaluation
The researchers evaluated the algorithm's performance on multivariate regression tasks using UCI datasets (Aquatic Toxicity, Energy Efficiency, and Facebook Comment Volume) and standard Bayesian Optimization (BO) benchmarks (Ackley, SixHumpCamel, Alpine, Beale, and Mccormick).
Calibration Results
On all UCI datasets, the online recalibration method achieved significantly lower calibration errors than raw models or standard Kernel Density Estimation (KDE) baselines. The algorithm demonstrates a consistent ability to reduce error over time, even in non-stationary environments.
Bayesian Optimization Performance
In Bayesian Optimization, where the data distribution shifts as the algorithm explores new regions of the search space, robust uncertainty quantification is vital. The calibrated models showed markedly faster convergence to global optima. For instance, on the SixHumpCamel benchmark, the calibrated approach reached a deeper optimum in roughly half the iterations required by the uncalibrated baseline.
Discussion and Key Insights
The study highlights several critical findings for robust forecasting:
- The Role of Proper Losses: The paper proves that recalibration is impossible without using a proper loss function like CRPS. This ensures the model stays performant while gaining reliability.
- Vanishing Regret: Theoretical guarantees ensure that the recalibrated model will eventually perform at least as well as the original uncalibrated forecaster.
- Model Agnosticism: The method is compatible with any black-box model (e.g., Neural Networks or Gaussian Processes) as long as its Cumulative Distribution Function (CDF) forecasts are accessible.
Limitations
While effective, the method introduces some computational overhead due to the $M$ binary subroutines. Additionally, the current theoretical proofs assume that the target variable $y$ is bounded within a known range. Extending these guarantees to unbounded distributions and optimizing hyperparameter selection (such as the number of intervals $M$) remain areas for future work.
Conclusion
By bridging the gap between adversarial online learning and probabilistic calibration, this work establishes a robust foundation for deploying machine learning in dynamic, high-stakes environments where reliable uncertainty estimation is paramount.
Summary updated