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. Particularly, we develop a convex analytic framework utilizing semi-infinite duality to obtain equivalent convex optimization problems for several 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 certain three-layer CNN training problems are equivalent to an $\ell_1$ regularized convex program. We also extend these results to multi-layer CNN architectures. Furthermore, we present extensions of our approach to different pooling methods.

本研究提出了使用ReLU激活函数的卷积神经网络(CNN)的训练方法，并引入了确切的凸优化公式，其复杂度与数据样本数量、神经元数量和数据维数成多项式关系。特别是，我们开发了一个凸解析框架，利用半无限对偶性来获得两层和三层CNN体系结构的等效凸优化问题。我们首先证明了利用l2范数正则化的凸程序可以全局优化两层CNNs。然后，我们证明了具有单个ReLU层的循环多层CNN训练问题等价于鼓励谱区域中的稀疏性的l1正则化凸优化程序。我们还将这些结果扩展到具有两个ReLU层的三层CNN中，并阐明了不同池化方法的内在建筑偏差作为凸正则化器的观点。

CNN结构的隐式凸规则化：在多项式时间内优化二层和三层网络的凸优化