In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies

Summary

In this paper, the authors consider the problem of uniform sampling from general convex body. The algorithm works by augmenting the state space followed by performing alternative Gibbs sampling, where one of the inner steps is implemented by rejection sampling. Non-asymptotic end-to-end bounds on the mixing time in Renyi divergence under warmness assumption is established. The analysis takes the view of the two updates as forward / backward heat flows, building on existing proximal sampler work, therefore offers a clean stochastic process perspective on the algorithm. Various connections of the proposed algorithm to ball walk and speedy walk are also discussed.

Strengths

The paper is clearly written and well-structured. Relevant related works are adequately surveyed with the topic being of great interest to many problems in machine learning and computational statistics. While the results and analysis build on the existing framework of proximal sampler for log-concave sampling, I think there are contributions in the paper to this new setting that's worth sharing with the community. The approach is conceptually simple and offers a fresh perspective on constrained sampling.

Weaknesses

I have listed some questions in the section below. My main concern is that while I understand the authors provide guarantee in a stronger metric compared to existing algorithm / analysis, given that the query complexity of In-and-Out matches that of some previous work, and the methods are similar in some regard (for example, the second step is conceptually similar to a projection step), it's unclear to me what the practical advantage of the proposed method may be. Minor comment: Some kind of table putting together all the mentioned rates under different assumptions / metrics alongside related previous results in the literature will help the reader digest things a bit better.

Questions

- I haven't given this a careful thought - does the result follow from the proximal sampler result by taking some suitable limit? (since the target is log-concave here and "discretization" isn't an issue for Gibbs sampler) Since I'm confused as to why warmness would show up here but not in the original proximal sampler? - I didn't quite follow Line 146-149 - how would In-and-Out compare to projection-based method? - Line 234-236 the comment about being lazy: In the proposed algorithm, if it doesn't make a proper move (i.e., declares "Failure"), wouldn't that be equivalent to a "lazy" step where things don't move? Or maybe another way to say this is - how should one take ergodic averages along the chain for computing expectation of some observable? It's not entirely clear from first reading. - How does one obtain a warm start in practice?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes the work is mostly theoretical.

Summary

The paper presents a novel random walk algorithm for uniform sampling of high-dimensional convex bodies that provides improved runtime complexity and guarantees on the result, especially with respect to Rényi divergence. Sampling high-dimensional convex bodies, a fundamental problem in algorithm theory with numerous applications in scientific computing, systems biology, differential privacy, and (to a lesser extent) machine learning. All the samplers known so far rely on Markov chains and most of the time, convergence analysis depends on limiting the conductivity of the associated chain, which in turn controls the mixing rate. The algorithm alternates in and out moves, which is a kind of modification of ball walk, avoiding MH step. The theoretical analysis shows that the method contracts the distribution towards the target distribution at a rate that is influenced by the isoperimetric properties of the convex body. The results show the effectiveness of the new algorithm compared to traditional methods such as the ball-walk and hit-and-run algorithms. The "in-and-out" method shows superior performance, especially in high-dimensional environments, due to its direct reduction to isoperimetric constants.

Strengths

- Introduction of the "in-and-out" algorithm for uniform sampling that uses a heat flow approach. - stronger guarantees in terms of Rényi divergence, which includes other divergence measures such as total variation (TV), Wasserstein (W2), Kullback-Leibler (KL) and chi-squared (χ2). - analysis of mixing rates from a heat flow perspective, providing new insights and extending known results for the unconstrained domain. Convergence rate is shown to be determined by functional inequalities such as Poincaré (PI) and Log-Sobolev inequalities (LSI-I). Iteration complexity: For isotropic distributions, the algorithm achieves convergence with a polynomial number of iterations depending on the dimension and the desired accuracy.

Weaknesses

- I don't see any major weaknesses. The paper is easy to read, the main stages of the analysis are outlined in the text (I didn't have time to check the appendices) and are interesting. I regret the absence of a numerical section to compare the interest of the In-and-Out method on practical examples [comparing it to existing algorithms].

Questions

- Can you provide more details on the initialization process and parameter selection (e.g., h, N) for the algorithm? - Could you elaborate on how the functional isoperimetric constants influence the convergence rate of the algorithm for specific geometry (polytopes, ellipsoids, etc...) ? - How can the algorithm be extended to sample from general log-concave distributions restricted to convex bodies or other non-log-concave distributions satisfying isoperimetric inequalities? [is there a "general" idea that can be preserved? - replacing the "hard" Metropolis filter by and In-and-Out mechanism ?] -

Rating

8

Confidence

5

Soundness

