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

Abstract

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.

References in corpus (8)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• On Exact Computation with an Infinitely Wide Neural Net
• Reliably Learning the ReLU in Polynomial Time
• 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

Cited by in corpus (6)

• The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
• Training a Two Layer ReLU Network Analytically
• Convex Regularization Behind Neural Reconstruction
• Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms
• The Convex Geometry of Backpropagation: Neural Network Gradient Flows Converge to Extreme Points of the Dual Convex Program
• Parallel Deep Neural Networks Have Zero Duality Gap