Research map / Learning theory and algorithms / Prediction and decision losses
Online conformal prediction with decaying step sizes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes online conformal prediction's quantile-tracking update with decaying step sizes, giving both adversarial long-run coverage and i.i.d. convergence of thresholds and instantaneous coverage.
Problem
Online conformal prediction methods with a fixed step size guarantee only long-run coverage and produce highly unstable prediction sets (empty or infinite) over time, with no convergence guarantee for i.i.d. data.
Approach
Use the online quantile-tracking update q_{t+1}=q_t+eta_t(1{miscover}-alpha) with decaying step sizes eta_t ~ t^{-1/2-eps}; this gives retrospective long-run coverage for arbitrary sequences and almost-sure convergence of the threshold and instantaneous coverage to nominal for i.i.d. data.
Key results
- Theory: with eta_t ~ t^{-1/2-eps}, long-run coverage error is O(T^{-(1/2-eps)}) in the adversarial setting, and q_t -> q* and instantaneous coverage -> 1-alpha almost surely for i.i.d. data.
- With a fixed step size, instantaneous coverage has lim inf 0 and lim sup 1 almost surely (Proposition on i.i.d. data), so prediction sets are empty or infinite infinitely often.
- On 3000 M4 series, decaying step size gives coverage 0.900 and variance 1.32 versus fixed step size coverage 0.902 and variance 1.58; infinite-set fraction 0.0069 vs 0.0112.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use a decaying rather than fixed step size | online conformal prediction · M4 time series | variance: 1.580243 -> 1.320579 | Helped |
| use a decaying rather than fixed step size | online conformal prediction · M4 time series | MSE: 2.922989 -> 2.366297 | Helped |
| use a decaying rather than fixed step size | online conformal prediction · M4 time series | infinite sets: 0.011179 -> 0.006883 | Helped |
| use a decaying rather than fixed step size | online conformal prediction · M4 time series | coverage: 0.901636 -> 0.900495 | No clear effect |
| add change-point-triggered learning-rate resets (ablation) | decaying online conformal prediction · M4 time series | variance: 1.320579 -> 1.144337 | Helped |
| add change-point-triggered learning-rate resets (ablation) | decaying online conformal prediction · M4 time series | MSE: 2.366297 -> 1.967552 | Helped |
| add change-point-triggered learning-rate resets (ablation) | decaying online conformal prediction · M4 time series | infinite sets: 0.006883 -> 0.005011 | Helped |
| add change-point-triggered learning-rate resets (ablation) | decaying online conformal prediction · M4 time series | coverage: 0.900495 -> 0.885174 | Hurt |
| use decaying rather than fixed step size | online conformal prediction · Elec2 | instantaneous coverage stability | Helped |
| use decaying rather than fixed step size | online conformal prediction · ImageNet | instantaneous coverage stability | Helped |
| use decaying rather than fixed step size | online conformal prediction · Elec2 and ImageNet | rolling coverage variability | Hurt |
Surprising findings
- Fixed step size yields tighter rolling coverage, but this comes from overcorrection producing extremely wide intervals, so it is undesirable.
- Fixed step size size-infinite-set frequency is about 1.6x that of decaying step size on M4 (0.0112 vs 0.0069).
Limitations
- Convergence guarantees are proved only for i.i.d. data (or convergent score functions), not for general time series.
- Decaying step sizes adapt slowly to distribution shifts, motivating the decay+adapt variant which is only heuristically evaluated.
- Quality of prediction sets depends on the underlying score/model choice.
Experimental setup
Datasets: Elec2 ImageNet validation (50000 images) M4 (3000 subsampled series)
Benchmarks: Elec2 ImageNet M4
Metrics: long-run coverage instantaneous coverage rolling coverage quantile variance MSE of quantile fraction of infinite prediction sets
Baselines: fixed step size online conformal (ACI) DTACI oracle quantile
Builds on: ACI (adaptive conformal inference) online conformal prediction online gradient descent
Closest papers by meaning
- Online Conformal Prediction via Online Optimization (ICML 2025 · similarity 0.90)
- Probabilistic Conformal Prediction with Approximate Conditional Validity (ICLR 2025 · similarity 0.90)
- Backward Conformal Prediction (NeurIPS 2025 · similarity 0.89)
- Valid Selection among Conformal Sets (NeurIPS 2025 · similarity 0.88)
- Co-optimization for Adaptive Conformal Prediction (NeurIPS 2026 · similarity 0.88)
- Rectifying Conformity Scores for Better Conditional Coverage (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.