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:
- 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.
- 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.
- 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.
- Rejection Sampling: Finally, a rejection step ensures the final point $\hat{\theta}$ lands within the original body $K$ and accurately follows the desired distribution.
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