# Tight Second-Order Certificates for Randomized Smoothing

arXiv: https://arxiv.org/abs/2010.10549 · HTML: https://mlsanity.com/paper/2010.10549/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2020.

## Built on by (most cited first, 10 of 10)

- [Double Sampling Randomized Smoothing](https://mlsanity.com/paper/2206.07912/) (2022)
- [Center Smoothing: Certified Robustness for Networks with Structured Outputs](https://mlsanity.com/paper/2102.09701/) (2021)
- [Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks](https://mlsanity.com/paper/2301.02039/) (2023)
- [Hierarchical Randomized Smoothing](https://mlsanity.com/paper/2310.16221/) (2023)
- [Invariance-Aware Randomized Smoothing Certificates](https://mlsanity.com/paper/2211.14207/) (2022)
- [Rethinking Randomized Smoothing from the Perspective of Scalability](https://mlsanity.com/paper/2312.12608/) (2023)
- [Towards Evading the Limits of Randomized Smoothing: A Theoretical Analysis](https://mlsanity.com/paper/2206.01715/) (2022)
- [Towards Large Certified Radius in Randomized Smoothing using Quasiconcave Optimization](https://mlsanity.com/paper/2302.00209/) (2023)
- [General Lipschitz: Certified Robustness Against Resolvable Semantic Transformations via Transformation-Dependent Randomized Smoothing](https://mlsanity.com/paper/2309.16710/) (2023)
- [Self-Review Reinforcement Learning (SRRL) with Cross-Episode Memory and Policy Distillation](https://mlsanity.com/paper/2607.05541/) (2026)

## Abstract (arXiv)

Randomized smoothing is a popular way of providing robustness guarantees against adversarial attacks: randomly-smoothed functions have a universal Lipschitz-like bound, allowing for robustness certificates to be easily computed. In this work, we show that there also exists a universal curvature-like bound for Gaussian random smoothing: given the exact value and gradient of a smoothed function, we compute a lower bound on the distance of a point to its closest adversarial example, called the Second-order Smoothing (SoS) robustness certificate. In addition to proving the correctness of this novel certificate, we show that SoS certificates are realizable and therefore tight. Interestingly, we show that the maximum achievable benefits, in terms of certified robustness, from using the additional information of the gradient norm are relatively small: because our bounds are tight, this is a fundamental negative result. The gain of SoS certificates further diminishes if we consider the estimation error of the gradient norms, for which we have developed an estimator. We therefore additionally develop a variant of Gaussian smoothing, called Gaussian dipole smoothing, which provides similar bounds to randomized smoothing with gradient information, but with much-improved sample efficiency. This allows us to achieve (marginally) improved robustness certificates on high-dimensional datasets such as CIFAR-10 and ImageNet. Code is available at https://github.com/alevine0/smoothing_second_order.