The full proof is given in Appendix REF  and the lower bound analogue is given in Appendix REF .
We now make some general observations about this result.
The bound (REF ) presents a pointwise guarantee in the sense that it upper bounds the distributional worst-case risk for a particular model \(\ell (\cdot )\) .
This is in contrast to bounds which hold uniformly for an entire model class and necessarily introduce complexity measures such as covering numbers and VC-dimension which are hard to compute for many
practical problems.
Other techniques which yield a pointwise robustness certificate of the form (REF ), typically express the uncertainty set as a Wasserstein ball around the distribution \(P\)  [1]}, [2]}, [3]}, [4]}, and require the model \(\ell \)  to be suitably smooth. For example, the certificate presented in [1]} can only be tractably computed for small neural networks for which one can upper bound their smoothness by bounding the Lipschitz constant of their gradients. For more general, and particularly large-scale networks, these bounds quickly become intractable and/or lead to vacuous certificates.
For example, it is known that computing the Lipschitz constant of neural networks with ReLU activations is NP-hard [6]}.
Secondly, we emphasize that our bound (REF ) is “faithful”, in the sense that, as the radius approaches zero, \(\rho \rightarrow 0\) , the bound converges towards the true expectation \(\mathbb {E}_P[\ell (Z)]\) .
This is of course desirable of any such bound as it indicates that any intrinsic gap vanishes as the covered distributions become increasingly closer to the reference distribution \(P\) .
A third observation is that the bound (REF ) is monotonically increasing in the variance, indicating that low variance models exhibit better generalization properties, which can be seen in light of the bias-variance trade-off.
Indeed, various recent works have highlighted the connection between variance regularization and generalization [7]}, [8]}, [9]}, [10]} and our result provides further evidence for this observation.
