The Geometry of Randomized Smoothing on Feasible Sets

Syed Izhan Khilji; Alireza Furutanpey; Schahram Dustdar

cs.LGSep 30, 2026

The Geometry of Randomized Smoothing on Feasible Sets

Authors: Syed Izhan Khilji, Alireza Furutanpey, Schahram Dustdar

Organizations: Technische Universität Wien · NeverBlink · Technische Universität Wien Universitat Pompeu Fabra

Abstract

Randomized smoothing certifies the probability of a fixed output event as the center of Gaussian noise moves. Feasibility or confidence filtering reports label probabilities only among retained proposals, producing a ratio. Its numerator is a fixed Gaussian event mass, while its denominator is the probability of retention and can change with the center. Substituting this ratio into the ordinary smoothing formula can therefore certify a ball that contains a decision boundary. We separate the problem into a geometric question and a certification question. Geometry determines when conditioning preserves Gaussian comparisons. Convex retained sets preserve the full comparison, while general sets require geometric control of the retained law as the center moves. Without such control, conditional probabilities imply no positive universal radius. Joint retention-and-label probabilities always yield a valid certificate for the same filtered predictor. A uniform covariance bound transfers divergence certificates to the retained law and can yield larger radii even when the Gaussian event comparison fails. Both methods admit finite-sample bounds. For a learned image classifier with a training-selected nonconvex filter, conditional Rényi bounds certify more images than joint-mass bounds without additional model evaluations. A released confidence filter exhibits verified label changes inside radii obtained by conditional substitution. An application of adaptive Gaussian composition covers causal finite-horizon executions with history-dependent center shifts under a pathwise energy bound.

Figures & tables

Figure 1: Normalization failure and geometry-controlled recovery. Panel A shows Proposition 5 . The conditional label changes at zero. The substituted interval crosses this boundary, while the joint-mass interval ends at it. Panel B uses the projected-band filter selected before CIFAR-10.2 access. Curves give the fraction of all test images with the correct selected label and a positive valid radius at least as large as the abscissa. Conditional Rényi and joint mass certify the same filtered predictor. Unfiltered smoothing is a separate baseline. The vertical line marks radius

0.2

Figure 2: Released-model evaluation and fixed-cohort attack. Panels A and B use all CIFAR-10 and CIFAR-10.1 v4 images with

N_{0}=100

N=10{,}000

, and

\delta=0.001

. The diagnostic conditional-substitution curve shares proposal batches with the certified calculations. Panel C includes all

128

deterministically selected images. Panel D divides twelve independently confirmed shifts by familywise lower bounds on their substituted radii. Every ratio is below one, its endpoint labels differ, and familywise error is at most

0.001

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: Compact nonconvex witness. Panel A shows the connected L-shaped support, the event

E

, and its complement

K\setminus E

. Panel B shows the tested displacement, the conditional decision boundary, and the substituted radius. The outward-certified bounds above establish the label change.

Figure 4: End-to-end radii for the nonconvex two-band family. The curves use the analytic Gaussian CDF formulas above. The points at

\delta=0.1

use the outward-certified calculation. The forward-KL radius remains close to the exact boundary and is more than twice the joint-mass radius at the certified point. The substituted conditional radius crosses the boundary.

Ctrl	Proposals	Safe	Goal	Timeout	Cost	$p_{L}$	$B_{\rm cert}$	$L_{.02}$	Shift safe
C1	one	211	78	133	45	$.694$	$.0989$	$.657$	213
C1	four	210	85	125	46	$.690$	$.0968$	$.653$	214
C2	one	187	60	127	69	$.600$	$.0495$	$.560$	180
C2	four	189	59	130	67	$.608$	$.0535$	$.568$	187
C3	one	205	107	98	51	$.670$	$.0861$	$.633$	204
C3	four	207	106	101	49	$.678$	$.0903$	$.641$	202

Appendix

Table 1: SafetyPointGoal2 trajectory evaluation. Safe is the certified event count. Goal and timeout partition that count. Cost is the nominal positive-cost count.

L_{.02}

is the familywise lower event probability at

B=0.02

. Shift safe is the descriptive count under the tested shift. C1, C2, and C3 follow the controller-seed order in the text.

