从抽样设计视角解析SGD噪声，揭示其与统计信息的深层联系。
Mini-Batch Covariance, Diffusion Limits, and Oracle Complexity in Stochastic Gradient Descent: A Sampling-Design Perspective
- 将小批量梯度噪声视为抽样设计对象，建立其与统计信息矩阵的关联。
- 证明了在有效维度下，均方误差收敛到1/N量级，且达到参数最优下界。
- 适合研究优化算法理论、统计学习和随机逼近的学者参考。
随机梯度下降（SGD）在模拟优化、随机规划和在线M估计中至关重要，其中采样成本是可调节的决策变量。本文将小批量梯度噪声视为抽样设计对象，在独立同分布的新样本小批量假设下，给定de Finetti指引测度μ时，条件协方差为b⁻¹G_μ(θ)；在可识别条件下，投影后的总体对象为b⁻¹G*(θ)，即正确模型下的投影Fisher信息，否则为Hessian的sandwich项。该识别确定了常步长SGD扩散分析中的噪声矩阵：原始迭代路径具有确定性流极限，√(b/η)缩放的波动满足带噪声协方差G*的功能中心极限定理；在非退化极值点附近，极限为Ornstein-Uhlenbeck过程，其李雅普诺夫协方差按η/b缩放与线性离散递推在首阶一致。在曲率-噪声相容性条件μ_F > 0下，我们证明了1/N量级的均方上界，并给出了相同阶的i.i.d.参数型费舍尔范特尔斯下界，其预言复杂度依赖于有效维度d_eff与条件数κ_F。数值实验验证了识别结果，并确认了直接SGD中的李雅普诺夫预测。
原文摘要 · Abstract (English)
Stochastic gradient descent (SGD) is central to simulation optimization, stochastic programming, and online M-estimation, where sampling effort is a decision variable. We study the mini-batch gradient noise as a sampling-design object. Under exchangeable fresh-sampling mini-batches, the conditional covariance given the de Finetti directing measure mu is b^{-1} G_mu(theta), and under identifiability the projected population object is b^{-1} G*(theta) -- projected Fisher information for correctly specified likelihoods, the sandwich partner of the Hessian otherwise. This identification fixes the noise matrix entering the diffusion analysis of constant-step SGD: the raw iterate path has a deterministic fluid limit, and the sqrt(b/eta)-scaled fluctuations satisfy a functional CLT with noise covariance G*; near a nondegenerate optimum the limit is Ornstein-Uhlenbeck, and its Lyapunov covariance scaled by eta/b matches the linearized discrete recursion at leading order. Under a curvature-noise compatibility condition mu_F > 0, we prove 1/N mean-square upper bounds and an i.i.d. parametric Fisher van Trees lower bound of the same rate order, with oracle-complexity guarantees depending on an effective dimension d_eff and condition number kappa_F. Numerical experiments verify the identification and confirm the Lyapunov predictions in direct SGD.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。