In this paper, we study the optimality gap between two-layer ReLU networks regularized with weight decay and their convex relaxations. We show that when the training data is random, the relative optimality gap between the original problem and its relaxation can be bounded by a factor of $O(\sqrt{\log n})$, where $n$ is the number of training samples. A simple application leads to a tractable polynomial-time algorithm that is guaranteed to solve the original non-convex problem up to a logarithmic factor. Moreover, under mild assumptions, we show that with random initialization on the parameters local gradient methods almost surely converge to a point that has low training loss. Our result is an exponential improvement compared to existing results and sheds new light on understanding why local gradient methods work well.

本文研究了采用权重衰减正则化的两层ReLU网络与其凸松弛之间的最优性差距，揭示了在随机训练数据情况下原问题与其松弛之间相对最优性差距可以通过O(√log n)的因子进行界定，且应用简单的算法可在多项式时间内解决原非凸问题，此外，在合理假设下，随机初始化参数的局部梯度方法几乎必定收敛于训练损失较低点，此结果相对现有结果而言具有指数级改进，并对解释局部梯度方法为何行之有效提供了新的见解。

ReLU神经网络的凸松弛在多项式时间内近似全局最优