Sampling from NonLogConcave Distributions via VarianceReduced Gradient Langevin Dynamics
[edit]
Proceedings of Machine Learning Research, PMLR 89:29362945, 2019.
Abstract
We study stochastic variance reductionbased Langevin dynamic algorithms, SVRGLD and SAGALD \citep{dubey2016variance}, for sampling from nonlogconcave distributions. Under certain assumptions on the log density function, we establish the convergence guarantees of SVRGLD and SAGALD in $2$Wasserstein distance. More specifically, we show that both SVRGLD and SAGALD require $ \tilde O\big(n+n^{3/4}/\epsilon^2 + n^{1/2}/\epsilon^4\big)\cdot \exp\big(\tilde O(d+\gamma)\big)$ stochastic gradient evaluations to achieve $\epsilon$accuracy in $2$Wasserstein distance, which outperforms the $ \tilde O\big(n/\epsilon^4\big)\cdot \exp\big(\tilde O(d+\gamma)\big)$ gradient complexity achieved by Langevin Monte Carlo Method \citep{raginsky2017non}. Experiments on synthetic data and real data back up our theory.
Related Material


