Research map / Learning theory and algorithms / Sample complexity

Occupancy-based Quantile Risk Control

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Statistical-query lower bounds · 0 citations (OpenAlex)

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.

Proposes OQRC, a training-free finite-sample quantile risk control method that bounds quantile-based risk via a finite-occupancy (discrete uniform) argument over calibration-loss bins, with Monte-Carlo approximation.

Problem

Quantile risk control (controlling VaR, CVaR and similar quantile-based risk measures of test losses) is either overly conservative or lacks finite-sample guarantees when calibration sets are small.

Approach

Partition the loss space by ordered calibration losses; the occupancy counts of test losses across the n+1 bins follow a discrete uniform law independent of loss values, so an upper bound on quantile risk can be taken as the maximum loss within each bin, yielding a finite-sample UCB and a calibrated lambda.

Key results

• On MS COCO under [0.85,0.95]-VaR-Interval, OQRC reduces RiskGap by 78.64% and AvgSize by 38.80% versus Two-sided BJ (alpha=0.4, 1-delta=0.9).
• CDRC-L fails to achieve the 1-delta coverage requirement on all three tasks, while OQRC maintains valid coverage (0.904-0.959 across settings).
• Across four classifier architectures on MS COCO, OQRC lowers average RiskGap from 0.347 to 0.075 and average AvgSize from 15.226 to 6.849.

Surprising findings

• OQRC's empirical coverage modestly exceeds the nominal 1-delta level, which the authors attribute to the FNP loss being discontinuous and violating the density-bound assumption of the tightness theory.
• The joint distribution of occupancy counts is discrete uniform regardless of the loss values, so the bound depends only on n and m.

Limitations

• Theory assumes i.i.d. calibration and test losses; distribution shift is not handled.
• Asymptotic tightness theorem requires a density bounded below on [L,U] and fixed m; FNP violates these conditions.
• Exact CDF computation is combinatorially expensive, requiring Monte-Carlo approximation for large m and n.

Experimental setup

Datasets: Kvasir Hyper-Kvasir CVC-ColonDB CVC-ClinicDB ETIS-Larib MS COCO Go Emotions

Benchmarks: Polyp (Kvasir-based pooled set) MS COCO Go Emotions

Metrics: coverage RiskGap AvgSize

Baselines: OrderStats One-sided BJ Two-sided BJ CDRC-L

Builds on: conformal risk control quantile risk control (Snell et al.) conformal distortion risk control via L-statistics Berk-Jones test Bates et al. risk control

Closest papers by meaning

• Conformal Risk Control (ICLR 2024 · similarity 0.87)
• Performative Risk Control: Calibrating Models for Reliable Deployment under Performativity (NeurIPS 2025 · similarity 0.85)
• Conformal Risk Training: End-to-End Optimization of Conformal Risk Control (NeurIPS 2025 · similarity 0.84)
• Conformal Validity Guarantees Exist for Any Data Distribution (and How to Find Them) (ICML 2024 · similarity 0.84)
• Rectifying Conformity Scores for Better Conditional Coverage (ICML 2025 · similarity 0.84)
• Conformal Prediction as Bayesian Quadrature (ICML 2025 · similarity 0.83)