The classical Langevin Monte Carlo method looks for i.i.d. samples from a target distribution by descending along the gradient of the target distribution. It is popular partially due to its fast convergence rate. However, the numerical cost is sometimes high because the gradient can be hard to obtain. One approach to eliminate the gradient computation is to employ the concept of "ensemble", where a large number of particles are evolved together so that the neighboring particles provide gradient information to each other. In this article, we discuss two algorithms that integrate the ensemble feature into LMC, and the associated properties. There are two sides of our discovery: 1. By directly surrogating the gradient using the ensemble approximation, we develop Ensemble Langevin Monte Carlo. We show that this method is unstable due to a potentially small denominator that induces high variance. We provide a counterexample to explicitly show this instability. 2. We then change the strategy and enact the ensemble approximation to the gradient only in a constrained manner, to eliminate the unstable points. The algorithm is termed Constrained Ensemble Langevin Monte Carlo. We show that, with a proper tuning, the surrogation takes place often enough to bring the reasonable numerical saving, while the induced error is still low enough for us to maintain the fast convergence rate, up to a controllable discretization and ensemble error. Such combination of ensemble method and LMC shed light on inventing gradient-free algorithms that produce i.i.d. samples almost exponentially fast.
翻译:古典的 Langevin Monte Carlo 方法通过在目标分布梯度沿目标分布梯度下降,寻找目标分布的样本。 它受到欢迎, 部分是因为其快速趋同率。 但是, 数字成本有时会很高, 因为梯度很难获得。 消除梯度计算的方法之一是使用“ 共变” 的概念, 即大量粒子一起进化, 从而让相邻的粒子能够相互提供梯度信息。 在此文章中, 我们讨论两种将混合的梯度特性纳入 LMC 和相关属性的算法。 我们发现的两个方面是 : 1. 通过使用组合近似率直接取代梯度, 我们开发了 Ensemble Langevin Monte Carlo 。 我们显示, 这种方法之所以不稳定, 是因为一个潜在的小分母值, 我们提供了一个反推论来明确显示这种不稳定性。 2. 然后我们修改策略, 并且以约束易变精度的组合, 消除不稳定点。 算法称为 Constraclegleble 的精度, 直接取代了 Langevlevin 和Met Carloo 。 我们展示了一种足够快速的精度,, 的精度的精度,, 使这个方法能快速地使快速的精度恢复到精确到精确到 。