提出更紧的神经网络梯度方法收敛与泛化界，适用于小宽度网络。
Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods
- 基于算法稳定性分析，推导深度网络的过拟合风险上界。
- 在无噪声可分数据下，测试误差率达 $e^{O(L)}/(γ^2 n)$，优于已有结果。
- 大步长显著提升分类性能，常数宽度网络仅需 $\ceil{\log(d)}$ 步达完美准确率。
本文研究平滑激活函数神经网络在梯度方法下的数据依赖收敛与泛化行为。通过算法稳定性分析，提出一种新的深度网络训练中逻辑损失的过拟合风险上界。相比传统基于Rademacher复杂度的界，本文结果更紧，适用于小宽度网络，不随宽度恶化，且具有算法依赖性，可刻画初始化对梯度下降样本复杂度的影响。在无噪声、以边缘 $γ$ 可被神经正切核（NTK）特征分离的数据下，测试误差率为 $e^{O(L)}/(γ^2 n)$，其中 $n$ 为训练集大小，$L$ 为隐藏层数。该界优于先前工作，同时保持多对数宽度条件。进一步针对带噪声数据，证明在多项式宽度条件下，梯度下降可达最优过拟合风险。最后，发现大步长显著优于标准NTK regime：对于常数宽度 $m$、二次激活、标准高斯初始化的一层神经网络，小批量SGD以线性样本复杂度、步长 $η = m$，只需 $\ceil{\log(d)}$ 次迭代即可达到完美测试精度，其中 $d$ 为数据维度。
原文摘要 · Abstract (English)
In this paper, we study the data-dependent convergence and generalization behavior of gradient methods for neural networks with smooth activation. Our first result is a novel bound on the excess risk of deep networks trained by the logistic loss, via an alogirthmic stability analysis. Compared to previous works, our results improve upon the shortcomings of the well-established Rademacher complexity-based bounds. Importantly, the bounds we derive in this paper are tighter, hold even for neural networks of small width, do not scale unfavorably with width, are algorithm-dependent, and consequently capture the role of initialization on the sample complexity of gradient descent for deep nets. Specialized to noiseless data separable with margin $γ$ by neural tangent kernel (NTK) features of a network of width $Ω(\text{poly}(\log(n)))$, we show the test-error rate to be $e^{O(L)}/{γ^2 n}$, where $n$ is the training set size and $L$ denotes the number of hidden layers. This is an improvement in the test loss bound compared to previous works while maintaining the poly-logarithmic width conditions. We further investigate excess risk bounds for deep nets trained with noisy data, establishing that under a polynomial condition on the network width, gradient descent can achieve the optimal excess risk. Finally, we show that a large step-size significantly improves upon the NTK regime's results in classifying the XOR distribution. In particular, we show for a one-hidden-layer neural network of constant width $m$ with quadratic activation and standard Gaussian initialization that mini-batch SGD with linear sample complexity and with a large step-size $η=m$ reaches the perfect test accuracy after only $\ceil{\log(d)}$ iterations, where $d$ is the data dimension.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。