Nonconvex sampling with the Metropolisadjusted Langevin algorithm
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:22592293, 2019.
Abstract
The Langevin Markov chain algorithms are widely deployed methods to sample from distributions in challenging highdimensional and nonconvex statistics and machine learning applications. Despite this, current bounds for the Langevin algorithms are worse than those of competing algorithms in many important situations, for instance when sampling from weakly logconcave distributions, or when sampling or optimizing nonconvex logdensities. We obtain improved bounds in many of these situations, showing that the Metropolisadjusted Langevin algorithm (MALA) is faster than the best bounds for its competitor algorithms when the target distribution satisfies weak third and fourth order regularity properties associated with the input data. In many settings, our regularity conditions are weaker than the usual Euclidean operator norm regularity properties, allowing us to show faster bounds for a much larger class of distributions than would be possible with the usual Euclidean operator norm approach, including in statistics and machine learning applications where the data satisfy a certain incoherence condition. In particular, we show that using our regularity conditions one can obtain faster bounds for applications which include sampling problems in Bayesian logistic regression with weakly convex priors, and the nonconvex optimization problem of learning linear classifiers with zeroone loss functions. Our main technical contribution is an analysis of the Metropolis acceptance probability of MALA in terms of its “energyconservation error," and a bound for this error in terms of third and fourth order regularity conditions. The combination of this higherorder analysis of the energy conservation error with the conductance method is key to obtaining bounds which have a sublinear dependence on the dimension $d$ in the nonstrongly logconcave setting.
Related Material


