Second-Order Convergence in Private Stochastic Non-Convex Optimization
This work addresses limitations in private optimization for machine learning practitioners, offering a more efficient method for ensuring privacy in non-convex settings, though it is incremental by building on existing perturbed gradient descent techniques.
The paper tackles the problem of finding second-order stationary points in differentially private stochastic non-convex optimization by proposing a perturbed stochastic gradient descent framework that avoids auxiliary private model selection, rectifying prior convergence error rates and extending to distributed learning with heterogeneous data, achieving improved utility as validated by experiments.
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.