Research map / Learning theory and algorithms / Prediction and decision losses
A Black-Box Reduction from Regret to Multi-Level Coverage
Tuo Liu, Edgar Dobriban, Francesco Orabona
Read the paperCheck your idea against 137,217 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.
Gives a black-box reduction converting online regret guarantees into multi-level online conformal prediction coverage guarantees, producing nested prediction sets across coverage levels.
Problem
Online conformal prediction must produce prediction sets at multiple coverage levels simultaneously, with average coverage converging to each target level on arbitrary (possibly adversarial) data, while keeping sets properly nested across levels.
Approach
Reduces multi-level online conformal coverage to regret minimization via a black-box reduction, so any online learner with regret guarantees can yield multi-level coverage; prior work used online gradient descent with lazy isotonic projections, which gives nesting but with weaker guarantees.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add lazy isotonic projection (ablation) | p-norm OMD · AAPL | Weighted Interval Score: -10.9% | Improved |
| add lazy isotonic projection (ablation) | p-norm OMD · Sinusoidal stream | Weighted Interval Score: -12.5% | Improved |
| add lazy isotonic projection (ablation) | p-norm OMD and UP-OCP · AAPL, sinusoidal | mean prediction-set width: 33% / 39% narrower (p-norm), 7-8% (UP-OCP) | Improved |
| add lazy isotonic projection (ablation) | all base learners · AAPL, sinusoidal | calibration | No clear effect |
| use UP-OCP instead of p-norm OMD and MultiQT | UP-OCP-Iso · AAPL | mean width | Improved |
| use UP-OCP instead of tuned baselines | UP-OCP-Iso · AAPL, sinusoidal | WIS | Improved |
| use oracle-tuned p-norm OMD step size | p-norm OMD · AAPL | coverage vs width | Mixed |
| increase number of levels d from 5 to 1000 | multi-level OCP · Sinusoidal stream | worst-level error | No clear effect |
Experimental setup
Baselines: online gradient descent with lazy isotonic projections
Builds on: online conformal prediction online gradient descent with lazy isotonic projections
Closest papers by meaning
- Online Conformal Prediction via Online Optimization (ICML 2025 · similarity 0.91)
- The Relationship Between No-Regret Learning and Online Conformal Prediction (ICML 2025 · similarity 0.88)
- Adaptive Conformal Inference by Betting (ICML 2024 · similarity 0.87)
- High-Dimensional Prediction for Sequential Decision Making (ICML 2025 · similarity 0.86)
- Backward Conformal Prediction (NeurIPS 2025 · similarity 0.86)
- Online Localized Conformal Prediction (NeurIPS 2026 · similarity 0.86)
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.
