Skip to yearly menu bar Skip to main content

Workshop: OPT 2023: Optimization for Machine Learning

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. While existing optimization theory can explain its faster convergence, they fall short in explaining its better generalization. In this paper, we study the generalization of ASGD for overparameterized linear regression. 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, 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 resultsuggests 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.

Chat is not available.