提出带角点梯度的优化方法，可在随机梯度下实现最优收敛速度。
Corner Gradient Descent
- 通过复平面轮廓设计角点梯度算法，加速收敛
- 在噪声下仍可达到理论最优的 $O(t^{-2ζ})$ 收敛率
- 适用于高维、谱衰减问题，适合机器学习优化场景
我们研究无限维二次优化中基于小批量随机梯度的优化问题，其谱条件满足幂律。已知确定性梯度下降（GD）的损失收敛率为 $L_t=O(t^{-ζ})$，而使用非平稳雅可比型动量（Heavy Ball）可提升至 $O(t^{-2ζ})$，且后者为固定调度下的最优速率。但在小批量随机梯度设置中，采样噪声会导致雅可比重力动量发散，因此尚无 $O(t^{-2ζ})$ 的有效算法。本文证明，通过具有无限记忆的广义平稳随机梯度算法可实现该速率。我们发现，复平面上具有外角为 $θπ$ 的轮廓可将原始 $O(t^{-ζ})$ 速率加速至 $O(t^{-θζ})$。对于确定性情况，增大 $θ$ 可逼近 $O(t^{-2ζ})$；但在随机情形中，$θ$ 过大将放大噪声，需权衡加速与噪声影响。我们证明最优角为 $θ_{ ext{max}} = \min(2, ν, \frac{2}{ζ+1/ν})$，其中 $ν$、$ζ$ 分别为容量与源谱条件中的指数。进一步利用快速有理逼近幂函数，我们实现了理想角点算法的高效有限记忆近似，并在合成问题和 MNIST 上验证了其实际效率。
原文摘要 · Abstract (English)
We consider SGD-type optimization on infinite-dimensional quadratic problems with power law spectral conditions. It is well-known that on such problems deterministic GD has loss convergence rates $L_t=O(t^{-ζ})$, which can be improved to $L_t=O(t^{-2ζ})$ by using Heavy Ball with a non-stationary Jacobi-based schedule (and the latter rate is optimal among fixed schedules). However, in the mini-batch Stochastic GD setting, the sampling noise causes the Jacobi HB to diverge; accordingly no $O(t^{-2ζ})$ algorithm is known. In this paper we show that rates up to $O(t^{-2ζ})$ can be achieved by a generalized stationary SGD with infinite memory. We start by identifying generalized (S)GD algorithms with contours in the complex plane. We then show that contours that have a corner with external angle $θπ$ accelerate the plain GD rate $O(t^{-ζ})$ to $O(t^{-θζ})$. For deterministic GD, increasing $θ$ allows to achieve rates arbitrarily close to $O(t^{-2ζ})$. However, in Stochastic GD, increasing $θ$ also amplifies the sampling noise, so in general $θ$ needs to be optimized by balancing the acceleration and noise effects. We prove that the optimal rate is given by $θ_{\max}=\min(2,ν,\tfrac{2}{ζ+1/ν})$, where $ν,ζ$ are the exponents appearing in the capacity and source spectral conditions. Furthermore, using fast rational approximations of the power functions, we show that ideal corner algorithms can be efficiently approximated by finite-memory algorithms, and demonstrate their practical efficiency on a synthetic problem and MNIST.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。