4

Presentation

3

Contribution

3

Limitations

yes

Summary

The paper addresses the fundamental problem of uniformly sampling high-dimensional convex bodies. The main contribution is the proposal of the In-and-Out algorithm, analyzed within the framework of the proximal sampling scheme. Using existing analyses from the literature, the paper derives strong results. Additionally, the authors discuss classical methods for constrained sampling and diffusion-based or proximal methods for unconstrained sampling.

Strengths

- Overall, I like this paper. It proposes a new method and offers valuable insights. Additionally, the paper achieves strong results with straightforward proofs. - The paper is well-written and easy to follow.

Weaknesses

- The analysis techniques used in the paper already exist in the literature, which limits the technical contribution. -The paper does not provide a comparison of iteration/query complexity with existing works.

Questions

- Is it possible to extend these results to the log-concave setting? - The membership oracle used is standard. What if we are given the polytope constraint explicitly?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

4

Limitations

NA

Summary

This work presents a new algorithm, called In-and-Out, for sampling from the uniform distribution over a convex subset $K$ of $R^d$ that comes with stronger guarantees than previous algorithms. The proposed algorithm is an instantiation of the Proximal Sampler (PS), an abstract sampling algorithm which was recently shown to have very strong guarantees (Chen et al., 2022 [27]). The PS was previously considered for sampling from $\propto e^{-f} dx$ given first-order oracle access to $f$, and was typically implemented using a form of rejection sampling; the guarantees in [27] are stated purely in terms of the Poincare Inequality (PI) or Log-Sobolev Inequality (LSI) constant of the target. In the setting of this work, the target is $\propto 1_K$ the uniform distribution on a set $K$ for which we have membership oracle access, and the implementation also uses (another form of) rejection sampling. The guarantees presented in this work follow from the analysis from [27] (§B.2) and a regularity lemma (Lemma 12), from bounds on the PI and LSI constants of uniform distributions known from various recent works (Lemma 9 and §D), and from fine bounds on the failure probability in rejection sampling (§B.3).

Strengths

From the point of view of the problem of sampling convex bodies, the contributions of this paper are outstanding. The results appear much stronger than previously known guarantees (but I am not familiar with the literature on this problem, so I can only trust the authors's discussion of the related work.) It illustrates that the diffusion approach to sampling can yield strong results on a problem where geometric approaches are perhaps more natural. From the point of view of algorithmic diffusion, this paper is not "just" a piecing together of several known components, as the analysis of the failure probability of the rejection step is not at all obvious. I found the concise rewriting of the analysis of [27] (Part I of §B.2) quite appreciable as well.

Weaknesses

- No application is presented or discussed. Usually for theoretical works such as this one, the value of the contribution lies in the analysis technique, with the hope that it will allow to eventually obtain guarantees for future applications. But the applications that naturally come to my mind are cases which the results of [27] already cover. Some minor suggestions: - The relation between Thms 1, 2, 3 is a little bit confusing, as only Thms 2, 3 talk about PI and LSI constants. Perhaps the presentation of the results could be made clearer by moving Lemma 9 to the end of §2, or at least making a reference to it there. - I would suggest mentioning already in the abstract or the introduction that In-and-Out is an instance of PS. This would be fairer w.r.t. prior work in my opnion. - The fact that Part I of §B.2 is a restatement of the analysis of [27] should be clarified (the terms "revisit" and "review" currently used on lines 563, 569 are not completely clear). - On lines 139-141, you mention that the time-reversal SDE has the property that it is also a reversal "pointwise", i.e, conditional on the endpoint. But I did not see where this fact is used, as in §B.2 only the reversal of the heat flow at the PDE level is used.

Questions

- Regarding the first point in "Weaknesses": what are some application cases in machine learning where your work applies? - Can the In-and-Out algorithm be extended to sampling from a target $\propto e^{-f} 1_K$ where $f$ is smooth on $R^d$ given first-order access to $f$ and membership oracle access to $K$? Specifically the rejection sampling step and its failure probability analysis (since I expect the analysis of the abstract algorithm, PS, is unchanged) - On line 175, you mention a better query complexity if $K$ is near-isotropic, but Corollary 1 just below is about the exactly-isotropic case. What does line 175 refer to? (Is it Thm 5? if yes it should be mentioned in the main text) - Out of curiosity: are there ways to rescale a convex body to be near-isotropic, given membership oracle access? This could give a preprocessing step which could improve the query complexity you report.

Rating

8

Confidence

4

Soundness

4

Presentation

4

Contribution

4

Limitations

The authors have adequately addressed the limitations.