Randomized smoothing for certified robustness

We give a short proof of the Cohen-Rosenfeld-Kolter theorem on the certified robustness of randomized smoothing.
Cohen-Rosenfeld-Kolter paper: arxiv.org/abs/1902.02918
Presented proof can be found in Salman-Yang-Li-Zhang-Zhang-Razenshteyn-Bubeck: arxiv.org/abs/1906.04584
For more background on adversarial examples see e.g., this video: • Adversarial Examples

[@CuongTran-jj9bu]

very useful :)

[@sparsam]

Just watched the video and it was really interesting!
Only the definition of \phi^{-1} was somehow inconsistent I think. If we define it to return the value that is smaller than the gaussian with probability p (in most of the video you have defined so I think), then there must be two modifications probably:
1) if p -> 1 then \phi^{-1}(p) -> -\infinity
2) at the end of the video \phi^{-1}(\hat{f}_B(x + \delta)) - \phi{-1}(\hat{f}_A(x + \delta)) must be examined

[@yingruli2250]

at 10:30, I think this equality in the red box, there is no negative sign inside the expectation, although it will not affect the other derivations.

[@SebastienBubeck]

Correct!