Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization

## Abstract

Abstract We study differentially private (DP) optimization algorithms for stochastic and empirical
objectives which are neither smooth nor convex, and propose methods that return a Goldstein-stationary point with sample complexity bounds that improve on existing works.
We start by providing a single-pass ( ε , δ ) 𝜀 𝛿 (\varepsilon,\delta) ( italic_ε , italic_δ ) -DP algorithm that
returns an ( α , β ) 𝛼 𝛽 (\alpha,\beta) ( italic_α , italic_β ) -stationary point as long as the dataset is of size Ω ~ ⁢ ( 1 / α ⁢ β 3 + d / ε ⁢ α ⁢ β 2 + d 3 / 4 / ε 1 / 2 ⁢ α ⁢ β 5 / 2 ) ~ Ω 1 𝛼 superscript 𝛽 3 𝑑 𝜀 𝛼 superscript 𝛽 2 superscript 𝑑 3 4 superscript 𝜀 1 2 𝛼 superscript 𝛽 5 2 \widetilde{\Omega}\left(1/\alpha\beta^{3}+d/\varepsilon\alpha\beta^{2}+d^{3/4}%
/\varepsilon^{1/2}\alpha\beta^{5/2}\right) over~ start_ARG roman_Ω end_ARG ( 1 / italic_α italic_β start_POSTSUPERSCRIPT 3 end_POSTSUPERSCRIPT + italic_d / italic_ε italic_α italic_β start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT + italic_d start_POSTSUPERSCRIPT 3 / 4 end_POSTSUPERSCRIPT / italic_ε start_POSTSUPERSCRIPT 1 / 2 end_POSTSUPERSCRIPT italic_α italic_β start_POSTSUPERSCRIPT 5 / 2 end_POSTSUPERSCRIPT ) ,
which is Ω ⁢ ( d ) Ω 𝑑 \Omega(\sqrt{d}) roman_Ω ( square-root start_ARG italic_d end_ARG ) times smaller than the algorithm of Zhang et al. ( 2024 ) for this task,
where d 𝑑 d italic_d is the dimension.
We then provide a multi-pass polynomial time algorithm which further improves the sample complexity to Ω ~ ⁢ ( d / β 2 + d 3 / 4 / ε ⁢ α 1 / 2 ⁢ β 3 / 2 ) ~ Ω 𝑑 superscript 𝛽 2 superscript 𝑑 3 4 𝜀 superscript 𝛼 1 2 superscript 𝛽 3 2 \widetilde{\Omega}\left(d/\beta^{2}+d^{3/4}/\varepsilon\alpha^{1/2}\beta^{3/2}\right) over~ start_ARG roman_Ω end_ARG ( italic_d / italic_β start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT + italic_d start_POSTSUPERSCRIPT 3 / 4 end_POSTSUPERSCRIPT / italic_ε italic_α start_POSTSUPERSCRIPT 1 / 2 end_POSTSUPERSCRIPT italic_β start_POSTSUPERSCRIPT 3 / 2 end_POSTSUPERSCRIPT ) ,
by designing a sample efficient ERM algorithm,
and proving that Goldstein-stationary points generalize from the empirical loss to the population loss.

## 1 Introduction

We consider optimization problems in which the loss function is stochastic or empirical, of the form

$$ $\displaystyle F(x)$ $\displaystyle:=\operatorname*{\mathbb{E}}_{\xi\sim\mathcal{P}}\left[f(x;\xi) \right],\text{~{}~{}~{}~{}~{}~{}~{}(stochastic)}$ $\displaystyle\widehat{F}^{\mathcal{D}}(x)$ $\displaystyle:=\frac{1}{n}\sum_{i=1}^{n}f(x;\xi_{i}),\text{~{}~{}~{}~{}~{}~{}~ {}~{}~{}(ERM)}$ $$

where $\mathcal{P}$ is the population distribution from which we sample a dataset $\mathcal{D}=(\xi_{1},\dots,\xi_{n})\sim\mathcal{P}^{n}$,
and the component functions $f(\,\cdot\,;\xi):\mathbb{R}^{d}\to\mathbb{R}$
may be neither smooth nor convex.
Such problems are ubiquitous throughout machine learning, where
losses given by deep-learning based models give rise to highly nonsmooth nonconvex (NSNC) landscapes.

Due to its fundamental importance in modern machine learning, the field of nonconvex optimization has received substantial attention in recent years.
Moving away from the classical regime of convex optimization, many works aimed at understanding the complexity of producing approximate-stationary points, namely with small gradient norm
(Ghadimi and Lan, ; Fang et al., ; Carmon et al., ; Arjevani et al., ). As it turns out, without smoothness, it is impossible to directly minimize the gradient norm without suffering from an exponential-dimension dependent runtime in the worst case (Kornowski and Shamir, ). Nonetheless,
a nuanced notion coined as Goldstein-stationarity (Goldstein, ), has been shown in recent years to enable favorable guarantees.
Roughly speaking, a point $x\in\mathbb{R}^{d}$ is called an $(\alpha,\beta)$-Goldstein stationary point (or simply $(\alpha,\beta)$-stationary) if there exists a convex combination of gradients in the $\alpha$-ball around $x$ whose norm is at most $\beta$.(^1^11Previous works typically use the notational convention $(\delta,\varepsilon)$-stationarity instead of $(\alpha,\beta)$, namely where $\delta$ is the radius (instead of $\alpha$) and $\varepsilon$ is the norm bound (instead of $\beta$). We depart from this notational convention in order to avoid confusion with the standard privacy notation of $(\varepsilon,\delta)$-DP.)
Following the groundbreaking work of Zhang et al. (),
a surge of works study NSNC optimization through the lens of Goldstein stationarity, with associated finite-time guarantees
(Davis et al., ; Lin et al., ; Cutkosky et al., ; Jordan et al., ; Kong and Lewis, ; Grimmer and Jia, ; Kornowski and Shamir, ; Tian and So, ).

In this work, we study NSNC optimization problems under the additional constraint of differential privacy (DP) (Dwork et al., ).
With the ever-growing deployment of ML models
in various domains, the privacy of the data on which models are trained is a major concern.
Accordingly, DP optimization is an extremely well-studied problem, with a vast literature focusing on functions that are assumed to be either convex or smooth (Bassily et al., ; Wang et al., ; Bassily et al., ; Wang et al., ; Feldman et al., ; Gopi et al., ; Arora et al., ; Carmon et al., ; Liu et al., ). The fundamental investigation in this literature is the privacy-utility trade-off, that is, assessing the minimal dataset size $n$ (referred to as the sample complexity) required in order to optimize the loss up to some error, using a DP algorithm.

For NSNC DP optimization, Zhang et al. () recently provided a zero-order algorithm,
namely that utilizes only function value evaluations of $f(\,\cdot\,;\xi)$,
which preforms a single pass over the dataset
and returns an $(\alpha,\beta)$-stationary point of $F$
under $(\varepsilon,\delta)$-DP as long as

$$ $n=\widetilde{\Omega}\left(\frac{d}{\alpha\beta^{3}}+\frac{d^{3/2}}{\varepsilon \alpha\beta^{2}}\right).$ (1) $$

To the best of our knowledge this is the only existing result in this realm.

### 1.1 Our contributions

In this paper, we provide new algorithms for NSNC DP optimization,
which
improve the previously best-known sample complexity for this task.
For consistency with the previous result by Zhang et al. (), our algorithms will be zero-order, yet in Appendix B we provide first-order algorithms
(i.e., gradient-based)
with the same sample complexities, and better oracle complexity.
Our contributions, summarized in Table 1, are as follows:

- 1.
Improved single-pass algorithm (Theorem 3.1):
We provide an $(\varepsilon,\delta)$-DP algorithm that
preforms a single pass over that dataset, and returns an $(\alpha,\beta)$-stationary point as long as
$n=\widetilde{\Omega}\left(\frac{1}{\alpha\beta^{3}}+\frac{d}{\varepsilon\alpha
\beta^{2}}+\frac{d^{3/4}}{\varepsilon^{1/2}\alpha\beta^{5/2}}\right),$
(2)
which is always at least $\Omega(\sqrt{d})$ times smaller than (1).(^2^22Note that $\frac{d^{3/4}}{\varepsilon^{1/2}\alpha\beta^{5/2}}\lesssim\frac{1}{\sqrt{d}}( \frac{d}{\alpha\beta^{3}}+\frac{d^{3/2}}{\varepsilon\alpha\beta^{2}})$ by the AM-GM inequality.)
Notably, the “non-private” term $1/\alpha\beta^{3}$ is dimension-independent, as opposed to (1),
which is the first result of this sort for NSNC DP optimization, and was erroneously claimed impossible by previous work (see Remark 3.2).
- 2.
Better multi-pass algorithm (Theorem 4.1):
In order to further improve the sample complexity, we move to consider ERM algorithms that go over the data multiple times (polynomially),
which we will later argue generalize to the population loss.
To that end, we provide an $(\varepsilon,\delta)$-DP ERM algorithm, that returns an $(\alpha,\beta)$-Goldstein stationary
point of $\widehat{F}^{\mathcal{D}}$ as long as
$n=\widetilde{\Omega}\left(\frac{d^{3/4}}{\varepsilon\alpha^{1/2}\beta^{3/2}}
\right).$
(3)
Notably, (3) substantially improves (2) (and thus, (1)) in parameter regimes of interest (small $\varepsilon,\alpha,\beta$, large $d$) with respect to the dimension and accuracy parameters, and in particular is the first algorithm to preform private ERM with sublinear dimension-dependent sample complexity for NSNC objectives.

In order to utilize our empirical algorithm for stochastic objectives, one must argue that Goldstein-stationarity generalizes from the ERM to the population. As no such argument is currently pointed out in the literature, we provide a result that ensures this:

- •
Additional contribution: generalizing from ERM to population (Proposition 5.1).
We show that with high probability, any $(\alpha,\widehat{\beta})$-stationary point of $\widehat{F}^{\mathcal{D}}$ is an $(\alpha,\beta)$-stationary point of $F$, for $\beta=\widehat{\beta}+\widetilde{O}(\sqrt{d/n})$.
Hence, the empirical guarantee (3)
generalizes to stochastic losses with an additional $d/\beta^{2}$ additive term in $n$ (up to log terms).

**Table 1: Main results (ignoring dependence on Lipschitz constant, initialization, and log terms).**
| Sample complexity summary | empirical | stochastic |
| --- | --- | --- |
| (Zhang et al., ) (single-pass) | $\frac{d}{\alpha\beta^{3}}+\frac{d^{3/2}}{\varepsilon\alpha\beta^{2}}$ |  |
| Theorem 3.1 (single-pass) | $\frac{1}{\alpha\beta^{3}}+\frac{d}{\varepsilon\alpha\beta^{2}}+\frac{d^{3/4}}{<br>\varepsilon^{1/2}\alpha\beta^{5/2}}$ |  |
| Theorem 4.1 (multi-pass) | $\frac{d^{3/4}}{\varepsilon\alpha^{1/2}\beta^{3/2}}$ | $\frac{d}{\beta^{2}}+\frac{d^{3/4}}{\varepsilon\alpha^{1/2}\beta^{3/2}}$ |

## 2 Preliminaries

#### Notation.

We denote by $\left\langle\cdot,\cdot\right\rangle,\left\|\,\cdot\,\right\|$ the standard Euclidean dot product and its induced norm.
For $x\in\mathbb{R}^{d}$ and $\alpha>0$,
we denote by $\mathbb{B}(x,\alpha)$ the closed ball of radius $\alpha$ centered at $x$, and further denote $\mathbb{B}_{\alpha}:=\mathbb{B}(0,\alpha)$. $\mathbb{S}^{d-1}\subset\mathbb{R}^{d}$ denotes the unit sphere.
We make standard use of $O$-notation to hide absolute constants, $\widetilde{O},\widetilde{\Omega}$ to hide poly-logarithmic factors, and also let $f\lesssim g$ denote $f=O(g)$.

#### Nonsmooth optimization.

A function $h:\mathbb{R}^{d}\to\mathbb{R}$ is called $L$-Lipschitz if for all $x,y\in\mathbb{R}^{d}:|h(x)-h(y)|\leq L\|x-y\|$. We call $h$ $H$-smooth, if $h$ is differentiable and $\nabla h$ is $H$-Lipschitz with respect to the Euclidean norm.
For Lipschitz functions, the Clarke subgradient set (Clarke, ) can be defined as

$$ $\partial h(x):=\mathrm{conv}\{g\,:\,g=\lim_{n\to\infty}\nabla h(x_{n}),\,x_{n} \to x\},$ $$

namely the convex hull of all limit points of $\nabla h(x_{n})$ over sequences of differentiable points
(which are a full Lebesgue-measure set by Rademacher’s theorem),
converging to $x$.
For $\alpha\geq 0$, the Goldstein $\alpha$-subdifferential (Goldstein, ) is further defined as

$$ $\partial_{\alpha}h(x):=\mathrm{conv}(\cup_{y\in\mathbb{B}(x,\alpha)}\partial h (y)),$ $$

and we denote the minimum-norm element of the Goldstein $\alpha$-subdifferential by

$$ $\displaystyle\overline{\partial}_{\alpha}h(x):={\arg\min}_{g\in\partial_{ \alpha}h(x)}\left\|g\right\|.$ $$

###### Definition 2.1 .

A point $x\in\mathbb{R}^{d}$ is called an $(\alpha,\beta)$-Goldstein stationary point of $h$ if $\left\|\overline{\partial}_{\alpha}h(x)\right\|\leq\beta$.

Throughout the paper we impose the following standard Lipschitz assumption:

###### Assumption 2.2 .

For any $\xi$, $f(\cdot\,;\xi):\mathbb{R}^{d}\to\mathbb{R}$ is $L$-Lipschitz (hence, so is $F$).

###### Definition 2.1 .

###### Assumption 2.2 .

#### Randomized smoothing.

Given any function $h:\mathbb{R}^{d}\to\mathbb{R}$, we denote its randomized smoothing $h_{\alpha}(x):=\operatorname*{\mathbb{E}}_{y\sim\mathbb{B}_{\alpha}}h(x+y)$.
We recall the following standard properties of randomized smoothing (Flaxman et al., ; Yousefian et al., ; Duchi et al., ; Shamir, ).

###### Fact 2.3 (Randomized smoothing) .

Suppose $h:\mathbb{R}^{d}\to\mathbb{R}$ is $L$-Lipschitz.
Then

- •
$h_{\alpha}$ is $L$-Lipschitz.
- •
$|h_{\alpha}(x)-h(x)|\leq L\alpha$ for any $x\in\mathbb{R}^{d}$.
- •
$h_{\alpha}$ is $O(L\sqrt{d}/\alpha)$-smooth.
- •
$\nabla h_{\alpha}(x)=\operatorname*{\mathbb{E}}_{y\sim\mathbb{B}_{\alpha}}[
\nabla h(x+y)]=\operatorname*{\mathbb{E}}_{y\sim\mathbb{S}^{d-1}}[\frac{d}{2
\alpha}(h(x+\alpha y)-h(x-\alpha y))y]$.

The following result shows that in order to find a Goldstein-stationary point of a function, it suffices to find a Goldstein-stationary point of its randomized smoothing:

###### Lemma 2.4 ( Kornowski and Shamir, 2024 , Lemma 4) .

Any $(\alpha,\beta)$-stationary point of $h_{\alpha}$ is
a $(2\alpha,\beta)$-stationary point of $h$.

###### Fact 2.3 (Randomized smoothing) .

###### Lemma 2.4 ( Kornowski and Shamir, 2024 , Lemma 4) .

#### Differential privacy.

Two datasets $\mathcal{D},\mathcal{D}^{\prime}\in\mathrm{supp}(\mathcal{P})^{n}$ are said to be neighboring
if they differ in only one data point. A randomized algorithm $\mathcal{A}:\mathcal{Z}^{n}\to\mathcal{R}$ is called $(\varepsilon,\delta)$ differentially private (or $(\varepsilon,\delta)$-DP) for $\varepsilon,\delta>0$ if for any two neighboring datasets $\mathcal{D},\mathcal{D}^{\prime}$ and measurable $E\subseteq\mathcal{R}$ in the algorithm’s range, it holds that $\Pr[\mathcal{A}(\mathcal{D})\in E]\leq e^{\varepsilon}\Pr[\mathcal{A}(\mathcal
{D}^{\prime})\in E]+\delta$ (Dwork et al., ).

Next, we recall the well-known tree mechanism given by Algorithm 1, and its associated guarantee presented below.

###### Proposition 2.5 (Tree Mechanism Dwork et al., 2010 ; Chan et al., 2011 ; Zhang et al., 2024 ) .

Let $\mathcal{Z}_{1},\cdots,\mathcal{Z}_{\Sigma}$ be dataset spaces, and $\mathcal{X}$ be the state space.
Let $\mathcal{M}_{i}:\mathcal{X}^{i-1}\times\mathcal{Z}_{i}\to\mathcal{X}$ be a sequence of algorithms for $i\in[\Sigma]$.
Let $\mathrm{ALG}:\mathcal{Z}^{(1:\Sigma)}\to\mathcal{X}^{\Sigma}$ be the algorithm that given a dataset $Z_{1:\Sigma}\in\mathcal{Z}^{(1:\Sigma)}$, sequentially computes $X_{i}=\sum_{j=1}^{i}\mathcal{M}_{i}(X_{1:j-1},Z_{i})+\mathrm{TREE}(i)$ for $i\in[\Sigma]$, and then outputs $X_{1:\Sigma}$.
Suppose for all $i\in[\Sigma]$, and neighboring $Z_{1:\Sigma},Z_{1:\Sigma}^{\prime}\in\mathcal{Z}^{(1:\Sigma)},\|\mathcal{M}_{i
}(X_{1:i-1},Z_{i})-\mathcal{M}_{i}(X_{1:i-1},Z_{i}^{\prime})\|\leq s$ for all auxiliary inputs $X_{1:i-1}\in\mathcal{X}^{i-1}$. Then setting $\sigma=4s\sqrt{\log\Sigma\log(1/\delta)}/{\varepsilon}$, Algorithm 1 is $(\varepsilon,\delta)$-DP.
Furthermore,
for all $t\in[\Sigma]:~{}\operatorname*{\mathbb{E}}[\mathrm{TREE}(t)]=0$ and $\operatorname*{\mathbb{E}}\left\|\mathrm{TREE}(t)\right\|^{2}\lesssim d\log(
\Sigma)\sigma^{2}$.

Figure: Algorithm 1 Tree Mechanism

###### Proposition 2.5 (Tree Mechanism Dwork et al., 2010 ; Chan et al., 2011 ; Zhang et al., 2024 ) .

### 2.1 Base algorithm: O2NC

Similar to Zhang et al. (), our general algorithm is based on the so-called “Online-to-Non-Convex conversion” (O2NC) of Cutkosky et al. ().
We slightly modify previous proofs by disentangling the role of the variance of the gradient estimator vs. its second order moment, as follows:

###### Proposition 2.6 (O2NC) .

Suppose that $\mathcal{O}(\,\cdot\,)$ is a stochastic gradient oracle of some differentiable function $h:\mathbb{R}^{d}\to\mathbb{R}$,
so that for all $z\in\mathbb{R}^{d}:~{}\operatorname*{\mathbb{E}}\|\mathcal{O}(z)-\nabla h(z)\|
^{2}\leq G_{0}^{2}$
and $\operatorname*{\mathbb{E}}\|\mathcal{O}(z)\|^{2}\leq G_{1}^{2}$.
Then running Algorithm 2 with
$\eta=\frac{D}{G_{1}\sqrt{M}},~{}MD\leq\alpha$,
uses $T$ calls to $\mathcal{O}(\,\cdot\,)$, and
satisfies

$$ $\displaystyle\operatorname*{\mathbb{E}}\left\|\overline{\partial}_{\alpha}h(x^ {\mathrm{out}})\right\|\leq\frac{h(x_{0})-\inf h}{DT}+\frac{3G_{1}}{2\sqrt{M}} +G_{0}.$ $$

We provide a proof of Proposition 2.6 in Appendix A.
Recalling that by Lemma 2.4 any $(\alpha,\beta)$-stationary point of $F_{\alpha}$ is a $(2\alpha,\beta)$-stationary point of $F$,
we see that it is enough to design a private stochastic gradient oracle $\mathcal{O}$ of $\nabla F_{\alpha}$, while controlling its variance $G_{0}$ and second moment $G_{1}$. In the next sections, we show how to construct such private oracles and derive the corresponding guarantees through Proposition 2.6.
As previously remarked,
in the main text, our oracles will be based on zero-order queries of the component functions $f(\,\cdot\,,\xi)$, yet
in Appendix B, we also show we can construct oracles with the same sample complexity using first-order queries with a lower oracle complexity.

Figure: Algorithm 2 Nonsmooth Nonconvex Algorithm (based on O2NC (Cutkosky et al., ))

###### Proposition 2.6 (O2NC) .

## 3 Single-pass algorithm

Figure: Algorithm 3 Single-pass instantiation of $\mathcal{O}(z_{t})$ in Line 7 of Algorithm 2

In this section, we consider Algorithm 3, which provides
an oracle to be used in Algorithm 2.
Algorithm 3
is such that throughout $T$ calls, it uses each data point once, and hence, privacy is maintained with no need for composition.
Before getting into the details, we will provide the main underlying idea.
We consider the zero-order gradient estimator

$$ $\tilde{\nabla}f_{\alpha}(x;\xi)=\frac{1}{m}\sum_{j=1}^{m}\frac{d}{2\alpha}(f(x +\alpha y_{j};\xi)-f(x-\alpha y_{j};\xi)),~{}~{}y_{1},\dots,y_{m}\overset{iid} {\sim}\mathrm{Unif}(\mathbb{S}^{d-1}),$ (4) $$

which is an unbiased estimator of $\nabla f_{\alpha}(x;\xi)$, to which we then apply variance reduction.
Zhang et al. () considered the oracle above specifically with $m=d$, for which it is easy to bound the sensitivity of this estimator over neighboring minibatches $\xi_{1:B},\xi^{\prime}_{1:B}$ of size $B$
by

$$ $\displaystyle\left\|\frac{1}{B}\sum_{i=1}^{B}\tilde{\nabla}f_{\alpha}(x;\xi_{i })-\frac{1}{B}\sum_{i=1}^{B}\tilde{\nabla}f_{\alpha}(x;\xi^{\prime}_{i})\right \|\leq\frac{Ld}{B}.$ (5) $$

Our key observation is that while this is indeed the worst-case sensitivity, we can get substantially lower sensitivity *with high probability*.
For sufficiently large $m$, standard sub-Gaussian concentration properties ensure that $\tilde{\nabla}f_{\alpha}(x;\xi_{i})\approx\nabla f_{\alpha}(x;\xi_{i})$ with high probability, and hence under this event we show the sensitivity over a mini-batch can be decreased to an order of $\frac{L}{B}$. As this is a factor of $d$ smaller than (5),
we can add significantly less noise in order to privatize, therefore leading to faster convergence to stationarity.

The main theorem in this section is the following:

###### Theorem 3.1 (Single-pass algorithm) .

Suppose $F(x_{0})-\inf_{x}F(x)\leq\Phi$, that Assumption 2.2 holds,
and let $\alpha,\beta,\delta,\varepsilon>0$ such that $\alpha\leq\frac{\Phi}{L}$.
Then setting $B_{1}=\Sigma,~{}B_{2}=1,~{}M=\alpha/4D,~{}m=\widetilde{O}(d^{2}B_{1}^{2}+\frac
{d\alpha^{2}B_{2}^{2}}{D^{2}}),~{}\sigma=\widetilde{O}(\frac{L}{B_{1}
\varepsilon}+\frac{LD\sqrt{d}}{\alpha B_{2}\varepsilon}),~{}\Sigma=\widetilde{
\Theta}((\frac{\alpha}{\varepsilon D})^{2/3}),~{}D=\widetilde{\Theta}(\min\{(
\frac{\Phi^{2}\alpha}{L^{2}T^{2}})^{1/3},(\frac{\Phi\alpha\varepsilon}{dLT})^{
1/2},(\frac{\Phi^{3}\alpha^{2}\varepsilon}{d^{3/2}L^{3}T^{3}})^{1/5}\}),~{}T=
\Theta(n)$, and running Algorithm 2 with Algorithm 3 as the oracle subroutine, is $(\varepsilon,\delta)$-DP.
Furthermore, its output satisfies
$\operatorname*{\mathbb{E}}\|\overline{\partial}_{2\alpha}F(x^{\mathrm{out}})\|\leq\beta$ as long as

$$ $n=\widetilde{\Omega}\left(\frac{\Phi L^{2}}{\alpha\beta^{3}}+\frac{\Phi Ld}{ \varepsilon\alpha\beta^{2}}+\frac{\Phi L^{3/2}d^{3/4}}{\varepsilon^{1/2}\alpha \beta^{5/2}}\right).$ $$

###### Remark 3.2 .

It is interesting to note that the “non-private” term $\Phi L^{2}/\alpha\beta^{3}$ in Theorem 3.1
is independent of the dimension $d$.
Not only is this the first result of this sort, this was even (erroneously) claimed impossible by Zhang et al. ().
The reason for this confusion is that while the optimal zero-order *oracle* complexity
is $d/\alpha\beta^{3}$ (Kornowski and Shamir, ), and in particular must scale with the dimension (Duchi et al., ), the *sample* complexity might not.

In the rest of the section, we will present the basic properties of this oracle in terms of sensitivity (implying the privacy), variance and second moment.
We will then plug these into Algorithm 2, which enables proving Theorem 3.1.
Corresponding proofs are deferred to Section 6.

###### Lemma 3.3 (Sensitivity) .

Consider the gradient oracle $\mathcal{O}(\cdot)$ in Algorithm 3 when acting on two neighboring minibatches $S_{t}$ and $S^{\prime}_{t}$, and correspondingly producing $g_{t}$ and $g_{t}^{\prime}$, respectively.
If $t\mathrm{~{}mod~{}}\Sigma=1$, then it holds with probability at least $1-\delta/2$ that

$$ $\displaystyle\|g_{t}-g_{t}^{\prime}\|\lesssim\frac{L}{B_{1}}+\frac{Ld\sqrt{ \log(dB_{1}/\delta)}}{\sqrt{m}}.$ $$

Otherwise, conditioned on $g_{t-1}=g_{t-1}^{\prime}$, we have with probability at least $1-\delta/2:$

