Sampling from Log-Concave Distributions with Infinity-Distance Guarantees
Authors: Oren Mangoubi
Nisheeth K Vishnoi
Venue: NeurIPS 2022 Accept (2022)
Keywords: sampling
differential privacy
log-concave distribution
infinity distance
Markov chains

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.

Sampling from Log-Concave Distributions with Infinity-Distance Guarantees
Oren Mangoubi Worcester Polytechnic Institute
Nisheeth K. Vishnoi Yale University
Abstract
For a d-dimensional log-concave distribution (0) x e constrained to con- vex body K, the problem of outputting samples from a distribution which is s-close infinity-distance suPłek log *(0)
v(0) arises in differentially private optimization. While sampling within total-variation distance & of i can be done by algorithms whose runtime depends polylogarithmicaly on prior algorithms for sampling & infinity distance have runtime bounds that depend polynomially algorithm that outputs point s-close in infinity distance that requires most poly(log' L d) calls to membership oracle for K and evaluation oracle for ʃ. when / is Lipschitz. Our approach de- parts from prior works that construct Markov chains error, and present a method to directly
on L. We bridge this gap by presenting
--dicreetization of K
to achieve sample with & convert continuous samples from K with total-variation bounds 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 log-concave distribution on polytopes K with infinity distance e, by plugging in TV-distance running time bounds for the Dikin Walk Markov chain.
Introduction
The problem of sampling from a log-concave distribution is as follows: For a convex body K C Rd and a convex function f K + R, output sample from the distribution T(f) x e ((0) This basic problem computer science, statistics, and machine learning. with applications
to optimization and integration [ 29] Bayesian statistics [39), reinforcement learning 16), and
differential privacy B2 20 24 Sampling exactly from ग known to computationally hard for most interesting cases of K and f [66] and, hence, the goal is to output samples from a distribution that is small (specified) "distance" to и. For applications such as computing the integral of bounds in the total variation (TV) distance [1] or KI. divergence (which implies a TVV bound) are sufficient. applications such as computing the expectation of Lipschitz function with respect to Wasserstein distance may also be sufficient. In differentially private optimization one requires bounds on the stronger infinity-distnce-
+ 20
v(0)
doo (v, T) = sup
log
(())
8EK
to guarantee pure differential privacy, and TV, KL, or Wasserstein bounds are insufficient; 14
Pure differential privacy (DP) is the strongest notion of DP and has been extensively studied (see e.g. the survey [14). It has advantages over weaker notions of differential privacy. E.g., when privacy of "groups" of individuals (rather than just single individuals) must be preserved, any mechanism which is (pure) E- E-DP (with respect to single individuals), is also kE-DP with respect to subsets of individuals. Motivated by applications to differential privacy, we study the problem of designing efficient algorithms to output samples from distribution which is e-close in d to I.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Related works. Several lines of work have designed Markov chains that generate samples from distributions that are close given log-concave distribution. These results differ in both their as- sumptions on the log-density and its support, as well as the distance used to measure closeness. One line of work includes bounds for sampling from log-concave distribution on a compactly supported convex body within TV distance (6)) including results with running time that is polylogarithmic
in
(as well as other results which give a running time bound that is polynomial in 3 5 41 ). In addition to assuming access to value oracle for f. some Markov chains just need access to a membership oracle for 1
30 29 BEI
18
while others assume that K is given polytope: They often also assume that K is contained in ball of radius R and contains a ball of smaller radius r. Many of these results assume that the target log- concave distribution satisfies "well-rounded" condition which says that the variance of the target distribution is (d) 60 29 or that it is in isotropic position (all eigenvalues of its covariance ma- trix are (1)) 25 when applied to log-concave distributions that not well-rounded or isotropic, these results require a "rounding" pre-processing procedure to find a linear transformation which makes the target distribution well-rounded or isotropic. Finally, it is often assumed that the func- tion f is such that f is L-Lipschitz or 3-smooth E4 including works handling the widely-studied special case when f is uniform on K where L = B 0 (see e.g.
30
{0 E R A0 I b} 2
33 35
34
26
PS 2
Another line of work gives sampling algorithms with bounds on the distance to the target density π in terms of Wasserstein distance [I3 M.. KL divergence 400 [2], and Renyi divergence [36). In contrast to works which assume access to an oracle for the value of f. many of these results instead assume access
oracle for the gradient of f and require the log-density to be L-Lipschitz or (-smooth on all of IRd (or on, e.g., a cube containing K) for some I., (3 > O. However, as noted earlier, bounds in the Wasserstein distance, KI. divergence, and o-Renyi divergence (for a oo) also do not imply bounds on the infinity distance, and the running time bounds provided by these works are polynomial in _. (See also Appendix A for additional discussion and challenges.)
Among prior works that give algorithms with bounds on dx 20 applies the grid walk Markov chain of (1] to sample from uniform distribution on convex body. [2] extends the approach
of 20 to log-Lipschitz log-concave distributions. Unlike the TV-distance case where algorithms whose rumning time depends logarithmically the error are known (e.g., 29 34 ). the best
available bounds for sampling within OE=) infinity-distance 20 have runtime that is polynomial in } and relatively large polynomial in d.
Our contributions. We present a new approach to output samples, which come with da bounds, from log-concave and log-Lipschitz distribution constrained to a convex body. Specifically, when K := {0- AO S b} is a polytope (where one is given A and b) our main result (Theorem 2.1 guarantees samples from distribution that is within O(s) error in dos and whose runtime de- pends logarithmically on _ compared to the polynomial dependence of (2]. Our approach departs from prior works that construct Markov chains on a 1 -idiserrtiiztooon of K to achieve a sample with & infinity-distance error, and we present method (Algorithm | to directly convert continuous samples from K with total-variatin bounds to samples with infinity bounds (Theorem 2.2). This continuous-ppace approach also allows us obtain an improvement on the dimension d in the run- ning time when K is a polytope by plugging in TV-distance running time bounds for the Dikin Walk Markov chain of [34). As immediate applications, we obtain faster algorithms for differentially private empirical risk minimization (Corollary 2.4) and low rank approximation (Corollary 2.5)
2 Results
Let B(c, = (= ( 1/2-11- u112 S $) and w denote the matrix matrix-multiplicationn constant.
Theorem 2.1 (Main result) There exists an algorithm which, given e, L,,r R O. A E Rmmxd b E R.m that define a polytope K := {0 E Rdd A0 & b} contained in a ball of radius R, a point E Rd such that K contains a ball B(a,r) r) of smaller radius r, and an oracle for the value of convex function f K > Rd, where f is L-Lipschitz. and defining π to be the distribution т & e- outputs a point from a distribution v such that doa (v. T) < e. Moreover, with very high probubilit this algorithm takes O(T) function evaluations and ((T x md=-1) arithmetic operations, where Rd+LRd j])-
T = O(m2d 2d d + m² dI. x [LR + d dlog(
re
1 'The number of steps is O(T x T). where B[r] S 3, (r 2 1) S (2)* for 1 2 0. and T S (Odlog( 4 +
LR) w.p. 1.
2

---

In comparison to the polynomial in runtime bounds of 22 Theorem 2.1 guarantees runtime that is logarithmic in 1. and also improves the dependence the dimension d, in the setting where K a polytope. Specifically, 2 show that the number steps of the grid walk to sample from a with infinity-distance error at most e is
o
( (d LLL polylog RR,
(Lemmaa 6.5 in the Arxiv version of 12). When applying their algorithm to the setting where f is constrained to a polytope K = fa E R Ar S b), each step of their grid walk Markov chain requires computing membership oracle for K and the value of the function f. The membership acle can be computed in ((md) arithmetic operations. Thus the bound on the number of arithmetic operations for each step of their grid walk is O(md) (provided that each function evaluation takes at most ((md) arithmetic operations). Thus the bound on the number of arithmetic operations to obtain a sample from is O (md' mdd I.A Tt*) x polylog( 7, R, d))) Thus, Theorem 2.1 improves on this bound by a factor of roughly e2m² de- For example, when m O(d.. as may be the case in differentially private applications, the improvement dd
We note that the bounds of 2 also apply in the more general setting where K is a convex body with membership oracle. One can extend our bounds to achieve runtime that is logarithmic in (and polynomial in d, L, R!) in the more general setting where K is convex body with membership oracle; we omit the details (see Remark 2.3)
Moreover, we also note that while there are several results which achieve O(5) TV bounds in time logarithmic in J. TV bounds do not in general imply (e)) bounds on the KL or Renyi divergence, or on the adinity-distance for any >> oF] On the other hand, an e-infinity-distace bound does immediately imply a bound of on the KI. divergence DKL, and a-Renyi divergence Da. since (ML n I d (14, T and (H, x) S d (1, TT) for any a >> 0 and any pair of distributions μı, w. Thus, under the same assumptions on K and f. Theorem 2.1 implies method of sampling from a Lipschitz concave log-density on K with E KL and Renyi divergence error in a number arithmetic operations that is logarithmic in 1. with the same bound on the number of arithmetic operations.
The polynomial dependence on 1 in 2 is due to the fact that they rely chain [. on a grid with cells of width w = O( (.5z). sample from æ within O(e) infinity-
discrete-space Markov
Since their Markov chain's 's runtime bound is polynomial in w they get runtime bound for sampling within (e)) infinity-distance that is polynomial in 1
5. The proof of Theorem 2.1 bypasses the use of discrete grid-based Markov chains by introducing Algorithm ! which transtorms any sample within = O(ce-d-nIAn TV distance of the distribution π εx e on the continuous set K (as opposed to a discretization of K), into a sample within O(e) infinity-distance from æ. This allows us to make use of a continuous-space Markov chain, whose step size is not restricted to a grid of width O LVd
and is instead independent of e, obtain sample within O(s) infinity-distance
from in time that is logarithmic in
Theorem 2.2 (Main technical contribution: Converting TV bounds to infinity-distane bounds)
There exists an algorithm (Algorithm D which, given E, R, L a membership oracle for convex body K contained in ball of radius R and containing a ball B(0, r), and an oracle which outputs point from a distribution μ which has TV distance
8 850 EX R(dlog( (B/,) + IRRP B/)/+IRR e-LR
Er
from a distribution л & 5 where : + is an L-Lipschitz function (see Appendix B for the exact values of ê and related hyper-parameters) outputs a point 0 E K such that the distribution
FFor instance, if =0) with support [0, 1), for every 8 there is distribution where ||2 k||TV < 28 and yet (v, x) 2 DKL(K, F) 2 $.2 (v(#) ed on 10, 6e $1. v(0) 1- 5 on
(b -, and v(0) = 0 otherwise)
3

---

of á satisfies (x)(v,)) S E. Moreover, with very high probabiliny this algorithm finishes in ((1) calls the sampling and membership oracles, plus ((d) arithmetic operations.
To the best of our knowledge Theorem 2.2 is the first result which for any L. R. 0, when provided as imput a sample from a continuous
TV distance 0 ö(s, r, R. L) > 0 from given distribution on a convex body K within some
distribution π on K, where K is contained in a ball of radius R and containing a ball of smaller radius т, outputs a sample with distribution within infinity- distance (e)) from This is in contrast to previous works [2] (see also 20 which applies only to the special case where π is the uniform distribution on K) which instead require as input sample with bounded TV distance from the restriction of discrete grid on K, and then convert this discrete-space sample into a sample within infinity-distacce (g) from the contimuous-space distribution π K R.
Algorithm 1: Interior point TV to distanc converter
Input: d E N
Input: A membership oracle for convex body K Rd and an > 0 such that B(0,r) S K.
Input: A sampling oracle which outputs a point from a distribution μ K +
Output: A point 0 E K.
Hyperparameters: A 0, Tiax (set in Appendix B
2 for i == I,..., Tmax do
Sample point μ Sample point & ~ Unif 1))
Set Z 8 Arg
Set 0 + -
i E K, output 0 with probability 1 and halt. Otherwise, continue.
7
8 end
Sample point ~ (ni,()((,r))
Output 0
10
Remark 2.3 (Extension to convex bodies with membership oracles) We note that Theorem 2. can be extended to the general setting where K is an arbitrary convex body in a ball of radius R and containing ball of smaller radius and only have membership oracle access to K. Namely, one can plug in the results of [29] to our Theorem 2.2 to generate a sample from a L- Lipschitz concave log-density on arbitrary convex body K in number of operations that is (pgay--loaiiithmii in z:r and polynomial on d, L, R. We omit the details.
Applications to differentially private optimization. Sampling from distributions with O(e) -nfinity-distace error has many applications differential privacy. Here, the goal to find ran- domized mechanism h n - R which, given dataset E D consisting of n datapoints, outputs model parameters 0 E R in some parameter space R, which minimize given (negative) utility function (0,xx), under the constraint that the output Ô preserves the pure a-differential pri- vacy of the data points x. randomized mechanism h DD" - R is said to be e-differentially private if for any datasets x; x' D which differ by single datapoint, and any S C R, we have that
P(h(x) E S) S P((((') E ES);
see
As one application of Theorem 2.1 we consider the problem of finding (approximate) minimum
i of empirical risk function f K Dn R under the constraint that the output Ô is g- differentially private, where f(0 = Σ
n (,, x.) Following (2). we assume that the (.(.)) given L 0. In this setting 2 show that the minimum ERM utility bound under the constraint that θ is pure E-differentially private, Egff(O,
L-Lipschitz for all E D N, for
mingek f00,z) = O dLR ), is achieved if one samples from the exponential mechanism ı ox e गंत! with infinity-distei distance error at most (EE). Plugging Theorem 2.1 into the framework of
"Algorithm I finishes in calls to the sampling and membership oracles, plus O(rd) arithmetic operations, where E|r] 3 and [F( 2 t) (3) for all > and 5d ()) 5LR + w.p. 1.

---

the exponential mechanism, we obtain a pure e-differentially private mechanism which achieves the minimum expected risk (Corollary 2.4 see Section C.I for proof).
Corollary 2.4 (Differentially private empirical risk minimization) There exists an algorithm which, given E, L, T, R. >> 0, A E Rmxxd , b I that define polytope K := {0 E R A0 s 6} contained ball of radius R and containing a ball ((0,r) r) of smaller radius r, and convex function f(0,x)) ()) = -iz Li(0, vi), where each l; K + R is L-Lipschitz, outputs random point i E K which is pure e-differentially private and satisfies
dLR
EgLs 2)1 min f(0, SO
Moreover, this algorithm takes at most T md arithmetic operations plus T evaluations of the function f. where T = O ((m?d' dd m² m2 dn?=?) (En + ddllog (*fd) (RRd)).
Corollary 2.4 improves on the previous bound 2 of O((22(1 + +n)dll + =2n'(m + n)dd) x L 1 polylog( n Rd )) arithmetic operations by factor of roughly max 2 : em? nd in the setting where the 4 are L-Lipschitz on a polytope K and each E, can be evaluated in O(d) operations. See Appendix for proof of this corollary.
As another application, we consider the problem of finding low-rank approximation of sample covariance matrix Σ = >> =i== u.u, where the datapoints t4; E I satisfy ||u/|| < 1, in differen- tially private manner. Given any > 0, the goal is find (random) rank-k projection matrix which maximizes the average variance [(, P)] of the matrix Σ (also reffered to as the utility of P), under the constraint that mechanism which outputs the matrix P e-differentially pri- vate. This problem has many applications to statistics and machine learning, including differentially private principal component analysis (PCA)
24
When privacy is not a concern, the solution /' which maximizes the variance is just projection matrix onto the subspace spanned by top-k eigenvectors of Σ, and the maximum variance satisfies (), = E A where A 2 .... 2 Aa > 0 denote the eigenvalues of E. However, when privacy concern, there is a tradeoff between the desired privacy level and the utility [p P)], and the maximum utility Ep [E, P)] one can achieve decreases with the privacy parameter E. The best current utility bound for an e-differentially private low rank approximation algorithm was achieved in [24]. who show that one can find a pure e-differentially private random rank-k projection matrix P such that [p P)] 2 (1-6) 81 Σ A whenever E X 2 Ω ( dk log }) for any 8 > 0. To generate the matrix P. their algorithm generates a sample, with infinity-distane Lipschitz concave log-density on polytope, and transforms this sample into projection matrix P. The sampling algorithm used in [24] has a bound of p d, X Aa) arithmetic operations and they leave as an open problem whether this can be improved from a polynomial dependence on to logarithmic dependence on 1. Corollary 2.5 shows that a direct application of Theorem 2.1 resolves this problem. (See Section for proot.)
error (c)), from
Corollary 2.5 (Differentially private low rank approximation) There exists an algorithm which, given a sample covariance matrix Σ Ei= u.u. its eigenvalues A1 2 ... Xd > an integer and e, outputs a random rank-k symmetric projection matrix P such that P is s-differentially private and satisfies the utility bound
" for datapoints uy E RR satisfying [|wl] S 1,
Ep E/ Σ M(E
whenever Ek= Xx) Z
C. log 1 for some universal constant C > 0. Moreover the number of 28
arithmetic operations is logarithmic in _ and polynomial in d and X1 Xd-
3 Proof Overviews
Given any e, and a function f TRd - R. the goal is to sample from a distribution T(0) x e(0)) constrained to a a d-dimensional convex body K with -nfinity-distanc error at most O(E) in number
5

---

of arithmetic operations that is logarithmic in We assume that K is contained in ball of some radius R > and contains a ball of some radius > O, and f L-Lipschitz. In addition we would also like our bounds to be polylogarithmic in 1., and polynomial in d, T,, R with a lower- order dependence on the dimension than currently available bounds for sampling from Lipschitz concave log-denn densitess on a polytope in anfinit-ddistane 22. We note that since whenever K is contained in a ball of radius R and contains a ball (30, r) of smaller radius т, we also have that ((0, r) C K S (0, 2R), without loss of generality, we may assume that r)),r) S K S B(0, R) as this would only change the bounds provided in our main theorems by a constant factor.
The main ingredient in the proof of Theorem 2.1 is Theorem 2.2 that uses Algorithm to transform a TV-bounded sample into a sample from π with error bounded in d Subsequently, we invoke Theorem 2.1 when K is given as polytope K := {xr E R Ax I b) and plug in the Dikin Walk Markov chain of [4 which generates independent samples from with bounded TV error. We first present an overview of the proof of Theorem 2 (The full proof has been omitted to space
restrictions and presented in Appendix B The proof of Theorem is presented Section 3.2
3.1 Converting samples with TV bounds to infinity bounds; proof of Theorem 2.2
Impossibility of obtaining log-dependence on infinity-distance via grid walk. One approach is to observe that if e/ has support on a discrete space S with most [.S] points, then any such that || - x||TV S
also satisfies
do (V, T) S 2 max e ((a)
minses e f=((=) X
for any S min T2)). This suggests forming grid G over K, then using discrete Markov chain to generate sample 9 within O(e) TV distance of the discrete distribution TG x e- with support on the grid G, and then designing an algorithm which takes as input and outputs a point with bounded infinity-distaney the special case when π is uniform on K, and then extended by (2) to log-Lipschitz log-concave distributions. In their approach, ( first run "grid-walk" Markov chain a discrete grid in cube containing K. They then apply the bound from M which says that the grid walk obtains a sample Z within TV distance O(d) from the distribution x e- (restricted the grid) in time that is polylogarithmic in z and quadratic in a where a is the distance between neighboring grid points. Since their grid has size |S| @(( (((
to the continuous distribution This approach was used in (20) in
)d), TV distance of O()) automatically implies an infinity-distance of (8ec S!). where is the ratio of the maximum to the minimum probability mass satisfying S e e..ft since f is L-Lipschitz on K C B(0, R). Thus, by using the grid walk to sample
within TV-distance d = 0 [STO] from the discrete distribution gG. they obtain sample Z which
also has infinity- distancee O(E) from &G. Finally, to obtain sample from the distribution x e- on the continuous space K, they sample a point uniformly from the "grid cell" [Z Z + a]d centered at Z. Since f' T.-Lipschitz, the ratio -1(2)
J(wy bounded by (ee) for all w in the grid cell [Z - a, Z + a]d as long as a = O (Ira)) implying that the sample is an infinity-distame of O()) from x ef_ However, since the running time bound of the grid walk is quadratic in a a=!, the grid coarseness a = O Lva
needed to achieve O(E) infinity-distanm from æ leads to a running time
bound which is quadratic in !.
To get around this problem, rather than relying on the use of discrete-space Markov chain such as the grid walk to sample within O(s) infinity-distance from ग, we introduce an algorithm (Algorithm which transforms any sample within 5 O (ee LR) TV distance from the distribution ı xx on the continuous space K (as opposed to a grid-based discretization of K), into a sample within (E) finiity-distance from This allows us to make use of continuous-spac. Markov chain, such as the Dikin walk of KE
whose step-size is not restricted by grid of coarseness = O Lvv
and instead is independent of e, in order to generate sample within (s)) infinity-distance from π in runtime that is logarithmic in
Converting continuous space TV-bounded samples to infinity-distanee bounded samples. As discussed in Section I there are many Markov chain results which allow one to sample from log-

---

concave distribution on K with error bounded in weaker metrics such as total variation, Wasserstein, or KL divergence. However, when sampling from continuous distribution, bounds these metrics do not directly imply bounds in infinity-distanc And techniques used to prove bounds in weaker metries do not easily extend to methods for bounding the infinity-distance; see Section A.T
Convolving with continuous noise. As first attempt, we consider the following simple algorithm: sample a point I ~ y from a distribution y with total variation error || H T|| S (()). Since
is L-Lipschitz, for any A & and any ball (2, A) in the A-interior of K (denoted by (K);
(u(z) S for all E int (K) by convolving ja with the uniform distribution on the ball B(0, A). Sampling from this
Definition B.1, we can obtain sample from distribution such that log
[(s))
distribution v can be achieved by first sampling 0 ~ μ and then adding noise ç ~ (n0 A)) to the sample 0.
m(2) Unfortunately, this simple algorithm does not allow us to guarantee that log( (og(% I at points 2 & (k)) which are a distance less than A from the boundary of K. see why, suppose that K [0, 1]d is the unit cube, that f is constant on K, and consider a point w (I...., 1) at the comnrr of the cube K. In this case could have that v(2) & 2 2-*x(=) for all in some ball
containing and hence de (v, T) sup log( ((=) ((=) 2 d2))(2), no matter how small we make A.
Stretching the convex body to handle points close to the boundary. To get around this problem, we m(*) would like to design an algorithm which samples from some distribution v such that log =(=) S
for all E K, including at points & near the corners of K. Towards this end, we first consider the special case where K itself contained the A A-interior of another convex body K", the function f K + I extends to an L-Lipschitz function on K' (also referred to here with slight abuse of notation as f) and where we are able to sample from the distribution xx e- on K' with O total variation error. If we sample 0 ~ e on K' with total variation error O(8) where 8 S se (R)) add noise & ~ Unif (0,, A))
for A LR and then reject 0 + only if it is not K, we obtain a sample whose distribution is O(s) from the distribution x e - on K in infinity-distance
However, we would still need to define and sample from such a convex body K", and to make sure that K" is not too large when compared to K; otherwise the samples from the distribution x e- on K' may be rejected with high probability. Moreover, another issue we need to deal with is that may not even be defined outside of K.
K
C
Y'
p
O
Figure 1: The construction used in the proof of Lemma
B.T
To get around these two problems, in Algorithm I we begin by taking as input a point 0 ~ p sampled from some distribution supported on K where || - k||Tv I 8 for some s ee llg((1) and add
noise& & ~ (B Ar) in order to sample from a distribution fa which satisfies log (()) for all 2 E in) Here r is the radius of the small ball contained in K; the choice of radius Ar for the noise distribution is because we will show in the following paragraphs that to sample from
A(=)
S
7

---

the distribution on K with anfinit-ddstaane error E it is sufficient sample a point in the Ar-interior of K and then apply "stretching" operation K.
We still need a method of sampling within (e)) infinity-distance error of x on all of K, including in the region K" K*Aint (K) near the boundary of K. Towards this end, after Algorithm generates point Z = 0 + & from the above-mentioned distribution p. it then multiplies Z by I-a and returns the resulting point 0 = --I Z if it is K, in other words, Z E (1 A)K. If we can show that
(1 -1-A7- K S intar (K), then this would imply that [log A(=) x(2) I & for all E (1 - A and hence
that the distribution of ò of the returned point & satisfies
((2)
i A)2)
1
log π T((1 - })=)
log
log
(1 - A) S (ee)
TT( A)²)
for all 2 E K. Since f is L-Lipschitz we have log (((1- A)8)
= OE)) for all E K, and hence we
would then have that the distribution á of the point returned by Algorithm satisfies
((2) log (2))
1(2) ([--A)=) O(s)) s O(E)
log
V2 K.
However, for ① to hold, we still need to show that (1 A)K C (K) (proved in Lemma B.1 In other words, we would like to show that for any point Z E (1 A)K, there is a ball B(Z, Ar) centered Z of radius Ar contained in K. To show this fact, it is sufficient to consider the convex hull C of B(O, r) U ( [ S K, and show that it contains the ball B(Z, Ar). Towards this end,
make the following geometric construction: we let p be point such that the line p0 is tangent to B(0, r). and q the point on pd which minimizes the distance ||g Z||2 (see Figure 1). Since Z0pp and ZZq are both right angles, we have that the triangles Op6 and ZgQ are similar triangles, and hence that - | In other words.
1
1 0|2
I-A 2
7| 4/12
xr=
x
A A
110
0/1
I-A Z
implying a ball of radius Ar centered at Z is contained C K, and hence that
A)K S in)
Bounding the infinity distance error. To complete the bound on the infinity-distance of the dis- tribution & of the point returned by Algorithm [ to the target distribution π. we must show both a lower bound (Lemma B.5) and an upper bound (Lemma B.6 on the ratio E(0) x(0) at every point 0 E K. Both the upper and lower bounds are necessary to bound the infinity-distance d (D(0), x0)) = supoek
log x(0)
218)
Both Lemmas B.5 and B.6 require the input point to have TV error å < ( - The term
R ( is a lower bound on the ratio of the volume of K to the volume of the smoothing ball B(0, Ar); this bound holds since K is contained in ball of radius R. The term e LLLR is lower bound on the ratio min x(()) of the minimum value of the density ' the maximum value of maxwex =(we
at any two points in K; this bound holds since f is L-Lipschitz.
The above choice of 8 ensures that in any ball B(z, Ar) with center a in the ir-interior of K, the distribution f of the input point, which satisfies || 1 k||rv I 6, will have between e and e times the probability mass which the target distribution π has inside the ball B(2, Ar). Thus, when the distribution j is smoothed by adding noise uniformly distributed on ball of radius Ar. the smoothed distribution 5(0) is within e and e times the target probability density r(0) at any point 0 in the Ar-interior of K, allowing us to bound the infinity distance error of the smoothed distribution 인 at any point 0 in the Ar-interior of K. We then apply this fact, together with Lemma
8

---

B.1 which says that for any point E K the point (1 A)0 is in the Ar-interior of K, to bound the distribution v of the output point (after the stretching operation) as follows,
Lemana 1A
(0) 2 (1-
11 ((1)) x x 10)) (2)
Here our choice of hyperparameter A < L. ensures that - -)" A1
211 and, since f is L-Lipschitz, that TT(1 A)0) 2 e < (0). This proves the lower bound (Lemma B.5 The proof
of the upper bound (Lemma B.6) follows in a similar way as equation but with the inequalities going in the opposite direction.
Bounding the number of iterations and concluding the proof of Theorem 2.2 We still need to deal with the problem that the point 0 may not be accepted. If this occurs, roughly speaking, we repeat the above procedure until point 0 with distribution & is accepted. To bound the number of iterations, show that θ is in K with high probability. Towards this end, first use the facts that f is L- Lipschitz and K S B(0, R). to show that the probability a point sampled from π oc e lies inside (1 -1- A) is at least (1 - A)de LAR 2 2 (Lemma B.2). Lemma B.2 says that you stretch the polytope by a factor of 1 I- then most of the volume of the stretched polytope (-- ) remains
inside the original polytope K. The term (1 -)= is just the ratio of the volume of (1 A to the volume of K. And, since f is I--Lipschitz, the term LALR bounds the ratio
=(0) of the target )(-=00)
density at any point 0 E K to the value of at the point T-2 O to which the stretching operation transports 0, whenever -- K. The choice of hyperparameter A max(d,L ensures that the acceptance probability (1 A)4e - guaranteed by Lemma B.2 is at least 9 Since the convex body (1 - A)K contains the ball B00, 5), applying Lemma
Iп B.1 second time (this time to the
convex body (1 A) we get that
(1 - 3A)K S int ((1 A)K).
Thus, by Lemma B.2 we have that 0 lies inside int ((1-A) with probability at least 10 (as O is sampled Irom æ with TV error 6). Therefore, since & ((, Ar), we must also have that the probability that the point i = --x (0 + E) is in K (and is therefore not rejected) greater than This implies that the number of iterations until our algorithm returns a point Ô is less than with probability at least 2- and the expected number of iterations is at most 2 (proved in Corollary B.4
9 5 2 8
10
Since each iteration requires random sample from the distribution μ4, and one call mem- bership oracle for K (to determine if H E K), the number of sampling oracle and membership oracle calls required by Algorithm D is (11) with very high probability. Therefore, with high proba- bility, Algorithm returns point 0 from distribution with infinity-distance most e from after O(1) calls to the sampling and membership oracles.
Since Algorithm succeeds with probability - - after k iterations, after
R
Tiax = 5d log(
+ 5LR +
iterations Algorithm 1 will have succeeded with probability roughly 1 (--(()) - In the very unlikely event that Algorithm [ still has not succeeded after Tmax iterations, Algorithm I simply outputs a point sampled from the uniform distribution on the ball B(0, r) of radius r contained in K. The probability mass of the target distribution æ inside this ball is at least as large as ( LR. thus, since is L-Lipschitz, distribution on this ball with probability =( =(A) 5d Sth does not change the 3o-distance error of the sample returned by the algorithm by more than
show in Corollary B.4 that outputing sample from the uniform
'In Algorithm we reject with a slightly higher probability to ensure that, in differential privacy appli- cations, in addition to the privacy of the point returned by the algorithm, the runtime is also e e-differentially private.

---

3.2 Completing the proof of Theorem 2.1
Proof: By Theorem |
the output of Algorithm | has infinity-distanee error bounded by as long as the input samples have TV distance eгror bounded by
R[( (/+) + LR)3 E e-LR
-d
850 E
er
and, with high probability, Algorithm 1 requires (1) such independent samples. To generate sample from i with TV enror O(6) when K {0 E R" A0 < bj is polytope defined by inequalities, we use the Dikin Walk Markov chain of R4 This Markov chain requires an initial point from some distribution PAo which is w-warm with respect to the stationary distribution и, that pa(#)
is, sup=e m[2) S w. To obtain a warm start, we let pi be the uniform distribution on the ball with radius r contained in K and sample from No- Since f is L-Lipschitz, and K is contained in a ball of radius R, Mu is w-warm with
1
max (00) x Voll - min,ex T())
R
d x E RL
w S
Vol(B(O,r)) x
we have that from this w-warm start the Dikin Walk Markov chain requires at most O((m²d + d² L R(²) ))) steps to generate sample with TV distance at most from n, where each step makes one function evaluation and O(md==1) arithmetic operations. Plugging in the above values of 6, w the number of Markov chain steps is
From 34
Rd + LRd )1
T O(m2m a + m2 ddd R²) [LR+ + d'log(
rE
generate each independent sample with the required TV error O()). Since the number of indepen- dent samples required as input for Algorithm D is (1) w.h.p., the number of arithmetic operations for Algorithm | to output a point with most infinity-distance error O(T mdd-1).
Finally, we note that in the more general setting where K is a convex body with membership oracle (but not necessarily) polytope, of 29 to generate samples from π with TV error O()) in a number of membership and function evaluation oracle calls that is polynomial in d and poly-logarithmic in z: R, We can then plug this sample into our Algorithm D to obtain a sample from x with infinity-distann error ((e) in a number of oracle calls that is logarrihhe in and polynomial d, L,, R. (see Remark 2.3
instead use, for instance, the hit-and-run Markov chain
4 Conclusion, Limitations, and Future Work
To the best of our knowledge, this the first work that presents an algorithm for sampling from log- concave distributions on convex bodies that comes with infinity-distance bounds and whose running time depends logarithmically on 1/e. Towards this, the main technical contribution is Algorithm
I (and Theorem 2.2) which achieves this improved dependence on by taking input continuous samples from a convex body with TV bounds and converting them to samples with infinity-distance bounds.
On the other hand, our bounds are polynomial in LR, yet there are algorithms for sampling from logconcave distributions т x e- on a convex body in the total variation distance that are poly- logarithmic in and do not assume f be Lipsehitz 29). Thus, the main open problem that remains is whether one can also obtain rumning time bounds for sampling in the infinity-distane which are poly-logarithmic R and do not require f to be Lipschitz.
Our main result also has direct applications to differentially private optimization (Corollaries 2.4 and 2.55 Differential privacy is notion which has been embraced in many technologies in societal contexts where privacy of individuals is a concern. Hence, we see our work to have a potential of positive societal impact and do not foresee any potential negative societal impacts.
Acknowledgments and Disclosure of Funding
This research was supported in part by NSF CCF-2104528, 19F-19,,347, and CCF-2112665 awards.
10

---

References
[1] David Applegate and Ravi Kanman. Sampling and integration of near log-concave functions. In Proceedings of the twenty-third annual ACM symposium Theory of computing, pages 156-163, 1991.
[2] Racf Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Effi- cient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464 473. IEEE, 2014.
[3] Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the SuLQ framework. In Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 128-138, 2005.
[4] Nicolas Brosse, Alain Durmus, Éric Moulines, and Marcelo Pereyra. Sampling from log- concave distribution with compact support with proximal Langevin Monte Carlo. In Confer- ence on Learning Theory, pages 319-342. PMLR, 2017.
[5] Sebastien Bubeck, Ronen Eldan, and Joseph Lehec. Finite-time analysis of projected Langevin Monte Carlo. In Advances in Neural Information Processing Systems, pages 1243-1251, Cite- seer, 2015.
[6] Olivier Chapelle and Lihong Li. An empirical evaluation of Thompson sampling. Advances in neural information processing systems, 24:2249-2257, 2011.
[7] Kamalika Chaudhuri, Anand Sarwate, and Kaushik Sinha. Near-optimal differentially private principal components. Advances in neural information processing systems, 25:989-9977 997999997,222 997, 2012.
[8] Yuansi Chen, Raaz Dwivedi, Martin J Wainwright, and Bin Yu. Vaidya walk: A sampling algorithm based on the volumetric barrier. In 2017 55th Annual Allerton Conference on Com- munication, Control, and Computing (Allerton), pages 1220-1227. IEEE, 2017.
[9] Xiang Cheng and Peter Bartlett. Convergence of Langevin MCMC in KL-divergence. In Algorithmic Learning Theory, pages 186-211. PMLR, 2018.
[10] Arnak Dalalyan. Theoretical guarantees for approximate sampling from smooth and log- concave densities. Journal of the Royal Statistical Society; Series B (Statistical Methodology), 79(3):651-676, 2017.
[11] Arnak S Dalalyan and Lionel Riou-Durand. On sampling from a log-concave density using kinetic Langevin diffusions. Bernoulli, 2663):1956 2020.
[12] Alain Durmus, Szymon Majewski, and Blazej Miasojedow. Analysis Langevin Monte Carlo via convex optimization. J. Mach. Learn. Res., 20:73-1, 20119.
[13] Alain Durmus and Eric Moulines. Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. Annals of Applied Probability, 27(3):155-11587, 2017.
[14] Cynthia Dwork and Aaron Roth. The algorithmic foundations differential privacy. Founda- tions and Trends in Theoretical Computer Science, 933-4)211--07, 2014.
[15] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: optimal bounds for privacy-presering principal component analysis. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 11-20, 2014.
[16] M. E. Dyer and A. M. Frieze. On the complexity of computing the volume of a polyhedron. SIAM Journal on Computing, 17(5):6679974, 1988.
[17] Alan Frieze and Ravi Kamnan. Soboley inequalities and sampling from log-concave dis- tributions. The Annals of Applied Probability, 91):14-26. 1999.
[18] Alan Frieze, Ravi Kannan, and Nick Polson. Sampling from log-coneave distributions. The Annals of Applied Probability, pages 812-837, 1994.

---

[19] Arun Ganesh and Kunal Talwar. Faster differentially private samplers via Rényi divergence analysis of discretized Langevin MCMC, Advances in Neural Information Processing Systems, 33, 2020.
[20] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 705-714, 2010.
[21] He Jia, Aditi Laddha, Yin Tat Lee, and Santosh S. Vempala. Reducing isotropy and volume to KLS: an O (n) volume algorithm. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 961-974. ACM, 2021.
[22] Richard Jordan, David Kinderlehrer, and Felix Otto. The variational formulation of the Pokker-Planck equation. SIAM journal on mathematical analysis, 29(1):1-17, 1998.
[23] Ravi Kannan and Hariharan Narayanan. Random walks on polytopes and an affine interior point method for linear programming. Mathematics of Operations Research, 37(1): 2012.
[24] Jonathan Leake, Colin S McSwiggen, and Nisheeth K Vishnoi. A polynomial-timg algorithm and applications for matrix sampling from Harish- Chandra--tayykkssnn--- densities. In ACM symposium on theory of computing STOC, 2021.
[25] Yin Tat Lee and Santosh Vempala. Eldan's stochastic localization and the KLS hyperplane conjecture: An improved lower bound for expansion. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 998- 190-1007. IEEE, 2017.
[26] Yin Tat Lee and Santosh S Vempala. Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation. In Proceedings of the 50th Annual ACM SIGAC7 Symposium on Theory of Computing, pages 1115-1121, 2018.
[27] László Lovász and Miklós Simonovits. Random walks in convex body and an improved volume algorithm. Random structures & algorithms, 4(4):359 1993.
[28] László Lovász and Santosh Vempala. Hit-and-run is fast and fun. preprint, Microsoft Research, 2003.
[29] László Lovász and Santosh Vempala. Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization. In Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on, pages 57-68. IEEE, 2006.
[30] László Lovász and Santosh Vempala. The geometry of logconeave functions and sampling algorithms. Random Structures & Algorithms, 30(3):307-358, 2007.
[31] Oren Mangoubi and Aaron Smith. Mixing of Hamiltonian Monte Carlo on strongly log- concave distributions: Continuous dynamics. The Annals of Applied Probability, in press.
[32] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE IEEE Symposium on Foundations of Computer Science (FOCS 077), pages 94-103. IEEE, 2007.
[33] Hariharan Narayanan. Randomized interior point methods for sampling and optimization. The Annals of Applied Probability, 26( 1):5976641, 2016.
[34] Hariharan Narayanan and Alexander Rakhlin. Efficient sampling from time-varying log- concave distributions. The Journal of Machine Learning Research, 18 18(1):011744055, 2017.
[35] Sushant Sachdeva and Nisheeth K Vishnoi. The mixing time of the Dikin walk in a polytope-a simple proof. Operations Research Letters, 44(5):630-63) 634, 2016.
[36] Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted Langevin algo- rithm: Isoperimetry suffices. In Advances in Neural Information Processing Systems, 2019,
[37] Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
[38] Nisheeth K. Vishnoi. An introduction to Hamiltonian Monte Carlo method for sampling-
CoRR, abs/2108. 12100,070..1077, 2021.
12

---

[39] Max Welling and Yee W Teh. Bayesian learning via stochastic gradient Langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-11), pages 681-688. Citeseer, 2011.
[40] Andre Wibisono. Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem. In Conference on Learning Theory, pages 2093-3021 PMLR, 2018
13

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A]. You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [N/A]
Did you include the license the code and datasets? [N/A]
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes] (See
Section 41
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] (See Section Appendix B and C
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] See supple- mentary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report enror bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (c.g., code, data, models) curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're re're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "QEB7iZoNM1K", "reviewer": "Reviewer_JJsb", "summary": "This paper proposes an algorithm to approximately sample from a log-concave distribution over a convex continuous body. In applications like Bayesian statistics, sampling exactly from a distribution often turns out to be difficult because its explicit form is known only up to proportionality. Also, one legacy application is to integrate a log-concave log-Lipschitz function over a convex body. One common practice to tackle such problems is to construct a Markov Chain over the discretized constraint space. Although such a method can generate samples from a distribution $\\epsilon$ close in total variation distance to the true distribution in computation time $polylog(1/\\epsilon)$, it fails to give a similar computation time algorithm to generate samples from  $\\epsilon$ close distribution in infinity-distance. The proposed sampling algorithm in this paper is able to give $poly(\\log 1/\\epsilon, d)$ guarantee on runtime to generate $\\epsilon$ infinity distance samples. The result also improves upon the dependency on dimension d in comparison to the state of the art. The result has its application in optimization preserving differential privacy in mechanism design game theory literature. The novelty of the method proposed here is to take a sample which is $O(\\epsilon)$ close in TV distance and convert it to $O(\\epsilon)$ close sample in infinity distance. It effectively uses a continuous-space Markov chain to bypass the limitation of the previous methods. The simulation of the continuous-space Markov chain has been done by convolving the initial sample with uniform noise followed by rejection sampling.\n\nThe paper is well written and well organized.\n\nRelevance: The result is quite relevant the authors have shown its applications in differentially private optimization. Nevertheless, approximate sampling from log-concave distributions with various distance guarantees has been at the core of learning literature\n\nCorrectness: The authors have given proof ideas of their main theorems. Although I have not been through the minute details, overall they seem to be correct.\n", "questions": "None.", "limitations": "None.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The work is original, clear, and relevant. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "G5Lu8HDxqDx", "reviewer": "Reviewer_HEwz", "summary": "The main aim of the paper is to introduce a sampling scheme with guarantees in the infinity distance when the sampled measure is log-concave.  Several applications and consequences, in differential privacy, are then demonstrated.", "questions": "Question/concern about Corollary 2.5:\nIn this application, there is a convex function $f(\\theta) = \\sum \\ell_i(\\theta, x_i)$ where $x_i \\in \\mathbb{R}^n$ and the task is to sample from $\\pi \\propto e^{-f(\\theta)/ \\epsilon}d\\theta$. The solution is to use the Dikin random walk to sample from $\\pi$ in total variation and then to use the above procedure to upgrade the guarantee to the infinity distance. The claim is that the output is differentially private.\n\nNow, I certainly agree that any point sampled from $\\pi$ (or something close to it) is differentially private. However, the Dikin random walk proceeds by evaluating the value of $f(\\theta)$ at each iteration, and the value of $f$ *depends* on the sample $\\{x_i\\}$.\nSo each iteration of the Dikin random walk is not private, and reveals something about the function being optimized and hence the sample.\n\nMoreover, I'm not sure I agree with the statement \"Otherwise, we output \n$\\hat{\\theta}= 0 \\in K$, which is clearly $\\epsilon$-differentially private since this output does not depend on the data\". If the algorithm fails to stop it is more likely that the sampled points were near the boundary of the body. The probability of this happening depends on the function being optimized, which again depends on the sample. \n\nAs I indicated above, I am not an expert in differential privacy. If I missed something basic I would appreciate the authors' explanation.\n\nMinor comments:\n- Line 58: \"bounds in the Wasserstein distance, KL divergence, and Renyi divergence metrics also do\n59 not imply bounds on the infinity distance,\" Isn't the Infinity distance simply the infinity Renyi divergence?\n\n- Theorem 2.2: $f$ should be declared to be convex.\n\n- Even after reading Remark 2.3 I find it very weird that Theorem 2.1 is stated with respect to polytopes and Theorem 2.2 is with respect to arbitrary convex bodies.\n\n- Corollary 2.2: Again, $f$ should be declared to convex.\n\n- Figure 1 really belongs in the appendix where it gives a visual aid to the proof.\n\n- Corollary B.4: This is not really important, but perhaps it is worth mentioning that the stopping time $\\tau$ has a (or more precisely dominated by) a geometric distribution. This immediately gives the tail and expectation bounds.\n\n- Line 728: Is $y$ distributed like $\\mu$ or $\\hat{\\mu}$ (it is $\\mu$ in the paragraph preceding the statement of the Lemma). It might be a good idea to remind the readers of all $\\mu$ and $\\nu$ notation before stating the lemma.\n\n- The authors make repeated use of the trivial inequality $\\max \\pi(\\theta) *Vol(B(0,R)) \\geq 1$. It could be helpful to state it somewhere at the beginning of the section and refer back to it,\n\n- Line 731-732: I think there is an offset in the 'numbering' of the inequalities.\n\n- Line 760: Should $B(0,r)$ be $B(a,r)$?\n\n---------------------------------------------------------------------------------------------------------------------------\nPost Rebuttal: The authors addressed my concerns and I raised my score.", "limitations": " The authors adequately addressed the limitations and potential negative societal impact of their work", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem of sampling in the so-called 'infinity distance' is an interesting problem that has gained some attention recently, mostly because of its potential applications to differential privacy. In this respect, the paper makes an interesting contribution that should be of interest to the NeurIPS community. \n\nOne major comment from my side is that this is not a paper about sampling. The main result is a somewhat simple and intuitive observation that shows how to 'upgrade' guarantees in total variation to guarantees in the infinity distance.\nWith slightly more details, suppose that one wishes to sample from the log-concave measure $\\pi$ and that one was able to attain a sample from $X \\sim \\mu$ which is close to $\\pi$ in total variation. Then, by smoothing $\\mu$ (with a convolution kernel), stretching it (by multiplying $X$ by a constant), and then conditioning it back to the support of $\\pi$ one gets a new law whose density is similar to $\\pi$ almost everywhere. From the description, it is clear that this procedure can be made algorithmic and it is shown that as long as $\\pi$ also has a log-Lipschitz density then the infinity distance guarantees are good.\n\nGiven my criticism above, I wish to emphasize one point. Even if the observation seems to be simple, it was not observed before, and its simplicity could be seen as an advantage, both since it is easily implementable and because it is easy to understand. I read through most of the proofs and could follow everything easily (I did find the informal explanation in the main body to be a bit confusing).\n\nI have one concern, which I detail below, related to one of the applications. It could be that the concern comes from my lack of expertise in differential privacy, and I am prepared to raise my score after reading the author's response.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FIR219hL1X-", "reviewer": "Reviewer_YRWJ", "summary": "This work gives the first algorithm (or rather \"meta-algorithm\") for sampling from log-concave distributions with an $\\epsilon$ infinity-distance guarantee and runtime which only has a poly-logarithmic dependence on $1/\\epsilon$. In particular, this paper provides a technique to convert any sampling algorithm with TV distance guarantees to one with infinity-distance guarantees. Further, they provide applications of their result in differentially private optimization i.e. differentially private empirical risk minimization and differentially private low-rank approximation. ", "questions": "Since the paper has strong theoretical contributions, I am okay with it not having any experiments. But it would be interesting to see how the current algorithm (it looks simple to implement) would compare in practice to previous algorithms with infinity-distance guarantees on well-known log-concave distributions.", "limitations": "Yes.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: I am not an expert in this area so I am not entirely sure about other related work. From reading the paper, this is a clear advance over previous state-of-the-art in sampling from log-concave distributions with infinity-distance guarantees.\n\nQuality: The submission is technically sound. All claims are well-supported with proofs. \n\nClarity: The submission is clearly written and well-organized.\n\nSignificance: Yes, the problems being studied are quite significant. Log-concave distributions are extremely well-studied in the literature with lots of applications. In particular, sampling from log-concave distributions with infinity-distance guarantees has applications in differential privacy, as shown in the applications in this work. Even otherwise, it is a very natural question to study. Improvement from runtimes that are poly(1/$\\epsilon$) to poly-log(1/$\\epsilon$) is an exponential improvement and so it is quite significant.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4OZUT_F-flX", "reviewer": "Reviewer_JWN3", "summary": "The authors propose an approximate sampling algorithm for compactly supported, log-concave, Lipschitz distributions. They prove that the distribution of the sample output by their algorithm is guaranteed to be $\\epsilon$-close in *infinity distance* to the target distribution in $\\mathcal{O}(\\mathrm{poly}(\\log\\epsilon^{-1}, d))$ steps, where $d_\\infty(q, p) = \\sup_x \\lvert \\log q(x) - \\log p(x) \\rvert$.\n\nThe key ingredient of their algorithm is a rejection sampler that takes an approximate sample whose law is already $\\delta$-close to the target in TV distance for some appropriately chosen $\\delta$. Then, it outputs another approximate sample with the required $\\epsilon$ infinity distance guarantee. They note that they can use previous methods that require $\\mathcal{O}(\\mathrm{poly}(\\log\\epsilon^{-1}, d))$ steps to attain a sample whose law is within the required $\\delta$ TV bound. Hence, combining it with their rejection sampler gives the desired result.\n\nThe authors also show that their method immediately yields more efficient solutions to some previously studied differentially privacy problems.  ", "questions": " ", "limitations": " ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\nThe authors study a relevant problem and propose an elegant solution to it that significantly improves the best known asymptotic runtime for the problem, from $\\mathcal{O}(\\epsilon^{-2}\\mathrm{poly}(d))$ to $\\mathcal{O}(\\mathrm{poly}(\\log\\epsilon^{-1}, d))$ steps. I appreciated that the authors also give some intuition in the main text and a lot more in Appendix A regarding why extending previous methods won't yield a solution as good as theirs.\n\nThe rejection sampler is a nice, simple algorithm and the proofs showing its desired properties are nicely laid out and clearly written. I checked the proofs in Appendix B and believe they are all correct.\n\nAltogether, I think the paper is a solid contribution to the literature.\n\n# Weaknesses\n\nThe greatest weakness of the paper is the lack of experiments, even in the supplementary material. I think it would be particularly nice if the authors could construct a distribution that is within the required TV distance to an appropriate target but far in terms of infinity distance and run their rejection sampler. Then, they could show that within the expected number of steps, the histogram of the samples output by their algorithm is within the required infinity distance to the target.\n\nThe second weakness is that I found the description of the second DP problem unnecessarily technical and hard to follow, in contrast with the rest of the paper. I would either make its description higher level or give more detail, as currently, it is quite hard to follow without a background in DP.\n\n## Miscellaneous & Typos\n - The whole paper, including the main text, has been uploaded as the supplementary material.\n - There is a slight inconsistency in the exposition in Section 2: the authors allow the inner ball to be centred at an arbitrary point $a$, while in Alg 1 and Section 3, they require the inner ball to be centred at the origin. This is especially confusing, as they later reuse $a$ as the distance between certain grid cells on L220 in Section 3.1. However, I believe that this shouldn't change any of their results.\n - I believe the lower bound on the infinity distance on L257 should be $d\\log 2$ instead of $2^d$.\n - What is the $E_P[\\cdot]$ operator on L179 and L189?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept