Abstain-or-Correct Certificates for Smoothed Classifiers Under ℓ∞ Attacks

A classifier that is allowed to say "I don't know" does not need the same robustness guarantee as one that must always answer. If an attacker nudges an input, a forced-choice model is safe only if its label does not change. A model that can abstain is also safe if it switches to abstaining, because abstention means handing the case to a human at a known cost. Existing certified defenses based on randomized smoothing ignore this distinction. Randomized smoothing means classifying many noisy copies of an input and taking the majority vote, which yields a provable radius within which the vote cannot flip. These methods certify that the label never changes, and they treat abstention as a sampling failure rather than as a decision. This note proposes certifying the weaker property that actually matters for deferral systems: within the threat ball, the model either returns the original label or abstains, and it never confidently returns a different label. For the Gaussian case this property has a closed form. With an acceptance threshold of τ = 0.9 it extends the certified radius by about 1.28σ beyond the standard one, where σ is the noise scale. We then pair it with smoothing distributions shaped to the ℓ∞ hypercube, which is the threat model where ordinary Gaussian smoothing performs worst.

The second half of the proposal turns per-input certificates into a population guarantee. Selective risk is the error rate on the inputs the model chooses to answer. We give a calibrated upper bound on selective risk under attack, and a calibrated lower bound on coverage under attack, which guards against an attacker forcing mass abstention. Both are fit on held-out clean data in the style of selection-with-guaranteed-risk. We deliberately use one fixed noise distribution for all inputs, not one tuned per input. This keeps the guarantee sound without the memory banks that data-dependent smoothing needs, and so avoids the conflict between those memory banks and the statistical calibration that selective prediction relies on.

Core Claim

Write $p_c(x)$ for the probability that the base network predicts class $c$ on $x + \delta$, where the noise $\delta$ is drawn from a fixed distribution $\mu$. The smoothed selective classifier outputs class $c$ only when a high-confidence lower bound on $p_c(x)$ is at least $\tau > 1/2$, and abstains otherwise. Let $A$ be the top class at $x$. Every other class then has probability at most $1 - p_A(x)$. An attacker can make the model output a wrong label at a perturbed point $x'$ only by raising some rival class from at most $1-p_A$ up to $\tau$.

The Neyman–Pearson argument used throughout randomized smoothing gives the worst-case growth $Q_v(q)$ of a set's noise probability, starting from probability $q$, when the input is shifted by $v$. The abstain-or-correct certificate at threat level $\epsilon$ is therefore

$$ \sup_{\|v\|\le\epsilon} Q_v\big(1-p_A(x)\big) < \tau . $$

For isotropic Gaussian noise of scale $\sigma$ and the ℓ2 norm, $Q_v(q)=\Phi(\Phi^{-1}(q)+\|v\|_2/\sigma)$, where $\Phi$ is the standard normal distribution function. The certified radius becomes

$$ R_{\text{sel}}=\sigma\big(\Phi^{-1}(p_A)+\Phi^{-1}(\tau)\big), $$

compared with $\sigma\,\Phi^{-1}(p_A)$ for label invariance. The certificate holds even at clean points where the model abstains, so it also covers inputs that would otherwise count as certification failures.

The open and substantive question is what happens away from the Gaussian/ℓ2 case. Here the certificate depends on the upper tail of $Q_v$, from $1-p_A$ up to $\tau$, rather than on its behaviour near 1/2. We hypothesize that the noise shape that maximizes the abstain-or-correct radius under ℓ∞ is different from the shape that maximizes ordinary ℓ∞ radii. If true, geometry alignment and selective prediction are coupled in a way neither literature has examined.

Relation to Prior Work

