Conformal Risk Minimization with Variance Reduction
Sima Noorani Orlando Romero Nicolo Dal Fabbro University of Pennsylvania University of Pennsylvania University of Pennsylvania [email protected] [email protected] [email protected] Hamed Hassani George Pappas University of Pennsylvania University of Pennsylvania [email protected] · 2024
Read Conformal Risk Minimization with Variance Reduction by Sima Noorani Orlando Romero Nicolo Dal Fabbro University of Pennsylvania University of Pennsylvania University of Pennsylvania [email protected] [email protected] [email protected] Hamed Hassani George Pappas University of Pennsylvania University of Pennsylvania [email protected] (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01696.txt.
Description
Abstract Conformal prediction (CP) is a distribution-free framework for achieving probabilistic guarantees on black-box models. CP is generally applied to a model post-training. Recent research efforts, on the other hand, have focused on optimizing CP efficiency during training . We formalize this concept as the problem of conformal risk minimization (CRM).
Catalog record
| CREATOR | Sima Noorani Orlando Romero Nicolo Dal Fabbro University of Pennsylvania University of Pennsylvania University of Pennsylvania [email protected] [email protected] [email protected] Hamed Hassani George Pappas University of Pennsylvania University of Pennsylvania [email protected] |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 99 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-01696
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Conformal Risk Minimization with Variance Reduction Sima Noorani Orlando Romero Nicolo Dal Fabbro University of Pennsylvania University of Pennsylvania University of Pennsylvania [email protected] [email protected] [email protected] Hamed Hassani George Pappas University of Pennsylvania University of Pennsylvania [email protected] [email protected] Abstract Conformal prediction (CP) is a distribution-free framework for achieving probabilistic guarantees on black-box models. CP is generally applied to a model post-training. Recent research efforts, on the other hand, have focused on optimizing CP efficiency during training . We formalize this concept as the problem of conformal risk minimization (CRM). In this direction, conformal training ( ConfTr ) by Stutz et al. [34] is a CRM technique that seeks to minimize the expected prediction set size of a model by simulating CP in-between training updates. In this paper, we provide a novel analysis for the ConfTr gradient estimation method, revealing a strong source of sample inefficiency that introduces training instability and limits its practical use. To address this challenge, we propose variance-reduced conformal training (VR-ConfTr) , a CRM method that carefully incorporates a novel variance reduction technique in the gradient estimation of the ConfTr objective function. Through extensive experiments 1 1 1 We release our code at https://github.com/nooranisima/conformal-risk-minimization-w-variance-reduction-code on various benchmark datasets, we demonstrate that VR-ConfTr consistently achieves faster convergence and smaller prediction sets compared to baselines. 1 Introduction Consider a classification task with input (features) X\in\mathcal{X} and corresponding labels Y\in\mathcal{Y}=\{1,\ldots,K\} . Let \pi_{\theta}:\mathcal{X}\rightarrow\mathbb{R}^{K} be a parameterized predictor which, for every input x and label y , approximates the posterior probability \pi(y|x)=\mathbb{P}\left({Y=y\,|\,X=x}\right) . Using \pi_{\theta} , we can estimate the label corresponding to an input x as \delta_{\theta}(x)=\arg\max_{y\in\mathcal{Y}}\pi_{\theta}(y|x) . Usually, the performance of the predictor \pi_{\theta} is assessed via the accuracy , which is the portion of testing samples whose predicted label matches the true label. While the accuracy is a key performance metric, in safety-critical applications it is crucial not only to predict accurately but also to quantify the uncertainty associated with a prediction. To address this, conformal prediction (CP) [ 36 , 33 , 4 ] , uses the (pre-trained) model \pi_{\theta} to construct, for an input X , a prediction set C(X)\subseteq\mathcal{Y} that contains the true label with high probability, satisfying the desired coverage guarantee. For example, the set C(X) satisfies marginal coverage with miscoverage rate \alpha\in(0,1) if \mathbb{P}\left({Y\in C(X)}\right)\geq 1-\alpha . One way to evaluate the usefulness of prediction sets is the length efficiency [ 17 ] , which represents a measure of their size. For instance, while it is possible to trivially guarantee any desired coverage by including the entire label space in C(x) , a prediction set constructed in this way is non-informative and useless. Thus, an efficient C(x) is as small as possible while maintaining the desired coverage guarantee. Addressing the efficiency challenge by refining the CP set construction technique applied post-training, though effective, is inherently constrained by the performance of the pre-trained model \pi_{\theta} . On the other hand, by integrating CP into the training process, recent research efforts [ 15 , 9 , 16 , 34 , 6 ] guide the training of a model \pi_{\theta} via CP-induced metrics, optimizing the model parameters \theta to improve its inherent CP efficiency . Here, we formalize this emerging optimization setting as the problem of conformal risk minimization (CRM). Among the existing CRM methods, the conformal training ( ConfTr ) approach first introduced by Stutz et al. [34] is an intuitive technique - based on simulating CP during training to construct differentiable approximations of prediction sets - which is recently gaining momentum [ 9 , 40 , 37 ] . However, despite its potential, ConfTr suffers from training instability and struggles to converge [ 34 , 27 , 12 ] . In this paper, we focus on the following questions: What is the source of training instability in ConfTr ? How can we address this limitation? We provide answers to both questions. First, we theoretically show that ConfTr is intrinsically sample-inefficient . Second, to address this limitation, we introduce variance-reduced conformal training VR-ConfTr , a provably sample efficient CRM algorithm that radically improves gradient estimation and enhances training stability. 1.1 Contributions Our contributions can be summarized as follows: Analysis of the ConfTr algorithm. Focusing on CRM for length efficiency optimization, we provide a novel analysis for the ConfTr [ 34 ] method, which reveals a strong source of sample inefficiency in its gradient estimation technique. In particular, we show that the ConfTr gradient variance is not reduced with the batch size , and we show that this is related to the need for improved estimators of the quantile gradients. A “plug-in” algorithm. We introduce the pipeline of variance-reduced conformal training ( VR-ConfTr ), our proposed algorithm to overcome this challenge, which (i) decouples the estimation of the population quantile and of its gradient, and (ii) leverages a “plug-in” step to incorporate improved estimates of quantiles’ gradients in the training. Novel variance reduction technique. Building on a fundamental result, which characterizes the gradient of the population quantile as a conditional expectation, we propose a novel estimator for quantiles’ gradients, which can be seamlessly integrated into VR-ConfTr . We show that, under reasonable assumptions, this integration makes VR-ConfTr provably sample-efficient : unlike ConfTr , our approach effectively reduces the variance of the resulting estimated gradients with the training batch size. Empirical validations. We extensively validate our method on various benchmark and real-world datasets, including MNIST, FMNIST, KMNIST, OrganAMNIST, and CIFAR10. Our results demonstrate that VR-ConfTr consistently and significantly improves the efficiency and stability of CRM for length efficiency optimization. Broad applicability. Our approach and variance reduction technique can be integrated into any CRM method that requires quantile gradient estimation, at essentially no additional computational cost, extending its utility to a large class of CP frameworks and learning models. 1.2 Related Works Conformal prediction (CP) is a distribution-free, principled framework that provides formal probabilistic guarantees for black-box models [ 36 , 33 , 4 ] , with exemplar applications in computer vision [ 2 ] , large language models [ 29 , 24 ] and path planning [ 26 ] . To improve CP efficiency, many research efforts have focused on approaches that apply CP post-training to black-box models. In particular, recent algorithmic developments address improving length efficiency through better conformity score design [ 31 , 43 , 1 , 14 , 28 ] , or on designing better calibration procedures [ 22 , 5 , 42 , 11 ] . These efforts do not fall under the CRM framework because they focus on learning low-dimensional hyper-parameters for pre-trained models as opposed to fully guiding the training of a \theta -parameterized model \pi_{\theta}(y|x) . Conformal risk minimization. There is a growing body of work [ 16 , 9 , 34 , 6 , 40 ] integrating ideas from conformal prediction in order to directly train a model for improved CP. Among these, ConfTr proposed by Stutz et al. [34] has gained significant attention. This approach addresses length efficiency optimization by defining a loss function obtained by simulating conformal prediction during training. We will extensively describe and provide a novel analysis for this approach in the next section. Earlier work by Bellotti [6] considered an approach analogous to ConfTr in