Introduction
High accuracy alone is not sufficient for reliability in machine learning. Although modern neural networks achieve strong empirical performance, their predictions can be highly sensitive to small, often imperceptible, input perturbations [18 ] . This sensitivity can be exploited by adversaries to easily degrade the model’s performance. There are many empirical, and heuristic defenses proposed in the literature which have been circumvented by stronger or adaptive attacks [5 ] . A principled way to address this issue is to use robustness certificates, which provide formal guarantees that the model prediction remains invariant within a predefined perturbation set. Certificates can be viewed as binary decision rules: when they certify an input at a sufficiently large radius, they signal that the prediction can be trusted with respect to the specified threat model, whether the input is clean or even if adversarially perturbed, the perturbation is not effective.
Existing robustness certificates typically obtain such guarantees through architecture-specific verification methods, such as convex relaxations, or mixed-integer programming [38 , 24 , 34 ] . While powerful, these methods require white-box access to the model, and often need to be adapted when new architectures or layers are introduced. Alternatively, randomized smoothing (RS) [11 ] wraps around any black-box classifier, and convolves it with a noise augmentation. The resulting smoothed classifier changes slowly with local perturbations. Hence, one can derive closed-form model-agnostic bounds on its change. This black-box nature is a major practical advantage, allowing it to easily apply to large modern networks, and even to API-accessible systems [10 ] . However, randomized smoothing-based certificates require a large number of model forward passes (e.g. 2 × 10 3 2 \times10^{3} 2 × 1 0 3 ) to estimate the smoothed class probabilities with high confidence, which can be prohibitively expensive especially with limited resources, or when the model itself is expensive to evaluate.
This cost is especially wasteful because not every input received by a system is adversarial; indeed, most inputs are expected to be clean. Moreover, in many settings, it is cheap to obtain a relatively small set of unlabeled samples representative of the deployment distribution. These observations motivate a distributional relaxation of robustness certification: rather than requiring a local certificate for every individual input, it may suffice to guarantee that certification failure is controllable below an adjustable low probability over test inputs.
In light of the arguments above, we define Proxy Certificate (ProxC), a framework for delegating expensive certification to cheap proxy functions under calibrated statistical control. Through a variant of conformal risk control (CRC) that we define in § 2.2 , we control how often the proxy deviates from the expensive function. Our proxy reduces the cost of the certification step to a single model forward. We define three variants for ProxC, tailored for various compute budgets: ProxC-A, that uses a single forward pass per calibration point, ProxC which computes an expensive backbone certificate on the small calibration set, and ProxC-H which can increase the certified ratio, in return for more Monte-Carlo (MC) sampling. All three variants use a single sample to certify each test point. We bound the risk anchored at the latent clean point, which lets a sound certificate computed only on clean calibration points calibrate a cheap proxy that remains valid under perturbation (see § F).
The resulting proxy can be used either as a standalone certificate or as a hybrid fallback mechanism that only calls the expensive certification on inputs rejected by the proxy. These are two different operating regimes: the standalone proxy gives the largest saving, while the fallback recovers the certified ratio of the backbone at a smaller speedup. As we show in Table 1 , by relaxing the soundness to bounded false approvals, we can reduce the cost of the certification step to a single forward, the same as verification-based approaches (importantly, the choice of label passed into the certificate is excluded from the cost evaluation. This can still follow the inference rule of the backbone). ProxC shows a higher certified accuracy compared to verification (note that our guarantee is marginal, and we use a slightly different architecture), and it is cheaper than randomized smoothing. In other words, in the trade-off between computational efficiency and applicability, we now propose a new dimension which is soundness. We propose smoothing-based guarantees with a realistic computational cost that is suitable for larger models like ViT, or language modeling in realistic time-sensitive scenarios.
Table 1. Results on ImageNet/ResNet, r = 0.14 r=0.14 r = 0.14 , σ = 0.5 \sigma=0.5 σ = 0.5 , α = 0.05 \alpha=0.05 α = 0.05 , Gaussian smoothing (2000 MC samples: 50 for the majority-vote label and 1950 for the certificate). The verification entry does not use smoothing (result directly reported from the reference); it gives a pointwise guarantee on a different architecture, so it is not directly comparable to the marginal guarantee of ProxC. Speedup is on forward calls and relative to randomized smoothing. Certification-only cost excludes the forwards for the label; end-to-end cost includes them.
Background
Problem setup. Let f : X → R ∣ Y ∣ f:\mathcal{X} \to\mathbb{R}^{|\mathcal{Y}|} f : X → R ∣ Y ∣ be a pre-trained classifier (can be a single model, a pipeline of models, or any general inference policy, e.g. majority vote over random augmentations) that returns a score per class. For an input x i ∈ X x_i \in\mathcal{X} x i ∈ X , its top prediction is y i = arg max y i f ( x i ) y i y_i = \arg\max_{y_i} f(x_i)_{y_i} y i = arg max y i f ( x i ) y i . For brevity, whenever f f f is compared across two inputs, e.g. f ( x ~ ) ≠ f ( x ) f(\tilde{x}) \ne f(x) f ( x ~ ) = f ( x ) , we compare the predicted labels, i.e. arg max y f ( x ~ ) y ≠ arg max y f ( x ) y \arg\max_y f(\tilde{x})_y \ne\arg\max_y f(x)_y arg max y f ( x ~ ) y = arg max y f ( x ) y . For the test point, x n + 1 x_{n+1} x n + 1 , an adversary introduces a perturbation x ~ n + 1 = x n + 1 + δ \tilde{x}_{n+1}=x_{n+1}+\delta x ~ n + 1 = x n + 1 + δ aiming to change the model’s prediction f ( x ~ n + 1 ) ≠ f ( x n + 1 ) f(\tilde{x}_{n+1}) \ne f(x_{n+1}) f ( x ~ n + 1 ) = f ( x n + 1 ) . The adversary is limited to keep the perturbation imperceptible – x ~ n + 1 \tilde{x}_{n+1} x ~ n + 1 has to be very close to x n + 1 x_{n+1} x n + 1 . This limitation is formally presented as a perturbation ball B : X → 2 X \mathcal{B} : \mathcal{X} \to2^{\mathcal{X}} B : X → 2 X – the set of all points from a given x x x that the adversary is allowed to choose. A common example for images is the ℓ 2 \ell_2 ℓ 2 ball B r ( x ) = { x ~ : ∥ x ~ − x ∥ 2 ≤ r } \mathcal{B}_r(x) = \{\tilde{x} : \lVert\tilde{x} - x \rVert_2 \le r\} B r ( x ) = { x ~ : ∥ x ~ − x ∥ 2 ≤ r } . The adversary has white-box access to the model (its architecture, parameters, etc), and the clean input x n + 1 x_{n+1} x n + 1 , but is not in control of the inference, and is unaware of the random seed used by the MC samples evaluated at test time. The test-time noise is freshly sampled for every query and is unknown when the adversary chooses its perturbation; hence we do not require a permanently secret global seed. We study the worst-case robustness: for any x ~ n + 1 ∈ B r ( x n + 1 ) \tilde{x}_{n+1} \in\mathcal{B}_r(x_{n+1}) x ~ n + 1 ∈ B r ( x n + 1 ) , the prediction should either remain the same, or the defense should abstain from certifying it. This is what we call the threat model.
Robustness certificate. A robustness certificate is a binary decision function
cert f , r ( x i ) = 1 ⇒ ∀ x ~ ∈ B r ( x i ) : f ( x ~ ) = f ( x i ) . (1) \operatorname{cert}_{f,r}(x_i) = 1 \qquad\Rightarrow\qquad\forall\tilde{x} \in\mathcal{B}_r(x_i) : f(\tilde{x}) = f(x_i). \tag*{(1)} cert f , r ( x i ) = 1 ⇒ ∀ x ~ ∈ B r ( x i ) : f ( x ~ ) = f ( x i ) . (1)
The certificate is sound : cert f , r ( x i ) = 1 \operatorname{cert}_{f,r}(x_i) = 1 cert f , r ( x i ) = 1 ensures f f f is stable entirely within B r ( x i ) \mathcal{B}_r(x_i) B r ( x i ) , but it is not complete : cert f , r ( x i ) = 0 \operatorname{cert}_{f,r}(x_i) = 0 cert f , r ( x i ) = 0 does not necessarily imply vulnerability. The standard use case of the certificate is to apply it at test time on each (potentially perturbed) input x ~ n + 1 \tilde{x}_{n+1} x ~ n + 1 , and if cert f , r ( x ~ n + 1 ) = 1 \operatorname{cert}_{f,r}(\tilde{x}_{n+1}) = 1 cert f , r ( x ~ n + 1 ) = 1 , we can safely use the prediction f ( x ~ n + 1 ) f(\tilde{x}_{n+1}) f ( x ~ n + 1 ) ; otherwise, we abstain.
Inverse ball B − 1 \mathcal{B}^{-1} B − 1 . While we allow the adversary to perturb x x x within B ( x ) \mathcal{B}(x) B ( x ) , from the defender’s perspective, we should ensure that the received x ~ \tilde{x} x ~ has the same prediction as x x x which is the reverse act w.r.t. the adversary. Hence, at the test time we use the certificate over the inverse ball B − 1 ( x ) = { x ~ : x ∈ B ( x ~ ) } \mathcal{B}^{-1}(x) = \{\tilde{x} : x \in\mathcal{B}(\tilde{x})\} B − 1 ( x ) = { x ~ : x ∈ B ( x ~ )} which is the smallest set that from any perturbed point x ~ ∈ B ( x ) \tilde{x} \in\mathcal{B}(x) x ~ ∈ B ( x ) it includes x x x . This is the ball that covers the clean point from any potential perturbation. In symmetric balls, we have B − 1 ( x ) = B ( x ) \mathcal{B}^{-1}(x) = \mathcal{B}(x) B − 1 ( x ) = B ( x ) . An example for non-symmetric ball is token insertion, or deletion, where the inverse ball is the opposite act; i.e. B r i n s , − 1 = B r d e l \mathcal{B}^{\mathrm{ins},-1}_r = \mathcal{B}^{\mathrm{del}}_r B r ins , − 1 = B r del .
Binary and confidence certificate. We use c ↓ c^{\downarrow} c ↓ and c ↑ c^{\uparrow} c ↑ for certified lower and upper bounds, with a slight overload: formally c ↓ ( f , B ( x ) ) ≤ inf x ~ ∈ B ( x ) f ( x ~ ) c^{\downarrow}(f, \mathcal{B}(x)) \le\inf_{\tilde{x} \in\mathcal{B}(x)} f(\tilde{x}) c ↓ ( f , B ( x )) ≤ inf x ~ ∈ B ( x ) f ( x ~ ) and c ↑ c^{\uparrow} c ↑ is the corresponding upper bound defined with supremum. In case that the bounds only depend on the value p = f ( x ) p = f(x) p = f ( x ) (not the function, and the point), we write c ↓ ( p , B ) c^{\downarrow}(p, \mathcal{B}) c ↓ ( p , B ) and c ↑ ( p , B ) c^{\uparrow}(p, \mathcal{B}) c ↑ ( p , B ) . Certificates often report c ↓ c^{\downarrow} c ↓ , and c ↑ c^{\uparrow} c ↑ , from which we obtain the 0/1 decision or the certified radii – the largest radius for which the prediction is provably invariant; i.e. r x ∗ = max { r : c ↓ ( f , B r ( x ) ) ≥ 1 / 2 } r_x^* = \max\{r : c^{\downarrow}(f, \mathcal{B}_r(x)) \ge1/2\} r x ∗ = max { r : c ↓ ( f , B r ( x )) ≥ 1/2 } . The latter is a common presentation of certificates; larger radii indicate stronger robustness. However ultimately the certification of a point boils down to comparison with a predefined radius r r r , which is a binary decision. We say x x x is certified at radius r r r either if c ↓ ( p y ∗ ( x ) , B r ) > 1 / 2 c^{\downarrow}(p_y^*(x), \mathcal{B}_r) > 1/2 c ↓ ( p y ∗ ( x ) , B r ) > 1/2 or if c ↑ ( p y ( x ) , B r ) > max y ≠ y ∗ c ↑ ( p y ( x ) , B r ) c^{\uparrow}(p_y(x), \mathcal{B}_r) > \max_{y \ne y^*} c^{\uparrow}(p_y(x), \mathcal{B}_r) c ↑ ( p y ( x ) , B r ) > max y = y ∗ c ↑ ( p y ( x ) , B r ) , for y ∗ y^* y ∗ as the top predicted class. In this work, we operate directly on these certified bounds.
Common certificates are often obtained via exact verification methods [38 , 24 ] and randomized smoothing [11 , 40 ] . The former is a white-box method that requires access to the model’s architecture and parameters, and is typically limited to smaller models of known architectures. The latter is a black-box method that can be applied to any model, and can scale to large and modern architectures, however it requires a large number of model forward passes to estimate the smoothed class probabilities with high confidence.
Objective. We replace the sound but expensive certificate with a tuned proxy function that controls the marginal false-approval rate at level α \alpha α . The guarantee holds for all adversarial perturbations x ~ n + 1 ∈ B ( x n + 1 ) \tilde{x}_{n+1} \in\mathcal{B}(x_{n+1}) x ~ n + 1 ∈ B ( x n + 1 ) for any given clean point x n + 1 x_{n+1} x n + 1 , and the expectation in Eq. (2) is taken marginally over the distribution of (latent) clean inputs. We assume a calibration dataset D n = { x 1 , … , x n } \mathcal{D}_n = \{x_1, \ldots, x_n\} D n = { x 1 , … , x n } of unlabeled points drawn exchangeably from the same distribution as the clean test input x n + 1 x_{n+1} x n + 1 over which we tune the certificate. Only the latent clean point x n + 1 x_{n+1} x n + 1 , and not x ~ n + 1 \tilde{x}_{n+1} x ~ n + 1 , needs to be exchangeable with D n \mathcal{D}_n D n ; e.g. for unseen deployment inputs, D n \mathcal{D}_n D n must be held out from the training data of f f f , as training and test points are not exchangeable conditional on the model. The outcome is a proxy that takes significantly lower computational cost only by relaxing the soundness of the original certificate to a marginally bounded false-approval rate; formally with cert f , r \operatorname{cert}_{f,r} cert f , r , we guarantee that
E D [ { f ( x ~ n + 1 ) ≠ f ( x n + 1 ) } ⋅ cert f , r ( x ~ n + 1 ) ∣ x ~ n + 1 ∈ B ( x n + 1 ) ] ≤ α . (2) \mathbb{E}_{\mathcal{D}}\left[\left\{f(\tilde{x}_{n+1}) \ne f(x_{n+1})\right\} \cdot\operatorname{cert}_{f,r}(\tilde{x}_{n+1}) \mid\tilde{x}_{n+1} \in\mathcal{B}(x_{n+1})\right] \le\alpha. \tag*{(2)} E D [ { f ( x ~ n + 1 ) = f ( x n + 1 ) } ⋅ cert f , r ( x ~ n + 1 ) ∣ x ~ n + 1 ∈ B ( x n + 1 ) ] ≤ α . (2)
In words, over many future (possibly perturbed) inputs, on average at most an α \alpha α fraction are approved while their prediction is flipped. The expectation is over the calibration set, the clean test point, and the internal randomness. Same as conformal prediction itself, the risk is bounded in expectation, and for a fixed calibration set can exceed α \alpha α (with a variance decreasing in the number of calibration points n n n ); the guarantee is also not conditional on any particular input, class, or subpopulation.
Our proxy certificate (ProxC) is built upon two key components, which we introduce next.
Randomized Smoothing
We recall a high level understanding of randomized smoothing, and defer the details to § B. A smoothing function ψ : X → X \psi:\mathcal{X}\to\mathcal{X} ψ : X → X augments the input with a random noise from a predefined distribution; ψ ( x ) = x + ϵ \psi(x)=x+\epsilon ψ ( x ) = x + ϵ . Wrapping any base classifier f f f , we define the smoothed class probability g ( x ) y = Pr ϵ [ f ( x + ϵ ) = y ] g(x)_y=\Pr_{\epsilon}[f(x+\epsilon)=y] g ( x ) y = Pr ϵ [ f ( x + ϵ ) = y ] . Because the push-forward measures f # ψ ( x ) f_{\#}\psi(x) f # ψ ( x ) and f # ψ ( x ~ ) f_{\#}\psi(\widetilde{x}) f # ψ ( x ) overlap heavily for nearby inputs, we can derive model-agnostic lower and upper bounds on g ( x ~ ) y g(\widetilde{x})_y g ( x ) y that depend only on p = g ( x ) y p=g(x)_y p = g ( x ) y and the perturbation radius. On images a well-known smoothing scheme is the isotropic Gaussian noise of magnitude σ \sigma σ , i.e. ϵ ∼ N ( 0 , σ 2 I ) \epsilon\sim\mathcal{N}(0,\sigma^2I) ϵ ∼ N ( 0 , σ 2 I ) . For ℓ 1 \ell_1 ℓ 1 and ℓ 2 \ell_2 ℓ 2 ball, isotropic Gaussian smoothing has closed form lower and upper bounds (c ↓ c^{\downarrow} c ↓ and c ↑ c^{\uparrow} c ↑ ) as Φ σ ( Φ − 1 ( p ) ± r ) \Phi_\sigma(\Phi^{-1}(p)\pm r) Φ σ ( Φ − 1 ( p ) ± r ) regardless of the model’s architecture, or the actual value of x x x . Here Φ σ \Phi_\sigma Φ σ is the CDF of N ( 0 , σ 2 I ) \mathcal{N}(0,\sigma^2I) N ( 0 , σ 2 I ) . For other smoothing schemes, similar bounds can be computed through the recipe from Yang et al. [ [40 ] .
Conformal Risk Control
CRC provides distribution-free, finite-sample guarantees on the expected risk of a system using an exchangeable subsample of its inputs [1 ] . Let L : X × [ 0 , 1 ] → R L:\mathcal{X}\times[0,1]\to\mathbb{R} L : X × [ 0 , 1 ] → R be a risk function with conservativeness parameter λ \lambda λ , so that L ( x , λ ) L(x,\lambda) L ( x , λ ) is non-increasing in λ \lambda λ , right continuous, upper bounded by l max l_{\max} l m a x , and min λ L ( ⋅ , λ ) ≤ α \min_\lambda L(\cdot,\lambda)\leq\alpha min λ L ( ⋅ , λ ) ≤ α for some user-specified α \alpha α . CRC guarantees that we can find λ ⋆ \lambda^\star λ ⋆ such that for future test points x n + 1 x_{n+1} x n + 1 drawn from the same distribution, E [ L ( x n + 1 , λ ⋆ ) ] ≤ α \mathbb{E}[L(x_{n+1},\lambda^\star)]\leq\alpha E [ L ( x n + 1 , λ ⋆ )] ≤ α . Over the holdout calibration points D n = { x i } i = 1 n \mathcal{D}_n=\{x_i\}_{i=1}^n D n = { x i } i = 1 n , and L ˉ n ( λ ) = 1 n ∑ i = 1 n L ( x i , λ ) \bar{L}_n(\lambda)=\frac{1}{n}\sum_{i=1}^nL(x_i,\lambda) L ˉ n ( λ ) = n 1 ∑ i = 1 n L ( x i , λ ) , under exchangeability of D = D n ∪ { x n + 1 } \mathcal{D}=\mathcal{D}_n\cup\{x_{n+1}\} D = D n ∪ { x n + 1 } CRC sets
λ ⋆ = inf { λ : n n + 1 L ˉ n ( λ ) + l max n + 1 ≤ α } , \lambda^\star=\inf\left\{\lambda:\frac{n}{n+1}\bar{L}_n(\lambda)+\frac{l_{\max}}{n+1}\leq\alpha\right\}, λ ⋆ = inf { λ : n + 1 n L ˉ n ( λ ) + n + 1 l m a x ≤ α } ,
ensuring E [ L ( x n + 1 , λ ⋆ ) ] ≤ α \mathbb{E}[L(x_{n+1},\lambda^\star)]\leq\alpha E [ L ( x n + 1 , λ ⋆ )] ≤ α .
ProxC: Proxy Certificate
Our proxy certificate is based on an internal binary proxy function h : X × [ 0 , 1 ] → { 0 , 1 } h:\mathcal{X}\times[0,1]\to\{0,1\} h : X × [ 0 , 1 ] → { 0 , 1 } ; the second parameter of this function, λ \lambda λ , controls its conservativeness. Through conformal risk control we compute the smallest valid parameter λ ⋆ \lambda^\star λ ⋆ that guarantees to control the rate of false-approval made by h ( ⋅ , λ ⋆ ) h(\cdot,\lambda^\star) h ( ⋅ , λ ⋆ ) . A direct application of CRC would treat false approval as an ordinary risk, guaranteeing validity of h ( ⋅ , λ ) h(\cdot,\lambda) h ( ⋅ , λ ) for clean test points that are in-distribution with D n \mathcal{D}_n D n . However, we aim to maintain the guarantee for any x ~ n + 1 ∈ B ( x n + 1 ) \widetilde{x}_{n+1}\in\mathcal{B}(x_{n+1}) x n + 1 ∈ B ( x n + 1 ) , not just the clean point. Thus, the risk observed at test time is not exchangeable with the risks used for calibration. We address this mismatch in § 3.1. After obtaining a valid robustly calibrated parameter λ ⋆ \lambda^\star λ ⋆ , we define c e r t ^ f , r ( x ~ n + 1 ) = h ( x ~ n + 1 , λ ⋆ ) \widehat{\mathrm{cert}}_{f,r}(\widetilde{x}_{n+1})=h(\widetilde{x}_{n+1},\lambda^\star) cert f , r ( x n + 1 ) = h ( x n + 1 , λ ⋆ ) , and guarantee E D [ 1 { f ( x ~ n + 1 ) ≠ f ( x n + 1 ) } ⋅ h ( x ~ n + 1 , λ ⋆ ) ] ≤ α \mathbb{E}_{\mathcal{D}}[\mathbb{1}\{f(\widetilde{x}_{n+1})\ne f(x_{n+1})\}\cdot h(\widetilde{x}_{n+1},\lambda^\star)]\leq\alpha E D [ 1 { f ( x n + 1 ) = f ( x n + 1 )} ⋅ h ( x n + 1 , λ ⋆ )] ≤ α for all x ~ n + 1 ∈ B ( x n + 1 ) \widetilde{x}_{n+1}\in\mathcal{B}(x_{n+1}) x n + 1 ∈ B ( x n + 1 ) .
Robust Conformal Risk Control Through Randomized Smoothing
Angelopoulos et al. [ [1 ] propose robust risk control by replacing the pointwise risk L ( x n + 1 , λ ) L(x_{n+1},\lambda) L ( x n + 1 , λ ) with its worst-case local value L ~ ( x , λ ) = sup x ~ ∈ B r ( x ) L ( x ~ , λ ) \widetilde{L}(x,\lambda)=\sup_{\widetilde{x}\in\mathcal{B}_r(x)}L(\widetilde{x},\lambda) L ( x , λ ) = sup x ∈ B r ( x ) L ( x , λ ) . Calibrating over L ~ \widetilde{L} L ensures
E D [ L ~ ( x ~ n + 1 , λ ) ∣ x ~ n + 1 ∈ B ( x ) ] ≤ E D [ sup x ~ n + 1 ∈ B r ( x n + 1 ) L ( x ~ n + 1 , λ ) ] ≤ α . \mathbb{E}_{\mathcal{D}}[\widetilde{L}(\widetilde{x}_{n+1},\lambda)\mid\widetilde{x}_{n+1}\in\mathcal{B}(x)]\leq\mathbb{E}_{\mathcal{D}}\left[\sup_{\widetilde{x}_{n+1}\in\mathcal{B}_r(x_{n+1})}L(\widetilde{x}_{n+1},\lambda)\right]\leq\alpha. E D [ L ( x n + 1 , λ ) ∣ x n + 1 ∈ B ( x )] ≤ E D [ x n + 1 ∈ B r ( x n + 1 ) sup L ( x n + 1 , λ ) ] ≤ α .
In practice, however, evaluating L ~ \widetilde{L} L itself a certification problem. While it can be upper bounded via c ↑ ( L ( ⋅ , λ ) , B ( x ) ) c^\uparrow(L(\cdot,\lambda),\mathcal{B}(x)) c ↑ ( L ( ⋅ , λ ) , B ( x )) , this reintroduces the computational cost we seek to avoid, as we use the certificate again. We instead rewrite the approach of Zargarbashi et al. [2025] for general risk control, and generalize it to sample-heavy calibration. We apply randomized smoothing at the level of the expected risk. We define a noise-augmented set D + = { x + ϵ : x ∈ D } \mathcal{D}^{+}=\{x+\epsilon:x\in\mathcal{D}\} D + = { x + ϵ : x ∈ D } that preserves exchangeability, yielding a conformal guarantee that is marginal over both the data distribution and the smoothing noises. Here, randomized smoothing bounds transfer this guarantee (conditional on each individual x n + 1 x_{n+1} x n + 1 ) to all perturbations in B r ( x n + 1 ) B_r(x_{n+1}) B r ( x n + 1 ) , enabling robust single-sample inference without Monte Carlo estimation at deployment.
Proposition 1. Let D n = { x 1 , … , x n } D_n = \{x_1, \ldots, x_n\} D n = { x 1 , … , x n } be exchangeable together with the (potentially unseen) clean test point x n + 1 x_{n+1} x n + 1 . Let L : X × [ 0 , 1 ] → { 0 , 1 } L : \mathcal{X} \times[0,1] \to\{0,1\} L : X × [ 0 , 1 ] → { 0 , 1 } be such that, for every x ∈ X x \in\mathcal{X} x ∈ X , the map λ ↦ L ( x , λ ) \lambda\mapsto L(x,\lambda) λ ↦ L ( x , λ ) is non-increasing, right-continuous, and we have L ( ⋅ , 1 ) = 0 L(\cdot,1)=0 L ( ⋅ , 1 ) = 0 . Let ψ : X → X \psi: \mathcal{X} \to\mathcal{X} ψ : X → X be a smoothing scheme that is independent of the data, with model-agnostic certified bounds c ↑ ( ⋅ , B − 1 ) c^{\uparrow}(\cdot,\mathcal{B}^{-1}) c ↑ ( ⋅ , B − 1 ) and c ↑ ( ⋅ , B ) c^{\uparrow}(\cdot,\mathcal{B}) c ↑ ( ⋅ , B ) . Given any user-specified tolerance α > 0 \alpha> 0 α > 0 , let ϵ 1 , … , ϵ n + 1 \epsilon_1,\ldots,\epsilon_{n+1} ϵ 1 , … , ϵ n + 1 be iid draws from ψ \psi ψ . With λ ∗ \lambda^* λ ∗ defined as either
λ ∗ = inf { λ : 1 n + 1 [ 1 + ∑ i = 1 n L ( x i + ϵ , λ ) ] ≤ c ↑ ( α , B − 1 ) } (3) \lambda^* = \inf\left\{\lambda: \frac{1}{n+1}\left[1+\sum_{i=1}^{n}L(x_i+\epsilon,\lambda)\right]\le c^{\uparrow}(\alpha,\mathcal{B}^{-1})\right\} \tag*{(3)} λ ∗ = inf { λ : n + 1 1 [ 1 + i = 1 ∑ n L ( x i + ϵ , λ ) ] ≤ c ↑ ( α , B − 1 ) } (3) or
λ ∗ = inf { λ : 1 n + 1 [ 1 + ∑ i = 1 n c ϵ ↑ ( Pr ϵ [ L ( x i + ϵ , λ ) = 1 ] , B ) ] ≤ α − δ } (4) \lambda^* = \inf\left\{\lambda: \frac{1}{n+1}\left[1+\sum_{i=1}^{n}c^{\uparrow}_{\epsilon}\left(\Pr_{\epsilon}[L(x_i+\epsilon,\lambda)=1],\mathcal{B}\right)\right]\le\alpha-\delta\right\} \tag*{(4)} λ ∗ = inf { λ : n + 1 1 [ 1 + i = 1 ∑ n c ϵ ↑ ( ϵ Pr [ L ( x i + ϵ , λ ) = 1 ] , B ) ] ≤ α − δ } (4) where the latter λ ∗ \lambda^* λ ∗ corresponds to the calibration-heavy variant, we have
E D , ϵ [ L ( x ~ n + 1 + ϵ , λ ∗ ) ] ≤ α , ∀ x ~ n + 1 ∈ B ( x n + 1 ) . \mathbb{E}_{D,\epsilon}\left[L(\widetilde{x}_{n+1}+\epsilon,\lambda^*)\right]\le\alpha,\quad\forall\widetilde{x}_{n+1}\in B(x_{n+1}). E D , ϵ [ L ( x n + 1 + ϵ , λ ∗ ) ] ≤ α , ∀ x n + 1 ∈ B ( x n + 1 ) . where δ ∈ [ 0 , 1 ] \delta\in[0,1] δ ∈ [ 0 , 1 ] is the confidence of the finite sample estimation, and c ϵ ↑ ( Pr ϵ [ L ( x + ϵ , λ ) = 1 ] , B ) c^{\uparrow}_{\epsilon}\left(\Pr_{\epsilon}[L(x+\epsilon,\lambda)=1],\mathcal{B}\right) c ϵ ↑ ( Pr ϵ [ L ( x + ϵ , λ ) = 1 ] , B ) is an upper confidence bound on c ↑ ( Pr ϵ [ L ( x + ϵ , λ ) = 1 ] , B ) c^{\uparrow}\left(\Pr_{\epsilon}[L(x+\epsilon,\lambda)=1],\mathcal{B}\right) c ↑ ( Pr ϵ [ L ( x + ϵ , λ ) = 1 ] , B ) with confidence 1 − δ n 1-\frac{\delta}{n} 1 − n δ .
Proofs are in § C. For the calibration-heavy approach, we estimate the risk at each point x i x_i x i by averaging over m m m noises { ϵ i , j } j = 1 m \{\epsilon_{i,j}\}_{j=1}^{m} { ϵ i , j } j = 1 m ; i.e. p ^ i ( λ ) = 1 m ∑ j = 1 m L ( x i + ϵ i , j , λ ) \widehat{p}_i(\lambda)=\frac{1}{m}\sum_{j=1}^{m}L(x_i+\epsilon_{i,j},\lambda) p i ( λ ) = m 1 ∑ j = 1 m L ( x i + ϵ i , j , λ ) . We then construct the Clopper-Pearson upper confidence bound p ‾ i ( λ ) \overline{p}_i(\lambda) p i ( λ ) with confidence 1 − δ / n 1-\delta/n 1 − δ / n , and set c ϵ ↑ ( Pr ϵ [ L ( x i + ϵ , λ ) = 1 ] , B ) : = c ↑ ( p ‾ i ( λ ) , B ) c^{\uparrow}_{\epsilon}(\Pr_{\epsilon}[L(x_i+\epsilon,\lambda)=1],\mathcal{B}):=c^{\uparrow}(\overline{p}_i(\lambda),\mathcal{B}) c ϵ ↑ ( Pr ϵ [ L ( x i + ϵ , λ ) = 1 ] , B ) := c ↑ ( p i ( λ ) , B ) . Since c ↑ c^{\uparrow} c ↑ is monotone and p ‾ i ( λ ) ≥ Pr ϵ [ L ( x i + ϵ , λ ) = 1 ] \overline{p}_i(\lambda)\ge\Pr_{\epsilon}[L(x_i+\epsilon,\lambda)=1] p i ( λ ) ≥ Pr ϵ [ L ( x i + ϵ , λ ) = 1 ] with the stated confidence, this construction is a valid upper bound on the true smoothed risk (see § A.1).
ProxC: Conformal Proxy Certificate
Let h ^ ( ⋅ , λ ) \widehat{h}(\cdot,\lambda) h ( ⋅ , λ ) be a binary proxy function that is controlled by a conservativeness parameter λ \lambda λ – for any x ∈ X x\in\mathcal{X} x ∈ X and λ 1 < λ 2 \lambda_1<\lambda_2 λ 1 < λ 2 , we have h ^ ( x , λ 1 ) ≥ h ^ ( x , λ 2 ) \widehat{h}(x,\lambda_1)\ge\widehat{h}(x,\lambda_2) h ( x , λ 1 ) ≥ h ( x , λ 2 ) ; a trivial example for proxy function is h ^ ( x , λ ) = I [ max y f ( x ) > λ ] \widehat{h}(x,\lambda)=\mathbb{I}[\max_y f(x)>\lambda] h ( x , λ ) = I [ max y f ( x ) > λ ] . We expect the certificate, and the proxy function to ensure that f ( x ~ n + 1 ) = f ( x n + 1 ) f(\widetilde{x}_{n+1})=f(x_{n+1}) f ( x n + 1 ) = f ( x n + 1 ) ; hence, we directly define the false approval risk for h ^ \widehat{h} h as
Pr D [ I { f ( x ~ n + 1 ) ≠ f ( x n + 1 ) } ⋅ h ^ ( x ~ n + 1 , λ ∗ ) ] ≤ α ∀ x ~ n + 1 ∈ B ( x n + 1 ) . \Pr_D\left[\mathbb{I}\{f(\widetilde{x}_{n+1})\ne f(x_{n+1})\}\cdot\widehat{h}(\widetilde{x}_{n+1},\lambda^*)\right]\le\alpha\quad\forall\widetilde{x}_{n+1}\in B(x_{n+1}). D Pr [ I { f ( x n + 1 ) = f ( x n + 1 )} ⋅ h ( x n + 1 , λ ∗ ) ] ≤ α ∀ x n + 1 ∈ B ( x n + 1 ) .
From Prop. 1, we concluded that augmenting x x x with a random noise results in black-box extension of the risk control guarantee to the whole B ( x n + 1 ) B(x_{n+1}) B ( x n + 1 ) . The risk defined above does not allow the proxy function for any inherent randomness. Hence, we replace the deterministic risk with the following probabilistic generalization
Pr D , ϵ [ I { f ( x ~ n + 1 ) ≠ f ( x n + 1 ) } ⋅ h ^ ( x ~ n + 1 + ϵ , λ ∗ ) ] ≤ α ∀ x ~ n + 1 ∈ B ( x n + 1 ) \Pr_{D,\epsilon}\left[\mathbb{I}\{f(\widetilde{x}_{n+1})\ne f(x_{n+1})\}\cdot\widehat{h}(\widetilde{x}_{n+1}+\epsilon,\lambda^*)\right]\le\alpha\quad\forall\widetilde{x}_{n+1}\in B(x_{n+1}) D , ϵ Pr [ I { f ( x n + 1 ) = f ( x n + 1 )} ⋅ h ( x n + 1 + ϵ , λ ∗ ) ] ≤ α ∀ x n + 1 ∈ B ( x n + 1 )
equivalently
E D [ max x ~ n + 1 ∈ B ( x n + 1 ) I { f ( x ~ n + 1 ) ≠ f ( x n + 1 ) } ⋅ Pr ϵ [ h ^ ( x ~ n + 1 + ϵ , λ ∗ ) = 1 ] ] ≤ α . (5) \mathbb{E}_D\left[\max_{\widetilde{x}_{n+1}\in B(x_{n+1})}\mathbb{I}\{f(\widetilde{x}_{n+1})\ne f(x_{n+1})\}\cdot\Pr_{\epsilon}\left[\widehat{h}(\widetilde{x}_{n+1}+\epsilon,\lambda^*)=1\right]\right]\le\alpha. \tag*{(5)} E D [ x n + 1 ∈ B ( x n + 1 ) max I { f ( x n + 1 ) = f ( x n + 1 )} ⋅ ϵ Pr [ h ( x n + 1 + ϵ , λ ∗ ) = 1 ] ] ≤ α . (5)
This also generalizes the threat model. In a deterministic setup, the adversary’s goal is to change the model’s prediction on an input. In case the certificate was not sound, a more realistic goal was to change the prediction, and fool the certificate to certify the point. Here, with the probabilistic notion of certificate, the goal of the adversary is to increase the probability of the proxy to approve a point while the label is also flipped. We guarantee the above risk to be bounded through the following:
Proposition 2. Let the proxy function h ^ \widehat{h} h be non-increasing and right continuous in λ \lambda λ , and let h ^ ( ⋅ , 1 ) = 0 \widehat{h}(\cdot,1)=0 h ( ⋅ , 1 ) = 0 . Let cert f , r \operatorname{cert}_{f,r} cert f , r be a sound certificate with respect to B r ( ⋅ ) B_r(\cdot) B r ( ⋅ ) , and let ψ \psi ψ be a smoothing scheme with model-agnostic upper, and lower bounds c ↑ c^{\uparrow} c ↑ , and c ↓ c^{\downarrow} c ↓ . Then the proxy function h ^ ( ⋅ + ϵ , λ ∗ ) \widehat{h}(\cdot+\epsilon,\lambda^*) h ( ⋅ + ϵ , λ ∗ ) with
either
λ ∗ = inf { λ : 1 n + 1 [ 1 + ∑ i = 1 n h ^ ( x i + ϵ , λ ) ⋅ ( 1 − cert f , r ( x i ) ) ] ≤ c ↑ ( α , B − 1 ) } (6) \lambda^{*}=\inf\left\{\lambda:\frac{1}{n+1}\left[1+\sum_{i=1}^{n}\hat{h}(x_i+\epsilon,\lambda)\cdot\left(1-\operatorname{cert}_{f,r}(x_i)\right)\right]\le c^{\uparrow}(\alpha,\mathcal{B}^{-1})\right\} \tag*{(6)} λ ∗ = inf { λ : n + 1 1 [ 1 + i = 1 ∑ n h ^ ( x i + ϵ , λ ) ⋅ ( 1 − cert f , r ( x i ) ) ] ≤ c ↑ ( α , B − 1 ) } (6)
or
λ ∗ = inf { λ : 1 n + 1 [ 1 + ∑ i = 1 n c ↑ ( h ^ λ , B ( x i ) ) ⋅ ( 1 − cert f , r ( x i ) ) ] ≤ α } (7) \lambda^{*}=\inf\left\{\lambda:\frac{1}{n+1}\left[1+\sum_{i=1}^{n}c^{\uparrow}(\hat{h}_{\lambda},\mathcal{B}(x_i))\cdot\left(1-\operatorname{cert}_{f,r}(x_i)\right)\right]\le\alpha\right\} \tag*{(7)} λ ∗ = inf { λ : n + 1 1 [ 1 + i = 1 ∑ n c ↑ ( h ^ λ , B ( x i )) ⋅ ( 1 − cert f , r ( x i ) ) ] ≤ α } (7)
guarantees Eq. (5) to hold.
Proof. Given that the certificate is sound, for any x x x , and x ~ ∈ B ( x ) \tilde{x}\in\mathcal{B}(x) x ~ ∈ B ( x ) , we have I { f ( x ~ ) ≠ f ( x ) } ≤ 1 − cert f , r ( x ) \mathbb{I}\{f(\tilde{x})\ne f(x)\}\le1-\operatorname{cert}_{f,r}(x) I { f ( x ~ ) = f ( x )} ≤ 1 − cert f , r ( x ) , and therefore
max x ~ n + 1 ∈ B ( x n + 1 ) I { f ( x ~ n + 1 ) ≠ f ( x n + 1 ) } ⋅ Pr ϵ [ h ^ ( x ~ n + 1 + ϵ , λ ∗ ) = 1 ] ≤ max x ~ n + 1 ∈ B ( x n + 1 ) I { f ( x ~ n + 1 ) ≠ f ( x n + 1 ) } ⋅ max x ~ n + 1 ∈ B ( x n + 1 ) Pr ϵ [ h ^ ( x ~ n + 1 + ϵ , λ ∗ ) = 1 ] ≤ ( 1 − cert f , r ( x n + 1 ) ) ⋅ max x ~ n + 1 ∈ B ( x n + 1 ) Pr ϵ [ h ^ ( x ~ n + 1 + ϵ , λ ∗ ) = 1 ] ≤ ( 1 − cert f , r ( x n + 1 ) ) ⋅ c ↑ ( h ^ λ , B ( x n + 1 ) ) \begin{aligned}
\max_{\tilde{x}_{n+1}\in\mathcal{B}(x_{n+1})}\mathbb{I}\{f(\tilde{x}_{n+1})\ne f(x_{n+1})\}\cdot\Pr_{\epsilon}\left[\hat{h}(\tilde{x}_{n+1}+\epsilon,\lambda^{*})=1\right] \\
&\le\max_{\tilde{x}_{n+1}\in\mathcal{B}(x_{n+1})}\mathbb{I}\{f(\tilde{x}_{n+1})\ne f(x_{n+1})\}\cdot\max_{\tilde{x}_{n+1}\in\mathcal{B}(x_{n+1})}\Pr_{\epsilon}\left[\hat{h}(\tilde{x}_{n+1}+\epsilon,\lambda^{*})=1\right] \\
&\le(1-\operatorname{cert}_{f,r}(x_{n+1}))\cdot\max_{\tilde{x}_{n+1}\in\mathcal{B}(x_{n+1})}\Pr_{\epsilon}\left[\hat{h}(\tilde{x}_{n+1}+\epsilon,\lambda^{*})=1\right] \\
&\le(1-\operatorname{cert}_{f,r}(x_{n+1}))\cdot c^{\uparrow}(\hat{h}_{\lambda},\mathcal{B}(x_{n+1}))
\end{aligned} x ~ n + 1 ∈ B ( x n + 1 ) max I { f ( x ~ n + 1 ) = f ( x n + 1 )} ⋅ ϵ Pr [ h ^ ( x ~ n + 1 + ϵ , λ ∗ ) = 1 ] ≤ x ~ n + 1 ∈ B ( x n + 1 ) max I { f ( x ~ n + 1 ) = f ( x n + 1 )} ⋅ x ~ n + 1 ∈ B ( x n + 1 ) max ϵ Pr [ h ^ ( x ~ n + 1 + ϵ , λ ∗ ) = 1 ] ≤ ( 1 − cert f , r ( x n + 1 )) ⋅ x ~ n + 1 ∈ B ( x n + 1 ) max ϵ Pr [ h ^ ( x ~ n + 1 + ϵ , λ ∗ ) = 1 ] ≤ ( 1 − cert f , r ( x n + 1 )) ⋅ c ↑ ( h ^ λ , B ( x n + 1 ))
The risk function has two inputs besides λ \lambda λ – the received point and its ground truth clean point, as an anchor. The anchor variable x n + 1 x_{n+1} x n + 1 should be kept explicit. We define the risk for the exchangeable paired sample { ( x i , x i ) } i = 1 n ∪ { ( x n + 1 , x n + 1 ) } \{(x_i,x_i)\}_{i=1}^{n}\cup\{(x_{n+1},x_{n+1})\} {( x i , x i ) } i = 1 n ∪ {( x n + 1 , x n + 1 )} , and only allow the first coordinate to be perturbed. For the single-sample rule define the binary anchored risk
L a n c ( ( z , x ) , λ ) = ( 1 − cert f , r ( x ) ) h ^ ( z , λ ) . L_{\mathrm{anc}}((z,x),\lambda)=(1-\operatorname{cert}_{f,r}(x))\hat{h}(z,\lambda). L anc (( z , x ) , λ ) = ( 1 − cert f , r ( x )) h ^ ( z , λ ) .
This risk is non-increasing, right-continuous, and bounded in λ \lambda λ as it inherits properties from h ^ \hat{h} h ^ . Note that the other term is only 0, or 1, and only a function of the second element x x x . Applying Prop. 1 in single-sample form, i.e. Eq. 3, tunes to λ ∗ \lambda^{*} λ ∗ as defined in Eq. (6) , and guarantees that
E D , ϵ [ ( 1 − cert f , r ( x n + 1 ) ) h ^ ( x ~ n + 1 + ϵ , λ ∗ ) ] ≤ α , ∀ x ~ n + 1 ∈ B ( x n + 1 ) . \mathbb{E}_{D,\epsilon}\left[(1-\operatorname{cert}_{f,r}(x_{n+1}))\hat{h}(\tilde{x}_{n+1}+\epsilon,\lambda^{*})\right]\le\alpha,\qquad\forall\tilde{x}_{n+1}\in\mathcal{B}(x_{n+1}). E D , ϵ [ ( 1 − cert f , r ( x n + 1 )) h ^ ( x ~ n + 1 + ϵ , λ ∗ ) ] ≤ α , ∀ x ~ n + 1 ∈ B ( x n + 1 ) .
Note that here, the risk control is applied to the tuple, and the certificate only to the first argument (the anchor). The soundness inequality I { f ( x ~ n + 1 ) ≠ f ( x n + 1 ) } ≤ 1 − cert f , r ( x n + 1 ) \mathbb{I}\{f(\tilde{x}_{n+1})\ne f(x_{n+1})\}\le1-\operatorname{cert}_{f,r}(x_{n+1}) I { f ( x ~ n + 1 ) = f ( x n + 1 )} ≤ 1 − cert f , r ( x n + 1 ) then implies
E D , ϵ [ I { f ( x ~ n + 1 ) ≠ f ( x n + 1 ) } h ^ ( x ~ n + 1 + ϵ , λ ∗ ) ] ≤ α ∀ x ~ n + 1 ∈ B ( x n + 1 ) . \mathbb{E}_{D,\epsilon}\left[\mathbb{I}\{f(\tilde{x}_{n+1})\ne f(x_{n+1})\}\hat{h}(\tilde{x}_{n+1}+\epsilon,\lambda^{*})\right]\le\alpha\qquad\forall\tilde{x}_{n+1}\in\mathcal{B}(x_{n+1}). E D , ϵ [ I { f ( x ~ n + 1 ) = f ( x n + 1 )} h ^ ( x ~ n + 1 + ϵ , λ ∗ ) ] ≤ α ∀ x ~ n + 1 ∈ B ( x n + 1 ) .
For the calibration-heavy rule, we compute the worst-case smoothed risk of the anchored loss. Since the certificate term ( 1 − cert f , r ( x ) ) (1-\operatorname{cert}_{f,r}(x)) ( 1 − cert f , r ( x )) depends only on the anchor x x x and not on the perturbed first argument, c ↑ ( L a n c ( ( ⋅ , x ) , λ ) , B ( x ) ) = ( 1 − cert f , r ( x ) ) c ↑ ( h ^ λ , B ( x ) ) c^{\uparrow}(L_{\mathrm{anc}}((\cdot,x),\lambda),\mathcal{B}(x))=(1-\operatorname{cert}_{f,r}(x))c^{\uparrow}(\hat{h}_{\lambda},\mathcal{B}(x)) c ↑ ( L anc (( ⋅ , x ) , λ ) , B ( x )) = ( 1 − cert f , r ( x )) c ↑ ( h ^ λ , B ( x )) . Applying the calibration-heavy form of Prop. 1 (i.e. Eq. 4) with this upper bound yields Eq. (7) and the same final guarantee Eq. (5) . The core intuition throughout is to define the risk as a function of both the perturbed input and the corresponding clean anchor. During calibration, both coordinates coincide and are observable; at test time, the guarantee holds with respect to the certificate evaluated at the (latent) clean point.
Augmented Inference
Prop. 2 requires an existing sound certificate at calibration time, which is itself computationally expensive. An alternative is to incorporate the noise augmentation directly into the inference rule, defining a probabilistic classifier which already exhibits robustness. In this case, the noise-augmented inference simultaneously produces a prediction and serves as an abstention rule: the proxy approves when the noise-augmented model agrees with the clean prediction, and the guarantee covers the event that the prediction at x ~ n + 1 + ϵ \tilde{x}_{n+1}+\epsilon x ~ n + 1 + ϵ toggles from that of x n + 1 x_{n+1} x n + 1 , and the proxy nevertheless approves. This is a guarantee on a randomized joint prediction-and-approval event: both the label and the approval are obtained from the same noise draw. The guarantee (for bounded false approval ratio) is written as:
E D [ max x ~ n + 1 ∈ B ( x n + 1 ) Pr ϵ [ I { f ( x ~ n + 1 + ϵ ) ≠ f ( x n + 1 ) } ⋅ h ^ ( x ~ n + 1 + ϵ , λ ∗ ) ] ] ≤ α (8) \mathbb{E}_{D}\left[\max_{\tilde{x}_{n+1}\in\mathcal{B}(x_{n+1})}\Pr_{\epsilon}\left[\mathbb{I}\{f(\tilde{x}_{n+1}+\epsilon)\ne f(x_{n+1})\}\cdot\hat{h}(\tilde{x}_{n+1}+\epsilon,\lambda^{*})\right]\right]\le\alpha \tag*{(8)} E D [ x ~ n + 1 ∈ B ( x n + 1 ) max ϵ Pr [ I { f ( x ~ n + 1 + ϵ ) = f ( x n + 1 )} ⋅ h ^ ( x ~ n + 1 + ϵ , λ ∗ ) ] ] ≤ α (8)
Proposition 3. Given the proxy function h ^ \hat{h} h ^ , and the smoothing distribution ψ \psi ψ with the same properties as in Prop. 2, the proxy function h ( z ) = h ^ ( z + ϵ , λ ∗ ) h(z)=\hat{h}(z+\epsilon,\lambda^*) h ( z ) = h ^ ( z + ϵ , λ ∗ ) with
λ ∗ = inf { λ : 1 n + 1 [ 1 + ∑ i = 1 n η ( x i + ϵ , λ , x i ) ] ≤ c ↓ ( α , B − 1 ) } \lambda^*=\inf\left\{\lambda:\frac{1}{n+1}\left[1+\sum_{i=1}^{n}\eta(x_i+\epsilon,\lambda,x_i)\right]\le c^{\downarrow}(\alpha,\mathcal{B}^{-1})\right\} λ ∗ = inf { λ : n + 1 1 [ 1 + i = 1 ∑ n η ( x i + ϵ , λ , x i ) ] ≤ c ↓ ( α , B − 1 ) } and η ( z , λ , x ) = h ^ ( z , λ ) ⋅ I { f ( z ) ≠ f ( x ) } \eta(z,\lambda,x)=\hat{h}(z,\lambda)\cdot\mathbb{I}\{f(z)\ne f(x)\} η ( z , λ , x ) = h ^ ( z , λ ) ⋅ I { f ( z ) = f ( x )} guarantees Eq. (8) to hold.
ProxC: The framework
While our framework is general, we focus on a trivial example which is a thresholded proxy function h ^ ( z , λ ) = I [ f ( z ) y > λ ] \hat{h}(z,\lambda)=\mathbb{I}[f(z)_y>\lambda] h ^ ( z , λ ) = I [ f ( z ) y > λ ] . Before deployment, we calibrate the proxy on D n D_n D n using noise-augmented inputs, following either Prop. 2 or Prop. 3 depending on the desired guarantee, and with either a single noise sample per point or a larger MC budget. Intuitively, for ProxC we run the expensive certificate once per calibration point; only the points it does not certify can be falsely approved, and we pick the least conservative λ \lambda λ for which the proxy approves such (noise-augmented) points rarely enough, at the corrected level c ↓ ( α , B − 1 ) c^{\downarrow}(\alpha,\mathcal{B}^{-1}) c ↓ ( α , B − 1 ) . At test time only the proxy is evaluated. The calibration produces a scalar λ ∗ \lambda^* λ ∗ for the given radius r r r . At test time, for the input x ~ n + 1 \tilde{x}_{n+1} x ~ n + 1 , one noise sample from ψ \psi ψ is drawn, added to x ~ n + 1 \tilde{x}_{n+1} x ~ n + 1 , and the result is passed through the proxy. Based on the desired guarantee our inference can be in either of the following directions: 1) If we target Eq. (5) , calibration uses a sound certificate as backbone to identify non-robust points; at deployment the same inference rule produces the label y y y and the proxy certifies robustness – therefore, we follow the inference rule of the certificate (in our experiments a majority vote over 50 noisy samples); 2) If we target Eq. (8) a single noise augmentation from ψ \psi ψ is used both to obtain the predicted label and to evaluate the proxy. In all cases, the output is a (label, certification decision) pair. Pseudo-code for all three variants is in § A.
Based on the budget for calibration, ProxC-A (Prop. 3) is the cheapest option with single sample both in calibration and test, ProxC (Prop. 2) stays in between only sampling to compute the backbone certificate, and ProxC-H uses high sample rate both for the backbone certificate and for estimation of the worst case risk. All three methods use a single sample at test time; see Table 5 in § A.
Fundamental limitations. Our guarantee relaxes the soundness to bounded error – our proxy certifies by mistake with a rate of at most α \alpha α for either clean or perturbed inputs. So to apply our framework we assume that such bounded error might be tolerable; e.g. large-scale dataset auditing, robustness monitoring, high-throughput content pipelines, or APIs where the proxy decides whether to escalate to the expensive certificate. Additionally, the backbone certified ratio is a performance ceiling; the sound certified ratio of ProxC (the fraction of certifications that are correct) is bounded by the backbone certificate’s certified ratio; however, the total certified ratio (because of the at-most-α \alpha α fraction of permitted false approvals) can get slightly higher (see Table 2 ViT at r = 0 r=0 r = 0 ). Our framework relies on a holdout calibration set D n = { x i } i = 1 n D_n=\{x_i\}_{i=1}^n D n = { x i } i = 1 n sampled exchangeably from the distribution of clean future test inputs; in contrast to conformal prediction, this assumption is relatively mild because the calibration points are unlabeled. Nevertheless, our approach is similarly sensitive to shifts in the distribution of unobserved clean points. Under distribution shift, the proxy can be recalibrated on a few recent unlabeled inputs by running the expensive certificate only on them. ProxC offers a marginal guarantee rather than conditional. This mirrors the usual limitation of conformal prediction, and risk control. This means that the proxy may be more conservative on some parts of the distribution and less reliable on others. Our main assumption is that the clean inputs follow the deployment distribution. This means that the adversary is not in control of data distribution (which is a shift in subpopulation). In local regions, and in low chance classes the risk can exceed α \alpha α (we report class-specific risks in Table 11 , and Table 12 ).
Table 2. Certified ratio (CR, %) and certified accuracy (CA, %) on ImageNet with σ = 0.5 \sigma= 0.5 σ = 0.5 . RS uses n = 2,000 n = 2{,}000 n = 2 , 000 (ResNet-50) and n = 10,000 n = 10{,}000 n = 10 , 000 (ViT) Monte Carlo samples (single calibration run each). Entries marked † use deterministic (non-smoothing) certificates reported directly from the reference. Note the comparison is between pointwise and marginal guarantees.
Table 11. False-approval risk and certified ratio of the proxy on ImageNet, stratified to the best and worst 100 classes.
Table 12. Per-class false-approval risk, certified ratio (CR), and risk conditional on approval (FA/appr = risk/CR) of the proxy on CIFAR-10, in % (setup of Table 13, ∣ D n ∣ = 500 |\mathcal{D}_n| = 500 ∣ D n ∣ = 500 , averaged over 500 calibration splits). All classes have the same frequency (10%), so the marginal values (last row) are the averages over classes.
These limitations motivate the future work: (i) designing better proxies to increase coverage over the backbone’s certified ratio; (ii) defining localized and adaptive forms of CRC, approaching for close-to-conditional guarantees; and (iii) handling distribution shift in the latent clean space.
Experiments
Our evaluation focuses on three points, also summarized in Table 1 . We show that (i) as guaranteed, the marginal false-approval rate remains below the tolerance α \alpha α on both clean and adversarial inputs; (ii) ProxC recovers a large fraction of the certified ratio and accuracy of randomized smoothing at a substantially lower computational cost; and (iii) the computational gains scale with the reduction in Monte Carlo samples required at inference time We further compare ProxC with state-of-the-art robustness certificates beyond randomized smoothing. Despite relaxing soundness to bounded risk, randomized smoothing scales more effectively to larger models such as vision transformers. We evaluate both text and image settings. The code is available at https://github.com/soroushzargar/ProxC .
Expected behaviour. The objective of ProxC is not to outperform the backbone certificate on which it is calibrated; by design, the backbone is the ceiling for performance. Instead, our aim is to approximate the certificate with a cheaper function (without the need for MC-sampling), while controlling its false signals statistically. In this sense, ProxC is successful when it remains valid, and can cover a higher portion of backbone certificate’s approval ratio; by design it is also supposed to reduce the cost by thousands of forward passes. Therefore we compare the risk as a sanity check, and report the certified ratio and accuracy as the analog to coverage in conformal prediction.
Setup of image experiments. We evaluate ProxC on CIFAR-10 [25 ] and ImageNet [12 ] datasets under ℓ 2 \ell_2 ℓ 2 perturbations. Our results are applicable to any binary certificate, and any smoothing scheme (same as Zargarbash et al. [2025]). We use two main model configurations. (i) ResNet-110 (CIFAR-10) and ResNet-50 (ImageNet). We follow Cohen et al. [2019], trained with Gaussian noise augmentation at the same σ \sigma σ as smoothing (default is σ = 0.5 \sigma= 0.5 σ = 0.5 ). (ii) Following Salman et al. [2020], and Carlini et al. [2022], the augmented input ( x ~ n + 1 + ϵ ) (\tilde{x}_{n+1}+\epsilon) ( x ~ n + 1 + ϵ ) is passed through class-unconditional diffusion followed by a BEiT-L model from Bao et al. [2021]. Models are frozen; only the proxy threshold λ \lambda λ is calibrated. Our default tolerance level is α = 0.05 \alpha= 0.05 α = 0.05 and for calibration-heavy experiment we use the Clopper-Pearson intervals with union confidence of 1 − δ = 0.999 1-\delta= 0.999 1 − δ = 0.999 — both for randomized smoothing and our own proxy certificate. We report the average over 5 runs with calibration set resampling (unless specified). ∣ D n ∣ |\mathcal{D}_n| ∣ D n ∣ is set variably between 200 and 500 points. We examine our method on 4096 images from CIFAR-10 and 2048 images from ImageNet. By default we run the backbone certificate with 2000 MC samples (unless specified), out of which 50 are used for the majority-vote prediction and 1950 for the certificate. Note that ProxC-A does not require such sampling. For calibration heavy methods, we use 20,000 MC samples at calibration-time which is a one time pre-processing.
Cost accounting. The single forward pass refers only to the certification decision: ProxC and ProxC-H still obtain the label with the inference rule of the backbone (50 forwards, i.e. 51 in total), ProxC-A uses the same noisy forward for the label and the approval (1 in total). The full accounting, the fallback cost across radii, and the break-even point of ProxC-H are in Table 9 , Table 10 , and § E.
Table 9. Forward passes per test input on ImageNet (2000 MC samples for randomized smoothing: 50 for the label and N M C = 1950 N_{\mathrm{MC}} = 1950 N MC = 1950 for the certificate). CR is the certified ratio of the proxy; the fallback calls the backbone certificate only when the proxy rejects.
Table 10. Fallback ProxC on ImageNet/ResNet: proxy reject rate and average forwards per query. Speedups are relative to randomized smoothing with 1950 (certification-only) and 2000 (end-to-end) forwards.
Results on image datasets. Table 1 reports results on ImageNet at r = 0.14 r = 0.14 r = 0.14 . There are two use cases: using ProxC as standalone reduces the certification cost from the MC sampling budget to 1, recovering acceptably high portion of the certified accuracy (in our case it is a 1950× \times × reduction of the certification-only cost, and from 2000 to 51 forwards, i.e. 39× \times × , end-to-end including the label). In fallback setup, the full certified ratio of the backbone certificate is recovered, at the cost of the speed up. Still in this setup we have a speed up of 2.50× \times × in certification-only cost (2.41× \times × end-to-end), which decreases with r r r (Table 10 ). ProxC-H improves the certified ratio of the ViT pipeline at r = 0.5 r = 0.5 r = 0.5 at the cost of a heavier calibration phase (Table 7 ). It uses the heavy computation only once, and in the test time it is under the same single-sample regime. The empirical false-approval rate remains well below α = 5 % \alpha= 5\% α = 5% in almost all experiments, confirming the validity of the theoretical guarantee (the guarantee is in expectation also over calibration sets, meaning that for a single split exceeding α \alpha α by a minor margin can happen, e.g. ViT at r = 0 r = 0 r = 0 in Table 2 ; this variance shrinks as ∣ D n ∣ |\mathcal{D}_n| ∣ D n ∣ grows, see Table 13 ). Figure 1 compares ProxC, and ProxC-A with the backbone randomized smoothing certificate in more detail: It shows that with RS we can not reduce the sample rate to acceptable budgets (top left). It also shows the effect of the smoothing magnitude σ \sigma σ (bottom left).
Figure 1. Top row (ImageNet). Left: certified ratio of randomized smoothing (RS) as a function of the Monte Carlo sample budget, across perturbation radii r r r (dotted lines show the performance on perturbed points). Middle: certified ratio (solid) and certified accuracy (dotted) as functions of r r r for ResNet. Right: the same comparison on the Vision Transformer. Bottom row (CIFAR-10). Left: Effect of σ \sigma σ on certified ratio. Middle: certified ratio of ProxC, and Right ProxC-A across various radii. All results are with σ = 0.5 \sigma= 0.5 σ = 0.5 unless specified. All curves report mean over 5 runs.
Table 7. Certified Ratio (CR, %) and Certified Accuracy (CA, %) on ImageNet with ViT + Denoising pipeline (σ = 0.5 \sigma=0.5 σ = 0.5 , 400 calibration samples, 3 independent runs, 99.9% confidence). α = 5 % \alpha= 5\% α = 5% . All values: mean ± std over runs. “—” denotes calibration failure.
Table 13. Effect of the calibration-set size n = ∣ D n ∣ n = |\mathcal{D}_n| n = ∣ D n ∣ on CIFAR-10 (ResNet-110, σ = 0.5 \sigma= 0.5 σ = 0.5 , α = 5 % \alpha= 5\% α = 5% ). Proxy risk and certified ratio (CR) in %, mean ± \pm ± std over 500 random calibration splits; the test set is all images not used for calibration. Infeasible: 1 / ( n + 1 ) > α r 1/(n + 1) > \alpha_r 1/ ( n + 1 ) > α r , so the proxy approves nothing.
Our main goal can be empirically validated in Table 2 . Randomized smoothing, and exact certificates operate at two ends of a trade-off between computational efficiency (from sample-rate), and other benefits like larger robust radii, and black-box access. The certification step of ProxC operates at the same computational cost as verification (a single forward), while its guarantee is from randomized smoothing. Setting aside the relaxation from a sound certificate to marginal bounded error, it highlights the potentials of randomized smoothing once its sampling bottleneck is removed by the proxy — redefining the trade-off. This relaxation emphasizes that this comparison should be interpreted with care – the results are not directly comparable; but it shows the trade-off between soundness, cost, and ratio. In applications where this relaxation is acceptable, the savings can be decisive. As noted before, the Jensen’s inequality is the cost of using a single sample in calibration. ProxC-H instead uses sampling to estimate the expected risk. As shown in Table 3 , by increasing the calibration time sample rate even new values of r r r become reachable. Note that this sampling is only done once, during calibration. Later in Table 6 we show the validity under PGD-RS attack which aims to break randomized smoothing. Still under attack the risk remains below the tolerance level.
Table 3. Calibration sample budget n m c n_{\mathrm{mc}} n mc for ProxC-H on ImageNet (ViT + denoising, σ = 0.5 \sigma= 0.5 σ = 0.5 , α = 0.05 \alpha= 0.05 α = 0.05 , averaged over 3 runs). Each cell reports CR (%) with FA (%) in parentheses. All FA values remain ≤ α = 5 % \le\alpha= 5\% ≤ α = 5% .
Table 6. Certified ratio (CR, %) and certified accuracy (CA, %) on perturbed CIFAR-10 (σ = 0.5 \sigma= 0.5 σ = 0.5 , calibration fraction 0.2), reported as mean ± std over two independent calibration runs. Test datapoints are attacked with PGD-RS attack on ℓ 2 \ell_2 ℓ 2 ball. Risk is the empirical false-approval rate of the proxy certificate under attack. Calibration fails at r ≥ 0.75 r \ge0.75 r ≥ 0.75 for both methods.
NLP experiments. We validate the framework on text classification, using CERT-ED [22 ] . The corresponding threat model is the edit (Levenshtein) distance at the token level The backbone smoothed classifier is RoBERTa-base fine-tuned on AG-News (4-class topic classification, 7,600 test inputs) with the matching noise distribution applied at every training forward pass. Table 4 reports the performance of ProxC, and ProxC-H alongside the base certificate. Here, the backbone certificate is over edit distance, and the proxy certificate is over r r r insertions. We further discuss the theoretical background behind the NLP-experiments in § E.
Table 4. NLP task: Certified ratio (CR) and certified accuracy (CA) of the backbone certificate and ProxC and risk. The certification is over r r r -insertions.
Conclusion
We introduced the proxy certificate (ProxC), a framework that significantly saves computational cost of robustness, by trading the pointwise soundness of a robustness certificate for a bounded marginal false-approval rate. We combine randomized smoothing with conformal risk control, allowing for a robust risk control setup, that works with a single augmented sample for the certification decision at test time (in contrast with heavy MC sampling). Depending on the compute budget, the calibration can be done with heavy MC sampling or again with a single sample. As a standalone certificate, ProxC certifies with one forward pass (51 end-to-end including the label), while as a fallback it recovers the backbone’s certified ratio with a more modest speedup (1.3–3.8× end-to-end on ImageNet). Under the bounded-risk relaxation, ProxC achieves higher certified accuracy than state-of-the-art deterministic verifiers at matching certification cost, although the two provide qualitatively different guarantees (marginal vs. pointwise) on different architectures, while its black-box nature enables application to large architectures such as vision transformers and language models that are out of reach for white-box verification. This highlights the potential in randomized smoothing, as a powerful defense. Our guarantee is marginal and does not extend to individual inputs, classes, or shifted distributions; addressing these, together with a cheaper label prediction and early-stopping backbones, is left for future work.
Acknowledgments and Disclosure of Funding
This work was supported only by the authors’ affiliations, the CISPA Helmholtz Center for Information Security and the University of Cologne, and received no third-party funding. The authors declare no competing interests.
Algorithms
For simplicity, in the algorithms below we write h ^ ( z , λ ; y ) \hat{h}(z,\lambda;y) h ^ ( z , λ ; y ) for the proxy approval of class y y y at the received point z z z . The class y y y can be determined by any arbitrary inference rule. For ProxC, and ProxC-H, we use the conventional classification approach in randomized smoothing, which is to take the majority vote class over a low sample rate (e.g. 50). We also write
R ˉ n ( λ ) = 1 + ∑ i = 1 n R i ( λ ) n + 1 \bar{R}_n(\lambda)=\frac{1+\sum_{i=1}^{n}R_i(\lambda)}{n+1} R ˉ n ( λ ) = n + 1 1 + ∑ i = 1 n R i ( λ )
which is the conformal empirical risk with the standard one-point correction. For ProxC, and ProxC-H we use c ↓ ( α , B − 1 ) c^{\downarrow}(\alpha,\mathcal{B}^{-1}) c ↓ ( α , B − 1 ) , and α − δ \alpha-\delta α − δ as the risk threshold, respectively, following the setup in Prop. 1.
Alg 1 is the pseudo-code for ProxC. It uses the backbone certificate only on D n D_n D n in order to identify the points for which false approval is possible – the points that the backbone certificate approves directly have a risk of 0 (i.e. c i = 1 c_i=1 c i = 1 ) since for any value of the proxy they are not a false approval. On non-certified points, the proxy is allowed to approve only often enough that the smoothed, robustly corrected CRC risk stays below α \alpha α . At test time the certificate is no longer evaluated: the calibrated proxy itself is the certificate.
Algorithm 1 PROXC: Proxy Certificate Inference
Require: Calibration set D n = { x i } i = 1 n D_n=\{x_i\}_{i=1}^{n} D n = { x i } i = 1 n , classifier f f f , sound certificate cert f , r \operatorname{cert}_{f,r} cert f , r , smoothing scheme ψ \psi ψ , proxy h ^ \hat{h} h ^ , target risk α \alpha α , radius r r r
Ensure: Calibrated threshold λ ∗ \lambda^{*} λ ∗ and proxy certificate cert ^ f , r \widehat{\operatorname{cert}}_{f,r} cert f , r
Calibration:
for i = 1 , … , n i=1,\ldots,n i = 1 , … , n do
Compute the reference prediction y i y_i y i using the inference rule associated with cert f , r \operatorname{cert}_{f,r} cert f , r
Compute the certificate decision c i ← cert f , r ( x i ) c_i\leftarrow\operatorname{cert}_{f,r}(x_i) c i ← cert f , r ( x i )
Draw one independent smoothing noise ϵ i ∼ ψ \epsilon_i\sim\psi ϵ i ∼ ψ and set z i ← x i + ϵ i z_i\leftarrow x_i+\epsilon_i z i ← x i + ϵ i
end for
Define R i ( λ ) ← ( 1 − c i ) h ^ ( z i , λ ; y i ) R_i(\lambda)\leftarrow(1-c_i)\hat{h}(z_i,\lambda;y_i) R i ( λ ) ← ( 1 − c i ) h ^ ( z i , λ ; y i )
Via binary search, set
λ ∗ ← inf { λ : R ˉ n ( λ ) ≤ c ↓ ( α , B − 1 ) } . \lambda^{*}\leftarrow\inf\{\lambda:\bar{R}_n(\lambda)\leq c^{\downarrow}(\alpha,\mathcal{B}^{-1})\}. λ ∗ ← inf { λ : R ˉ n ( λ ) ≤ c ↓ ( α , B − 1 )} .
Deployment:
Given x ~ \tilde{x} x ~ , compute y ← y\leftarrow y ← the reference prediction at x ~ \tilde{x} x ~ (e.g. majority vote over 50 noisy samples)
Draw ϵ ∼ ψ \epsilon\sim\psi ϵ ∼ ψ and return y y y if h ^ ( x ~ + ϵ , λ ∗ ; y ) = 1 \hat{h}(\tilde{x}+\epsilon,\lambda^{*};y)=1 h ^ ( x ~ + ϵ , λ ∗ ; y ) = 1 ; otherwise abstain
return cert ^ f , r ( x ~ ) = h ^ ( x ~ + ϵ , λ ∗ ; y ) \widehat{\operatorname{cert}}_{f,r}(\tilde{x})=\hat{h}(\tilde{x}+\epsilon,\lambda^{*};y) cert f , r ( x ~ ) = h ^ ( x ~ + ϵ , λ ∗ ; y )
Alg 2 removes the explicit certificate completely. Instead of asking whether cert f , r \operatorname{cert}_{f,r} cert f , r can prove local stability, calibration directly measures whether the randomized inference rule changes the clean prediction. The proxy is then calibrated as an abstention rule for the augmented probabilistic classifier itself. This is the cheapest version of the framework: calibration and deployment both use the same one-sample augmented inference mechanism, and the guarantee is exactly the joint event of toggled prediction and false-approval in Eq. 8.
Front-Loaded Calibration for ProxC-H
Alg 3 is useful when a single-time high computational cost is available; given higher compute power, it allows for less conservative proxy. Calibration proceeds in two independent phases (detailed below): a tuning phase (Alg 4) that uses m t u n e m_{\mathrm{tune}} m tune noise samples per point to select a candidate threshold λ c a n d \lambda_{\mathrm{cand}} λ cand via a simulated CRC condition, and a validation phase (Alg 5) that uses m c e r t m_{\mathrm{cert}} m cert fresh, independent samples to confirm λ c a n d \lambda_{\mathrm{cand}} λ cand at the fixed threshold. The two-stage split eliminates the selection effect that arises when the same samples are used to both scan for λ ∗ \lambda^{*} λ ∗ and bound the risk at λ ∗ \lambda^{*} λ ∗ . Deployment remains identical to ProxC: one noisy proxy evaluation decides whether the prediction is accepted.
Taken together, the three algorithms give a simple recipe. Use ProxC when a trusted certificate can be afforded once on the calibration set and deployment must be cheap. Use ProxC-A when even calibration-time certification is undesirable and one is willing to certify the randomized inference rule directly. Use ProxC-H when calibration is allowed to be sample-heavy; the additional calibration
Algorithm 2 PROXC-A: Proxy-Augmented Inference
Require: Calibration set D n = { x i } i = 1 n \mathcal{D}_n = \{x_i\}_{i=1}^n D n = { x i } i = 1 n , classifier f f f , smoothing scheme ψ \psi ψ , proxy h ^ \hat{h} h ^ , target risk α \alpha α , radius r r r
Ensure: Calibrated threshold λ ∗ \lambda^* λ ∗ and augmented proxy certificate cert ^ f , r A \widehat{\operatorname{cert}}^{\mathrm{A}}_{f,r} cert f , r A
Calibration:
for i = 1 , … , n i = 1,\ldots,n i = 1 , … , n do
Compute the clean anchor prediction y i ← f ( x i ) y_i \leftarrow f(x_i) y i ← f ( x i )
Draw one independent smoothing noise ϵ i ∼ ψ \epsilon_i \sim\psi ϵ i ∼ ψ and set z i ← x i + ϵ i z_i \leftarrow x_i + \epsilon_i z i ← x i + ϵ i
Compute the augmented prediction y ~ i ← f ( z i ) \tilde{y}_i \leftarrow f(z_i) y ~ i ← f ( z i )
end for
Define R i ( λ ) ← I { y ~ i ≠ y i } h ^ ( z i , λ ; y ~ i ) R_i(\lambda) \leftarrow\mathbb{I}\{\tilde{y}_i \ne y_i\}\hat{h}(z_i,\lambda;\tilde{y}_i) R i ( λ ) ← I { y ~ i = y i } h ^ ( z i , λ ; y ~ i )
Set
λ ∗ ← inf { λ : R ‾ n ( λ ) ≤ c ∗ ( α , B − 1 ) } . \lambda^* \leftarrow\inf\{\lambda: \overline{R}_n(\lambda) \le c^*(\alpha,B^{-1})\}. λ ∗ ← inf { λ : R n ( λ ) ≤ c ∗ ( α , B − 1 )} .
Deployment:
Given x ~ \tilde{x} x ~ , draw ϵ ∼ ψ \epsilon\sim\psi ϵ ∼ ψ , set z ← x ~ + ϵ z \leftarrow\tilde{x}+\epsilon z ← x ~ + ϵ , and compute y ← f ( z ) y \leftarrow f(z) y ← f ( z )
Return y y y if h ^ ( z , λ ∗ ; y ) = 1 \hat{h}(z,\lambda^*;y)=1 h ^ ( z , λ ∗ ; y ) = 1 ; otherwise abstain
return cert ^ f , r A ( x ~ ) = h ^ ( x ~ + ϵ , λ ∗ ; f ( x ~ + ϵ ) ) \widehat{\operatorname{cert}}^{\mathrm{A}}_{f,r}(\tilde{x}) = \hat{h}(\tilde{x}+\epsilon,\lambda^*;f(\tilde{x}+\epsilon)) cert f , r A ( x ~ ) = h ^ ( x ~ + ϵ , λ ∗ ; f ( x ~ + ϵ ))
Algorithm 3 PROXC-H: Calibration-Heavy Proxy Certificate
Require: Calibration set D n = { x i } i = 1 n \mathcal{D}_n = \{x_i\}_{i=1}^n D n = { x i } i = 1 n , classifier f f f , sound certificate cert f , r \operatorname{cert}_{f,r} cert f , r , smoothing scheme ψ \psi ψ , proxy h ^ \hat{h} h ^ , target risk α \alpha α , radius r r r , tuning sample-rate m t u n e m_{\mathrm{tune}} m tune , certification sample-rate m c e r t m_{\mathrm{cert}} m cert , confidence parameter δ \delta δ , tuning slack δ 0 > 0 \delta_0 > 0 δ 0 > 0
Ensure: Calibrated threshold λ ∗ \lambda^* λ ∗ and proxy certificate cert ^ f , r H \widehat{\operatorname{cert}}^{\mathrm{H}}_{f,r} cert f , r H
Precomputation:
for i = 1 , … , n i = 1,\ldots,n i = 1 , … , n do
Compute the reference prediction y i y_i y i and certificate decision c i ← cert f , r ( x i ) c_i \leftarrow\operatorname{cert}_{f,r}(x_i) c i ← cert f , r ( x i )
end for
λ c a n d ← TUNE ( D n , y 1 : n , c 1 : n , m t u n e , m c e r t , α , δ , δ 0 ) \lambda_{\mathrm{cand}} \leftarrow\operatorname{TUNE}(\mathcal{D}_n,y_{1:n},c_{1:n},m_{\mathrm{tune}},m_{\mathrm{cert}},\alpha,\delta,\delta_0) λ cand ← TUNE ( D n , y 1 : n , c 1 : n , m tune , m cert , α , δ , δ 0 )
if VALIDATE ( D n , y 1 : n , c 1 : n , λ c a n d , m c e r t , α , δ ) \operatorname{VALIDATE}(\mathcal{D}_n,y_{1:n},c_{1:n},\lambda_{\mathrm{cand}},m_{\mathrm{cert}},\alpha,\delta) VALIDATE ( D n , y 1 : n , c 1 : n , λ cand , m cert , α , δ ) then
λ ∗ ← λ c a n d \lambda^* \leftarrow\lambda_{\mathrm{cand}} λ ∗ ← λ cand
else
λ ∗ ← 1 \lambda^* \leftarrow1 λ ∗ ← 1 ▹ h ^ ( ⋅ , 1 ) = 0 \triangleright\hat{h}(\cdot,1)=0 ▹ h ^ ( ⋅ , 1 ) = 0 : no certifications
end if
Deployment:
Given x ~ \tilde{x} x ~ , compute y ← y \leftarrow y ← the reference prediction at x ~ \tilde{x} x ~ (e.g. vote over 50 noisy samples)
Draw one smoothing noise ϵ ∼ ψ \epsilon\sim\psi ϵ ∼ ψ and return y y y if h ^ ( x ~ + ϵ , λ ∗ ; y ) = 1 \hat{h}(\tilde{x}+\epsilon,\lambda^*;y)=1 h ^ ( x ~ + ϵ , λ ∗ ; y ) = 1 ; otherwise abstain
return cert ^ f , r H ( x ~ ) = h ^ ( x ~ + ϵ , λ ∗ ; y ) \widehat{\operatorname{cert}}^{\mathrm{H}}_{f,r}(\tilde{x}) = \hat{h}(\tilde{x}+\epsilon,\lambda^*;y) cert f , r H ( x ~ ) = h ^ ( x ~ + ϵ , λ ∗ ; y )
samples usually reduce the conservativeness of the single-sample proxy while preserving the same marginal false-approval guarantee.
The multiple-testing issue in single-phase calibration. The probabilities used in Eq. (7) need to be estimated via MC sampling. However, using an algorithm like binary search over the same set of samples brings statistical flaw to the estimation. On the other hand, resampling and re-estimating the values at each step of the binary search is also expensive. As an alternative, we divide the computation of λ ∗ \lambda^* λ ∗ into two phases: tuning (with low sample rate), and validation with high sample rate. The theoretical guarantee is the result of the validation step, therefore we can reuse the samples while tuning.
Two-stage fix. We decouple threshold selection from threshold validation by splitting the noise budget as m t u n e + m c e r t m_{\mathrm{tune}} + m_{\mathrm{cert}} m tune + m cert . The tuning phase (Alg 4) uses m t u n e m_{\mathrm{tune}} m tune samples per calibration point to select a candidate λ c a n d \lambda_{\mathrm{cand}} λ cand by simulating the certification budget: the empirical count p ^ i t u n e ( λ ) ⋅ m c e r t \hat{p}_i^{\mathrm{tune}}(\lambda)\cdot m_{\mathrm{cert}} p ^ i tune ( λ ) ⋅ m cert is projected to scale m c e r t m_{\mathrm{cert}} m cert , a Clopper-Pearson bound is computed at that simulated count, and the smoothing upper bound is applied, all with an extra slack δ 0 \delta_0 δ 0 . The validation phase (Alg 5) then draws
Table 5. What is guaranteed by randomized smoothing (RS) and by the ProxC variants. In all cases the adversary knows the model weights, the clean input, and the procedure, and may choose any x ~ n + 1 ∈ B ( x n + 1 ) \tilde{x}_{n+1} \in\mathcal{B}(x_{n+1}) x ~ n + 1 ∈ B ( x n + 1 ) ; it does not control or observe the internal randomness (e.g. ϵ \epsilon ϵ ).
Algorithm 4 PROXC-H-TUNE: Tuning Phase for PROXC-H
Require: Precomputed ( y i , c i ) i = 1 n (y_i,c_i)_{i=1}^{n} ( y i , c i ) i = 1 n , calibration set D n \mathcal{D}_n D n , proxy h ^ \hat{h} h ^ , smoothing ψ \psi ψ , m t u n e m_{\mathrm{tune}} m tune , m c e r t m_{\mathrm{cert}} m cert , α \alpha α , δ \delta δ , tuning slack δ 0 \delta_0 δ 0
Ensure: Candidate threshold λ c a n d \lambda_{\mathrm{cand}} λ cand
for i = 1 , … , n i=1,\ldots,n i = 1 , … , n do
for j = 1 , … , m t u n e j=1,\ldots,m_{\mathrm{tune}} j = 1 , … , m tune do
Draw ϵ i , j ∼ ψ \epsilon_{i,j} \sim\psi ϵ i , j ∼ ψ ; set a i , j ( λ ) ← h ^ ( x i + ϵ i , j , λ ; y i ) a_{i,j}(\lambda) \gets\hat{h}(x_i+\epsilon_{i,j},\lambda;y_i) a i , j ( λ ) ← h ^ ( x i + ϵ i , j , λ ; y i )
end for
p ^ i t u n e ( λ ) ← m t u n e − 1 ∑ j = 1 m t u n e a i , j ( λ ) \hat{p}^{\mathrm{tune}}_i(\lambda) \gets m_{\mathrm{tune}}^{-1}\sum_{j=1}^{m_{\mathrm{tune}}} a_{i,j}(\lambda) p ^ i tune ( λ ) ← m tune − 1 ∑ j = 1 m tune a i , j ( λ )
k i s i m ( λ ) ← ⌊ p ^ i t u n e ( λ ) ⋅ m c e r t ⌋ k_i^{\mathrm{sim}}(\lambda) \gets\lfloor\hat{p}^{\mathrm{tune}}_i(\lambda)\cdot m_{\mathrm{cert}}\rfloor k i sim ( λ ) ← ⌊ p ^ i tune ( λ ) ⋅ m cert ⌋
p ˉ i s i m ( λ ) ← CP ↑ ( k i s i m ( λ ) , m c e r t , 1 − δ / n ) \bar{p}_i^{\mathrm{sim}}(\lambda) \gets\operatorname{CP}^{\uparrow}(k_i^{\mathrm{sim}}(\lambda),m_{\mathrm{cert}},1-\delta/n) p ˉ i sim ( λ ) ← CP ↑ ( k i sim ( λ ) , m cert , 1 − δ / n )
R i s i m ( λ ) ← ( 1 − c i ) c ↑ ( p ˉ i s i m ( λ ) , B ( x i ) ) R_i^{\mathrm{sim}}(\lambda) \gets(1-c_i)c^{\uparrow}(\bar{p}_i^{\mathrm{sim}}(\lambda),\mathcal{B}(x_i)) R i sim ( λ ) ← ( 1 − c i ) c ↑ ( p ˉ i sim ( λ ) , B ( x i ))
end for
R ˉ n s i m ( λ ) ← 1 + ∑ i = 1 n R i s i m ( λ ) n + 1 \bar{R}_n^{\mathrm{sim}}(\lambda) \gets\dfrac{1+\sum_{i=1}^{n}R_i^{\mathrm{sim}}(\lambda)}{n+1} R ˉ n sim ( λ ) ← n + 1 1 + ∑ i = 1 n R i sim ( λ )
return λ c a n d ← inf { λ : R ˉ n s i m ( λ ) ≤ α − δ − δ 0 } \lambda_{\mathrm{cand}} \gets\inf\{\lambda:\bar{R}_n^{\mathrm{sim}}(\lambda)\leq\alpha-\delta-\delta_0\} λ cand ← inf { λ : R ˉ n sim ( λ ) ≤ α − δ − δ 0 }
m c e r t m_{\mathrm{cert}} m cert independent noise samples at the fixed threshold λ c a n d \lambda_{\mathrm{cand}} λ cand . Because λ c a n d \lambda_{\mathrm{cand}} λ cand is determined before the validation samples are drawn, the CP bounds in the validation phase are valid for the specific threshold λ c a n d \lambda_{\mathrm{cand}} λ cand without any selection correction. Note that both phases reuse the same calibration inputs x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n . This is not a source of selection bias; only reusing the same Monte Carlo noise to both select and validate λ c a n d \lambda_{\mathrm{cand}} λ cand would be. Splitting the calibration points into tuning and validation sets is therefore unnecessary, and would only reduce the effective calibration size.
Formal validity.
Proposition 4. Let λ ∗ \lambda^* λ ∗ be the output of Alg 3, i.e. λ ∗ = λ c a n d \lambda^*=\lambda_{\mathrm{cand}} λ ∗ = λ cand if the validation check in Alg 5 passes and λ ∗ = 1 \lambda^*=1 λ ∗ = 1 otherwise, and suppose the validation noise is drawn independently of the tuning noise. Then
E [ ( 1 − c ( x n + 1 ) ) c ↑ ( p ( x n + 1 , λ ∗ ) , B ) ] ≤ α , \mathbb{E}\left[(1-c(x_{n+1}))c^{\uparrow}(p(x_{n+1},\lambda^*),\mathcal{B})\right]\leq\alpha, E [ ( 1 − c ( x n + 1 )) c ↑ ( p ( x n + 1 , λ ∗ ) , B ) ] ≤ α , where p ( x , λ ) = Pr ϵ [ h ^ ( x + ϵ , λ ) = 1 ] p(x,\lambda)=\Pr_{\epsilon}[\hat{h}(x+\epsilon,\lambda)=1] p ( x , λ ) = Pr ϵ [ h ^ ( x + ϵ , λ ) = 1 ] , c ( x ) = cert f , r ( x ) c(x)=\operatorname{cert}_{f,r}(x) c ( x ) = cert f , r ( x ) , and the expectation is over the calibration set, the test point, and the tuning and validation noise.
Proof. Let R ∘ ( x , λ ) = ( 1 − c ( x ) ) c ↑ ( p ( x , λ ) , B ) R^{\circ}(x,\lambda)=(1-c(x))c^{\uparrow}(p(x,\lambda),\mathcal{B}) R ∘ ( x , λ ) = ( 1 − c ( x )) c ↑ ( p ( x , λ ) , B ) be the exact (infinite-MC) risk. It is bounded in [ 0 , 1 ] [0,1] [ 0 , 1 ] , non-increasing in λ \lambda λ (since p p p is non-increasing in λ \lambda λ and c ↑ c^{\uparrow} c ↑ is non-decreasing in its first argument), and R ∘ ( ⋅ , 1 ) = 0 R^{\circ}(\cdot,1)=0 R ∘ ( ⋅ , 1 ) = 0 . The backbone decisions c i c_i c i (computed with their own independent MC noise per point) are treated as part of the exchangeable calibration data.
Oracle step. Consider first an oracle procedure that knows p p p exactly and targets α − δ \alpha-\delta α − δ :
λ o r = inf { λ : 1 + ∑ i = 1 n R ∘ ( x i , λ ) n + 1 ≤ α − δ } . \lambda_{\mathrm{or}}=\inf\left\{\lambda:\frac{1+\sum_{i=1}^{n}R^{\circ}(x_i,\lambda)}{n+1}\leq\alpha-\delta\right\}. λ or = inf { λ : n + 1 1 + ∑ i = 1 n R ∘ ( x i , λ ) ≤ α − δ } .
@page 16/35 starts_mid=0 ends_mid=0
Table 5 (PDF p. 16). What is guaranteed by randomized smoothing (RS) and by the ProxC variants. In all cases the adversary knows the model weights, the clean input, and the procedure, and may choose any x ~ n + 1 ∈ B ( x n + 1 ) \tilde{x}_{n+1} \in\mathcal{B}(x_{n+1}) x ~ n + 1 ∈ B ( x n + 1 ) ; it does not control or observe the internal randomness (e.g. ϵ \epsilon ϵ ).
Algorithm 4 PROXC-H-TUNE: Tuning Phase for PROXC-H
Require: Precomputed ( y i , c i ) i = 1 n (y_i,c_i)_{i=1}^{n} ( y i , c i ) i = 1 n , calibration set D n \mathcal{D}_n D n , proxy h ^ \hat{h} h ^ , smoothing ψ \psi ψ , m t u n e m_{\mathrm{tune}} m tune , m c e r t m_{\mathrm{cert}} m cert , α \alpha α , δ \delta δ , tuning slack δ 0 \delta_0 δ 0
Ensure: Candidate threshold λ c a n d \lambda_{\mathrm{cand}} λ cand
for i = 1 , … , n i=1,\ldots,n i = 1 , … , n do
for j = 1 , … , m t u n e j=1,\ldots,m_{\mathrm{tune}} j = 1 , … , m tune do
Draw ϵ i , j ∼ ψ \epsilon_{i,j} \sim\psi ϵ i , j ∼ ψ ; set a i , j ( λ ) ← h ^ ( x i + ϵ i , j , λ ; y i ) a_{i,j}(\lambda) \gets\hat{h}(x_i+\epsilon_{i,j},\lambda;y_i) a i , j ( λ ) ← h ^ ( x i + ϵ i , j , λ ; y i )
end for
p ^ i t u n e ( λ ) ← m t u n e − 1 ∑ j = 1 m t u n e a i , j ( λ ) \hat{p}^{\mathrm{tune}}_i(\lambda) \gets m_{\mathrm{tune}}^{-1}\sum_{j=1}^{m_{\mathrm{tune}}} a_{i,j}(\lambda) p ^ i tune ( λ ) ← m tune − 1 ∑ j = 1 m tune a i , j ( λ )
k i s i m ( λ ) ← ⌊ p ^ i t u n e ( λ ) ⋅ m c e r t ⌋ k_i^{\mathrm{sim}}(\lambda) \gets\lfloor\hat{p}^{\mathrm{tune}}_i(\lambda)\cdot m_{\mathrm{cert}}\rfloor k i sim ( λ ) ← ⌊ p ^ i tune ( λ ) ⋅ m cert ⌋
p ˉ i s i m ( λ ) ← CP ↑ ( k i s i m ( λ ) , m c e r t , 1 − δ / n ) \bar{p}_i^{\mathrm{sim}}(\lambda) \gets\operatorname{CP}^{\uparrow}(k_i^{\mathrm{sim}}(\lambda),m_{\mathrm{cert}},1-\delta/n) p ˉ i sim ( λ ) ← CP ↑ ( k i sim ( λ ) , m cert , 1 − δ / n )
R i s i m ( λ ) ← ( 1 − c i ) c ↑ ( p ˉ i s i m ( λ ) , B ( x i ) ) R_i^{\mathrm{sim}}(\lambda) \gets(1-c_i)c^{\uparrow}(\bar{p}_i^{\mathrm{sim}}(\lambda),\mathcal{B}(x_i)) R i sim ( λ ) ← ( 1 − c i ) c ↑ ( p ˉ i sim ( λ ) , B ( x i ))
end for
R ˉ n s i m ( λ ) ← 1 + ∑ i = 1 n R i s i m ( λ ) n + 1 \bar{R}_n^{\mathrm{sim}}(\lambda) \gets\dfrac{1+\sum_{i=1}^{n}R_i^{\mathrm{sim}}(\lambda)}{n+1} R ˉ n sim ( λ ) ← n + 1 1 + ∑ i = 1 n R i sim ( λ )
return λ c a n d ← inf { λ : R ˉ n s i m ( λ ) ≤ α − δ − δ 0 } \lambda_{\mathrm{cand}} \gets\inf\{\lambda:\bar{R}_n^{\mathrm{sim}}(\lambda)\leq\alpha-\delta-\delta_0\} λ cand ← inf { λ : R ˉ n sim ( λ ) ≤ α − δ − δ 0 }
m c e r t m_{\mathrm{cert}} m cert independent noise samples at the fixed threshold λ c a n d \lambda_{\mathrm{cand}} λ cand . Because λ c a n d \lambda_{\mathrm{cand}} λ cand is determined before the validation samples are drawn, the CP bounds in the validation phase are valid for the specific threshold λ c a n d \lambda_{\mathrm{cand}} λ cand without any selection correction. Note that both phases reuse the same calibration inputs x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n . This is not a source of selection bias; only reusing the same Monte Carlo noise to both select and validate λ c a n d \lambda_{\mathrm{cand}} λ cand would be. Splitting the calibration points into tuning and validation sets is therefore unnecessary, and would only reduce the effective calibration size.
Formal validity.
Proposition 4. Let λ ∗ \lambda^* λ ∗ be the output of Alg 3, i.e. λ ∗ = λ c a n d \lambda^*=\lambda_{\mathrm{cand}} λ ∗ = λ cand if the validation check in Alg 5 passes and λ ∗ = 1 \lambda^*=1 λ ∗ = 1 otherwise, and suppose the validation noise is drawn independently of the tuning noise. Then
E [ ( 1 − c ( x n + 1 ) ) c ↑ ( p ( x n + 1 , λ ∗ ) , B ) ] ≤ α , \mathbb{E}\left[(1-c(x_{n+1}))c^{\uparrow}(p(x_{n+1},\lambda^*),\mathcal{B})\right]\leq\alpha, E [ ( 1 − c ( x n + 1 )) c ↑ ( p ( x n + 1 , λ ∗ ) , B ) ] ≤ α , where p ( x , λ ) = Pr ϵ [ h ^ ( x + ϵ , λ ) = 1 ] p(x,\lambda)=\Pr_{\epsilon}[\hat{h}(x+\epsilon,\lambda)=1] p ( x , λ ) = Pr ϵ [ h ^ ( x + ϵ , λ ) = 1 ] , c ( x ) = cert f , r ( x ) c(x)=\operatorname{cert}_{f,r}(x) c ( x ) = cert f , r ( x ) , and the expectation is over the calibration set, the test point, and the tuning and validation noise.
Proof. Let R ∘ ( x , λ ) = ( 1 − c ( x ) ) c ↑ ( p ( x , λ ) , B ) R^{\circ}(x,\lambda)=(1-c(x))c^{\uparrow}(p(x,\lambda),\mathcal{B}) R ∘ ( x , λ ) = ( 1 − c ( x )) c ↑ ( p ( x , λ ) , B ) be the exact (infinite-MC) risk. It is bounded in [ 0 , 1 ] [0,1] [ 0 , 1 ] , non-increasing in λ \lambda λ (since p p p is non-increasing in λ \lambda λ and c ↑ c^{\uparrow} c ↑ is non-decreasing in its first argument), and R ∘ ( ⋅ , 1 ) = 0 R^{\circ}(\cdot,1)=0 R ∘ ( ⋅ , 1 ) = 0 . The backbone decisions c i c_i c i (computed with their own independent MC noise per point) are treated as part of the exchangeable calibration data.
Oracle step. Consider first an oracle procedure that knows p p p exactly and targets α − δ \alpha-\delta α − δ :
λ o r = inf { λ : 1 + ∑ i = 1 n R ∘ ( x i , λ ) n + 1 ≤ α − δ } . \lambda_{\mathrm{or}}=\inf\left\{\lambda:\frac{1+\sum_{i=1}^{n}R^{\circ}(x_i,\lambda)}{n+1}\leq\alpha-\delta\right\}. λ or = inf { λ : n + 1 1 + ∑ i = 1 n R ∘ ( x i , λ ) ≤ α − δ } .
Algorithm 5 PROXC-H-VALIDATE: Validation Phase for PROXC-H
Require: Precomputed ( y i , c i ) i = 1 n (y_i,c_i)_{i=1}^{n} ( y i , c i ) i = 1 n , calibration set D n \mathcal{D}_n D n , proxy h ^ \hat{h} h ^ , smoothing ψ \psi ψ , fixed threshold λ c a n d \lambda_{\mathrm{cand}} λ cand , m c e r t m_{\mathrm{cert}} m cert , α \alpha α , δ \delta δ
Ensure: Boolean: True iff the CRC condition holds at λ c a n d \lambda_{\mathrm{cand}} λ cand
1: for i = 1 , … , n i=1,\ldots,n i = 1 , … , n do 2: for j = 1 , … , m c e r t j=1,\ldots,m_{\mathrm{cert}} j = 1 , … , m cert do 3: Draw ϵ i , j c e r t ∼ ψ \epsilon^{\mathrm{cert}}_{i,j}\sim\psi ϵ i , j cert ∼ ψ ; set a i , j c e r t ← h ^ ( x i + ϵ i , j c e r t , λ c a n d ; y i ) a^{\mathrm{cert}}_{i,j}\leftarrow\hat{h}(x_i+\epsilon^{\mathrm{cert}}_{i,j},\lambda_{\mathrm{cand}};y_i) a i , j cert ← h ^ ( x i + ϵ i , j cert , λ cand ; y i ) 4: end for 5: k i c e r t ← ∑ j = 1 m c e r t a i , j c e r t k^{\mathrm{cert}}_i\leftarrow\sum_{j=1}^{m_{\mathrm{cert}}}a^{\mathrm{cert}}_{i,j} k i cert ← ∑ j = 1 m cert a i , j cert 6: p ˉ i c e r t ← CP ↑ ( k i c e r t , m c e r t , 1 − δ / n ) \bar{p}^{\mathrm{cert}}_i\leftarrow\operatorname{CP}^{\uparrow}(k^{\mathrm{cert}}_i,m_{\mathrm{cert}},1-\delta/n) p ˉ i cert ← CP ↑ ( k i cert , m cert , 1 − δ / n ) 7: R i c e r t ← ( 1 − c i ) c ↑ ( p ˉ i c e r t , B ( x i ) ) R^{\mathrm{cert}}_i\leftarrow(1-c_i)c^{\uparrow}(\bar{p}^{\mathrm{cert}}_i,\mathcal{B}(x_i)) R i cert ← ( 1 − c i ) c ↑ ( p ˉ i cert , B ( x i )) 8: end for 9: R ˉ n c e r t ( λ c a n d ) ← 1 + ∑ i = 1 n R i c e r t n + 1 \bar{R}^{\mathrm{cert}}_n(\lambda_{\mathrm{cand}})\leftarrow\frac{1+\sum_{i=1}^{n}R^{\mathrm{cert}}_i}{n+1} R ˉ n cert ( λ cand ) ← n + 1 1 + ∑ i = 1 n R i cert 10: return [ R ˉ n c e r t ( λ c a n d ) ≤ α − δ ] \left[\bar{R}^{\mathrm{cert}}_n(\lambda_{\mathrm{cand}})\le\alpha-\delta\right] [ R ˉ n cert ( λ cand ) ≤ α − δ ]
with the convention λ o r = 1 \lambda_{\mathrm{or}}=1 λ or = 1 if the set is empty. Since R ∘ R^{\circ} R ∘ is bounded and non-increasing in λ \lambda λ , the standard CRC argument [1 ] gives
E [ R ∘ ( x n + 1 , λ o r ) ] ≤ α − δ . \mathbb{E}[R^{\circ}(x_{n+1},\lambda_{\mathrm{or}})]\le\alpha-\delta. E [ R ∘ ( x n + 1 , λ or )] ≤ α − δ .
Importantly, CRC is applied only to this canonical oracle threshold. In the next steps we show that, for any calibration set, the implemented threshold is at least as conservative as λ o r \lambda_{\mathrm{or}} λ or except on an event of probability at most δ \delta δ .
Tuning and validation. Let λ c a n d = g ( x 1 : n , ξ 0 ) \lambda_{\mathrm{cand}}=g(x_{1:n},\xi_0) λ cand = g ( x 1 : n , ξ 0 ) be the output of the tuning phase, where ξ 0 \xi_0 ξ 0 denotes the tuning noise. During validation we draw fresh noise ξ 1 \xi_1 ξ 1 , independent of ξ 0 \xi_0 ξ 0 . Conditional on the calibration inputs and on ξ 0 \xi_0 ξ 0 , the threshold λ c a n d \lambda_{\mathrm{cand}} λ cand is fixed relative to ξ 1 \xi_1 ξ 1 , and for each i i i the count k i c e r t k^{\mathrm{cert}}_i k i cert is Binomial ( m c e r t , p ( x i , λ c a n d ) ) \operatorname{Binomial}(m_{\mathrm{cert}},p(x_i,\lambda_{\mathrm{cand}})) Binomial ( m cert , p ( x i , λ cand )) . Therefore the Clopper-Pearson bounds are valid binomial bounds at one fixed threshold, i.e. p ˉ i c e r t ≥ p ( x i , λ c a n d ) \bar{p}^{\mathrm{cert}}_i\ge p(x_i,\lambda_{\mathrm{cand}}) p ˉ i cert ≥ p ( x i , λ cand ) with probability at least 1 − δ / n 1-\delta/n 1 − δ / n , and no simultaneous confidence band over all λ \lambda λ is needed.
Union bound. Let E = { p ˉ i c e r t ≥ p ( x i , λ c a n d ) for every i } \mathcal{E}=\{\bar{p}^{\mathrm{cert}}_i\ge p(x_i,\lambda_{\mathrm{cand}})\text{ for every }i\} E = { p ˉ i cert ≥ p ( x i , λ cand ) for every i } . By the union bound over the n n n calibration points, Pr ( E c ) ≤ δ \Pr(\mathcal{E}^{c})\le\delta Pr ( E c ) ≤ δ . Since c ↑ c^{\uparrow} c ↑ is non-decreasing in its first argument, on E \mathcal{E} E the validation risks upper-bound the corresponding oracle risks, R i c e r t = ( 1 − c i ) c ↑ ( p ˉ i c e r t , B ) ≥ R ∘ ( x i , λ c a n d ) R^{\mathrm{cert}}_i=(1-c_i)c^{\uparrow}(\bar{p}^{\mathrm{cert}}_i,\mathcal{B})\ge R^{\circ}(x_i,\lambda_{\mathrm{cand}}) R i cert = ( 1 − c i ) c ↑ ( p ˉ i cert , B ) ≥ R ∘ ( x i , λ cand ) for every i i i . Consequently, on E \mathcal{E} E , if the validation passes,
1 + ∑ i = 1 n R ∘ ( x i , λ c a n d ) n + 1 ≤ 1 + ∑ i = 1 n R i c e r t n + 1 ≤ α − δ , \frac{1+\sum_{i=1}^{n}R^{\circ}(x_i,\lambda_{\mathrm{cand}})}{n+1}
\le
\frac{1+\sum_{i=1}^{n}R^{\mathrm{cert}}_i}{n+1}
\le\alpha-\delta, n + 1 1 + ∑ i = 1 n R ∘ ( x i , λ cand ) ≤ n + 1 1 + ∑ i = 1 n R i cert ≤ α − δ ,
so λ c a n d \lambda_{\mathrm{cand}} λ cand is feasible for the oracle constraint and, by the definition of λ o r \lambda_{\mathrm{or}} λ or , λ ∗ = λ c a n d ≥ λ o r \lambda^*=\lambda_{\mathrm{cand}}\ge\lambda_{\mathrm{or}} λ ∗ = λ cand ≥ λ or . If the validation fails, λ ∗ = 1 ≥ λ o r \lambda^*=1\ge\lambda_{\mathrm{or}} λ ∗ = 1 ≥ λ or . In both cases, by monotonicity, R ∘ ( x n + 1 , λ ∗ ) ≤ R ∘ ( x n + 1 , λ o r ) R^{\circ}(x_{n+1},\lambda^*)\le R^{\circ}(x_{n+1},\lambda_{\mathrm{or}}) R ∘ ( x n + 1 , λ ∗ ) ≤ R ∘ ( x n + 1 , λ or ) on E \mathcal{E} E .
Conclusion. Since R ∘ ≤ 1 R^{\circ}\le1 R ∘ ≤ 1 , we have R ∘ ( x n + 1 , λ ∗ ) ≤ R ∘ ( x n + 1 , λ o r ) + I { E c } R^{\circ}(x_{n+1},\lambda^*)\le R^{\circ}(x_{n+1},\lambda_{\mathrm{or}})+\mathbb{I}\{\mathcal{E}^{c}\} R ∘ ( x n + 1 , λ ∗ ) ≤ R ∘ ( x n + 1 , λ or ) + I { E c } , and therefore
E [ R ∘ ( x n + 1 , λ ∗ ) ] ≤ E [ R ∘ ( x n + 1 , λ o r ) ] + Pr ( E c ) ≤ ( α − δ ) + δ = α . \mathbb{E}[R^{\circ}(x_{n+1},\lambda^*)]\le\mathbb{E}[R^{\circ}(x_{n+1},\lambda_{\mathrm{or}})]+\Pr(\mathcal{E}^{c})\le(\alpha-\delta)+\delta=\alpha. E [ R ∘ ( x n + 1 , λ ∗ )] ≤ E [ R ∘ ( x n + 1 , λ or )] + Pr ( E c ) ≤ ( α − δ ) + δ = α .
Combined with the randomized-smoothing bound and the soundness of the backbone certificate (as in the proof of Prop. 2 ), this yields the false-approval guarantee of Eq. (5) for ProxC-H. Note that the Monte Carlo validation is not used to apply CRC directly to an adaptively selected empirical risk; it certifies that the selected threshold is at least as conservative as the exact oracle CRC threshold, except on the validation-failure event whose probability is budgeted by δ \delta δ (the same δ \delta δ by which the CRC target is lowered to α − δ \alpha-\delta α − δ ). The slack δ 0 \delta_0 δ 0 only affects how often the validation passes, not the validity. As for all our results, the guarantee is in expectation over the calibration set, the test point, and the method’s randomness: if R ( D ′ ) R(\mathcal{D}') R ( D ′ ) denotes the expected test risk conditional on a fixed calibration set D ′ \mathcal{D}' D ′ , we have E D ′ [ R ( D ′ ) ] ≤ α \mathbb{E}_{\mathcal{D}'}[R(\mathcal{D}')]\le\alpha E D ′ [ R ( D ′ )] ≤ α , while R ( D ′ ) R(\mathcal{D}') R ( D ′ ) itself can vary across calibration sets. When the validation check fails, λ ∗ = 1 \lambda^*=1 λ ∗ = 1 and no certifications are issued; this branch is already accounted for in the proof above. Repeating the validation with fresh noise after a failure would require splitting $\delta across the attempts. To avoid such failure we use the slack variable δ 0 \delta_0 δ 0 to stay on the safe side. Note that the inf in Eq. 4 is to find the most efficient parameter, however for any λ > λ ∗ \lambda> \lambda^* λ > λ ∗ still the risk remains below the desired α \alpha α . This is due to the monotonicity of the risk. Therefore, finding in any form and then validating it via Alg 5 does not introduce any flaw in the framework.
Introduction to Randomized Smoothing
Some of our theoretical results rely on the structure of randomized smoothing. For completeness, and to fix notation, we therefore present a self-contained formulation of randomized smoothing.
Let X ⊆ R d \mathcal{X} \subseteq\mathbb{R}^d X ⊆ R d be the input space and let Y = { 1 , … , K } \mathcal{Y} = \{1,\ldots,K\} Y = { 1 , … , K } be the label space. For a classifier f : X → Y f:\mathcal{X}\to\mathcal{Y} f : X → Y and a perturbation set B ( x ) \mathcal{B}(x) B ( x ) , pointwise adversarial robustness requires f ( x ~ ) = f ( x ) f(\tilde{x}) = f(x) f ( x ~ ) = f ( x ) for all x ~ ∈ B ( x ) \tilde{x} \in\mathcal{B}(x) x ~ ∈ B ( x ) . It is convenient to reduce the K K K -class problem to a binary one. Fix a predicted class y ∗ y^* y ∗ via some inference rule (e.g. majority vote over m m m noisy evaluations of f f f ), and define the binary acceptance indicator f ⊤ ( x ) = 1 [ f ( x ) = y ∗ ] f^{\top}(x) = \mathbb{1}[f(x) = y^*] f ⊤ ( x ) = 1 [ f ( x ) = y ∗ ] . Let f ˉ ⊤ ( x ) = Pr ϵ [ f ( x + ϵ ) = y ∗ ] \bar{f}^{\top}(x) = \Pr_{\epsilon}[f(x+\epsilon)=y^*] f ˉ ⊤ ( x ) = Pr ϵ [ f ( x + ϵ ) = y ∗ ] be its smoothed version. Robustness of the prediction y ∗ y^* y ∗ at radius r r r is then equivalent to min x ~ ∈ B r ( x ) f ⊤ ( x ~ ) ≥ 1 / 2 \min_{\tilde{x}\in B_r(x)} f^{\top}(\tilde{x}) \ge1/2 min x ~ ∈ B r ( x ) f ⊤ ( x ~ ) ≥ 1/2 , a condition the smoothing certificate can lower-bound in closed form.
More formally, if ℓ : Y × Y → { 0 , 1 } \ell:\mathcal{Y}\times\mathcal{Y}\to\{0,1\} ℓ : Y × Y → { 0 , 1 } denotes the zero-one loss, the worst-case robust error of f f f at ( x , y ) (x,y) ( x , y ) is sup x ~ ∈ B ( x ) ℓ ( f ( x ~ ) , y ) \sup_{\tilde{x}\in\mathcal{B}(x)}\ell(f(\tilde{x}),y) sup x ~ ∈ B ( x ) ℓ ( f ( x ~ ) , y ) . The ideal robust classifier minimizes the expected worst-case error:
f r o b ∗ ∈ arg min f : X → Y E ( x , y ) ∼ D [ sup x ~ ∈ B ( x ) ℓ ( f ( x ~ ) , y ) ] . f^*_{\mathrm{rob}} \in\arg\min_{f:\mathcal{X}\to\mathcal{Y}} \mathbb{E}_{(x,y)\sim\mathcal{D}}\left[\sup_{\tilde{x}\in\mathcal{B}(x)}\ell(f(\tilde{x}),y)\right]. f rob ∗ ∈ arg f : X → Y min E ( x , y ) ∼ D [ x ~ ∈ B ( x ) sup ℓ ( f ( x ~ ) , y ) ] .
This objective is the natural formalization of robustness, but it is computationally intractable for modern neural networks: the inner maximization ranges over a continuous, high-dimensional perturbation set, while the outer minimization ranges over a non-convex class of classifiers.
Randomized smoothing replaces the deterministic classifier with a noise-averaged one. Let ψ \psi ψ be a smoothing distribution over perturbations ϵ ∈ R d \epsilon\in\mathbb{R}^d ϵ ∈ R d , and define the smoothed class probabilities
p y ( x ) : = Pr ϵ ∼ ψ [ f ( x + ϵ ) = y ] , y ∈ Y . p_y(x) := \Pr_{\epsilon\sim\psi}[f(x+\epsilon)=y], \qquad y\in\mathcal{Y}. p y ( x ) := ϵ ∼ ψ Pr [ f ( x + ϵ ) = y ] , y ∈ Y .
The associated smoothed classifier is g ( x ) : = arg max y ∈ Y p y ( x ) g(x):=\arg\max_{y\in\mathcal{Y}}p_y(x) g ( x ) := arg max y ∈ Y p y ( x ) ; it predicts the class most frequently returned by the base classifier under random perturbations of the input. For Gaussian smoothing ϵ ∼ N ( 0 , σ 2 I ) \epsilon\sim\mathcal{N}(0,\sigma^2 I) ϵ ∼ N ( 0 , σ 2 I ) , the smoothed classifier admits a closed-form ℓ 2 \ell_2 ℓ 2 robustness certificate [11 ] . Let
y A = arg max y ∈ Y p y ( x ) , p A = p y A ( x ) , p B = max y ≠ y A p y ( x ) . y_A = \arg\max_{y\in\mathcal{Y}} p_y(x), \qquad p_A=p_{y_A}(x), \qquad p_B=\max_{y\ne y_A}p_y(x). y A = arg y ∈ Y max p y ( x ) , p A = p y A ( x ) , p B = y = y A max p y ( x ) .
If p A > p B p_A>p_B p A > p B , then the prediction of g g g is invariant inside the ℓ 2 \ell_2 ℓ 2 ball of radius
r ∗ = σ 2 ( Φ − 1 ( p A ) − Φ − 1 ( p B ) ) . r^*=\frac{\sigma}{2}\left(\Phi^{-1}(p_A)-\Phi^{-1}(p_B)\right). r ∗ = 2 σ ( Φ − 1 ( p A ) − Φ − 1 ( p B ) ) .
where Φ \Phi Φ denotes the standard Gaussian CDF. Hence randomized smoothing converts probabilistic class separation under Gaussian noise into a deterministic robustness guarantee over an ℓ 2 \ell_2 ℓ 2 ball.
More generally, randomized smoothing certifies expectations of bounded functions under the distribution shift induced by adversarial perturbations. For any measurable function h : X → [ 0 , 1 ] h:\mathcal{X}\to[0,1] h : X → [ 0 , 1 ] , define its smoothed value
h ˉ ( x ) : = E ϵ ∼ ψ [ h ( x + ϵ ) ] . \bar{h}(x):=\mathbb{E}_{\epsilon\sim\psi}[h(x+\epsilon)]. h ˉ ( x ) := E ϵ ∼ ψ [ h ( x + ϵ )] .
A smoothing certificate provides deterministic functions c ↓ ( ⋅ , B − 1 ) c^{\downarrow}(\cdot,\mathcal{B}^{-1}) c ↓ ( ⋅ , B − 1 ) and c ↑ ( ⋅ , B ) c^{\uparrow}(\cdot,\mathcal{B}) c ↑ ( ⋅ , B ) such that, for all x ~ ∈ B ( x ) \tilde{x}\in\mathcal{B}(x) x ~ ∈ B ( x ) ,
h ˉ ( x ~ ) ≤ c ↑ ( h ( x ) , B ) , h ˉ ( x ) ≤ c ↓ ( h ( x ~ ) , B − 1 ) . \bar{h}(\tilde{x})\le c^{\uparrow}(h(x),\mathcal{B}), \qquad\bar{h}(x)\le c^{\downarrow}(h(\tilde{x}),\mathcal{B}^{-1}). h ˉ ( x ~ ) ≤ c ↑ ( h ( x ) , B ) , h ˉ ( x ) ≤ c ↓ ( h ( x ~ ) , B − 1 ) .
These inequalities say that the smoothed value at any perturbed point is bounded above by a function of the smoothed value at the clean point, and vice versa.
Optimization formulation. The bound c ↑ ( p , B ) c^{\uparrow}(p,\mathcal{B}) c ↑ ( p , B ) is defined as the solution of a functional optimization problem: given that the smoothed value at the clean point equals p p p , what is the largest possible smoothed value the same function can achieve at any perturbed point?
c ↑ ( p , B ) = sup h : X → [ 0 , 1 ] x ~ ∈ B ( x ) h ˉ ( x ~ ) subject to h ˉ ( x ) = p . (9) c^{\uparrow}(p,\mathcal{B})=\sup_{\substack{h:\mathcal{X}\to[0,1]\\ \widetilde{x}\in\mathcal{B}(x)}}\ \bar{h}(\widetilde{x})\quad\text{subject to}\quad\bar{h}(x)=p. \tag*{(9)} c ↑ ( p , B ) = h : X → [ 0 , 1 ] x ∈ B ( x ) sup h ˉ ( x ) subject to h ˉ ( x ) = p . (9)
This is an infinite-dimensional linear program in h h h . By the Neyman–Pearson lemma, the optimizer is a threshold function on the likelihood ratio of the two noise-shifted distributions:
h ⋆ ( z ) = 1 [ q x ~ ( z ) q x ( z ) ≥ τ ] , h^{\star}(z)=\mathbf{1}\left[\frac{q_{\widetilde{x}}(z)}{q_x(z)}\geq\tau\right], h ⋆ ( z ) = 1 [ q x ( z ) q x ( z ) ≥ τ ] ,
where q x q_x q x and q x ~ q_{\widetilde{x}} q x are the densities of x + ϵ x+\epsilon x + ϵ and x ~ + ϵ \widetilde{x}+\epsilon x + ϵ respectively, and τ ≥ 0 \tau\geq0 τ ≥ 0 is chosen so that h ˉ ⋆ ( x ) = p \bar{h}^{\star}(x)=p h ˉ ⋆ ( x ) = p . Geometrically, h ⋆ h^{\star} h ⋆ accepts precisely the half-space where the noise-shifted distribution is more likely to have originated from x ~ \widetilde{x} x than from x x x .
Function independence. A consequence of the Neyman–Pearson characterization is that c ↑ ( p , B ) c^{\uparrow}(p,\mathcal{B}) c ↑ ( p , B ) depends on h h h only through p = h ˉ ( x ) p=\bar{h}(x) p = h ˉ ( x ) : any two functions with the same smoothed value at x x x share the same worst-case upper bound. In particular, the bound does not depend on the architecture of f f f , the specific input x x x , or any internal structure of the model — only on the scalar p p p , the noise level σ \sigma σ , and the perturbation radius r r r . This is the model-agnostic (“black-box”) property that makes randomized smoothing applicable without modification to any classifier, and that justifies writing c ↑ ( p , B ) c^{\uparrow}(p,\mathcal{B}) c ↑ ( p , B ) as a function of p p p alone.
For Gaussian smoothing ϵ ∼ N ( 0 , σ 2 I ) \epsilon\sim\mathcal{N}(0,\sigma^{2}I) ϵ ∼ N ( 0 , σ 2 I ) , the likelihood ratio between x ~ + ϵ \widetilde{x}+\epsilon x + ϵ and x + ϵ x+\epsilon x + ϵ is a function of the scalar projection ( z − x ) ⊤ ( x ~ − x ) / ∥ x ~ − x ∥ 2 (z-x)^{\top}(\widetilde{x}-x)/\lVert\widetilde{x}-x\rVert_{2} ( z − x ) ⊤ ( x − x ) / ∥ x − x ∥ 2 , which is univariate Gaussian under both distributions. The half-space threshold then integrates to a Gaussian CDF:
c ↑ ( p , B ) = Φ ( Φ − 1 ( p ) + r σ ) , c ↓ ( p , B − 1 ) = Φ ( Φ − 1 ( p ) − r σ ) , c^{\uparrow}(p,\mathcal{B})=\Phi\left(\Phi^{-1}(p)+\frac{r}{\sigma}\right),\qquad c^{\downarrow}(p,\mathcal{B}^{-1})=\Phi\left(\Phi^{-1}(p)-\frac{r}{\sigma}\right), c ↑ ( p , B ) = Φ ( Φ − 1 ( p ) + σ r ) , c ↓ ( p , B − 1 ) = Φ ( Φ − 1 ( p ) − σ r ) ,
where r = ∥ x ~ − x ∥ 2 r=\lVert\widetilde{x}-x\rVert_{2} r = ∥ x − x ∥ 2 and Φ \Phi Φ is the standard Gaussian CDF. The worst-case perturbation direction is irrelevant: only the radius r r r enters. Note that c ↑ ( c ↓ ( p , B − 1 ) , B ) = p c^{\uparrow}(c^{\downarrow}(p,\mathcal{B}^{-1}),\mathcal{B})=p c ↑ ( c ↓ ( p , B − 1 ) , B ) = p , a property used crucially in the proof of Prop. 1.
In practice, the probabilities p y ( x ) p_y(x) p y ( x ) and smoothed expectations h ˉ ( x ) \bar{h}(x) h ˉ ( x ) are not available in closed form. They are estimated by Monte Carlo:
ϵ 1 , … , ϵ m ∼ i i d ψ , p ^ y ( x ) = 1 m ∑ j = 1 m 1 { f ( x + ϵ j ) = y } . \epsilon_1,\ldots,\epsilon_m\overset{\mathrm{iid}}{\sim}\psi,\qquad\widehat{p}_y(x)=\frac{1}{m}\sum_{j=1}^{m}\mathbf{1}\{f(x+\epsilon_j)=y\}. ϵ 1 , … , ϵ m ∼ iid ψ , p y ( x ) = m 1 j = 1 ∑ m 1 { f ( x + ϵ j ) = y } .
Finite-sample certificates replace the exact probabilities with high-confidence lower bounds (e.g. Clopper–Pearson intervals). This statistical correction is essential: without it, the certificate is only asymptotically valid and may overestimate the certified radius at finite sample budgets. This sampling requirement—thousands of forward passes per input—is the primary computational bottleneck that motivates the proxy framework of the present paper.
Proofs
Proposition 1. Let D n = { x 1 , … , x n } D_n=\{x_1,\ldots,x_n\} D n = { x 1 , … , x n } be exchangeable together with the (potentially unseen) clean test point x n + 1 x_{n+1} x n + 1 . Let L : X × [ 0 , 1 ] → { 0 , 1 } L:\mathcal{X}\times[0,1]\to\{0,1\} L : X × [ 0 , 1 ] → { 0 , 1 } be such that, for every x ∈ X x\in\mathcal{X} x ∈ X , the map λ ↦ L ( x , λ ) \lambda\mapsto L(x,\lambda) λ ↦ L ( x , λ ) is non-increasing, right-continuous, and we have L ( ⋅ , 1 ) = 0 L(\cdot,1)=0 L ( ⋅ , 1 ) = 0 . Let ψ : X → X \psi:\mathcal{X}\to\mathcal{X} ψ : X → X be a smoothing scheme that is independent of the data, with model-agnostic certified bounds c ↓ ( ⋅ , B − 1 ) c^{\downarrow}(\cdot,\mathcal{B}^{-1}) c ↓ ( ⋅ , B − 1 ) and c ↑ ( ⋅ , B ) c^{\uparrow}(\cdot,\mathcal{B}) c ↑ ( ⋅ , B ) . Given any user-specified tolerance α > 0 \alpha>0 α > 0 , let ϵ 1 , … , ϵ n + 1 \epsilon_1,\ldots,\epsilon_{n+1} ϵ 1 , … , ϵ n + 1 be iid draws from ψ \psi ψ . With λ ⋆ \lambda^{\star} λ ⋆ defined as either
λ ⋆ = inf { λ : 1 n + 1 [ 1 + ∑ i = 1 n L ( x i + ϵ , λ ) ] ≤ c ↓ ( α , B − 1 ) } (10) \lambda^{\star}=\inf\left\{\lambda:\frac{1}{n+1}\left[1+\sum_{i=1}^{n}L(x_i+\epsilon,\lambda)\right]\leq c^{\downarrow}(\alpha,\mathcal{B}^{-1})\right\} \tag*{(10)} λ ⋆ = inf { λ : n + 1 1 [ 1 + i = 1 ∑ n L ( x i + ϵ , λ ) ] ≤ c ↓ ( α , B − 1 ) } (10) or
or λ ⋆ = inf { λ : 1 n + 1 [ 1 + ∑ i = 1 n c ^ ϵ ↓ ( Pr ϵ [ L ( x i + ϵ , λ ) = 1 ] , B ) ] ≤ α − δ } (11) \text{or }\quad\lambda^{\star}=\inf\left\{\lambda:\frac{1}{n+1}\left[1+\sum_{i=1}^{n}\widehat{c}^{\downarrow}_{\epsilon}\left(\operatorname{Pr}_{\epsilon}[L(x_i+\epsilon,\lambda)=1],\mathcal{B}\right)\right]\leq\alpha-\delta\right\} \tag*{(11)} or λ ⋆ = inf { λ : n + 1 1 [ 1 + i = 1 ∑ n c ϵ ↓ ( Pr ϵ [ L ( x i + ϵ , λ ) = 1 ] , B ) ] ≤ α − δ } (11)
where the latter λ ∗ \lambda^{\ast} λ ∗ corresponds to the calibration-heavy variant, we have
E D , ϵ [ L ( x ~ n + 1 + ϵ , λ ∗ ) ] ≤ α , ∀ x ~ n + 1 ∈ B ( x n + 1 ) . \mathbb{E}_{\mathcal{D},\epsilon}\left[L(\tilde{x}_{n+1}+\epsilon,\lambda^{\ast})\right]\leq\alpha,\quad\forall\tilde{x}_{n+1}\in\mathcal{B}(x_{n+1}). E D , ϵ [ L ( x ~ n + 1 + ϵ , λ ∗ ) ] ≤ α , ∀ x ~ n + 1 ∈ B ( x n + 1 ) .
where δ ∈ [ 0 , 1 ] \delta\in[0,1] δ ∈ [ 0 , 1 ] is the confidence of the finite sample estimation, and c ϵ ↑ ( Pr ϵ [ L ( x + ϵ , λ ) = 1 ] , B ) c^{\uparrow}_{\epsilon}\left(\Pr_{\epsilon}[L(x+\epsilon,\lambda)=1],\mathcal{B}\right) c ϵ ↑ ( Pr ϵ [ L ( x + ϵ , λ ) = 1 ] , B ) is an upper confidence bound on c ↑ ( Pr ϵ [ L ( x + ϵ , λ ) = 1 ] , B ) c^{\uparrow}\left(\Pr_{\epsilon}[L(x+\epsilon,\lambda)=1],\mathcal{B}\right) c ↑ ( Pr ϵ [ L ( x + ϵ , λ ) = 1 ] , B ) with confidence 1 − δ n 1-\frac{\delta}{n} 1 − n δ .
Proof for Prop. 1. First, we prove for the single-sample calibration case. Since the noise augmenting function ψ \psi ψ is independent of the data, the set D + = { x + ϵ : x ∈ D } \mathcal{D}^{+}=\{x+\epsilon:x\in\mathcal{D}\} D + = { x + ϵ : x ∈ D } is also exchangeable. The risk function evaluated at the new points, i.e. L ( ⋅ + ϵ , λ ) L(\cdot+\epsilon,\lambda) L ( ⋅ + ϵ , λ ) , maintains all mentioned properties; this is since the non-increasing, right-continuous, and bounded behaviour of L L L is over the entire domain X \mathcal{X} X . Therefore, we can apply the conformal risk control result of Angelopoulos et al. [ [1 ] to the augmented dataset, meaning that for the arbitrary tolerance α \alpha α , we first compute c ↑ ( α , B − 1 ) c^{\uparrow}(\alpha,\mathcal{B}^{-1}) c ↑ ( α , B − 1 ) , and for
λ ∗ = inf { λ : 1 n + 1 [ 1 + ∑ i = 1 n L ( x i + ϵ i , λ ) ] ≤ c ↑ ( α , B − 1 ) } . \lambda^{\ast}=\inf\left\{\lambda:\frac{1}{n+1}\left[1+\sum_{i=1}^{n}L(x_i+\epsilon_i,\lambda)\right]\leq c^{\uparrow}(\alpha,\mathcal{B}^{-1})\right\}. λ ∗ = inf { λ : n + 1 1 [ 1 + i = 1 ∑ n L ( x i + ϵ i , λ ) ] ≤ c ↑ ( α , B − 1 ) } .
CRC guarantees that
E D , ϵ [ 1 , n + 1 ] [ L ( x n + 1 + ϵ n + 1 , λ ∗ ) ] ≤ c ↑ ( α , B − 1 ) . \mathbb{E}_{\mathcal{D},\epsilon_{[1,n+1]}}\left[L(x_{n+1}+\epsilon_{n+1},\lambda^{\ast})\right]\leq c^{\uparrow}(\alpha,\mathcal{B}^{-1}). E D , ϵ [ 1 , n + 1 ] [ L ( x n + 1 + ϵ n + 1 , λ ∗ ) ] ≤ c ↑ ( α , B − 1 ) .
with ϵ [ 1 , n + 1 ] \epsilon_{[1,n+1]} ϵ [ 1 , n + 1 ] as the noises in D + \mathcal{D}^{+} D + . Defining β n + 1 = Pr ϵ n + 1 [ L ( x n + 1 + ϵ n + 1 , λ ^ ) = 1 ] \beta_{n+1}=\Pr_{\epsilon_{n+1}}\left[L(x_{n+1}+\epsilon_{n+1},\hat{\lambda})=1\right] β n + 1 = Pr ϵ n + 1 [ L ( x n + 1 + ϵ n + 1 , λ ^ ) = 1 ] we have
E D , ϵ [ 1 , n ] [ Pr ϵ n + 1 [ L ( x n + 1 + ϵ n + 1 , λ ^ ) = 1 ] ] ≤ c ↑ ( α , B − 1 ) ⇒ E D , ϵ [ 1 , n ] [ β n + 1 ] ≤ c ↑ ( α , B − 1 ) , \mathbb{E}_{\mathcal{D},\epsilon_{[1,n]}}\left[\Pr_{\epsilon_{n+1}}\left[L(x_{n+1}+\epsilon_{n+1},\hat{\lambda})=1\right]\right]\leq c^{\uparrow}(\alpha,\mathcal{B}^{-1})\quad\Rightarrow\quad\mathbb{E}_{\mathcal{D},\epsilon_{[1,n]}}\left[\beta_{n+1}\right]\leq c^{\uparrow}(\alpha,\mathcal{B}^{-1}), E D , ϵ [ 1 , n ] [ ϵ n + 1 Pr [ L ( x n + 1 + ϵ n + 1 , λ ^ ) = 1 ] ] ≤ c ↑ ( α , B − 1 ) ⇒ E D , ϵ [ 1 , n ] [ β n + 1 ] ≤ c ↑ ( α , B − 1 ) ,
with β n + 1 = Pr ϵ n + 1 [ L ( x n + 1 + ϵ n + 1 , λ ^ ) = 1 ] \beta_{n+1}=\Pr_{\epsilon_{n+1}}\left[L(x_{n+1}+\epsilon_{n+1},\hat{\lambda})=1\right] β n + 1 = Pr ϵ n + 1 [ L ( x n + 1 + ϵ n + 1 , λ ^ ) = 1 ] . Through randomized smoothing we have
max x ~ ∈ B ( x n + 1 ) Pr ϵ n + 1 [ L ( x ~ + ϵ n + 1 , λ ^ ) = 1 ] ≤ c ↑ ( Pr ϵ n + 1 [ L ( x n + 1 + ϵ n + 1 , λ ^ ) = 1 ] , B ) = c ↑ ( β n + 1 , B ) . \max_{\tilde{x}\in\mathcal{B}(x_{n+1})}\Pr_{\epsilon_{n+1}}\left[L(\tilde{x}+\epsilon_{n+1},\hat{\lambda})=1\right]\leq c^{\uparrow}\left(\Pr_{\epsilon_{n+1}}\left[L(x_{n+1}+\epsilon_{n+1},\hat{\lambda})=1\right],\mathcal{B}\right)=c^{\uparrow}(\beta_{n+1},\mathcal{B}). x ~ ∈ B ( x n + 1 ) max ϵ n + 1 Pr [ L ( x ~ + ϵ n + 1 , λ ^ ) = 1 ] ≤ c ↑ ( ϵ n + 1 Pr [ L ( x n + 1 + ϵ n + 1 , λ ^ ) = 1 ] , B ) = c ↑ ( β n + 1 , B ) .
Zargarbashi et al. [2025] proves that the lower bound c ↓ ( α , B − 1 ) c^{\downarrow}(\alpha,\mathcal{B}^{-1}) c ↓ ( α , B − 1 ) is a convex function. Similarly, Lemma 1 shows that c ↑ ( β n + 1 , B ) c^{\uparrow}(\beta_{n+1},\mathcal{B}) c ↑ ( β n + 1 , B ) is a concave function of β n + 1 \beta_{n+1} β n + 1 . Since c ↑ ( ⋅ , B ) c^{\uparrow}(\cdot,\mathcal{B}) c ↑ ( ⋅ , B ) is monotone in its first argument, we can use Jensen’s inequality. Let α r : = c ↑ ( α , B − 1 ) \alpha_r:=c^{\uparrow}(\alpha,\mathcal{B}^{-1}) α r := c ↑ ( α , B − 1 ) , we have
E D , ϵ [ 1 , n ] [ c ↑ ( β n + 1 , B ) ] ≤ c ↑ ( E D , ϵ [ 1 , n ] [ β n + 1 ] , B ) ≤ c ↑ ( α r , B ) = c ↑ ( c ↓ ( α , B − 1 ) , B ) = α . \mathbb{E}_{\mathcal{D},\epsilon_{[1,n]}}\left[c^{\uparrow}(\beta_{n+1},\mathcal{B})\right]\leq c^{\uparrow}\left(\mathbb{E}_{\mathcal{D},\epsilon_{[1,n]}}[\beta_{n+1}],\mathcal{B}\right)\leq c^{\uparrow}(\alpha_r,\mathcal{B})=c^{\uparrow}\left(c^{\downarrow}(\alpha,\mathcal{B}^{-1}),\mathcal{B}\right)=\alpha. E D , ϵ [ 1 , n ] [ c ↑ ( β n + 1 , B ) ] ≤ c ↑ ( E D , ϵ [ 1 , n ] [ β n + 1 ] , B ) ≤ c ↑ ( α r , B ) = c ↑ ( c ↓ ( α , B − 1 ) , B ) = α .
The last equality follows from c ↑ ( c ↓ ( α , B − 1 ) , B ) = α c^{\uparrow}(c^{\downarrow}(\alpha,\mathcal{B}^{-1}),\mathcal{B})=\alpha c ↑ ( c ↓ ( α , B − 1 ) , B ) = α , which is a property of the randomized-smoothing certificate. Therefore, for all x ~ n + 1 ∈ B ( x n + 1 ) \tilde{x}_{n+1}\in\mathcal{B}(x_{n+1}) x ~ n + 1 ∈ B ( x n + 1 )
E D , ϵ [ 1 , n ] [ Pr ϵ n + 1 [ L ( x ~ n + 1 + ϵ n + 1 , λ ^ ) = 1 ] ] ≤ E D , ϵ [ 1 , n ] [ max x ~ ∈ B ( x n + 1 ) Pr ϵ n + 1 [ L ( x ~ + ϵ n + 1 , λ ^ ) = 1 ] ] ≤ α . \mathbb{E}_{\mathcal{D},\epsilon_{[1,n]}}\left[\Pr_{\epsilon_{n+1}}\left[L(\tilde{x}_{n+1}+\epsilon_{n+1},\hat{\lambda})=1\right]\right]\leq\mathbb{E}_{\mathcal{D},\epsilon_{[1,n]}}\left[\max_{\tilde{x}\in\mathcal{B}(x_{n+1})}\Pr_{\epsilon_{n+1}}\left[L(\tilde{x}+\epsilon_{n+1},\hat{\lambda})=1\right]\right]\leq\alpha. E D , ϵ [ 1 , n ] [ ϵ n + 1 Pr [ L ( x ~ n + 1 + ϵ n + 1 , λ ^ ) = 1 ] ] ≤ E D , ϵ [ 1 , n ] [ x ~ ∈ B ( x n + 1 ) max ϵ n + 1 Pr [ L ( x ~ + ϵ n + 1 , λ ^ ) = 1 ] ] ≤ α .
For the calibration-heavy version, first consider the asymptotically valid setup – estimation with infinite samples; define
R ( x i , λ ) = c ↑ ( Pr ϵ [ L ( x i + ϵ , λ ) = 1 ] , B ) . R(x_i,\lambda)=c^{\uparrow}\left(\Pr_{\epsilon}[L(x_i+\epsilon,\lambda)=1],\mathcal{B}\right). R ( x i , λ ) = c ↑ ( ϵ Pr [ L ( x i + ϵ , λ ) = 1 ] , B ) .
By the randomized-smoothing certificate,
R ( x i , λ ) ≥ sup x ~ i ∈ B ( x i ) Pr ϵ [ L ( x ~ i + ϵ , λ ) = 1 ] . R(x_i,\lambda)\geq\sup_{\tilde{x}_i\in\mathcal{B}(x_i)}\Pr_{\epsilon}[L(\tilde{x}_i+\epsilon,\lambda)=1]. R ( x i , λ ) ≥ x ~ i ∈ B ( x i ) sup ϵ Pr [ L ( x ~ i + ϵ , λ ) = 1 ] .
Since L ( ⋅ , λ ) L(\cdot,\lambda) L ( ⋅ , λ ) is non-increasing and right-continuous in λ \lambda λ , upper bounded by 1 1 1 , and L ( ⋅ , 1 ) = 0 L(\cdot,1)=0 L ( ⋅ , 1 ) = 0 , the same properties are preserved for sup x ~ i ∈ B ( x i ) Pr ϵ [ L ( x ~ i + ϵ , λ ) = 1 ] \sup_{\tilde{x}_i\in\mathcal{B}(x_i)}\Pr_{\epsilon}[L(\tilde{x}_i+\epsilon,\lambda)=1] sup x ~ i ∈ B ( x i ) Pr ϵ [ L ( x ~ i + ϵ , λ ) = 1 ] . Replacing this loss with an upper bound (e.g. R R R ) regardless of whether it preserves the same properties, results in a higher parameter λ \lambda λ and therefore it satisfies the guarantee over the original risk. Therefore, we can directly apply CRC with the risk R R R and tune λ \lambda λ resulting in the guarantee over sup x ~ n + 1 ∈ B ( x n + 1 ) Pr ϵ [ L ( x ~ n + 1 + ϵ , λ ) = 1 ] \sup_{\tilde{x}_{n+1}\in\mathcal{B}(x_{n+1})}\Pr_{\epsilon}[L(\tilde{x}_{n+1}+\epsilon,\lambda)=1] sup x ~ n + 1 ∈ B ( x n + 1 ) Pr ϵ [ L ( x ~ n + 1 + ϵ , λ ) = 1 ]
λ ∗ = inf { λ : 1 + ∑ i = 1 n R ( x i , λ ) n + 1 ≤ α } ⇒ E D [ R ( x n + 1 , λ ∗ ) ] ≤ α . \lambda^{\ast}=\inf\left\{\lambda:\frac{1+\sum_{i=1}^{n}R(x_i,\lambda)}{n+1}\leq\alpha\right\}\quad\Rightarrow\quad\mathbb{E}_{\mathcal{D}}[R(x_{n+1},\lambda^{\ast})]\leq\alpha. λ ∗ = inf { λ : n + 1 1 + ∑ i = 1 n R ( x i , λ ) ≤ α } ⇒ E D [ R ( x n + 1 , λ ∗ )] ≤ α .
E D , ϵ [ L ( x ~ n + 1 + ϵ , λ ∗ ) ] ≤ E D [ sup x ~ ∈ B ( x n + 1 ) Pr ϵ [ L ( x ~ + ϵ , λ ∗ ) = 1 ] ] ≤ E D [ R ( x n + 1 , λ ∗ ) ] ≤ α . \mathbb{E}_{D,\epsilon}\left[L(\tilde{x}_{n+1}+\epsilon,\lambda^*)\right] \le\mathbb{E}_{D}\left[\sup_{\tilde{x}\in B(x_{n+1})}\Pr_{\epsilon}\left[L(\tilde{x}+\epsilon,\lambda^*)=1\right]\right] \le\mathbb{E}_{D}\left[R(x_{n+1},\lambda^*)\right] \le\alpha. E D , ϵ [ L ( x ~ n + 1 + ϵ , λ ∗ ) ] ≤ E D [ x ~ ∈ B ( x n + 1 ) sup ϵ Pr [ L ( x ~ + ϵ , λ ∗ ) = 1 ] ] ≤ E D [ R ( x n + 1 , λ ∗ ) ] ≤ α .
For the finite-sample version, the confidence event must hold simultaneously over all calibration points. Using the union bound, the failure probability over the n n n calibration points, each with confidence 1 − δ n 1-\frac{\delta}{n} 1 − n δ , accumulates to δ \delta δ . Notably if we calibrate CRC on α − δ \alpha-\delta α − δ instead of α \alpha α , then the total failure probability is at most α − δ + δ = α \alpha-\delta+\delta=\alpha α − δ + δ = α . This requires the bounds to hold at the selected λ ∗ \lambda^* λ ∗ ; when λ ∗ \lambda^* λ ∗ is searched over the same Monte Carlo samples that are used for the bounds, pointwise bounds do not guarantee this. This is why in practice we use the two-phase procedure of § A.1, whose complete failure-probability is given in the proof of Prop. 4.
An important building block in the above proof is the following lemma.
Lemma 1. c † ( β , B ) c^\dagger(\beta,\mathcal{B}) c † ( β , B ) is concave and monotonically increasing w.r.t. β \beta β .
Proof. The Lagrangian form of the upper-bound problem is:
L ( β , λ ) = max h ∈ { 0 , 1 } ∣ X ∣ Pr ϵ [ h ( t ~ + ϵ ) = 1 ] − λ ( Pr ϵ [ h ( t + ϵ ) = 1 ] − β ) = max h ∈ { 0 , 1 } ∣ X ∣ E z ∼ q [ h ( z ) ] − λ ⋅ E z ∼ p [ h ( z ) − β ] = λ ⋅ β + max h ∈ { 0 , 1 } ∣ X ∣ E z ∼ q [ h ( z ) ] − λ ⋅ E z ∼ p [ h ( z ) ] = λ ⋅ β + max h ∈ { 0 , 1 } ∣ X ∣ ∫ X ( q ( z ) − λ ⋅ p ( z ) ) ⋅ h ( z ) d z . \begin{aligned}
\mathcal{L}(\beta,\lambda) &= \max_{h\in\{0,1\}^{|\mathcal{X}|}} \Pr_{\epsilon}[h(\tilde{t}+\epsilon)=1]-\lambda\left(\Pr_{\epsilon}[h(t+\epsilon)=1]-\beta\right) \\
&= \max_{h\in\{0,1\}^{|\mathcal{X}|}} \mathbb{E}_{z\sim q}[h(z)]-\lambda\cdot\mathbb{E}_{z\sim p}[h(z)-\beta] \\
&= \lambda\cdot\beta+\max_{h\in\{0,1\}^{|\mathcal{X}|}}\mathbb{E}_{z\sim q}[h(z)]-\lambda\cdot\mathbb{E}_{z\sim p}[h(z)] \\
&= \lambda\cdot\beta+\max_{h\in\{0,1\}^{|\mathcal{X}|}}\int_{\mathcal{X}}(q(z)-\lambda\cdot p(z))\cdot h(z)\,dz.
\end{aligned} L ( β , λ ) = h ∈ { 0 , 1 } ∣ X ∣ max ϵ Pr [ h ( t ~ + ϵ ) = 1 ] − λ ( ϵ Pr [ h ( t + ϵ ) = 1 ] − β ) = h ∈ { 0 , 1 } ∣ X ∣ max E z ∼ q [ h ( z )] − λ ⋅ E z ∼ p [ h ( z ) − β ] = λ ⋅ β + h ∈ { 0 , 1 } ∣ X ∣ max E z ∼ q [ h ( z )] − λ ⋅ E z ∼ p [ h ( z )] = λ ⋅ β + h ∈ { 0 , 1 } ∣ X ∣ max ∫ X ( q ( z ) − λ ⋅ p ( z )) ⋅ h ( z ) d z .
The optimal classifier is:
h ( z ) = { 1 if q ( z ) − λ ⋅ p ( z ) ≥ 0 0 otherwise. h(z)=
\begin{cases}
1 & \text{if } q(z)-\lambda\cdot p(z)\ge0 \\
0 & \text{otherwise.}
\end{cases} h ( z ) = { 1 0 if q ( z ) − λ ⋅ p ( z ) ≥ 0 otherwise.
Intuitively, to maximize the term ∫ X ( q ( z ) − λ ⋅ p ( z ) ) ⋅ h ( z ) d z \int_{\mathcal{X}}(q(z)-\lambda\cdot p(z))\cdot h(z)\,dz ∫ X ( q ( z ) − λ ⋅ p ( z )) ⋅ h ( z ) d z , we select h ( z ) = 1 h(z)=1 h ( z ) = 1 whenever the integrand is positive.
The resulting dual with λ ≥ 0 \lambda\ge0 λ ≥ 0 is:
L ( β , λ ) = λ ⋅ β + ∫ max { 0 , q ( z ) − λ ⋅ p ( z ) } d z = λ ⋅ β + l ( λ ) , \mathcal{L}(\beta,\lambda)=\lambda\cdot\beta+\int\max\{0,q(z)-\lambda\cdot p(z)\}\,dz=\lambda\cdot\beta+l(\lambda), L ( β , λ ) = λ ⋅ β + ∫ max { 0 , q ( z ) − λ ⋅ p ( z )} d z = λ ⋅ β + l ( λ ) ,
where l ( λ ) : = ∫ max { 0 , q ( z ) − λ ⋅ p ( z ) } d z l(\lambda):=\int\max\{0,q(z)-\lambda\cdot p(z)\}\,dz l ( λ ) := ∫ max { 0 , q ( z ) − λ ⋅ p ( z )} d z depends only on λ \lambda λ .
Minimizing over λ \lambda λ gives:
c † ( β , B ) = min λ λ ⋅ β + l ( λ ) , c^\dagger(\beta,\mathcal{B})=\min_{\lambda}\lambda\cdot\beta+l(\lambda), c † ( β , B ) = λ min λ ⋅ β + l ( λ ) ,
which is a pointwise minimum of affine functions in β \beta β , and therefore concave in β \beta β .
The monotonicity w.r.t. β \beta β directly follows from the definition. Increasing β \beta β enlarges the feasible set, and therefore the optimal value cannot decrease.
Proof for Prop. 3. This is a direct implication of Prop. 1 with the risk function defined as η ( z , λ , x ) = h ^ ( z , λ ) ⋅ I { f ( z ) ≠ f ( x ) } \eta(z,\lambda,x)=\hat{h}(z,\lambda)\cdot\mathbb{I}\{f(z)\ne f(x)\} η ( z , λ , x ) = h ^ ( z , λ ) ⋅ I { f ( z ) = f ( x )} . The risk function inherits the properties from h ^ \hat{h} h ^ , as I { f ( z ) ≠ f ( x ) } \mathbb{I}\{f(z)\ne f(x)\} I { f ( z ) = f ( x )} ranges in { 0 , 1 } \{0,1\} { 0 , 1 } and is independent of λ \lambda λ . The upper bound is defined as c † ( η ( ⋅ , λ , x ) , B ( x ) ) c^\dagger(\eta(\cdot,\lambda,x),B(x)) c † ( η ( ⋅ , λ , x ) , B ( x )) . The final guarantee is Pr D , ϵ [ h ^ ( x ~ n + 1 + ϵ , λ ∗ ) ⋅ I { f ( x ~ n + 1 + ϵ ) ≠ f ( x n + 1 ) } = 1 ] ≤ α \Pr_{D,\epsilon}\left[\hat{h}(\tilde{x}_{n+1}+\epsilon,\lambda^*)\cdot\mathbb{I}\{f(\tilde{x}_{n+1}+\epsilon)\ne f(x_{n+1})\}=1\right]\le\alpha Pr D , ϵ [ h ^ ( x ~ n + 1 + ϵ , λ ∗ ) ⋅ I { f ( x ~ n + 1 + ϵ ) = f ( x n + 1 )} = 1 ] ≤ α for all x ~ n + 1 ∈ B ( x n + 1 ) \tilde{x}_{n+1}\in\mathcal{B}(x_{n+1}) x ~ n + 1 ∈ B ( x n + 1 ) .
Alternatively we can define a calibration-heavy version for which we have
λ ∗ = inf { λ : 1 n + 1 [ 1 + ∑ i = 1 n c ^ † ( η ( ⋅ , λ , x i ) , B ( x i ) ) ] ≤ α } \lambda^*=\inf\left\{\lambda:\frac{1}{n+1}\left[1+\sum_{i=1}^{n}\hat{c}^{\dagger}(\eta(\cdot,\lambda,x_i),\mathcal{B}(x_i))\right]\le\alpha\right\} λ ∗ = inf { λ : n + 1 1 [ 1 + i = 1 ∑ n c ^ † ( η ( ⋅ , λ , x i ) , B ( x i )) ] ≤ α }
however there is no use-case for it that can not be better accomplished by ProxC, or ProxC-H. □
Technical Details
False-approval rate vs. false positive rate. A more intuitive risk to tune ProxC with, instead of Eq. (2) , would be to control the false positive rate (FPR), defined as the conditional probability of a proxy approval given that the point is non-robust:
F P R = Pr [ cert ^ f , r ( x ~ n + 1 ) = 1 ∣ f ( x ~ n + 1 ) ≠ f ( x n + 1 ) ] = Pr [ cert ^ f , r ( x ~ n + 1 ) = 1 , f ( x ~ n + 1 ) ≠ f ( x n + 1 ) ] Pr [ f ( x ~ n + 1 ) ≠ f ( x n + 1 ) ] . \begin{aligned}
\mathrm{FPR}=\Pr\left[\widehat{\operatorname{cert}}_{f,r}(\tilde{x}_{n+1})=1\mid f(\tilde{x}_{n+1})\ne f(x_{n+1})\right] \\
&=\frac{\Pr\left[\widehat{\operatorname{cert}}_{f,r}(\tilde{x}_{n+1})=1,\ f(\tilde{x}_{n+1})\ne f(x_{n+1})\right]}{\Pr\left[f(\tilde{x}_{n+1})\ne f(x_{n+1})\right]}.
\end{aligned} FPR = Pr [ cert f , r ( x ~ n + 1 ) = 1 ∣ f ( x ~ n + 1 ) = f ( x n + 1 ) ] = Pr [ f ( x ~ n + 1 ) = f ( x n + 1 ) ] Pr [ cert f , r ( x ~ n + 1 ) = 1 , f ( x ~ n + 1 ) = f ( x n + 1 ) ] .
Controlling FPR ≤ α \le\alpha ≤ α is equivalent to controlling our marginal false-approval rate at the adjusted level α ⋅ ρ \alpha\cdot\rho α ⋅ ρ , where ρ = Pr [ f ( x ~ n + 1 ) ≠ f ( x n + 1 ) ] \rho=\Pr[f(\tilde{x}_{n+1})\ne f(x_{n+1})] ρ = Pr [ f ( x ~ n + 1 ) = f ( x n + 1 )] is the marginal non-robustness rate of the classifier. This coupling introduces an undesirable dependence on the quality of the underlying classifier. For a poorly robust classifier—one for which the sound certificate denies a large fraction of inputs—ρ \rho ρ is large, and the same absolute number of false approvals is normalized by a large denominator, making FPR ≤ α \le\alpha ≤ α easy to satisfy. Conversely, for a near-fully robust classifier where ρ \rho ρ is small, the denominator shrinks, the FPR estimate becomes a high-variance ratio, and calibration grows sensitive to individual false approvals in the calibration set. The marginal false-approval rate avoids this instability by treating the risk as a joint probability: the quantity ( 1 − cert f , r ( x ) ) h ^ ( x + ϵ , λ ) ∈ [ 0 , 1 ] (1-\operatorname{cert}_{f,r}(x))\hat{h}(x+\epsilon,\lambda)\in[0,1] ( 1 − cert f , r ( x )) h ^ ( x + ϵ , λ ) ∈ [ 0 , 1 ] is a bounded random variable whose sample mean is directly controlled by CRC with finite-sample guarantees, regardless of ρ \rho ρ . In this sense, our choice is not merely a notational preference: it ensures that the difficulty of proxy calibration is invariant to the non-robustness rate of the backbone classifier.
Supplementary on Experiments
Perturbed-data evaluation. We additionally evaluate whether the calibrated proxy certificates remain reliable when the test inputs are explicitly perturbed. For each clean CIFAR-10 test point, we generate an adversarial perturbation using the PGD-RS attack within the ℓ 2 \ell_2 ℓ 2 ball of radius r r r , and then evaluate the proxy certificate on the perturbed input. This setting directly tests the failure mode controlled by our risk: a proxy approval on an input whose prediction can change under perturbation. In Table 6 , we report the certified ratio (CR), certified accuracy (CA), and the empirical false-approval risk under attack. As expected, increasing r r r makes the certification problem harder and decreases both CR and CA (both in the backbone certificate, and in our own ProxC, and ProxC-A). At the same time, the average empirical risk remains below the target level α = 0.05 \alpha=0.05 α = 0.05 across all runs, showing that the proxy remains conservative even when evaluated on attacked inputs. Calibration fails for both ProxC and ProxC-A at r ≥ 0.75 r\ge0.75 r ≥ 0.75 , where the perturbed problem becomes too severe for either proxy to satisfy the prescribed risk constraint. This results in ProxC, and ProxC-A rejecting all inputs for that radius.
Detailed results. Table 7 reports results on ImageNet with the denoising + ViT pipeline. The ProxC-H approach is calibrated over 20,000 calibration MC samples and 400 calibration points.
Table 8 presents results on CIFAR-10 (σ = 0.5 \sigma=0.5 σ = 0.5 ) for ProxC under three risk budgets α ∈ { 2 % , 5 % , 10 % \alpha\in\{2\%,5\%,10\%\\ α ∈ { 2% , 5% , 10% . As expected, increasing α \alpha α grants the proxy a looser budget, allowing it to certify a larger fraction of samples. At r = 0.00 r=0.00 r = 0.00 , ProxC (α = 2 % \alpha=2\% α = 2% ) certifies only 48.8% of samples—well below RS (81.0%)—while remaining highly conservative with an empirical risk of 1.6%. With α = 5 % \alpha=5\% α = 5% , the proxy closes much of this gap (70.9% CR), and at α = 10 % \alpha=10\% α = 10% it slightly exceeds RS (82.3%), certifying more samples than the standard certificate by accepting a higher false-certificate rate (9.6%). Across all radii and risk levels, the empirical risk stays within the target budget (except 5.6% for α = 5 % \alpha=5\% α = 5% at r = 0 r=0 r = 0 , which is within the split-to-split variation of a single run, see Table 13 ), demonstrating the validity of the conformal calibration procedure.
Table 8. Certified Ratio (CR, %) and Certified Accuracy (CA, %) on CIFAR-10 (σ = 0.5 \sigma=0.5 σ = 0.5 , ResNet backbone, single run). Results are for three risk levels 2%, 5%, and 10%.
Fallback cost across radii. In the fallback mode, the backbone certificate is called exactly when the proxy rejects, so the reject rate is 1 − C R 1 - \mathrm{CR} 1 − CR and the cost follows the formula in Table 9 . Table 10 reports the reject rate and the resulting cost on ImageNet with ResNet (2000 samples in total: 50 for the label and 1950 for randomized smoothing). We report both the certification-only cost (compared to 1950 forwards) and the end-to-end cost including the 50 forwards of the label (compared to 2000 forwards). As the radius grows, the proxy rejects more inputs, and the speedup of the fallback decreases. ProxC-H always costs more than ProxC, but this gap is amortized over the queries, and it allows for a higher certified ratio, especially at larger radii (Table 3 ).
Class-stratified risk. The guarantee of ProxC is marginal: it says nothing about any particular class, subpopulation, or input. To assess how concentrated the false-approval risk is, Table 11 reports the risk on ImageNet stratified to the best and the worst 100 classes, and shows that the risk is heterogeneous across classes; however, aggregating over groups of 100 classes is only a partial characterization, and the marginal guarantee does not establish class-conditional or worst-class control. Table 12 reports the per-class risk on CIFAR-10. Four of the ten classes exceed α r \alpha_r α r at each radius (up to 3.46% at r = 0.12 r = 0.12 r = 0.12 and 2.63% at r = 0.25 r = 0.25 r = 0.25 , both for truck), and the risk conditional on approval is highest for classes with a low certified ratio (e.g. 12% for cat and deer at $r = 0.12). Binned by the proxy score, the false approvals concentrate just above the threshold: at r = 0.12 r = 0.12 r = 0.12 the test points with a score between 0.66 and 0.88 have a risk of about 10–11%, while the top decile has 0.1%. In order to avoid such imbalance, one can use the techniques like Mondrian conformal prediction to compute the λ \lambda λ threshold separately for each class, but this requires a larger calibration set to maintain the same statistical confidence.
Calibration-set size. The guarantee of ProxC holds in expectation over the calibration set, therefore for a single split the risk can exceed the tolerance. Table 13 studies the effect of n = ∣ D n ∣ n = \lvert D_n \rvert n = ∣ D n ∣ on CIFAR10 with the ResNet-110 of Cohen et al. [2019] (σ = 0.5 \sigma= 0.5 σ = 0.5 , α = 5 % \alpha= 5\% α = 5% ). We compute the backbone certificate (2000 MC samples) once on all 10,000 test images, and for each n n n draw 500 random calibration sets; the remaining images are used for testing. Since the proxy is calibrated on clean points at the corrected level α r = c ↓ ( α , B − 1 ) \alpha_r = c^{\downarrow}(\alpha, \mathcal{B}^{-1}) α r = c ↓ ( α , B − 1 ) , we compare the empirical risk with α r \alpha_r α r . For every r r r and n n n , the mean risk does not exceed α r \alpha_r α r by more than 0.2 standard errors, and it matches the CRC value ⌊ α r ( n + 1 ) ⌋ / ( n + 1 ) \lfloor\alpha_r(n + 1) \rfloor/(n + 1) ⌊ α r ( n + 1 )⌋ / ( n + 1 ) . The CRC correction requires n ≥ 1 / α r − 1 n \ge1/\alpha_r - 1 n ≥ 1/ α r − 1 (e.g. 62 points at r = 0.25 r = 0.25 r = 0.25 , and 244 at r = 0.5 r = 0.5 r = 0.5 ), below which the proxy approves nothing, and the CR levels off at n ≈ 500 n \approx500 n ≈ 500 . At n = 500 n = 500 n = 500 the results are within one standard deviation of the single-run values in Table 8 .
Compute resources. All experiments were run on NVIDIA H100 and A100 GPUs. For efficiency, we precomputed the noisy logits required by the randomized-smoothing certificate and by the proxy variants, and reused these cached logits across calibration and evaluation runs. This means that the main GPU cost comes from the forward passes needed to obtain the Monte Carlo samples. Once the logits are available, the remaining steps, including calibration, threshold selection, empirical risk estimation, and the computation of the certified lower and upper bounds, are lightweight post-processing operations that can be executed on CPU. Thus, the computational bottleneck is the number of model evaluations required by the underlying certificate, while the proposed proxy calibration itself adds negligible overhead beyond standard array operations. We highlight that we do not train or finetune any model and all the experiments are running on pre-trained models.
NLP Certificate
In Table 4 , we use the edit-distance certificate from Huang et al. [2024], and provide a proxy certificate for r r r insertions. The smoothing scheme is to delete tokens with p d e l p_{\mathrm{del}} p del probability. Here we provide theoretical support for the experiments and derivations.
Symmetry of the edit-distance ball. The Levenshtein (edit) distance satisfies the axioms of a metric, and in particular symmetry: d e d i t ( x , x ~ ) = d e d i t ( x ~ , x ) d_{\mathrm{edit}}(x,\tilde{x}) = d_{\mathrm{edit}}(\tilde{x},x) d edit ( x , x ~ ) = d edit ( x ~ , x ) for all inputs x , x ~ x,\tilde{x} x , x ~ . The edit-distance ball of radius r r r centred at x x x is
B r e d i t ( x ) : = { x ~ : d e d i t ( x , x ~ ) ≤ r } . \mathcal{B}^{\mathrm{edit}}_r(x) := \{\tilde{x}: d_{\mathrm{edit}}(x,\tilde{x}) \le r\}. B r edit ( x ) := { x ~ : d edit ( x , x ~ ) ≤ r } .
Symmetry of the distance immediately implies that x ~ ∈ B r e d i t ( x ) \tilde{x} \in\mathcal{B}^{\mathrm{edit}}_r(x) x ~ ∈ B r edit ( x ) if and only if x ∈ B r e d i t ( x ~ ) x \in\mathcal{B}^{\mathrm{edit}}_r(\tilde{x}) x ∈ B r edit ( x ~ ) . In the notation of §2, this means ( B e d i t ) − 1 = B e d i t (\mathcal{B}^{\mathrm{edit}})^{-1} = \mathcal{B}^{\mathrm{edit}} ( B edit ) − 1 = B edit : the edit-distance ball is its own inverse ball.
Insertion and deletion balls are mutual inverses. The insertion-only and deletion-only sub-balls are not individually symmetric, but they are inverses of each other. If x ˉ \bar{x} x ˉ is reachable from x x x by r r r insertions, then x x x is reachable from x ˉ \bar{x} x ˉ by exactly r r r deletions, and vice versa. Writing B r i n s ( x ) B_{r}^{\mathrm{ins}}(x) B r ins ( x ) and B r d e l ( x ) B_{r}^{\mathrm{del}}(x) B r del ( x ) for the sets of sequences reachable from x x x by at most r r r insertions and r r r deletions respectively,
x ˉ ∈ B r i n s ( x ) ⟺ x ∈ B r d e l ( x ˉ ) , \bar{x} \in B_{r}^{\mathrm{ins}}(x) \Longleftrightarrow x \in B_{r}^{\mathrm{del}}(\bar{x}), x ˉ ∈ B r ins ( x ) ⟺ x ∈ B r del ( x ˉ ) ,
so that ( B r i n s ) − 1 = B r d e l (B_{r}^{\mathrm{ins}})^{-1}=B_{r}^{\mathrm{del}} ( B r ins ) − 1 = B r del and ( B r d e l ) − 1 = B r i n s (B_{r}^{\mathrm{del}})^{-1}=B_{r}^{\mathrm{ins}} ( B r del ) − 1 = B r ins . Insertions and deletions are therefore dual operations under the inverse-ball map.
This is specifically important since we use inverse ball for single sample calibration in Prop. 2 .
Upper and lower bounds under edit operations. Following Huang et al. [ [22 ] , the smoothed classifier admits explicit upper and lower bounds under edit-distance perturbations. Consider an input x x x and a perturbed input x ˉ \bar{x} x ˉ obtained using n d e l n_{\mathrm{del}} n del deletions, n i n s n_{\mathrm{ins}} n ins insertions, and n s u b n_{\mathrm{sub}} n sub substitutions, with
n d e l + n i n s + n s u b = r . n_{\mathrm{del}}+n_{\mathrm{ins}}+n_{\mathrm{sub}}=r. n del + n ins + n sub = r .
Then, for any class y y y , the smoothed classifier score satisfies
p d e l n d e l − n i n s ( p y ( x ) − 1 + p d e l n s u b + n i n s ) ≤ p y ( x ˉ ) ≤ p d e l n d e l − n i n s p y ( x ) + 1 − p d e l n s u b + n d e l . p_{\mathrm{del}}^{n_{\mathrm{del}}-n_{\mathrm{ins}}}\left(p_y(x)-1+p_{\mathrm{del}}^{n_{\mathrm{sub}}+n_{\mathrm{ins}}}\right) \le p_y(\bar{x}) \le p_{\mathrm{del}}^{n_{\mathrm{del}}-n_{\mathrm{ins}}}p_y(x)+1-p_{\mathrm{del}}^{n_{\mathrm{sub}}+n_{\mathrm{del}}}. p del n del − n ins ( p y ( x ) − 1 + p del n sub + n ins ) ≤ p y ( x ˉ ) ≤ p del n del − n ins p y ( x ) + 1 − p del n sub + n del .
The certificate follows from comparing the lower bound on the predicted class score against the upper bound on the runner-up, analogously to the ℓ 2 \ell_2 ℓ 2 certificate.
Under a fixed edit budget r r r , the conservative worst-case configuration is attained when all perturbations are substitutions: n s u b = r n_{\mathrm{sub}}=r n sub = r and n d e l = n i n s = 0 n_{\mathrm{del}}=n_{\mathrm{ins}}=0 n del = n ins = 0 . Substituting into the general bounds yields the Levenshtein-distance certificate of Huang et al. [ [22 ] :
p y ( x ) − 1 + p d e l r ≤ p y ( x ˉ ) ≤ p y ( x ) + 1 − p d e l r . p_y(x)-1+p_{\mathrm{del}}^r \le p_y(\bar{x}) \le p_y(x)+1-p_{\mathrm{del}}^r. p y ( x ) − 1 + p del r ≤ p y ( x ˉ ) ≤ p y ( x ) + 1 − p del r .
Substitutions are the worst case because they combine the effect of both a shrinking lower bound and a growing upper bound simultaneously, without the compensating multiplicative factor that pure insertions or deletions introduce.
Per-operation certificates. The same framework yields tighter certificates when the threat model is restricted to a single operation type. For substitution-only perturbations (n s u b = r n_{\mathrm{sub}}=r n sub = r , n d e l = n i n s = 0 n_{\mathrm{del}}=n_{\mathrm{ins}}=0 n del = n ins = 0 ):
p y ( x ) − 1 + p d e l r ≤ p y ( x ˉ ) ≤ p y ( x ) + 1 − p d e l r . p_y(x)-1+p_{\mathrm{del}}^r \le p_y(\bar{x}) \le p_y(x)+1-p_{\mathrm{del}}^r. p y ( x ) − 1 + p del r ≤ p y ( x ˉ ) ≤ p y ( x ) + 1 − p del r .
For insertion-only perturbations (n i n s = r n_{\mathrm{ins}} = r n ins = r , n d e l = n s u b = 0 n_{\mathrm{del}} = n_{\mathrm{sub}} = 0 n del = n sub = 0 ):
p d e l − r ( p y ( x ) − 1 + p d e l r ) ≤ p y ( x ˉ ) ≤ p d e l − r p y ( x ) . p_{\mathrm{del}}^{-r}(p_y(x) - 1 + p_{\mathrm{del}}^r) \le p_y(\bar{x}) \le p_{\mathrm{del}}^{-r}p_y(x). p del − r ( p y ( x ) − 1 + p del r ) ≤ p y ( x ˉ ) ≤ p del − r p y ( x ) .
For deletion-only perturbations (n d e l = r n_{\mathrm{del}} = r n del = r , n i n s = n s u b = 0 n_{\mathrm{ins}} = n_{\mathrm{sub}} = 0 n ins = n sub = 0 ):
p d e l r p y ( x ) ≤ p y ( x ˉ ) ≤ p d e l r p y ( x ) + 1 − p d e l r . p_{\mathrm{del}}^r p_y(x) \le p_y(\bar{x}) \le p_{\mathrm{del}}^r p_y(x) + 1 - p_{\mathrm{del}}^r. p del r p y ( x ) ≤ p y ( x ˉ ) ≤ p del r p y ( x ) + 1 − p del r .
These expressions reveal qualitatively different distortions: substitutions induce additive shifts, whereas insertions and deletions induce multiplicative rescalings, consistent with the inverse-ball duality established above.
For instance, to apply Prop. 2 on the insertion-only ball, we need to take the lower bound of the deletion-only ball, or the upper bound of the insertion ball itself, which means that c † ( α , B − 1 ) = p d e l r α c^\dagger(\alpha,\mathcal{B}^{-1}) = p_{\mathrm{del}}^r\alpha c † ( α , B − 1 ) = p del r α , and c † ( α , B − 1 ) = p d e l − r α c^\dagger(\alpha,\mathcal{B}^{-1}) = p_{\mathrm{del}}^{-r}\alpha c † ( α , B − 1 ) = p del − r α . In our experiments the only ball that could be certified effectively was the insertion ball.
Insertions as a valid proxy threat model. The backbone certificate is derived over the full edit-distance ball B r e d i t ( x ) \mathcal{B}^{\mathrm{edit}}_r(x) B r edit ( x ) , but the proxy in Table 4 is calibrated against r r r -insertion perturbations. This choice is valid by containment: any sequence reachable from x x x by r r r insertions has Levenshtein distance at most r r r from x x x , so
B r i n s ( x ) ⊆ B r e d i t ( x ) . \mathcal{B}^{\mathrm{ins}}_r(x) \subseteq\mathcal{B}^{\mathrm{edit}}_r(x). B r ins ( x ) ⊆ B r edit ( x ) .
A certificate valid over the full edit-distance ball therefore remains valid over the insertion-only sub-ball, and the proxy guarantee of Prop. 2 carries over without modification. Insertions are a natural and semantically meaningful subset of the edit-distance threat model, covering realistic perturbations such as token injection or paraphrase expansion, and their ball is a strict subset of the edit-distance ball certified by the backbone.
Related Works
Certified robustness. The vulnerability of neural networks to adversarial perturbations has motivated a large literature on defenses and robustness verification. Purely empirical defenses are difficult to trust in isolation: e.g. Athalye et al. [ [5 ] showed that defenses relying on gradient masking can be circumvented by adaptive attacks. Certified robustness replaces this empirical evaluation with a formal implication: if a point is certified, then the prediction is guaranteed to be constant within the specified perturbation set. One line of work obtains such guarantees by reasoning directly about the network, using satisfiability or mixed-integer formulations [24 , 34 ] , convex outer relaxations [38 ] , and layer-wise linear bounds [37 , 44 ] . These methods are sound and often tight for the architectures they support, but their cost and implementation dependence make them difficult to apply to large modern pipelines, or to black-box systems where the model internals are unavailable. Our work keeps the soundness of an existing certificate as a calibration signal, but changes its deployment role: instead of verifying every test point, the certificate is used to control the marginal false-approval rate of a cheaper proxy.
Randomized smoothing. Randomized smoothing is the most relevant certificate for our setting because it is model-agnostic and therefore applies to arbitrary classifiers through noisy inference. Cohen et al. [ [11 ] proposed the standard Gaussian certificate for ℓ 2 \ell_2 ℓ 2 robustness and showed that smoothing scales to ImageNet. Subsequent work broadened the certificate in several directions: Lee et al. [ [27 ] derived tight certificates for broader randomized ensembles and discrete perturbations, Yang et al. [ [40 ] developed a general recipe for smoothing with different perturbation geometries and smoothing distributions. Other work has improved the trained smoothed classifier itself, for example through adversarially trained smoothed classifiers [32 ] . Smoothing has also been used to certify quantities beyond the top-label robustness radius, such as predictive confidence [26 ] , and has been extended to structured outputs such as segmentation [13 ] . Denoised smoothing prepends a denoiser before the classifier so that pretrained models can be certified without changing the classifier; for the denoiser we can typically use a diffusion model [33 , 10 ] . In summary, so far randomized smoothing seems to scale on larger datasets, and models, and return better certified accuracy compared to verifications, and exact certificates. The main limitation shared by these approaches is the same one we target: the smoothed class probabilities have to be estimated by Monte Carlo sampling at calibration and test time, and finite-sample confidence corrections can require hundreds or thousands of forward passes per input. Recent work reduces this cost for the certificate itself through confidence sequences and early stopping [35 ] . Such techniques are complementary to ours: they can reduce the cost of the backbone certificate, and hence both our calibration cost and the fallback cost, without changing the proxy calibration. Our framework is orthogonal to the choice of smoothing certificate; it asks how to use such certificates less often while still retaining a formal, distribution-free validity statement.
Relaxed and distributional robustness. Classical certification is pointwise: every certified input receives a local guarantee. This is the strongest statement, but also the most expensive one. Several works have considered relaxations that replace worst-case pointwise robustness with a distributional or probabilistic guarantee. Rice et al. [ [29 ] studied robustness notions between average-case (random) and worst-case perturbation. In contrast, our work provides efficiency for the worst-case perturbation which is a different (and stronger) guarantee. We assume every test point is perturbed at its worst. Blohm et al. [ [9 ] proposed probably approximately global (PAG) robustness certification, which also relaxes the soundness to a marginal guarantee. Their guarantee connects the confidence of the prediction with its robust radius – they propose a ρ \rho ρ -κ \kappa κ robustness guarantee, ensuring that with confidence higher than κ \kappa κ , with high probability x x x has a robust radius above ρ \rho ρ . This work is conceptually close to ours in that it also trades pointwise guarantee for a statistically meaningful marginal guarantee. The distinction is that we do not aim to certify the global robustness of the classifier itself, and we do not offer a guaranteed mapping between confidence and robust radii. While we use a simple thresholded proxy as our example, one can define more complex functions and adapt it to our framework for free; additionally, we aim to replace the expensive certificate, with a cheaper function and not to state a confidence-radii front for the classifier. Our proxy is allowed to accept many inputs cheaply, while its probability of accepting a genuinely non-robust input is controlled over the future data distribution. Intuitively, the distinction is analogous to the difference between conformal prediction and post-hoc calibration methods such as Platt scaling: PAG constructs a distributional guarantee over robustness events, whereas our method calibrates a proxy certificate to imitate an expensive certificate under a controlled marginal false-approval risk.
Conformal prediction and conformal risk control. Conformal prediction provides distribution-free finite-sample guarantees under exchangeability [36 , 4 , 2 ] . In classification, set-valued predictors with valid coverage were studied by Sadinle et al. [2018] and Romano et al. [ [30 ] , and the same idea has since been used as a general-purpose uncertainty quantification tool. Extensions beyond exact exchangeability, such as the weighted and approximate guarantees studied by Barber et al. [ [7 ] , are relevant whenever deployment differs from calibration. Conformal risk control (CRC) extends the conformal guarantee from miscoverage to general monotone risks [1 ] . Instead of requiring the loss to be the indicator of a missed label, CRC calibrates a parameter so that the expected value of a user-chosen risk is below a target level. This is the main statistical primitive in our paper: the event we need to control is not ordinary miscoverage, but false approval by a proxy certificate. Related risk-control ideas also appear in risk-controlling prediction sets [8 ] , in the Learn then Test framework for finite-sample control of more general risks [3 ] , and in selective prediction where a model learns when to abstain [14 , 15 ] . Our use of CRC differs from standard selective classification because the controlled failure event is defined relative to adversarial robustness, and the test point may be a perturbation of an exchangeable clean point rather than itself exchangeable with the calibration data.
Robust conformal prediction. Standard conformal guarantees do not directly survive adversarial test-time perturbations, since the perturbed test input is no longer exchangeable with the clean calibration data. A common strategy is to replace the conformity score by a worst-case score over the perturbation set. Gendler et al. [ [16 ] combine conformal prediction with randomized smoothing in this way, obtaining adversarially robust coverage under ℓ 2 \ell_2 ℓ 2 perturbations. Ghosh et al. [ [17 ] propose a probabilistic variant that controls coverage for most perturbations rather than the worst case, improving the efficiency-robustness trade-off. Zargarbashi et al. [ [42 ] derive tighter robust conformal sets by bounding the worst-case change in conformity scores, covering both evasion and poisoning perturbations. Jeary et al. [ [23 ] use verifiers to obtain robust conformal guarantees, and Massena et al. [ [28 ] propose efficient robust conformal prediction through Lipschitz-bounded networks. In a smoothing-based line, Yan et al. [ [39 ] revisit randomized-smoothed conformal prediction, identifying practical validity issues and improving set efficiency. The closest recent lines are Zargarbashi et al. [2025], who show that robust conformal prediction can be obtained from a single randomly augmented sample by certifying the conformal procedure itself, and Zargarbashi and Bojchevski [ [41 ] , who use a single binary certificate for robust conformal prediction. Our work can be viewed as moving this single-sample idea from prediction sets to proxy certification. We do not construct a set that covers the true label; instead, we calibrate a proxy decision rule so that approving an unsafe perturbed input is rare. More precisely, robust conformal risk control [1 ] requires the worst-case loss over the perturbation set for every calibration point, which is itself a certification problem, and single-sample robust conformal prediction [Zargarbashi et al., 2025] controls the coverage of a prediction set. Relative to these, the new ingredients of our work are: (i) the anchored false-approval risk (Prop. 2 ), defined on the pair of received point and latent clean anchor, which lets a sound certificate evaluated only at clean calibration points serve as the calibration signal, while the guarantee holds at the perturbed test point; and (ii) adapting the single-sample argument from coverage to general bounded monotone risks, which requires the concavity of c † c^\dagger c † (Lemma 1).
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly describe the proposed framework, the conformal risk control guarantee (bounded marginal false-approval rate), both the standalone and fallback certificate use cases, and the empirical scope (vision transformers and language models). Aspirational goals are distinguished from proven guarantees.
Guidelines:
The answer [N/A] means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A [No] or [N/A] answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper includes a dedicated limitations paragraph (Fundamental limitations in § 3.4 ) that discusses the gap between marginal and instance-wise guarantees, the dependence on proxy quality, and the exchangeability assumption underlying the conformal risk control framework.
Guidelines:
The answer [N/A] means that the paper has no limitation while the answer [No] means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate “Limitations” section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results are stated with explicit assumptions (e.g., exchangeability of the calibration set). Complete proofs are provided in the appendix, with proof sketches in the main text to convey intuition.
Guidelines:
The answer [N/A] means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The calibration procedure, proxy tuning via conformal risk control, evaluation protocol, and all hyperparameter choices are described in sufficient detail in the paper and appendix. Code is also released at https://github.com/soroushzargar/ProxC.
Guidelines:
The answer [N/A] means that the paper does not include experiments.
If the paper includes experiments, a [No] answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general, releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code is publicly available at https://github.com/soroushzargar/ProxC. All experiments rely on publicly available pretrained models and standard benchmarks.
Guidelines:
The answer [N/A] means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so [No] is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results?
Answer: [Yes]
Justification: The paper specifies the calibration set sizes, risk level α \alpha α , proxy choices, and evaluation metrics. Full details are provided in the appendix.
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Variance is reported for key experiments. Variance is generally very small, which is expected given the theoretical guarantees of the conformal risk control framework, and this is noted in the paper. Guidelines:
The answer [N/A] means that the paper does not include experiments.
The authors should answer [Yes] if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates).
If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: Formal hardware specifications (GPU type: NVIDIA H100 and A100) are reported in § E.
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper).
Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?
Answer: [Yes]
Justification: The research is foundational methodology for robustness certification and conforms with the NeurIPS Code of Ethics. No human subjects, sensitive data, or dual-use concerns are involved.
Guidelines:
The answer [N/A] means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer [No], they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [N/A]
Justification: This is foundational methodology research on robustness certification without a direct path to specific deployment applications. The work improves the efficiency of existing safety tools and does not introduce new capabilities with foreseeable negative societal impacts.
Guidelines:
The answer [N/A] means that there is no societal impact of the work performed.
If the authors answer [N/A] or [No], they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)?
Answer: [N/A]
Justification: The paper does not release new models or datasets. The released code implements a post-hoc certification method applied to existing publicly available models, posing no elevated misuse risk.
Guidelines:
The answer [N/A] means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes]
Justification: All pretrained models and datasets used in the experiments are cited with references to their original papers. Their usage is consistent with their intended research purposes.
Guidelines:
The answer [N/A] means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset’s creators.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The code implementing the proposed proxy certificate framework is released at https://github.com/soroushzargar/ProxC with documentation sufficient to reproduce the experiments.
Guidelines:
The answer [N/A] means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [N/A]
Justification: The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [N/A]
Justification: The paper does not involve human subjects research and requires no IRB review.
Guidelines:
The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required.
Answer: [N/A]
Justification: LLMs appear in the paper only as one of the evaluated classifier architectures (i.e., as objects to be certified), not as a component of the proposed method. LLMs were used solely for writing assistance and proofreading, which does not require declaration per NeurIPS policy.
Guidelines:
The answer [N/A] means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.