Sampling Beyond Log Concavity via Functional Inequalities

107 concepts68 papers

The Convexity Barrier in Sampling

In mathematical optimization, convexity is the gold standard. If a function is convex, any local minimum is a global minimum, allowing simple gradient descent algorithms to reliably find the optimal solution. In the world of probabilistic sampling, the traditional analogue to convexity is log-concavity. A target probability distribution $\pi(x) \propto \exp(-V(x))$ is strongly log-concave if its negative log-density—the potential function $V(x)$—is strongly convex.

Under strong log-concavity, classical sampling algorithms like Langevin Monte Carlo (LMC) behave beautifully. They explore the distribution efficiently, and their non-asymptotic convergence rates can be tightly bounded, as demonstrated by Xiang Cheng et al. in Convergence of Langevin MCMC in KL-divergence.

However, real-world machine learning applications routinely break this assumption. The loss landscapes of deep neural networks, multimodal mixtures, and the data distributions modeled by score-based generative diffusion models are stubbornly non-log-concave. They feature multiple modes, local bumps, and complex geometries. If we rely strictly on traditional convexity-based proofs, we are left with pessimistic, exponentially slow convergence bounds.

To explain why sampling algorithms actually succeed in practice on these complex distributions, a powerful research direction has emerged: analyzing convergence using functional inequalities rather than strict geometric constraints.

Sampling as Optimization in the Space of Measures

To understand why functional inequalities unlock non-log-concave sampling, we must first shift our perspective from tracking a single particle to tracking an entire ensemble of particles. Instead of viewing Langevin dynamics as a stochastic process moving through a non-convex Euclidean landscape, we can view it as a deterministic process moving through the infinite-dimensional space of probability measures.

In a seminal paper, Andre Wibisono proved that Langevin dynamics can be rigorously interpreted as a continuous-time gradient flow in the Wasserstein space of probability measures (Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem). Specifically, the algorithm performs gradient descent to minimize a global objective functional: the Kullback-Leibler (KL) divergence to the target distribution.

While the underlying potential $V(x)$ may be highly non-convex in vector space, the KL divergence functional can behave predictably in the space of measures. This realization allows researchers to borrow powerful tools from optimization theory. If we can find a functional analogue to the conditions that guarantee global convergence in non-convex optimization, we can prove that sampling will converge efficiently even when the target distribution is multimodal.

The Functional PL Condition: Log-Sobolev Inequalities

In standard optimization, the Polyak-Łojasiewicz (PL) condition allows gradient descent to converge exponentially fast to a global minimum without requiring the objective function to be convex. The PL condition simply states that the gradient norm at any point dominates the suboptimality gap to the global minimum.

In the space of probability measures, the exact functional analogue of the PL condition is the Log-Sobolev Inequality (LSI). As noted by Feng Liu (Convergence of Mean-Field Langevin Stochastic Descent-Ascent for Distributional Minimax Optimization) and Mingyang Yi et al. (Continuous-time Riemannian SGD and SVRG Flows on Wasserstein Probabilistic Space), LSI acts as a distributional gradient dominance condition. It bounds the optimality gap (the KL divergence) by the velocity of the gradient flow (the relative Fisher Information):

$$\text{KL}(\mu \mid \pi) \le \frac{1}{2\rho} \text{I}(\mu \mid \pi)$$

where $\rho$ is the log-Sobolev constant.

If a target distribution satisfies LSI, the continuous-time diffusion process is guaranteed to converge exponentially fast to equilibrium. Crucially, LSI does not require the distribution to be unimodal or log-concave; it is an isoperimetric property. It ensures that the probability landscape is sufficiently well-connected, meaning it lacks deep, completely isolated energy wells that would permanently trap the sampler.

Provable Efficiency and Dimension Dependence

Translating continuous-time exponential decay into practical, discrete-time algorithms requires proving that discretization errors do not accumulate catastrophically. By analyzing discrete samplers under the assumption of LSI rather than strict log-concavity, researchers have established remarkably sharp complexity bounds.

For instance, Bin Yang et al. proved that Langevin Monte Carlo on non-convex distributions satisfying LSI achieves a sharp dimension dependence of $O(\sqrt{d})$ in Wasserstein distance (Non-asymptotic Error Bounds in $\mathcal{W}_2$-Distance with Sqrt(d) Dimension Dependence and First Order Convergence for Langevin Monte Carlo beyond Log-Concavity). This matches the best-known rates for purely convex problems, demonstrating that high-dimensional non-convex sampling can be just as efficient as convex sampling, provided the distribution returns to equilibrium at a sufficient rate.

This framework has also successfully explained the polynomial-time complexity of modern generative models. Holden Lee et al. leveraged LSI to provide the first polynomial complexity bounds for score-based diffusion models (Convergence for score-based generative modeling with polynomial complexity). Similarly, Nima Anari et al. used LSI to design highly parallelized sampling algorithms via Picard iterations, showing that rapid mixing under LSI allows for efficient path refinement across modern parallel architectures (Fast parallel sampling under isoperimetry).

A Spectrum of Functional Inequalities

Not all non-log-concave distributions satisfy a strict Log-Sobolev Inequality. When target distributions exhibit heavier tails or weaker connectivity, researchers rely on a broader spectrum of functional inequalities to characterize convergence.

[Weak Poincaré] --------> [Poincaré] --------> [Log-Sobolev (LSI)]
  (Heavy tails,             (Exponential tails,   (Light tails,
   algebraic decay)          geometric decay)      exponential decay)
  • The Poincaré Inequality: A weaker condition than LSI, the Poincaré inequality bounds the variance of a function rather than its entropy. It guarantees exponential convergence in $L^2$ space but yields slower mixing times in KL divergence. Sinho Chewi et al. unified the analysis of LMC by interpolating between Poincaré and log-Sobolev conditions using the Latała–Oleszkiewicz inequality, capturing distributions with linear to quadratic tail growth (Analysis of Langevin Monte Carlo from Poincare to Log-Sobolev).
  • Weak and Weighted Poincaré Inequalities: For distributions with polynomial tail decay (such as Cauchy-type distributions), even a standard Poincaré inequality fails. To handle these heavy-tailed targets, Ye He et al. introduced a framework based on Weighted Poincaré Inequalities, establishing rigorous non-asymptotic complexity bounds where convergence rates shift from exponential to algebraic decay (Mean-Square Analysis of Discretized Itô Diffusions for Heavy-tailed Sampling).
  • Talagrand's Inequality ($T_1$): For interacting particle methods like Stein Variational Gradient Descent (SVGD), local curvature assumptions can be bypassed entirely. Adil Salim et al. established global convergence for SVGD under Talagrand’s Inequality $T_1$, which constrains the global tail behavior rather than local geometry (A Convergence Theory for SVGD in the Population Limit under Talagrand's Inequality T1).

Taming Instability with Dissipativity and Annealing

While functional inequalities guarantee that a distribution will eventually return to equilibrium, discrete algorithms can still become unstable if the gradients grow too quickly or if the local landscape is highly irregular. To bridge the gap between continuous-time theory and discrete-time practice, researchers combine functional inequalities with structural conditions like weak dissipativity.

Weak dissipativity requires the potential function $V(x)$ to exert a strong restorative force toward the origin only outside a bounded region, allowing arbitrary non-convexity or complexity near the center. Iosif Lytras et al. utilized this to prove non-asymptotic convergence for "tamed" Langevin algorithms that rescale superlinear gradients (Tamed Langevin sampling under weaker conditions). Similarly, Marien Renaud et al. demonstrated that weak dissipativity ensures the geometric ergodicity and stability of proximal MCMC methods in non-smooth, non-convex image restoration tasks (From stability of Langevin diffusion to convergence of proximal MCMC for non-log-concave sampling).

When a distribution features deep, isolated modes that violate global isoperimetry entirely, multi-scale or annealing strategies are deployed. Wei Guo et al. proved that Annealed Langevin Monte Carlo (ALMC) bypasses restrictive geometric assumptions by gradually flattening the distribution, achieving polynomial complexity on highly multi-modal targets (Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling).

By shifting the analytical toolkit from local geometric properties (like Hessians and convexity) to global functional properties (like LSI and Poincaré inequalities), this line of research provides the mathematical foundation explaining why high-dimensional, non-convex sampling is not only possible, but provably efficient.

Key Foundational Work

Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem (2018) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_functional_inequality_based_convergence_d8785c52,
  title = {functional inequality-based convergence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/functional-inequality-based-convergence/rdr_d8785c52d6424f93b8fac28e421a0d3d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_functional_inequality_based_convergence_d8785c52_v1,
  title = {functional inequality-based convergence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/functional-inequality-based-convergence/rdr_d8785c52d6424f93b8fac28e421a0d3d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake