Center Smoothing: Certified Robustness for Networks with Structured Outputs Appendix

Let, y be a point in that intersection. Since, by definition, ˆr(x0,) is the radius of the smallest ball with 1/2 + probability mass of f(x0 + P) over all possible centers in Rk and ˆRis the radius of the smallest such ball centered at ˆf(x), we must have ˆr(x0,) ˆR. Consider the smallest ball B(z0,ˆr(x, 1)) that encloses at least 1/2 + 1 probability mass of f(x+ P). Since, r is the radius of the minimum enclosing ball that contains at least half of the points in Z, we have r ˆr(x, 1). Now, using the definition of ˆRand following the same reasoning as theorem 2, we can say that, d( ˆf(x), ˆf(x0)) βˆr(x0,) + ˆR (1 + β) ˆR.