Training-Conditional Coverage Bounds for Uniformly Stable Learning Algorithms
The training-conditional coverage performance of the conformal prediction is known to be empirically sound. Recently, there have been efforts to support this observation with theoretical guarantees. The training-conditional coverage bounds for jackknife+ and full-conformal prediction regions have been established via the notion of $(m,n)$-stability by Liang and Barber~[2023]. Although this notion is weaker than uniform stability, it is not clear how to evaluate it for practical models. In this paper, we study the training-conditional coverage bounds of full-conformal, jackknife+, and CV+ prediction regions from a uniform stability perspective which is known to hold for empirical risk minimization over reproducing kernel Hilbert spaces with convex regularization. We derive coverage bounds for finite-dimensional models by a concentration argument for the (estimated) predictor function, and compare the bounds with existing ones under ridge regression.
Code (0)
등록된 구현이 없습니다.
Tasks
Conformal PredictionPredictionSimilar Papers 제목 키워드 기반
Linear programming approach to partially identified econometric models
Sharp bounds on partially identified parameters are often given by the values of linear programs (LPs). This paper introduces a novel estimator of the LP value. Unlike existing procedures, our estimator is root-n-consist…
Distribution-free changepoint localization after sequential change detection
This paper introduces a distribution-free framework for constructing post-detection confidence sets for changepoints after stopping a sequential change detection procedure. It is well known that conformal test martingale…
Change DetectionFast-Rate Loss Bounds via Conditional Information Measures with Applications to Neural Networks
We present a framework to derive bounds on the test loss of randomized learning algorithms for the case of bounded loss functions. Drawing from Steinke & Zakynthinou (2020), this framework leads to bounds that depend on …
Nonvacuous Loss Bounds with Fast Rates for Neural Networks via Conditional Information Measures
We present a framework to derive bounds on the test loss of randomized learning algorithms for the case of bounded loss functions. This framework leads to bounds that depend on the conditional information density between…
Generalization Bounds for Uniformly Stable Algorithms
Uniform stability of a learning algorithm is a classical notion of algorithmic stability introduced to derive high-probability bounds on the generalization error (Bousquet and Elisseeff, 2002). Specifically, for a loss f…
Generalization Bounds