Second-Order Convergence in Private Stochastic Non-Convex Optimization

We thank Reviewer Rud7 for the thoughtful feedback and for acknowledging the clarity of our theoretical analysis and the significance of our results, particularly the rectified error rate and the first error bound for DP-SOSP under arbitrarily heterogeneous data.

Response to Weaknesses

1. Regarding empirical results only mentioned in the appendix: We appreciate the reviewer’s suggestion. We will summarize the key empirical results in the main text and, if accepted, use the extra page to incorporate them more clearly.

2. Regarding need for more insights into the importance of DP-SOSP and the theorems: Thank you for pointing this out. We agree that providing more intuitive explanations about the motivation and implications of DP-SOSP would benefit a broader audience. In the final version, we will update the introduction to emphasize why DP-SOSP is important: while first-order convergence (FOSP) may still return saddle points or local maxima, second-order guarantees are essential for ensuring meaningful local optimality in non-convex problems. We will also include a brief comment on what insights the theorems provide.

Response to Question

Our work focuses on population risk minimization because the issues we identified in the prior method and its analysis primarily arise in this setting. For ERM, we note that our Gauss-PSGD framework is also compatible with ERM analysis, and whether it can improve the bound for ERM is an interesting problem to investigate for future work. Regarding lower bound, the results presented in [29] are directly from [1], which primarily addresses convex loss functions and first-order stationary points. In contrast, establishing lower bounds for finding DP-SOSP in non-convex optimization is inherently more challenging and remains an open problem, which we leave for future work.

We thank Reviewer jvqK for the detailed and constructive review. We are grateful for the recognition of our contributions, including the correction of flaws in prior saddle point escape analysis, the design of Gauss-PSGD based on model drift, the elimination of high-overhead private model selection, and the extension to distributed learning with heterogeneous data. We also appreciate the acknowledgment of the clarity and rigor of our theorems and algorithmic design.

Response to Weaknesses

1. Regarding dense parameter settings in Section 3.3 and 4.2： Thank you for the suggestion. In the final version, we will supplement the main text with more intuitive explanations of the parameters, including how they relate to algorithmic behavior and theoretical guarantees, to improve accessibility for broader audiences.

2. Regarding practical impact for industrial-scale ML tasks: We agree that connecting our theoretical results to real-world applications is important. This work focuses primarily on improving and correcting the theoretical foundations of DP-SOSP, particularly addressing limitations in [29] and providing a refined understanding of saddle point escape behavior. That said, we will add a brief discussion to highlight potential industrial use cases, such as privacy-preserving distributed training, and we plan to explore more empirical evaluations in future work.

3 & 4. Regarding the organization of the paper: We appreciate the helpful suggestions. Due to strict page constraints, we initially placed some experimental results and prior work discussions in the appendix. We agree that summarizing key empirical findings, especially the comparison with [29], in the main paper would strengthen the presentation. If accepted, we will use the additional content page to reincorporate the most essential experiments and discussion of prior works into the main submission, making it more self-contained and empirically grounded.

Response to Questions

Q1: The parameter settings are derived from our convergence and privacy analysis:

• The escape threshold $\chi$ is set to match the gradient estimation error, as established in Lemma 5, which ensures a uniform average decrease in function value of at least $O(\chi^2\eta)$ per PSGD step, regardless of whether the algorithm is in an escape phase, as shown in Lemma 6.
• The model drift threshold $\kappa$ is chosen to balance the cumulative error introduced by the gradient oracle $\mathcal{O}_1$ and $\mathcal{O}_2$, as shown around lines 790 and 820.
• The maximum drift threshold $\mathcal{R}$ and the maximum escape steps $\Gamma$ are designed to (1) control the curvature-dependent term $\mathscr{P}_h(t)$, as in Eq. (41); and (2) ensure that the stochastic gradient noise term $\mathscr{P} _{sg}(t)$ remains bounded, as in Eq. (43).
• The maximum repeat number $Q$ is selected logarithmically in failure probability to amplify success probability, as specified in Lemma 2.

Q2: The model drift criterion is particularly useful in settings where global function values are inaccessible, but model updates are observable, such as the population risk minimization setting considered in our paper. One potential issue is that small, flat local minima may trigger unnecessary escapes. However, as noted in our response to Reviewer jpLh's Q1, this does not affect our convergence guarantee to a DP-SOSP. Moreover, this property could potentially be leveraged to encourage flatter minima, in line with recent work on sharpness-aware minimization for improved generalization. We view this as a promising direction for future research.

Thanks to the authors for their detailed response. I acknowledge the theoretical contributions of the paper. However, as with many differentially private (DP) works that include dense mathematical derivations and theorems, the true impact of such contributions can be difficult to assess if the results do not provide clear insights into practical scenarios. In that sense, while the theory appears sound, it is challenging to evaluate its real-world significance, as many DP papers appear equally rigorous on the surface.

That said, I appreciate the additional experiments provided in the rebuttal. However, another concern arises: when comparing results across DP-SGD, DIFF2, and the proposed method using ResNet-18, it appears that the proposed method outperforms the others in federated settings. This outcome contradicts my general understanding—federated learning typically yields comparable or slightly worse performance than centralized settings due to issues such as data heterogeneity and limited communication. Clarification on this point would be helpful.

We thank Reviewer DNHR for the positive assessment and for highlighting the originality, significance, and clarity of our work. We are particularly grateful for the recognition of our new second-order error analysis for DP non-convex optimization, the extension to distributed heterogeneous data, the design of the unified Gauss-PSGD framework with Ada-DP-SPIDER, and the clarity of our theoretical exposition despite the technical density.

