PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved Online Conformal Prediction via Strongly Adaptive Online Learning

Aadyot Bhatnagar, Huan Wang, Caiming Xiong, Yu Bai

arXiv:2302.07869v1cs.LGcs.AImath.STstat.MEstat.MLstat.TH

TL;DR

Online conformal prediction needs coverage and useful prediction sets even as data distributions shift, while whole-horizon regret may not ensure strong performance on every interval. The paper develops SAOCP and SF-OGD, proving strongly adaptive regret and approximately valid coverage, and reports better localized coverage and smaller sets than existing methods in real-world experiments.

  • Problem

    Standard regret minimization evaluates performance over the full horizon, but changing distributions can make guarantees over every time interval important.

    Source: §1 · p. 2, §3 · p. 5

  • Method

    SAOCP aggregates experts that operate on their own active intervals, with SF-OGD used as the expert algorithm and also studied independently.

    Source: §1 · p. 2, §3 · p. 6

  • Results

    SAOCP achieves near-optimal strongly adaptive regret for all interval lengths simultaneously, and SAOCP and SF-OGD achieve approximately valid coverage.

    Source: §1 · p. 2

  • Takeaways & Limitations

    On time-series forecasting and image classification under distribution shift, the methods achieve better localized-window coverage and smaller prediction sets than existing methods.

    Source: §6 · p. 11

    The analysis assumes true radii are almost surely bounded in [0, D].

    Source: §2 · p. 4

Abstract

from arXiv · show

We study the problem of uncertainty quantification via prediction sets, in an online setting where the data distribution may vary arbitrarily over time. Recent work develops online conformal prediction techniques that leverage regret minimization algorithms from the online learning literature to learn prediction sets with approximately valid coverage and small regret. However, standard regret minimization could be insufficient for handling changing environments, where performance guarantees may be desired not only over the full time horizon but also in all (sub-)intervals of time. We develop new online conformal prediction methods that minimize the strongly adaptive regret, which measures the worst-case regret over all intervals of a fixed length. We prove that our methods achieve near-optimal strongly adaptive regret for all interval lengths simultaneously, and approximately valid coverage. Experiments show that our methods consistently obtain better coverage and smaller prediction sets than existing methods on real-world tasks, such as time series forecasting and image classification under distribution shift.

1 Introduction

Prediction sets quantify uncertainty by aiming for valid coverage, but online conformal methods need interval-level guarantees when distributions shift. The paper introduces interval-local experts and reports near-optimal strongly adaptive regret, approximately valid coverage, and improved empirical performance.

