Abstract: Since deep neural network training problems are inherently non-convex, their recent dramatic success largely relies on non-convex optimization heuristics and experimental findings. However, extensive research has failed to provide a solid understanding of the reasons behind the success of these highly complex non-convex optimization models. The choice of optimization method and its internal parameters such as initialization, mini-batching and step sizes have a considerable effect on the quality of a non-convex model. This is in sharp contrast to convex optimization problems, where these optimization parameters have no effect, and globally optimal solutions can be obtained in a very robust, efficient, and reproducible manner.

To this end, in this talk, we study multilayer neural networks with ReLU activations through the lens of convex optimization. We introduce exact convex optimization formulations of ReLU network training problems. We show that two and three layer networks can be globally trained via convex programs with the number of variables polynomial in the number of training samples, feature dimension, and the number of hidden neurons. Our results provide an equivalent characterization of neural networks as convex models where a mixture of locally linear models is fitted to the data with sparsity inducing convex regularization. Moreover, we show that certain standard two and three layer convolutional neural networks can be globally optimized in fully polynomial time. We discuss extensions to batch normalization, generative adversarial networks, and deeper architectures. Finally, we present numerical simulations verifying our claims and illustrating that the proposed convex approach is faster and more reliable than standard local search heuristics such as SGD.