Adaptive Calibration in Non-Stationary Environments

• URL: http://arxiv.org/abs/2605.11490v1
• Date: Tue, 12 May 2026 04:06:40 GMT
• Title: Adaptive Calibration in Non-Stationary Environments
• Abstract summary: We develop a suite of algorithms that achieve adaptive calibration guarantees under multiple calibration measures.<n>Our approach builds on and extends prior work [Hu et al., 2026, Luo et al., 2025], introducing a novel non-uniform partition of the prediction space that allocates finer resolution near the underlying ground truth.
• Score: 44.81344039432424
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Making calibrated online predictions is a central challenge in modern AI systems. Much of the existing literature focuses on fully adversarial environments where outcomes may be arbitrary, leading to conservative algorithms that can perform suboptimally in more benign settings, such as when outcomes are nearly stationary. This gap raises a natural question: can we design online prediction algorithms whose calibration error automatically adapts to the degree of non-stationarity in the environment, smoothly interpolating between i.i.d. and adversarial regimes? We answer this question in the affirmative and develop a suite of algorithms that achieve adaptive calibration guarantees under multiple calibration measures. Specifically, with $T$ being the number of rounds and $C\in[0,T]$ being an unknown non-stationary measure defined as the minimal $\ell_1$ deviation of the mean outcomes, our algorithms attain $\widetilde{O}(\sqrt{T}+(TC)^{\frac{1}{3}})$ for $\ell_1$ calibration error and $\widetilde{O}((1+C)^{\frac{1}{3}})$ for both $\ell_2$ and pseudo KL calibration error. These bounds match the optimal rates in the stationary case ($C=0$) and recover known guarantees in the fully adversarial regime ($C=T$). Our approach builds on and extends prior work [Hu et al., 2026, Luo et al., 2025], introducing an epoch-based scheduling together with a novel non-uniform partition of the prediction space that allocates finer resolution near the underlying ground truth.

Related papers

• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  We investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner.<n>The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm.<n>We establish an information-theoretic lower bound that scales as $(sqrtmathbbE[S_T])$, providing a fundamental characterization of the best achievable prediction-adaptive regret.
  arXiv  Detail & Related papers  (2026-05-21T08:57:38Z)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  Self-distillation (SD) is the process of retraining a student on a mixture of ground-truth and the teacher's own predictions.<n>We show that for any prediction risk, the optimally mixed student improves upon the ridge teacher for every regularization level.<n>We propose a consistent one-shot tuning method to estimate $star$ without grid search, sample splitting, or refitting.
  arXiv  Detail & Related papers  (2026-02-19T17:21:15Z)
• Near-optimal Swap Regret Minimization for Convex Losses [21.006993033547708]
  We give a randomized online algorithm that guarantees near-optimal $widetilde O(sqrt T)$ expected swap regret against any sequence of $T$ adaptively chosen Lipschitz convex losses on the unit interval.
  arXiv  Detail & Related papers  (2026-02-09T16:26:34Z)
• Efficient Calibration for Decision Making [26.81026842833163]
  Hu and Wu (FOCS'24) use this to define an approximate calibration measure called calibration decision loss ($mathsfCDL$)<n>We develop a comprehensive theory of when $mathsfCDL_K$ is information-theoretically and computationally tractable.
  arXiv  Detail & Related papers  (2025-11-17T18:52:00Z)
• Truthfulness of Decision-Theoretic Calibration Measures [5.414308305392762]
  We introduce a new calibration measure termed subsampled step calibration, $mathsfStepCEtextsfsub$, that is both decision-theoretic and truthful.<n>In particular, on any product distribution, $mathsfStepCEtextsfsub$ is truthful up to an $O(1)$ factor whereas prior decision-theoretic calibration measures suffer from an $e-Omega(T)$-$Omega(sqrtT)$ truthfulness gap.
  arXiv  Detail & Related papers  (2025-03-04T08:20:10Z)
• Orthogonal Causal Calibration [55.28164682911196]
  We develop general algorithms for reducing the task of causal calibration to that of calibrating a standard (non-causal) predictive model.<n>Our results are exceedingly general, showing that essentially any existing calibration algorithm can be used in causal settings.
  arXiv  Detail & Related papers  (2024-06-04T03:35:25Z)
• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  We propose algorithms that utilize the variance of the reward distribution as well as the $B_K$, and show that they can achieve tighter regret upper bounds. We introduce two novel algorithms: Restarted Weighted$textOFUL+$ and Restarted $textSAVE+$. Notably, when the total variance $V_K$ is much smaller than $K$, our algorithms outperform previous state-of-the-art results on non-stationary linear bandits under different settings.
  arXiv  Detail & Related papers  (2024-03-15T23:36:55Z)
• Testing Calibration in Nearly-Linear Time [14.099477870728595]
  We focus on the algorithmic study of calibration through the lens of property testing. We make the simple observation that the empirical smooth calibration linear program can be reformulated as an instance of minimum-cost flow on a highly-structured graph. We present experiments showing the testing problem we define faithfully captures standard notions of calibration, and that our algorithms scale efficiently to accommodate large sample sizes.
  arXiv  Detail & Related papers  (2024-02-20T17:53:24Z)
• An Elementary Predictor Obtaining $2\sqrt{T}+1$ Distance to Calibration [4.628072661683411]
  We show that an online predictor can obtain $O(sqrtT)$ distance to calibration in the adversarial setting. We give an extremely simple, efficient, deterministic algorithm that obtains distance to calibration error at most $2sqrtT+1$.
  arXiv  Detail & Related papers  (2024-02-18T00:53:05Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  We present the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an $tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regret. We also propose a variance-adaptive algorithm for linear mixture Markov decision processes (MDPs) in reinforcement learning.
  arXiv  Detail & Related papers  (2023-02-21T00:17:24Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  We prove that our algorithms require a number of evaluations gradient independent of training set size and number of parameters. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9--36 times more efficient than full-batch methods.
  arXiv  Detail & Related papers  (2020-10-12T17:41:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.