AI Paper Atlas

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

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Conformal prediction sets · 0 citations (OpenAlex)

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 changedWhereMeasuredEffect
add lazy isotonic projection (ablation)p-norm OMD · AAPLWeighted Interval Score: -10.9%Improved
add lazy isotonic projection (ablation)p-norm OMD · Sinusoidal streamWeighted Interval Score: -12.5%Improved
add lazy isotonic projection (ablation)p-norm OMD and UP-OCP · AAPL, sinusoidalmean prediction-set width: 33% / 39% narrower (p-norm), 7-8% (UP-OCP)Improved
add lazy isotonic projection (ablation)all base learners · AAPL, sinusoidalcalibrationNo clear effect
use UP-OCP instead of p-norm OMD and MultiQTUP-OCP-Iso · AAPLmean widthImproved
use UP-OCP instead of tuned baselinesUP-OCP-Iso · AAPL, sinusoidalWISImproved
use oracle-tuned p-norm OMD step sizep-norm OMD · AAPLcoverage vs widthMixed
increase number of levels d from 5 to 1000multi-level OCP · Sinusoidal streamworst-level errorNo 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

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy