Fast Mixing of Multi-Scale Langevin Dynamics under the Manifold Hypothesis
This addresses computational bottlenecks in image generation for researchers and practitioners, though it is incremental by building on existing Langevin Dynamics methods.
The paper tackles the slow mixing time of Langevin Dynamics for image generation by leveraging the manifold hypothesis to reduce mixing time from exponential in ambient dimension to depending on intrinsic dimension, and uses a multi-scale approach to trade off image quality and computational cost.
Recently, the task of image generation has attracted much attention. In particular, the recent empirical successes of the Markov Chain Monte Carlo (MCMC) technique of Langevin Dynamics have prompted a number of theoretical advances; despite this, several outstanding problems remain. First, the Langevin Dynamics is run in very high dimension on a nonconvex landscape; in the worst case, due to the NP-hardness of nonconvex optimization, it is thought that Langevin Dynamics mixes only in time exponential in the dimension. In this work, we demonstrate how the manifold hypothesis allows for the considerable reduction of mixing time, from exponential in the ambient dimension to depending only on the (much smaller) intrinsic dimension of the data. Second, the high dimension of the sampling space significantly hurts the performance of Langevin Dynamics; we leverage a multi-scale approach to help ameliorate this issue and observe that this multi-resolution algorithm allows for a trade-off between image quality and computational expense in generation.