Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

The paper is well written and well organized.

Relevance: 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

Correctness: 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.

strengths_and_weaknesses: The work is original, clear, and relevant. 
questions: None.
limitations: None.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
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.

Quality: The submission is technically sound. All claims are well-supported with proofs. 

Clarity: The submission is clearly written and well-organized.

Significance: 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.

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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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$.

The 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.

The authors also show that their method immediately yields more efficient solutions to some previously studied differentially privacy problems.  
strengths_and_weaknesses: # Strengths
The 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.

The 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.

Altogether, I think the paper is a solid contribution to the literature.

# Weaknesses

The 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.

The 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.

## Miscellaneous & Typos
 - The whole paper, including the main text, has been uploaded as the supplementary material.
 - 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.
 - I believe the lower bound on the infinity distance on L257 should be $d\log 2$ instead of $2^d$.
 - What is the $E_P[\cdot]$ operator on L179 and L189?
questions:  
limitations:
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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. 

One 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.
With 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.

Given 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).

I 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.
questions: Question/concern about Corollary 2.5:
In 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.

Now, 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\}$.
So each iteration of the Dikin random walk is not private, and reveals something about the function being optimized and hence the sample.

Moreover, I'm not sure I agree with the statement "Otherwise, we output 
$\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. 

As I indicated above, I am not an expert in differential privacy. If I missed something basic I would appreciate the authors' explanation.

Minor comments:
- Line 58: "bounds in the Wasserstein distance, KL divergence, and Renyi divergence metrics also do
59 not imply bounds on the infinity distance," Isn't the Infinity distance simply the infinity Renyi divergence?

- Theorem 2.2: $f$ should be declared to be convex.

- 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.

- Corollary 2.2: Again, $f$ should be declared to convex.

- Figure 1 really belongs in the appendix where it gives a visual aid to the proof.

- 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.

- 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.

- 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,

- Line 731-732: I think there is an offset in the 'numbering' of the inequalities.

- Line 760: Should $B(0,r)$ be $B(a,r)$?

---------------------------------------------------------------------------------------------------------------------------
Post 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
review_title: null

Meta-review: metareview: Sampling from log-concave distributions is a well studied problem and there are many existing algorithms that can sample from a distribution close to the true distribution up to a small total variation distance. The paper gives a new reduction that can use these algorithms as a subroutine to get samples from a distribution close to the true distribution in infinity distance i.e. the densities are close everywhere. This problem commonly arises in differentially private optimization. The reduction is simple and can be implemented easily. All reviewers agree that the paper is a significant contribution to the literature, it is well written, and the algorithm has potential to be useful in practice.
confidence: Certain
Decision: Accept