CS Paper Radar

Conformalized Quantile Regression and Minimax Limits of Fixed-Score Calibration under Known Covariate Shift

Rustam Isaev, Anton Conrad, Denis Belomestny, Eric Moulines, Sergey Samsonov

cs.LG math.STstat.ML ·submitted 2026-09-21 17:24 UTC · v1
theory

Abstract

In this paper, we study nonasymptotic $L^p$ error bounds for interval length and conditional coverage in split conformalized quantile regression (CQR). Our bounds rely on local regularity conditions and accuracy guarantees for the estimated quantiles. We further instantiate our bounds for quantile regression with sparse ReLU neural networks. We also consider covariate shift, where the calibration and test covariates have different distributions, and derive nonasymptotic bounds for this setting. We obtain matching minimax upper and lower bounds in expectation for two constructed fixed-score calibration benchmarks under known covariate shift. The bounds match for every $p\in[1,\infty]$ in the scalar problem and for finite $p$ in the $K$-threshold problem; for the latter, a high-probability minimax lower bound holds for every $p\in[1,\infty]$.

Comment
65 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Sharp training-conditional coverage for conformal prediction under covariate shift

cs.LG stat.MLmath.STstat.ME ·2026-09-27 ·Mehrdad Pournaderi
theory similarity 0.66
Abstract

Weighted split conformal prediction reweights calibration scores by the likelihood ratio between the test and training covariate distributions and guarantees marginal coverage under covariate shift. We study its coverage conditional on the calibration data. An elementary argument, based on a single concentration inequality at a fixed population quantile, gives explicit training-conditional bounds without unspecified constants, and shows that the relevant scale is not the supremum of the likelihood ratio but a variance proxy built from the chi-squared divergence of the shift and from the average of the ratio over the part of the test population, of probability equal to the miscoverage level, where it is largest. A two-point lower bound shows that the root-m rate and the chi-squared contribution are intrinsic to the shift. Run at an explicitly inflated level, the weighted quantile becomes a deterministic PAC prediction set. We compare it with randomized rejection sampling and with importance-weighted learn-then-test and, through a certified choice of a clipping level for the likelihood ratio, map the regime in which each gives the narrower valid set. The analysis extends to estimated likelihood ratios and to tail functionals estimated from an unlabeled source sample, which yields a fully finite-sample certificate.

0.45

Occupancy-based Quantile Risk Control

cs.LG stat.ML ·2026-09-02 ·Zihao Shi, Huajun Xi, Bingyi Jing, Hongxin Wei
theory similarity 0.63
Abstract

Conformal risk control is an emerging framework for the safe deployment of machine learning models with finite-sample guarantees. To accommodate a broader class of risk notions, quantile risk control extends this framework to quantile-based risk measures. However, existing methods either suffer from excessive conservatism or lack rigorous finite-sample guarantees. To address these limitations, we introduce Occupancy-based Quantile Risk Control (OQRC), a novel method that provides tight risk control bounds with finite-sample validity. Our key idea is to formulate risk control as a finite-occupancy problem by partitioning the loss space with the ordered calibration losses. Specifically, we estimate the distribution of test losses across the resulting bins and upper-bound the risk by the maximum loss attained within each bin. We then select the parameter $λ$ such that this upper bound does not exceed a predefined threshold $α$ with high probability $1-δ$. Theoretically, we establish a finite-sample guarantee showing that OQRC yields tight risk control bounds that converge to the optimal bounds at a provable rate of $\mathcal{O}_ p(n^{-1/2})$. Extensive experiments demonstrate the effectiveness of our method, reducing the risk gap by up to 78.64\% on common benchmarks.

0.16

Split Conformal Interval Length under Huber Contamination

cs.LG ·2026-10-11 ·Xiao Zhang, Bowen Zhang, Lie He
theory similarity 0.62
Abstract

Existing analyses of interval length in split conformal prediction largely focus on clean data. However, how contamination at the training and calibration stages alters interval length relative to the corresponding clean population oracle remains understudied. In this paper, we consider Huber contamination and derive a finite-sample upper bound that holds uniformly over contaminating distributions, with leading terms scaling as $L(δ_1+n_1^{-1/2}) +(n_2^{-1/2}+δ_2)/((1-δ_2)r_0)$, in addition to a clean-sample estimation term. We further establish a minimax lower bound matching the upper-bound rate up to constant factors on a regular asymmetric location submodel. For calibration contamination, we obtain an exact worst-case characterization of the population interval-length deviation. We also extend the upper-bound results to conformalized quantile regression and adaptive residual scores. Experiments on synthetic and real-world datasets provide empirical support for our theoretical findings on training and calibration contamination.

0.15

Finite-Sample Distribution Theory and Efficient Large-Scale Inference for Online Quantile Regression

cs.LG stat.MLmath.STstat.ME ·2026-10-05 ·Ziyang Wei, Jiaqi Li, Lan Wang, Wei Biao Wu
theory similarity 0.62
Abstract

This paper studies online quantile regression for large-scale and streaming data using Stochastic SubGradient Descent (SSGD) with constant learning rates. Classical offline inference for quantile regression is computationally and memory intensive. Existing works of online inference for quantile regression provide only asymptotic guarantees and typically require sub-exponential tail conditions for distribution theory. To bridge these gaps, we introduce new techniques to prove a quenched central limit theorem (CLT) and finite-sample Gaussian approximation for SSGD under a finite-moment assumption. We further show that Ruppert-Polyak averaging with a constant learning rate has a non-vanishing bias and fails to satisfy CLT centering at the population target. Hence we propose suffix averaging to address this issue and establish its finite-sample Gaussian approximation. Based on these results, we provide an efficient online inference method for quantile regression that avoids covariance estimation. Numerical experiments show that our method achieves desirable empirical coverage rates and competitive performance compared to other inference methods. We also apply our approach to U.S. wage data to demonstrate its practical effectiveness.

0.18

Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent

cs.LG math.NA ·2026-09-11 ·Jamie Haddock, Anna Ma, Elizaveta Rebrova
theory similarity 0.61
Abstract

We study loss-based filtering for finite-sum optimization with a subset of corrupted component functions whose gradients may be highly unreliable. Motivated by minimum-loss-based SGD (min-$k$-loss) and quantile-based methods for corrupted linear systems, we propose and analyze a general loss-filtering framework -- Quantile-\(k\)-Loss SGD (Q\(k\)L-SGD) -- that samples \(k\) component losses at each iteration and updates using an index chosen uniformly from the lower empirical \(q\)-quantile. We prove linear convergence of this family of methods under standard convexity assumptions, requiring the sample size to scale with the number of corruptions and a subset strong-convexity threshold. For the cases when large enough sampling is impossible or undesirable, we give a complementary small-sample probabilistic analysis that covers any sample size $k$ and the convergence behavior depends on the probability of selecting an outlier and on the curvature of the selected good step. Experiments on polynomial regression, regularized logistic regression, and regularized hinge loss show that intermediate quantiles often outperform both standard SGD and min-\(k\)-loss SGD. In particular, min-\(k\) often stalls by repeatedly selecting nearly solved components, while intermediate quantiles retain robustness and produce more informative updates.

0.30

Minimax Quantile Bounds via Information Measures

cs.IT math.ST ·2026-08-21 ·Amedeo Roberto Esposito
similarity 0.60
Abstract

We develop a unified information-theoretic framework for lower bounding minimax quantiles. The starting point is a loss-adapted Neyman--Pearson metaconverse that bounds the minimax success probability at every loss threshold and confidence level. The bound separates the small-ball behaviour of the prior under the loss from the statistical distinguishability of the observation model, and is optimised over an auxiliary output distribution. Different relaxations of this Neyman--Pearson bound yield converses based on \(f\)-informativity, Sibson mutual information \(I_α\), Maximal Leakage, and Amemiya norms. Classical Fano and Le Cam lower bounds are recovered as special cases. The framework also clarifies why different information measures are suited to different recovery criteria. Maximal Leakage is exact for a class of symmetric exact-recovery problems. We use this identity to derive finite-sample bounds on the full minimax exact-recovery risk in the balanced Gaussian weighted stochastic block model, as well as two-sided finite-sample minimax-quantile bounds for low-rank matrix estimation under isotropic bounded-energy noise. For approximate Hamming recovery, we exhibit a heterogeneous binary model in which an optimised finite Sibson order yields a strong converse while the Maximal Leakage specialisation is trivial. Finally, for one-coordinate Poisson localisation, a Bennett-type Young function used through its Amemiya norm recovers the exact success-probability scale, whereas classical Fano and fixed-power relaxations are strictly weaker. These results show that sharp converses for minimax quantiles require adapting the information measure to the recovery resolution, whether exact or approximate, and to the tail behaviour of the likelihood ratio.

0.45

Finite-Sample Optimal Conformal Prediction Sets under Covariate Shift

cs.LG stat.MLmath.COmath.PR+1 ·2026-10-27 ·Zhongyang Li
theory similarity 0.60
Abstract

We study conformal prediction under covariate shift with a known covariate density ratio, seeking prediction sets with minimum expected length under the target distribution. For every calibration sample size, we prove that the rule combining the inverse conditional-density score with randomized weighted conformal calibration minimizes this expected length among all rules valid over the full weighted-exchangeability class. We approximate the oracle using quantile and kernel histograms, including forest-weighted estimators, and select estimators and tuning parameters by resampling to estimate calibrated target length. On a bounded response domain, we bound excess length linearly in $L^1$ density error at fixed calibration size, without requiring a uniform positive lower bound on the true density. We also bound selection-pool and resampling errors. Under explicit growth conditions, the selected procedure approaches the same oracle while the calibration size remains fixed. Experiments on 36 known-density configurations and four public regression datasets compare coverage, prediction-set length, and runtime with existing methods. In targeted low-coverage and strong-shift comparisons, inverse-density selection yields shorter mean sets in most cases and lower mean runtime than the evaluated weighted baselines, with some differences in achieved coverage.

0.13

Predicted Class Correction: Conformal Thresholds for Classes with No Calibration Data

cs.LG cs.CV ·2026-10-18 ·One Octadion, Novanto Yudistira, Yuta Nakashima
similarity 0.60
Abstract · 23 pages including supplementary material, 4 figures

Class-conditional conformal prediction calibrates a separate score threshold for every class and therefore requires labelled calibration examples of every class. In long-tailed deployments these are exactly what is missing: rare classes are left with few or no held-out examples, and existing methods are either undefined for them or fall back to the shared marginal threshold. We ask whether the per-class correction can instead be predicted from descriptors of the class that require no labels at all. We propose Predicted Class Correction (PCC), which regresses the offset between the per-class and the marginal conformal quantile on geometric descriptors of the classifier head, shrinks the prediction by a scalar selected on the labelled classes, and refits a single marginal offset. The descriptors depend only on the model's weights, so a class with zero calibration examples still receives its own threshold, and since only one scalar is calibrated, split conformal's marginal guarantee is retained. On ImageNet, PCC improves worst-class coverage on such classes by 0.058 [0.006, 0.110] at matched average set size, 42% of an oracle that sees the test labels. Of eight baselines on the same splits, six change the statistic by exactly zero and the best reaches 0.016 with an interval containing zero, so PCC is the only one distinguishable from no improvement; the gain persists with only 100 labelled classes out of 1000. A second finding concerns evaluation: worst-class coverage becomes unmeasurable before it becomes unachievable. Below roughly 35 test examples per class no improvement can be shown even for an oracle, so a null result there reflects the evaluation set, not the method. Restricting evaluation above this depth recovers a significant improvement on Pl@ntNet-300K, where the effect had appeared absent.

0.17