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
this https URL

提出一种新的 Second-order Smoothing (SoS) 方法，计算基于高斯随机采样函数的最近对抗例的距离下界，证明该证书的正确性且具有实现性。同时，提供一种高效的基于高斯 dipole 随机采样函数的证书计算方法，并在 CIFAR-10 和 ImageNet 等高维数据集上取得了略微提高的鲁棒性证书。