Three papers motivate the gap. Certifying Confidence via Randomized Smoothing certifies lower bounds on smoothed softmax confidence under isotropic Gaussian noise and the ℓ2 norm. It does not certify the asymmetric accept-or-abstain property, define a risk–coverage guarantee, or go beyond ℓ2. Adversarially Robust Conformal Prediction smooths conformal scores to keep 90% set coverage under ℓ2 attack. It outputs label sets rather than point predictions with abstention, and it names ℓ1 and ℓ∞ as unsolved. One Sample is Enough to Make Conformal Prediction Robust makes that setting cheap with a single noisy pass, but it remains isotropic and set-valued.

Certify or Predict is the nearest architectural relative. It routes inputs between a deterministically certified network and an accurate uncertified one. Rejected inputs receive uncertified answers instead of being deferred, and its deterministic bounds limit how large a network it can handle.

Two lines constrain the design. Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness shows that i.i.d. noise loses ℓ∞ radius as $1/\sqrt{d}$, where $d$ is input dimension. Our certificate does not escape this rate; it improves the constant through τ and through the noise shape, and we say so plainly. Data Dependent Randomized Smoothing, ANCER and RANCER obtain large gains with per-input noise, but they need memory-based conflict clipping that breaks exchangeability. That is why we restrict ourselves to noise that is fixed globally, or at most learned once on training data.

Three works supply the method. Randomized Smoothing of All Shapes and Sizes provides the Wulff-crystal shape matching. Black-Box Certification with Randomized Smoothing provides mixed-norm and centripetal ℓ∞ distributions and the functional-optimization bounds on $Q_v$. UniCR provides automated search over noise families, which we redirect toward the selective objective. Selective Classification for Deep Neural Networks supplies the binomial calibration that converts per-point certificates into population bounds.

Finally, Hidden Cost of Randomized Smoothing shows that smoothing erases small decision regions: ship 68% versus cat 22% on CIFAR-10 at σ=1, and more than 75% of ImageNet classes at 0% at σ=0.5. This bears directly on whether abstention harms some classes far more than others.

Research Program

The first component is a certificate engine. It computes $\sup_{\|v\|_\infty\le\epsilon}Q_v(q)$ in the upper-tail regime for four noise families: product uniform (cube), generalized Gaussian, the mixed-norm/centripetal family, and isotropic Gaussian with ℓ2-to-ℓ∞ conversion as a reference. It uses closed forms where they exist and the functional-optimization lower bounds otherwise. All bounds are made sound for Monte Carlo estimation by accepting only when a Clopper–Pearson lower bound clears τ.

The second component is a noise-shape study. For each family we search shape parameters to maximize two objectives, the average abstain-or-correct radius at a fixed clean coverage and the ordinary average certified radius, and compare the optima. A gap between the two optimal shapes is the main scientific result we are looking for.

The third component is the population guarantee. On a calibration set, each point is labelled "attack-safe" (the certificate holds and the clean label is correct, or the certificate holds and the point is abstained) and "attack-accepted" (the acceptance lower bound stays at or above τ over the whole ball). Binomial bounds then give, with probability at least $1-\delta$, an upper bound on adversarial selective risk and a lower bound on adversarial coverage at each τ. Sweeping τ produces a certified risk–coverage curve.

The fourth component is a per-class audit of where abstentions fall, to test whether abstention converts the shrinking phenomenon's silent errors into deferrals or simply hides those classes.

Baselines

The naive reference point is the base network with softmax-response thresholding and no smoothing, calibrated with selection-with-guaranteed-risk as in Selective Classification for Deep Neural Networks. That paper reports 1% error at 78% coverage on clean CIFAR-10. Under a PGD attack that targets both the label and the confidence, we expect its selective risk to blow up. This baseline shows what is lost by having no certificate at all.

The most direct competitor is standard certify-or-abstain smoothing. It uses the same base network, noise, and sample budget, but abstains whenever the label-invariance radius falls below ε. Our certificate contains it as a special case, so it is also the ablation that isolates our key ingredient, the asymmetric certificate. Beating it means a higher certified attack-safe fraction at matched clean coverage and matched τ.

