在线梯度下降在核回归中表现优异，突破了传统方法的性能饱和瓶颈。
Learning Curves of Stochastic Gradient Descent in Kernel Regression
- 采用指数衰减学习率的单遍随机梯度下降
- 在不同样本量下达到近最优误差率，仅在极端误设时失效
- 适合研究模型泛化与深度学习优化机制的读者
本文研究在线一阶算法（如单遍随机梯度下降，SGD）在核回归中的表现，对比离线方法（如岭回归和无岭回归）。在最优预测器不属再生核希尔伯特空间（RKHS）的模型误设条件下，分析球面上内积核的情况。针对不同样本规模 $n$ 与输入维度 $d$，刻画了过拟合风险的精确阶数。令人惊讶的是，除了当 $n o ty$ 且 $niggg d^γ$（任意常数 $γ>0$）的最终阶段，其余情况下 SGD 均能以常数倍达到最小最大最优率，未出现普遍存在的性能饱和现象。其根本原因在于指数衰减学习率调度，这正是深度神经网络训练中的常见实践。作为副产品，首次严格证明该策略在常规设置下优于迭代平均法。
原文摘要 · Abstract (English)
This paper considers a canonical problem in kernel regression: how good are the model performances when it is trained by the popular online first-order algorithms, compared to the offline ones, such as ridge and ridgeless regression? In this paper, we analyze the foundational single-pass Stochastic Gradient Descent (SGD) in kernel regression under source condition where the optimal predictor can even not belong to the RKHS, i.e. the model is misspecified. Specifically, we focus on the inner product kernel over the sphere and characterize the exact orders of the excess risk curves under different scales of sample sizes $n$ concerning the input dimension $d$. Surprisingly, we show that SGD achieves min-max optimal rates up to constants among all the scales, without suffering the saturation, a prevalent phenomenon observed in (ridge) regression, except when the model is highly misspecified and the learning is in a final stage where $n\gg d^γ$ with any constant $γ>0$. The main reason for SGD to overcome the curse of saturation is the exponentially decaying step size schedule, a common practice in deep neural network training. As a byproduct, we provide the \emph{first} provable advantage of the scheme over the iterative averaging method in the common setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。