Private Zeroth-Order Nonsmooth Nonconvex Optimization

We thank the reviewer for the careful reading and supportive rating. We also thank the reviewer for all the constructive comments, and we will address each comment accordingly in the future version. Below we address the reviewer’s questions.

Q1.

As the reviewer pointed out, the definition of Goldstein stationary point implies the inequality $\\| \nabla h(x)\\|\_\delta \le \inf \\| \frac{1}{|S|}\sum_{y\in S} \nabla h(y)\\|$, but the converse is not necessarily true. In this sense, the word “Equivalently” should rather be “Consequently”. We apologize for the confusion caused by the mistake, and we will correct the wording.

Q2.

First, we would like to quote Lin et. al. [1] Theorem 3.1: $\nabla \hat F_\delta(x) \in \partial_\delta F(x)$.

By the definition that $\partial_\delta F(x) = \text{conv}(\cup_{y\in B(x,\delta)} \nabla F(y))$, any $g\in \partial_\delta \hat F_\delta(x)$ has form $g=\sum \lambda_i \hat \nabla F_\delta(y_i)$ where $\lambda_i$’s are convex coefficients and $y_i\in B(x,\delta)$. By the quoted Thm. 3.1, $\nabla \hat F_\delta(y_i) \in \partial_\delta F(y_i) \subseteq \partial_{2\delta} F(x)$ since $\\|x-y_i\\| \le \delta$. This further implies that $g \in \partial_{2\delta} F(x)$ for any $g\in \partial_\delta \hat F_\delta(x)$, and thus $\partial_\delta \hat F_\delta(x) \subseteq \partial_{2\delta} F(x)$. Consequently, $\\| \nabla F(x) \\|\_{2\delta} := \inf \\{ \\|g\\| : g\in \partial_{2\delta} F(x)\\} \le \inf \\{ \\|g\\| : g\in \partial_\delta \hat F_\delta(x)\\} := \\| \nabla \hat F_\delta(x) \\|_\delta$, and this proves Corollary 2.3.

We realize this proof is not “immediately” from Lemma 2.2. We will address the wording for clarity and will include a formal proof of Cor. 2.3 in the future version.

Last comment

We would like to clarify that the proof after Corollary 4.4 is the proof of Cor. 4.4 itself, while the proof of Theorem 4.3 is deferred to Appendix C due to space limit. We apologize for the confusion, and we will clarify this in the future version.

Q5. convergence bound in terms of data size $M$

In the proof of Theorem 4.9, we showed that $\mathbb{E} \\|\nabla F(\overline w)\\|_{2\delta} \lesssim (d/\delta M)^{1/3} + (d/M)^{1/3} + (d^{3/2}/\rho\delta M)^{1/2} + (d^{3/2}/\rho M)^{1/2}$. Here $\rho$ denotes the DP parameter (corresponding to $\epsilon$ in $(\epsilon,\delta)$-DP) and the symbol $\lesssim$ hides dependence on constants $F^*, L$ and logarithmic factors. In the future version, we will include this convergence bound w.r.t. $M$ in the main theorem.

Q5. multi-epoch training

We want to clarify that our paper primarily addresses the stochastic optimization (SO) problem, which seeks to optimize the expected loss $\mathbb{E}[f(x,z)]$. In contrast, multi-epoch training pertains to the empirical risk minimization (ERM) problem, aiming to optimize the finite-sum loss $\frac{1}{n}\sum_{i=1}^n f(x,z_i)$. It is important to recognize that ERM, while of significant interest, represents a distinct topic. Moreover, prior works have indicated that SO and ERM problems exhibit differing convergence bounds [1].

References

[1] Arora, R., Bassily, R., González, T., Guzmán, C., Menart, M., and Ullah, E., “Faster Rates of Convergence to Stationary Points in Differentially Private Optimization”, arXiv e-prints, 2022. doi:10.48550/arXiv.2206.00846.

We thank the reviewer for detailed reading and comments. We address the questions and comments below.

Q3. discussion about $\delta$ and Online-to-nonconvex updates

We would like to clarify that our result does not have any implicit limitation on the range of $\delta$. Note that O2NC (Algorithm 3) has two loops: $K$ outer loops and $T$ inner loops for a total of $N=KT$ iterations. It is true that for each $T$ inner iterations, $x$ can move a distance up to $\delta$, i.e., $\\|x_1^k - x_{T+1}^k\\| \le \delta$. However, since there are $K$ such outer loops, the total distance between the last-iterate and the initial point is $\\|x_1^1 - x_{T+1}^K\\| \le K\delta$. As shown in Theorem 4.9, the optimal tuning of $K$ is approximately $N^{1/3}/d^{1/3}\delta^{2/3}$, which yields an upper bound of $K\delta = O((\delta N/d)^{1/3})$ instead of $O(\delta)$. We hope this clarifies the reviewer’s misunderstanding.

Q2. computation complexity

The computation complexity of our algorithm is $O(dM)$ function evaluations, where $d$ is the dimension and $M$ is the data size. We admit that the computation complexity of our algorithm is $d$ times greater than first-order algorithms. However, we would like to point out that in practice, function evaluations can be much cheaper than gradient computations. Moreover, the task of computing $d$ i.i.d. function evaluations per data point can be further accelerated by parallelization.

Q2. GRAD and DIFF estimators

We agree with the reviewer that it’s not necessary for the GRAD estimator to sample $d$ uniform vectors. Using the two-point estimator and following the previous result in (Shamir 2017) Lemma 10, we will achieve the same linear dimension dependence.

For the DIFF estimator, our analysis technique does not require two-point estimators, as they would not enhance the dimension dependence of DIFF's variance. We provide a detailed discussion on the design of GRAD and DIFF in the last two paragraphs of Section 3.

Q3. assumption that $f(x,z)$ is differentiable

We agree that assuming $f$ is differentiable is not required. For non-differentiable $f$, the online-to-non-convex algorithm (Cutkosky et. al. 2023) adds a small perturbation to $f$, achieving the same convergence guarantee. In our paper, we assumed differentiability to avoid this additional perturbation and thus simplify the presentation. Very likely in our setting even this perturbation is unnecessary (since we already perturb the loss).. We will add a discussion about differentiability in the future version.

Q4. presentation of Remark 4.2 and Theorem 4.3

To clarify Remark 4.2 and Theorem 4.3, we would like to first reference our notation for binary trees detailed in Appendix C, which was deferred due to space limit. A node in a binary tree is denoted by the tuple $(i,j)$, where $i$ is the leftmost leaf child and $j$ is the rightmost leaf child. We agree that in the practical implementation of NODE, the first index in the tuple is not required for summation. However, this tuple notation greatly simplifies the proof of Theorem 4.3.

Furthermore, we would like to provide a more detailed explanation of the function $\text{NODE}(t)$. Consider a complete binary tree of $k=\lceil \log_2 t\rceil$ layers, with the root layer labeled as layer 0 and the leaf layer labeled as layer $k$. Starting from layer 0 which only contains the root node $(1,2^k)$, the root node is stored if $2^k\le t$, represented by the right index $n_0=2^k$. Otherwise, no node is stored in layer 0 and $n_0$ is set to $\varnothing$. In each subsequent layer $i$, a node with right index $n_i$ is stored if $n_i \le t$ and $n_i > n_j$ for all $j<i$. Specifically, at most one node is stored per layer, which explains why NODE(7) returns 3 nodes while NODE(8) only returns 1 node. The central message of Remark 4.2 is the inequality $|\text{NODE}(t)| \le \lceil \log_2 t\rceil$.

For Theorem 4.3, $\mathcal{S}^{(i)}$ is a typo; it should instead be $\mathcal{X}$, representing the state space, i.e., the set of all parameters $x$ for $f(x,z)$ in our case. Here $\mathcal{X}^i$ denotes the Cartesian product of $\mathcal{X}$.

We apologize for the confusion caused by our presentation, and we will improve the presentation with more clarity in the future version.

continues in the next thread...

We thank the reviewer for their detailed reading and comments. We address the comments and questions below.

Q2. sampling $d$ estimators per data point

The requirement of $d$ i.i.d. function evaluations per data point stems from the limit of our analysis technique in order to reduce the variance by a factor of $d$ and achieve the optimal dimension dependence. Exploring whether alternative methods can achieve the same dimension dependence without requiring $d$ function evaluations per data point, or showing the necessity of this requirement, remains an interesting open question. That said, we emphasize that these $d$ function evaluations are using the same sample, and so do not require more data samples.

DP mechanisms in previous DP optimization algorithms

We thank the reviewer's constructive suggestion and will expand the discussion on DP mechanisms in the related works section. Here's a brief overview:

