Mirrored Langevin Dynamics
We consider the problem of sampling from constrained distributions, which has posed significant challenges to both non-asymptotic analysis and algorithmic design. We propose a unified framework, which is inspired by the classical mirror descent, to derive novel first-order sampling schemes. We prove that, for a general target distribution with strongly convex potential, our framework implies the existence of a first-order algorithm achieving O( −2 d) convergence, suggesting that the state-of-the-artÕ( −6 d 5 ) can be vastly improved. With the important Latent Dirichlet Allocation (LDA) application in mind, we specialize our algorithm to sample from Dirichlet posteriors, and derive the first non-asymptoticÕ( −2 d 2 ) rate for first-order sampling. We further extend our framework to the mini-batch setting and prove convergence rates when only stochastic gradients are available. Finally, we report promising experimental results for LDA on real datasets.
This is a very well-written paper and excellently presented with some interesting supporting theoretical results. The paper introduces a method (mirror map) from the optimization literature, mirrored descent, to perform scalable Monte Carlo sampling in a constrained state space. The mirror map works by transforming the sampling problem onto an unconstrained space, where stochastic gradient Markov chain Monte Carlo (MCMC) algorithms, in particular, stochastic gradient Langevin dynamics, can be readily applied. The Fenchal dual of the transformation function is used to transform the samples from the unconstrained space back onto the constrained space.   In the paper, the authors state that a "good" mirror map is required. It isn't quite clear what this means. It would seem from the main paper that the mirror map function, h, should be twice continuously differentiable. However, this seems to conflict with the results in the appendix where h \in C^5 and not h \in C^2. Could the authors please clarify?  In Section 3.2.2. (simplex section), a mirror map is given for the simplex example, however, it isn't clear how this is derived, or in fact, how one would create their own mirror in a different setting, e.g. sampling on the positive real line. Is there a general recipe that can be applied? How do you know that the chosen mirror map is optimal, assuming that there exists a wider class of mirror maps?  My main criticism of the paper is related to the simulation study, which is quite limited. It's a little strange that only two Dirichlet examples are given even though the authors could apply their methodology to other constrained spaces. Is there a reason why only the Dirichlet was considered?   Figure 1 only plots the results for the first dimension. Can we assume that the results are the same for all dimensions? This is an important point as it isn't completely clear whether or not the proposed approach works better than Patterson & Teh method (SGRLD) when sampling near to the boundary. It also appears from the simulation study that the improvement offered by the mirror map is only minor compared to SGRLD, could the authors comment on this further? Perhaps explain whether or not there are scenarios where SGRLD would be better.  Overall, this is a nice contribution to the stochastic gradient MCMC literature with strong supporting theoretical results. A particularly nice outcome of this paper is related to the simplex example, where the mirror map approach transforms the sampling problem from being non-log-concave to strictly log-concave.