论文标题
在基于随机梯度的采样中利用CLT结构：改进的分析和更快的算法
Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms
论文作者
论文摘要
我们考虑采样算法的随机近似值，例如随机梯度Langevin Dynamics（SGLD）和用于相互作用的粒子动力学（IPD）的随机批处理方法（RBM）。我们观察到由随机近似引入的噪声几乎是高斯，因为中央限制定理（CLT），而驱动的布朗尼运动则完全高斯。我们利用这种结构来吸收扩散过程中的随机近似误差，并为这些算法获得改进的收敛保证。对于SGLD，我们证明了KL差异的第一个稳定收敛速率，而无需均匀的温暖开始，假设目标密度满足了对数 - 核心的不平等。我们的结果意味着与先前的作品相比，在明显较温和的假设下，一阶甲骨文的复杂性。我们还证明了SGLD在较弱的条件下的首次保证，例如Hölder的平滑度和繁政不平等，从而弥合了LMC和SGLD的最先进保证之间的差距。我们的分析激发了一种称为协方差校正的新算法，该算法通过重新缩放扩散强度来纠正由随机近似引起的其他噪声。最后，我们将技术应用于分析RBM，并在最小的假设下，根据先前工作的保证（例如，消除指数依赖性的依赖性）显着改善。
We consider stochastic approximations of sampling algorithms, such as Stochastic Gradient Langevin Dynamics (SGLD) and the Random Batch Method (RBM) for Interacting Particle Dynamcs (IPD). We observe that the noise introduced by the stochastic approximation is nearly Gaussian due to the Central Limit Theorem (CLT) while the driving Brownian motion is exactly Gaussian. We harness this structure to absorb the stochastic approximation error inside the diffusion process, and obtain improved convergence guarantees for these algorithms. For SGLD, we prove the first stable convergence rate in KL divergence without requiring uniform warm start, assuming the target density satisfies a Log-Sobolev Inequality. Our result implies superior first-order oracle complexity compared to prior works, under significantly milder assumptions. We also prove the first guarantees for SGLD under even weaker conditions such as Hölder smoothness and Poincare Inequality, thus bridging the gap between the state-of-the-art guarantees for LMC and SGLD. Our analysis motivates a new algorithm called covariance correction, which corrects for the additional noise introduced by the stochastic approximation by rescaling the strength of the diffusion. Finally, we apply our techniques to analyze RBM, and significantly improve upon the guarantees in prior works (such as removing exponential dependence on horizon), under minimal assumptions.
