Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper provides formal guarantees for finding second order stationary points of nonconvex loss functions under differential privacy and certain (standard) smoothness assumptions on the loss function. The paper provides a formal analysis for a noisy version of the "gradient descent with negative curvature steps" algorithm. Privacy is ensured via noisy versions of the gradient or Hessian at each step. The paper also analyzes a DP line search (for step sizes) variant of the algorithm which guarantees privacy via the sparse vector technique. Finally, the paper provides experiments for a nonconvex loss function to study the effectiveness of their method.
strength_and_weaknesses: Strengths:

The paper provides sound and precise proofs and theorem statements. The paper provides both a simple and more involved (line search) version of their algorithm, which makes the overall analysis easier to follow and provides a deeper look into their method. The authors provide experiments to support the rational for using line search, and show that this method leads to faster running time.

Weaknesses: 

The results of the paper may be of limited interest. The rates achieved by the algorithm for obtaining a second order stationary point do not improve upon existing rates and are in fact worse than DPTR as the authors themselves note. The authors argue that their algorithm is more practical than DPTR, because less Hessian evaluations are needed. While this is true, the algorithm seems no more practical than the the DP-GD algorithm of (Wang et al., 2019), as there too the Hessian would only need to be evaluated after first order stationarity is checked. Further, DP-GD achieves the same rate. The authors do propose a line search variant to further improve the practical running time, but the fact that any Hessian computations are still needed limits the reach of this improvement. 
clarity,_quality,_novelty_and_reproducibility: For the most part the paper is clearly written and provides adequate details in the proof, although the experiments sections seems to lack a comparison to the DP-GD method of (Wang et al, 2019). I do think that the proof of Theorem 1 should make a comment with regards to the sensitivity bound. There are a few minor typos/broken references that could easily be fixed. 
summary_of_the_review: The paper is well written and proposes a new algorithm/analysis for finding second order stationary points. However, the results obtained by this analysis do not improve over existing methods.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors proposed differentially private optimization algorithms for empirical risk minimization. To improve the speed and practicality of the algorithm, the authors proposed to use several simple yet effective strategies such as line search and mini-batching. The effectiveness of the proposed approach is validated through numerical experiments. 
strength_and_weaknesses: Strength:
 The problem studied in the paper is important and interesting. The proposed algorithm makes sense. 

Weaknesses:

1. The presentation of the paper could be further improved. For instance, the benefits of using nonconvex loss functions should be clarified in the introduction section. In Assumptions 1 and 2, restrictions on loss functions are imposed. Further remarks, including loss functions that satisfy the assumptions, are expected here. 

2. I think more details regarding the numerical experiments should be provided. For example, how the tuning parameters were selected is not clear to me. And it is also not clear why this particular loss function is chosen in numerical experiments. I expect more extensive simulation results. 

 
clarity,_quality,_novelty_and_reproducibility: Clarity: this paper is in general well-written. 

Quality: the results provided by the paper seem correct

Novelty: the proposed algorithm is novel. 

Reproducibility: proofs for the theorems seem correct. 
summary_of_the_review: see above
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the problem of differentially private nonconvex ERM. More specifically, the authors propose a differentially private method aiming to find the approximate second-order necessary solution. The proposed method is a straightforward extension of the existing nonprivate method by injecting random Gaussian noise into the objectives, gradients, and Hessians. The authors provide the convergence guarantee of the proposed method, and an experiment validates the effectiveness of the proposed method.
strength_and_weaknesses: The strength of the paper:
1. The proposed method is able to find the 2NS of the nonconvex ERM with privacy guarantees.
2. The convergence guarantee is established.
3. A line search-based algorithm is developed, which could be of independent interest.

