Research map / Learning theory and algorithms / Prediction and decision losses
Conformal Predictions under Markovian Data
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 split conformal prediction on Markovian data, showing the coverage gap scales as sqrt(t_mix ln n / n), and proposes K-split CP (thinning the calibration set by K) that reduces the gap to t_mix/(n ln n).
Problem
Split conformal prediction loses its finite-sample coverage guarantee when calibration data are correlated as a Markov chain rather than i.i.d. or exchangeable; the coverage gap and prediction set size under such dependence are unclear.
Approach
Derives coverage-gap and set-size bounds for split CP under Markovian data using mixing-time concentration, and introduces K-split CP, which keeps one in every K calibration samples and chooses K from the chain's mixing rate (estimated online), so that the thinned chain's dependence is negligible.
Key results
- Split CP coverage gap under Markovian data is O(sqrt(t_mix ln(n)/n)); with optimal K-split CP the gap improves to O(t_mix/(n ln n)), dividing the gap by roughly sqrt(n) ln(n)^{3/2}.
- For K* = O(t_mix ln n), the high-probability bound on quantile error goes from O(sqrt(t_mix/n)) for split CP to O(sqrt(t_mix ln(n)/n)) for K*-split CP.
- Experiments on lazy random walk (w=20, rho=0.97), Gaussian AR(1), EUR/SEK and French electricity data show all methods approach 1-alpha coverage as n grows, with K-split CP over-covering at small n.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Thin the calibration dataset using K-split CP instead of using all calibration samples | Split CP · Markovian data, geometrically ergodic chain | coverage gap: \sqrt{t_\mathrm{mix}{\ln(n)\over n}} -> \frac{t_\mathrm{mix}}{n\ln (n)} | Helped |
| Use the optimal K★ thinning parameter | K-split CP · Markovian data, geometrically ergodic chain | quantile estimation error: {\cal O}_n(\sqrt{\frac{t_\mathrm{mix}\ln (\frac{2}{\delta})}{n}}) -> {\cal O}_n(\sqrt{\frac{t_\mathrm{mix}\ln(n)\ln (\fr | Hurt |
| Correct the quantile level used by K-split CP to account for the reduced calibration set (ablation) | K-split CP · Synthetic lazy random walk, low n | coverage deviation from 1-α | Helped |
| Use K-split CP rather than full Split CP | Split CP · Synthetic lazy random walk (w=20) | coverage | Mixed |
| Use K-split CP rather than full Split CP | Split CP · Gaussian AR(1), θ=0.9, ω=1 | coverage | Helped |
Surprising findings
- Thinning the calibration set with K-split CP makes coverage over-conservative when the reduced calibration set is small, motivating a corrected quantile level.
Limitations
- Results rely on geometric ergodicity / beta-mixing assumptions and known or estimable mixing rate.
- K-split CP can over-cover when the thinned calibration set is small, requiring a corrected quantile level.
- Estimation of rho for continuous state spaces is not covered by the estimator; only finite state spaces have guarantees for K-hat.
Experimental setup
Datasets: synthetic lazy random walk synthetic Gaussian AR(1) EUR/SEK exchange rate per-minute data (2022, histdata.com) French electricity price data (2016-2019)
Benchmarks: synthetic lazy random walk synthetic Gaussian AR(1) EUR/SEK exchange rate French electricity price forecasting
Metrics: empirical coverage relative difference of prediction set length to optimal leng
Baselines: split conformal prediction K-split conformal prediction (corrected) oracle optimal prediction set
Builds on: split conformal prediction beta-mixing concentration adaptive conformal inference
Closest papers by meaning
- Improving the Statistical Efficiency of Cross-Conformal Prediction (ICML 2025 · similarity 0.89)
- Non-exchangeable Conformal Prediction with Optimal Transport: Tackling Distribution Shift with Unlabeled Data (NeurIPS 2025 · similarity 0.88)
- Probabilistic Conformal Prediction with Approximate Conditional Validity (ICLR 2025 · similarity 0.87)
- Online conformal prediction with decaying step sizes (ICML 2024 · similarity 0.87)
- Backward Conformal Prediction (NeurIPS 2025 · similarity 0.87)
- False Coverage Proportion Control for Conformal Prediction (ICML 2025 · similarity 0.87)
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.