Summary
This paper proposes sample-efficient methods for computing probabilistic robustness certificates for randomized smoothing. The proposed methods replace the standard Clopper-Pearson confidence interval on the classifier’s score, with a confidence sequence, thereby allowing the number of samples to be determined adaptively given a radius of certification $r$ and significance level $\alpha$. Two variants of the method are proposed: one that updates the sequence on a geometric schedule (shown to achieve the asymptotically optimal sample complexity) and another that adopts a betting strategy. The methods are shown to consume 1.5–3 times fewer samples compared to prior work (Horváth et al., 2022).
Strengths
**Originality:**
This paper imports methods from statistics/probability theory, which have not previously been applied in the context of randomized smoothing. The methods appear to be an excellent fit for improving the statistical efficiency (and hence computational efficiency) of randomized smoothing. It’s worth noting that the methods have been adapted, in that the bounds are specialized for Bernoulli random variables (rather than generic bounded random variables).
**Significance:**
The computational cost of randomized smoothing is a barrier to adoption, so it’s great to see work in this direction. The proposed algorithms for adaptively determining the sample size is relatively simple to implement which should encourage adoption.
**Quality:**
The method is well-motivated. The theory and experiments are generally well-executed, apart from some minor issues outlined below.
**Clarity:**
The writing is reasonably clear, apart from some issues discussed below.
Weaknesses
**Clarity:**
The paper is mostly clear, however some parts could be improved:
- Section 3: Definition 3.1 seems out-of-place: it’s not clear that a generic formulation of sequential decision making is needed, if the experiments focus on randomized smoothing. Section 3.1 includes some discussion of the results, but is labeled “related work”. It would be good to add a few more sentences discussing the results
- Section 2.2: I find it confusing that symmetric/asymmetric confidence sequences are discussed before confidence sequences are defined (even informally).
- Line 189: I found this paragraph confusing – I wonder if it could be explained more concretely (with an example) in an appendix.
**Impact:**
- The formulation of randomized smoothing in Section 2 covers additive smoothing mechanisms, where the certificate is an $\ell_p$-ball. I suspect the formulation could be generalized to capture non-additive smoothing mechanisms and more general certificate geometries without impacting the validity of the results.
- The proposed method is not applicable if one wants to estimate the maximum certified radius at an input. I wonder whether the method could be adapted to estimate the maximum certified radius within some tolerance.
**Minor:**
- line 24: Provide citation for claim that randomized smoothing “is currently the strongest certification method”
- line 62: “realizations **are** lowercase”
- line 77: Extraneous closing bracket
- line 88: “de-randomized” has not been defined yet. Consider defining earlier or providing a citation.
- line 92: Provide citation for claim that the Clopper-Pearson interval is “well known to be conservative”
- line 94: In what sense is the confidence interval “optimal”? In terms of coverage?
- line 121: “even” → “event”
- line 128: Is the case where u() = 0 an upper confidence interval?
- Proposition 2.4: Coverage has not been defined for a randomized confidence interval.
- line 180: Should $\in$ be $\subseteq$?
- line 247: Provide citation for Ville’s inequality
- Table 1 caption: Delete “of number of samples”
- line 324: “improved them at places” is ambiguous.
- line 328: I’m not convinced that we now have a “perfect” understanding of statistical estimation for randomized smoothing. For instance, this paper has not considered the problem of estimating the smoothed classifier’s prediction. It’s possible there may be more sample-efficient ways of estimating the smoothed classifier’s prediction and bounds on the top-2 scores jointly.
- “We stress out <some statement>” sounds unusual. It would be more natural to say “We stress <some statement>”.
Questions
- Does the method apply to the more general formulations of randomized smoothing?
- Could the method be adapted to estimate the maximum certified radius within some tolerance? This would cover another common use case.
Limitations
The limitations ought to be discussed more. For example, the experiments only cover one dataset/model, the proposed method only improves sample complexity if the radius is fixed.