$$ $\displaystyle\|g_{t}-g_{t}^{\prime}\|\lesssim\frac{L\sqrt{d}D}{\alpha B_{2}}+ \frac{Ld\sqrt{\log(dB_{1}/\delta)}}{\sqrt{m}}.$ $$

With the sensitivity bound given by Lemma 3.3, we easily derive the privacy guarantee of our oracle from the Tree Mechanism (Proposition 2.5).

###### Lemma 3.4 (Privacy) .

Running Algorithm 3 with $m=O\left(\log(dB_{2}/\delta)(d^{2}B_{1}^{2}+\frac{d\alpha^{2}B_{2}^{2}}{D^{2}}
)\right)$ and $\sigma=O\left(\frac{L\sqrt{\log(1/\delta)}}{B_{1}\varepsilon}+\frac{LD\sqrt{d
\log(1/\delta)}}{\alpha B_{2}\varepsilon}\right)$ is $(\varepsilon,\delta)$-DP.

We next analyze the variance and second moment of the gradient oracle.

###### Lemma 3.5 (Variance) .

In Algorithm 3, for all $t\in[T]$ it holds that

$$ $\displaystyle\operatorname*{\mathbb{E}}\|\tilde{g}_{t}-\nabla F_{\alpha}(z_{t} )\|^{2}$ $\displaystyle\lesssim\frac{L^{2}}{B_{1}}+\frac{L^{2}d^{2}}{B_{1}m}+\frac{L^{2} dD^{2}\Sigma}{\alpha^{2}B_{2}}+\sigma^{2}d\log\Sigma+\frac{L^{2}d^{2}\Sigma}{ mB_{2}},$ $\displaystyle\operatorname*{\mathbb{E}}\|\tilde{g}_{t}\|^{2}$ $\displaystyle\lesssim L^{2}+\frac{L^{2}d^{2}}{B_{1}m}+\frac{L^{2}dD^{2}\Sigma} {\alpha^{2}B_{2}}+\sigma^{2}d\log\Sigma+\frac{L^{2}d^{2}\Sigma}{mB_{2}}.$ $$

Combining the ingredients that we have set up,
we can derive Theorem 3.1.

###### Proof of Theorem 3.1 .

The privacy guarantee follows directly from Lemma 3.4, by noting that our parameter assignment implies $B_{1}T/\Sigma+B_{2}T=O(n)$, which allows letting $T=\Theta(n)$ while never re-using samples (hence no privacy composition is required).
Therefore, it remains to show the utility bound.
By applying Lemma 2.4 and Proposition 2.6, we get that

$$ $\displaystyle\operatorname*{\mathbb{E}}\|\overline{\partial}_{2\alpha}F(x^{ \mathrm{out}})\|\leq\operatorname*{\mathbb{E}}\|\overline{\partial}_{\alpha}F_ {\alpha}(x^{\mathrm{out}})\|$ $\displaystyle\leq\frac{F_{\alpha}(x_{0})-\inf F_{\alpha}}{DT}+\frac{3G_{1}}{2 \sqrt{M}}+G_{0}$ $\displaystyle\leq\frac{2\Phi}{DT}+\frac{3G_{1}}{2\sqrt{M}}+G_{0},$ (6) $$

where the last inequality used the fact that
Assumption 2.2
and Fact 2.3 together imply that $F_{\alpha}(x_{0})-\inf F_{\alpha}\leq F(x_{0})-\inf F+L\alpha\leq\Phi+L\alpha
\leq 2\Phi$.
Under our parameter assignment, Lemma 3.5 yields

$$ $\displaystyle G_{1}\lesssim G_{0}+L,$ (7) $$

which plugged into (6) gives

$$ $\displaystyle\operatorname*{\mathbb{E}}\|\overline{\partial}_{2\alpha}F(x^{ \mathrm{out}})\|=O\left(\frac{\Phi}{DT}+\frac{L}{\sqrt{M}}+G_{0}\right).$ (8) $$

Moreover, under our parameter assignment Lemma 3.5 also gives the bound

$$ $\displaystyle G_{0}$ $\displaystyle\lesssim\frac{L}{B_{1}}+\frac{LD\sqrt{d\Sigma}}{\alpha B_{2}}+ \sigma\sqrt{d\log\Sigma}=\widetilde{O}\left(\frac{LDd^{1/2}\Sigma^{1/2}}{ \alpha}+\frac{Ld^{1/2}}{\Sigma\varepsilon}+\frac{LDd}{\alpha\varepsilon}\right),$ (9) $$

which propagated into (8) and recalling that $M=\Theta(\alpha/D)$
shows that

$$ $\displaystyle\operatorname*{\mathbb{E}}\|\overline{\partial}_{2\alpha}F(x^{ \mathrm{out}})\|=\widetilde{O}\left(\frac{\Phi}{DT}+\frac{LD^{1/2}}{\alpha^{1/ 2}}+\frac{LDd^{1/2}\Sigma^{1/2}}{\alpha}+\frac{Ld^{1/2}}{\Sigma\varepsilon}+ \frac{LDd}{\alpha\varepsilon}\right)~{}.$ $$

Plugging our assignments of $\Sigma$ and $D$, and recalling that $n=\Theta(T)$, a straightforward calculation simplifies the bound above to

$$ $\displaystyle\operatorname*{\mathbb{E}}\|\overline{\partial}_{2\alpha}F(x^{ \mathrm{out}})\|$ $\displaystyle=\widetilde{O}\left(\left(\frac{\Phi L^{2}}{T\alpha}\right)^{1/3} +\left(\frac{\Phi dL}{T\alpha\varepsilon}\right)^{1/2}+\left(\frac{\Phi^{2}L^{ 3}d^{3/2}}{T^{2}\alpha^{2}\varepsilon}\right)^{1/5}\right)$ $\displaystyle=\widetilde{O}\left(\left(\frac{\Phi L^{2}}{n\alpha}\right)^{1/3} +\left(\frac{\Phi dL}{n\alpha\varepsilon}\right)^{1/2}+\left(\frac{\Phi^{2}L^{ 3}d^{3/2}}{n^{2}\alpha^{2}\varepsilon}\right)^{1/5}\right).$ (10) $$

Bounding the latter by $\beta$ and solving for $n$ completes the proof.

∎

###### Theorem 3.1 (Single-pass algorithm) .

###### Remark 3.2 .

###### Lemma 3.3 (Sensitivity) .

###### Lemma 3.4 (Privacy) .

###### Lemma 3.5 (Variance) .

###### Proof of Theorem 3.1 .

## 4 Multi-pass algorithm

Figure: Algorithm 4 Multi-pass instantiation of $\mathcal{O}(z_{t})$ in Line 7 of Algorithm 2

In this section, we consider a different oracle construction
given by Algorithm 4,
to be used in Algorithm 2.
The main difference from the previous section is that this oracle reuses data points a polynomial number of times,
and therefore cannot *directly* guarantee generalization to the stochastic objective.
Instead, in this section we analyze the empirical objective $\widehat{F}^{\mathcal{D}}(x):=\frac{1}{n}\sum_{i=1}^{n}f(x;\xi_{i})$. After establishing ERM results,
in Section 5, we will show that any empirical Goldstein-stationarity guarantee generalizes to the population loss.

Similarly to the single-pass oracle (Algorithm 3), we use randomized smoothing and variance reduction. A difference in the oracle construction is that we replace the tree mechanism with the Gaussian mechanism and apply advanced composition for the privacy analysis (since now samples are reused).
The main theorem for this section is the following:

###### Theorem 4.1 (Multi-pass ERM) .

Suppose $\widehat{F}^{\mathcal{D}}(x_{0})-\inf_{x}\widehat{F}^{\mathcal{D}}(x)\leq\Phi$, Assumption 2.2 holds, and let $\alpha,\beta,\delta,\varepsilon>0$ such that $\alpha\leq\frac{\Phi}{L}$.
Then setting $m=\frac{L^{2}d\Sigma}{n\sigma_{1}^{2}}+\frac{L^{2}d}{n\sigma_{2}^{2}}$, $\sigma_{1}=O(\frac{L\sqrt{T\log(1/\delta)/\Sigma}}{n\varepsilon})$, $\sigma_{2}=O(\frac{LD\sqrt{Td\log(1/\delta)}}{\alpha n\varepsilon})$, $\Sigma=\tilde{\Theta}(\frac{\alpha}{D\sqrt{d}})$, $D=\tilde{\Theta}(\frac{\alpha^{2}\beta^{2}}{L^{2}}),T=\tilde{\Theta}(\frac{
\Phi L^{2}}{\alpha^{2}\beta^{3}})$, and running Algorithm 2 with Algorithm 4 as the oracle subroutine is $(\varepsilon,\delta)$-DP.
Furthermore, its output satisfies $\operatorname*{\mathbb{E}}\|\overline{\partial}_{2\alpha}\widehat{F}^{\mathcal
{D}}(x^{\mathrm{out}})\|\leq\beta$ as long as

$$ $n=\widetilde{\Omega}\left(\frac{\sqrt{\Phi}Ld^{3/4}}{\varepsilon\alpha^{1/2} \beta^{3/2}}\right).$ $$

###### Remark 4.2 .

As we will show in Section 5,
Theorem 4.1 also provides the same population guarantee for $\|\overline{\partial}_{2\alpha}F(x^{\mathrm{out}})\|$ with an additional $L^{2}d/\beta^{2}$ term (up to log factors) to the sample complexity.

To prove Theorem 4.1, we analyze the properties of the oracle given by Algorithm 4.
The sensitivity of $g_{t}$ in Algorithm 4 directly follows from Lemma 3.3.(^3^33In this section we use full-batch size for simplicity, but using smaller batches (of arbitrary size) and applying privacy amplification by subsampling, yields the same results up to constants.)
By the standard composition results of the Gaussian mechanism (e.g., Mironov ), we have the following privacy guarantee:

###### Lemma 4.3 (Privacy) .

Calling Algorithm 4 $T$ times with $m=\frac{L^{2}d\Sigma}{n\sigma_{1}^{2}}+\frac{L^{2}d}{n\sigma_{2}^{2}}$, $\sigma_{1}=O(\frac{L\sqrt{T\log(1/\delta)/\Sigma}}{n\varepsilon})$ and $\sigma_{2}=O(\frac{LD\sqrt{Td\log(1/\delta)}}{\alpha n\varepsilon})$ is $(\varepsilon,\delta)$-DP.

In terms of the oracle’s variance, we show:

###### Lemma 4.4 (Variance) .

In Algorithm 4, for any $t\in[T]$, we have

$$ $\displaystyle\operatorname*{\mathbb{E}}\|\tilde{g}_{t}-\nabla F_{\alpha}^{ \mathcal{D}}(z_{t})\|^{2}$ $\displaystyle\lesssim\frac{L^{2}d^{2}\Sigma}{mn}+\sigma_{1}^{2}d+\sigma_{2}^{2 }d\Sigma,$ $\displaystyle\operatorname*{\mathbb{E}}\|\tilde{g}_{t}\|^{2}$ $\displaystyle\lesssim L^{2}+\frac{L^{2}d^{2}\Sigma}{mn}+\sigma_{1}^{2}d+\sigma _{2}^{2}d\Sigma.$ $$

The proof of Theorem 4.1, which we defer to Section 6, is a combination of the two previous lemmas and Proposition 2.6.

###### Theorem 4.1 (Multi-pass ERM) .

###### Remark 4.2 .

###### Lemma 4.3 (Privacy) .

###### Lemma 4.4 (Variance) .

## 5 Empirical to population Goldstein-stationarity

In this section, we provide a generalization result, showing that our ERM algorithm from the previous section also guarantees Goldstein-stationarity in terms of the population loss.
We prove the following more general statement:

###### Proposition 5.1 .

Under Assumption 2.2, suppose $\mathcal{D}\sim\mathcal{P}^{n}$, and consider running
an algorithm on $\widehat{F}^{\mathcal{D}}$ whose (possibly randomized) output $x^{\mathrm{out}}\in\mathcal{X}\subset\mathbb{R}^{d}$
is
supported over a set $\mathcal{X}$ of diameter $\leq R$.
Then with probability at least $1-\zeta:~{}\|\overline{\partial}_{\alpha}F(x^{\mathrm{out}})\|\leq\|\overline{
\partial}_{\alpha}\widehat{F}^{\mathcal{D}}(x^{\mathrm{out}})\|+\widetilde{O}
\left(L\sqrt{{d\log(R/\zeta)}/{n}}\right)$.

We remark that in all algorithms of interest, the output is known to lie in some predefined set, such as a sufficiently large ball around the initialization.
As long as the diameter $R$ is polynomial in the problem parameters, the $\log(R)$ in the result above is therefore negligible.
For instance, Algorithm 2 is easily verified to output a point $x^{\mathrm{out}}\in\mathbb{B}(x_{0},DT)$ (since $\|x_{t+1}-x_{t}\|\leq D$).
Hence, in our use case, Proposition 5.1 ensures $\|\overline{\partial}_{2\alpha}F(x^{\mathrm{out}})\|\leq\|\overline{\partial}_
{2\alpha}\widehat{F}^{\mathcal{D}}(x^{\mathrm{out}})\|+\beta$ for $n=\widetilde{O}(d/\beta^{2})$.

###### Proposition 5.1 .

## 6 Proofs

### 6.1 Proofs from Section 3

###### Proof of Lemma 3.3 .

