Risk Bounds of Accelerated SGD for Overparameterized Linear Regression
Xuheng Li Yihe Deng Jingfeng Wu Dongruo Zhou Quanquan Gu
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.