提出新型随机定位方法，提升非欧几何下采样与隐私优化效率
Functional Stochastic Localization
- 用对数拉普拉斯变换替代高斯正则化，拓展随机定位框架
- 在满足泛函庞加莱不等式时，给出马尔可夫链混合时间上界
- 应用于ℓ_p空间差分隐私凸优化，零阶模型查询复杂度更优
Eldan的随机定位是一种概率构造，在高维几何与采样算法设计中发挥关键作用。为应对非欧几何下的采样及优化中的镜面下降算法，我们发展了Eldan过程的函数型推广，将高斯正则化替换为任意正整数倍的对数拉普拉斯变换正则化。我们进一步给出了由该定位过程诱导的马尔可夫链的混合时间上界，条件是目标分布满足泛函庞加莱不等式。最后，我们将该框架应用于ℓ_p范数（p ∈ [1,2)）下的差分隐私凸优化，在零阶模型中实现了比现有最优方法更低的查询复杂度。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。