Note that for any $y\in\mathrm{Unif}(\mathbb{S}^{d-1}):\|\frac{d}{2\alpha}(f(z+\alpha y;\xi)-f(z-
\alpha y;\xi))y\|\leq Ld$ due to the Lipschitz assumption.
Hence, for any $\xi\in S_{t}$, by
a standard sub-Gaussian bound (Theorem D.2) we have

$$ $\displaystyle\Pr\left[\|\tilde{\nabla}f(z_{t};\,\xi)-\nabla f_{\alpha}(z_{t}; \,\xi)\|\leq\frac{Ld\sqrt{\log(8dB_{1}/\delta)}}{\sqrt{m}}\right]\geq 1-\delta /8B_{1}.$ (11) $$

If $t\text{~{}mod~{}}\Sigma=1$, then

$$ $\displaystyle\|g_{t}-g_{t}^{\prime}\|=$ $\displaystyle~{}\left\|\frac{1}{B_{1}}(\sum_{\xi\in S_{t}}\tilde{\nabla}f(z_{t };\xi)-\sum_{\xi^{\prime}\in S_{t}^{\prime}}\tilde{\nabla}f(z_{t};\xi^{\prime} ))\right\|$ $\displaystyle\leq$ $\displaystyle\left\|\frac{1}{B_{1}}(\sum_{\xi\in S_{t}}\tilde{\nabla}f(z_{t}; \xi)-\nabla f_{\alpha}(z_{t};\xi))\right\|+\left\|\frac{1}{B_{1}}(\sum_{\xi\in S _{t}}\nabla f_{\alpha}(z_{t};\xi)-\sum_{\xi^{\prime}\in S_{t}^{\prime}}\nabla f _{\alpha}(z_{t};\xi^{\prime}))\right\|$ $\displaystyle~{}~{}+\left\|\frac{1}{B_{1}}(\sum_{\xi^{\prime}\in S_{t}^{\prime }}\tilde{\nabla}f(z_{t};\xi^{\prime})-\nabla f_{\alpha}(z_{t};\xi^{\prime})) \right\|.$ $$

Further note that $\|\frac{1}{B_{1}}(\sum_{\xi\in S_{t}}\nabla f_{\alpha}(z_{t};\xi)-\sum_{\xi^{
\prime}\in S_{t}^{\prime}}\nabla f_{\alpha}(z_{t};\xi^{\prime}))\|\leq 2L/B_{1}$, hence by Equation (11) and the union bound,

$$ $\displaystyle\Pr\left[\left\|\frac{1}{B_{1}}(\sum_{\xi\in S_{t}}\tilde{\nabla} f(z_{t};\xi)-\sum_{\xi^{\prime}\in S_{t}^{\prime}}\tilde{\nabla}f(z_{t};\xi^{ \prime}))\right\|\geq\frac{Ld\sqrt{\log(8dB_{1}/\delta)}}{\sqrt{m}}\right]\leq 1 -\delta/8,$ $$

which proves the claim in the case when $t\text{~{}mod~{}}\Sigma=1$.
The other case follows from the same argument.
∎

###### Proof of Lemma 3.4 .

By Lemma 3.3 and our assignment of $m$, we know that with probability at least $1-\delta/2$, the sensitivity of all $t$ is bounded by $O(\frac{L}{B_{1}}+\frac{L\sqrt{d}D}{\alpha B_{2}})$, namely for all $t:$

$$ $\displaystyle\|g_{t}-g_{t}^{\prime}\|\lesssim\frac{L}{B_{1}}+\frac{L\sqrt{d}D} {\alpha B_{2}}.$ $$

Then the privacy guarantee follows from the Tree Mechanism (Proposition 2.5).
∎

###### Proof of Lemma 3.5 .

First, note that by Proposition 2.5 and the facts that $\operatorname*{\mathbb{E}}[g_{t}]=\nabla F_{\alpha}(z_{t})$ and $\|\nabla F_{\alpha}(z_{t})\|\leq L$, we get

$$ $\displaystyle\operatorname*{\mathbb{E}}\|\tilde{g}_{t}\|^{2}\lesssim$ $\displaystyle\operatorname*{\mathbb{E}}\|g_{t}\|^{2}+d\sigma^{2}\log\Sigma \lesssim\operatorname*{\mathbb{E}}\|g_{t}-\nabla F_{\alpha}(z_{t})\|^{2}+L^{2} +d\sigma^{2}\log\Sigma,$ $$

and also

$$ $\displaystyle\operatorname*{\mathbb{E}}\|\tilde{g}_{t}-\nabla F_{\alpha}(z_{t} )\|^{2}\lesssim\operatorname*{\mathbb{E}}\|\tilde{g}_{t}-g_{t}\|^{2}+ \operatorname*{\mathbb{E}}\|g_{t}-\nabla F_{\alpha}(z_{t})\|^{2}\lesssim d \sigma^{2}\log\Sigma+\operatorname*{\mathbb{E}}\|g_{t}-\nabla F_{\alpha}(z_{t} )\|^{2}.$ $$

Therefore, we see that in order to obtain both claimed bounds, it suffices to bound $\operatorname*{\mathbb{E}}\|g_{t}-\nabla F_{\alpha}(z_{t})\|^{2}$. To that end, denote by $t_{0}\leq t$ the largest integer such that $t_{0}\text{~{}mod~{}}\Sigma=1$, and note that $t-t_{0}<\Sigma$. Further denote $\Delta_{j}:=g_{j}-g_{j-1}$. Then we have

$$ $\displaystyle\operatorname*{\mathbb{E}}\|g_{t}-\nabla F_{\alpha}(z_{t})\|^{2}$ $\displaystyle=\operatorname*{\mathbb{E}}\left\|g_{t_{0}}+\sum_{j=t_{0}+1}^{t} \Delta_{j}-\left(\sum_{j=t_{0}+1}^{t}(\nabla F_{\alpha}(z_{j})-\nabla F_{ \alpha}(z_{j-1}))+\nabla F_{\alpha}(z_{t_{0}})\right)\right\|^{2}$ $\displaystyle=\underset{(I)}{\underbrace{\operatorname*{\mathbb{E}}\|g_{t_{0}} -\nabla F_{\alpha}(z_{t_{0}})\|^{2}}}+\sum_{j=t_{0}}^{t}\underset{(II)}{ \underbrace{\operatorname*{\mathbb{E}}\|\Delta_{j}-(\nabla F_{\alpha}(z_{j})- \nabla F_{\alpha}(z_{j-1}))\|^{2}}},$ (12) $$

where the last equality is due to the cross terms
having zero mean. We further see that

$$ $\displaystyle(I)$ $\displaystyle\lesssim\operatorname*{\mathbb{E}}\left\|g_{t_{0}}-\frac{1}{B_{1} }\sum_{\xi\in S_{t_{0}}}\nabla f_{\alpha}(z_{t_{0}};\xi_{i})\right\|^{2}+ \operatorname*{\mathbb{E}}\left\|\frac{1}{B_{1}}\sum_{\xi\in S_{t_{0}}}\nabla f _{\alpha}(z_{t_{0}};\xi_{i})-\nabla F_{\alpha}(z_{t_{0}})\right\|^{2}$ $\displaystyle\lesssim\frac{L^{2}d^{2}}{B_{1}m}+\frac{L^{2}}{B_{1}},$ (13) $$

as well as

$$ $\displaystyle(II)$ $\displaystyle=\operatorname*{\mathbb{E}}\left\|\frac{1}{B_{2}}\sum_{\xi\in S_{ t}}(\tilde{\nabla}f(z_{j};\,\xi)-\tilde{\nabla}f(z_{j-1};\,\xi))-(\nabla F_{ \alpha}(z_{j})-\nabla F_{\alpha}(z_{j-1}))\right\|^{2}$ $\displaystyle=\frac{1}{B_{2}^{2}}\sum_{\xi\in S_{t}}\operatorname*{\mathbb{E}} \|(\tilde{\nabla}f(z_{j};\,\xi)-\tilde{\nabla}f(z_{j-1};\,\xi))-(\nabla F_{ \alpha}(z_{j})-\nabla F_{\alpha}(z_{j-1}))\|^{2}$ $\displaystyle\lesssim\frac{1}{B_{2}^{2}}\sum_{\xi\in S_{t}}\Big{(} \operatorname*{\mathbb{E}}\|\tilde{\nabla}f(z_{j};\,\xi)-\nabla f_{\alpha}(z_{ j};\,\xi)\|^{2}+\operatorname*{\mathbb{E}}\|\tilde{\nabla}f(z_{j-1};\,\xi)- \nabla f_{\alpha}(z_{j-1};\,\xi)\|^{2}$ $\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\operatorname*{\mathbb{E}}\|( \nabla f_{\alpha}(z_{j};\,\xi)-\nabla f_{\alpha}(z_{j-1};\,\xi))-(\nabla F_{ \alpha}(z_{j})-\nabla F_{\alpha}(z_{j-1}))\|^{2}\Big{)}$ $\displaystyle\lesssim\frac{L^{2}d^{2}}{mB_{2}}+\frac{dL^{2}D^{2}}{\alpha^{2}B_ {2}}.$ (14) $$

Plugging (13) and (14) into (12) and recalling that $t-t_{0}<\Sigma$ completes the proof.
∎

###### Proof of Lemma 3.3 .

###### Proof of Lemma 3.4 .

###### Proof of Lemma 3.5 .

### 6.2 Proofs from Section 4

###### Proof of Lemma 4.4 .

First, it suffices to prove the first bound, as

$$ $\operatorname*{\mathbb{E}}\|\tilde{g}_{t}\|^{2}\lesssim\operatorname*{\mathbb{ E}}\|\tilde{g}_{t}-\nabla F_{\alpha}^{\mathcal{D}}(z_{t})\|^{2}+\operatorname* {\mathbb{E}}\|\nabla F_{\alpha}^{\mathcal{D}}(z_{t})\|^{2}\leq\operatorname*{ \mathbb{E}}\|\tilde{g}_{t}-\nabla F_{\alpha}^{\mathcal{D}}(z_{t})\|^{2}+L^{2}.$ $$

To that end, let $t_{0}\leq t$ be the largest integer such that $t_{0}\text{~{}mod~{}}\Sigma\equiv 1$, and note that $t-t_{0}<\Sigma$.
Define $\Delta_{j}:=\frac{1}{n}\sum_{\xi\in\mathcal{D}}(\tilde{\nabla}f(z_{j};\,\xi)-
\tilde{\nabla}f(z_{j-1};\,\xi))$.
It holds that

$$ $\displaystyle\operatorname*{\mathbb{E}}\|\tilde{g}_{t}-\nabla F_{\alpha}^{ \mathcal{D}}(z_{t})\|^{2}\leq\underset{(I)}{\underbrace{\operatorname*{\mathbb {E}}\|g_{t_{0}}-\nabla F_{\alpha}^{\mathcal{D}}(z_{t_{0}})\|^{2}}}+\sum_{j=t_{ 0}}^{t}\underset{(II)}{\underbrace{\operatorname*{\mathbb{E}}\|\Delta_{j}-( \nabla F_{\alpha}^{\mathcal{D}}(z_{j})-\nabla F_{\alpha}^{\mathcal{D}}(z_{j-1} ))\|^{2}}}+\underset{(III)}{\underbrace{\sum_{j=t_{0}}^{t}\operatorname*{ \mathbb{E}}\|\chi_{j}\|^{2}}}.$ $$

Similar to the proof of Lemma 3.5,
we have that

$$ $\displaystyle(I)$ $\displaystyle=\operatorname*{\mathbb{E}}\left\|g_{t_{0}}-\frac{1}{n}\sum_{\xi \in\mathcal{D}}\nabla f_{\alpha}(z_{t_{0}};\xi_{i})\right\|^{2}\lesssim\frac{L ^{2}d^{2}}{nm},$ $\displaystyle(II)$ $\displaystyle=\frac{1}{n^{2}}\operatorname*{\mathbb{E}}\|\sum_{\zeta\in \mathcal{D}}(\tilde{\nabla}f(z_{j};\xi)-\tilde{\nabla}f(z_{j-1};\xi))-(\nabla \widehat{F}^{\mathcal{D}}_{\alpha}(z_{j})-\nabla\widehat{F}^{\mathcal{D}}_{ \alpha}(z_{j-1}))\|^{2}$ $\displaystyle\lesssim\frac{1}{n^{2}}\sum_{\xi\in\mathcal{D}}\Big{(} \operatorname*{\mathbb{E}}\|\tilde{\nabla}f(z_{j};\,\xi)-\nabla f_{\alpha}(z_{ j};\,\xi)\|^{2}+\operatorname*{\mathbb{E}}\|\tilde{\nabla}f(z_{j-1};\,\xi)- \nabla f_{\alpha}(z_{j-1};\,\xi)\|^{2}\Big{)}$ $\displaystyle\lesssim\frac{L^{2}d^{2}}{mn},$ $\displaystyle(III)$ $\displaystyle\leq\sigma_{1}^{2}d+\sigma_{2}^{2}(\Sigma-1),$ $$

overall completing the proof.

∎

###### Proof of Theorem 4.1 .

Setting $m=\frac{L^{2}d\Sigma}{n\sigma_{1}^{2}}+\frac{L^{2}d}{n\sigma_{2}^{2}}$, $\sigma_{1}=O(\frac{L\sqrt{T\log(1/\delta)/\Sigma}}{n\varepsilon})$ and $\sigma_{2}=O(\frac{LD\sqrt{Td\log(1/\delta)}}{\alpha n\varepsilon})$, the privacy guarantee follows from Lemma 4.3.
Moreover, by our parameter settings, we have

$$ $\displaystyle G_{0}^{2}:=\operatorname*{\mathbb{E}}\|\tilde{g}_{t}-\nabla F_{ \alpha}^{\mathcal{D}}(z_{t})\|^{2}\lesssim\frac{L^{2}dT\log(1/\delta)/\Sigma}{ n^{2}\varepsilon^{2}}+\frac{L^{2}D^{2}Td^{2}\Sigma\log(1/\delta)}{\alpha^{2}n^ {2}\varepsilon^{2}},$ $\displaystyle G_{1}^{2}:=\operatorname*{\mathbb{E}}\|\tilde{g}_{t}\|^{2} \lesssim L^{2}+\frac{L^{2}dT\log(1/\delta)/\Sigma}{n^{2}\varepsilon^{2}}+\frac {L^{2}D^{2}Td^{2}\Sigma\log(1/\delta)}{\alpha^{2}n^{2}\varepsilon^{2}}.$ $$

Therefore, setting $\Sigma=\widetilde{\Theta}(\frac{\alpha}{D\sqrt{d}})$, we see that $G_{0}=\widetilde{O}(\frac{L\sqrt{DT}d^{3/4}}{n\varepsilon\sqrt{\alpha}})$ and $G_{1}\lesssim L+G_{0}$.
By Proposition 2.6, we also know that

$$ $\displaystyle\operatorname*{\mathbb{E}}\|\overline{\partial}_{2\alpha}\widehat {F}^{\mathcal{D}}(x^{\mathrm{out}})\|\leq\operatorname*{\mathbb{E}}\|\overline {\partial}_{\alpha}\widehat{F}^{\mathcal{D}}_{\alpha}(x^{\mathrm{out}})\|$ $\displaystyle\leq\frac{F_{\alpha}(x_{0})-\inf F_{\alpha}}{DT}+\frac{3G_{1}}{2 \sqrt{M}}+G_{0}$ $\displaystyle\leq\frac{2\Phi}{DT}+\frac{3G_{1}}{2\sqrt{M}}+G_{0}.$ $$

Recalling that $M=\Theta(\alpha/D)$ and setting $D=\tilde{\Theta}(\frac{\alpha^{2}\beta^{2}}{L^{2}}),~{}T=\tilde{\Theta}(\frac{
\Phi L^{2}}{\alpha^{2}\beta^{3}})$, we have

$$ $\displaystyle\operatorname*{\mathbb{E}}\|\overline{\partial}_{\alpha}\widehat{ F}^{\mathcal{D}}_{\alpha}(x^{\mathrm{out}})\|$ $\displaystyle=\widetilde{O}\left(\frac{\Phi}{DT}+\frac{L\sqrt{D}}{\sqrt{\alpha }}+\frac{L\sqrt{DT}d^{3/4}}{n\varepsilon\sqrt{\alpha}}\right)$ $\displaystyle=\frac{\beta}{2}+\widetilde{O}\left(\frac{Ld^{3/4}\sqrt{\Phi}}{n \varepsilon\sqrt{\alpha\beta}}\right).$ $$

The latter is bounded by $\beta$ for $n=\widetilde{\Omega}\left(\frac{L\sqrt{\Phi}d^{3/4}}{\varepsilon\alpha^{1/2}
\beta^{3/2}}\right)$, hence completing the proof.

∎

###### Proof of Lemma 4.4 .

###### Proof of Theorem 4.1 .

### 6.3 Proofs from Section 5

###### Proof of Proposition 5.1 .

Applying a gradient uniform convergence bound for Lipschitz objectives over a bounded domain (Mei et al., , Theorem 1), shows that
with probability at least $1-\zeta$,
for any differentiable $x\in\mathcal{X}:$

$$ $\left\|\nabla\widehat{F}^{\mathcal{D}}(x)-\nabla F(x)\right\|=\widetilde{O} \left(L\sqrt{\frac{d\log(R/\zeta)}{n}}\right).$ (15) $$

Therefore, given any $x\in\mathcal{X}$, let $y_{1},\dots,y_{k}\in\mathbb{B}(x,\alpha)$ be points satisfying $\overline{\partial}_{\alpha}\widehat{F}^{\mathcal{D}}(x)=\sum_{i=1}^{k}\lambda
_{i}\nabla\widehat{F}^{\mathcal{D}}(y_{i})$ for coefficients $(\lambda_{i})_{i=1}^{k}\geq 0,\sum_{i=1}^{k}\lambda_{i}=1$ — note that such points exist by definition of the Goldstein subdifferential.
Noting that $\sum_{i=1}^{k}\lambda_{i}\nabla F(y_{i})\in\partial_{\alpha}F(x)$,
and recalling that
$\overline{\partial}_{\alpha}F(x)$ is the minimal norm element of $\partial_{\alpha}F(x)$, we get that

$$ $\left\|\overline{\partial}_{\alpha}F(x)\right\|\leq\left\|\sum_{i=1}^{k} \lambda_{i}\nabla F(y_{i})\right\|=\left\|\sum_{i=1}^{k}\lambda_{i}(\nabla \widehat{F}^{\mathcal{D}}(y_{i})+\upsilon_{i})\right\|=(\star)$ $$

where
$\upsilon_{i}:=\nabla F(y_{i})-\nabla\widehat{F}^{\mathcal{D}}(y_{i})$
satisfy $\left\|\upsilon_{i}\right\|=\widetilde{O}\left(L\sqrt{\frac{d\log(R/\zeta)}{n}
}\right)$ for all $i\in[k]$ by (15). Hence

$$ $\displaystyle(\star)$ $\displaystyle\leq\left\|\sum_{i=1}^{k}\lambda_{i}\nabla\widehat{F}^{\mathcal{D }}(y_{i})\right\|+\left\|\sum_{i=1}^{k}\lambda_{i}\upsilon_{i}\right\|$ $\displaystyle\leq\left\|\overline{\partial}_{\alpha}\widehat{F}^{\mathcal{D}}( x)\right\|+\sum_{i=1}^{k}\lambda_{i}\left\|\upsilon_{i}\right\|$ $\displaystyle\leq\left\|\overline{\partial}_{\alpha}\widehat{F}^{\mathcal{D}}( x)\right\|+\widetilde{O}\left(L\sqrt{\frac{d\log(R/\zeta)}{n}}\right).$ $$

∎

###### Proof of Proposition 5.1 .

## 7 Discussion

In this paper, we studied nonsmooth nonconvex optimization, and
proposed differentially private algorithms for this task which return Goldstein-stationary points, improving the previously known sample complexity for this task.

Our single-pass algorithm reduces the sample complexity by at least a $\Omega(\sqrt{d})$ factor (and sometimes more, depending on the parameter regime of interest), compared to the previous such result by Zhang et al. ().
Furthermore, our result has a dimension-independent “non-private” term, which was previously claimed impossible.
Moreover, we propose a multi-pass algorithm which preforms sample-efficient ERM, and show that it further generalizes to the population.

It is interesting to note that our guarantees are in terms of so-called “approximate” $(\varepsilon,\delta)$-DP, whereas Zhang et al. () derive a Rényi-DP guarantee (Mironov, ).
This is in fact inherent to our techniques, since we condition on a highly probable event in order to substantially decrease the effective sensitivity of our gradient estimators.
Further examining this potential gap in terms of sample complexity between approximate- and Rényi-DP for nonsmooth nonconvex optimization is an interesting direction for future research.

Another important problem that remains open is establishing tight lower bounds for DP nonconvex optimization and perhaps further improving the sample complexities obtained in this paper.
We note that the current upper and lower bounds do not fully match
even in the smooth setting.
In Appendix C, we provide evidence that our upper bound can be further improved, by proposing a
computationally-*inefficient* algorithm, which converges to a relaxed notion of stationarity, using even fewer samples than the algorithms we presented in this work.

## Appendix A Proof of Proposition 2.6 (O2NC)

We start by noting
that the update rule for $\Delta_{t}$ which is given by

$$ $\displaystyle{\Delta}_{t+1}=\mathrm{clip}_{D}\left({\Delta}_{t}-\eta\tilde{g}_ {t}\right)=\min\left\{1,\tfrac{D}{\left\|{\Delta}_{t}-\eta\tilde{g}_{t}\right \|}\right\}\cdot({\Delta}_{t}-\eta\tilde{g}_{t})$ $$

is precisely the online project gradient descent update rule, with respect to linear losses of the form $\ell_{t}(\cdot)=\left\langle\tilde{g}_{t},\cdot\right\rangle$, over the ball of radius $D$ around the origin. Accordingly,
recalling that $\operatorname*{\mathbb{E}}\|\tilde{{g}}_{t}-\nabla h(z_{t})\|^{2}\leq G_{1}^{2}$, combining the linearity of expectation with the standard regret analysis of online linear optimization (cf. Hazan, ) gives the following:

###### Lemma A.1 .

By setting $\eta=\frac{D}{G_{1}\sqrt{M}}$, for any $u\in\mathbb{R}^{d}$ with $\left\|u\right\|\leq D$ it holds that

$$ $\operatorname*{\mathbb{E}}_{\tilde{{g}}_{1},\dots,\tilde{{g}}_{M}}\left[\sum_{ m=1}^{M}\left\langle\tilde{g}_{m},{\Delta}_{m}-u\right\rangle\right]\leq\tfrac {3}{2}DG_{1}\sqrt{M}.$ $$

Back to analyzing Algorithm 2, since $x_{t}=x_{t-1}+\Delta_{t}$ it holds that

$$ $\displaystyle h(x_{t})-h(x_{t-1})$ $\displaystyle=\int_{0}^{1}\left\langle\nabla h(x_{t-1}+s\Delta_{t}),\Delta_{t} \right\rangle ds$ $\displaystyle=\operatorname*{\mathbb{E}}_{s_{t}\sim\mathrm{Unif}[0,1]}\left[ \langle\nabla h(x_{t-1}+s_{t}{\Delta}_{t}),\Delta_{t}\rangle\right]= \operatorname*{\mathbb{E}}_{s_{t}}\left[\left\langle\nabla h(z_{t}),\Delta_{t} \right\rangle\right].$ $$

Note that $\langle\nabla h(z_{t}),\Delta_{t}\rangle=\langle\nabla h(z_{t}),u\rangle+
\langle\tilde{g}_{t},\Delta_{t}-u\rangle+\langle\nabla h(z_{t})-\tilde{g}_{t},
\Delta_{t}-u\rangle$, so by summing over $t\in[T]=[K\times M]$, we get for any fixed sequence $u_{1},\dots,u_{K}\in\mathbb{R}^{d}:$

$$ $\displaystyle\inf h\leq h(x_{T})$ $\displaystyle\leq h(x_{0})+\sum_{t=1}^{T}\operatorname*{\mathbb{E}}\left[\left \langle\nabla h(z_{t}),\Delta_{t}\right\rangle\right]$ $\displaystyle=h(x_{0})+\sum_{k=1}^{K}\sum_{m=1}^{M}\operatorname*{\mathbb{E}} \left[\left\langle\tilde{g}_{(k-1)M+m},\Delta_{(k-1)M+m}-u_{k}\right\rangle\right]$ $\displaystyle~{}~{}~{}+\sum_{k=1}^{K}\sum_{m=1}^{M}\operatorname*{\mathbb{E}} \left[\left\langle\nabla h(z_{(k-1)M+m}),u_{k}\right\rangle\right]+\sum_{t=1}^ {T}\operatorname*{\mathbb{E}}[\langle\nabla h(z_{t})-\tilde{g}_{t},\Delta_{t}- u\rangle]$ $\displaystyle\leq h(x_{0})+\tfrac{3}{2}KDG_{1}\sqrt{M}+\sum_{k=1}^{K}\sum_{m=1 }^{M}\operatorname*{\mathbb{E}}\left[\left\langle\nabla h(z_{(k-1)M+m}),u_{k} \right\rangle\right]+G_{0}DT,$ $$

where the last inequality follows from applying Lemma A.1 to each $M$ consecutive iterates, and combining the bias bound $\operatorname*{\mathbb{E}}\left\|\tilde{{g}}_{t}-\nabla h(z_{t})\right\|\leq G
_{0}$ with Cauchy-Schwarz.

Letting $u_{k}:=-D\frac{\sum_{m=1}^{M}\nabla h(z_{(k-1)M+m})}{\left\|\sum_{m=1}^{M}
\nabla h(z_{(k-1)M+m})\right\|}$, rearranging and dividing by $DT=DKM$, we obtain

$$ $\displaystyle\frac{1}{K}\sum_{k=1}^{K}\operatorname*{\mathbb{E}}\left\|\frac{1 }{M}\sum_{m=1}^{M}\nabla h(z_{(k-1)M+m})\right\|$ $\displaystyle\leq\frac{h(x_{0})-\inf h}{DT}+\frac{3G_{1}}{2\sqrt{M}}+G_{0}.$ (16) $$

Finally, note that for all $k\in[K],m\in[M]:\left\|z_{(k-1)M+m}-\overline{x}_{k}\right\|\leq MD\leq\alpha$ since the clipping operation ensures each iterate is at most of distance $D$ to its predecessor, and therefore
$\nabla h(z_{(k-1)M+m})\in\partial_{\alpha}h(\overline{x}_{k})$. Since the set $\partial_{\alpha}h(\cdot)$ is convex by definition, we further see that

$$ $\frac{1}{M}\sum_{m=1}^{M}\nabla h(z_{(k-1)M+m})\in\partial_{\alpha}h(\overline {x}_{k})~{},$ $$

and hence by (16) we get

$$ $\operatorname*{\mathbb{E}}\left\|\overline{\partial}_{\alpha}h(x^{\mathrm{out} })\right\|=\frac{1}{K}\sum_{k=1}^{K}\operatorname*{\mathbb{E}}\left\|\overline {\partial}_{\alpha}h(\overline{x}_{k})\right\|\leq\frac{h(x_{0})-\inf h}{DT}+ \frac{3G_{1}}{2\sqrt{M}}+G_{0}.$ $$

###### Lemma A.1 .

## Appendix B First-order algorithm

In this appendix, our goal is to show that the zero-order algorithms presented in the main text can be replaced by first-order algorithms with the sample complexity, and reduced oracle complexity.

The simple idea is to replace the zero-order gradient estimator from Eq. (4) by the first-order estimator

$$ $\tilde{\nabla}f_{\alpha}(x;\xi)=\frac{1}{m}\sum_{j=1}^{m}\nabla f(x+\alpha y_{ j};\xi),~{}~{}y_{1},\dots,y_{m}\overset{iid}{\sim}\mathrm{Unif}(\mathbb{S}^{d- 1}).$ (17) $$

While this estimator has the same expectation as the zero-order variant, the key difference lies in the fact that its subGaussian norm is substantially smaller (as it does not depend on $d$), hence smaller $m$ suffices for concentration. This observation enables reducing the oracle complexity, while ensuring the same sample complexity guarantee as in the main text.

We fully analyze here a single-pass first-order oracle, presented in Algorithm 5, which can be used in Algorithm 2,
similarly to Section 3.
We note that a similar analysis can be applied to the multi-pass oracle of Section 4, once again by replacing (4) by (17).

As in Section 3, we will present the basic properties of this oracle. We will then plug these into Algorithm 2, leading to the main result of this section, Theorem B.4.

Figure: Algorithm 5 First-order instantiation of $\mathcal{O}(z_{t})$ in Line 7 of Algorithm 2

###### Lemma B.1 (Sensitivity) .

Consider the gradient oracle $\mathcal{O}(\cdot)$ in Algorithm 5 when acting on two neighboring minibatches $S_{t}$ and $S^{\prime}_{t}$, and correspondingly producing $g_{t}$ and $g_{t}^{\prime}$, respectively.
If $t\mathrm{~{}mod~{}}\Sigma=1$, then

$$ $\displaystyle\|g_{t}-g_{t}^{\prime}\|\leq\frac{L}{B_{1}}.$ $$

Otherwise, conditioned on $g_{t-1}=g_{t-1}^{\prime}$, we have with probability at least $1-\delta/2:$

$$ $\displaystyle\|g_{t}-g_{t}^{\prime}\|\lesssim\frac{L\sqrt{d}D}{\alpha B_{2}}+ \frac{L\sqrt{\log(dB_{2}/\delta)}}{\sqrt{m}}.$ $$

With the sensitivity bound given by Lemma B.1, we easily derive the privacy guarantee of our algorithm from the Tree Mechanism (Proposition 2.5).

###### Lemma B.2 (Privacy) .

Running Algorithm 5 with $m=O(\log(dB_{2}/\delta)\frac{B_{2}^{2}\alpha^{2}}{D^{2}d})$ and $\sigma=O(\frac{L\sqrt{\log(1/\delta)}}{B_{1}\varepsilon}+\frac{LD\sqrt{d\log(1
/\delta)}}{\alpha B_{2}\varepsilon})$ is $(\varepsilon,\delta)$-DP.

###### Proof.

By Lemma B.1 and our assignment of $m$, we know that with probability at least $1-\delta/2$, for any $t$, we have

$$ $\displaystyle\|g_{t}-g_{t}^{\prime}\|\lesssim\frac{L}{B_{1}}+\frac{L\sqrt{d}D} {\alpha B_{2}}.$ $$

Then the privacy guarantee follows from the Tree Mechanism (Proposition 2.5).

∎

We next provide the required variance bound on the gradient oracle.

###### Lemma B.3 (Variance) .

In Algorithm 5, for all $t$ it holds that

$$ $\displaystyle\operatorname*{\mathbb{E}}\|\tilde{g}_{t}-\nabla F_{\alpha}(z_{t} )\|^{2}$ $\displaystyle\lesssim\frac{L^{2}}{B_{1}}+\frac{L^{2}dD^{2}\Sigma}{\alpha^{2}B_ {2}}+\sigma^{2}d\log\Sigma+\frac{L^{2}\Sigma}{mB_{2}},$ $\displaystyle\operatorname*{\mathbb{E}}\|\tilde{g}_{t}\|^{2}$ $\displaystyle\lesssim L^{2}+\frac{L^{2}dD^{2}\Sigma}{\alpha^{2}B_{2}}+\sigma^{ 2}d\log\Sigma+\frac{L^{2}\Sigma}{mB_{2}}.$ $$

Having set up the required bounds, we can prove our main result for the first-order setting.

###### Theorem B.4 (First-order) .

Suppose $F(x_{0})-\inf_{x}F(x)\leq\Phi$, that Assumption 2.2 holds,
and let $\alpha,\beta,\delta,\varepsilon>0$ such that $\alpha\leq\frac{\Phi}{L}$.
Then setting $B_{1}=\Sigma,~{}B_{2}=1,~{}M=\alpha/4D,~{}m=\widetilde{O}(\frac{B_{2}^{2}
\alpha^{2}}{D^{2}d}),~{}\sigma=\widetilde{O}(\frac{L}{B_{1}\varepsilon}+\frac{
LD\sqrt{d}}{\alpha B_{2}\varepsilon}),~{}\Sigma=\widetilde{\Theta}((\frac{
\alpha}{\varepsilon D})^{2/3}),~{}D=\widetilde{\Theta}(\min\{(\frac{\Phi^{2}
\alpha}{L^{2}T^{2}})^{1/3},(\frac{\Phi\alpha\varepsilon}{dLT})^{1/2},(\frac{
\Phi^{3}\alpha^{2}\varepsilon}{d^{3/2}L^{3}T^{3}})^{1/5}\}),~{}T=\Theta(n)$, and running Algorithm 2 with Algorithm 5 as the oracle subroutine, is $(\varepsilon,\delta)$-DP.
Furthermore, its output satisfies
$\operatorname*{\mathbb{E}}\|\overline{\partial}_{2\alpha}F(x^{\mathrm{out}})\|\leq\beta$ as long as

$$ $\displaystyle n=\widetilde{\Omega}\left(\frac{\Phi L^{2}}{\alpha\beta^{3}}+ \frac{\Phi Ld}{\varepsilon\alpha\beta^{2}}+\frac{\Phi L^{3/2}d^{3/4}}{ \varepsilon^{1/2}\alpha\beta^{5/2}}\right).$ $$

###### Remark B.5 (Oracle complexity) .

Compared to the zero-order result given by Theorem 3.1, we see that the number of calls to $\mathcal{O}(\,\cdot\,)$, namely $T$, is on the same order, and that in both cases the amortized oracle complexity of $\mathcal{O}(\,\cdot\,)$ is $O(m)$.
The difference between the settings is that the first-order oracle instantiation sets $m$ to be $\widetilde{\Omega}(d^{2})$ times smaller than its zero-order counterpart, and hence we gain this multiplicative factor in the overall oracle complexity.

###### Proof of Theorem B.4 .

The privacy guarantee follows directly from Lemma B.2, by noting that our parameter assignment implies $B_{1}T/\Sigma+B_{2}T=O(n)$, hence it allows letting $T=\Theta(n)$ while never re-using samples.

As to the sample complexity, note that our parameter assignment ensures that

$$ $\displaystyle G_{1}$ $\displaystyle=O\left(G_{0}+L\right),$ $\displaystyle G_{0}$ $\displaystyle=\widetilde{O}\left(\frac{LDd^{1/2}\Sigma^{1/2}}{\alpha}+\frac{Ld ^{1/2}}{\Sigma\varepsilon}+\frac{LDd}{\alpha\varepsilon}\right),$ $$

similarly to (7) and (9) in the proof of Theorem 3.1. The rest of the proof is therefore exactly the same as for Theorem 3.1.
∎

###### Lemma B.1 (Sensitivity) .

###### Lemma B.2 (Privacy) .

###### Proof.

###### Lemma B.3 (Variance) .

###### Theorem B.4 (First-order) .

###### Remark B.5 (Oracle complexity) .

###### Proof of Theorem B.4 .

### B.1 Proofs from Appendix B

###### Proof of Lemma B.1 .

The case when $t\text{~{}mod~{}}\Sigma=1$ trivially follows the Lipschitz assumption.
Thus we will consider the more involved case.
For any $\xi\in S_{t}$, by a standard sub-Gaussian bound (Theorem D.2) we have

$$ $\displaystyle\Pr\left[\|\tilde{\nabla}f(z_{t};\,\xi)-\nabla f_{\alpha}(z_{t}; \,\xi)\|\leq\frac{L\sqrt{\log(8dB_{2}/\delta)}}{\sqrt{m}}\right]\geq 1-\delta/ 8B_{2},$ $$

so by the union bound, we get that with probability at least $1-\delta/8$, for all $\xi_{i}\in S_{t}:$

$$ $\displaystyle\|\tilde{\nabla}f(z_{t};\,\xi)-\nabla f_{\alpha}(z_{t};\,\xi)\| \leq\frac{L\sqrt{\log(8dB_{2}/\delta)}}{\sqrt{m}}.$ (18) $$

Hence,

$$ $\displaystyle\|g_{t}-g_{t}^{\prime}\|$ $\displaystyle\leq\left\|\frac{1}{B_{2}}\sum_{\xi\in S_{t}}\Big{(}(\tilde{ \nabla}f(z_{t};\xi)-\tilde{\nabla}f(z_{t-1};\xi_{i}))-(\nabla f_{\alpha}(z_{t} ;\xi))-\nabla f_{\alpha}(z_{t-1};\xi))\Big{)}\right\|$ $\displaystyle~{}~{}~{}~{}+\left\|\frac{1}{B_{2}}\sum_{\xi\in S_{t}}\Big{(}( \nabla f_{\alpha}(z_{t};\xi)-\nabla f_{\alpha}(z_{t-1};\xi))-\sum_{\xi^{\prime }\in S_{t}^{\prime}}(\nabla f_{\alpha}(z_{t};\xi^{\prime})-\nabla f_{\alpha}(z _{t};\xi^{\prime}))\Big{)}\right\|$ $\displaystyle~{}~{}~{}~{}+\left\|\frac{1}{B_{2}}\sum_{\xi^{\prime}\in S_{t}^{ \prime}}\Big{(}(\tilde{\nabla}f(z_{t};\xi^{\prime})-\tilde{\nabla}f(z_{t-1}; \xi^{\prime}))-(\nabla f_{\alpha}(z_{t};\xi^{\prime})-\nabla f_{\alpha}(z_{t-1 };\xi^{\prime}))\Big{)}\right\|$ $\displaystyle\lesssim\frac{L\sqrt{d}D}{\alpha B_{2}}+\frac{L\sqrt{\log(dB_{2}/ \delta)}}{\sqrt{m}},$ $$

where the last inequality step is due to the smoothness of $f_{\alpha}$ (Fact 2.3) combined with the fact that
$\left\|z_{t}-z_{t-1}\right\|\leq 2D$,
and (18).

∎

###### Proof of Lemma B.3 .

Applying by Proposition 2.5, we have

$$ $\displaystyle\operatorname*{\mathbb{E}}\|\tilde{g}_{t}-\nabla F_{\alpha}(z_{t} )\|^{2}\lesssim\operatorname*{\mathbb{E}}\|\tilde{g}_{t}-g_{t}\|^{2}+ \operatorname*{\mathbb{E}}\|g_{t}-\nabla F_{\alpha}(z_{t})\|^{2}\lesssim d \sigma^{2}\log\Sigma+\operatorname*{\mathbb{E}}\|g_{t}-\nabla F_{\alpha}(z_{t} )\|^{2},$ $$

and also since $\operatorname*{\mathbb{E}}[g_{t}]=\nabla F_{\alpha}(z_{t})$ and $\|\nabla F_{\alpha}(z_{t})\|\leq L$, we have

$$ $\displaystyle\operatorname*{\mathbb{E}}\|\tilde{g}_{t}\|^{2}\lesssim \operatorname*{\mathbb{E}}\|g_{t}\|^{2}+d\sigma^{2}\log\Sigma\lesssim \operatorname*{\mathbb{E}}\|g_{t}-\nabla F_{\alpha}(z_{t})\|^{2}+L^{2}+d\sigma ^{2}\log\Sigma.$ $$

We therefore see that both claimed bounds will follow from bounding $\operatorname*{\mathbb{E}}\|g_{t}-\nabla F_{\alpha}(z_{t})\|^{2}$.

To that end, denote by $t_{0}\leq t$ the largest integer such that $t_{0}\text{~{}mod~{}}\Sigma=1$, and note that $t-t_{0}<\Sigma$. Further denote $\Delta_{j}:=g_{j}-g_{j-1}$. Then we have

