Functional Stochastic Localization
Anming Gu, Bobby Shi, Kevin Tian · 2026
Read Functional Stochastic Localization by Anming Gu, Bobby Shi, Kevin Tian (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-2602-03999.txt.
Introduction
Anming Gu and 2 co-authors generalize a powerful sampling construction. Eldan's stochastic localization gradually reveals a random draw from a distribution, and it has driven breakthroughs in high-dimensional geometry. Their 2026 paper rebuilds the process for non-Euclidean geometry, motivated by mirror descent in optimization.
Gaussian smoothing is replaced by a broader family of regularizers built from log-Laplace transforms. The authors bound the mixing time of the resulting Markov chain under a functional Poincaré inequality. Applied to private convex optimization in certain norms, the framework improves known query costs. The work extends a central modern tool to geometries where it could not go before.
Catalog record
| CREATOR | Anming Gu, Bobby Shi, Kevin Tian |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 111 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-03999
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Functional Stochastic Localization Anming Gu, Bobby Shi, Kevin Tian Abstract Eldan’s stochastic localization is a probabilistic construction that has proved instrumental to modern breakthroughs in high-dimensional geometry and the design of sampling algorithms. Motivated by sampling under non-Euclidean geometries and the mirror descent algorithm in optimization, we develop a functional generalization of Eldan’s process that replaces Gaussian regularization with regularization by any positive integer multiple of a log-Laplace transform. We further give a mixing time bound on the Markov chain induced by our localization process, which holds if our target distribution satisfies a functional Poincaré inequality. Finally, we apply our framework to differentially private convex optimization in ℓ p \ell_{p} norms for p ∈ [ 1 , 2 ) p\in[1,2) , where we improve state-of-the-art query complexities in a zeroth-order model. 1 Introduction Stochastic localization, an elegant construction introduced in [ 36 ] , has emerged as a key ingredient in modern analysis frameworks, enabling numerous recent breakthroughs in high-dimensional geometry and probability [ 71 , 37 , 61 , 38 , 34 , 35 , 46 ] . As a few highlights, the stochastic localization framework has led to improvements to the Kannan-Lovász-Simonovitz (KLS) constant [ 36 , 70 , 24 , 60 , 53 , 62 ] and the recent resolution of Bourgain’s slicing conjecture [ 58 ] and the thin-shell conjecture [ 59 ] . Recently, through its application to proximal sampling [ 69 , 21 ] and the framework of localization schemes [ 23 ] , stochastic localization has also seen applications in the design and analysis of sampling algorithms, for both continuous and discrete distributions [ 33 , 32 , 44 , 5 ] . A standard viewpoint of stochastic localization is as solving the following problem: given a base density \pi over \mathbb{R}^{d} , and a time parameter \tau>0 , construct a distribution over linear tilts \mathbf{y}_{\tau}\propto\mathbb{R}^{d} , 1 1 1 Here and throughout, we use \mathcal{T}_{\mathbf{v}}\nu to mean the density that is \propto\exp(\left\langle\mathbf{v},\cdot\right\rangle)\nu ; see Section 2 for notation. such that \pi_{\tau}\propto\mathcal{T}_{\mathbf{y}_{\tau}}\exp(-\frac{\tau}{2}\lVert\cdot\rVert_{2}^{2})\pi equals \pi in expectation, over the randomness of \mathbf{y}_{\tau} . This equality holds in a pointwise sense, i.e., \mathbb{E}[\pi_{\tau}(\mathbf{x})]=\pi(\mathbf{x}) for all \mathbf{x}\in\mathbb{R}^{d} . The reason this is beneficial is because regardless of how \mathbf{y}_{\tau} is realized, a large Gaussian regularization \propto\exp(-\frac{\tau}{2}\lVert\cdot\rVert_{2}^{2}) is induced. By using the strong geometric properties enjoyed by Gaussians, e.g., isoperimetric, Poincaré, or log-Sobolev inequalities, this process can then be used to reason about \pi itself. Functional stochastic localization. A key feature of stochastic localization is that it primarily lends itself to tools tailored to the Euclidean geometry. This is unsurprising: Gaussians are induced by a (Euclidean) quadratic potential \psi=\frac{1}{2}\left\lVert\cdot\right\rVert_{2}^{2} , and various alternate definitions of stochastic localization (cf. [ 84 ] for a recent survey) rely on stochastic differential equations (SDEs), which are based on the Euclidean construction of Brownian motion. This begs the question: is there a generalization that is more naturally equipped to handle non-Euclidean geometry, e.g., induced by a non-Euclidean norm, or even an arbitrary convex function \psi:\mathbb{R}^{d}\to\mathbb{R} ? This line of inquiry is motivated by the rich literature on non-Euclidean optimization, which has had wide-ranging applications such as sparse recovery [ 19 ] , matrix completion [ 1 ] , combinatorial optimization [ 57 , 68 ] , multi-armed bandit problems [ 17 ] , and more. Many of these applications are intimately related to the framework of mirror descent , a “functional” generalization of gradient descent induced by a non-Euclidean regularizer \psi:\mathbb{R}^{d}\to\mathbb{R} . A parallel question would then be: is there a functional generalization of stochastic localization, e.g., a distribution over linear tilts \mathbf{c}_{\tau}\in\mathbb{R}^{d} that satisfies, for some convex \psi:\mathbb{R}^{d}\to\mathbb{R} , and \pi a density on \mathbb{R}^{d} , \mathbb{E}\left[\pi_{\tau}\right]=\pi,\text{ pointwise on }\mathbb{R}^{d},\text{ where }\pi_{\tau}:=\mathcal{T}_{\mathbf{c}_{\tau}}\exp{\left(-\tau\psi\right)}\pi? (1) The primary contribution of our work is to investigate this question, and to construct a generalized process realizing ( 1 ) for structured \psi . We term our construction functional stochastic localization (to contrast with [ 36 ] , henceforth referred to as (Euclidean) stochastic localization ). Applications to sampling. While we believe our construction is interesting in its own right, our primary motivation is applications to designing sampling algorithms under non-Euclidean regularity. Since the characterization of sampling as optimization over the space of measures [ 55 ] , sampling algorithms for continuous distributions have drawn heavy inspiration from convex optimization [ 27 , 28 , 89 , 90 , 88 , 29 , 76 , 80 ] (cf. [ 26 ] for a thorough discussion). However, compared to sampling in Euclidean spaces, development of non-Euclidean samplers has lagged behind. The sampling analog of mirror descent is to reweight Brownian motion by \nabla^{2}\psi , e.g., in the mirror Langevin dynamics [ 50 , 25 ] . Several works have considered the corresponding discretization [ 50 , 94 , 2 , 54 , 73 ] ; however, they often require non-standard assumptions to achieve vanishing bias [ 73 ] , or only discretize the drift but not the diffusion [ 2 , 54 , 45 ] . Other approaches include the discretized Riemannian Langevin dynamics, which requires exact sampling from the manifold [ 40 , 72 ] , or using a filter to obtain an unbiased algorithm [ 86 , 85 ] , which again requires additional regularity. Recently, [ 43 ] introduced a complementary approach via a functional variant of the proximal sampler (an algorithmic variant of Euclidean stochastic localization), and studied its use in sampling from non-Euclidean spaces. This approach was based on the theory of the log-Laplace transform \varphi^{\sharp} (LLT, Definition 1 ), a probabilistic analog of the Fenchel transform \varphi^{*} central to mirror descent. Moreover, [ 43 ] showed that LLTs satisfy useful properties, e.g., self-concordance and strong convexity-smoothness duality (Facts 1 , 2 ) that make them amenable to applications similar to uses of mirror descent. The construction of [ 43 ] can be rephrased in terms of ( 1 ), where \psi is an LLT, but their framework only permitted taking \tau=1 . Moreover, the proof strategy of [ 43 ] led to a quadratic overhead in the mixing time of their sampler compared to Euclidean counterparts, opening the door to a stronger and more flexible approach. 2 2 2 We expand on this point in Section 1.1 . The conference version appeared at COLT 2023 [ 41 ] , but contained an error. This was later fixed in the third arXiv version, which led to a quadratic overhead, cf. their Section 1.4. 1.1 Our approach We develop a new approach to the construction of processes matching ( 1 ), when \psi:=\varphi^{\sharp} is a log-Laplace transform (Definition 1 ). Our construction is summarized and analyzed in Section 3 , and carefully uses structural facts about LLTs and exponential families , a parametric family of high-dimensional distributions, to argue that the martingale property ( 1 ) holds. Defining functional stochastic localization. Our framework is motivated by and related to [ 43 ] , but substantially broadens its flexibility. To better explain this relationship, it is helpful to outline a typical mixing-time result for Euclidean proximal samplers. Let \pi be a density on \mathbb{R}^{d} that satisfies an \alpha -Poincaré inequality (PI, Definition 3 ).