FLAIRGEORGIA TECH

FLAIR · project

Proximal sampler: Improved Dimension Dependence of a Proximal Algorithm for Sampling

How does the cost of sampling grow with the dimension of a probability distribution? This work improves that dependence for the proximal sampler, an algorithm whose efficiency hinges on a subproblem called the restricted Gaussian oracle.

An efficient approximate oracle

The central idea is to implement this oracle using approximate rejection sampling. The analysis controls the error introduced by the approximation through a concentration inequality for semi-smooth functions under Gaussian distributions. This allows a less expensive oracle to be used while retaining guarantees for the overall sampling algorithm.

Guarantees across target distributions

The resulting complexity bounds cover strongly log-concave and log-concave targets, distributions satisfying logarithmic Sobolev or Poincaré inequalities, and more general semi-smooth or composite potentials. The paper’s contribution is an improved dependence on dimension across these settings, with assumptions and error guarantees stated for each case. It builds on the proximal sampling framework while refining its key computational step.

Publication

Improved Dimension Dependence of a Proximal Algorithm for Sampling

Jiaojiao Fan, Bo Yuan, and Yongxin Chen

COLT 2023