Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks

We develop exact representations of training two-layer neural networks with\nrectified linear units (ReLUs) in terms of a single convex program with number\nof variables polynomial in the number of training samples and the number of\nhidden neurons. Our theory utilizes semi-infinite duality and minimum norm\nregularization. We show that ReLU networks trained with standard weight decay\nare equivalent to block $\\ell_1$ penalized convex models. Moreover, we show\nthat certain standard convolutional linear networks are equivalent\nsemi-definite programs which can be simplified to $\\ell_1$ regularized linear\nmodels in a polynomial sized discrete Fourier feature space.\n