One Sample is Enough to Make Conformal Prediction Robust
Soroush H. Zargarbashi, Mohammad Sadegh Akhondzadeh, Aleksandar Bojchevski
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 the inputs with worst-case noise. For that, applying randomized smoothing (inference over a noise-augmented distribution around the input) is a well-established approach as it is resilient to larger radii, and applicable to any black-box model. However current smoothing-based RCPs require many model forward passes per each input which is computationally expensive. We show that without any informations (e.g. distribution of scores, inputs, etc), conformal prediction combined with *single* randomized augmented inference already shows robustness. Hence, we can lower bound its worst case coverage guarantee through any binary certificate. Our single sample approach (RCP1) returns (robust) prediction sets with a set sizes comparable to state of the art given large number of inferences (e.g. $\sim 100$) per input. Our key insight is to certify the conformal 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.