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 的风险界

Risk Bounds of Accelerated SGD for Overparameterized Linear Regression

Learning algorithms that divide the data into batches are prevalent in many
machine-learning applications, typically offering useful trade-offs between
computational efficiency and performance. In this paper, we examine the
benefits of batch-partitioning through the lens of a minimum-norm
overparameterized linear regression model with isotropic Gaussian features. We
suggest a natural small-batch version of the minimum-norm estimator, and derive
an upper bound on its quadratic risk, showing it is inversely proportional to
the noise level as well as to the overparameterization ratio, for the optimal
choice of batch size. In contrast to minimum-norm, our estimator admits a
stable risk behavior that is monotonically increasing in the
overparameterization ratio, eliminating both the blowup at the interpolation
point and the double-descent phenomenon. Interestingly, we observe that this
implicit regularization offered by the batch partition is partially explained
by feature overlap between the batches.
Our bound is derived via a novel combination of techniques, in particular
normal approximation in the Wasserstein metric of noisy projections over random
subspaces.

本文探讨了使用小批量的阈值学习算法进行分类的好处及最小二乘回归模型的上限风险，同时提出了一个基于特征重叠的小批量版本的最小二乘估计器，它比最小二乘估计器更稳定

批次稳定高维超参数线性回归中的最小范数风险

Batches Stabilize the Minimum Norm Risk in High Dimensional  Overparameterized Linear Regression

Stochastic gradient descent (SGD) has been shown to generalize well in many
deep learning applications. In practice, one often runs SGD with a
geometrically decaying stepsize, i.e., a constant initial stepsize followed by
multiple geometric stepsize decay, and uses the last iterate as the output.
This kind of SGD is known to be nearly minimax optimal for classical
finite-dimensional linear regression problems (Ge et al., 2019). However, a
sharp analysis for the last iterate of SGD in the overparameterized setting is
still open. In this paper, we provide a problem-dependent analysis on the last
iterate risk bounds of SGD with decaying stepsize, for (overparameterized)
linear regression problems. In particular, for last iterate SGD with (tail)
geometrically decaying stepsize, we prove nearly matching upper and lower
bounds on the excess risk. Moreover, we provide an excess risk lower bound for
last iterate SGD with polynomially decaying stepsize and demonstrate the
advantage of geometrically decaying stepsize in an instance-wise manner, which
complements the minimax rate comparison made in prior works.

本文针对几何递减步长的随机梯度下降算法在过参数化线性回归问题中的应用，对其迭代步数的风险进行了理论分析，并探讨了不同递减方法对算法优化效果的影响。