- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper claims a way (ContRS) to extend randomized smoothing from categorical model outputs to continuous-output tasks. It selects the center of an output neighborhood with the largest probability mass and derives a certified input radius for a prescribed output tolerance. Experiments compare ContRS with center smoothing and safe region certification across several prediction tasks.
Critical strengths
- ContRS considers several output distances, making the method applicable across structured-output tasks.
Critical weaknesses
-
The claimed research gap in the introduction part is overstated. For example, existing percentile-smoothing bounds can be inverted to obtain a certified input radius for a prescribed output tolerance. Given certified bounds for , any satisfying and certifies the desired tolerance . Likewise, the center-smoothing guarantee gives , where , since this ball retains majority mass under perturbation and the center-smoothing bounds the output change by . According to these, the stated certification problem is a straightforward corollary of existing smoothing guarantees. Thus I find the claimed research gap unconvincing.
-
The theoretical novelty beyond existing smoothing certificates is insufficiently established. In the metric and relaxed-triangle settings, ContRS reuses the Gaussian radius formula of safe region, and the paper attributes its improvements to output-region selection. This further suggests that the contribution lies in the predictor and region-selection strategy rather than a new radius calculation.
Questions for authors
-
Why does directly inverting existing percentile- or center-smoothing bounds not solve your stated research problem?
-
Does ContRS still outperform safe region when the target probability of the baseline is tuned rather than fixed at ?
8 comments
Response to Reviewer Comments (Part 2)
Second, certification via competing neighborhoods. Theorem 4.1 treats outputs whose discrepancy from the original prediction exceeds the prescribed tolerance as competing centers. It compares the probability mass of the original prediction’s neighborhood with the supremum of the masses of all competing neighborhoods. When the former exceeds the latter, this probability gap yields a certified input radius within which the prediction recomputed after an input perturbation remains within the prescribed tolerance of the original prediction. This analysis extends class-probability comparisons in classical random smoothing to neighborhood-probability comparisons for continuous outputs. It does not require the original neighborhood to contain more than half of the probability mass, and the discrepancy need not be symmetric or satisfy a triangle inequality.
Third, finite-sample certification guarantees. Corollary 4.2 shows that a center selected from finitely many samples can support valid certification of the population smoothed prediction defined by maximizing neighborhood probability mass, even when the selected center is not globally optimal over the output space. Specifically, center selection and probability estimation use independent samples. If the lower confidence bound on the selected neighborhood’s probability mass exceeds one half, the relevant geometric conditions yield a certified input radius. With the prescribed confidence, the following holds simultaneously for every perturbation within that radius: the perturbed population prediction remains within tolerance of both the original population prediction and the selected sample center. This guarantee requires neither exact optimization over the entire output space nor convergence of the sampled center to a population optimum; it follows from the probability mass of the selected neighborhood.
[1] Cohen, J., Rosenfeld, E., Kolter, J. Z. Certified Adversarial Robustness via Randomized Smoothing. ICML, 2019.
Q3: Why does directly inverting existing percentile- or center-smoothing bounds not solve your stated research problem?
Re: Thank you for this question. Direct inversion can indeed yield a certified input radius for a prescribed output tolerance in the settings covered by existing percentile and center smoothing guarantees. The distinction we intend to emphasize concerns how the smoothed prediction is constructed and certified, rather than whether an input radius can be obtained by inversion.
For percentile smoothing, inversion directly provides the desired tolerance certificate for scalar outputs. For vector outputs, it also applies when the coordinate-wise bounds can be combined into a valid bound under the desired output discrepancy. However, this requires relating the coordinate representation and its interval bounds to that discrepancy. For variable-length or unordered structured outputs, constructing a consistent coordinate representation and deriving such a bound may require task-specific design and analysis [2]. Moreover, relying on coordinate-wise intervals may overlook joint constraints among output components, leading to conservative variation bounds and smaller certified input radii. Inverting the bounds does not remove these representation requirements or make the bounds on output variation tighter. ContRS instead selects the center whose output neighborhood has the largest probability mass, with the neighborhood defined by the chosen discrepancy and prescribed tolerance. This aligns prediction aggregation with the allowed output variation and enables certification to directly bound the discrepancy between the original and perturbed smoothed predictions.
For center smoothing, inversion can yield a valid certified input radius, but it retains the center of the smallest ball containing at least half of the output probability mass. This center need not capture the greatest probability mass at the neighborhood radius determined by the prescribed output tolerance, which can limit the resulting certified input radius. In contrast, ContRS fixes the neighborhood radius according to that tolerance and selects the center with the largest neighborhood probability mass.
Specifically, for the same base predictor, noise level, discrepancy, and output tolerance , let , where for metric outputs, and define
By construction, . Therefore, when , the corresponding population majority certificates satisfy
=\sigma\Phi^{-1}(p_*) \ge \sigma\Phi^{-1}(p_{\mathrm{CS}}) =R_{\mathrm{CS}}^{\mathrm{inv}}.$$Response to Reviewer Comments (Part 3)
The inequality is strict whenever . Thus, ContRS maximizes this particular population majority certificate at the fixed neighborhood radius, while inversion of center smoothing preserves the original center. The certification benefit comes from optimizing the probability mass entering the shared Gaussian formula.
In summary, inversion answers how to certify an existing smoothed prediction at a prescribed tolerance. However, inversion does not optimize prediction aggregation or center selection, and the resulting bounds may remain conservative. ContRS instead sets the neighborhood radius according to the prescribed tolerance and selects the center whose neighborhood has the largest probability mass to improve certificate tightness.
[2] Kumar, A., Goldstein, T. Center Smoothing: Certified Robustness for Networks with Structured Outputs. NeurIPS, 2021.
Q4: Does ContRS still outperform safe region when the target probability of the baseline is tuned rather than fixed at p=0.55?
Re: Thank you for this question. Our choice of follows the original setting used by safe region in its comparison with center smoothing. To examine sensitivity to this choice, we additionally evaluate a higher target probability, , across all three tasks, using . For each input and noise setting, let denote the radius of the output ball selected by safe region at . We set the ContRS output tolerance to , so its neighborhood radius equals . We report certified input radii and smoothing errors. Larger radii and smaller smoothing errors are better.
Comparison of certified input radii between ContRS and safe region at matched output neighborhood scales.
| Task | Method | |||||
|---|---|---|---|---|---|---|
| Face Detection (Jaccard Distance) | safe region | 0.1081 | 0.1486 | 0.2457 | 0.3522 | 0.5066 |
| ContRS | 0.2328 | 0.3781 | 0.6832 | 0.7496 | 0.6498 | |
| Image Reconstruction (Perceptual Distance) | safe region | 0.0977 | 0.1220 | 0.1467 | 0.1715 | 0.1959 |
| ContRS | 0.1885 | 0.2360 | 0.2806 | 0.3283 | 0.3698 | |
| Image-Text Retrieval (Cosine Distance) | safe region | 0.0970 | 0.1221 | 0.1462 | 0.1710 | 0.1950 |
| ContRS | 0.1770 | 0.2192 | 0.2664 | 0.3091 | 0.3352 |
Comparison of smoothing errors between ContRS and safe region at matched output neighborhood scales.
| Task | Method | |||||
|---|---|---|---|---|---|---|
| Face Detection (Jaccard Distance) | safe region | 0.0972 | 0.1209 | 0.1625 | 0.2403 | 0.3486 |
| ContRS | 0.0852 | 0.1001 | 0.1220 | 0.1365 | 0.1706 | |
| Image Reconstruction (Perceptual Distance) | safe region | 0.0007 | 0.0013 | 0.0021 | 0.0031 | 0.0042 |
| ContRS | 0.0007 | 0.0013 | 0.0021 | 0.0030 | 0.0041 | |
| Image-Text Retrieval (Cosine Distance) | safe region | 0.1933 | 0.2469 | 0.2892 | 0.3231 | 0.3517 |
| ContRS | 0.1920 | 0.2460 | 0.2892 | 0.3226 | 0.3516 |
In general, ContRS achieves larger certified input radii in all 15 evaluated task and noise configurations. Its smoothing error is lower in 11 configurations and equal at the reported precision in the remaining four. These results show that the observed certification benefits persist across three tasks.
Response to Reviewer Comments (Part 1)
Thank you for your time and feedback on our work. We have provided detailed, point-by-point responses to the issues and questions you raised. We have also added clarifications in Introduction and at the end of Method in the revised PDF. We hope these responses and revisions address your concerns and clarify our motivation and contributions.
Q1: The claimed research gap in the introduction part is overstated. The stated certification problem is a straightforward corollary of existing smoothing guarantees.
Re: Thank you for your suggestion. We would like to further clarify the motivation of our work. Our key point is not that existing extensions of randomized smoothing cannot derive certified input radii by inverting or converting their guarantees. Rather, their output representations, aggregation criteria, and certification targets can impose limitations on cross-task applicability and certificate tightness. These limitations are not removed simply by inverting an existing bound.
For percentile smoothing, handling variable-length or unordered structured outputs typically requires constructing a consistent coordinate representation and translating coordinate-wise intervals into a bound on overall output variation. This requires task-specific design and analysis. Moreover, relying on coordinate-wise bounds may overlook joint constraints among output components, leading to conservative variation bounds and smaller certified input radii.
For center smoothing, inversion can provide a certified input radius for a prescribed output tolerance, but it does not change the prediction center. The center is still chosen as the center of the smallest ball containing at least half of the output probability mass. When the ball radius is fixed according to the prescribed tolerance, this center may capture less probability mass than another center. Consequently, the corresponding majority-based certificate is sub-optimal.
Thus, the key distinction lies not merely in deriving a certified input radius from an output tolerance, but in incorporating the prescribed tolerance into prediction aggregation and certification analysis to obtain tighter certificates. Guided by this principle, ContRS extends randomized smoothing to continuous outputs and offers a new approach to robustness certification that goes beyond a straightforward corollary of existing smoothing guarantees.
Q2: The theoretical novelty beyond existing smoothing certificates is insufficiently established. This further suggests that the contribution lies in the predictor and region-selection strategy rather than a new radius calculation.
Re: Thank you for this comment. We would like to clarify that the Gaussian radius formula is an established tool in classical randomized smoothing for deriving certified input radii from probability bounds. Both center smoothing and safe region build on Gaussian probability bounds derived from the Neyman–Pearson lemma [1], using their respective prediction constructions and certification analyses to establish robustness guarantees. Sharing this common analytical tool therefore does not, by itself, imply a lack of theoretical novelty. Building on the same foundation, our main theoretical contribution is to incorporate the prescribed output tolerance directly into the definition of the smoothed prediction and establish the corresponding population stability conditions and finite-sample certification guarantees, as detailed below.
First, definition of the smoothed prediction. ContRS incorporates the prescribed output tolerance into its prediction definition to improve certificate tightness: it sets the neighborhood radius according to the allowed output variation, then selects the center whose neighborhood has the largest probability mass. This construction extends the single-label events used in classical classification smoothing to events defined by output neighborhoods, aggregating probability mass across nearby outputs to define predictions in continuous output spaces. For discrete labels equipped with the discrete distance, these neighborhoods reduce to single-label events, recovering classical randomized smoothing. Thus, the output tolerance directly informs prediction aggregation and provides the basis for subsequent stability analysis and certification.