Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization

We thank the reviewer for their work and are encouraged by their appreciation of our results! We will incorporate the suggested changes and references into the final version.

We are extremely grateful for the reviewer's careful review and for finding numerous typos. We note that the only change incurred by these straightforward fixes (specifically, due to the $\sqrt{B_1}$ in the denominator in Line 286) will be the non-private term in Theorem 3.1 becoming $\sqrt{d}$ times larger, that is $\sqrt{d}/\alpha\beta^3$. We emphasize that this does not affect the main claims in our paper: Our obtained complexity is still $\Omega(\sqrt{d})$ smaller than previous results, and still breaks the erroneous lower bound claimed in previous work. Moreover, neither of our improved empirical/generalization results later in the paper are affected.

We conjecture that the previously claimed dimension-independent bound $O(1/\alpha\beta^3)$ might still be achievable. The $\sqrt{d}$ factor appears to stem from the randomized smoothing technique we employed. With improved smoothing approaches, it may be possible to eliminate this dimension dependence. In the final version we will accommodate the current fix accordingly, explore this conjecture further, and plan to acknowledge the reviewer for their help.

We also appreciate the references suggested by the reviewer. We will add proper citations to Abadi et al. (2016) for the moment account method for privacy composition, as well as to Kulkarni et al. (2021) for their enhancements to the approach.

Regarding the oracle complexity concern, the reviewer is correct that our choice of large $m$ increases the oracle complexity. As noted in Remark 3.3, our parameter choice prioritizes minimizing sample complexity, which comes at the cost of increased oracle calls. In the final version, we will clarify this trade-off more explicitly and discuss potential approaches to balance sample and oracle complexity for different application needs.

We thank the reviewer and are encouraged by the positive review! We clarify the raised issues below:

Regarding the "weakness" mentioned, we want to clarify that we did not assume anything stronger than previous results. In our proof, we use concentration inequalities for sub-Gaussian vectors, but these vectors are actually bounded due to the Lipschitz assumption (a standard assumption in the literature, also used by Zhang et al. (2024)).

We address the Questions below:

(1) We are not aware of a sample complexity lower bound in the non-private literature for finding a Goldstein-stationary point. Regarding oracle complexity, it is known to be $\Theta(1/\alpha\beta^3)$ (see Cutkosky et al., ICML 2023). As pointed out by Reviewer rnQ5, there is a small bug in our analysis that leads to a worse non-private term $O(\sqrt{d}/\alpha\beta^3)$ after fixing the error (primarily by resetting the hyperparameters). Despite this, our result still breaks upon the zero-order oracle lower bound of previous work. The dimension-dependence likely stems from the randomized smoothing technique we employed. We conjecture that the previously claimed dimension-independent bound $O(1/\alpha\beta^3)$ could be achieved, possibly through an improved smoothing technique. Therefore, we cannot currently determine the full extent to which our results might be further improved.

(2) Yes, this is true. As discussed in Remark 3.3, our choice of m aims to minimize the sample complexity, and we will rewrite this to be more clear that this is indeed at the cost of larger oracle complexity in the zero-order case.

(3) The privacy guarantee always holds - the tail event is accounted for in the 'delta' in the $(\epsilon,\delta)$-DP definition, which allows the privacy to break with probability at most $\delta$. As the reviewer correctly guessed, this approach is indeed standard in the DP literature, and we also discuss this in the Discussion section.

We thank the reviewer and are encouraged by the positive review!

We thank the reviewer and are encouraged by the positive review!

Designing optimization algorithms for nonsmooth-nonconvex losses is a topic that gained substantial attention recently mainly due to deep learning applications. Indeed, only few works further provide grounded privacy guarantees when optimizing such losses, as this is a relatively new area of research, yet as the reviewer noted, “Preserving privacy of the data used to train machine learning models is a very important area with broad interest.” Our work aims to bridge this gap and provide foundational algorithms that may be widely applied as privacy-preserving machine learning continues to grow in importance.