Private Stochastic Optimization for Achieving Second-Order Stationary Points

Authors: Youming Tao, Dongxiao Yu, Xiuzhen Cheng, Falko Dressler, Di Wang
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: differential privacy, non-convex optimization, saddle points

Abstract:
This paper addresses the challenge of achieving second-order stationary points (SOSP) in differentially private stochastic non-convex optimization. We identify two key limitations in the state-of-the-art: (i) inaccurate error rates caused by the omission of gradient variance in saddle point escape analysis, resulting in inappropriate parameter choices and overly optimistic performance estimates, and (ii) inefficiencies in private SOSP selection via the AboveThreshold algorithm, particularly in distributed learning settings, where perturbing and sharing Hessian matrices introduces significant additional noise. To overcome these challenges, we revisit perturbed stochastic gradient descent (SGD) with Gaussian noise and propose a new framework that leverages general gradient oracles. This framework introduces a novel criterion based on model drift distance, ensuring provable saddle point escape and efficient convergence to approximate local minima with low iteration complexity. Using an adaptive SPIDER as the gradient oracle, we establish a new DP algorithm that corrects existing error rates. Furthermore, we extend our approach to a distributed adaptive SPIDER, applying our framework to distributed learning scenarios and providing the first theoretical results on achieving SOSP under differential privacy in distributed environments with heterogeneous data. Finally, we analyze the limitations of the AboveThreshold algorithm for private model selection in distributed learning and show that as model dimensions increase, the selection process introduces additional errors, further demonstrating the superiority of our proposed framework.

Decision: reject
Reviewer scores: 6, 8, 8, 5

Reviews and discussion:
<thread>
creation date:
1730593776913

thread_type:
official_review

<thread_object>
creator: reviewer_vfr1

<content>
summary:
The paper studies the convergence to a SOSP while preserving differential privacy. The paper points out an issue in the analysis of Liu et al. (2024) - incorrect handling of the stochastic noise - and shows how to fix it. It then presents a differentially private algorithm in the distributed settings.

strengths:
A clear set of results on an interesting theoretically and well-motivated and studied problem.

weaknesses:
Major concerns:

-- Please make it clear where you use non-constant learning rate. You don’t mention it in the main body and even at the crucial point - which seems to be Equation (41). This is a major concern since this is the part which, as you claim, is incorrect in Liu et al.

-- I believe the discussion “Gaps in Private SOSP selection” in Section 3 is not exactly fair.
1) First, one can compute the smallest Hessian eigenvalues efficiently - by using Hessian-vector products, which can be computed efficiently in neural networks.
2) Second, not sure what you mean by “requires additional data” - Liu et al. give bounds in Lemmas 4.1 and 4.5, and no additional data seems to be required.
3) Liu et al. didn’t try to guarantee privacy in the distributed settings, so I’m not sure one can call it a gap. That said, I’m not sure that even their approach has many concerns. First, one can approximate the gradient norm using sketches. Second, as outlined above, one don’t need to perturb Hessians, just the vectors resulting from the Hessian-vector products. Since this needs to be computed for at most logarithmic number of candidates, I expect the overall increase in the amount of noise to be negligible compared with the entire training procedure.

-- You want to find an α-SOSP for the population risk, while the proof seems to only cover the empirical risk (i.e. on the sampled dataset).

-- The choice of b1 and b2 depends on η and χ. On the other hand, η and χ depend on b1 and b2. Please eliminate the cyclic dependency, i.e. express b1 and b2 in terms of problem parameters. Please also express σ and r in the terms of problem parameters. Due to the cyclic dependency, combined with complicated expressions for b1 and b2, I couldn’t verify whether Theorem 2 is correct.

-- In Section 4, I don’t see why you can’t just use the analysis of Jin et al. black-box. The choice of parameters is the same, and the only change I see is how you check whether the point is a saddle point, by checking whether the point moved sufficiently far; this technique is, however, covered in their earlier paper “How to Escape Saddle Points Efficiently”.

questions:
-- For all statements (at least for major theorems and lemmas), please:
1) State all assumptions and parameters precisely (you can state assumptions and refer to them later). To give an example, I spent quite some time looking for definition of U.
2) Refer to the algorithms they correspond to.
3) Refer to where they are proved in the appendix.

-- I personally believe the notation for the escaping radius is not great. I suggest using a more self-explanatory notation, such as R.

-- It’s not clear to me that the choice α = Θ(ψ) is the optimal choice. For example, in analysis of DP-SGD, alpha is basically independent of ψ (that is, you can make ψ and the number of iterations T arbitrarily large, without changing α), so it’s surprising to me that you have a hard dependence of α on ψ.

-- I think the paper would benefit from experimental evaluation.