DP guarantees in gradient-based optimization are typically achieved by adding Gaussian noise to stochastic gradients and then applying a non-DP algorithm. The noise variance depends on the sensitivity of these gradients, thus making the design of low-sensitivity gradient estimators a key focus in our paper. In Appendix E, we show that applying this approach to our setting results in significantly worse bounds. More advanced approaches in the literature use private amplification mechanisms to reduce noise levels while maintaining DP guarantees. These methods include amplification by subsampling [1], iteration [2], and shuffling [3], and are commonly applied in DP optimization algorithms to achieve better privacy guarantees. Particularly, the tree mechanism that we use is also one of those mechanisms for privately summing a sequence of updates [4].

For illustration, DP-SGD [5] adds Gaussian noise to stochastic gradients of standard SGD and utilizes subsampling for amplification. Private SpiderBoost [6], building on the non-private SpiderBoost, employs the tree mechanism for noise reduction.

Q1.

In Section 1.1, we intended to indicate that our rate matches the state-of-the-art, as demonstrated by Kornowski and Shamir (2023), and that the non-private component of the bound matches the optimal rate in terms of $\epsilon$ and $\delta$.. We'll revise our wording for clarity.

Regarding the lower bound for zeroth-order non-smooth non-convex optimization, no formal proof exists for $\Omega(d\delta^{-1}\epsilon^{-3})$ to our knowledge. However, Cutkosky et. al. (2023) proved a $\delta^{-1}\epsilon^{-3}$ lower bound for first-order non-smooth non-convex problems, suggesting our algorithm is optimal in terms of $\delta,\epsilon$. Moreover, Duchi et. al. (2013) showed a $d\epsilon^{-2}$ lower bound for the zeroth-order convex and smooth problem with one function evaluation per iteration. This finding suggests that the lower bound of the zeroth-order non-smooth, non-convex problem is likely to exhibit some dimension dependence.

References

[1] Bassily, R., Smith, A., and Thakurta, A., “Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds”, arXiv e-prints, 2014. doi:10.48550/arXiv.1405.7085.

[2] Feldman, V., Mironov, I., Talwar, K., and Thakurta, A., “Privacy Amplification by Iteration”, arXiv e-prints, 2018. doi:10.48550/arXiv.1808.06651.

[3] Erlingsson, Ú., Feldman, V., Mironov, I., Raghunathan, A., Talwar, K., and Thakurta, A., “Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity”, arXiv e-prints, 2018. doi:10.48550/arXiv.1811.12469.

[4] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. 2010. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing (STOC '10). Association for Computing Machinery, New York, NY, USA, 715–724. https://doi.org/10.1145/1806689.1806787

[5] Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., Zhang, L., “Deep Learning with Differential Privacy”, arXiv e-prints, 2016. doi:10.48550/arXiv.1607.00133.

[6] Arora, R., Bassily, R., González, T., Guzmán, C., Menart, M., and Ullah, E., “Faster Rates of Convergence to Stationary Points in Differentially Private Optimization”, arXiv e-prints, 2022. doi:10.48550/arXiv.2206.00846.

[7] Kornowski, G. and Shamir, O., “An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization”, arXiv e-prints, 2023. doi:10.48550/arXiv.2307.04504.

[8] Cutkosky, A., Mehta, H., and Orabona, F., “Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion”, arXiv e-prints, 2023. doi:10.48550/arXiv.2302.03775.

[9] Duchi, J. C., Jordan, M. I., Wainwright, M. J., and Wibisono, A., “Optimal rates for zero-order convex optimization: the power of two function evaluations”, arXiv e-prints, 2013. doi:10.48550/arXiv.1312.2139.

We thank the reviewer for their detailed reading and comments. We address the comments below, and we are glad to answer any future questions.

We agree with the reviewer that our algorithm builds on the non-private online-to-non-convex (O2NC) conversion. However, adapting O2NC for privacy involves several complex techniques, such as creating low-sensitivity zeroth-order estimators and using the tree mechanism to reduce noise. Even these need some finesse to be used in our setting - as evidenced by our use of multiple function evaluations to reduce variance in the gradient difference estimator. The technical novelty in our work lies in developing the insights needed to combine these techniques to achieve a private algorithm. Moreover, we would also like to emphasize that our research is the first to solve the zeroth-order non-smooth, non-convex optimization problem with differential privacy.