Research map / Learning theory and algorithms / Sample complexity
Riemannian Proximal Sampler for High-accuracy Sampling on Manifolds
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 the Riemannian Proximal Sampler, a two-step (manifold Brownian increment + Riemannian heat-kernel) sampler with KL and TV high-accuracy guarantees, practical oracles via heat-kernel truncation and Varadhan's asymptotics, and a link to entropy-regularized JKO.
Problem
Sampling from densities defined on Riemannian manifolds with high accuracy (polylog(1/eps) iteration complexity), which prior manifold samplers lack since they achieve only poly(1/eps) rates and require exact Brownian increments.
Approach
Generalizes the Euclidean proximal sampler to manifolds by alternating a manifold Brownian increment step and a Riemannian heat-kernel (restricted Gaussian) step; proves LSI-based KL contraction via curvature-dependent Fisher-information analysis, extends to TV under inexact oracles, and implements oracles via heat-kernel truncation rejection sampling or Varadhan's asymptotics (Riemannian Gaussian
Key results
- Exact-oracle analysis gives O(log(1/eps)) iterations (up to step-size factors) in KL under LSI, with contraction rate (1+eta*alpha)^{-2k} for non-negative Ricci curvature.
- With inexact oracles under TV-accuracy assumption, O~(log^2(1/eps)) iterations suffice for O~(eps) TV error.
- Numerical experiments show the proximal sampler with large step size reaches higher accuracy than Riemannian LMC on von Mises-Fisher and positive-definite-matrix targets; no numeric table given.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the unbiased proximal sampler with a large step size instead of biased Riemannian LMC | Sampling the von Mises-Fisher distribution on hyperspheres · Hyperspheres (including $\mathcal{S}^{2}$ and $\mathcal{S}^{5}$) | Fréchet variance | Helped |
| Use the proximal sampler instead of Riemannian LMC with step size 0.0001 | Sampling on the manifold of positive definite matrices · Positive definite matrices, $P_3$ | Fréchet variance | Helped |
Surprising findings
- Riemannian LMC diverged on the P_3 experiment at step size 0.001, while the proximal sampler stayed stable at large step sizes.
Limitations
- Truncation-based implementation only known for homogeneous spaces; general manifolds open.
- Geodesic random walk approximation of MBI lacks non-asymptotic high-accuracy guarantees.
- Negative curvature requires step size bounded by curvature-dependent constant.
Experimental setup
Benchmarks: von Mises-Fisher sampling on hyperspheres S^2 and S^5 manifold of positive definite matrices P_3 with quartic potential
Metrics: expected squared geodesic distance (Fréchet variance) to mod
Baselines: Riemannian Langevin Monte Carlo
Builds on: Euclidean proximal sampler Langevin Monte Carlo JKO scheme Varadhan's asymptotics
Closest papers by meaning
- Efficient Diffusion Models for Symmetric Manifolds (ICML 2025 · similarity 0.88)
- Generative Modeling on Manifolds Through Mixture of Riemannian Diffusion Processes (ICML 2024 · similarity 0.87)
- Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method (ICML 2025 · similarity 0.85)
- Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal Point (ICML 2024 · similarity 0.85)
- Improving the Euclidean Diffusion Generation of Manifold Data by Mitigating Score Function Singularity (NeurIPS 2025 · similarity 0.85)
- Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization (ICML 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.