-- You assume that each individual function (i.e. f(..., z)) is Lipschitz, smooth, and has Lipschitz Hessian. Do you need all of these assumptions for the individual functions?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730644343975

thread_type:
official_review

<thread_object>
creator: reviewer_mxdc

<content>
summary:
This paper studies a DP stochastic non-convex optimization problem with the focus on convergence to the second-order stationary points (SOSP), which is a new formulation and more stringent than previous focus first-order stationary points (FOSP). By revisiting the perturbed SGD with Gaussian noises, the paper corrects the error rate analysis in Liu et al. 2024 who ignored the statistic gradient variance, and improve the computational cost as well as the statistics error in the distributed learning setting in the previous literature Liu et al. 2024.

strengths:
The paper is technically solid and well-written. The insight that model parameters move sufficiently far (over a threshold) leads to the novel algorithmic design as well as the theoretical analysis. The comparisons with the Liu et al. 2024 is solid and comprehensive. The extension to the distributed learning setting with improved computational cost and error guarantee showcase the power of the proposed algorithmic design and analysis.

weaknesses:
A modest size of empirical experiments could help with the illustration of the practical value of the proposed novel algorithm.

questions:
None.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730662684780

thread_type:
official_review

<thread_object>
creator: reviewer_vxfn

<content>
summary:
The paper presents a new framework for achieving SOSPs in DP non-convex optimization. The authors improved over the current state-of-the-art methods by better accounting over gradient variance and error rates based on a perturbed SGD . The framework is also extended to distributed environments.

strengths:
The authors improve upon the state-of-the-art in the challenging area of private stochastic optimization for general non-convex functions.

The paper is a collection of elegant and technically solid results that advance the field through sophisticated analytical techniques.

The proposed algorithm represents a significant innovation compared to previous results.

weaknesses:
For a reader who is not fluent with the literature, the paper is not easy to follow. Several insights are left unexplained. The paper is quite dense without enough provided intuition on the proposed algorithm. However, this is somehow understandable due to the page limit.

questions:
Compared to "Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks," the algorithm got rid of the internal state of "Frozen," which seems to be important. Could the authors further explain this insight?

The gap between the current result and the lower bound is still large (rate of n); any comments on this?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730699993775

thread_type:
official_review

<thread_object>
creator: reviewer_h4wk

<content>
summary:
This paper addresses the problem of achieving second-order stationary points (SOSP) in differentially private (DP) stochastic non-convex optimization. The authors identify two key limitations in the state-of-the-art Liu et al. (2024): (i) inaccurate error rates caused by the omission of gradient variance in saddle point escape analysis (ii) inefficiencies in private SOSP selection via the AboveThreshold algorithm.

The authors propose a new framework that leverages general gradient oracles to overcome these challenges.
The paper establishes a new DP algorithm that corrects existing error rates, and extends the approach to distributed settings.

strengths:
- The paper is well structured and easy to follow. It clearly outlines the gap in state-of-the-art (SOTA) and the contributions.
- The paper points out an error in the analysis of SOTA and establishes the correct rate. The proposed DP-SPIDER seems simpler than the SOTA.
- The authors also consider the distributed settings and demonstrate the benefits of their proposed approach over the AboveThreshold used in SOTA.

weaknesses:
The paper fixes the error in SOTA and establishes a correct rate. It would be nice if the authors could discuss if they think their results can be improved and how they compare with the results in SOTA if an easy fix is possible.

questions:
Is the error in Liu et al. (2024) easy to fix? If so, what would be the correct error rate and how does it compare to your results?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732557742661

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Kind Reminder: Your Feedback Matters – Please Check Our Response

comment:
Dear Reviewers,

We sincerely appreciate your valuable time and effort in reviewing our paper and recognizing its contributions and quality. As the discussion phase is coming to an end, we kindly request you to review our responses and the revised manuscript. If you have any further questions, we would be more than happy to address them. We look forward to your kind re-evaluation of our work.

Thank you for your support!

Sincerely,

Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
Paper studies the problem of privately achieving second order stationary point (SOSP). First, authors identify that current state-of-the-art (SOTA) method has an error in their theoretical analysis and its SOSP selection sub-routine is inefficient. Then they provide a new algorithm and analysis techniques which sidesteps this inefficiency and provide new SOTA DP optimization results. Paper seems to contain correct theory and interesting techniques even though it is dense and hard to parse.

Authors do not provide any empirical evaluation and justify their choice to do so by appealing to standards set by two recent works on this topic. Empirical evaluation is considered important in both ML and Optimization algorithms literature, and particularly in the ICLR conference. For example, proper experimental evaluation of the claims in the prior SOTA work may have identified the error in the analysis. Therefore, the authors are strongly encouraged to add experiments in their next revision.

PS: Notations used in the paper were challenging to parse, especially the non-standard calligraphic letter which all looked similar.