acceptodds
Under review as a conference paper at ICLR 2027

The Geometry of Randomized Smoothing on Feasible Sets

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.

Primary area:
learning theory
Keywords:
randomized smoothing, certified robustness, adversarial robustness, certified radius, Gaussian conditioning, feasible-set constraints

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 2 reviews, above 68% of the others.
Reviewer_txqvOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies randomized smoothing when noisy samples are filtered by a fixed feasibility or confidence rule before their labels are aggregated. It shows that applying the ordinary Gaussian robustness formula to label probabilities conditional on retention can produce invalid certificates. The authors characterize when conditioning preserves Gaussian probability and divergence bounds, and connect these properties to the retention probability and conditional covariance. They also prove that conditional label probabilities alone cannot give a positive universal radius over arbitrary filters. Two valid certification routes are developed: one using joint retention-and-label probabilities, and another using a uniform covariance bound. Analytic examples and image-classification experiments illustrate both the failure of the naive substitution and improvements in certification for a fixed filtered predictor.

Critical strengths
  1. The paper identifies a certification error and makes it precise through explicit counterexamples and an impossibility result. The released-model investigation also shows that the issue can occur in an existing implementation. The joint-mass correction preserves the filtered predictor and has a finite sample procedure.

  2. The distinction between Gaussian event comparisons and divergence bounds is useful. In particular, the nonconvex example shows that conditioning can preserve useful divergence bounds even when the ordinary Gaussian probability comparison fails. The covariance-based analysis then explains how a valid conditional certificate can still be obtained.

Critical weaknesses
  1. My main concern is the practicality of the stronger geometric certificate. Proposition 9 requires a verified covariance bound throughout a neighborhood, which is a substantial additional input for a learned confidence or feasibility filter. The positive image experiment uses a specially structured projected-band filter for which this bound follows analytically. It remains unclear which practically motivated filters can obtain a useful bound without substantial additional verification. Moreover, unfiltered smoothing remains stronger even with matched model calls (Table 9), while the band filter is not tied to an independent feasibility requirement. The experiment therefore demonstrates better certification of a particular filtered predictor, but leaves its broader practical value unclear.

  2. I found the exposition difficult to follow, particularly the organization of Sections 3 and 4. The paper moves between event comparisons, divergence bounds, an exact CDF criterion, and a local covariance diagnostic before giving operation on page 7. These results serve different purposes, and the reader has to reconstruct which ones diagnose failure and which ones yield a usable certificate. The main text should also distinguish the new insights from the applications of existing tools more directly, using the comparison already provided in Appendix J.

Questions for authors
  1. Beyond the projected-band construction, which practically motivated nonconvex filters can currently obtain a useful, verified covariance bound for Proposition 9? Please explain what is needed to determine Λ\Lambda and RR, including the computational effort.

  2. What independent task or feasibility requirement motivates retaining the filter in the positive image experiment? Given that unfiltered smoothing performs better at matched model calls, a clearer account of when filtering is necessary or otherwise valuable would strengthen the practical significance. I am not asking that filtering always outperform ordinary smoothing, but that the example explain why preserving this filtered predictor is a useful objective.

1 comment

We structure our response into 1) Changes we made to address reviewer concers and 2) answering the questions.

Addressing Weaknesses

Adding covariance verification for nonconvex box unions

It remains unclear which practically motivated filters can obtain a useful bound without substantial additional verification.

We added a verifier for explicit nonconvex box unions in Section 4, Table 1, and Appendix J, with independent products in Appendix J.1. Answer 1 below explains its inputs and computational effort. Answer 2 separates the image experiment's certificate comparison from the trained-controller task requirement.

Improving clarity, organization, and attribution

These results serve different purposes, and the reader has to reconstruct which ones diagnose failure and which ones yield a usable certificate.

We clarified the roles of the results in Sections 3-4. The projected-CDF criterion characterizes event control, and local covariance diagnoses divergence behavior. Certification uses either joint masses or a covariance bound verified throughout the required neighborhood. Section 4 now states the verifier inputs and procedure alongside the examples. Moreover, Section 1 and Appendix H explicitly distinguish the conditional-law results from the convex comparison, rejection-based certification, and categorical Rényi threshold inherited from prior work.

Q&A

Question 1

Beyond the projected-band construction, which practically motivated nonconvex filters can currently obtain a useful, verified covariance bound for Proposition 9? Please explain what is needed to determine Λ\Lambda and RR, including the computational effort.

