Dimension-free regimes for unadjusted Langevin in ridge-separable models: A subspace robust Wasserstein analysis
Classical analyses of the Unadjusted Langevin Algorithm (ULA) in Wasserstein-2 distance predict a dimension-dependent mixing time and bias, yet empirically ULA often estimates low-dimensional statistical functionals accurately without scaling the step size with dimension. This paper proposes using the subspace robust Wasserstein (SRW) distance to analyze ULA on ridge-separable Bayesian posteriors, proving that iteration complexity can be dimension-free in both the overparameterized regime ($N \lesssim d$) and the large-sample regime ($N \gtrsim d^2$), while showing such guarantees are impossible near the proportional regime $N \asymp d$. The results explain a bell-shaped bias profile and provide a rotationally invariant alternative to prior $\ell^\infty$-based dimension-free analyses that fail under isotropy.
A sharp and well-structured theoretical contribution that convincingly bridges the gap between classical dimension-dependent ULA theory and empirical observations in high-dimensional Bayesian inference. The three-regime analysis is nuanced, the Gaussian-perturbation bounds are technically elegant, and the explicit proportional-regime lower bound clarifies the limits of dimension-free sampling. The main caveat is a restrictive strong-convexity assumption ($\bar{\alpha}>0$) in the asymptotic regime, which excludes many standard generalized linear models.
The central technical advance is the decomposition in Theorem 2, which separates the ULA error into a Gaussian part $G_k$ and a perturbation remainder $R_k$ to prove that the SRW bias scales as $\mathrm{SRW}(\pi, \hat{\pi}) \lesssim h\sqrt{\beta} + h\sqrt{\beta}\mathfrak{S}d$, while the standard $W_2$ bias retains a $\sqrt{d}$ factor. For ridge-separable models this yields effective rank $N$ instead of dimension $d$ when $N \ll d$, and Gaussian-perturbation estimates give dimension-free bounds when $N \gg d$. The proportional-regime impossibility result (Theorem 4) is equally compelling: using a product measure on coordinate vectors, the authors prove the SRW bias can grow as $\sqrt{d}\,h$, rigorously establishing that dimension-free rates fail there.
A major limitation is that Theorem 3 requires $\bar{\alpha} > 0$, i.e., uniform strong convexity of the individual unary potentials $u_i$; as the authors themselves note, this excludes Bayesian logistic regression and common GLMs where individual Hessians can vanish.
Beyond this modeling gap, the proportional-regime impossibility result in Theorem 4 relies on a data distribution $\nu$ with a sub-Gaussian constant $K \asymp \sqrt{d/\log d}$ that scales with dimension; the authors supplement this with Gaussian simulations in Figure 3, but the theoretical counterexample does not fully capture the constant-$K$ regime most relevant in practice. Additionally, the transition to truly dimension-free complexity in the asymptotic regime only occurs when $N \gtrsim d^2$ (up to logarithms), leaving the intermediate window $d \ll N \ll d^2$ with weaker guarantees.
The comparisons to related work are fair and precise. The authors correctly observe that classical $W_2$ guarantees require a step size scaling inversely with dimension, whereas their SRW analysis escapes this dependence in favorable regimes.
They also cleanly distinguish their rotationally invariant approach from the $\ell^\infty$-Wasserstein dimension-free bounds of Che+24 and LZ25, noting that sparsity assumptions are unnatural for ridge-separable potentials because this model class is preserved under isometries. Numerical evidence in Figure 1 (logistic regression) and Figure 3 (proportional regime) aligns well with the theoretical predictions.
The paper provides detailed descriptions of the simulation protocols and full proof strategies in the appendices, but no code repository or data archive is mentioned.
Theorem statements include explicit dependence on problem parameters $(K, \kappa_\Sigma, \bar{\alpha}, \bar{\beta}, \bar{M})$, though some absolute constants remain unspecified and step-size choices are given as "sufficiently small" rather than fully constructive. The appendices contain complete derivations of random-matrix concentration (Lemma 3.4) and Gaussian-perturbation moment bounds (Lemma 2.1), which should allow experts to reconstruct the analysis, but independent reproduction would be facilitated by releasing the simulation scripts.
The Unadjusted Langevin Algorithm (ULA) is widely used for high-dimensional Bayesian inference. Classical analyses in Wasserstein-2 distance predict an asymptotic bias and a mixing time that grow with dimension, but this metric is stronger than necessary for many statistical tasks. We instead analyze the bias in subspace robust Wasserstein distance, which controls the mean and arbitrary low-dimensional marginals and is therefore well suited to observables typically estimated in practice. For ridge-separable potentials formed with i.i.d. data, we prove high-probability bounds showing a bell-shaped mixing profile as the number of data points $N$ varies relative to the dimension $d$. In the overparameterized regime, the effective dimension is the rank $N$ of the data-dependent perturbation, leading to complexity depending on $N$ rather than $d$. In the large-sample regime, Gaussian-perturbation estimates yield dimension-free complexity once $N$ is sufficiently large. In contrast, near the proportional regime $\asymp d$, we prove that dimension-free guarantees are impossible in general.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.