# Structured Logconcave Sampling with a Restricted Gaussian Oracle

arXiv: https://arxiv.org/abs/2010.03106 · HTML: https://mlsanity.com/paper/2010.03106/

## Key facts

- Cited by 86 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2020.

## Built on by (most cited first, 30 of 86)

- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [The probability flow ODE is provably fast](https://mlsanity.com/paper/2305.11798/) (2023)
- [Principled Probabilistic Imaging using Diffusion Models as Plug-and-Play Priors](https://mlsanity.com/paper/2405.18782/) (2024)
- [Variational inference via Wasserstein gradient flows](https://mlsanity.com/paper/2205.15902/) (2022)
- [Improved analysis for a proximal algorithm for sampling](https://mlsanity.com/paper/2202.06386/) (2022)
- [Provably Robust Score-Based Diffusion Posterior Sampling for Plug-and-Play Image Reconstruction](https://mlsanity.com/paper/2403.17042/) (2024)
- [InverseBench: Benchmarking Plug-and-Play Diffusion Priors for Inverse Problems in Physical Sciences](https://mlsanity.com/paper/2503.11043/) (2025)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Reverse Diffusion Monte Carlo](https://mlsanity.com/paper/2307.02037/) (2023)
- [Improved dimension dependence of a proximal algorithm for sampling](https://mlsanity.com/paper/2302.10081/) (2023)
- [Beyond Log-Concavity and Score Regularity: Improved Convergence Bounds for Score-Based Generative Models in W2-distance](https://mlsanity.com/paper/2501.02298/) (2025)
- [A Proximal Algorithm for Sampling from Non-smooth Potentials](https://mlsanity.com/paper/2110.04597/) (2021)
- [A Proximal Algorithm for Sampling](https://mlsanity.com/paper/2202.13975/) (2022)
- [Diffusive Gibbs Sampling](https://mlsanity.com/paper/2402.03008/) (2024)
- [Training Neural Samplers with Reverse Diffusive KL Divergence](https://mlsanity.com/paper/2410.12456/) (2024)
- [Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions](https://mlsanity.com/paper/2106.05480/) (2021)
- [Mean-field Variational Inference via Wasserstein Gradient Flow](https://mlsanity.com/paper/2207.08074/) (2022)
- [Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion](https://mlsanity.com/paper/2402.17886/) (2024)
- [In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies](https://mlsanity.com/paper/2405.01425/) (2024)
- [High-accuracy sampling for diffusion models and log-concave distributions](https://mlsanity.com/paper/2602.01338/) (2026)
- [When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?](https://mlsanity.com/paper/2304.04724/) (2023)
- [Private Convex Optimization in General Norms](https://mlsanity.com/paper/2207.08347/) (2022)
- [Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks](https://mlsanity.com/paper/2302.09699/) (2023)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [More Efficient Randomized Exploration for Reinforcement Learning via Approximate Sampling](https://mlsanity.com/paper/2406.12241/) (2024)
- [Sampling and Integration of Logconcave Functions by Algorithmic Diffusion](https://mlsanity.com/paper/2411.13462/) (2024)
- [Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequality](https://mlsanity.com/paper/2502.05623/) (2025)
- [Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits](https://mlsanity.com/paper/2209.12897/) (2022)

## Abstract (arXiv)

We give algorithms for sampling several structured logconcave families to high accuracy. We further develop a reduction framework, inspired by proximal point methods in convex optimization, which bootstraps samplers for regularized densities to improve dependences on problem conditioning. A key ingredient in our framework is the notion of a "restricted Gaussian oracle" (RGO) for g: ℝd rightarrow ℝ, which is a sampler for distributions whose negative log-likelihood sums a quadratic and g. By combining our reduction framework with our new samplers, we obtain the following bounds for sampling structured distributions to total variation distance ε. For composite densities exp(-f(x) - g(x)), where f has condition number kappa and convex (but possibly non-smooth) g admits an RGO, we obtain a mixing time of O(kappa d log3frackappa dε), matching the state-of-the-art non-composite bound; no composite samplers with better mixing than general-purpose logconcave samplers were previously known. For logconcave finite sums exp(-F(x)), where F(x) = frac1nsumi ∈ [n] fi(x) has condition number kappa, we give a sampler querying widetildeO(n + kappamax(d, √nd)) gradient oracles to fii ∈ [n]; no high-accuracy samplers with nontrivial gradient query complexity were previously known. For densities with condition number kappa, we give an algorithm obtaining mixing time O(kappa d log2frackappa dε), improving the prior state-of-the-art by a logarithmic factor with a significantly simpler analysis; we also show a zeroth-order algorithm attains the same query complexity.