Adaptive Batch Size for Privately Finding Second-Order Stationary Points

Thank you for your valuable feedback and thoughtful comments. Below are our responses to your points and questions:

1. On Structure and Flow: We acknowledge that the structure and flow of the paper could be improved. We will add more discussions to provide intuition for the technical lemmas and ensure the paper feels more cohesive and easier to follow.

2. On Empirical Evaluations: While the primary focus of this work is on theoretical improvements, an empirical evaluation would provide additional insights. We believe that comparing our approach to existing algorithms in the literature could make for a valuable separate project.

3. On Notations: Thank you for pointing out the potential ambiguity in the notations $\mathcal{O}_1$ and $\mathcal{O}_2$​. We will consider revising the notation to reduce confusion.

4. Assumptions in the Work: Our assumptions (e.g., Lipschitz, smoothness, and Hessian Lipschitz conditions) are standard in the literature and align with those used in related works.

5. On Sample Complexity and Data Sharing (Question 3): This is an excellent question. Sharing data across the outer loops while maintaining unbiased gradients poses challenges, as reusing data points could introduce dependencies. As a result, the gradient estimates may no longer be unbiased. A naive generalization bound in a bounded domain is $O(\sqrt{d/n})$, as discussed in Appendix A.2. We currently do not have a satisfactory solution for addressing this issue but agree that it is an important direction for future investigation. This may improve the bound for finding SOSP of population function.

Thank you for taking the time to review our work and for your detailed feedback. Below, we address your questions and comments:

1. Regarding the Matrix Mechanism: Within our algorithm framework, improvements over the binary tree mechanism primarily affect constants but will not affect the asymptotics. However, discussing the potential use of the matrix mechanism and its advantages would be valuable, and we will include such discussions in the revised version.

2. On the privacy of $\tilde{\Delta}_t$: The binary tree mechanism privates $\tilde{\Delta}_t$. Consequently, $b_t$ (specified in Line 369) is also private due to the postprocessing property of differential privacy.

3. On Notation and Norms: As noted In line 164, we use $\|\cdot\|$ to represent the $\ell_2$ norm of a vector and the operator norm of a matrix. To improve clarity, we will expand the explanations of notations in the revised version and consider including a table of notation for better readability.

Thank you for your response and for acknowledging the clarifications. If you have any further questions or concerns, please don’t hesitate to reach out—we’d be happy to address them.

Additionally, if our clarifications have adequately addressed your concerns, we kindly request you to consider revisiting the score, as it would greatly help us in the review process.

Thank you again for your valuable time and feedback!

Thank you for your positive feedback and for pointing out the related work that needs to be included. They are primarily about finding first-order stationary points; we will add them to the updated version.

Thank you for your valuable feedback. While we aim to present a self-contained theoretical paper in this submission, empirical comparisons with existing algorithms in the literature would be an interesting direction for future work.

Below, we address your questions:

1. For FOSP, the current lower bound we know is $\Omega(\sqrt(d)/n\epsilon)$ for privately finding FOSP of the empirical function, a result derived from private mean estimation (and applicable to SOSP as well). The non-private term $O(1/n^{1/3})$ is only known to be tight in the high-dimension case (as we discussed around Line 85). Closing these gaps for both FOSP and SOSP remains an open and intriguing research direction.
2. If we query oracle_1 every time, the tree mechanism offers no advantage, and the approach effectively reduces back to the DP-SGD combined with the Gaussian mechanism. Even in non-private settings, variance-reduction-based algorithms generally outperform standard SGD (in terms of theoretical convergence rate). Lemma 3.6 provides some intuition for leveraging oracle_2: querying oracle_1 alone leads to an error proportional to $\sum_i ||x_i-x_{i-1}||$, whereas incorporating oracle_2 for variance reduction makes the error proportional to $\sqrt{\sum_i ||x_i-x_{i-1}||^2}$. This allows us to use a larger batch size each time we query oracle_1, significantly reducing the variance and error of the gradient estimators.
3. We are considering the regime where $\sqrt(d)/n\epsilon<< O(1)$, ensuring that the bounds remain non-trivial (as under the Lipschitz assumption, any point can be an O(1)-SOSP). In this regime, we always have $(\sqrt{d}/n\epsilon)^{1/2}<< (\sqrt{d}/n\epsilon)^{3/7}$. When we state that $\epsilon$ is "sufficiently small," we refer to cases where the private term dominates the non-private term $n^{-1/3}$. We will clarify this in the revised version.