The development of efficient sampling algorithms catering to non-Euclidean
geometries has been a challenging endeavor, as discretization techniques which
succeed in the Euclidean setting do not readily carry over to more general
settings. We develop a non-Euclidean analog of the recent proximal sampler of
[LST21], which naturally induces regularization by an object known as the
log-Laplace transform (LLT) of a density. We prove new mathematical properties
(with an algorithmic flavor) of the LLT, such as strong convexity-smoothness
duality and an isoperimetric inequality, which are used to prove a mixing time
on our proximal sampler matching [LST21] under a warm start. As our main
application, we show our warm-started sampler improves the value oracle
complexity of differentially private convex optimization in $\ell_p$ and
Schatten-$p$ norms for $p \in [1, 2]$ to match the Euclidean setting [GLL22],
while retaining state-of-the-art excess risk bounds [GLLST23]. We find our
investigation of the LLT to be a promising proof-of-concept of its utility as a
tool for designing samplers, and outline directions for future exploration.

本文介绍了一种针对非欧几里得几何体的高效采样算法，该算法通过 log-Laplace 变换提供正则化性质，这种采样器匹配现有的欧几里得采样器，并在凸优化等领域表现出色。