Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks

Summary

This paper provides a private algorithm for (Stochastic) Non-Convex Optimization using gradients, differences between two successive gradients, and the exponential mechanism for privacy (added to the gradient). It leverages the SpiderBoost algorithm and its private version to find (privately) stationary points. The main challenge addressed by the paper is to keep the quality of the gradient estimations at all steps.

Strengths

- simple modification of SpiderBoost to maintain the quality of the gradient estimations. - interesting properties of the algorithm, i.e., the algorithm is capable of escaping the saddle point with high probability, and a large drift implies significant decrease in the function value, limiting the number of gradient queries.

Weaknesses

- there is something weird about Algorithm 1. drift_t is set to zero in lines 7 and 10, but then overwritten in line 14.

Questions

See above

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

- traditional hypotheses on these types of results

Summary

This paper addresses the problem of private stochastic optimization for general non-convex functions. For smoothed functions, the authors propose a combination of the Gaussian mechanism and the variance reduction technique (spider algorithm) to find the SOSP of the loss function. Their results for the empirical risk improve upon previous state-of-the-art bounds by a factor of $n\varepsilon$ and their results for the population risk are new in the field of private optimization literature. For general Lipschitz non-convex problems, the authors establish improved bounds for bounding the excess risk using exponential mechanisms. Notably, they provide a new exponentially-time algorithm that matches the proposed lower bound.

Strengths

The paper is well-written and clear in its claims. The authors propose a novel approach to private stochastic optimization for both smooth and non-convex loss functions by combining existing private mechanisms with the Spider algorithm. They provide new results for both upper and lower bounds on the excess population risk, which are technically solid and contribute to the literature on private stochastic optimization. Overall, the results presented in the paper make a valuable contribution to the field.

Weaknesses

1. The paper makes a significant contribution to improving the bounds for private optimization, but there is still a gap between the existing upper and lower bounds that needs to be explored in future work. 2. While the paper focuses on theoretical studies, the authors could consider conducting experimental studies to validate their theoretical findings

Questions

I have no further questions.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Yes

Summary

The paper introduces a non-convex optimization framework that integrates two types of gradient oracle and an application of the exponential mechanism to find the global minima of non-convex objectives, requiring minimal assumptions and showcasing remarkable population risk bound performance. The paper also highlights the ability to emulate previous empirical and population risk bounds effectively, removing the necessity for smoothness assumptions.

Strengths

This paper presents robust, theoretical insights into a clearly defined problem, and its logical flow makes it accessible and easy to comprehend. It commendably surveys and incorporates existing related literature.

Weaknesses

This paper appears to conclude abruptly, with the discourse ending unexpectedly following a theorem. The absence of a conclusion or summary weakens the paper's overall structure. There is an absence of numerical experiments. Additionally, the authors seem to have relied solely on Advanced Composition for privacy accounting. There are, however, various alternative privacy accounting methods available that could potentially improve the overall performance. For instance, the 'Better Privacy Accounting' method [1], utilization of GDP [2], or the application of tighter composition theorems [3] might be considered for future research and improvements. [1]: Altschuler, J., & Talwar, K. (2022). Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. Advances in Neural Information Processing Systems, 35, 3788-3800. [2] Liu, Y., Sun, K., Jiang, B., & Kong, L. (2022). Identification, amplification and measurement: A bridge to gaussian differential privacy. Advances in Neural Information Processing Systems, 35, 11410-11422. [3] Kairouz, P., Oh, S., & Viswanath, P. (2015, June). The composition theorem for differential privacy. In International conference on machine learning (pp. 1376-1385). PMLR.

Questions

How does the performance of the Stochastic Spider, as presented in this paper, compare to that of the BoostSpider in practical applications? While the theoretical results indicate a rate improvement, is this enhancement accompanied by an increase in constants and an impact on finite sample performances?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

See weaknesses.

Summary

