Training-Conditional Coverage Bounds for Uniformly Stable Learning Algorithms
This work addresses the need for reliable uncertainty quantification in machine learning predictions, offering incremental theoretical improvements for researchers and practitioners using conformal prediction.
The paper tackles the problem of providing theoretical guarantees for training-conditional coverage in conformal prediction methods by deriving bounds based on uniform stability, which is more practical to evaluate than previous notions. It results in coverage bounds for finite-dimensional models, specifically comparing them under ridge regression.
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.