Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks
This provides a theoretical foundation for understanding neural network training as convex optimization, potentially benefiting researchers in machine learning theory and optimization.
The paper tackles the problem of training two-layer neural networks with ReLUs by developing exact convex optimization formulations that are solvable in polynomial time, showing equivalence to block ℓ1 penalized convex models and simplifying certain convolutional networks to ℓ1 regularized linear models.
We develop exact representations of training two-layer neural networks with rectified linear units (ReLUs) in terms of a single convex program with number of variables polynomial in the number of training samples and the number of hidden neurons. Our theory utilizes semi-infinite duality and minimum norm regularization. We show that ReLU networks trained with standard weight decay are equivalent to block $\ell_1$ penalized convex models. Moreover, we show that certain standard convolutional linear networks are equivalent semi-definite programs which can be simplified to $\ell_1$ regularized linear models in a polynomial sized discrete Fourier feature space.