Adaptive conformal inference

Context. Split conformal prediction gives $\mathbb P(Y\in\hat C)\ge1-\alpha$ only when calibration and test points are exchangeable. In online use (markets, election night, transaction streams) the data drift, and a quantile calibrated on the past undercovers after a shift. Earlier fixes need to know something about the shift (a likelihood ratio, or the radius of a divergence ball); this paper assumes nothing. It keeps the conformal machinery and treats the level fed to the calibration quantile as one parameter, re-estimated online from the observed misses. Gibbs and Candès run coverage as a feedback loop, raising the nominal coverage after a miss and lowering it after a hit. The parameter integrates the coverage error, and since it is confined to a bounded interval (below 0 the set is everything, above 1 it is empty), the integrated error stays bounded and the average miss rate converges to $\alpha$ at rate $1/(\gamma T)$ on every data sequence. This is integral control with a bounded state, and the step size $\gamma$ trades slow response to a shift against step-to-step noise, as with constant-step SGD tracking a moving optimum.

Setting. Pairs $(X_t,Y_t)$ arrive one at a time, and $Y_t$ is revealed after each prediction. At time $t$ there is a score $S_t$ (say $|y-\hat\mu(x)|$, or the CQR score) and a calibration quantile function $\hat Q_t$, both refit on past data, and the set $\hat C_t(\beta)=\{y:S_t(X_t,y)\le\hat Q_t(1-\beta)\}$. $\hat Q_t$ is non-decreasing with $\hat Q_t(p)=-\infty$ for $p<0$ and $+\infty$ for $p>1$, so $\hat C_t(\beta)$ is the whole line for $\beta<0$ and empty for $\beta>1$. Let $M_t(\beta)=\mathbb P(S_t(X_t,Y_t)>\hat Q_t(1-\beta))$ be the miscoverage at level $\beta$ and $\alpha_t^*=\sup\{\beta:M_t(\beta)\le\alpha\}$ the level that would give coverage $1-\alpha$ at time $t$. Adaptive conformal inference (ACI) starts at $\alpha_1\in[0,1]$ (in practice $\alpha_1=\alpha$) and updates $$\mathrm{err}_t=\mathbf 1\{Y_t\notin\hat C_t(\alpha_t)\},\qquad \alpha_{t+1}=\alpha_t+\gamma(\alpha-\mathrm{err}_t).$$ A miss lowers $\alpha_t$ by $\gamma(1-\alpha)$, widening the next set, and a hit raises it by $\gamma\alpha$.

Proposition (long-run coverage on any sequence). With no assumption on the data, for every $T$ and on every path, $$\Big|\frac1T\sum_{t=1}^T\mathrm{err}_t-\alpha\Big|\le\frac{\max\{\alpha_1,1-\alpha_1\}+\gamma}{\gamma T}.$$ For $\alpha_1=\alpha=0.1$ and the paper's $\gamma=0.005$, the right side is $181/T$. In a noiseless model with a fixed target $\alpha^*$ and piecewise-linear $M$, the average error is exactly $(1-(1-c\gamma)^T)\,|\alpha_1-\alpha^*|/(\gamma T)$ for small $\gamma$, $c$ the slope of $M$ on the side where $\alpha_1$ starts, so the $1/(\gamma T)$ rate is the right one when $\alpha^*$ is unknown.

Hidden Markov model and per-step coverage. The finer results put a model on the drift. A Markov chain $A_t$ drives the environment, and given the chain the pairs are independent with $(X_t,Y_t)\sim P_{A_t}$; the score and quantile function are held fixed. Write $M(p|a)=\mathbb P(S(X_t,Y_t)>\hat Q(1-p)\mid A_t=a)$, let $\alpha_a^*$ solve $M(\alpha_a^*|a)=\alpha$, and let $D=\mathbb E|\alpha^*_{A_{t+1}}-\alpha^*_{A_t}|$ be the drift of the target. The pair $(\alpha_t,A_t)$ is assumed to start in its unique stationary law. Theorem. If every $M(\cdot|a)$ is $L$-Lipschitz and each $\alpha_a^*\in(0,1)$ exists, then $$\mathbb E\big[(M(\alpha_t|A_t)-\alpha)^2\big]\le\frac{L(1+\gamma)}{\gamma}\,D+\frac{L\gamma}2,$$ which at $\gamma=\sqrt{2D}$ is at most $L(\sqrt2+1)\sqrt D$; with perfect quantiles $L=1$.

Theorem (concentration of the miss rate). In the same model, let the chain have absolute spectral gap $1-\eta>0$, and set $B=\sup_a|\mathbb E[\mathrm{err}_t|A_t=a]-\alpha|$ and $\sigma_B^2=\mathbb E[(\mathbb E[\mathrm{err}_t|A_t]-\alpha)^2]$. Then $$\mathbb P\Big(\Big|\frac1T\sum_{t\le T}\mathrm{err}_t-\alpha\Big|\ge\varepsilon\Big)\le2e^{-T\varepsilon^2/8}+2\exp\Big(-\frac{T(1-\eta)\varepsilon^2}{8(1+\eta)\sigma_B^2+20B\varepsilon}\Big),$$ and under a second-order expansion of each $M(\cdot|a)$ at $\alpha_a^*$ with slope bounded away from $0$ and below $1/\gamma$, $\sigma_B^2\le B^2$ and $B\le C(\gamma+\gamma^{-1}\epsilon_1)$, with $\epsilon_1$ the worst conditional expected one-step drift of $\alpha^*$. Step 4 explains why the first term is established only for a single state.

Consequences and limits. ACI is a one-line wrapper that drives any conformal method's long-run miss rate to $\alpha$ on any sequence, drifting or adversarial, and under slow drift it also tracks per-step coverage, with $\gamma$ set by how fast the right level moves. The guarantee is about frequency only: it says nothing about set size, and a method that outputs the whole line 90% of the time and the empty set otherwise also satisfies it; infinite sets occur whenever $\alpha_t<0$. Most of the work is done by the score and the refit model, which should make $\alpha_t^*$ nearly stationary, as the normalized volatility score does. The finer theory needs a fixed quantile function, a stationary start and a hidden Markov model, $\gamma$ is chosen by hand, and each label must arrive before the next prediction. The last point matters in fraud, where chargebacks arrive weeks late and the loop would run on stale errors; the paper lists delayed feedback as open. Later work chooses $\gamma$ online by aggregating copies of ACI (Gibbs and Candès, 2022) and recasts the update as a controller on the score quantile (Angelopoulos et al., 2023).