随机梯度下降最优步长调度有了精确理论
Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization
SGD 的步长到底该怎么设，这篇论文直接算出了极小极大最优解，还证明了唯一性，做优化理论或调参的都该看看。
arXiv 新论文研究光滑凸优化中随机梯度下降的步长调度设计，假设梯度噪声条件零均值且方差有界。作者给出维度 d≥N+1 时 SGD 最终迭代点期望次优性的精确最坏情况分析，适用于 [0,1.5]^N 内任意 N 个步长的调度，并提供匹配的目标函数与噪声分布证明保证可达。当方差下界达到 Ω(1/√N) 时，论文给出极小极大最优的步长调度并证明其唯一性。这些最优步长单调递减，说明确定性情形下固定分形调度的加速在随机情形不再成立。
Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization
This work considers the design of stepsize schedules for stochastic gradient descent in smooth convex optimization. Throughout, we assume that gradient noise is conditionally zero-mean with bounded variance. Among problems with dimension $d\geq N+1$, we provide an exact worst-case analysis of the expected suboptimality of stochastic gradient descent's final iterate. Our analysis applies to any (potentially nonconstant) schedule of $N$ stepsizes in $[0,1.5]^N$. Here, exact means that we provide a matching objective function and noise distributions where our guarantee is attained. Whenever the variance bound is at least $Ω(1/\sqrt{N})$, our theory provides the minimax optimal stepsize schedule for stochastic gradient descent and proves its uniqueness. These optimal stepsizes monotonically decrease, ruling out any accelerations in expected final suboptimality from fixed fractal schedules observed in the deterministic case.