Current result	Used here	Established here
Occupancy divergences	Fixed-support Rényi log-partition identities and truncated-family KL and skew-Jensen identities ( Nielsen and Nock, 2011 ; Nielsen, 2022 )	Gaussian occupancy specialization followed by the equivalence between concave log occupancy and the stated ordered-pair KL and positive-order Rényi rates
Covariance control	Log-normalizer differentiation supplies standard moment and Fisher identities	Their specialization gives the finite-path KL integral, local Rényi rate, and top-covariance diagnostic used here
Corollary 2	Strongly log-concave tradeoff comparison of Gopi et al. (2022, Theorem 13)	Intrinsic affine-hull specialization with displacement scale $\\|a-b\\|/\sigma$
Proposition 3	Neyman–Pearson ordering for the monotone likelihood ratio between two conditioned Gaussian centers	Necessary and sufficient projected-mass inequalities for every measurable retained event under an arbitrary fixed set
Theorem 7 and Algorithm 1	Joint selected-label and selected-or-rejection masses ( Sheikholeslami et al., 2022 , Theorem 3.1)	Explicit competitor bounds and their simultaneous combination with the rejection-complement bound for arbitrary fixed filters
Limits of conditional votes	The cited joint-event certificate does not provide a radius from conditional votes alone	Sharpness of the joint-mass radius and the support-free conditional-only impossibility result

Appendix

Table 2: Result-level relation to prior work. The middle column gives the earlier statement used here. The last column gives the result established in this paper.

Calculation	Positive	Median	$0.3$	$0.5$	$0.7$
Conditional substitution	$.8941$	$.6668$	$.6835$	$.6007$	$.4406$
Joint complement	$.8868$	$.3342$	$.5163$	$.3221$	$.1416$
Joint explicit	$.8872$	$.3293$	$.5114$	$.3137$	$.1323$
Joint simultaneous	$.8875$	$.3330$	$.5153$	$.3202$	$.1394$
Unfiltered Gaussian	$.9122$	$.3924$	$.5525$	$.3917$	$.2403$

Appendix

Table 3: Additional full-test results. Positive is the fraction receiving a strictly positive radius. Median is over all test images. The remaining columns are correct fractions with radius strictly above the displayed value.

Calculation	Positive	Median	$0.3$	$0.5$	$0.7$
Conditional substitution	$.8461$	$.5193$	$.5270$	$.4414$	$.2796$
Joint simultaneous	$.8362$	$.2122$	$.3449$	$.1752$	$.0643$
Joint complement	$.8362$	$.2125$	$.3459$	$.1757$	$.0663$
Joint explicit	$.8352$	$.2095$	$.3414$	$.1707$	$.0579$
Unfiltered Gaussian	$.8733$	$.2503$	$.3909$	$.2395$	$.1192$

Appendix

Table 4: Full CIFAR-10.1 v4 results. Positive is the fraction receiving a strictly positive radius. Median is over all

2{,}021

images. The remaining columns are correct fractions with radius strictly above the displayed value.

Cohort	ID	labels	$\\|\Delta\\|_{2}$	$r_{L}$	$\\|\Delta\\|_{2}/r_{L}$	nominal	shifted
3	174	$6\to 2$	$.1641$	$.1852$	$.886$	$57.47$	$18.19$
11	1586	$3\to 2$	$.3205$	$.3707$	$.864$	$88.38$	$29.30$
15	879	$2\to 6$	$.2744$	$.2912$	$.942$	$77.59$	$29.93$
16	1060	$7\to 4$	$.4674$	$.4739$	$.986$	$94.80$	$23.82$
19	759	$1\to 9$	$.2920$	$.3014$	$.969$	$78.27$	$5.80$
37	215	$0\to 9$	$.1325$	$.1496$	$.885$	$47.36$	$3.88$

Appendix

Table 5: Fresh confirmation for every positive screen in the fixed cohort. The last two columns give the declared winner’s advantage over the other listed label as a percentage of all retained proposals. Every row is verified.

ID	labels	$\\|\Delta\\|_{2}$	$r_{L}$	nominal counts	shifted counts	verified
4924	$7\to 5$	$.4577$	$.5097$	$52295/965$	$7182/17611$	yes
5089	$6\to 3$	$.3116$	$.3585$	$32339/2345$	$9196/17483$	yes
8654	$2\to 3$	$.3316$	$.4141$	$8736/358$	$2052/4782$	yes
6665	$4\to 3$	$.2843$	$.3685$	$18244/1172$	$5741/7099$	yes
634	$7\to 4$	$.3068$	$.4013$	$36793/1873$	$11556/12135$	no
5211	$7\to 3$	$.2570$	$.3775$	$27299/1245$	$7754/7157$	no

