  We study training of Convolutional Neural Networks (CNNs) with ReLU
activations and introduce exact convex optimization formulations with a
polynomial complexity with respect to the number of data samples, the number of
neurons, and data dimension. More specifically, we develop a convex analytic
framework utilizing semi-infinite duality to obtain equivalent convex
optimization problems for several two- and three-layer CNN architectures. We
first prove that two-layer CNNs can be globally optimized via an $\ell_2$ norm
regularized convex program. We then show that multi-layer circular CNN training
problems with a single ReLU layer are equivalent to an $\ell_1$ regularized
convex program that encourages sparsity in the spectral domain. We also extend
these results to three-layer CNNs with two ReLU layers. Furthermore, we present
extensions of our approach to different pooling methods, which elucidates the
implicit architectural bias as convex regularizers.
