Appendix AMarginBound A.1 ToyExample LetfW(x)=W3ρ(W2ρ(ˆW

Itisworth noting that there exist possible scenarios fortheabove inequalities toholdandtherefore achievingtheworst-case error. A.3.2 All-PerturbedBound In the following proof for Theorem 2, we apply similar steps in Appendix A.2 and consider the difference between set of pairwise margin under natural and weight perturbation setting, recall in Theorem2wedefinedthat fW(x)=WL(..WN...ρ(W1x)...)andfcW(x)= ˆW We note that each convolution operation can be described as matrix multiplication of a doubly block Toeplitz matrix. Inequality(d)resultsfromusingtriangle inequality and taking its maximum, inequality (e) isby the definition of margin and inequality (f) comes fromthefactthatwithReLU wehavekρ(Ax)k1 kAxk1. Wedenote theloss function asCE(), and during training, hard label was applied. Once we have calculated an upper bound forR(ˆ`F), then Theorem 4 is a direct consequence of Lemma2and3.