Implicit Convex Regularizers of CNN Architectures: Convex Optimization of Two- and Three-Layer Networks in Polynomial Time

Abstract

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.

arXiv commentAccepted for Spotlight Presentation at ICLR 2021

References in corpus (10)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• ImageNet-trained CNNs are biased towards texture; increasing shape bias improves accuracy and robustness
• On the Spectral Bias of Neural Networks
• Gradient Descent Quantizes ReLU Network Features
• Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process
• Complexity of Training ReLU Neural Network
• Revealing the Structure of Deep Neural Networks via Convex Duality
• Convex Geometry and Duality of Over-parameterized Neural Networks
• Demystifying Batch Normalization in ReLU Networks: Equivalent Convex Optimization Models and Implicit Regularization