Sampling from Log-Concave Distributions with Infinity-Distance Guarantees

Oren Mangoubi, Nisheeth K. Vishnoi

In the realm of probabilistic algorithms, "close enough" is typically measured using Total Variation (TV) distance. If you are sampling from a distribution, TV distance guarantees that, on average, your samples will resemble the target distribution. However, for high-stakes applications like Differential Privacy (DP), "on average" is insufficient. DP requires a strict guarantee that the probability of any specific outcome is almost exactly what it should be. This necessitates a much more rigorous metric: Infinity-Distance ($d_\infty$).

Historically, achieving these ironclad infinity-distance guarantees was computationally prohibitive. While TV-distance sampling could be executed in time logarithmic to the error ($1/\epsilon$), infinity-distance sampling required time polynomial in $1/\epsilon$. In their NeurIPS 2022 paper, Oren Mangoubi and Nisheeth K. Vishnoi bridge this gap, introducing the first algorithm that achieves infinity-distance guarantees with a runtime that scales logarithmically with the error.

The Challenge: Total Variation vs. Infinity Distance

The authors address the challenge of sampling from a log-concave distribution $\pi(\theta) \propto e^{-f(\theta)}$ constrained within a convex body $K$ (such as a polytope).

Standard sampling algorithms, like the Dikin Walk or Hit-and-Run, are highly efficient at converging in TV distance. However, in Pure Differential Privacy, one must ensure that for any two neighboring datasets, the ratio of the output densities is strictly bounded. This translates directly to requiring a small infinity-distance: $$d_\infty(\nu, \pi) := \sup_{\theta \in K} \left| \log \frac{\nu(\theta)}{\pi(\theta)} \right| \leq \epsilon$$

Previous methods for $d_\infty$ sampling relied on discretizing the continuous space into a very fine grid. Because the grid had to be incredibly dense to provide these strong guarantees, the runtime exploded as the required error $\epsilon$ shrank. The "holy grail" in this domain was to find a continuous-space algorithm that could match the efficiency of TV-distance samplers without relying on grid discretization.

The Solution: A Continuous-Space Converter

The core contribution of this work is a novel "TV-to-infinity-distance converter." Rather than building a new Markov Chain from scratch, the authors provide a post-processing recipe that transforms standard samples into samples with strong $d_\infty$ guarantees:

  1. Start with a TV-close sample: Utilize an existing efficient sampler (like the Dikin Walk) to obtain a point $\theta$ from a distribution $\mu$ that is close to $\pi$ in TV distance.
  2. Add Noise (Convolution): Add a small amount of uniform noise to the sample. This "smooths" the distribution, a standard technique used to transition from TV to $d_\infty$ bounds.
  3. The "Stretching" Trick: Smoothing often fails near the boundaries of the convex body $K$ because the noise "ball" might spill outside the allowed space, distorting the density. To resolve this, the authors apply a geometric transformation that "stretches" the points away from the boundary toward the interior.
  4. Rejection Sampling: Finally, a rejection step ensures the final point $\hat{\theta}$ lands within the original body $K$ and accurately follows the desired distribution.
Geometric stretching operation to ensure boundary resilience.

This stretching operation, defined as $\hat{\theta} = \frac{1}{1-\Delta} Z$, is a critical insight. It ensures that every point considered has a "safety buffer" (an interior ball) around it. This buffer allows the noise convolution to behave predictably, even near the edges of complex shapes. By staying in continuous space and using this stretching operation, the algorithm avoids the polynomial runtime penalty associated with grid-based walks.

Key Results and Applications

By combining this converter with the Dikin Walk (for polytopes) or Hit-and-Run (for general convex bodies), the authors achieve several breakthrough results:

  • Logarithmic Speedup: The algorithm's runtime is $O(poly(\log 1/\epsilon, d))$, where $d$ is the dimension. This is a massive improvement over prior $O(poly(1/\epsilon))$ bounds.
  • Faster DP-ERM: The authors apply their sampler to Differentially Private Empirical Risk Minimization (ERM). They demonstrate that optimal utility for "pure" DP can be achieved with significantly fewer arithmetic operations than previously possible.
  • DP Low-Rank Approximation: The paper provides the first algorithm for differentially private low-rank approximation (PCA) where the complexity depends only logarithmically on the inverse privacy and error parameters.

Limitations and Future Directions

While this paper presents a major theoretical leap, a few limitations remain. The current bounds depend polynomially on the Lipschitz constant $L$ of the function $f$ and the radius $R$ of the body. In standard TV sampling, some algorithms can achieve polylogarithmic dependence on the "aspect ratio" ($R/r$); extending this efficiency to $d_\infty$ remains an open challenge.

Additionally, the algorithm assumes a "warm start" (an initial point or distribution to start the Markov Chain). While standard in theory, finding these warm starts for highly complex bodies can still be a practical bottleneck. Finally, while this paper focuses on the gold standard of "pure" DP, exploring how these $d_\infty$ converters could optimize "approximate" DP (which is slightly more lenient) could pave the way for even faster practical implementations.

Summary updated

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.
BibTeX
@inproceedings{mangoubi2022sampling,
  author = {Oren Mangoubi and Nisheeth K. Vishnoi},
  title = {{Sampling from Log-Concave Distributions with Infinity-Distance Guarantees}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=nmhAZzmfOcv},
}
Figure