Accelerated stochastic gradient descent (ASGD) is a workhorse in deep learning and often achieves better generalization performance than SGD. However, existing optimization theory can only explain the faster convergence of ASGD, but cannot explain its better generalization. In this paper, we study the generalization of ASGD for overparameterized linear regression, which is possibly the simplest setting of learning with overparameterization. We establish an instance-dependent excess risk bound for ASGD within each eigen-subspace of the data covariance matrix. Our analysis shows that (i) ASGD outperforms SGD in the subspace of small eigenvalues, exhibiting a faster rate of exponential decay for bias error, while in the subspace of large eigenvalues, its bias error decays slower than SGD; and (ii) the variance error of ASGD is always larger than that of SGD. Our result suggests that ASGD can outperform SGD when the difference between the initialization and the true weight vector is mostly confined to the subspace of small eigenvalues. Additionally, when our analysis is specialized to linear regression in the strongly convex setting, it yields a tighter bound for bias error than the best-known result.

我们研究了加速随机梯度下降（ASGD）在过参数化线性回归中的泛化情况，建立了数据协方差矩阵的每个特征子空间下的ASGD的过量风险界限，结果显示出ASGD在小特征值子空间中的偏差误差以指数衰减的速度优于SGD，而在大特征值子空间中，偏差误差的衰减速度较慢，且ASGD的方差误差始终大于SGD的。我们的研究表明，当初始化向量与真实权重向量的差异主要集中在小特征值子空间时，ASGD可以优于SGD。此外，当我们将分析专门应用于强凸设置下的线性回归问题时，得到的偏差误差界限比已知结果更紧。

过参数化线性回归的加速SGD的风险界