arXiv:2501.04134stat.MLcs.LG2025-01JMLR

分析非非扩张迭代下的朗之万算法混合时间与隐私边界,突破传统限制。

Mixing Times and Privacy Analysis for the Projected Langevin Algorithm under a Modulus of Continuity

  • 提出基于连续性模的新框架,拓展隐私放大迭代方法适用范围。
  • 在非光滑、弱光滑等情形下获得维度无关的混合时间上界。
  • 适用于梯度不光滑的凸损失场景,适合隐私与优化交叉研究者。

我们研究了投影朗之万算法(LA)的混合时间以及噪声随机梯度下降(SGD)的隐私曲线,突破了以往仅限于非扩张迭代的分析局限。具体而言,推导出投影LA的新混合时间上界,在若干重要情况下为维度无关且关于精度呈对数多项式依赖,与光滑凸情形的已有结果高度吻合。同时,建立了子采样噪声SGD的隐私曲线新上界,揭示其对梯度正则性的关键依赖,适用于广泛的非光滑凸损失函数。分析核心在于将隐私放大由迭代(PABI)框架扩展至梯度映射未必非扩张的噪声迭代,通过构造一个优化问题以获取最优的瑞尼散度界,该问题的可解性关键取决于梯度映射的连续性模。在非光滑凸、弱光滑及(强)耗散等典型情形下,该优化问题可精确求解,从而得到基于PABI的最紧上界。

原文摘要 · Abstract (English)

We study the mixing time of the projected Langevin algorithm (LA) and the privacy curve of noisy Stochastic Gradient Descent (SGD), beyond nonexpansive iterations. Specifically, we derive new mixing time bounds for the projected LA which are, in some important cases, dimension-free and poly-logarithmic on the accuracy, closely matching the existing results in the smooth convex case. Additionally, we establish new upper bounds for the privacy curve of the subsampled noisy SGD algorithm. These bounds show a crucial dependency on the regularity of gradients, and are useful for a wide range of convex losses beyond the smooth case. Our analysis relies on a suitable extension of the Privacy Amplification by Iteration (PABI) framework (Feldman et al., 2018; Altschuler and Talwar, 2022, 2023) to noisy iterations whose gradient map is not necessarily nonexpansive. This extension is achieved by designing an optimization problem which accounts for the best possible Rényi divergence bound obtained by an application of PABI, where the tractability of the problem is crucially related to the modulus of continuity of the associated gradient mapping. We show that, in several interesting cases -- namely the nonsmooth convex, weakly smooth and (strongly) dissipative -- such optimization problem can be solved exactly and explicitly, yielding the tightest possible PABI-based bounds.

朗之万算法隐私分析优化理论连续性模

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。