This paper studies differentially private second-order optimization problems, where the loss function is assumed to be second-order smooth. The objective is to identify second-order stationary points (SOSP) while ensuring privacy guarantees. The authors present results for both empirical risk and population risk, with notable advancements over existing state-of-the-art outcomes. Specifically, the empirical risk minimization (ERM) bound improves from the state-of-art rate, while the population risk result stands as the first of its kind in the literature on differentially private SOSP optimization. Furthermore, the paper contributes a lower bound analysis for private SOSP optimization, further strengthening its significance in this domain.

Strengths

The strength of this paper lies in its highly comprehensive study of private second-order optimization. The authors study both empirical risk minimization and population risk, and the obtained bounds improves from the state-of-the-art results in both case. The inclusion of a lower bound also closes the gap of this problem.

Weaknesses

The authors can enhance the writing by providing additional discussion regarding the algorithm employed, the obtained results, and the insights derived from their findings. Furthermore, providing more detailed explanations for the technical results cited from previous works, such as Lemma 3.4 and Alg.2, would help clarify any confusion and prevent ambiguity.

Questions

I have a few questions regarding the general SOSP framework (Algorithm 1): - What role does $\text{frozen}_t$ play? - line 8: why is an additional noise $g_t$ added to the private oracle $\mathcal{O}_1(x_t)$? - Since Alg. 1 only serves as a non-private SOSP optimization framework, is it possible to choose other variance-reduction algorithms (e.g., [1])? If not, what is the key characteristic that distinguishes SpiderBoost from other optimizers in the private setting? Also, Section 5 focuses on private excess risk minimization, which seems to deviate from the previous discussion about SOSP. I'm wondering how Sec. 5 relates to the previous part of the paper? Reference: 1. Ashok Cutkosky, Francesco Orabona. Momentum-Based Variance Reduction in Non-Convex SGD.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

N/A

Summary

The paper studies the problem of non-convex optimization under differential privacy constraints. The goal of the paper is to find first and second order stationary points of the function. The proposed algorithm which is inspired by SpiderBoost [1] is a sampling based method that generates a private estimator that minimizes both excess empirical and population risks.  The authors studied the cases: when only polynomial run time is allowed, and when the exponential run time is permitted. In the first case, their proposed algorithm outperforms the previous best and tightens the gap between the provided upper bound and the already existing lower bound. For the case when exponential run time is allowed, the paper provides a nearly matching upper and lower bound.  [1] Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. Advances in Neural Information Processing Systems, 32, 2019.

Strengths

The paper is a collection of elegant results. From a technical point of view, the paper is solid. It enhances advanced techniques to fulfill its objective. While the paper outperforms previous best algorithm [2], with polynomial run time it relaxes the smoothness assumption that has been assumed in [2].  [2] Di Wang, Changyou Chen, and Jinhui Xu. Differentially private empirical risk minimization with non-convex loss functions. In International Conference on Machine Learning, pages 6526–6535. PMLR, 2019.

Weaknesses

For a reader who is not fluent with the literature, the paper is not easy to follow. Several insights left to be unexplained. The paper is quite dense without enough provided intuition on the proposed algorithm. The authors did a good job in mentioning the similarities with precious work, but they did not discuss their technical novelties. Some expressions and notation are left undefined (ex. W_2 at line 308).  As a side note, I think P at line 18 should be P*.

Questions

1. What is the main technical novelty of the work? 2. Is the proposed algorithm a privatized version of SpiderBoost? if yes, except the added gaussian noise what are the additional elements that are added? And can one similarly construct a privatized version of other algorithms like Spider or SARAH? 3. Can you please provide an intuition that why your technique could relax the smoothness assumption? 4. Except the relaxed smoothness assumption, can you please provide an intuition what would be the difference in the perfromance if one used Spider or SARAH instead of SpiderBoost?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The limitation of the work is the optimality gap between the upper and lower bound, where the authors mentioned this and referred to it as an open problem.