A recent line of research on deep learning focuses on the extremely over-parameterized setting, and shows that when the network width is larger than a high degree polynomial of the training sample size $n$ and the inverse of the target accuracy $\epsilon^{-1}$, deep neural networks learned by (stochastic) gradient descent enjoy nice optimization and generalization guarantees. Very recently, it is shown that under certain margin assumption on the training data, a polylogarithmic width condition suffices for two-layer ReLU networks to converge and generalize (Ji and Telgarsky, 2019). However, how much over-parameterization is sufficient to guarantee optimization and generalization for deep neural networks still remains an open question. In this work, we establish sharp optimization and generalization guarantees for deep ReLU networks. Under various assumptions made in previous work, our optimization and generalization guarantees hold with network width polylogarithmic in $n$ and $\epsilon^{-1}$. Our results push the study of over-parameterized deep neural networks towards more practical settings.

本研究探讨了在过度参数化的深度神经网络中，当网络宽度大于训练样本大小和目标误差的高次多项式的倒数时，通过（随机）梯度下降学习的深度神经网络可以获得良好的优化和泛化性能。此外，我们还构建了深层ReLU网络的学习保证，使得网络宽度对n和ϵ的对数具有良好保证。

深度ReLU网络学习所需的过度参数化程度是多少？