The verified family comprises explicit unions of boxes, including L-shaped workspaces, rectangular obstacle exclusions, and unequal corridors. The verifier takes the set, nominal center, noise scale, and a chosen verification radius RR. Rational cells cover the entire center ball. Outward Gaussian moment enclosures prove positive retention and bound covariance throughout every cell. The largest verified eigenvalue bound, divided by σ2\sigma^2, gives Λ\Lambda.

For a candidate radius rr at Rényi order α\alpha, choose R≥αrR\geq\alpha r and check Proposition 8, the revised numbering of Proposition 9. Increasing RR can increase both the verification cost and Λ\Lambda. The two-dimensional examples each use 4,0964{,}096 cells and take at most 0.1320.132 seconds in one CPU process, excluding imports. An exact product constraining all 3232 coordinates takes 1.921.92 seconds. Work is additive across independent blocks at fixed block dimension. Coupled constraints require joint verification. This gives a tractable geometric family, while verification of general neural confidence regions remains open.

Question 2

What independent task or feasibility requirement motivates retaining the filter in the positive image experiment? Given that unfiltered smoothing performs better at matched model calls, a clearer account of when filtering is necessary or otherwise valuable would strengthen the practical significance. I am not asking that filtering always outperform ordinary smoothing, but that the example explain why preserving this filtered predictor is a useful objective.

The band filter has no independent CIFAR feasibility requirement. We clarified in Section 5 that it makes the covariance premise analytically checkable and permits a controlled comparison of certificates for one fixed filtered predictor. Unfiltered smoothing remains stronger at matched model calls. The supported conclusion is improved certification of that filtered predictor.

The added control studies address a separate task requirement. Retention enforces zero next-step native cost for trained actors, at the observed expense of progress and possible abstention (Appendix K). These studies use joint-event certification and an offline restored-state simulator oracle.

Reviewer_85qHOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies randomized smoothing when noisy proposals are filtered and the classifier reports label probabilities conditional on retention. It shows that inserting these conditional probabilities into the radius of Cohen et al. (2019) is unsound in general, gives conditions under which conditioning preserves the Gaussian comparisons (Theorem 1, Corollary 2, Proposition 3), and gives two sound certificates: one from joint retained-label masses (Theorem 7) and one under a conditional covariance bound (Proposition 9). Experiments audit a released certificate

Critical strengths

Correctness. The main results (Theorems 1 and 7, Propositions 3, 5, 8, and 9) appear mathematically correct.

Demonstration of the failure of an existing certificate. The paper shows that a published certificate (AuditVotes, image version) can be wrong: on real images, it finds labels that change within the radius the certificate claims is safe, and confirms these cases carefully

Critical weaknesses

Several of the results follow from known work, for example Gopi et al. and earlier work on smoothing with rejection (Sheikholeslami et al.), etc. The paper acknowledges this. The new parts, mainly the analysis of when filtering breaks the standard guarantee and the audit, are useful, but the overall contribution is somewhat moderate.

An evaluation on a trained model where filtering is required would strengthen the results.

Questions for authors

see above

4 comments

Contribution and clarity

Several of the results follow from known work, for example Gopi et al. and earlier work on smoothing with rejection (Sheikholeslami et al.), etc.

We clarified the attribution in Sections 1 and 4 and Appendix H. Gopi et al. provide the convex comparison, Sheikholeslami et al. already certify the task-label argmax excluding rejection through joint masses, and Li et al. provide the categorical Rényi threshold.

We characterize when conditioning preserves event comparisons and divergence bounds, prove that these properties differ, and show why conditional votes alone cannot determine a positive universal radius. The nonconvex example in Section 4 satisfies every Gaussian-rate divergence bound while its substituted conditional radius crosses a decision boundary. The released-model audit confirms that this failure also occurs on learned predictions.

To address the presentation concern, Section 3 distinguishes characterization and local diagnostics from usable certificates. Section 4 gives the certification procedures and makes the additional inputs for covariance verification explicit, with a concrete comparison in Table 1.

Evaluation on trained controllers

An evaluation on a trained model where filtering is required would strengthen the results.

We added trained-controller evaluations in Section 5 and Appendix K. We require zero next-step native cost in SafetyPointGoal2. The fixed-state study shows that enforcing this constraint changes selected labels and permits joint-mass certification, while reducing certified progress relative to unfiltered execution.

The separate ordinary-reset study in Appendix K.1 evaluates goal completion before cost. Filtering preserves the observed Gaussian baseline's goal paths and changes costly endings primarily into abstentions. Timeouts and abstentions count as failures to complete the goal. The experiments use an offline restored-state simulator oracle and joint-event certificates.

Can the authors provide an updated document where the changes are clearly marked? We have a short time ahead of us before the deadline and this would facilitate the efforts of the referees.

Yes, of course.