A second ablation uses isotropic Gaussian noise with our asymmetric certificate and ℓ2-to-ℓ∞ conversion. Comparing it with geometry-aligned noise isolates the noise-shape contribution. As a scale reference, RANCER reports 56% certified accuracy for isotropic smoothing at ℓ2 radius 0.25 on CIFAR-10.

The strongest existing system with a certified selection component on ℓ∞ is ACE from Certify or Predict. It reports 90.1% natural accuracy with 27.5% certified robustness at ε=2/255 on CIFAR-10, and 80.1% with 10.5% at 8/255. We compare at its operating points. Beating ACE means a larger certified attack-safe fraction at equal or higher clean accuracy on answered inputs, at ε=2/255 and 8/255. The comparison is somewhat apples-to-oranges, since ACE never abstains, so we report both its numbers and ours under an abstention-counts-as-safe accounting.

We also include RSCP converted to selection. It abstains unless the robust conformal set has exactly one label, at matched nominal risk. Its paper reports 90% coverage maintained under ℓ2 attack, compared with roughly 45% for vanilla conformal prediction. No reported ℓ∞ result was found on Lacuna for RSCP.

All smoothed methods share one ResNet backbone trained with matched noise augmentation, the same sample counts (100 for selection, 10,000 for estimation), the same failure probability, and an equal hyperparameter search budget over σ or shape parameters.

Why not just…?

Why not just abstain whenever the ordinary certified radius is below ε? This is the strongest alternative, and our certificate reduces to it as τ approaches 1/2. The Gaussian closed form says the gain is an additive σΦ⁻¹(τ). The open question is whether that gain survives the upper-tail behaviour of ℓ∞-shaped noise; uniform noise, for example, has light tails. The matched-coverage comparison settles this directly. If the gain is negligible under ℓ∞, the result reduces to a negative finding about geometry, and we would report it as such.

Why not just use isotropic Gaussian smoothing and convert ℓ2 radii to ℓ∞? Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness shows this conversion loses a √d factor. However, every i.i.d. family has the same rate, so on CIFAR-10 the constant may favour Gaussian. The isotropic-asymmetric ablation tests exactly this, on CIFAR-10 and on ImageNet where d is larger.

Why not just threshold robust conformal sets to singletons? This yields a certified selective classifier for free under ℓ2, which makes it a genuine threat there. It does not yet exist for ℓ∞ (Adversarially Robust Conformal Prediction). It also guarantees marginal coverage of sets rather than risk on answered inputs, so its singleton rate can be low. We run it under ℓ2, where it is defined, to check that our method is competitive on that home ground.

Why not just use a deterministic certified selector like ACE? The reported certified robustness of 10.5% at 8/255 on CIFAR-10 and 3.1% on ImageNet200 at 1/255 (Certify or Predict) suggests that deterministic bounds cap the achievable safe fraction. Our comparison at those operating points tests whether smoothing does better.

Proposed Experiments

The main experiments run on CIFAR-10 and CIFAR-100 at ℓ∞ ε ∈ {2/255, 4/255, 8/255}, and on ImageNet (ResNet-50) at ε=1/255, with ℓ2 runs as a sanity check against closed forms. The primary outputs are certified adversarial risk–coverage curves with their attack-safe and attack-coverage bounds. Secondary outputs are per-class abstention and error rates, reported against the shrinking-phenomenon numbers, and empirical attacks against the smoothed selector that target both wrong acceptance and forced abstention, to verify that the bounds are never violated.

Three results would be decisive. First, the asymmetric certificate must beat certify-or-abstain at matched coverage under ℓ∞, not only under ℓ2. Second, the noise shape that is optimal for the selective objective must measurably differ from the shape that is optimal for ordinary radii; if the optima coincide, the coupling claim fails. Third, the per-class audit must show that the extra coverage is not bought by permanently deferring the small classes that smoothing already erases. If abstentions concentrate on those classes, we would report that as a fairness cost of certified deferral, not hide it.