Risk Bounds of Accelerated SGD for Overparameterized Linear Regression

Thank you for your positive feedback and suggestions!

Q1. The experiments are not comprehensive enough, for example, the paper finds that the variance error of ASGD is always larger than that of SGD, but there is not enough experimental support for this claim.

A1. Thank you for your suggestion. We have provided additional experiments to justify that the variance error of ASGD is larger than that of SGD. We have also provided additional experiments that compare both the bias error and the variance error of ASGD and SGD for linear regression instances with different spectra of $\mathbf{H}$, including $\lambda_k=k^{-2}$, $\lambda_k=k\log (k+1)$ and $\lambda_k=e^{-k/2}$. In these experiments, we use the same hyperparameters as those used in Section 6. $\mathbf{w}_0$ is initialized as $\mathbf{w}_0=10\cdot\\mathbf{e}\_1$, representing the case where $\mathbf{w}_0-\mathbf{w}^*$ is refined mainly to the subspace of large eigenvalues, or $\mathbf{w}_0=10\cdot\mathbf{e}\_{10}$, representing the case where $\mathbf{w}_0-\mathbf{w}^*$ is refined mainly to the subspace of small eigenvalues. The experimental results are shown in Figures 3-5 in Appendix A. From our experiments, we can observe that the variance error of ASGD is larger than that of SGD, and that the bias error of ASGD is smaller when $\mathbf{w}_0-\mathbf{w}^*$ is refined mainly to the subspace of small eigenvalues. Please refer to Appendix A in the revision for more details.

Q2. How is overparameterization reflected in Theorem 4.1?

A2. The excess risk bound provided in Theorem 4.1 is not explicitly related to the model dimension $d$. Instead, it depends on $k^*$ which is referred to as the effective dimension. For many data covariance matrix $\mathbf{H}$, even if $d$ is very large or even goes to infinity (i.e., overparameterization regime), $k^*$ can still be small or finite, and the excess risk bound does not go to infinity. This improves previous results that explicitly depend on the model dimension $d$ (Jain et al. 2018). This is how overparameterization is reflected in Theorem 4.1.

Q3. Please provide a more detailed explanation of the challenges encountered in theoretical analysis and how to address them in the submission.

A3. The most significant challenge is that, different from previous methods analyzing SGD (Zou et al. ,2021; Wu et al. ,2022), the monotonicity of the second moment for the bias error $\mathbf{B}_t$ is violated in ASGD. Therefore, we need to calculate the explicit expression of $\mathbf{A}_i^k$, and analyze quantities like those in Lemma K.5, Lemma K.6 and Lemma K.7.

Another challenge is the identification of the eigenvalue cutoffs $k^\dagger$, $k^\ddagger$, $\hat k$ and $k^*$. This is much more complicated than SGD because $\lambda_i$ significantly affects the decay rate of $\mathbf{A}_i^k$. Specifically, the eigenvalues of $\mathbf{A}_i$ can be complex or real, which also depends on $\lambda_i$. As a comparison, in the SGD results (Zou et al. ,2021; Wu et al. ,2022), there are only two cutoffs for eigenvalue.

Last but not least, we develop a new choice of parameters (Eq. (4.2)) for ASGD in the overparameterized regime. This choice of parameters is obtained through a fine-grained analysis of the effect of fourth-moment (see details in Appendix F.2), where we manage to avoid the model dimension $d$ in our choice of parameters.

Q4. Can you provide more instances that satisfy Assumption 3.2?

A4. Yes. The first example is: $\mathbf{H}^{-1/2}\mathbf{x}$ is $\sigma^2$-sub-Gaussian, then Assumption 3.2 is satisfied with $\psi=16\sigma^4$ (see Lemma A.1 of Zou et al., 2021). Another example is: $\mathbf{H}^{-1/2}\mathbf{x}$ is $\sigma^2$-sub-exponential, then Assumption 3.2 is also satisfied with $\psi=256\sigma^4$.

Jain et al. "Accelerating stochastic gradient descent for least squares regression." In Conference On Learning Theory, pp. 545-604. PMLR, 2018.

Zou et al. "Benign overfitting of constant-stepsize SGD for linear regression." In Conference on Learning Theory, pp. 4633-4635. PMLR, 2021.

Wu et al. "Last iterate risk bounds of sgd with decaying stepsize for overparameterized linear regression." In International Conference on Machine Learning, pp. 24280-24314. PMLR, 2022.

Thank you for your helpful feedback.

Q1. The claim in the abstract about ASGD outperforming SGD if the initialization minus optimizers lives in the subspace of the small eigenvalues is true but a bit useless, since it is very unlikely this happens. It is a low dimensional subspace and most of the rest of the space is dominated by the large eigenvalues.

A1. We would like to emphasize that this result in actually useful in the sense that (1) even for the simplest possible problem of linear regression, no prior work has demonstrated when ASGD can outperform SGD, and we are the first to give a quantitative condition, which deepens the understanding of ASGD vs. SGD in terms of generalization performance; (2) It is not “unlikely” that $\mathbf{w}_0-\mathbf{w}^*$ aligns well with the subspace of small eigenvalues. In practice, one often uses zero initialization or randomly initialization $\mathbf{w}_0$ that is close to zero. In this case, when the ground truth $\mathbf{w}^*$ is more aligned with the subspace of small eigenvalues, we will have $\mathbf{w}_0-\mathbf{w}^*$ is more aligned well with the subspace of small eigenvalues.

Q2. It is informative and of value to have all of the details in this setting that are provided in this work, but the results are weak, essentially a negative result that could have maybe been anticipated for this kind of algorithm.

A2. We would like to emphasize that our work not only provides a “negative” result, but also a “positive” result, which identifies a class of linear regression instances for which ASGD can outperform SGD (in Theorem 5.1). Moreover, we believe that our result is strong: it is the first result characterizing the excess risk of ASGD in the overparameterized regime. From a technical point of view, our result is also highly nontrivial to obtain (See the key techniques in Section 7).

Q3. Can you provide any examples of settings in which you can guarantee you can initialize to be in the good regime that you show for ASGD, i.e. when $\mathbf{w}_0-\mathbf{w}^*$ is essentially aligned with the subspace associated to small eigenvalues?

A3. Yes, we can first consider a $2$-dimensional model where $\lambda_1=1$ and $\lambda_2=0.01$, the ground truth weight vector is $\mathbf{w}^*=(1, 10)^\top$, and the initialization is $\mathbf{w}_0=(0, 0)^\top$. This is exactly the case where $\mathbf{w}_0-\mathbf{w}^*$ lies primarily in the subspace of small eigenvalues of the data covariance matrix. This type of ill-posed model is quite common in practice. It is also very easy to extend this example to the high-dimensional settings.

Dear Reviewer BSyC,

Thank you again for your insightful comments. We would like to follow up with you and address any outstanding questions if you still have. In our response, we have provided a representative linear regression instance where $\mathbf{w}_0-\mathbf{w}^*$ is mainly refined to the space of large eigenvalues of $\mathbf{H}$. Please let us know if you have any other suggestions.

Thank you very much for your strong support!