Improved high-dimensional estimation with Langevin dynamics and stochastic weight averaging
Stanley Wei, Alex Damian, Jason D. Lee · 2026
Read Improved high-dimensional estimation with Langevin dynamics and stochastic weight averaging by Stanley Wei, Alex Damian, Jason D. Lee (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-06028.txt.
Introduction
Wei and colleagues show Langevin dynamics succeed with n at least d to the k-star over 2 using averages. Prior work showed n at least d to the max of 1 and k-star minus 1 necessary. Recently, smoothed gradient descent beat these bounds with n at least d to the max of 1 and k-star over 2. The key quantity is the information exponent k-star. Noise plus averaging emulates landscape smoothing. The authors apply this to tensor PCA and single-index settings, conjecturing minibatch SGD matches this rate.
Catalog record
| CREATOR | Stanley Wei, Alex Damian, Jason D. Lee |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 103882 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.06028
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Improved high-dimensional estimation with Langevin dynamics and stochastic weight averaging Stanley Wei, Alex Damian, Jason D. Lee Abstract Significant recent work has studied the ability of gradient descent to recover a hidden planted direction θ ⋆ ∈ S d − 1 \theta^{\star}\in S^{d-1} in different high-dimensional settings, including tensor PCA and single-index models. The key quantity that governs the ability of gradient descent to traverse these landscapes is the information exponent k ⋆ k^{\star} [ 7 ] , which corresponds to the order of the saddle at initialization in the population landscape. 7 showed that n ≳ d max ( 1 , k ⋆ − 1 ) n\gtrsim d^{\max(1,k^{\star}-1)} samples were necessary and sufficient for online SGD to recover θ ⋆ \theta^{\star} , and 6 proved a similar lower bound for Langevin dynamics. More recently, 14 showed it was possible to circumvent these lower bounds by running gradient descent on a smoothed landscape, and that this algorithm succeeds with n ≳ d max ( 1 , k ⋆ / 2 ) n\gtrsim d^{\max(1,k^{\star}/2)} samples, which is optimal in the worst case. This raises the question of whether it is possible to achieve the same rate without explicit smoothing. In this paper, we show that Langevin dynamics can succeed with n ≳ d k ⋆ / 2 n\gtrsim d^{k^{\star}/2} samples if one considers the average iterate , rather than the last iterate. The key idea is that the combination of noise-injection and iterate averaging is able to emulate the effect of landscape smoothing. We apply this result to both the tensor PCA and single-index model settings. Finally, we conjecture that minibatch SGD can also achieve the same rate without adding any additional noise. 1 Introduction In many learning settings, gradient descent is the default algorithm, and recent years have seen significant progress in understanding its theoretical properties and learnability guarantees in different feature learning settings [ 13 , 27 ] . While the optimization process is non-convex in general, there are many settings in which we can nonetheless tractably give learning guarantees. Single index models, or functions of the form \sigma(\theta^{\star}\cdot x) , provide one such sandbox; here, the goal is to recover this planted direction \theta^{\star}\in S^{d-1} through which the target depends on the input. In the statistics literature, single index models have been studied for decades [ 21 , 18 ] , and are also known as generalized linear models. In the special case where the link function \sigma is monotonic, the information-theoretic sample complexity of n\asymp d to learn \theta^{\star} is achieved via perceptron-like algorithms [ 24 , 23 ] . For non-monotonic link functions, one classic example is the phase-retrieval problem where \sigma(t)=|t| , which has been well-studied [ 11 , 26 ] . For the case of Gaussian input data, the information exponent k^{\star} of the link function \sigma tells us the sample complexity needed to learn \theta^{\star} with “correlational learners” [ 7 ] . This can be extended to allow for label preprocessing [ 28 , 26 , 10 , 17 , 32 , 25 , 4 ] and the resulting exponent becomes the “generative exponent” [ 15 ] . 7 shows that using n\gtrsim d^{k^{\star}-1} samples is necessary and sufficient for a certain class of online stochastic gradient descent (SGD) algorithms. 14 improves this to n\gtrsim d^{\max(1,k^{\star}/2)} samples by running online SGD on a smoothed loss, and they provide a matching correlational statistical query (CSQ) lower bound. Key to their analysis is the fact that the smoothed loss boosts the signal-to-noise ratio in the region near initialization (i.e. when the current iterate lies in the equatorial region with respect to \theta^{\star} ). Overall, the information exponent has been shown to determine the sample complexity in many settings [ 7 , 14 , 8 , 1 , 16 ] . A recent work of 22 analyzes the spherical symmetric distribution case, which slightly relaxes the Gaussian data assumption. In particular, the work by 1 provides a generalization of the information exponent to the multi index setting, in which the target depends on a low dimensional subspace of the input instead of just a single direction [ 30 , 12 ] . We would also like to note the connection of learning information exponent k single index models to the order k tensor PCA problem [ 29 ] . In both problems, it turns out that the partial trace estimator returns the direction of the planted spike with optimal sample complexity of d^{k/2} in the CSQ framework, and similar smoothing-based approaches there [ 3 , 9 ] have been proposed to return this estimator. Notably, along this line of work, 6 conjectures that Langevin dynamics in the tensor PCA setting does not work due to the divergence of the computational-statistical gap in this setting. In our work, we surprisingly show that Langevin dynamics can still be used to recover the planted direction of the single index model. To achieve this, we run Langevin dynamics, but we take the time average of all the iterates. Our analysis reveals that with n\gtrsim d^{\lceil k^{\star}/2\rceil} samples, we are able to recover the direction of the partial trace estimator and hence \theta^{\star} . The key insight is that this Langevin dynamics process closely tracks the Brownian motion on the sphere, and averaging out the iterates roughly corresponds to an ergodicity concentration argument on the sphere. Our main theorem is the following. Theorem 1 (Main theorem (informal)) . Consider a link function \sigma with information exponent k^{\star} . Then, with n\gtrsim d^{\lceil k^{\star}/2\rceil} samples drawn i.i.d. from the standard d -dimensional Gaussian, running Algorithm 1 recovers the ground truth direction \theta^{\star} . We can also shave off a factor of \sqrt{d} to improve the sample complexity to n\gtrsim d^{k^{\star}/2} by running Algorithm 1 and running online SGD on the returned time averaged estimator. This corresponds to the warm start in 14 for the odd case. 2 Setup and Main Contributions 2.1 Notation We use \|\cdot\|_{p} to denote the vector \ell_{p} -norm; furthermore, when p=2 , we often drop the subscript and write \|\cdot\|. Given a probability measure \gamma over \mathbb{R}^{d} , we denote L^{2}(\mathbb{R}^{d},\gamma) the space of \gamma -measurable and square-integral functions; we shorthand this to L^{2}(\gamma) when the domain is clear. For f\in L^{2}(\gamma) , we denote \|f\|_{L^{2}(\gamma)}^{2}=\mathbb{E}_{z\sim\gamma}[f(z)^{2}] . We also denote \mu to be the uniform measure on S^{d-1} . 2.2 Setting We consider in this paper tensor PCA [ 29 ] and single-index models. 2.2.1 Tensor PCA For tensor PCA, we will assume there is a planted direction \theta^{\star}\in S^{d-1} and we observe the k -tensor T defined by: \displaystyle T=\theta^{\star\otimes k}+n^{-1/2}Z\quad\mbox{where}\quad Z_{i_{1},\ldots,i_{k}}\stackrel{{\scriptstyle\text{i.i.d.}}}{{\sim}}N(0,1) We consider optimizing the negative log-likelihood: \displaystyle L(\theta)=-\expectationvalue{T, \theta^{\otimes k}} Information theoretically, \theta^{\star} is possible to recover whenever n\gtrsim d . However, common techniques like approximate message passing (AMP), tensor power method, and online SGD require n\gtrsim d^{k-1} to recover \theta^{\star} [ 29 , 7 ] . Nevertheless, it is possible to recover \theta^{\star} with n\gtrsim d^{k/2} samples using tensor unfolding [ 29 ] , the partial-trace estimator [ 19 ] , and landscape smoothing [ 3 , 9 , 14 ] . In our paper, we show Langevin dynamics combined with iterate