Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning
Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning
复制标题
DOI：
--
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Andrew G. Lamperski
中科院分区：
文献类型：
--
作者：
Andrew G. Lamperski
朗之万算法是一种带有加性噪声的梯度下降算法。它们已经在马尔可夫链蒙特卡罗（MCMC）采样、优化和学习中使用了几十年。它们在无约束非凸优化和学习问题上的收敛性近年来得到了广泛的研究。其他工作研究了投影朗格万算法，用于从限制于凸紧集的对数凹分布中采样。对于学习和优化，对数凹分布对应于凸损失。本文分析了具有紧凸约束集和IID外部数据变量的非凸损失情况。我们将得到的方法称为投影随机梯度朗之万算法（PSGLA）。我们证明了该算法在1-Wasserstein距离上与目标分布的偏差为$O(T^{-1/4}(\log T)^{1/2})$。对于优化和学习，我们证明该算法平均达到$\epsilon$ -次优解，前提是它运行的时间在$\epsilon^{-1}$上是多项式，在问题维度上稍微是超指数。
Langevin algorithms are gradient descent methods with additive noise. They have been used for decades in Markov chain Monte Carlo (MCMC) sampling, optimization, and learning. Their convergence properties for unconstrained non-convex optimization and learning problems have been studied widely in the last few years. Other work has examined projected Langevin algorithms for sampling from log-concave distributions restricted to convex compact sets. For learning and optimization, log-concave distributions correspond to convex losses. In this paper, we analyze the case of non-convex losses with compact convex constraint sets and IID external data variables. We term the resulting method the projected stochastic gradient Langevin algorithm (PSGLA). We show the algorithm achieves a deviation of $O(T^{-1/4}(\log T)^{1/2})$ from its target distribution in 1-Wasserstein distance. For optimization and learning, we show that the algorithm achieves $\epsilon$-suboptimal solutions, on average, provided that it is run for a time that is polynomial in $\epsilon^{-1}$ and slightly super-exponential in the problem dimension.