arXiv:2505.15647cs.LGcs.AI2025-05NeurIPS被引 4

提出新方法实现差分隐私下非凸优化的二阶收敛,无需额外选择机制。

Second-Order Convergence in Private Stochastic Non-Convex Optimization

  • 用模型漂移距离判断是否逃出鞍点,避免依赖二阶信息
  • 在真实数据集上验证,收敛误差率优于已有方法
  • 适合高维分布式学习场景,解决私有选择导致的性能下降

我们研究差分隐私(DP)随机非凸优化中寻找二阶驻点(SOSP)的问题。现有方法存在两大缺陷:(i) 忽视梯度方差对鞍点逃逸分析的影响,导致收敛误差率不准确;(ii) 依赖辅助的私有模型选择过程来识别DP-SOSP,显著损害实用性,尤其在分布式设置下。为此,我们提出一个通用的扰动随机梯度下降(PSGD)框架,基于高斯噪声注入和通用梯度算子。核心创新是利用模型漂移距离判断是否逃出鞍点,确保收敛至近似局部极小值,无需依赖二阶信息或额外的DP-SOSP识别。通过采用自适应DP-SPIDER估计器作为具体梯度算子,我们开发了一种新DP算法,修正了先前工作的收敛误差率。我们进一步将该算法扩展至异构数据的分布式学习,首次提供了此类设置下寻找DP-SOSP的正式保证。分析还揭示了高维模型下私有选择过程的负面影响,凸显我们设计的实用性。在真实数据集上的数值实验验证了该方法的有效性。

原文摘要 · Abstract (English)

We investigate the problem of finding second-order stationary points (SOSP) in differentially private (DP) stochastic non-convex optimization. Existing methods suffer from two key limitations: (i) inaccurate convergence error rate due to overlooking gradient variance in the saddle point escape analysis, and (ii) dependence on auxiliary private model selection procedures for identifying DP-SOSP, which can significantly impair utility, particularly in distributed settings. To address these issues, we propose a generic perturbed stochastic gradient descent (PSGD) framework built upon Gaussian noise injection and general gradient oracles. A core innovation of our framework is using model drift distance to determine whether PSGD escapes saddle points, ensuring convergence to approximate local minima without relying on second-order information or additional DP-SOSP identification. By leveraging the adaptive DP-SPIDER estimator as a specific gradient oracle, we develop a new DP algorithm that rectifies the convergence error rates reported in prior work. We further extend this algorithm to distributed learning with heterogeneous data, providing the first formal guarantees for finding DP-SOSP in such settings. Our analysis also highlights the detrimental impacts of private selection procedures in distributed learning under high-dimensional models, underscoring the practical benefits of our design. Numerical experiments on real-world datasets validate the efficacy of our approach.

差分隐私非凸优化二阶收敛分布式学习

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