We develop exact representations of two layer neural networks with rectified linear units in terms of a single convex program with number of variables polynomial in the number of training samples and number of hidden neurons. Our theory utilizes semi-infinite duality and minimum norm regularization. Moreover, we show that certain standard multi-layer convolutional neural networks are equivalent to L1 regularized linear models in a polynomial sized discrete Fourier feature space. We also introduce exact semi-definite programming representations of convolutional and fully connected linear multi-layer networks which are polynomial size in both the sample size and dimension.

本文中，我们利用半无限对偶及最小规范化，将使用修正线性单元的两层神经网络的训练准确表述为单一凸程序，其变量数量与训练样本数量和隐藏层神经元数量呈多项式关系，并证明使用标准权重衰减进行修正线性单元网络训练的等效于带块$l_1$惩罚的凸模型。此外，我们还证明了某些标准卷积线性网络等效于半定程序，可以在多项式大小的离散傅里叶特征空间中简化为带$l_1$正则化的线性模型。

神经网络是凸正则化器：两层神经网络的精确多项式时间凸优化公式