Fast Mixing of Multi-Scale Langevin Dynamics under the Manifold Hypothesis

• URL: http://arxiv.org/abs/2006.11166v2
• Date: Mon, 22 Jun 2020 19:54:55 GMT
• Title: Fast Mixing of Multi-Scale Langevin Dynamics under the Manifold Hypothesis
• Authors: Adam Block, Youssef Mroueh, Alexander Rakhlin, and Jerret Ross
• Abstract summary: We show how the Langevin dimension algorithm allows for the considerable reduction of time depending on the (much) smaller data. Second, the high of the sampling space significantly hurts the performance of Langevin Dynamics.
• Score: 85.65870661645823
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Space-local memory in generalized master equations: Reaching the thermodynamic limit for the cost of a small lattice simulation [0.0]
  We introduce a novel approach that exploits finite memory in time textitand space to efficiently predict the many-body dynamics of dissipative lattice problems. We demonstrate the strengths of this method by focusing on nonequilibrium polaron relaxation and transport in the dispersive Holstein model.
  arXiv  Detail & Related papers  (2024-11-13T13:30:03Z)
• Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problems [78.96969465641024]
  We extend mean-field Langevin dynamics to minimax optimization over probability distributions for the first time with symmetric and provably convergent updates. We also study time and particle discretization regimes and prove a new uniform-in-time propagation of chaos result.
  arXiv  Detail & Related papers  (2023-12-02T13:01:29Z)
• Convergence of mean-field Langevin dynamics: Time and space discretization, stochastic gradient, and variance reduction [49.66486092259376]
  The mean-field Langevin dynamics (MFLD) is a nonlinear generalization of the Langevin dynamics that incorporates a distribution-dependent drift. Recent works have shown that MFLD globally minimizes an entropy-regularized convex functional in the space of measures. We provide a framework to prove a uniform-in-time propagation of chaos for MFLD that takes into account the errors due to finite-particle approximation, time-discretization, and gradient approximation.
  arXiv  Detail & Related papers  (2023-06-12T16:28:11Z)
• A scalable deep learning approach for solving high-dimensional dynamic optimal transport [18.67654056717166]
  We propose a deep learning based method to solve the dynamic optimal transport in high dimensional space. Our method contains three main ingredients: a carefully designed representation of the velocity field, the discretization of the PDE constraint along the characteristics, and the computation of high dimensional integral by Monte Carlo method in each time step.
  arXiv  Detail & Related papers  (2022-05-16T08:56:05Z)
• Multivariate Time Series Forecasting with Dynamic Graph Neural ODEs [65.18780403244178]
  We propose a continuous model to forecast Multivariate Time series with dynamic Graph neural Ordinary Differential Equations (MTGODE) Specifically, we first abstract multivariate time series into dynamic graphs with time-evolving node features and unknown graph structures. Then, we design and solve a neural ODE to complement missing graph topologies and unify both spatial and temporal message passing.
  arXiv  Detail & Related papers  (2022-02-17T02:17:31Z)
• Convex Analysis of the Mean Field Langevin Dynamics [49.66486092259375]
  convergence rate analysis of the mean field Langevin dynamics is presented. $p_q$ associated with the dynamics allows us to develop a convergence theory parallel to classical results in convex optimization.
  arXiv  Detail & Related papers  (2022-01-25T17:13:56Z)
• The Limiting Dynamics of SGD: Modified Loss, Phase Space Oscillations, and Anomalous Diffusion [29.489737359897312]
  We study the limiting dynamics of deep neural networks trained with gradient descent (SGD) We show that the key ingredient driving these dynamics is not the original training loss, but rather the combination of a modified loss, which implicitly regularizes the velocity and probability currents, which cause oscillations in phase space.
  arXiv  Detail & Related papers  (2021-07-19T20:18:57Z)
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling [55.498092486970364]
  Nesterov's Accelerated Gradient (NAG) for optimization has better performance than its continuous time limit (noiseless kinetic Langevin) when a finite step-size is employed. This work explores the sampling counterpart of this phenonemon and proposes a diffusion process, whose discretizations can yield accelerated gradient-based MCMC methods.
  arXiv  Detail & Related papers  (2020-06-16T15:07:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.