One Sample is Enough to Make Conformal Prediction Robust
This work addresses the computational bottleneck in robust conformal prediction for users needing reliable uncertainty estimates under worst-case noise, offering a more efficient solution.
The paper tackles the computational inefficiency of robust conformal prediction by showing that a single forward pass on a randomly perturbed input can provide robustness, resulting in smaller average prediction set sizes compared to state-of-the-art methods that require around 100 passes per input.
Given any model, conformal prediction (CP) returns prediction sets guaranteed to include the true label with high adjustable probability. Robust CP (RCP) extends this to inputs with worst-case noise. A well-established approach is to use randomized smoothing for RCP since it is applicable to any black-box model and provides smaller sets compared to deterministic methods. However, current smoothing-based RCP requires many model forward passes per each input which is computationally expensive. We show that conformal prediction attains some robustness even with a forward pass on a single randomly perturbed input. Using any binary certificate we propose a single sample robust CP (RCP1). Our approach returns robust sets with smaller average set size compared to SOTA methods which use many (e.g. around 100) passes per input. Our key insight is to certify the conformal prediction procedure itself rather than individual scores. Our approach is agnostic to the setup (classification and regression). We further extend our approach to smoothing-based robust conformal risk control.