A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers

Summary

The paper investigates the complexity of sampling from heavy-tailed distributions and presents a distinction between obtaining high-accuracy and low-accuracy guarantees. It analyzes two types of proximal samplers: those based on Gaussian oracles and those based on stable oracles. The main findings are that Gaussian oracle-based samplers can only achieve low-accuracy guarantees when sampling from heavy-tailed distributions, while stable oracle-based samplers can achieve high-accuracy guarantees. Additionally, the paper establishes lower bounds for samplers using the stable oracle, indicating that the presented upper bounds are optimal and cannot be fundamentally improved.

Strengths

1. The problem is well-motivated and interesting. 2. Designed the algorithms and derived the upper bounds and lower bounds for different settings. 3. The authors also provided insightful discussion. 4. The authors provided solid theoretical proof for the results.

Weaknesses

There is no experiment to verify the theoretical findings.

Questions

1. Can you give an example in the real-world to motivate your problem? 2. Is it possible to run some experiments to verify your results?

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

There is no experiment.

Summary

This paper studies the problem of heavy-tailed sampling. First, the paper shows that while the gaussian proximal samplers are efficient for light-tailed targets, they are not accurate for heavy-tailed ones; the paper develops a lower bounds for the Gaussian proximal samplers, which reveals a fundamental challenge in heavy-tailed settings. Then, the paper proceeds to develop a novel samplers based on restricted alpha-stable oracle; the insight is to replace the standard heat equation in gaussian oracle with a fractional heat flow. The paper proves that under suitable conditions the proposed sampler is efficient for heavy-tailed targets. Additionally, the paper proposes a practical implementation for a particular case of alpha=1.

Strengths

- Novel theoretical analysis for the gaussian oracle sampler, which provides a new insight to developing sampling algorithms - A novel methodology for heavy-tailed sampling

Weaknesses

- The paper is purely theoretical and lacks experimental evaluation; it would be nice to at least have a toy illustration for the implementable algorithm 2+3 in the alpha=1 case. - As the authors discussed in Sec5, the current paper does not present implementable algorithms for general alpha values in (0,2).

Questions

- I wonder if the efficiency rejection sampling efficiency in Alg.3 has been taken into account of the sampler's theoretical complexity and practical complexity? - Maybe I am missing this -- what is the impact of alpha?

Rating

7

Confidence

1

Soundness

3

Presentation

3

Contribution

3

Limitations

Most of the limitations have been touched upon in sec 5. Otherwise see the weakness comments.

Summary

The paper focus on studying the complexity of heavy-tailed sampling and present a separation result in terms of obtaining high-accuracy versus low-accuracy guarantees. Their results are presented for proximal samplers that are based on Gaussian versus stable oracles. Authors show that proximal samplers based on the Gaussian oracle have a fundamental barrier in that they necessarily achieve only low-accuracy guarantees when sampling from a class of heavy-tailed targets. In contrast, proximal samplers based on the stable oracle exhibit high-accuracy guarantees, thereby overcoming the aforementioned limitation. They also prove lower bounds for samplers under the stable oracle and show that our upper bounds cannot be fundamentally improved.

Strengths

Although I am not an expert in this field, I find this work quite interesting. The authors provide new material and support their statements with proofs.

Weaknesses

The paper is not tested in any way on a numerical experiment. I am convinced that a paper presented at this type of conference should be both motivated by a real-world application and tested numerically, e.g., on a near-real-world formulation of the problem. **After a rebuttal process**, the authors agreed with this weakness and promised to add the experiments to the final version of the paper.

Questions

N/A

Rating

7

Confidence

1

Soundness

2

Presentation

2

Contribution

3

Limitations

N/A

Summary

The authors provide a lower bound for sampling from heavy tailed distributions under the Gaussian oracle of order $O(\textup{poly}(1/\varepsilon))$. They then propose an alternative proximal sampling algorithm using the $\alpha$-stable oracle that achieves a convergence rate of $O(\log(1/\varepsilon))$ for heavy-tailed distributions satisfying a fractional Poincare inequality. They then provide a practical implementation of the stable proximal sampler, and lower bounds on its convergence rate.

Strengths

- This work presents a very nice combination of results showing a separation in the performance of stable and Gaussian proximal samplers. The combination of lower and upper bounds separating the two methods makes the work a particularly interesting contribution. - The addition of a practical implementation of the stable proximal sampler is nice to have, demonstrating that it is viable in practice. - The work is generally clearly presented and the authors are clear about their contributions. - Overall, I consider this to be a very sound piece of theoretical work.

Weaknesses

I have no major concerns about this paper. The presentation is somewhat dense in places, though this is mostly just a consequence of it being a very technical paper and not a flaw as such. If the authors want to make the claim that practicioners should use the stable proximal sampler in applied settings, then they may want to provide empirical evidence of its performance compared to the Gaussian proximal sampler. However, I understand that this is not the main purpose of this theoretical paper.

Questions

I have no clarifications to request.

Rating

8

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors provide an adequate discussion of the limitations of their methods in the final section, and I foresee no additional negative impacts of their work.

Summary

This paper studies the complexity of sampling heavy-tailed distributions. It provides lower bounds on the complexity of Gaussian-based samplers for a class of heavy-tailed targets. Then, the paper constructs proximal samplers based on stable oracles, which improve the sampling complexity.

Strengths

* This paper is well-written. The background of sampling and the research problems regarding sampling complexity are clearly introduced. The contributions of the lower bound on Gaussian-based samplers for heavy-tailed targets and the improved complexity using stable oracles are clearly presented. * The paper is technically sound. The definitions and assumptions are discussed clearly, and the theoretical results are supported by proof sketches.

Weaknesses

The contribution of the paper could be improved with empirical experiments to evaluate the sampling algorithms and their complexity.

Questions

* Is there any intuition that a Gaussian-based sampler has lower accuracy for heavy-tailed targets than for non-heavy-tailed targets? * How would a Gaussian-based sampler compare with a stable oracle for not heavy-tailed targets?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

NA