$$ $\displaystyle\operatorname*{\mathbb{E}}\|g_{t}-\nabla F_{\alpha}(z_{t})\|^{2}$ $\displaystyle=\operatorname*{\mathbb{E}}\left\|g_{t_{0}}+\sum_{j=t_{0}+1}^{t} \Delta_{j}-\big{(}\sum_{j=t_{0}+1}^{t}(\nabla F_{\alpha}(z_{j})-\nabla F_{ \alpha}(z_{j-1}))+\nabla F_{\alpha}(z_{t_{0}})\big{)}\right\|^{2}$ $\displaystyle=\operatorname*{\mathbb{E}}\|g_{t_{0}}-\nabla F_{\alpha}(z_{t_{0} })\|^{2}+\sum_{j=t_{0}}^{t}\operatorname*{\mathbb{E}}\|\Delta_{j}-(\nabla F_{ \alpha}(z_{j})-\nabla F_{\alpha}(z_{j-1}))\|^{2},$ $\displaystyle\lesssim\frac{L^{2}}{B_{1}}+\sum_{j=t_{0}}^{t}\underset{(\star)}{ \underbrace{\operatorname*{\mathbb{E}}\|\Delta_{j}-(\nabla F_{\alpha}(z_{j})- \nabla F_{\alpha}(z_{j-1}))\|^{2}}}$ (19) $$

where the second equality is due to the cross terms
having zero mean.
Moreover, we have

$$ $\displaystyle(\star)$ $\displaystyle=\operatorname*{\mathbb{E}}\left\|\frac{1}{B_{2}}\sum_{\xi\in S_{ t}}(\tilde{\nabla}f(z_{j};\,\xi)-\tilde{\nabla}f(z_{j-1};\,\xi))-(\nabla F_{ \alpha}(z_{j})-\nabla F_{\alpha}(z_{j-1}))\right\|^{2}$ $\displaystyle=\frac{1}{B_{2}^{2}}\sum_{\xi\in S_{t}}\operatorname*{\mathbb{E}} \|(\tilde{\nabla}f(z_{j};\,\xi)-\tilde{\nabla}f(z_{j-1};\,\xi))-(\nabla F_{ \alpha}(z_{j})-\nabla F_{\alpha}(z_{j-1}))\|^{2}$ $\displaystyle\lesssim\frac{1}{B_{2}^{2}}\sum_{\xi\in S_{t}}\Big{(} \operatorname*{\mathbb{E}}\|\tilde{\nabla}f(z_{j};\,\xi)-\nabla f_{\alpha}(z_{ j};\,\xi)\|^{2}+\operatorname*{\mathbb{E}}\|\tilde{\nabla}f(z_{j-1};\,\xi)- \nabla f_{\alpha}(z_{j-1};\,\xi)\|^{2}$ $\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\operatorname*{\mathbb{E}}\|( \nabla f_{\alpha}(z_{j};\,\xi)-\nabla f_{\alpha}(z_{j-1};\,\xi))-(\nabla F_{ \alpha}(z_{j})-\nabla F_{\alpha}(z_{j-1}))\|\Big{)}^{2}$ $\displaystyle\lesssim\frac{L^{2}}{mB_{2}}+\frac{dL^{2}D^{2}}{\alpha^{2}B_{2}},$ $$

which plugged into (19)
completes the proof by recalling that $t-t_{0}\leq\Sigma$.

∎

###### Proof of Lemma B.1 .

###### Proof of Lemma B.3 .

## Appendix C Even better sample complexity via optimal smoothing

In this Appendix,
our aim is to provide evidence that the sample complexities of NSNC DP optimization obtained in our work are likely improvable, at least
with a computationally inefficient method.
This approach is inspired by Lowy et al. [], which in the context of smooth optimization, showed significant sample complexity gains using algorithms with exponential runtime. As as we will show, a similar phenomenon might hold for nonsmooth optimization.
To that end, we propose a slight relaxation of Goldstein-stationarity, and show it can be achieved using less samples via an exponential time algorithm.

### C.1 Relaxation of Goldstein-stationarity

Recall that $x\in\mathbb{R}^{d}$ is called an $(\alpha,\beta)$-Goldstein stationary point
of an objective $F(x)=\operatorname*{\mathbb{E}}_{\xi}[f(x;\xi)]$ if there exist $y_{1},\dots,y_{k}\in\mathbb{B}(x,\alpha)$ and convex coefficients $(\lambda_{i})_{i=1}^{k}$ so that $\|\sum_{i\in[k]}\lambda_{i}\operatorname*{\mathbb{E}}_{\xi}[\nabla f(y_{i};\xi
)]\|\leq\beta$.
Arguably, the two most important properties satisfied by this definition are that

- (i)
If $f(x;\xi)$ are $L$-smooth, any $(\alpha,\beta)$-stationary point is $O(\alpha+\beta)$-stationary.
- (ii)
If $\left\|\overline{\partial}_{\alpha}F(x)\right\|\neq 0$, then $F\left(x-\tfrac{\alpha}{\left\|\overline{\partial}_{\alpha}F(x)\right\|}
\overline{\partial}_{\alpha}F(x)\right)\leq F(x)-\alpha\left\|\overline{
\partial}_{\alpha}F(x)\right\|$.

The first property shows that Goldstein-stationarity reduces to (“classic”) stationarity under smoothness. The second, known as Goldstein’s descent lemma [Goldstein, ], is a generalization of the classic descent lemma for smooth functions.

It is easy to see that Goldstein-stationarity is equivalent to the existence of a distribution $P$ supported over $\mathbb{B}(x,\alpha)$, such that $\|\operatorname*{\mathbb{E}}_{\xi,\,y\sim P}[\nabla f(y;\xi)]\|\leq\beta$.
We will now define a relaxation of Goldstein-stationarity that is easily verified to satisfy both of the aforementioned properties.

###### Definition C.1 .

We call a point $x\in\mathbb{R}^{d}$ an $(\alpha,\beta)$-*component-wise* Goldstein-stationary point of $F(x)=\operatorname*{\mathbb{E}}_{\xi}[f(x;\xi)]$ if
there exist distributions $P_{\xi}$ supported over $\mathbb{B}(x,\alpha)$, such that $\|\operatorname*{\mathbb{E}}_{\xi,\,y\sim P_{\xi}}[\nabla f(y;\xi)]\|\leq\beta$.

In other words, the definition above allows the sampled points $y_{1},\dots,y_{k}$ in the vicinity of $x$ to vary for different components, and as before, the sampled gradient must have small expected norm.
We next show that this relaxed stationarity notion allows improving the sample complexity of DP NSNC optimization.

###### Definition C.1 .

### C.2 Optimal smoothing and faster algorithm

In the previous sections, given an objective $f$, we
used the fact that Goldstein-stationary points of the randomized smoothing $f_{\alpha}$ correspond to Goldstein-stationary point of $f$, and
therefore constructed private gradient oracles of $f_{\alpha}$, which is $O(\sqrt{d}/\alpha)$-smooth.
Consequently, the sensitivity of the gradient oracle had a $\sqrt{d}$ dimension dependence (as seen in Lemma 3.3), thus affecting the overall sample complexity.

Instead of randomized smoothing, we now consider the Lasry-Lions (LL) smoothing [Lasry and Lions, ], a method that smooths Lipschitz functions in a dimension independent manner, which we now recall.
Given $h:\mathbb{R}^{d}\to\mathbb{R}$, denote the so-called Moreau envelope

$$ $M_{\lambda}(h)(x):=\min_{y}\left[h(y)+\frac{1}{2\lambda}\left\|y-x\right\|^{2} \right],$ $$

and the Lasry-Lions smoothing:

$$ $\tilde{h}_{\lambda\mathrm{LL}}(x):=-M_{\lambda}(-M_{2\lambda}(h))(x)=\max_{z} \min_{y}\left[h(z)+\frac{1}{4\lambda}\left\|z-y\right\|^{2}-\frac{1}{2\lambda} \left\|y-x\right\|^{2}\right].$ (20) $$

###### Fact C.2 .

[Lasry and Lions, , Attouch and Aze, ]
Suppose $h:\mathbb{R}^{d}\to\mathbb{R}$ is $L$-Lipschitz. Then:
(i) $\tilde{h}_{\lambda\mathrm{LL}}$ is $L$-Lipschitz; (ii) $|\tilde{h}_{\lambda\mathrm{LL}}(x)-h(x)|\leq L\lambda$ for any $x\in\mathbb{R}^{d}$;
(iii) $\arg\min\tilde{h}_{\lambda\mathrm{LL}}=\arg\min h$;
(iv) $\tilde{h}_{\lambda\mathrm{LL}}$ is $O(L/\lambda)$-smooth.

The key difference between LL-smoothing and randomized smoothing is that the smoothness constant of LL-smoothing is dimension independent.
By solving the optimization problem in Eq. (20), it is clear that the values, and therefore gradients, of $\tilde{f}_{\lambda\mathrm{LL}}(x;\xi_{i})$ can be obtained up to arbitrarily high accuracy.
Notably, it was shown by
Kornowski and Shamir []
that solving this problem requires, in general, an exponential number of oracle calls to the original function.

Nonetheless, computational considerations aside, it is not even clear that the LL smoothing helps in terms of finding Goldstein-stationary points of the original function, which was previously shown for randomized smoothing (Lemma 2.4). This is the purpose of the following result, which we prove:

###### Lemma C.3 .

If $h$ is $L$-Lipschitz, then any $\beta$-stationary point of $\tilde{h}_{\lambda\mathrm{LL}}$ is a
$(3\lambda L,\beta)$-Goldstein stationary point of $h$.

Given the lemma above, we are able to utilize smooth algorithms for finding stationary points, and convert the guarantee to Goldstein-stationary points of our objective of interest.
Specifically, we will invoke the following result.

###### Proposition C.4 ( Lowy et al., 2024 ) .

Given an ERM objective $\tilde{F}(x)=\frac{1}{n}\sum_{i=1}^{n}\tilde{f}(x;\xi_{i})$ with $L_{0}$-Lipschitz and $L_{1}$-smooth components,
and an initial point $x_{0}\in\mathbb{R}^{d}$ such that $\mathrm{dist}(x_{0},\arg\min\tilde{F})\leq R$,
there’s an $(\varepsilon,\delta)$-DP algorithm that returns $\tilde{x}^{\mathrm{out}}$ with $\operatorname*{\mathbb{E}}\|\nabla\tilde{F}(\tilde{x}^{\mathrm{out}})\|=
\widetilde{O}\left(\frac{R^{1/3}L_{0}^{2/3}L_{1}^{1/3}d^{2/3}}{n\varepsilon}+
\frac{L_{0}\sqrt{d}}{n\varepsilon}\right)$.

We remark that we assume for simplicity that $\mathrm{dist}(x_{0},\arg\min\widehat{F}^{\mathcal{D}})=\mathrm{dist}(x_{0},
\arg\min\tilde{F})\leq R$, though the analysis extends to that case where $R$ is the initial distance to a point with sufficiently small loss (e.g., if the infimum is not attained).
Overall,
by setting $\lambda=\alpha/3L$,
and combining
Fact C.2, Lemma C.3 and Proposition C.4, we get the following:

###### Theorem C.5 .

Under Assumption 2.2, suppose $\mathrm{dist}(x_{0},\arg\min\widehat{F}^{\mathcal{D}})\leq R$.
Then there is an $(\varepsilon,\delta)$-DP algorithm that outputs $x^{\mathrm{out}}$ satisfying
$(\alpha,\beta)$-component-wise Goldstein-stationarity (in expectation)
as long as

$$ $\displaystyle n=\widetilde{\Omega}\left(\frac{R^{1/3}L^{4/3}d^{2/3}}{ \varepsilon\alpha^{1/3}\beta}\right).$ $$

###### Fact C.2 .

###### Lemma C.3 .

###### Proposition C.4 ( Lowy et al., 2024 ) .

###### Theorem C.5 .

### C.3 Proofs from Appendix C

###### Proof of Lemma C.3 .

Suppose $x$ is a $\beta$-stationary point of $\tilde{h}_{\lambda\mathrm{LL}}$.
Let $z^{*}\in\mathbb{R}^{d}$ be the solution of the maximization problem defining the LL smoothing. By [Attouch and Aze, , Remark 4.3.e], $z^{*}$ is uniquely defined, and satisfies

$$ $\nabla\tilde{h}_{\lambda\mathrm{LL}}(x)\in\partial(M_{2\lambda}(h))(z^{*}).$ (21) $$

Further denote $\mathcal{Y}^{*}:=\arg\min_{y}\left[h(y)+\frac{1}{4\lambda}\left\|z^{*}-y\right
\|^{2}\right]\subseteq\mathbb{R}^{d}$.
Rearranging the definition of the Moreau envelope by expanding the square, we see that

$$ $M_{2\lambda}(h)(z^{*})=\frac{1}{4\lambda}\left\|z^{*}\right\|^{2}-\frac{1}{2 \lambda}\max_{y}\left[\left\langle z^{*},y\right\rangle-2\lambda h(y)-\frac{1} {2}\left\|y\right\|^{2}\right],$ $$

from which we get

$$ $\partial M_{2\lambda}h(z^{*})=\frac{1}{2\lambda}z^{*}-\frac{1}{2\lambda} \mathrm{conv}\left\{y^{*}:y^{*}\in\mathcal{Y}^{*}\right\}=\mathrm{conv}\left\{ \frac{1}{2\lambda}(z^{*}-y^{*}):y^{*}\in\mathcal{Y}^{*}\right\}.$ (22) $$