Please see the updated supplementary material, which now includes the file "revision-with-diff.pdf," which highlights the changes directly.

I would like to thank the authors for the revision, their responses and the careful documentation of their updates. I will keep the overall rating at 3 (weak acceptance)

Comments on the paper

3 comments

Addressing Weaknesses

Adding covariance verification for nonconvex box unions

A covariance estimate at the nominal center does not establish this premise.

We made the uniform requirement explicit in Section 4 and added whole-neighborhood verification for box unions and independent products in Appendices J and J.1. The verifier covers the tilted centers through the R/αR/\alpha restriction in Proposition 8. Answer 1 below gives the tractable family and evidence of a useful improvement. General neural-region covariance verification remains open.

Clarifying practical scope and extending the evaluation

They constrain the practical conclusion to stronger certification of an existing filtered predictor, rather than an established reason to introduce filtering.

We adopted this scope explicitly in Section 5. Unfiltered smoothing remains stronger, including at matched model calls. The added second checkpoint and noise scale reproduce the advantage of conditional over joint-mass certification within the same architecture (Appendix I.10, Table 11). The independent reason to filter comes from the trained-controller native-cost requirement in Appendix K. Those experiments use joint-event certificates and an offline simulator oracle.

Questions for Authors

Question 1

Beyond the projected-band construction and the finite-diameter bound, can you identify a practically relevant filter family for which uniform covariance control is both verifiable and tight enough to improve on joint-mass certification? Clarifying the tractable scope would strengthen the constructive contribution, a general neural-region verifier is not required.

Explicit box unions model nonconvex workspaces, obstacle exclusions, and alternative corridors. Section 4, Table 1, and Appendix J verify covariance by enclosing Gaussian moments over every cell covering the chosen neighborhood. For unequal corridors, the verified conditional radius exceeds the joint-mass upper bound by more than 4.9%4.9\%. Joint masses remain stronger for the other two geometries, so the improvement depends on the set and decision rule.

Appendix J.1 extends verification to exact orthogonal products of independent constraints, including unbounded sets with every coordinate constrained. Their infinite diameter makes the finite-diameter bound inapplicable. Independence permits blockwise verification. Coupled constraints require a joint calculation.

Question 2

What operational decision is supported by the certified cost-avoidance event when many successful trajectories are timeouts? The distinction from task completion is stated clearly, but explaining the intended use would help assess the significance of this extension beyond the single-step results.

For a proposed perturbation budget, compare the certified lower probability of cost avoidance with an application-chosen requirement qq. If the bound meets qq, it certifies that requirement for the declared reset cohort and unchanged bounded execution. A bound below qq withholds certification and is inconclusive about actual reliability. The application must justify qq.

We clarified this decision rule in Section 5 and Appendix G.1. The original study concerns avoiding native cost until the first goal or the 500500-step horizon, using an observation-only heuristic verifier. Cost-free timeouts satisfy that event. It supports a bounded cost-avoidance requirement that permits timeouts. Goal completion requires its own event.

The separate new study in Appendix K.1 uses an offline restored-state simulator oracle and counts timeouts and abstentions as goal failures. It preserves the observed Gaussian baseline's goal paths, with no additional goals recovered by resampling. Corollary 15 and Appendix G.2 certify the joint event of goal completion using first proposals, estimated over all trials, and transfer it to the full execution assuming the stated conditions on the causal program. Physical recovery after abstention remains outside the guarantee.

Dear reviewers and area chairs,

Our heartfelt thanks for taking the time to review our paper and provide suggestions. Please excuse our rather delayed responses. Considering that the reviewer concerns were fair, actionable, and largely in agreement, we decided to directly revise the paper's weaknesses based on the provided feedback. We have addressed all concerns to the best of our ability and have uploaded the revision. The updated supplementary material includes the additional material and a file that directly highlights the revision changes.

To summarize the most relevant changes:

  • Added covariance verification for nonconvex filters. We provide a verifier for explicit box unions and independent products, checking the full required neighborhood and reporting concrete examples and computational costs.

  • Added trained-controller evaluations with an explicit safety requirement. We evaluate filtering that enforces zero next-step cost, measure goal completion separately from cost avoidance, and clarify the operational meaning of the trajectory guarantees.

  • Improved clarity, organization, and attribution. We clarify which results diagnose failures and which provide usable certificates, explain their assumptions, and distinguish our contributions from where we build on prior work.

  • Extended the image evaluation. We repeat the certificate comparison with a second checkpoint and noise scale, including the unfiltered baseline.

We provide detailed answers to the individual concerns and questions in the respective reviewer threads.

Thank you so much for addressing my concerns. I am keeping my score (3: weak acceptance).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.