Appendix

Table 6: Independent endpoint confirmation. Count pairs give original-label and alternative-label retained counts among one million proposals. A verified row has both declared endpoint winners and a shift below

r_{L}

Threshold	$0$	$.5$	$.7$	$.8$	$.85$	$.9$	$.925$	$.95$	$.975$
Dev	$.400$	$.395$	$.376$	$.355$	$.344$	$.324$	$.308$	$.283$	$.240$
Confirm	$.399$	$.394$	$.376$	$.358$	$.343$	$.320$	$.304$	$.279$	$.237$
Retained	$1.000$	$.876$	$.698$	$.607$	$.555$	$.493$	$.455$	$.407$	$.338$

Appendix

Table 7: Threshold selection. Dev and confirm are mean explicit-joint certified accuracies over the three declared radii. Retained is the mean confirmation proposal fraction.

Figure 5: Product-box study. Panel A finds ten covariance-direction KL ratios above one from five base geometries. The maximum is $1.0448$ , and no independent-direction ratio exceeds one. Every fixed-anchor control in Panel B stays below one. The study does not estimate prevalence.

Figure 6: Held-out covariance replication. Panel A compares anchor directional covariance and finite KL over all $1{,}024$ factor rows. The diagonal is equality and dotted lines mark the Gaussian rate of one. Panel B shows the signed finite-minus-anchor ratio, exposing the finite-scale discrepancy hidden by the near-diagonal scatter. Twenty-seven repeated top-covariance rows from $14$ base geometries exceed one. No independent row does. The $128$ base geometries, not factor rows, are the independent analysis units. Direct KL and the path integral agree within $1.77\times 10^{-15}$ .

Class	Retained	F-acc	U-acc	KL	Joint	Strong
airplane	$.420$	$.505$	$.505$	$.280$	$.250$	$26$
automobile	$.418$	$.640$	$.640$	$.420$	$.385$	$35$
bird	$.437$	$.505$	$.510$	$.275$	$.210$	$34$
cat	$.424$	$.545$	$.540$	$.250$	$.190$	$44$
deer	$.432$	$.585$	$.585$	$.340$	$.275$	$34$
dog	$.415$	$.660$	$.655$	$.490$	$.420$	$34$

Appendix

Table 8: CIFAR-10.2 results by class. Retained is the mean estimation-stream fraction. F-acc and U-acc are filtered and unfiltered selected-label accuracy. KL and Joint are correct certified fractions at radius

0.2

in the original forward-KL analysis. Strong counts correct images whose forward-KL lower radius exceeds the joint-mass upper radius by at least

0.01

Certificate	$r\geq 0.2$	$r\geq 0.3$	$r\geq 0.5$
Conditional forward KL	$829$	$0$	$0$
Conditional reverse KL	$888$	$698$	$329$
Conditional Rényi	$892$	$713$	$381$
Joint mass	$725$	$417$	$0$
Unfiltered, original	$948$	$814$	$529$
Unfiltered, matched calls	$945$	$806$	$522$

Appendix

Table 9: Correctly certified CIFAR-10.2 images out of

2{,}000

. All filtered methods use identical counts and selected labels. The unfiltered predictor uses its separate original streams. Matched calls uses a random subset of those streams with the same model-call count as the filtered methods.

Figure 7: Conditional divergence certificates on the retained CIFAR-10.2 counts. Panel A includes all

2{,}000

images and displays the forward-KL ceiling and its removal by reverse KL. Panel B shows all

1{,}084

correctly selected labels with finite paired bounds. Green points have a conditional Rényi lower radius at least

0.01

above their joint-mass upper radius. The dashed diagonal denotes equality.

Explore similar work

Jun 1, 2026cs.LG

RRISE: Robust Radius Inference via a Surrogate Estimator

Randomized smoothing (RS) uses a smoothed classifier to provide architecture-agnostic certificates of

\ell_2

