Research map / Learning theory and algorithms / Sample complexity
Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models
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.
Proposes parallel Picard-based samplers that reduce adaptive complexity of log-concave sampling (overdamped Langevin) and SDE-based diffusion model sampling from O(log^2 d) to O(log d) via diagonal time-slice updating.
Problem
Reducing adaptive complexity (number of sequential rounds) of log-concave sampling and SDE-based sampling for score-based diffusion models, where prior parallel Picard methods achieve only O(log^2(d/eps^2)).
Approach
Updates time slices in a diagonal fashion, where each update performs P Picard iterations using both the previous slice's right boundary and same-slice grid points updated in prior rounds, controlling score-estimation error accumulation so total adaptive complexity becomes O(log d).
Key results
- Parallel Picard sampler for strongly log-concave sampling achieves O~(log(d/eps^2)) adaptive complexity (improved from O~(log^2(d/eps^2))) with O~(kappa^2 d/eps^2 log(d/eps^2)) queries per iteration at most.
- Parallel Picard algorithm for SDE-based diffusion model sampling achieves O~(log(d/eps^2)) adaptive complexity and O~(d^2/eps^2) space complexity.
- Theoretical results only; no experiments reported in the provided text.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use diagonal-style parallel updates with repeated Picard iterations | Strongly log-concave sampling with overdamped Langevin diffusion · Strongly log-concave sampling | adaptive complexity: \widetilde{\mathcal{O}}\left(\log^2\left(\frac{d}{\varepsilon^2}\right)\right) -> \widetilde{\mathcal{O}}\left(\log\left | Helped |
| Use diagonal-style parallel Picard updates | Diffusion models with SDE implementation · Diffusion models, SDE implementation | adaptive complexity: \mathcal{O}(\log^2\frac{d}{\varepsilon^2}) -> \mathcal{O}(\log\frac{d}{\varepsilon^2}) | Helped |
| Use overdamped rather than underdamped Langevin diffusion | Parallel Picard method · Strongly log-concave sampling | space complexity: \widetilde{\mathcal{O}}\big(\frac{d^{3/2}}{\varepsilon}\big) -> \widetilde{\mathcal{O}}\big(\frac{d^2}{\varepsilon^2}\bi | Hurt |
| Use SDE rather than ODE implementation | Parallel Picard method for diffusion models · Diffusion models | space complexity | Hurt |
| Increase processor and gradient-evaluation count to achieve logarithmic adaptive complexity | Parallel Picard method for strongly log-concave sampling · Strongly log-concave sampling | processor and gradient-evaluation count: \mathcal{O}\left(\frac{d}{\varepsilon^2}\right) -> {\mathcal{O}}\left(\frac{d}{\varepsilon^2}\log\left(\frac{d}{\varepsi | Hurt |
Limitations
- Space complexity is suboptimal due to less smooth overdamped/SDE trajectories.
- Adaptive complexity remains linear in condition number kappa; dependence on kappa not improved.
- Benefits require very large numbers of processors (batch size on the order of kappa d/eps^2), which may be impractical.
Experimental setup
Metrics: adaptive complexity space complexity KL divergence Wasserstein-2 distance total variation
Baselines: parallel Picard method (O(log^2) adaptive complexity) parallel midpoint method randomized midpoint method underdamped Langevin parallel sampler
Builds on: Picard iterations parallel midpoint method Langevin Monte Carlo Girsanov's theorem
Closest papers by meaning
- Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel (ICLR 2025 · similarity 0.93)
- Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity (NeurIPS 2024 · similarity 0.90)
- Query Lower Bounds for Diffusion Sampling (NeurIPS 2026 · similarity 0.88)
- Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers (ICLR 2024 · similarity 0.87)
- Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics (ICLR 2025 · similarity 0.87)
- Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis (ICLR 2025 · similarity 0.87)
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.