The training of two-layer neural networks with nonlinear activation functions
is an important non-convex optimization problem with numerous applications and
promising performance in layerwise deep learning. In this paper, we develop
exact convex optimization formulations for two-layer neural networks with
second degree polynomial activations based on semidefinite programming.
Remarkably, we show that semidefinite lifting is always exact and therefore
computational complexity for global optimization is polynomial in the input
dimension and sample size for all input data. The developed convex formulations
are proven to achieve the same global optimal solution set as their non-convex
counterparts. More specifically, the globally optimal two-layer neural network
with polynomial activations can be found by solving a semidefinite program
(SDP) and decomposing the solution using a procedure we call Neural
Decomposition. Moreover, the choice of regularizers plays a crucial role in the
computational tractability of neural network training. We show that the
standard weight decay regularization formulation is NP-hard, whereas other
simple convex penalties render the problem tractable in polynomial time via
convex programming. We extend the results beyond the fully connected
architecture to different neural network architectures including networks with
vector outputs and convolutional architectures with pooling. We provide
extensive numerical simulations showing that the standard backpropagation
approach often fails to achieve the global optimum of the training loss. The
proposed approach is significantly faster to obtain better test accuracy
compared to the standard backpropagation procedure.

本文提出了基于半定规划的二层神经网络的精确凸优化公式，可在多种神经网络体系结构中实现全局最优解，相比标准反向传播方法速度更快且准确性更高。