Research map / Bandits and online learning / Online convex optimization and games
The Relationship Between No-Regret Learning and Online Conformal Prediction
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.
Relates no-regret learning to online conformal prediction: shows external regret does not imply coverage in adversarial or group-conditional settings, ties threshold-calibrated/multivalid coverage to swap regret, and proves O(sqrt T) group-conditional coverage for FTRL/OGD-based GCACI.
Problem
Online conformal prediction guarantees marginal coverage in adversarial settings via OGD-like algorithms, but their coverage analyses do not follow from OGD's regret guarantee; the relationship between no-regret learning and (group-conditional / multivalid) online coverage is unclear.
Approach
Shows external regret on pinball loss does not imply coverage (adversarially or with context even in i.i.d.), but swap regret is tightly equivalent to threshold-calibrated and multivalid coverage; proves FTRL iterates give group-conditional coverage bounded by the gradient of the regularizer, yielding a multi-group ACI (GCACI) with O(sqrt T) group coverage error.
Key results
- GCACI reaches group-conditional coverage faster than MVP across time-series, UCI Airfoil and Folktables experiments (q=0.9).
- Empirically ||theta_t||_inf stays bounded by a small constant, giving much faster than the O(sqrt T) worst-case bound.
- Theorem shows external regret does not imply coverage (counterexample with odd/even thresholds) while swap regret implies threshold-calibrated coverage with error O(sqrt(gamma/T)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GCACI instead of MVP | Online group-conditional coverage · AMD time-series data | convergence speed | Helped |
| Use GCACI instead of MVP | Online group-conditional coverage · UCI Airfoil | convergence speed | Helped |
| Use GCACI instead of MVP | Online group-conditional coverage · Folktables | convergence speed | Helped |
| Use MVP instead of GCACI for smaller groups | Online group-conditional coverage · Experiments on AMD time-series, UCI Airfoil, and Folktables | convergence to target coverage | Hurt |
| Increase the GCACI learning rate | GCACI · Experiments on AMD time-series, UCI Airfoil, and Folktables | convergence speed | Helped |
| Set the GCACI learning rate to η = 1 | GCACI · Experiments on AMD time-series, UCI Airfoil, and Folktables | convergence speed | Helped |
| Use constant learning rate η instead of η = 1/√T | GCACI · Worst-case regret guarantee | regret guarantee | Hurt |
| Run GCACI with binary groups | GCACI · Experiments on AMD time-series, UCI Airfoil, and Folktables | parameter norm | Helped |
Surprising findings
- Low external regret on pinball loss can coexist with zero coverage, even in i.i.d. settings when the algorithm uses context.
- Empirically the parameter norm stays bounded far below the O(sqrt T) worst-case bound, suggesting the bound is loose for binary groups.
Limitations
- Worst-case O(sqrt T) bound is tight only for real-valued group functions; binary-group bound is only conjectured.
- Coverage-from-regret results require smoothness assumptions on the score distribution.
- Group functions must be prediction-independent for the FTRL results.
Experimental setup
Datasets: AMD stock WSJ daily prices 2000-2020 UCI Airfoil self-noise dataset Folktables 2018 US Census (California, Pennsylvania)
Benchmarks: AMD volatility time series UCI Airfoil synthetic covariate shift Folktables income prediction
Metrics: group conditional miscoverage convergence rate time to reach epsilon=0.01 of target coverage L-infinity norm of parameters
Baselines: MVP (multi valid predictor) ACI
Builds on: ACI (adaptive conformal inference) online gradient descent multivalid predictor (MVP) follow the regularized leader
Closest papers by meaning
- Online Conformal Prediction via Online Optimization (ICML 2025 · similarity 0.90)
- Discounted Adaptive Online Learning: Towards Better Regularization (ICML 2024 · similarity 0.89)
- A Simple and Optimal Approach for Universal Online Learning with Gradient Variations (NeurIPS 2024 · similarity 0.87)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.87)
- Group-wise oracle-efficient algorithms for online multi-group learning (NeurIPS 2024 · similarity 0.87)
- No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! (NeurIPS 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.