The Weaknesses of the paper:
1. The proposed method seems to be a straightforward extension of the existing nonprivate method by injecting random Gaussian noise to objectives, gradients, and Hessians. What is the key challenge when you derive the theoretical guarantees compared with the nonprivate counterpart?
2. To control the error introduced by the random noise, the proposed method require a stringent condition on the sample complexity. This condition could be violated in practice. Therefore, a more meaningful question could be: given a fixed sample size $n$ and the privacy budget $\rho$, what is the best $(\epsilon_{g},\epsilon_{H})$-2NS one can achieve using your proposed method.
3. The proposed method needs to compute the Hessian matrix, which could be time-consuming.
4. It seems that there is no advantage in terms of sample complexity when we use line search-based algorithm.
5. A single experiment with a small dataset is not enough to validate the effectiveness of the proposed method. The authors should consider experiments using neural networks.
clarity,_quality,_novelty_and_reproducibility: The presentation is clear. However, it is unclear how to keep track of the privacy loss and determine $\sigma,\sigma_g,\sigma_H$  when we implement the algorithm in practice. 
summary_of_the_review: The problem considered in this paper is very relevant and interesting. However, the proposed method seems to be incremental. In addition, the requirement for the sample seems to be very strong, and it is unclear how to determine the privacy related parameters in practice.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents differentially private algorithms to find approximate solutions with second-order guarantees for nonconvex problems, i.e., solutions with small gradients and almost positive definite Hessian matrices. The paper first develops an algorithm with step size depending on some parameters of problems, and then extends it to the algorithms with line search. A minibatch variant is also discussed. Experimental results are also presented to show the effectiveness of the proposed algorithm.

strength_and_weaknesses: **Strength**

Most of the DP algorithms focus on finding first-order approximate solutions of ERM problems. This paper aims to find second-order approximate solutions, which are much more challenging.

Both theoretical and experimental analysis are presented for the proposed algorithm with and without line search.

**Weakness**

The paper only discusses results on sample complexity. There is no analysis on the computation complexity for the proposed algorithm, which is also an important issue.

The sample complexity is of the order $O(\alpha^{-2})$, which is worse than the state of the art $O(\alpha^{-7/4})$.

The theoretical analysis assumes a bounded gradient assumption on the loss function. In the experiments, the function involves a regularizer $\sum_i\lambda w_i^2/(1+w_i^2)$, whose gradients are not bounded. Therefore, the theoretical analysis and experimental analysis are not consistent.
clarity,_quality,_novelty_and_reproducibility: The paper is largely clearly written. However, the motivation of the algorithms are not clear. It would be helpful if the authors can give some explanation of the algorithm.

The paper does not use the standard template of ICLR2023. The authors need to address this in the revised version.

There is a gap between the derived sample complexity and the existing bound. It would be helpful if the authors can explain the challenge in bridging this gap.

Above Eq (7), the authors say the step sizes are independent of k. However, this is not the case according to the step size in Eq (7): 

Above Lemma 2: "oef" should be "of"

Section 4: "columns is" should be "columns are"

Proof of Theorem 8: "similar to D.4" should be "similar to Corollary D.4"?

The section of conclusion is not provided.

Definition A.2: the inequality should be an equality

Definition A.4: it seems that "$M$ satisfies $(\alpha,\xi+\rho\alpha)$-RDP" is not correct

Proposition A.6: "$(\epsilon,\delta)$-DP to zCDP" should be "zCDP to $(\epsilon,\delta)$-DP"

Proposition A.7: $\Delta_f$ should be $\Delta_h$

Below Eq (30): there is ??
summary_of_the_review: The paper considers a challenging problem of finding the second-order approximate solutions for smooth ERM problems. The analysis seems to be challenging and interesting. There is a gap between theory and experiments: the theoretical analysis requires a bounded gradient assumption, which does not hold for the problem considered in the experiments.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper formally studies differentially private algorithms for approximating second-order stationary points of nonconvex losses. 

The authors give formal convergence guarantees for noisy SGD with negative curvature search. The authors also propose a differentially private line search method for selecting the step size. The theoretical results are complemented with numerical experiments to test the performance of the proposed methods. 

Although the authors provide rigorous analyses and formal guarantees for a fundamental problem of considerable importance to the area of privacy-preserving optimization, the results are mostly incremental. The formal results do not provide rate improvements for this problem compared to prior constructions (DP-TR [Wang & Xu 2021] and DP-GD [Wang et al.  2019]). 

The claims of practicality of the proposed methods compared to the existing ones are not very convincing due to the lack of formal, precise statements showing a quantifiable computational advantage over the prior methods (particularly, the authors do not provide precise discussion of the computational cost of the noisy Hessian and the noisy Hessian-vector approximation and also the impact of the approximation on the convergence rate). 

The proposed methods are also of limited novelty as they are natural and obvious  extensions of existing methods in the literature of non-convex optimization. There are also some concerns about the correctness of the claim that $O(d^2)$ running time can be avoided. The argument provided for that claim is not precise and sufficiently detailed. 

The above shortcomings make the work of limited interest. 

justification_for_why_not_higher_score: The paper have several major shortcomings. The largest is that it does not provide any clear improvements over prior work.
Decision: Reject