classification robustness, but its dependence on per-input Monte Carlo (MC) sampling undermines its use in real-time systems. We argue that this cost is structural rather than fundamental, such that it can be significantly reduced by sharing information across the deployment stream. We introduce RRISE, an RS framework that compresses certification into a single forward pass through a learned surrogate. RRISE trains the surrogate against precomputed MC class-count targets via a soft-label cross-entropy loss and converts surrogate predictions into provably conservative certified radii through a one-time conformal calibration step. The resulting certificate is deployment-verifiable: whenever the calibrated radius is positive, the surrogate's prediction provably matches the smoothed classifier's and the smoothed classifier is constant on a ball of that radius around the input. Across image classification benchmarks, RRISE matches fixed-budget MC certified accuracy within

0.84

percentage points while replacing up to

10^4

noisy base-model evaluations per query with a single surrogate forward pass, recouping MC training cost after

\approx 10^5

deployment queries. On CIFAR-100 and Tiny ImageNet, where the only prior offline-surrogate method collapses, RRISE achieves

1.23

1.91\times

higher certified accuracy, establishing efficient randomized smoothing as a practical path to certified robustness in repeated-deployment settings.

Jong-Ik Park, Shreyas Chaudhari, Carlee Joe-Wong +1

Carnegie Mellon University

Smoothing Machine Learning Surrogates Conformal Risk Control Random Certificates Cross-Entropy Losses

Ask PDF

May 13, 2026cs.LG

Certified Robustness under Heterogeneous Perturbations via Hybrid Randomized Smoothing

Randomized smoothing provides strong, model-agnostic robustness certificates, but existing guarantees are limited to single modalities, treating continuous and discrete inputs in isolation. This limitation becomes critical in multimodal models, where decisions depend on cross-modal semantics and adversaries can jointly perturb heterogeneous inputs, rendering unimodal certificates insufficient. We introduce a unified randomized smoothing framework for mixed discrete--continuous inputs based on an analytically tractable Neyman--Pearson formulation of the joint worst-case problem. By analyzing the joint likelihood ordering induced by factorized discrete and continuous noise, our approach yields a closed-form, one-dimensional certificate that strictly generalizes both Gaussian (image-only) and discrete (text-only) randomized smoothing. We validate the framework on multimodal safety filtering, providing, to our knowledge, the first model-agnostic Neyman--Pearson certificate for joint discrete-token and continuous-image perturbations in interaction-dependent text--image safety filtering.

Blaise Delattre, Hengyu Wu, Paul Caillon +2

Department of Computer Science, School of Computing, Institute of Science Tokyo, Tokyo, Japan · PSL University, Paris, France · College of Computing and Data Science, Nanyang Technological University, Singapore

Smoothing Robustness Verification Safety Filters

Ask PDF

Apr 27, 2026cs.LG

Laplace-Bridged Randomized Smoothing for Fast Certified Robustness

Randomized Smoothing (RS) offers formal

\ell_2

guarantees for arbitrary base classifiers but faces two key practical bottlenecks: (i) it often relies on noise-augmented training to achieve nontrivial certificates, which increases training cost, can reduce clean accuracy, and weakens RS as a genuinely post-hoc defense; and (ii) certification is computationally expensive, typically requiring tens of thousands of noisy forward passes per input, which hinders deployment, especially on resource-constrained edge devices. To address both limitations, we propose Laplace-Bridged Smoothing (LBS), an analytic reformulation of RS that replaces high-dimensional input-space Monte Carlo (MC) sampling with efficient computations in a low-dimensional probability space. LBS preserves formal robustness guarantees without requiring noise-augmented training while substantially reducing certification burden. On CIFAR-10 and ImageNet, LBS attains stronger certified robustness than RS and reduces per-sample certification cost by nearly an order of magnitude. Notably, on NVIDIA Jetson Orin Nano and Raspberry Pi 4, LBS achieves speedups of up to

494\times

, enabling practical certified deployment on real-world edge devices. Finally, we provide theoretical justification for the analytic formulation and certificate validity of LBS.

Miao Lin, MD Saifur Rahman Mazumder, Feng Yu +2

Department of Computer Science, Old Dominion University, Norfolk, VA, USA · Department of Mathematical Sciences, University of Texas at El Paso, El Paso, TX, USA · School of Cybersecurity, Old Dominion University, Norfolk, VA, USA

Smoothing Noise-Aware Privacy-Preserving Machine Learning Certification Imagenet Monte Carlo

Ask PDF