  We propose a sampling algorithm that achieves superior complexity bounds in
all the classical settings (strongly log-concave, log-concave,
Logarithmic-Sobolev inequality (LSI), Poincar\'e inequality) as well as more
general settings with semi-smooth or composite potentials. Our algorithm is
based on the proximal sampler introduced in~\citet{lee2021structured}. The
performance of this proximal sampler is determined by that of the restricted
Gaussian oracle (RGO), a key step in the proximal sampler. The main
contribution of this work is an inexact realization of RGO based on approximate
rejection sampling. To bound the inexactness of RGO, we establish a new
concentration inequality for semi-smooth functions over Gaussian distributions,
extending the well-known concentration inequality for Lipschitz functions.
Applying our RGO implementation to the proximal sampler, we achieve
state-of-the-art complexity bounds in almost all settings. For instance, for
strongly log-concave distributions, our method has complexity bound
$\tilde\mathcal{O}(\kappa d^{1/2})$ without warm start, better than the minimax
bound for MALA. For distributions satisfying the LSI, our bound is $\tilde
\mathcal{O}(\hat \kappa d^{1/2})$ where $\hat \kappa$ is the ratio between
smoothness and the LSI constant, better than all existing bounds.
