提出新方法证明随机逼近与梯度下降收敛性，放宽噪声条件。
Revisiting Stochastic Approximation and Stochastic Gradient Descent
- 引入广义大数定律（GSLLN）替代传统方法
- 允许噪声无有限均值或二阶矩，适用范围更广
- 首次给出零阶SGD最弱收敛条件，理论拓展显著
本文提出一种新方法，用于证明随机逼近（SA）和随机梯度下降（SGD）算法的收敛性。该方法基于广义大数定律（GSLLN），可将目标函数性质与测量误差（噪声序列）性质解耦。相比主流的ODE方法和鞅方法，新方法允许更广泛的噪声信号，包括无有限二阶矩甚至无有限均值的噪声。通过此方法，我们还推导出零阶SGD的收敛条件：仅需2d次函数值评估即可近似梯度，无需显式梯度计算。所获条件为目前最弱，极大扩展了SA与SGD理论的应用范围。
原文摘要 · Abstract (English)
In this paper, we introduce a new approach to proving the convergence of the Stochastic Approximation (SA) and the Stochastic Gradient Descent (SGD) algorithms. The new approach is based on a concept called GSLLN (Generalized Strong Law of Large Numbers), which extends the traditional SLLN. Using this concept, we provide sufficient conditions for convergence, which effectively decouple the properties of the function whose zero we are trying to find, from the properties of the measurement errors (noise sequence). The new approach provides an alternative to the two widely used approaches, namely the ODE approach and the martingale approach, and also permits a wider class of noise signals than either of the two known approaches. In particular, the ``noise'' or measurement error \textit{need not} have a finite second moment, and under suitable conditions, not even a finite mean. By adapting this method of proof, we also derive sufficient conditions for the convergence of zero-order SGD, wherein the stochastic gradient is computed using $2d$ function evaluations, but no gradient computations. The sufficient conditions derived here are the weakest to date, thus leading to a considerable expansion of the applicability of SA and SGD theory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。