Response to Weaknesses

1. Regarding the scope of experiments: We agree that more demanding tasks and broader baselines would strengthen the empirical perspective. However, as the reviewer noted, our paper is primarily theoretical. Our experiments are designed to validate the theoretical claims, particularly by demonstrating that our method outperforms the only existing DP non-convex baseline with second-order guarantees (Liu et al. [1]). While general-purpose baselines like DP-SGD are widely used, they do not target second-order guarantees and are therefore not directly comparable in this context. That said, we fully agree that expanding the experimental evaluation to more complex models and broader tasks is a valuable direction, which we plan to pursue in future work on differentially private optimization.

2. Regarding the conclusion being the appendix: We appreciate this suggestion and agree that key discussion sections such as the conclusion and limitations are best included in the main text. In the final version, we will further compress technical parts as needed and take advantage of the optional extra content page (if accepted) to bring these important sections back into the main paper.

Response to Questions

Q1 & Q2: Thank you for raising this point. We agree that including $c_1$ and $c_2$ in Theorem 2 could be confusing, since they do not appear explicitly in the final error bound. These constants originate from the Gaussian mechanism and determine the variance of added noise. In the final version, we will remove these constants from the theorem statement and instead include them only in the algorithmic and privacy analysis sections, with a clearer explanation of their origin and meaning. To answer the second part: yes, these constants are consistent with those derived in standard moments-accountant analyses (e.g., Abadi et al. 2016), and we will make this more explicit in the paper.

Q3: This is a sharp observation. We note that the difference in test accuracy is marginal, which we believe is primarily due to random variation across runs. As the number of clients $m$ and the number of samples per client $n$ increase, the marginal gain in utility from relaxing the privacy budget (i.e., increasing $\epsilon$) becomes smaller. This aligns with our theoretical bound $\tilde{O}(\frac{1}{(mn)^{1/3}} + \big(\frac{\sqrt{d}}{\epsilon \sqrt{m}n}\big)^{2/5})$, where the influence of $\epsilon$ becomes less significant when $mn$ grows. Therefore, in high-data regimes, the effect of changing $\epsilon$ may be overshadowed by the inherent variance of the stochastic training process.

Q4: Thank you for pointing this out. You are correct. We apply gradient clipping during training. The clipping threshold was chosen via grid search, and the configuration reported in the paper uses a threshold of 1.0. We will add this detail in the final version.

Q5: Thank you for catching this typo. We will fix it in the final version.

We thank Reviewer jpLh for the detailed and constructive feedback. We are especially grateful for the recognition of our theoretical contributions, including the improved and corrected convergence error rates, the avoidance of separate private model selection procedures, and the extension to distributed heterogeneous settings. We also appreciate the acknowledgement of our use of model drift as a novel escape criterion for saddle points.

Response to Weaknesses

1. Regarding empirical evaluation: We acknowledge the importance of empirical validation in differentially private optimization. As the reviewer noted, our work is primarily theoretical, and our experiments are designed to evaluate the effectiveness of our approach specifically in the context of DP-SOSP under population risk minimization, where Liu et al. [1] is the only prior relevant baseline. In this regard, we believe our experiments are both necessary and sufficient to support the contributions of this work. We agree that broader empirical comparisons (e.g., with general-purpose DP classifiers) are valuable but fall outside the specific scope of our problem. We view this direction as important future work and plan to pursue more comprehensive empirical studies that explore utility trade-offs across broader tasks.

2. Regarding theoretical assumptions and ease of implementation: We thank the reviewer for this valuable suggestion. We agree that a clearer discussion of how hyperparameters (whether stemming from the assumptions such as Lipschitzness and smoothness, or from the optimization procedure such as the drift threshold and learning rate) influence practical performance would help make our results more accessible. We will also include in the appendix a structured summary of the constants and polylog factors that are currently hidden in the Big-O notation, as well as comments on their practical implications.

3. Regarding the minor comments: We thank the reviewer for the constructive suggestions. We will take all of them into consideration when preparing the final version.

Response to Questions

Q1: While it is possible that a local minimum in a very flat landscape may trigger noticeable model drift, our algorithm is designed to ensure that it eventually returns a true local minimum. Specifically, the algorithm escapes every saddle point with high probability (as shown in Lemma 1), and each successful escape (whether from a saddle point or a flat region) incurs a large model drift and sufficient function decrease (Lemma 4). Since the objective is bounded below, the total number of such escapes is bounded. Therefore, the algorithm must eventually reach and return an approximate local minimum (i.e., an $\alpha$-SOSP).

Q2: Yes, our framework can be readily extended to other privacy notions such as Rényi DP, Gaussian DP, or z-CDP. We emphasize that changing the specific DP definition does not meaningfully affect our results, as our analysis is based on the Gaussian mechanism, which satisfies all these privacy notions. Any improvements would only be polynomial in terms of $log(1/\delta)$, which does not qualitatively change our convergence guarantees.

Q3: Norm-sub-Gaussian random vectors are a general class that includes sub-Gaussian vectors as a special case (see [22]), and this assumption has been adopted in prior state-of-the-art work on non-private SOSP problems [23]. We believe it is a reasonable and flexible starting point for analyzing DP-SOSP. That said, we agree that understanding the behavior of saddle point escape under heavy-tailed noise is an important direction for future work, and we plan to investigate this further.