Instance-Adaptive Online Multicalibration

Zhiming Huang; Jamie Morgenstern; Aaron Roth; Claire Jie Zhang

cs.LGMay 10, 2026

Instance-Adaptive Online Multicalibration

Authors: Zhiming Huang, Jamie Morgenstern, Aaron Roth, Claire Jie Zhang

Organizations: Paul G. Allen School of Computer Science and Engineering, University of Washington · Department of Computer and Information Sciences, University of Pennsylvania

Abstract

We study online multicalibration beyond the worst-case. We give a single, efficient algorithm which dynamically interpolates between benign and worst-case sequences by adaptively refining a dyadic grid of prediction values. Its error is controlled by the number of leaves in the refinement tree. Our analysis recovers the known $\widetilde O(T^{2/3})$ worst-case-optimal rate for online multicalibration, while simultaneously automatically adapting to easier instances: in the marginal stochastic setting it obtains a rate of $\widetilde O(\sqrt T)$ , and for piecewise-stationary means with $J$ segments its rate is $\widetilde O(\sqrt{JT})$ . More generally, the rate depends on a threshold-complexity measure of the predictable mean process relative to the group family. We show that this dependence is tight up to logarithmic factors.

Explore similar work

Adaptive Calibration in Non-Stationary Environments
May 12, 2026Junyan Liu, Haipeng Luo, Lillian J. RatliffNon-Stationarity Adversaries
The Sample Complexity of Multicalibration
Apr 23, 2026Natalie Collina, Jiuyao Lu, Georgy Noarov +1Multicalibration and Calibration Optimal Sample Complexity
Efficient Sequential Calibration with $O(T^{2/3-ε})$ Error Bound
Jul 14, 2026Zihan ZhangMulticalibration and Calibration High-Fidelity Surrogates

May 12, 2026 · cs.LGJ/K move · Enter open · S save

Adaptive Calibration in Non-Stationary Environments

Junyan Liu, Haipeng Luo, Lillian J. Ratliff

University of Washington · University of Southern California

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,

K

being the unknown number of i.i.d. segments of the environment, and

C\in[0,T]

being another unknown non-stationary measure defined as the minimal

\ell_1

deviation of the mean outcomes, our algorithms attain

\widetilde{O}(\min\{\sqrt{T}+(TC)^{\frac{1}{3}}, \sqrt{KT}\})

for

\ell_1

calibration error and

\widetilde{O}(\min\{(1+C)^{\frac{1}{3}}, K\})

for both

\ell_2

and pseudo KL calibration error. These bounds match the optimal rates in the stationary case (

C=0

and

K=1

) and recover known guarantees in the fully adversarial regime (

C, K=Ω(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.

Non-Stationarity Adversaries Environment

Open paper Ask about it PDF

Abstract

Explore similar work

Adaptive Calibration in Non-Stationary Environments

The Sample Complexity of Multicalibration

Efficient Sequential Calibration with O(T2/3−ε)O(T^{2/3-ε})O(T2/3−ε) Error Bound

Efficient Sequential Calibration with $O(T^{2/3-ε})$ Error Bound