Supplementary to " Approximation with CNNs in Sobolev Space: with Applications to Classification "

In the Supplementary materials, we include detailed descriptions on convex surrogate losses,convolutional neural networks, non-asymptotic error bounds for commonly used loss functions, and prove Theorems 2.1,2.2, A toy example on the numerical performance of CNN approximation is presented in Appendix D. We next give a brief review of the convex surrogate loss functions and discuss in details on the connection between the excess risk with respect to the ϕ-loss and that of 0-1 loss [28, 4]. Let ϕbe a given convex univariate function ϕ: R [0,). Instead of minimizing the excess risk R over H, we consider minimizing the risk with respect to the loss ϕ(ϕ-risk) R(f):= E{ϕ(Yf(X))} over a certain class of functions F, where ϕ: R [0,) is some generic loss function. For the special case when H = {h: h(x) = sign(f(x)),f F} and ϕ() is a step function, i.e., ϕ(x) = 1 Guohao Shen and Yuling Jiao contributed equally to this work Corresponding authors 36th Conference on Neural Information Processing Systems (NeurIPS 2022). As shown in [28] and [4], for a properly chosen ϕ, ˆfn can indeed help reduce the 0-1 excess risk R (ˆhn) R (h0). More precisely, let R0:= inff measurable R(f), then for a proper ϕ, we have ψ(R (ˆhn) R (h0)) R(ˆfn) R(f0), where ψ: [ 1,1] [0,)is a nonnegative continuous function, invertible on [0,1], and achieves its minimum at 0 with ψ(0) = 0. A wide variety of popular classification methods are based on this tactic.