Abstract
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 arbitrarily 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.
Abstract (translated)
我们研究了在差异隐私（DP）随机非凸优化中寻找二阶平稳点（SOSP）的问题。现有方法存在两个关键局限性：(i) 由于忽视了鞍点逃脱分析中的梯度方差，导致收敛误差率不准确；(ii) 需要依赖于辅助的私有模型选择程序来识别DP-SOSP，这在分布式环境中可能会显著损害效用。 为解决这些问题，我们提出了一种基于高斯噪声注入和一般梯度预测器构建的泛化扰动随机梯度下降（PSGD）框架。我们框架的一个核心创新是使用模型漂移距离来确定PSGD是否逃脱了鞍点，并确保在不依赖于二阶信息或额外DP-SOSP识别的情况下收敛到近似局部最小值。 通过利用自适应DP-SPIDER估计算法作为特定的梯度预测器，我们开发了一种新的DP算法，该算法纠正了先前工作中报告的收敛误差率。我们将此算法进一步扩展至任意异构数据分布式的环境中，并为在这种设置下寻找DP-SOSP提供了第一个正式保证。 我们的分析还强调，在高维模型下的分布式学习中私有选择程序带来的负面影响，突显了我们设计的实际应用价值。在现实世界的数据集上的数值实验验证了我们方法的有效性。
URL
https://arxiv.org/abs/2505.15647
