math.PRFeb 3, 2026

Functional Stochastic Localization

Authors: Anming Gu, Bobby Shi, Kevin Tian

Organizations: University of Texas at Austin

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.

Explore similar work

Mar 31, 2026

Total Variation Guarantees for Sampling with Stochastic Localization

Motivated by the success of score-based generative models, a number of diffusion-based algorithms have recently been proposed for the problem of sampling from a probability measure whose unnormalized density can be accessed. Among them, Grenioux et al. introduced SLIPS, a sampling algorithm based on Stochastic Localization. While SLIPS exhibits strong empirical performance, no rigorous convergence analysis has previously been provided. In this work, we close this gap by establishing the first guarantee for SLIPS in total variation distance. Under minimal assumptions on the target, our bound implies that the number of steps required to achieve an ε\varepsilon-guarantee scales linearly with the dimension, up to logarithmic factors. The analysis leverages techniques from the theory of score-based generative models and further provides theoretical insights into the empirically observed optimal choice of discretization points.
Nov 2, 2026

Subpolynomial-Query Proximal Sampling Beyond Log-Concavity

We study the gradient query complexity of sampling from a density π(x)∝e−V(x)π(x)\propto\mathrm{e}^{-V(x)} on Rd\mathbb{R}^d, where VV has a ββ-Lipschitz gradient but need not be convex. Our approach uses the proximal sampler, which alternates Gaussian perturbation with sampling a position conditional on the noisy observation. We implement its observation chain using the high-order noisy conditional sampler of [OpenAI 2026], obtaining improved dimension dependence under functional inequalities. If ππ satisfies a log-Sobolev inequality (LSI) with constant αα, then for every fixed ν>0ν>0, there is a finite constant CνC_ν depending only on νν such that the algorithm returns a sample within total-variation distance ε\varepsilon using at most Cνκ(d+κ+ε−1+∥∇V(x0)∥2/β)νC_νκ(d+κ+\varepsilon^{-1}+\|\nabla V(x_0)\|^2/β)^ν queries, where κ=β/ακ=β/α and x0x_0 is an arbitrary reference point for initialization. The analysis controls center-dependent local errors along exact proximal histories and removes the final observation noise by conditional decoding. Under a Poincaré inequality (PI), we obtain a corresponding guarantee from a warm start with a known bound on its Rényi divergence. An oracle lower bound shows that a stationary point alone, which suffices under LSI, is insufficient under PI.
Apr 7, 2026

Optimal Rates for Pure ε\varepsilon-Differentially Private Stochastic Convex Optimization with Heavy Tails

We study stochastic convex optimization (SCO) with heavy-tailed gradients under pure ε\varepsilon-differential privacy (DP). Instead of assuming a bound on the worst-case Lipschitz parameter of the loss, we assume only a bounded kk-th moment. This assumption allows for unbounded, heavy-tailed stochastic gradient distributions, and can yield sharper excess risk bounds. Prior work characterized the minimax optimal rate for ρρ-zero-concentrated DP SCO up to logarithmic factors in this setting, but the pure ε\varepsilon-DP case has remained open. We characterize the minimax optimal excess-risk rate for pure ε\varepsilon-DP heavy-tailed SCO up to logarithmic factors. Our algorithm achieves this rate in polynomial time with high probability. Moreover, it runs in deterministic polynomial time when the worst-case Lipschitz parameter is polynomially bounded. For important structured problem classes -- including hinge/ReLU-type and absolute-value losses on Euclidean balls, ellipsoids, and polytopes -- we achieve deterministic polynomial time even when the worst-case Lipschitz parameter is infinite. Our approach is based on a novel framework for privately optimizing Lipschitz extensions of the empirical loss. We complement our upper bound with a nearly matching high-probability lower bound.