2025-11-17T13:58:12.673309

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

Bravo, Flores-Mella, Guzmán
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.
academic

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

基本信息

  • 论文ID: 2501.04134
  • 标题: Mixing Times and Privacy Analysis for the Projected Langevin Algorithm under a Modulus of Continuity
  • 作者: Mario Bravo, Juan Pablo Flores-Mella, Cristóbal Guzmán
  • 分类: stat.ML cs.LG math.OC math.ST stat.TH
  • 发表时间: 2025年1月 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2501.04134

摘要

本文研究了投影朗之万算法(Projected Langevin Algorithm)的混合时间和噪声随机梯度下降(SGD)的隐私曲线，超越了非扩张迭代的范围。具体而言，作者为投影朗之万算法导出了新的混合时间界限，在某些重要情况下，这些界限是无维度的且在精度上是多对数级的，与光滑凸情况下的现有结果紧密匹配。此外，本文还为子采样噪声SGD算法建立了新的隐私曲线上界。这些界限显示了对梯度正则性的关键依赖，对光滑情况之外的广泛凸损失函数都有用。

研究背景与动机

问题背景

  1. 采样问题的重要性: 从对数凹分布π ∝ e^(-f)采样是一个基本的算法问题，是体积估计、优化、贝叶斯统计、机器学习和差分隐私等问题的基础构建块。
  2. 朗之万算法: 朗之万算法通过离散化朗之万扩散来近似模拟目标分布：
    dL_t = -∇f(L_t)dt + √2dW_t

    离散化后得到马尔可夫链：
    X_{t+1} = Π_X[X_t - η∇f(X_t) + √(2η)ξ_t]
  3. 现有方法的局限性:
    • 大部分研究集中在强凸光滑势函数设置
    • 对非光滑凸势函数的研究较少
    • PABI(Privacy Amplification by Iteration)技术主要限于非扩张迭代

研究动机

本文旨在将PABI技术扩展到非扩张迭代之外，通过连续性模数(modulus of continuity)来量化底层映射的正则性，从而处理包括不可微函数在内的更广泛的势函数类别。

核心贡献

  1. 扩展PABI框架: 将PABI技术扩展到具有连续性模数的一般映射，甚至可以处理不连续映射。
  2. 优化问题设计: 设计了一个优化问题来获得PABI应用的最佳Rényi散度界限，该问题的可处理性与相关梯度映射的连续性模数密切相关。
  3. 显式解: 证明了当连续性模数为φ(δ) = √(cδ² + h)形式时，优化问题可以精确显式求解。
  4. 混合时间界限: 为凸和(p,M)-弱光滑情况建立了新的混合时间界限，在某些情况下是无维度的且在精度上是多对数级的。
  5. 隐私曲线分析: 为噪声SGD建立了新的隐私曲线上界，显示了对梯度正则性的关键依赖。

方法详解

任务定义

研究投影噪声迭代：

X_{t+1} = Π_X[Φ_t(X_t) + ξ_t], ξ_t ~ N(0, σ²_t I_{d×d})

其中Φ_t具有连续性模数φ_t。

连续性模数框架

定义

对于映射Φ: X ⊆ ℝ^d → ℝ^d，非递减函数φ: ℝ₊ → ℝ₊是Φ的连续性模数，如果：

‖Φ(x) - Φ(y)‖ ≤ φ(‖x - y‖) ∀x, y ∈ X

重要案例

  1. 凸Lipschitz: φ(δ) = √(δ² + (2ηL)²)
  2. 凸(p,M)-弱光滑: φ(δ) = √(δ² + (2η^(1/(1-p))√((1-p)/(1+p))(M/2)^(1/(1-p)))²)
  3. 强耗散: φ(δ) = √((1-2ηκ+η²β²)δ² + 2ηλ)

PABI扩展

核心引理

