Functional Stochastic Localization
This work addresses sampling challenges in high-dimensional geometry and optimization, with applications in privacy-preserving algorithms, though it builds incrementally on existing localization methods.
The authors tackled the problem of sampling under non-Euclidean geometries by developing a functional generalization of Eldan's stochastic localization process, which improved state-of-the-art query complexities for differentially private convex optimization in ℓ_p norms for p in [1, 2).
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 $\ell_p$ norms for $p \in [1, 2)$, where we improve state-of-the-art query complexities in a zeroth-order model.