Furthermore, for any $y^{*}\in\mathcal{Y}^{*}$, by first-order optimality it holds that

$$ $0\in\partial\left[h(y^{*})+\frac{1}{4\lambda}\left\|y^{*}-z^{*}\right\|^{2} \right]\subseteq\partial h(y^{*})+\frac{1}{2\lambda}(y^{*}-z^{*}),$ $$

and therefore

$$ $\frac{1}{2\lambda}(z^{*}-y^{*})\in\partial h(y^{*}).$ (23) $$

By combining (21), (22) and (23) we conclude that

$$ $\nabla\tilde{h}_{\lambda\mathrm{LL}}(x)\in\partial M_{2\lambda}h(z^{*}) \subseteq\mathrm{conv}\left\{\partial h(y^{*}):y^{*}\in\mathcal{Y}^{*}\right\} \subseteq\partial_{r}h(x),$ $$

where the last holds for $r:=\max_{y^{*}\in\mathcal{Y}^{*}}\|x-y^{*}\|$. Therefore, recalling that $\|\nabla\tilde{h}_{\lambda\mathrm{LL}}(x)\|\leq\beta$, all that remains is to bound $r$.

To that end, it clearly holds that $r\leq\|x-z^{*}\|+\max_{y^{*}\in\mathcal{Y}^{*}}\|z^{*}-y^{*}\|$. Furthermore, by [Attouch and Aze, , Remark 4.3.e] it holds that $z^{*}-x=\lambda\nabla\tilde{h}_{\lambda\mathrm{LL}}(x)$ which implies
$\|x-z^{*}\|=\lambda\beta$.
As to the second summand, by (22) it holds that $\max_{y^{*}\in\mathcal{Y}^{*}}\|z^{*}-y^{*}\|\leq 2\lambda\cdot\max_{g\in
\partial M_{2\lambda}h(z^{*})}\|g\|\leq 2\lambda L$, by the fact that $M_{2\lambda}(h)$ is $L$-Lipschitz. Overall $r\leq\lambda\beta+2\lambda L$, and as we can assume without loss of generality that $\beta\leq L$ since otherwise the claim is trivially true (note that all points are $L$ stationary), this completes the proof.

∎

###### Proof of Lemma C.3 .

## Appendix D Concentration lemma for vectors with sub-Gaussian norm

Here we recall a standard concentration bound for
vectors with sub-Gaussian norm, which notably applies in particular to bounded random vectors.

###### Definition D.1 (Norm-sub-Gaussian) .

We say a random vector $X\in\mathbb{R}^{d}$ is $\zeta$-norm-sub-Gaussian for $\zeta>0$,
if $\Pr[\|X-\operatorname*{\mathbb{E}}X\|\geq t]\leq 2e^{-t^{2}/2\zeta^{2}}$ for all $t\geq 0$.

###### Theorem D.2 (Hoeffding-type inequality for norm-subGaussian, Jin et al., 2019 ) .

Let $X_{1},\cdots,X_{k}\in\mathbb{R}^{d}$ be random vectors, and let $\mathcal{F}_{i}=\sigma(X_{1},\cdots,X_{i})$ for $i\in[k]$ be the corresponding filtration.
Suppose for each $i\in[k]$, $X_{i}\mid\mathcal{F}_{i-1}$ is zero-mean $\zeta_{i}$-norm-sub-Gaussian. Then, there exists an absolute constant $c>0$, such that for any $\gamma>0:$

$$ $\displaystyle\Pr\left[\left\|\sum_{i\in[k]}X_{i}\right\|\geq c\sqrt{\log(d/ \gamma)\sum_{i\in[k]}\zeta_{i}^{2}}\right]\leq\gamma.$ $$

###### Definition D.1 (Norm-sub-Gaussian) .

###### Theorem D.2 (Hoeffding-type inequality for norm-subGaussian, Jin et al., 2019 ) .

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: 1. I am confused by the explanation of the improvement on the non-private term Remark 3.2. The authors explain that
> while the optimal zero-order oracle complexity is d/αβ^3 (Kornowski & Shamir, 2024), and in particular must scale
with the dimension (Duchi et al., 2015), the sample complexity might not.
Since the algorithm is one-pass, then the sample complexity would be worse than the oracle complexity?
2. Is Online-to-Non-Convex conversion optimal? (Related to the weakness above) If not, any algorithms based on it will be suboptimal.
soundness: 3
strengths: - The paper is well-structured and easy to follow.
- The results improve over prior state of the art, establishing the first DP NSNC ERM algorithm with sublinear dim-dependent sample complexity. The non-private term is dimension-independent, which improves over the previous dimensional dependent result in Zhang et al. 2024.
summary: The paper presents algorithms to improve sample complexity in differentially private (DP) nonsmooth, nonconvex (NSNC) optimization. The authors propose two zero-order algorithms that improve the results over Zhang et al. 2024
1. Single-pass, sqrt(d) improvement over Zhang et al. 2024. The authors also establish a dimension-independent “non-private” term, which is not known before for NSNC DP optimization.
2. A multi-pass algorithm further improves the sample complexity, yielding the first algorithm to preform private ERM with sublinear dimension-dependent sample complexity for NSNC objectives.
Additionally, the authors show that Goldstein-stationarity generalizes from the ERM to the population.
weaknesses: My main concern is about contextualizing the contribution:
Like Zhang et al. 2024, this paper also heavily relies on “Online-to-Non-Convex conversion” (O2NC) of Cutkosky et al. (2023). The authors also mention that a lower bound is unknown, making it hard to assess the contribution beyond incremental improvement.

A discussion of the Tree Mechanism is missing. It would be very hard for readers not familiar with the Tree Mechanism to understand.
Typo: page 2 and in particular is the first algorithm to [preform] private ERM

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: - Why did the authors decide to use Gaussian Mechanism instead of the tree mechanism for ERM?
soundness: 3
strengths: - The paper is a fairly simple extension of previous results. The authors are able to improve the past sample complexity by an order of $O(\sqrt{d})$ by using a high probability subgaussian bound on the sensitivity of the queries. 

- The paper also extends the results to other settings.

- The generalization statement (Proposition 5.1) is a cool result to show the validity of the ERM approach for solving the Goldstein-stationary point.

- The paper is well written overall.
summary: This paper studies the problem of designing Differentially Private Algorithms for Nonsmooth Nonconvex Optimization. It specifically studies the zeroth order settings. Thanks to more careful analysis, the paper is able to improve on the dimension dependence of the previous results. It also extends the past result to the ERM settings.
weaknesses: - The paper is basically using the same algorithm proposed by [1]. This is not a huge issue since they are able to make some nice modifications to improve the sample complexity. However, this does limit the potential impact of the paper.

- I also think $m$ is quite large, which would make it really inefficient to run in practice. Currently, m can be something like $O(d^2T^{4/5})$, which is very hard to do in practice.

- It would be interesting if there were some matching upper bounds.

[1] Zhang, Qinzi, Hoang Tran, and Ashok Cutkosky. "Private zeroth-order nonsmooth nonconvex optimization." arXiv preprint arXiv:2406.19579 (2024).

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. The tree mechanism in Algorithm 1 is hard to understand and seems logically inconsistent. Specifically, regarding the function NODE, what is its intended purpose? There appears to be no defined output for NODE. Moreover, in line 13, $k'$ is assigned a value greater than $k$, however, line 14 subsequently tests the condition $k'\le k$, which can never be true. As a result, $S$ remains an empty set and is never updated.

2. In the fourth line of Proposition 2.5, for calculating each $X_i$, should it instead use $\sum_{j=1}^i M_j$  rather than the expression given in the paper  $\sum_{j=1}^i M_i$?

3. In (Cutkoskyetal.,2023), $\Delta_{t+1}$ is updated by $\Delta_{t}+\eta g$ (as stated in their Remark 10), while in Algorithm 2 line 8, $\Delta_{t+1}$ is updated by $\Delta_{t}-\eta g$. Could you clarify the rationale behind this difference?

4. In Theorem 3.1, while the sample complexity has been reduced by a factor of $\Omega(\sqrt{d})$ compared to (Zhang et al., 2024), this comes at the expense of increasing the number of random directions $m$ from $d$ to $d^2$, potentially resulting in a longer runtime.
soundness: 2
strengths: The paper studies an important problem in DP non-convex optimization, and achieves improved sample complexity bounds over existing works.
summary: This paper explores differentially private (DP) optimization algorithms for stochastic and empirical objectives that are non-smooth and non-convex, presenting methods that achieve Goldstein-stationary points with improved sample complexity bounds compared to prior work. The authors introduce a single-pass ($\epsilon$,$\delta$)-DP algorithm capable of producing ($\alpha$,$\beta$)-stationary points. Subsequently, they propose a multi-pass, polynomial-time algorithm that further refines sample efficiency by designing an effective ERM algorithm and demonstrating that Goldstein-stationary points can generalize from the empirical to the population loss.
weaknesses: The presentation is at times unclear, leading to a disjointed reading experience.

Additionally, the paper offers limited technical innovation. Most of the algorithmic framework and techniques appear to be adapted from previous works.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. Is the result in the paper tight? In other words, is there a lower bound provided?

2. What is the key challenge in improving the result by at least $\(\sqrt{d}\)$? Specifically, how does this improvement compare to the results in the referenced work?

3. What role does the (α, β)-Goldstein stationary point play in this paper?

4. What is the novelty of this paper compared to previous works?

5. Can you explain more about the result regarding the non-private term and private and how they contribute to the final result?
soundness: 3
strengths: 1. **Significant Improvement in Sample Complexity**  
   The paper offers a substantial reduction in sample complexity for differentially private (DP) nonsmooth nonconvex (NSNC) optimization. The single-pass algorithm achieves a lower dependence on dimension \(d\) compared to prior work, which is highly impactful for high-dimensional problems in machine learning.

2. **Innovative Use of Goldstein-Stationarity**  
   By focusing on Goldstein-stationary points, the authors leverage a nuanced stationarity condition suitable for nonsmooth nonconvex optimization, allowing for more practical solutions where traditional gradient-based methods fall short. This approach builds on and expands the utility of Goldstein-stationarity in DP settings.

3. **Generalization from Empirical to Population Loss**  
   The paper addresses a theoretical gap by proving that empirical guarantees of Goldstein-stationarity translate to the population loss. This generalization strengthens the theoretical foundation and practical relevance of the proposed algorithms, as it ensures that results on empirical data apply to broader distributions.

4. **Applicability to Real-World DP Machine Learning Tasks**  
   The proposed algorithms are zero-order (using only function evaluations) and thus avoid the need for gradient information, making them suitable for a wider range of machine learning models that may have nonsmooth, nonconvex loss landscapes. This approach is particularly beneficial in privacy-sensitive applications like federated learning.

5. **Novel Dimension-Independent Term**  
   The single-pass algorithm introduces a dimension-independent term in the "non-private" component of the sample complexity, challenging previous assumptions in DP optimization for NSNC objectives. This innovation indicates potential for further sample complexity improvements and opens new directions for DP research in nonconvex settings.
summary: This paper addresses differential privacy (DP) in nonsmooth, nonconvex optimization, aiming to improve sample complexity for finding Goldstein-stationary points in such challenging settings. Traditional DP optimization methods often assume convexity or smoothness, but this work proposes new algorithms that can handle nonsmooth nonconvex (NSNC) objectives.
### Key Contributions

1. **Single-Pass Algorithm**  
   The authors present a single-pass (ε, δ)-DP algorithm that finds an (α, β)-stationary point with improved sample complexity. This algorithm reduces dimensional dependence by a factor of \(\Omega(\sqrt{d})\) over previous approaches, making DP optimization feasible in high-dimensional settings while maintaining privacy guarantees.

2. **Multi-Pass Algorithm**  
   A multi-pass ERM-based algorithm further enhances sample efficiency, allowing the algorithm to iterate over the data multiple times and achieve sublinear dimension-dependent sample complexity. This approach improves convergence while satisfying DP constraints.

3. **Generalization from ERM to Population Loss**  
   The authors establish that Goldstein-stationarity achieved on empirical loss also applies to the population loss with high probability. This result expands the utility of their approach by ensuring that empirical results generalize to the population.


The proposed algorithms make notable progress in DP optimization for NSNC problems, improving sample efficiency while maintaining privacy. This advancement is valuable for practical applications where data privacy is essential, especially in high-dimensional machine learning settings. Additionally, the generalization result strengthens the applicability of Goldstein-stationary points beyond empirical settings.
weaknesses: 1. There is some typo, for instance, line 077 the last word should be perform.

2. Randomized Smoothing is an ordinary technique used in this setting, and I wonder the novelty except for this to deal with the non-smooth setting.

Meta-review: This paper presents new single-pass and multi-pass algorithms for differentially private (DP) optimization of nonsmooth nonconvex. Authors provide new state-of-art art sample complexity for both these types of algorithms. Algorithm similar to Zhang et al., 2024, but authors provide a new analysis utilizing the smoothness of the randomly smoothed envelope to improve sensitivity of zeroth order gradient and therefore improve utility trade off of private optimization. However, many reviewers had concerns about presentation and novelty of the techniques used. Paper also do not provide experimental validation of their results.

Decision: Reject