引理3.2: 设X ⊆ ℝ^d是闭凸集，Φ具有连续性模数φ。对于随机变量X, X'和高斯噪声ξ ~ N(0, σ²I)，令Y = Π_XΦ(X) + ξ, Y' = Π_XΦ(X') + ξ，则对任意0 < a ≤ φ(δ)：

R_α^(φ(δ)-a)(Y‖Y') ≤ R_α^(δ)(X‖X') + αa²/(2σ²)

移位优化问题

为获得最紧的PABI界限，需解决移位优化问题：

min_{u∈R} E(u) := Σ_{t=1}^T (φ_{t-1}(u_{t-1}) - u_t)²/σ²_{t-1}

主要理论结果

定理3.4 (主要结果)

设φ_t(δ) = √(c_tδ² + h_t)，则对于投影噪声迭代：

R_α(X_T‖X'_T) ≤ α/2 [Π_{k=0}^{T-1}c_k D² / Σ_{j=0}^{T-1}σ²_j Π_{l=j+1}^{T-1}c_l + Σ_{t=0}^{T-1} h_t Π_{k=t+1}^{T-1}c_k / Σ_{j=t}^{T-1}σ²_j Π_{l=j+1}^{T-1}c_l]

实验设置

理论分析框架

本文主要是理论工作，通过严格的数学证明建立界限，而非实证实验。分析包括：

  1. 混合时间分析: 使用全变差距离评估收敛速度
  2. 隐私分析: 使用Rényi差分隐私框架
  3. 优化分析: 证明移位优化问题的最优解存在性和唯一性

评价指标

  • 混合时间: T_{mix,TV}(ε) = min{t ∈ ℕ: d(t) ≤ ε}
  • Rényi散度: R_α(μ‖ν)
  • 全变差距离: ‖μ - ν‖_

实验结果

混合时间界限

定理4.2 (弱光滑情况)

对于凸和(p,M)-弱光滑函数，如果1/η ≥ Θ，则：

T_{mix,TV}(ε) ≤ ⌈D²/η⌉ · ⌈log₂(1/ε)⌉

其中Θ = (M/2)^(2/(1+p))(1-p)/(1+p) max{16ln(D(M/2)^(1/(1-p))e), 27}^((1-p)/(1+p))

定理4.3 (强耗散情况)

对于(λ,κ)-强耗散和β-光滑函数，设c = 1 - 2ηκ + η²β² < 1，则：

T_{mix,TV}(ε) = O(log_{1/c}(1 + D²(1-c)/(4η)) · (e/(1-c))^{λ/2} log₂(1/ε))

隐私曲线分析

定理5.2 (噪声SGD)

对于凸、L-Lipschitz和(p,M)-弱光滑损失，噪声SGD满足(α,ε)-RDP，其中：

ε ≤ α/σ² [16L²T/n² + D²/(η²T) + 4η^(2p/(1-p))(1-p)/(1+p)(M/2)^(2/(1-p))ln(T·e)]

关键发现

  1. 维度无关性: 在某些情况下，混合时间界限不依赖于维度d
  2. 正则性依赖: 隐私界限显著依赖于梯度的正则性参数p
  3. 最优性: 对于φ(δ) = √(cδ² + h)形式的连续性模数，优化问题有唯一最优解
  4. 退化情况: 当p = 0(Lipschitz情况)时，无法获得随n → ∞消失的隐私界限

相关工作

朗之万算法研究

  • 光滑强凸情况: Dalalyan (2017), Durmus and Moulines (2019)等的大量研究
  • 非光滑情况: 研究相对较少，主要包括Pereyra (2016), Chatterji et al. (2020)等

PABI技术

  • 原始框架: Feldman et al. (2018)提出
  • 扩展应用: Altschuler and Talwar (2022, 2023)应用于光滑凸情况
  • 本文贡献: 扩展到连续性模数框架

差分隐私

  • 经典分析: 假设所有迭代都被发布
  • 最后迭代: Chourasia et al. (2021), Ye and Shokri (2022)等研究最后迭代的隐私

结论与讨论

主要结论

  1. 成功将PABI技术扩展到非扩张迭代之外
  2. 为多种重要的势函数类别建立了紧致的界限
  3. 证明了连续性模数在隐私和采样分析中的关键作用

局限性

  1. 非光滑情况: 在Lipschitz情况下无法获得非平凡的隐私放大
  2. 步长限制: 某些结果需要更严格的步长约束
  3. 特定形式: 主要结果限于φ(δ) = √(cδ² + h)形式的连续性模数

未来方向

  1. 扩展到更一般的连续性模数形式
  2. 改进非光滑情况下的隐私界限
  3. 研究鞍点问题等更复杂设置

深度评价

优点

  1. 理论创新: 将PABI技术成功扩展到更一般的设置，具有重要的理论价值
  2. 数学严谨: 证明完整严密，优化问题的解析解展现了深刻的数学洞察
  3. 实用价值: 结果适用于包括不可微函数在内的广泛势函数类别
  4. 统一框架: 通过连续性模数提供了统一的分析框架

不足

  1. 应用受限: 主要结果局限于特定形式的连续性模数
  2. 实证验证: 缺乏数值实验验证理论结果的紧致性
  3. 非光滑挑战: 在非光滑情况下的隐私结果相对悲观

影响力

  1. 理论贡献: 为采样和隐私分析提供了新的理论工具
  2. 方法论价值: 连续性模数方法可能启发其他相关研究
  3. 实践指导: 为实际算法设计提供了理论指导

适用场景

  1. 贝叶斯推断: 涉及非光滑先验的后验采样
  2. 差分隐私: 需要精确隐私保证的机器学习应用
  3. 优化: 非光滑凸优化问题的随机算法分析

参考文献

  • Altschuler, J. and Talwar, K. (2022, 2023). Privacy amplification by iteration
  • Feldman, V. et al. (2018). Privacy amplification by iteration
  • Dalalyan, A. (2017). Langevin Monte Carlo analysis
  • Bubeck, S. et al. (2018). Projected Langevin Monte Carlo

这篇论文在理论机器学习和差分隐私领域做出了重要贡献，通过连续性模数的创新使用，成功扩展了PABI技术的适用范围，为非光滑优化和隐私保护算法分析提供了新的理论工具。