Browsing by Author "Wang, Lihan"

Now showing 1 - 4 of 4

Open Access
Complexity of zigzag sampling algorithm for strongly log-concave distributions
Lu, Jianfeng; Wang, Lihan
We study the computational complexity of zigzag sampling algorithm for strongly log-concave distributions. The zigzag process has the advantage of not requiring time discretization for implementation, and that each proposed bouncing event requires only one evaluation of partial derivative of the potential, while its convergence rate is dimension independent. Using these properties, we prove that the zigzag sampling algorithm achieves $\varepsilon$ error in chi-square divergence with a computational cost equivalent to $O\bigl(\kappa^2 d^\frac{1}{2}(\log\frac{1}{\varepsilon})^{\frac{3}{2}}\bigr)$ gradient evaluations in the regime $\kappa \ll \frac{d}{\log d}$ under a warm start assumption, where $\kappa$ is the condition number and $d$ is the dimension.
Open Access
On explicit $L^2$-convergence rate estimate for piecewise deterministic Markov processes
Lu, Jianfeng; Wang, Lihan
We establish $L^2$-exponential convergence rate for three popular piecewise deterministic Markov processes for sampling: the randomized Hamiltonian Monte Carlo method, the zigzag process, and the bouncy particle sampler. Our analysis is based on a variational framework for hypocoercivity, which combines a Poincar\'{e}-type inequality in time-augmented state space and a standard $L^2$ energy estimate. Our analysis provides explicit convergence rate estimates, which are more quantitative than existing results.
Open Access
On explicit $L^2$-convergence rate estimate for underdamped Langevin dynamics
Cao, Yu; Lu, Jianfeng; Wang, Lihan
We provide a new explicit estimate of exponential decay rate of underdamped Langevin dynamics in $L^2$ distance. To achieve this, we first prove a Poincar\'{e}-type inequality with Gibbs measure in space and Gaussian measure in momentum. Our new estimate provides a more explicit and simpler expression of decay rate; moreover, when the potential is convex with Poincar\'{e} constant $m \ll 1$, our new estimate offers the decay rate of $\mathcal{O}(\sqrt{m})$ after optimizing the choice of friction coefficient, which is much faster compared to $\mathcal{O}(m)$ for the overdamped Langevin dynamics.
Open Access
Quantitative Analysis in Stochastic Homogenization and Hypocoercive PDEs in Sampling
(2021) Wang, Lihan
In this dissertation, we study two types of equations that involve randomness, and conduct quantitative analysis to study their ergodicity: (I) stochastic homogenization; (II) hypocoercive PDEs that arise from sampling.
In Chapter 2, we study the optimal numerical algorithms to compute the electrical field generated by a localized charge and an infinite random heterogeneous medium in dimension 3, only using the information of the medium in a large finite box. The algorithm is optimal if the medium is a sample from a stationary ensemble with a finite range of dependence. The algorithm is motivated by multipole expansion for stochastic homogenization, and the proof relies on estimates of second-order, next to first-order, correctors, which in turn relies on a parabolic semigroup estimate.
In Chapter 3, we provide an explicit estimate of exponential decay rate for underdamped Langevin dynamics in $L^2$ distance. To achieve this, we prove a Poincar\'{e}-type inequality in time-augmented state space, so that the exponential convergence is reduced to a standard energy dissipation estimate. Our new estimate provides a more explicit and simpler expression of decay rate; moreover, our estimate is the first that shows, for a wide variety of convex potentials, after optimizing the choice of friction coefficient, the underdamped Langevin dynamics converge much faster than the overdamped Langevin dynamics.
In Chapter 4, we establish $L^2$-exponential convergence rate for three popular piecewise deterministic Markov processes for sampling: the randomized Hamiltonian Monte Carlo method, the zigzag process, and the bouncy particle sampler. Similar to Chapter 3, our analysis is based on the variational framework for hypocoercivity, and also provides explicit convergence rate estimates that are more quantitative than existing results.
Finally in Chapter 5, we identify possible open problems and future research directions for both topics that follow the work established in this dissertation.