1 Introduction

  • Conformal prediction produces prediction sets with valid coverage guarantees, but those guarantees rely on exchangeability, which can fail under distribution shift.The cited alternatives include reweighting and distributionally robust optimization.Source: §1 · p. 1
  • Prior online conformal methods adapt a prediction-set radius using regret minimization, seeking coverage and sublinear regret; the latter helps keep set sizes reasonable.The cited methods include Gibbs and Cand`es (2021, 2022), Zaffran et al. (2022), and Feldman et al. (2022).Source: §1 · pp. 1–2
  • When distributions shift, whole-horizon regret may miss poor performance within intervals; FACI does not achieve near-optimal regret simultaneously for all interval lengths.The paper motivates guarantees within intervals between shifts, in addition to guarantees over the full horizon.Source: §1 · p. 2
  • SAOCP assigns experts their own active intervals, and the paper also studies SF-OGD as an independent online conformal prediction algorithm.Both methods build on strongly adaptive regret minimization.Source: §1 · p. 2
  • SAOCP achieves near-optimal strongly adaptive regret for all interval lengths simultaneously, while SAOCP and SF-OGD achieve approximately valid coverage.The contribution is proved in Section 4.Source: §1 · p. 2
  • On time-series forecasting and image classification under distribution shift, SAOCP and SF-OGD achieve better localized-window coverage and smaller prediction sets than existing methods.These are the two real-world tasks reported in the experiments.Source: §1 · p. 2

1.1 Related work

  • Related distribution-shift approaches include reweighting, distributionally robust optimization, and doubly robust calibration; the paper's regret serves as a surrogate for prediction-set efficiency.Other related work studies conformal prediction for time series and strongly adaptive online learning.Source: §1.1 · pp. 2–3
  • SAOCP differs from FACI because its experts operate only on their own active intervals, yielding a better strongly adaptive regret guarantee.FACI's experts run over the full horizon.Source: §1.1 · p. 3

2 Preliminaries

Online conformal prediction selects a prediction-set radius before seeing each label, then uses the observed outcome to update it. The paper reviews coverage and regret objectives, the quantile-loss formulation, and the bounded-radius assumption.

2 Preliminaries

  • At each round, the prediction set is chosen using the current input and past observations before the true label is observed.A prediction set maps an input to a subset of possible labels; examples include regression intervals and classification label sets.Source: §2 · p. 3
  • Online conformal prediction targets coverage 1 − α and evaluates radii with the (1 − α)-quantile loss; ACI updates the radius upward after miscoverage and downward after coverage.ACI learns the quantile level from past scores for its confidence sets.Source: §2 · pp. 3–4
  • The method predicts a radius for a nested family of sets, where increasing the radius yields a larger set; the true radius is the smallest one that covers the label.For regression, the radius can be the half-width of an interval around a base prediction.Source: §2 · p. 3
  • The analysis assumes that every true radius is almost surely bounded in [0, D].The paper also reports that FACI performs better when trained to predict the true radius directly under its more general parameterization.Source: §2 · p. 4
  • ACI has approximately valid empirical coverage and a regret bound on quantile losses, while regret helps rule out trivial strategies that alternate empty and full prediction sets.Coverage and regret guarantees do not imply one another without further distributional assumptions.Source: §2 · p. 4

3 Strongly Adaptive Online Conformal Prediction

Whole-horizon regret may conceal poor performance during distribution changes, motivating guarantees over intervals of different lengths. SAOCP combines experts active on finite intervals, using SF-OGD experts to obtain strongly adaptive performance.

3 Strongly Adaptive Online Conformal Prediction

  • Strongly adaptive regret measures maximum regret over all intervals of a fixed length, extending ordinary regret to localized windows.The paper seeks such guarantees simultaneously across interval lengths to address changing environments.Source: §3 · p. 5
  • SAOCP starts a new expert at each time with a finite active interval, then aggregates predictions from the experts currently active.The lifetime design permits at most g⌊log2 t⌋ active experts at time t and total runtime O(T log T).Source: §3 · pp. 5–6
  • SAOCP uses SF-OGD experts, which adapt their effective learning rate according to cumulative past gradient norms and provide anytime regret guarantees.The paper selects SF-OGD as an expert satisfying the required regret properties on its active interval.Source: §3 · p. 6
  • SF-OGD can also run independently over the full horizon as an online conformal prediction algorithm, and the paper reports strong empirical performance in many scenarios.Plugging SF-OGD into SAOCP gives the full meta-algorithm.Source: §3 · p. 6

4 Theory

SAOCP achieves near-optimal strongly adaptive regret simultaneously across interval lengths, while the paper establishes coverage guarantees for SF-OGD and SAOCP under stated conditions.

4.1 Strongly Adaptive Regret

  • SAOCP achieves a near-optimal strongly adaptive regret guarantee simultaneously for all interval lengths.The guarantee is obtained by combining SF-OGD's regret bound with the strongly adaptive regret guarantee for SAOCP.Source: §4.1 · p. 6
  • Unlike FACI, SAOCP's strongly adaptive regret guarantee holds simultaneously for all interval lengths; FACI's rate can match it for one length but not multiple lengths at once.Their meta-algorithms also differ in expert design: SAOCP experts vary by active interval, while FACI experts vary by learning rate and remain active over [T].Source: §4.1 · p. 7
  • SAOCP also achieves near-optimal dynamic regret on any interval, with a rate depending on the path length of the true radii.The result follows from a reduction from dynamic regret to strongly adaptive regret.Source: §4.1 · p. 7

4.2 Coverage

  • For any T, SF-OGD achieves CovErr(T) ≤ O(α^-2 T^-1/4 log T), without distributional assumptions.The paper also states the rate as O(t^-1/4 log t) for any t ∈ [T].Source: §4.2 · p. 7
  • If β ∈ (1/2, 1), Sβ(T) ≤ eO(T^γ), and γ < 1 − β, the randomized SAOCP variant has CovErr(T) ≤ eO(T^-min{1/2−β, β−1+γ}) = oT(1).The bound depends on Sβ(T), which measures smoothness of expert weights and cumulative gradient norms for individual experts.Source: §4.2 · p. 7
  • The SAOCP coverage theorem extends to other expert weights and active intervals; with one expert active over [T], it recovers SF-OGD's coverage bound.This single-expert case recovers the eO(α^-2 T^-1/4) bound.Source: §4.2 · p. 7
  • Under mild distributional regularity, SAOCP's coverage error on an interval of length k is eO(k^-1/(2q) + (VarI/k)^(1/q)), yielding approximately valid coverage when VarI = o(k).Here q ≥ 2 quantifies distribution regularity, and VarI measures variation between the true quantiles over interval I.Source: §4.2 · pp. 7–8

5 Experiments

Across time-series forecasting and image classification under distribution shift, SAOCP shows strong local coverage and competitive prediction-set sizes. The experiments compare coverage and set-size behavior across methods under the stated datasets and shift settings.

5 Experiments

  • The experiments test online uncertainty quantification on four time-series datasets and on TinyImageNet and ImageNet with corrupted versions, using sudden and gradual corruption shifts.For image classification, 500 examples are sampled at each corruption level before moving to the next; local coverage and set size are evaluated over windows of 100.Source: §5.1 · p. 9, §5.2 · pp. 10–11

5.1 Time Series Forecasting

  • Across all three M4 datasets, SAOCP maintains global coverage in (0.85, 0.95) and achieves the best or second-best interval width, local coverage error, and strongly adaptive regret.On M4 Hourly this holds for all base predictors; on M4 Daily, SAOCP achieves the best results on those metrics for all base predictors.Source: §5.1 · p. 9, Table 1 · p. 9, Table 2 · p. 9
  • When the base predictor’s MAE is at least 0.14, SCP, NExCP, and FACI each fail to attain global coverage in (0.85, 0.95) in multiple cases.The authors note this suggests an advantage to predicting the radius directly, as SF-OGD and SAOCP do.Source: §5.1 · p. 10

5.2 Image Classification Under Distribution Shift

  • Under sudden and gradual image-distribution shifts, SAOCP and SF-OGD stay closest to 0.9 local coverage, with the difference most notable at sudden shifts.On TinyImageNet, SAOCP has slightly better local coverage than SF-OGD with similar set sizes; on ImageNet, their local coverage is similar, while SAOCP tends to use smaller sets.Source: Figure 1 · p. 10, §5.2 · p. 11

6 Conclusion

The paper develops online conformal prediction algorithms for arbitrary distribution shifts. Its conclusion highlights approximately valid coverage, improved strongly adaptive regret, and favorable local-window experimental performance, while identifying stronger coverage guarantees and radius optimality as future questions.

6 Conclusion

  • The algorithms achieve approximately valid coverage and better strongly adaptive regret than existing work, while experiments show closer-to-target local-window coverage and smaller prediction sets.The authors identify stronger coverage guarantees and characterizing the optimality of learned radii under distribution shift as open questions.Source: §6 · p. 11

A.1 Properties of SF-OGD

This appendix establishes properties of SF-OGD, illustrates why coverage alone can admit trivial behavior, and outlines the interval decomposition used to prove the strongly adaptive regret bound.

A.1 Properties of SF-OGD

  • If true radii stay in [0, D], SF-OGD’s iterates remain bounded; its regret bound follows by applying a scale-free mirror-descent result to the quantile loss.The bounded-iterate result allows initialization in [−η, D + η], while the anytime regret proposition assumes initialization in [0, D] and learning rate η = D/…; the supplied passage does not show the full bound.Source: §A.1 · p. 16

A.2 Example of “Trivial” Algorithm with Coverage Guarantee

  • An algorithm that alternates between maximum and minimum radii can achieve approximately (1 − α) empirical coverage with O(1/T) error, yet incur linear regret on a constant-radius sequence.For true radii D/2, the comparator’s quantile loss is zero, while the trivial algorithm’s loss is at least α(1 − α)DT.Source: §A.2 · pp. 17–18

B.1 Proof of Proposition 4.1

  • The strongly adaptive regret proof partitions each queried interval into prefixes of experts’ active intervals, then takes a supremum over comparators and intervals.The proof combines the interval decomposition with the SF-OGD regret bound and obtains the desired bound on SAReg(T, k).Source: §B.1 · p. 18

B.2 Dynamic Regret for SAOCP

This appendix compares SAOCP’s interval-wise regret with FACI, develops coverage-bound arguments, and shows how the coverage result includes SF-OGD as a special case.

B.2 Dynamic Regret for SAOCP

  • SAOCP’s average dynamic regret bound holds simultaneously across interval lengths and locations, while FACI has worse dependence on interval length when true-radius variation is o(k).In that low-variation regime, FACI has better dependence on average path length; the comparison is framed against the interval path length.Source: §B.2 · pp. 18–19

B.3 Proof of Theorem 4.2

  • The proof of Theorem 4.2 uses bounded iterates and bounds on the miscoverage gradients, with the concluding bound stated for η = Θ(D).The supplied excerpts do not include the full theorem bound.Source: §B.3 · p. 19

B.4 Coverage of SAOCP

  • The coverage proof groups time steps into blocks and bounds a coverage-error quantity using the expert weights and active intervals.The theorem considers a randomized SAOCP variant that samples an expert and outputs that expert’s radius.Source: §B.4 · p. 21

B.4.1 Discussions & SF-OGD as a Special Case

  • The coverage proof applies to other expert-aggregation schemes with arbitrary active intervals; setting one expert active throughout recovers SF-OGD, whose bound is subsumed by the theorem.For this special case, the passage states Sβ(T) ≤ eO(α^-2) for β in (1/2, 1).Source: §B.4.1 · pp. 22–23

C Distribution-Aware Coverage Guarantees for SAOCP

SAOCP’s interval coverage guarantee depends on assumptions about the conditional score densities and how the target quantiles vary over time. Its coverage error is smaller when quantile variation is lower, and coverage is approximately valid when that variation grows sublinearly with interval length.

Coverage guarantees

  • Under density bounds, SAOCP bounds quantile-estimation and interval-miscoverage errors on every interval, with rates depending on interval length and quantile variation.The lower-density assumption uses q ≥ 2; the upper-density assumption bounds the conditional density of the true radii.Source: C Distribution-Aware Coverage… · pp. 23–24
  • Coverage error is lower when interval quantile variation is lower, and coverage is approximately valid when Var_I = o(|I|).Here, the variation concerns the 1 − α conditional quantiles across the interval.Source: C Distribution-Aware Coverage… · p. 24

Assumptions and interpretation

  • The parameter q controls the local lower-density assumption’s difficulty; larger q relaxes that assumption but makes closeness to the true quantile less aligned with expected quantile-loss regret.Smaller α also makes the bound’s D/∆_I term larger, reflecting greater difficulty learning more extreme quantiles.Source: C Distribution-Aware Coverage… · p. 24

Proof approach

  • The proof converts strongly adaptive interval regret into expected quantile-estimation error, then uses Lipschitz conditional CDFs to obtain a coverage bound.The argument also bounds variation in true conditional quantiles over the interval.Source: C Distribution-Aware Coverage… · pp. 23–24

D Additional Time Series Experiments

The additional time-series results report similar performance among methods on NN5 Daily and results on M4 Weekly similar to those on M4 Daily.

M4 Weekly

NN5 Daily

E Additional Experimental Details

The appendix specifies implementation choices for the compared methods, including their tuning parameters and how those parameters vary across tasks.

Baseline implementations

  • The appendix lists split conformal and weighted-quantile NExCP as comparison methods, with NExCP using geometrically decaying weights.FACI-S applies FACI to the scores S_t rather than α_t, with losses based on the scores.Source: E Additional Experimental Details · p. 27

FACI

  • FACI uses target interval length k = 100; trying k = 20 for time-series experiments produced worse results.Its listed setup also uses eight experts with learning rates from 0.001 to 0.128.Source: E Additional Experimental Details · p. 27

SF-OGD

  • SF-OGD uses maximum radius D, set from the largest observed calibration residual per forecast horizon for time series and from image-classification regularization parameters for classification.For time series, D/3 is set to the largest horizon-specific calibration residual.Source: E Additional Experimental Details · p. 27

SAOCP

F Time Series Experiments with Ensemble Models

The ensemble experiments combine EnbPI with online conformal methods and report strong EnbSAOCP results on M4 datasets. On NN5, the methods have similar strongly adaptive regret, while EnbSAOCP is narrower than EnbSF-OGD.

Experimental setup

  • The experiments pair EnbPI’s ensemble residuals with radius-selection methods including NExCP, FACI, SF-OGD, and SAOCP.The ensemble uses five models.Source: F Time Series Experiments with… · p. 28
  • The authors describe EnbPI’s contribution as orthogonal to theirs and report that the methods can be combined.They frame the comparison as putting other methods on even footing with EnbPI, which removes the train/calibration split and uses an ensemble.Source: F Time Series Experiments with… · p. 28

Results

  • EnbSAOCP generally has the best or second-best interval width, worst-case local coverage error, and strongly adaptive regret across M4 datasets.On M4 Hourly, it has the best local coverage error and strongly adaptive regret for all models except ARIMA, where its regret is somewhat high; on M4 Daily, it is best or second-best across these metrics and is the only method with valid coverage for LGBM.Source: F Time Series Experiments with… · p. 28, Table 5 · p. 28, Table 6 · p. 28
  • On NN5, methods have similar strongly adaptive regret; EnbSF-OGD and EnbSAOCP have the best and second-best local coverage error, with slightly wider intervals.EnbSAOCP’s intervals are narrower than EnbSF-OGD’s across the board.Source: F Time Series Experiments with… · p. 28

G Image Classification on TinyImageNet/TinyImageNet-C

On TinyImageNet-C, SAOCP and SF-OGD maintain local coverage closest to 0.9, with SAOCP having better coverage than SF-OGD. On ImageNet/ImageNet-C shifts, they remain closest to target coverage, and SAOCP returns smaller sets than SF-OGD.

G Image Classification on TinyImageNet/TinyImageNet-C

  • The TinyImageNet classifier achieved 52.8% final test accuracy after SGD training with early stopping.The experiment uses TinyImageNet and its corrupted version TinyImageNet-C.Source: G Image Classification on… · p. 28
  • The uncertainty-quantification experiment uses conformal score (15) with width regularization parameters λ = 0.01 and kreg = 20.The passage identifies these settings for the conformal score used in the experiment.Source: G Image Classification on… · pp. 28–29
  • SAOCP and SF-OGD keep local coverage closest to 0.9 on TinyImageNet-C, with SAOCP achieving better coverage than SF-OGD.The differences are most apparent under sudden shifts; all methods attain similar prediction set sizes.Source: G Image Classification on… · p. 29
  • Across sudden and gradual ImageNet/ImageNet-C shifts, SAOCP and SF-OGD stay closest to 0.9 coverage, while SAOCP returns smaller prediction sets.The shifts occur every 500 steps, and the plotted values are moving averages with window size 100.Source: Figure 2 · p. 30

Related papers

Loading 2302.07869v1…