Research map / Learning theory and algorithms / Sample complexity
A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows Gaussian-oracle proximal samplers and Langevin diffusion have poly(1/ε) complexity for heavy-tailed (generalized Cauchy) targets, while stable-oracle proximal samplers achieve O(log(1/ε)) complexity under fractional Poincaré inequalities, with matching lower bounds for the implementable α=1 version.
Problem
Sampling from heavy-tailed targets (e.g., generalized Cauchy) with high-accuracy guarantees: gradient-based and Gaussian-oracle proximal samplers only achieve poly(1/ε) iterations.
Approach
Replace the Gaussian heat-flow step of the proximal sampler with an exact α-stable (fractional heat flow) step and a restricted α-stable oracle, which yields chi-square convergence under a fractional Poincaré inequality; for α=1 the oracle is implemented by rejection sampling using Cauchy proposals.
Key results
- Gaussian-oracle proximal sampler and Langevin diffusion require Ω̃(ε^{-2/ν}) iterations (TV) for generalized Cauchy targets, i.e., poly(1/ε).
- Stable proximal sampler with α≤ν achieves O(log(d/ε)) iteration complexity in χ² divergence under α-FPI.
- For α=1 rejection-sampling implementation, ν≥1 gives O(log(1/ε)) complexity, while ν∈(0,1) gives poly(1/ε) with a lower bound matching up to factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the Gaussian oracle with the practical stable oracle (α=1) | Proximal sampler · Generalized Cauchy targets, ν≥1 | iteration complexity: $\Tilde{\Omega}(\varepsilon^{-\frac{1}{\nu}})$ vs. $\mathcal{O}(\log(\varepsilon^{-1}))$ | Helped |
| Replace the Gaussian oracle with the practical stable oracle (α=1) | Proximal sampler · Generalized Cauchy targets, ν∈(0,1) | iteration complexity: $\Tilde{\Omega}(\varepsilon^{-\frac{1}{\nu}})$ vs. $\Tilde{\mathcal{O}}(\varepsilon^{-\frac{1}{\nu}+1})$; by a factor of | Helped |
| Use an α-stable oracle with α≤ν instead of a Gaussian oracle | Proximal sampler · Generalized Cauchy targets | iteration complexity: poly(1/ε) to log(1/ε) | Helped |
Surprising findings
- The implementable α=1 stable sampler transitions to poly(1/ε) complexity when ν∈(0,1), so the high-accuracy regime is not achieved for all heavy tails.
Limitations
- Efficient implementation of the stable oracle is only given for α=1; other α are left to future work.
- Implementable α=1 sampler is poly(1/ε) for ν∈(0,1), i.e., low-accuracy in that regime.
- Requires a global minimizer of V for the rejection step, which may be hard to find.
Experimental setup
Metrics: chi-square divergence total variation iteration complexity
Baselines: Gaussian proximal sampler Langevin diffusion
Builds on: proximal sampler Langevin diffusion fractional Poincaré inequality
Closest papers by meaning
- Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD (NeurIPS 2024 · similarity 0.87)
- Faster Sampling via Stochastic Gradient Proximal Sampler (ICML 2024 · similarity 0.86)
- Sub-Gaussian Confidence Intervals for Heavy-Tailed Data: Characterizing the Limits of Inference (NeurIPS 2026 · similarity 0.85)
- New Sample Complexity Bounds for Sample Average Approximation in Heavy-Tailed Stochastic Programming (ICML 2024 · similarity 0.85)
- Concentration Inequalities for General Functions of Heavy-Tailed Random Variables (ICML 2024 · similarity 0.85)
- Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.