Abstract
For a $d$-dimensional log-concave distribution $\pi(\theta) \propto e^{-f(\theta)}$ constrained to a convex body $K$, the problem of outputting samples from a distribution $\nu$ which is $\varepsilon$-close in infinity-distance $\sup_{\theta \in K} |\log \frac{\nu(\theta)}{\pi(\theta)}|$ to $\pi$ arises in differentially private optimization. While sampling within total-variation distance $\varepsilon$ of $\pi$ can be done by algorithms whose runtime depends polylogarithmically on $\frac{1}{\varepsilon}$, prior algorithms for sampling in $\varepsilon$ infinity distance have runtime bounds that depend polynomially on $\frac{1}{\varepsilon}$. We bridge this gap by presenting an algorithm that outputs a point $\varepsilon$-close to $\pi$ in infinity distance that requires at most $\mathrm{poly}(\log \frac{1}{\varepsilon}, d)$ calls to a membership oracle for $K$ and evaluation oracle for $f$, when $f$ is Lipschitz. Our approach departs from prior works that construct Markov chains on a $\frac{1}{\varepsilon^2}$-discretization of $K$ to achieve a sample with $\varepsilon$ infinity-distance error, and present a method to directly convert continuous samples from $K$ with total-variation bounds to samples with infinity bounds. This approach also allows us to obtain an improvement on the dimension $d$ in the running time for the problem of sampling from a log-concave distribution on polytopes $K$ with infinity distance $\varepsilon$, by plugging in TV-distance running time bounds for the Dikin Walk Markov chain.
Introduction
Sampling from log-concave distributions constrained to convex bodies is a cornerstone of modern machine learning, supporting tasks ranging from Bayesian inference to high-dimensional optimization. In practice, exact sampling is computationally prohibitive, leading researchers to rely on algorithms that produce samples from a distribution $\nu$ that is "close" to the target distribution $\pi$.
The standard metric for "closeness" in the sampling literature is Total Variation (TV) distance. However, for applications in pure differential privacy (DP), TV distance is insufficient. Pure DP requires guarantees in infinity-distance ($d_\infty$), defined as the supremum of the log-ratio of the two densities. This metric ensures that the probability ratio is bounded even in the extreme tails of the distribution—a strict requirement for the privacy-loss guarantees of DP.
The Challenge: TV vs. Infinity Distance
Existing algorithms for sampling in TV distance are highly efficient, with runtimes scaling polylogarithmically with the inverse error tolerance ($\log(1/\varepsilon)$). In contrast, prior methods for achieving infinity-distance guarantees have been significantly slower. These methods typically relied on discretizing the convex body into a fine grid (a $1/\varepsilon^2$-discretization), leading to runtimes that scale polynomially with $1/\varepsilon$. This "curse of the grid" makes such algorithms impractical for high-dimensional problems or high-precision requirements.
Methodology: The Continuous Conversion Algorithm
This paper introduces a novel "converter" algorithm that upgrades samples from standard, fast Markov chains (which provide TV guarantees) into samples that satisfy infinity-distance bounds. The approach avoids discretization entirely by staying in continuous space.
1. Baseline TV Sampling
The process begins by using an optimized continuous-space Markov chain, such as the Dikin Walk, to generate a sample that is close to the target distribution $\pi$ in TV distance.
2. Continuous Noise Addition
To bridge the gap between TV and infinity distance, the algorithm adds a small amount of continuous uniform noise to the initial sample. This smoothing step is critical for bounding the density ratios across the entire domain.
3. Geometric Stretching and Rejection
Adding noise near the boundary of a convex body $K$ presents a challenge: the noise might push the sample outside the feasible region. To resolve this, the authors employ a "stretching" trick. The noisy sample is multiplied by a scaling factor slightly greater than 1, expanding the distribution outward. A rejection sampling step is then applied to ensure the final sample remains within the original boundary $K$. This geometric approach ensures that the probability mass is properly bounded without requiring complex reflection mechanics or grid-based constraints.
Key Results and Theoretical Contributions
The proposed algorithm yields several significant improvements over the state-of-the-art:
- Exponential Speedup in Error Dependence: The runtime dependence on the error tolerance $\varepsilon$ is reduced from polynomial ($1/\varepsilon^2$) to logarithmic ($\log(1/\varepsilon)$).
- Improved Dimensionality Scaling: For polytopes defined by $m$ inequalities in $d$ dimensions, the algorithm improves the arithmetic operation bound by a factor of approximately $\frac{1}{\varepsilon^2} m^3 d^{8-\omega}$ compared to previous grid-walk methods.
- Applications to DP-ERM: The sampler enables a pure $\varepsilon$-differentially private algorithm for Empirical Risk Minimization (ERM) that achieves optimal theoretical utility with significantly reduced computational overhead.
- Solving DP-PCA: The authors apply the sampler to provide a differentially private low-rank approximation (PCA) method, solving an open problem regarding runtimes logarithmic in $1/\varepsilon$.
Limitations and Future Work
While the algorithm provides a massive improvement in error scaling, it currently assumes that the target function's log-density is $L$-Lipschitz and that the convex body is contained within a ball of radius $R$. The runtime remains polynomial with respect to $L$ and $R$. Future research may explore whether these logarithmic infinity-distance bounds can be achieved without the Lipschitz assumption or with polylogarithmic dependence on the radius $R$.
Conclusion
By decoupling the sampling process from the bounding process, this work provides a general framework for upgrading TV-distance samplers to meet the more stringent requirements of infinity-distance. This result not only advances the theory of log-concave sampling but also provides a practical path forward for high-performance, purely differentially private machine learning.
Summary updated