Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms
Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms
复制标题
DOI：
--
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Arda Sahiner;Tolga Ergen;J. Pauly;Mert Pilanci
中科院分区：
文献类型：
--
作者：
Arda Sahiner;Tolga Ergen;J. Pauly;Mert Pilanci
我们描述了两层向量输出RELU神经网络训练问题的凸半无限对偶问题。这种半无限对偶允许有限维表示，但它的支集是在难以刻画的凸集上。特别地，我们证明了非凸神经网络训练问题等价于有限维凸共正规划。我们的工作首次发现了神经网络的全局最优解和协同阳性程序的全局最优解之间的紧密联系。因此，我们展示了神经网络如何通过半非负矩阵因式分解隐式地尝试求解余正规划，并从这一公式中得出关键的见解。我们描述了第一个可证明地寻找向量输出神经网络训练问题的全局最小值的算法，对于固定的数据秩样本数是多项式的，但在维度上是指数的。然而，在卷积结构的情况下，计算复杂性仅在滤波器大小和所有其他参数的多项式中是指数的。我们描述了用软阈值奇异值分解精确地找到该神经网络训练问题的全局最优解的情况，并给出了对某些类问题保证精确的正向松弛解，它与实际中的随机梯度下降解相对应。
We describe the convex semi-infinite dual of the two-layer vector-output ReLU neural network training problem. This semi-infinite dual admits a finite dimensional representation, but its support is over a convex set which is difficult to characterize. In particular, we demonstrate that the non-convex neural network training problem is equivalent to a finite-dimensional convex copositive program. Our work is the first to identify this strong connection between the global optima of neural networks and those of copositive programs. We thus demonstrate how neural networks implicitly attempt to solve copositive programs via semi-nonnegative matrix factorization, and draw key insights from this formulation. We describe the first algorithms for provably finding the global minimum of the vector output neural network training problem, which are polynomial in the number of samples for a fixed data rank, yet exponential in the dimension. However, in the case of convolutional architectures, the computational complexity is exponential in only the filter size and polynomial in all other parameters. We describe the circumstances in which we can find the global optimum of this neural network training problem exactly with soft-thresholded SVD, and provide a copositive relaxation which is guaranteed to be exact for certain classes of problems, and which corresponds with the solution of Stochastic Gradient Descent in practice.