Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms

We describe the convex semi-infinite dual of the two-layer vector-output ReLU\nneural network training problem. This semi-infinite dual admits a finite\ndimensional representation, but its support is over a convex set which is\ndifficult to characterize. In particular, we demonstrate that the non-convex\nneural network training problem is equivalent to a finite-dimensional convex\ncopositive program. Our work is the first to identify this strong connection\nbetween the global optima of neural networks and those of copositive programs.\nWe thus demonstrate how neural networks implicitly attempt to solve copositive\nprograms via semi-nonnegative matrix factorization, and draw key insights from\nthis formulation. We describe the first algorithms for provably finding the\nglobal minimum of the vector output neural network training problem, which are\npolynomial in the number of samples for a fixed data rank, yet exponential in\nthe dimension. However, in the case of convolutional architectures, the\ncomputational complexity is exponential in only the filter size and polynomial\nin all other parameters. We describe the circumstances in which we can find the\nglobal optimum of this neural network training problem exactly with\nsoft-thresholded SVD, and provide a copositive relaxation which is guaranteed\nto be exact for certain classes of problems, and which corresponds with the\nsolution of Stochastic Gradient Descent in practice.\n