Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization

We thank the reviewer for their time, for appreciating the strengths of our work, and appreciate their constructive efforts in helping us strengthen it.

We address the raised questions:

1. It is currently not known whether the result of this paper is tight, due to lacking lower bounds in the private regime. The non-private term is indeed optimal (as indicated by the lower bound by Cutkosky et al.), whereas the exact private terms are not even known in the well-studied smooth nonconvex case.

2. As we discuss in the paper, we identify several challenges in order to improve previous results. The first of which is to decrease the sensitivity of the gradients estimator which allows adding less noise in order to privatize. Moreover, we then also further improve the results by utilizing the empirical objective for which we derive tighter guarantees, and prove that these also generalize to the population, which no previous work has done in this context. We further discuss these in the top common comment.

3. Goldstein-stationarity has recently emerged as a popular framework for designing and analyzing optimization algorithms for nonsmooth nonconvex objectives, which is an important regime in modern deep learning applications. The reason for this is that function-value minimization as well as stationarity are impossible to efficiently achieve in the non-smooth non-convex setting, and Goldstein stationarity is the strongest known optimality condition that can be efficiently achieved. While many works studied this notion without privacy, only one previous paper studied this notion in the private setting. In our paper, we substantially improve upon these previous results, and along the way develop techniques (e.g., generalization of Goldstein-stationary points) that may find uses beyond private optimization.

4. As pointed out throughout the paper (and also acknowledged by the reviewer, e.g. strengths #3 and #5), there are several novel aspects in our analysis that allow us to derive significantly better results than previous works on this subject. These include reducing the sensitivity of the gradient estimator, and also generalizing from the empirical loss to the population loss. Please note the top common comment for further discussion.

5. In private stochastic optimization, the sample complexity consists of terms that depend on the privacy parameters, and terms that are independent of them (referred to as “non-private” terms). We significantly improve both terms in our work, and emphasize that the non-private term we get is even better than previously thought to be possible (and in particular, optimal).

Given that the reviewer acknowledges the significant contributions of our work, we kindly ask them to consider reevaluating their rating in light of these clarifications. We hope we have been able to address the raised questions, and please let us know in case of any additional questions or feedback.

We thank the reviewer for their time, and appreciate their constructive efforts in helping us strengthen our work.

We have attempted to address the novelty concerns in the common response above. Below we address the other questions raised by the reviewer:

1,2.: Thank you for pointing out the typos in the tree mechanism section, we appreciate the reviewer’s detailed review. The condition in Algorithm 1 should indeed be $k' \leq t$, and the expression in the fourth line of Proposition 2.5 should be $\sum_{j=1}^i M_j$. We have corrected these errors in the revised version.

The tree mechanism approach ensures that the algorithm maintains strong differential privacy guarantees while minimizing the error introduced by noise. It has become a standard tool in differential privacy and in private optimization, and further details can be found in lecture notes and textbooks. To clarify the tree mechanism, we provide a brief and non-technical explanation:

Suppose we are given a sequence of real numbers $X_1, X_2, \ldots, X_n$, where each $X_i$ lies in $[0, 1]$, and we aim to compute the cumulative sums $\sum_{j=1}^i X_j$ for all $i \in [n]$ while preserving differential privacy.

A naive approach would add independent Gaussian noise to each $X_i$, but this results in an error proportional to $\sqrt{n}$, which grows poorly with $n$. The binary tree mechanism improves on this by organizing the computations into a hierarchical structure:

• Binary Tree Construction: We construct a complete binary tree with $n$ leaves, where each leaf corresponds to one $X_i$. Each internal node of the tree represents the sum of the values of its descendant nodes. For instance: A node spanning the range $(u, v)$ represents $\sum_{j=u}^v X_j$; Its left child spans $(u, m)$, and its right child spans $(m+1, v)$, where $m$ is the midpoint of $[u, v]$.

• Adding Independent Noise: To privatize the sums, independent Gaussian noise is added to the output of every node in the tree. This means that, for any node spanning a range $(u, v)$, the privatized sum is: $\text{PrivSum}(u, v) = \sum_{j=u}^v X_j + N_{u,v},$ where $N_{u,v}$ is Gaussian noise with an appropriate scale determined by the privacy parameters.

• Querying Cumulative Sums: To compute any cumulative sum $\sum_{j=1}^i X_j$, the mechanism selects at most $\log n$ nodes from the tree whose ranges cover $[1, i]$. The noisy outputs from these nodes are combined to produce the privatized result. This hierarchical structure ensures that the total error scales with $O(\log^2 n)$, which is significantly smaller than $\sqrt{n}$ for large $n$.

• Role of $\text{NODE}(t)$: In Algorithm 1, the function $\text{NODE}(t)$ determines the set of nodes needed to cover the range $[1, t]$ in the tree in a greedy way. These nodes are then used to determine which Gaussians should be added to compute the privatized sum.

We hope this explanation clarifies the tree mechanism and its implementation. Please let us know if you have additional questions or feedback.

3. These are precisely the same update rules in disguise, since the authors therein “subtract” the update whereas we “add” it, so they are defined as negations. In detail, in remark 10 therein, they query the gradient at $z_n:=x_n+(s_n-1)\Delta_n$, and since $s_n\sim[0,1]$, it holds that $(s_n-1)\sim[-1,0]$, or in other words $z_n=x_n-s’_n\Delta_n$ where $s’_n\sim[0,1]$.

4. This is true. We therefore complement our results by a first-order algorithm (in Appendix C) with a substantially reduced oracle complexity which avoids this blow-up - see Remark C.5, and also our top-comment for further discussion.

We kindly ask the reviewer to consider reevaluating the rating in light of these corrections and clarifications, as they address the key concerns they raised.

We thank the reviewer for their time and effort, and are encouraged by their appreciation of our contribution.

Regarding the question the reviewer raised: In the ERM setting, we re-use samples, and therefore must use privacy composition theorems in order to argue about the privacy of the overall algorithm. Since Gaussian composition guarantees are simpler to apply than their counterparts for the tree mechanism, we choose to use the Gaussian mechanism to avoid further unnecessary complications. We thank the reviewer for raising this question, and we will clarify this in the revised version.

We thank the reviewer for their time and effort, and are encouraged by their appreciation of our contribution and presentation.

We also thank the reviewer for their questions, and we will modify writing to better explain the points they have raised. We address them as follows:

1. Indeed, while the single-pass algorithm uses each datapoint $\xi_i$ once throughout its run, in each step it queries $m$ oracle calls in order to stabilize the response (hence reducing sensitivity), as seen for example in line 6 of Algorithm 3. In other words, the oracle complexity is m times the sample complexity, and hence it does not “break” known lower bounds.

2. Yes, this is a good point: the O2NC itself is optimal, as it is matched by a (non-private) lower bound, as discussed in the original paper by Cutkosky, Mehta and Orbaona. The difficulty in having a matching lower bound lies in the private regime, for which even in the more well-studied smooth non-convex case there are currently gaps between known upper and lower bounds.