The Geometry of Efficient Nonconvex Sampling

• URL: http://arxiv.org/abs/2603.25622v1
• Date: Thu, 26 Mar 2026 16:35:53 GMT
• Title: The Geometry of Efficient Nonconvex Sampling
• Abstract summary: We present an efficient algorithm for uniformly sampling from an arbitrary compact body.<n>The complexity of the algorithm is in the dimension of the Poincaré constant of the uniform distribution on $mathcalX$ and the volume growth constant of the set $mathcalX$.
• Score: 18.653581233103157
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present an efficient algorithm for uniformly sampling from an arbitrary compact body $\mathcal{X} \subset \mathbb{R}^n$ from a warm start under isoperimetry and a natural volume growth condition. Our result provides a substantial common generalization of known results for convex bodies and star-shaped bodies. The complexity of the algorithm is polynomial in the dimension, the Poincaré constant of the uniform distribution on $\mathcal{X}$ and the volume growth constant of the set $\mathcal{X}$.

Related papers

• Intrinsic Wasserstein Rates for Score-Based Generative Models on Smooth Manifolds [61.14405512940818]
  We show that Score-based generative models are trained in high-dimensional ambient spaces.<n>We use a ReLU implementation of nearest-projection coordinates via finite intrinsic anchors and Gauss Newton.
  arXiv  Detail & Related papers  (2026-05-15T10:20:05Z)
• Convergence Analysis of the PAGE Stochastic Algorithm for Weakly Convex Finite-Sum Optimization [56.57092765118707]
  The algorithm was designed to find stationary points of averages of work of this type.<n>It provides a continuous non-smooth case ($tautauL$) which improves between the general framework ($tautauL$) and the rate of change.
  arXiv  Detail & Related papers  (2025-08-31T08:06:53Z)
• An exact analytical solution for Dicke superradiance [0.0]
  We revisit the Dicke superradiance problem, where an ensemble of N identical two-level systems undergoes collective spontaneous decay.<n>We present a compact, closed-form solution that expresses the dynamics as a finite sum over residues or, equivalently, a complex contour integral.
  arXiv  Detail & Related papers  (2024-09-29T20:40:54Z)
• Rényi-infinity constrained sampling with $d^3$ membership queries [2.209921757303168]
  We propose a constrained proximal sampler, a principled and simple algorithm that possesses elegant convergence guarantees. We show that it converges in the R'enyi-infinity divergence ($mathcal R_infty$) with no query complexity overhead when starting from a warm start.
  arXiv  Detail & Related papers  (2024-07-17T19:20:08Z)
• In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies [12.806971416812432]
  We present a new random walk for uniformly sampling high-dimensional convex bodies.<n>It achieves state-of-the-art runtime complexity with stronger guarantees on the output.
  arXiv  Detail & Related papers  (2024-05-02T16:15:46Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  We prove that the hardness of approximation of ReLU networks not only mirrors the complexity of the Max-Cut problem but also, in certain special cases, exactly corresponds to it. In particular, when $epsilonleqsqrt84/83-1approx 0.006$, we show that it is NP-hard to find an approximate global dataset of the ReLU network objective with relative error $epsilon$ with respect to the objective value.
  arXiv  Detail & Related papers  (2023-11-18T04:41:07Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Lifting uniform learners via distributional decomposition [17.775217381568478]
  We show how any PAC learning algorithm that works under the uniform distribution can be transformed, in a blackbox fashion, into one that works under an arbitrary and unknown distribution $mathcalD$. A key technical ingredient is an algorithm which, given the aforementioned access to $mathcalD$, produces an optimal decision tree decomposition of $mathcalD$.
  arXiv  Detail & Related papers  (2023-03-27T23:55:25Z)
• Universal coding, intrinsic volumes, and metric complexity [3.4265828682659705]
  In this assignment, the goal is to predict, or equivalently, a sequence of real-valued observations almost as well as the best distribution with mean-valued subsets of $mathbbRn.<n>As part of our analysis, we also characterize the minimax redundancy for a general constraint set.<n>We contrast our findings with classical results in information theory.
  arXiv  Detail & Related papers  (2023-03-13T16:54:04Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance. Our theoretical analysis is further validated by numerical experiments.
  arXiv  Detail & Related papers  (2021-09-08T18:00:05Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.