# Private Zeroth-Order Nonsmooth Nonconvex Optimization

Qinzi Zhang, Hoang Tran & Ashok Cutkosky
Department of Electrical and Computer Engineering
Boston University
Boston, MA, USA
<EMAIL_ADDRESS>
###### Abstract

We introduce a new zeroth-order algorithm for private stochastic optimization
on nonconvex and nonsmooth objectives. Given a dataset of size $M$, our
algorithm ensures $(\alpha,\alpha\rho^{2}/2)$-Rényi differential privacy and
finds a $(\delta,\epsilon)$-stationary point so long as
$M=\tilde{\Omega}\left(\frac{d}{\delta\epsilon^{3}}+\frac{d^{3/2}}{\rho\delta\epsilon^{2}}\right)$.
This matches the optimal complexity of its non-private zeroth-order analog.
Notably, although the objective is not smooth, we have privacy “for free”
whenever $\rho\geq\sqrt{d}\epsilon$.

##  1 Introduction

We study the stochastic optimization problem of the form

$\min_{{\bm{x}}\in\mathbb{R}^{d}}F({\bm{x}})=\mathbb{E}_{z}[f({\bm{x}},z)],$

where the stochastic function $f({\bm{x}},z)$ might be both non-convex and
non-smooth with respect to ${\bm{x}}$. Our focus is on zeroth-order
algorithms, often referred to as gradient-free algorithms. Unlike first-order
algorithms that have access to the stochastic gradient $\nabla f({\bm{x}},z)$,
zeroth-order algorithms can access only the function value $f({\bm{x}},z)$.

Non-convex stochastic optimization is fundamental to modern machine learning.
For example, in deep learning, ${\bm{x}}$ is the weight of some neural network
model, $z$ is a datapoint, and $f({\bm{x}},z)$ represents the loss of the
model evaluated on ${\bm{x}}$ and $z$. Consequently, training the machine
learning model equates to minimizing the non-convex objective $F({\bm{x}})$.
Given its significant role, there has been a marked increase in research
focusing on non-convex optimization in recent years (Ghadimi & Lan, 2013;
Arjevani et al., 2019; 2020; Carmon et al., 2019; Fang et al., 2018; Cutkosky
& Orabona, 2019). Since finding a global minimum of non-convex $F({\bm{x}})$
is intractable, many previous works assume that $F$ is smooth, and their goal
is to find an $\epsilon$-stationary point ${\bm{x}}$ where $\|\nabla
F({\bm{x}})\|\leq\epsilon$. However, objectives are not always smooth,
especially with the ever-increasing complexity of modern machine learning
models. Making the problem even more difficult, recent research shows that
finding an $\epsilon$-stationary point of a non-smooth objective might be
intractable (Zhang et al., 2020; Kornowski & Shamir, 2022).

To address this issue, Zhang et al. (2020) introduces an alternative objective
for the convergence analysis of non-smooth non-convex optimization.
Specifically, they propose the notion of Goldstein stationary point
(Goldstein, 1977): ${\bm{x}}$ is said to be an $(\delta,\epsilon)$-stationary
point of $F$ if there exists a subset $S$ in the ball of radius $\delta$
centered at ${\bm{x}}$ such that $\left\|\mathbb{E}\left[\nabla
F({\bm{y}})\right]\right\|\leq\epsilon$ where ${\bm{y}}$ is uniformly
distributed over $S$. Recently, there have been many works on first-order
algorithms using this framework (Zhang et al., 2020; Tian et al., 2022;
Cutkosky et al., 2023). Notably, Cutkosky et al. (2023) designs an “Online-to-
non-convex Conversion” algorithm that finds a $(\delta,\epsilon)$-stationary
point with $O(\delta^{-1}\epsilon^{-3})$ samples, which is proven to be the
optimal rate. However, first-order algorithms have their own limitations. For
many applications, computing first-order gradients can be computationally
expensive or even impossible (Nelson, 2010; Mania et al., 2018). Hence, there
are many recent results focusing on designing efficient zeroth-order
algorithms for non-smooth non-convex optimization (Lin et al., 2022; Chen et
al., 2023; Kornowski & Shamir, 2023). Recently, Kornowski & Shamir (2023)
proposes a zeroth-order algorithm that requires only
$O(d\delta^{-1}\epsilon^{-3})$ samples, which is the current state-of-the-art
rate for zeroth-order optimization on non-smooth non-convex objectives. The
additional dimension dependence is an inevitable cost of zeroth-order
algorithms even when the objective is smooth or convex (Duchi et al., 2015).

In this paper, we study zeroth-order stochastic optimization on non-convex and
non-smooth objectives. Zeroth-order optimization is particularly important in
cases where memory is constrained or the model is excessively large so that
computing a backwards pass is forbiddingly expensive. In addition, we also aim
to protect the privacy of user’s data. For example, consider the practical
problem of training a recommendation model or a chat response model. At each
step the algorithm is given a set of different users who report the model’s
performance in the form of “upvotes” or “downvotes”. It’s important to make
updates using such zeroth-order feedback while preserving the privacy of
feedback from the individual users.

To this end, we require our algorithm to be differentially private (DP) (Dwork
et al., 2006), which means with high probability, the output of our algorithm
operating on any particular dataset is almost indistinguishable from the
output when one datapoint in the dataset is perturbed.

The primary objective of private stochastic optimization is to minimize the
dataset size required to solve the optimization problem while maintaining
differential privacy guarantees. This area has seen extensive research
efforts. While problems with convex objectives have been well-studied over the
past decade (Chaudhuri et al., 2011; Jain et al., 2012; Kifer et al., 2012;
Bassily et al., 2014; Talwar et al., 2014; Jain & Thakurta, 2014; Bassily et
al., 2019; Feldman et al., 2020; Bassily et al., 2021b; Zhang et al., 2022),
more recent efforts have focused on private non-convex optimization (Wang et
al., 2017; 2019a; Tran & Cutkosky, 2022; Wang et al., 2019b; Zhou et al.,
2020; Bassily et al., 2021a; Arora et al., 2023). Recently, Arora et al.
(2023) designs an algorithm that, assuming the objective is smooth, finds an
$\epsilon$-stationary point and satisfies $(\rho,\gamma)$-DP with
$\tilde{O}(\epsilon^{-3}+\sqrt{d}\rho^{-1}\epsilon^{-2})$ data complexity.
While private non-convex optimization has seen rapid advancements, certain
challenges remain. Many previous studies hinge on the assumption of smooth
objectives since their methods are essentially extensions of non-private non-
convex optimization algorithms. In fact, this limitation emerges even in
situations where the objective is convex, in which case smoothness provides a
critical tool for reducing sensitivity. Since the results in non-smooth non-
convex optimization are recent, its differentially private counterpart remains
largely unexplored.

###  1.1 Our Contributions

The main contribution of this paper is the introduction of a zeroth-order
algorithm for differentially private stochastic optimization on non-convex and
non-smooth objectives. To our knowledge, this is the first work under this
framework. Our algorithm satisfies $(\alpha,\alpha\rho^{2}/2)$-Rényi
differential privacy (RDP) (Mironov, 2017) (which is approximately
$(\rho,\gamma)$-DP) and finds a $(\delta,\epsilon)$-stationary point with
$\tilde{O}(d\delta^{-1}\epsilon^{-3}+d^{3/2}\rho^{-1}\delta^{-1}\epsilon^{-2})$
data complexity. Notably, the non-private term $O(d\delta^{-1}\epsilon^{-3})$
matches the state-of-the-art complexity found in its non-private counterpart.
Moreover, when $\rho\geq\sqrt{d}\epsilon$, the non-private term is dominating,
suggesting that privacy can be attained without additional cost. This is
consistent with the observations when the objective is smooth (Arora et al.,
2023).

Our algorithm incorporates four essential components, each crucial for
achieving the optimal rate. We leverage the non-private Online-to-non-convex
Conversion (O2NC) framework by Cutkosky et al. (2023), which finds a
$(\delta,\epsilon)$-stationary point of a non-smooth objective using a first-
order oracle. We then build an approximate first-order oracle (i.e. a gradient
estimator) with a zeroth-order oracle. Although this high-level strategy is a
common technique, our approach distinguishes itself through its gradient
oracle design. In contrast to prior non-private approaches that directly
approximate the gradient with a standard zeroth-order estimator (Kornowski &
Shamir, 2023), we introduce a variance-reduced gradient oracle. Our approach
incorporates two zeroth-order estimators: one for the gradient and another for
its difference between two points. Our gradient oracle also differs subtly
from the standard zeroth-order estimator by sampling $d$ i.i.d. estimators for
each data point, which is required to achieve the optimal dimension
dependence. Both estimators exhibit reduced sensitivity. We reduce the privacy
cost of our variance-reduced estimators by using the “tree mechanism” (Dwork
et al., 2010; Chan et al., 2011), yielding a new state-of-the-art privacy
guarantee.

Omitting any component from our algorithm significantly impacts the results.
Neither utilizing the O2NC technique nor sampling $d$ i.i.d. estimators
results in an additional dimension dependence of $\sqrt{d}$. Moreover, the
combination of the variance-reduced oracle and the tree mechanism is crucial
for optimal privacy. A naive approach might directly make O2NC private adding
noise to classical zeroth-order gradient estimators, but this yields a sub-
optimal rate with an extra factor of $\epsilon^{-1}$. More details about the
intuitions and challenges of our algorithm can be found in Section 4.1.

##  2 Preliminary

#### Notation

We use bold font ${\bm{x}}$ to denote a vector ${\bm{x}}\in\mathbb{R}^{d}$,
and denote the Euclidean norm of ${\bm{x}}$ by $\|{\bm{x}}\|$. We denote the
unit ball and unit sphere in $\mathbb{R}^{d}$ by $\mathbb{B}$ and $\SS$, and
denote the uniform distribution on $\mathbb{B}$ and $\SS$ by ${\cal
U}_{\mathbb{B}}$ and ${\cal U}_{\SS}$ respectively. We denote an open ball in
$\mathbb{R}^{d}$ centered at ${\bm{x}}$ of radius $r$ by
$B({\bm{x}},r)=\\{{\bm{y}}:\|{\bm{x}}-{\bm{y}}\|<r\\}$. For $n\in\mathbb{N}$,
we denote the set $\\{1,\ldots,n\\}$ by $[n]$, and we denote a sequence
$a_{1},\ldots,a_{n}$ by $a_{1:n}$. We use the standard big-O notation, and use
$\tilde{O}$ to hide additional logarithmic factors. We interchangeably use
$f(x)\lesssim g(x)$ to denote $f(x)=\tilde{O}(g(x))$.

#### Non-smooth Optimization

A function $h:\mathbb{R}^{d}\to\mathbb{R}$ is $L$-Lipschitz if
$|h({\bm{x}})-h({\bm{y}})|\leq L\|{\bm{x}}-{\bm{y}}\|$ for all
${\bm{x}},{\bm{y}}\in\mathbb{R}^{d}$; $h$ is $H$-smooth if it is
differentiable and $\|\nabla h({\bm{x}})-\nabla h({\bm{y}})\|\leq
H\|{\bm{x}}-{\bm{y}}\|$ for all ${\bm{x}},{\bm{y}}\in\mathbb{R}^{d}$. A point
${\bm{x}}^{*}\in\mathbb{R}^{d}$ is an $\epsilon$-stationary point of $h$ if
$\|\nabla h({\bm{x}}^{*})\|\leq\epsilon$.

######  Definition 2.1.

Let $\delta>0$ and $h:\mathbb{R}^{d}\to\mathbb{R}$ be differentiable. The
Goldstein $\delta$-subdifferential of $h$ at ${\bm{x}}$ is
$\partial_{\delta}h({\bm{x}})=\operatorname{conv}(\cup_{y\in
B({\bm{x}},\delta)}\nabla h({\bm{y}}))$. We define $\|\nabla
h({\bm{x}})\|_{\delta}=\inf\\{\|{\bm{g}}\|:{\bm{g}}\in\partial_{\delta}h({\bm{x}})\\}$.
Then ${\bm{x}}^{*}$ is said to be a Goldstein $(\delta,\epsilon)$-stationary
point of $h$ if $\|\nabla h({\bm{x}}^{*})\|_{\delta}\leq\epsilon$. Note that

$\textstyle\|\nabla h({\bm{x}})\|_{\delta}\leq\inf_{S\subset
B({\bm{x}},\delta)}\left\|\frac{1}{|S|}\sum_{{\bm{y}}\in S}\nabla
h({\bm{y}})\right\|.$

#### Differential Privacy

A stochastic optimization algorithm can be considered as a randomized
algorithm that takes a dataset $Z$ (a collection of data points
$z_{1},\ldots,z_{M}$) and outputs an output $\overline{\bm{w}}$. Throughout
this paper, we denote ${\cal Z}$ as the set of all possible datasets of size
$M$. Two datasets $Z,Z^{\prime}\in{\cal Z}$ are neighboring if they differ
only in one data point. A randomized algorithm ${\cal A}:{\cal Z}\to{\cal R}$
is said to be $(\epsilon,\delta)$-differentially private
($(\epsilon,\delta)$-DP) for $\epsilon,\delta>0$ if for all neighboring
datasets $Z,Z^{\prime}$ and measurable $E\subseteq{\cal R}$, we have
$\mathop{\mathbb{P}}\\{{\cal A}(Z)\in E\\}\leq
e^{\epsilon}\mathop{\mathbb{P}}\\{{\cal A}(Z^{\prime})\in E\\}+\delta$ (Dwork
et al., 2006).

Another common privacy measure is Rényi differential privacy (RDP). Algorithm
${\cal A}$ is $(\alpha,\rho)$-RDP for $\alpha>1,\rho>0$ if for all neighboring
$Z,Z^{\prime}$, $D_{\alpha}({\cal A}(Z)\|{\cal A}(Z^{\prime}))\leq\rho$
(Mironov, 2017), where $D_{\alpha}(\mu\|\nu)$ is the Rényi divergence of
distributions $\mu,\nu$. RDP can be converted to $(\epsilon,\delta)$-DP as
follows: if an algorithm is $(\alpha,\alpha\rho^{2}/2)$-RDP for all
$\alpha>1$, then it is also $(2\rho\ln(1/\delta)^{1/2},\delta)$-DP for all
$\delta\geq\exp(-\rho^{2})$ (Mironov, 2017, Proposition 3). Therefore, we use
$(\alpha,\alpha\rho^{2}/2)$-RDP as a measure of differential privacy in our
paper.

If $\|{\cal A}(Z)-{\cal A}(Z^{\prime})\|\leq s$ for any neighboring
$Z,Z^{\prime}$, we say the sensitivity of ${\cal A}$ is bounded by $s$. It is
well known that in this case, adding a Gaussian noise ${\cal
N}(0,\sigma^{2}I)$ to the output of ${\cal A}$, where $\sigma=s/\rho$, ensures
that ${\cal A}$ is $(\alpha,\alpha\rho^{2}/2)$-RDP (Mironov, 2017).

We also make use of the “tree mechanism” Dwork et al. (2010); Chan et al.
(2011), which is a technique that allows for private release of _running sums_
of potentially sensitive data (Algorithm 5).

#### Online Learning

Our algorithm builds on the Online-to-non-convex algorithm by Cutkosky et al.
(2023), so we briefly introduce the setting of online convex optimization
(OCO) (Cesa-Bianchi & Lugosi, 2006; Hazan, 2019; Orabona, 2019). An OCO
algorithm proceeds in rounds. In each round $t$, it outputs ${\bm{x}}_{t}$,
receives a convex loss function $\ell_{t}({\bm{x}})$, and suffers loss
$\ell_{t}({\bm{x}}_{t})$. It is common to use a linear loss
$\ell_{t}({\bm{x}})=\langle{\bm{v}}_{t},{\bm{x}}\rangle$. An OCO algorithm has
domain bounded by $D$ if $\|{\bm{x}}_{t}\|\leq D$ for all $t$.

The goal of online learning is to minimize the static regret defined as

$\textstyle\mathrm{Reg}_{T}({\bm{u}})=\sum_{t=1}^{T}\ell_{t}({\bm{x}}_{t})-\ell_{t}({\bm{u}})=\sum_{t=1}^{T}\langle{\bm{v}}_{t},{\bm{x}}_{t}-{\bm{u}}\rangle,$

where ${\bm{u}}$ is some comparator vector (often,
${\bm{u}}=\operatorname*{arg\,min}\sum_{t=1}^{T}\ell_{t}({\bm{x}})$). There
are many OCO algorithms that achieve the minimax optimal $O(\sqrt{T})$ regret.
For example, projected Online Subgradient Descent (OSD) (Zinkevich, 2003) with
domain bounded by $D$ satisfies

$\textstyle\mathbb{E}[\mathrm{Reg}_{T}({\bm{x}})]\leq
D\sqrt{\sum_{t=1}^{T}\mathbb{E}\|{\bm{v}}_{t}\|^{2}}.$

#### Uniform Smoothing

Randomized smoothing is a well known technique that converts a possibly non-
smooth function to a smooth approximation (Flaxman et al., 2005; Duchi et al.,
2012; Lin et al., 2022). Given a Lipschitz function
$h:\mathbb{R}^{d}\to\mathbb{R}$ and $\delta>0$, we define the uniform
smoothing of $h$ as $\hat{h}_{\delta}({\bm{x}})=\mathbb{E}_{{\bm{v}}\sim{\cal
U}_{\mathbb{B}}}[h({\bm{x}}+\delta{\bm{v}})]$. In later sections, we denote
$\hat{F}_{\delta}({\bm{x}})$ and $\hat{f}_{\delta}({\bm{x}},z)$ as the uniform
smoothing of the objective $F({\bm{x}})$ and $f({\bm{x}},z)$ respectively. As
shown in prior works (see (Yousefian et al., 2012) and Duchi et al. (2012,
Section E)), uniform smoothing is a smooth approximation whose gradient can be
estimated by finite differentiation. We rephrase the key properties in the
following lemma, whose proof is presented in the appendix for completeness.

######  Lemma 2.2.

Suppose $h:\mathbb{R}^{d}\to\mathbb{R}$ is $L$-Lipschitz. Then (i)
$\hat{h}_{\delta}$ is $L$-Lipschitz; (ii)
$\|\hat{h}_{\delta}({\bm{x}})-h({\bm{x}})\|\leq L\delta$; (iii)
$\hat{h}_{\delta}$ is differentiable and $\frac{\sqrt{d}L}{\delta}$-smooth;
(iv)

$\nabla\hat{h}_{\delta}({\bm{x}})=\mathbb{E}_{{\bm{u}}\sim{\cal
U}_{\SS}}[\tfrac{d}{\delta}h({\bm{x}}+\delta{\bm{u}}){\bm{u}}]=\mathbb{E}_{{\bm{u}}\sim{\cal
U}_{\SS}}[\tfrac{d}{2\delta}(h({\bm{x}}+\delta{\bm{u}})-h({\bm{x}}-\delta{\bm{u}})){\bm{u}}];$

As a corollary, finding an $(\delta,\epsilon)$-stationary point of
$\hat{F}_{\delta}$ is sufficient to find an $(2\delta,\epsilon)$-stationary
point of $F$. The formal statement is as follows (Kornowski & Shamir (2023,
Lemma 4); proof is presented in Appendix A for completeness).

######  Corollary 2.3.

Suppose $F:\mathbb{R}^{d}\to\mathbb{R}$ is $L$-Lipschitz. Then for any
$\epsilon,\delta>0$,
$\|\nabla\hat{F}_{\delta}({\bm{x}})\|_{\delta}\leq\epsilon$ implies that
$\|\nabla F({\bm{x}})\|_{2\delta}\leq\epsilon$.

###  2.1 Analysis Organization

As a brief overview, our algorithm leverages O2NC to privately optimize the
uniform smoothing of the objective. Note that O2NC does not require any
smoothness itself - we employ uniform smoothing because it allows us to
construct a low-sensitivity gradient oracle from a zeroth-order oracle. The
smoothness property is tangential. We construct a variance-reduced gradient
oracle for O2NC and incorporate the tree mechanism for enhanced privacy. This
oracle is based on two zeroth-order estimators: one for the stochastic
gradient of the uniform smoothing and another for the gradient difference.

This paper is organized in the following order. In Section 3, we introduce the
zeroth-order estimators. In Section 4.1, we present the O2NC algorithm
combined with the private variance-reduced gradient oracle. In Section 4.2, we
demonstrate the improved privacy guarantee provided by the tree mechanism. We
conclude with the convergence analysis in Section 4.3.

##  3 Zeroth-Order Estimators

Let $F({\bm{x}})=\mathbb{E}_{z}[f({\bm{x}},z)]$ and denote $\hat{F}_{\delta}$
and $\hat{f}_{\delta}$ as the uniform smoothing of $F$ and $f$ respectively.
Using the randomized smoothing technique from Lemma 2.2, we can construct
unbiased zeroth-order estimators for both $\nabla\hat{F}_{\delta}({\bm{x}})$
and $\nabla\hat{F}_{\delta}({\bm{x}})-\nabla\hat{F}_{\delta}({\bm{y}})$. The
key properties of these estimators Grad and Diff, as defined in Algorithm 1
and 2, are summarized in the following results.

######  Lemma 3.1.

If $f({\bm{x}},z)$ is differentiable and $L$-Lipschitz in ${\bm{x}}$, then for
any $\delta>0,{\bm{x}}\in\mathbb{R}^{d}$ and neighboring data batches
$z_{1:b},z^{\prime}_{1:b}$ of size $b$,

$\displaystyle\mathbb{E}[\textsc{Grad}_{f,\delta}({\bm{x}},z_{1:b})]=\nabla\hat{F}_{\delta}({\bm{x}}),$
(unbiased)
$\displaystyle\mathbb{E}\|\textsc{Grad}_{f,\delta}({\bm{x}},z_{1:b})-\nabla\hat{F}_{\delta}({\bm{x}})\|^{2}\leq\tfrac{16dL^{2}}{b},$
(variance)
$\displaystyle\|\textsc{Grad}_{f,\delta}({\bm{x}},z_{1:b})-\textsc{Grad}_{f,\delta}({\bm{x}},z^{\prime}_{1:b})\|\leq\tfrac{2dL}{b}.$
(sensitivity)

######  Lemma 3.2.

If $f({\bm{x}},z)$ is differentiable and $L$-Lipschitz in ${\bm{x}}$, then for
any $\delta>0$, ${\bm{x}},{\bm{y}}\in\mathbb{R}^{d}$ and neighboring data
batches $z_{1:b},z^{\prime}_{1:b}$ of size $b$,

$\displaystyle\mathbb{E}[\textsc{Diff}_{f,\delta}({\bm{x}},{\bm{y}},z_{1:b})]=\nabla\hat{F}_{\delta}({\bm{x}})-\nabla\hat{F}_{\delta}({\bm{y}}),$
(unbiased)
$\displaystyle\mathbb{E}\|\textsc{Diff}_{f,\delta}({\bm{x}},{\bm{y}},z_{1:b})-[\nabla\hat{F}_{\delta}({\bm{x}})-\nabla\hat{F}_{\delta}({\bm{y}})]\|^{2}\leq\tfrac{16dL^{2}}{b\delta^{2}}\|{\bm{x}}-{\bm{y}}\|^{2},$
(variance)
$\displaystyle\|\textsc{Diff}_{f}({\bm{x}},{\bm{y}},z_{1:b})-\textsc{Diff}_{f}({\bm{x}},{\bm{y}},z^{\prime}_{1:b})\|\leq\tfrac{2dL}{b\delta}\|{\bm{x}}-{\bm{y}}\|.$
(sensitivity)

Algorithm 1 Zeroth-order gradient oracle
$\textsc{Grad}_{f,\delta}({\bm{x}},z_{1:b})$

1:Input: loss function $f$, constant $\delta>0$, parameter ${\bm{x}}$, i.i.d.
data batch $z_{1:b}$

2:Sample ${\bm{u}}_{11},\ldots,{\bm{u}}_{bd}\sim\mathrm{Uniform}(\SS)$ i.i.d.

3:Return
$\textsc{Grad}_{f,\delta}({\bm{x}},z_{1:b})=\frac{1}{b}\sum_{i=1}^{b}\frac{1}{d}\sum_{j=1}^{d}\frac{d}{2\delta}(f({\bm{x}}+\delta{\bm{u}}_{ij},z_{i})-f({\bm{x}}-\delta{\bm{u}}_{ij},z_{i})){\bm{u}}_{ij}$.

Algorithm 2 Zeroth-order gradient difference oracle
$\textsc{Diff}_{f,\delta}({\bm{x}},{\bm{y}},z_{1:b})$

1:Input: loss function $f$, constant $\delta>0$, parameter
${\bm{x}},{\bm{y}}$, i.i.d. data batch $z_{1:b}$

2:Sample ${\bm{u}}_{11},\ldots,{\bm{u}}_{bd}\sim\mathrm{Uniform}(\SS)$ i.i.d.

3:Return
$\textsc{Diff}_{f,\delta}({\bm{x}},{\bm{y}},z_{1:b})=\frac{1}{b}\sum_{i=1}^{b}\frac{1}{d}\sum_{j=1}^{d}\frac{d}{\delta}(f({\bm{x}}+\delta{\bm{u}}_{ij},z_{i})-f({\bm{y}}+\delta{\bm{u}}_{ij},z_{i})){\bm{u}}_{ij}$.

Proofs for Lemmas 3.1 and 3.2 are both stemming from the uniform smoothing
properties detailed in Lemma 2.2. We defer the proofs to Appendix B. Notably,
these lemmas indicate that both the gradient and gradient difference
estimators are unbiased, with low variance and sensitivity. Specifically, in
our final algorithm, we will be able to control the distance between
parameters ${\bm{x}},{\bm{y}}$ in two successive iterations by $\delta/T$. As
a result, the variance in Lemma 3.2 is bounded by $O({dL^{2}}/{bT^{2}})$, and
its sensitivity is bounded by $O({dL}/{bT})$. Using these estimators, we
construct zeroth-order gradient oracles by exploiting the decomposition
$\nabla\hat{F}_{\delta}({\bm{x}}_{t})=\nabla\hat{F}_{\delta}({\bm{x}}_{1})+\sum_{i=1}^{t}\nabla\hat{F}_{\delta}({\bm{x}}_{i})-\nabla\hat{F}_{\delta}({\bm{x}}_{i-1})\approx\textsc{Grad}_{f,\delta}({\bm{x}}_{1},z)+\sum_{i=1}^{t}\textsc{Diff}_{f,\delta}({\bm{x}}_{i},{\bm{x}}_{i-1},z)$.
Our constructed oracles have low variance and low sensitivity, thus allowing
us to incorporate the tree mechanism to privately aggregate the sum with less
noise. A more detailed exploration of this idea is presented in the subsequent
sections, especially in Corollary 4.4 and Lemma 4.8.

In addition, we would like to discuss the rationale behind sampling $d$ i.i.d.
uniform vectors ${\bm{u}}_{ij}$ for each data point $z_{i}$. For the gradient
estimator grad, it is feasible to approximate
$\nabla\hat{f}_{\delta}({\bm{x}},z_{i})$ with a single two-point estimator,
namely
${\bm{g}}_{i}=\frac{d}{2\delta}(f({\bm{x}}+\delta{\bm{u}},z_{i})-f({\bm{x}}-\delta{\bm{u}},z_{i})){\bm{u}}$,
as it is proved that $\mathbb{E}\|{\bm{g}}_{i}\|^{2}=O(dL^{2})$ (Shamir, 2017,
Lemma 10). The central argument hinges on a concentration inequality for
Lipschitz functions, which states that if $h$ is $L$-Lipschitz on ${\bm{u}}$
and ${\bm{u}}\sim{\cal U}_{\SS}$, then
$\mathop{\mathbb{P}}\\{|h({\bm{u}})-\mathbb{E}h({\bm{u}})|\geq t\\}\leq
2\exp(-\frac{dt^{2}}{2L^{2}})$, as per (Wainwright, 2019) Proposition 3.11. In
the context of their proof, $h({\bm{u}})=f({\bm{x}}+\delta{\bm{u}})$ which is
$L\delta$-Lipschitz.

However, this argument isn’t applicable to the gradient difference estimator
diff. In order to apply the concentration inequality, we need to bound the
Lipschitz constant of
$h({\bm{u}})=f({\bm{x}}+\delta{\bm{u}})-f({\bm{y}}+\delta{\bm{u}})$. Although
this function is indeed $2L\delta$-Lipschitz, using this would bound the
variance at $O(dL^{2})$, which doesn’t match our target of $O(dL^{2}/T^{2})$.
On the other hand, directly using the Lipschitzness of $f$ bounds
$\mathbb{E}\|\frac{d}{\delta}(f({\bm{x}}+\delta{\bm{u}},z_{i})-f({\bm{y}}+\delta{\bm{u}},z_{i})){\bm{u}}\|^{2}\leq(\frac{dL}{\delta}\|{\bm{x}}-{\bm{y}}\|)^{2}=O(d^{2}L^{2}/T^{2})$.
Consequently, we need to sample $d$ i.i.d. uniform vectors to reduce the
dimension dependence of the variance by a factor of $d$ in order to match the
optimal rate. While a more efficient analysis that avoids sampling $d$ uniform
vectors might exist, we are currently unaware of it.

##  4 Our Algorithm and Results

Algorithm 3 Online-to-Nonconvex Conversion

1:Input: OCO algorithm ${\cal A}$ with domain $D$, gradient oracle ${\cal O}$,
initial state ${\bm{x}}_{1}$.

2:for $k=1,2,\ldots,K$ do

3: for $t=1,2,\ldots,T$ do

4: Receive $\Delta_{t}^{k}$ from ${\cal A}$. (For example,
$\Delta_{1}^{k}\leftarrow 0$ and
$\Delta_{t}^{k}\leftarrow\Pi_{D}(\Delta_{t-1}^{k}-\eta\tilde{\bm{g}}_{t-1}^{k}),t\geq
2$.)

5: Update ${\bm{x}}_{t+1}^{k}\leftarrow{\bm{x}}_{t}^{k}+\Delta_{t}^{k}$ and
${\bm{w}}_{t}^{k}\leftarrow{\bm{x}}_{t}^{k}+s_{t}^{k}\Delta_{t}^{k}$, where
$s_{t}^{k}\sim\mathrm{Uniform}([0,1])$.

6: Query gradient estimator $\tilde{\bm{g}}_{t}^{k}$ from ${\cal O}$.

7: Send $\ell_{t}^{k}(\cdot)=\langle\tilde{\bm{g}}_{t}^{k},\cdot\rangle$ to
${\cal A}$ and ${\cal A}$ updates $\Delta_{t+1}^{k}$.

8: end for

9: Compute
$\overline{\bm{w}}^{k}\leftarrow\frac{1}{T}\sum_{t=1}^{T}{\bm{w}}_{t}^{k}$.

10: Reset ${\bm{x}}_{1}^{k+1}\leftarrow{\bm{x}}_{T+1}^{k}$ and restart ${\cal
A}$.

11:end for

12:Output
$\overline{\bm{w}}\sim\mathrm{Uniform}(\\{\overline{\bm{w}}^{1},\ldots,\overline{\bm{w}}^{K}\\})$.

###  4.1 Private Online-to-Non-Convex Conversion

Our algorithm builds on the Online-to-Nonconvex Conversion (O2NC) by (Cutkosky
et al., 2023), which is a general framework that converts any OCO algorithm
with $O(\sqrt{T})$ regret into a nonsmooth nonconvex optimization algorithm
that finds a $(\delta,\epsilon)$-stationary point in
$O(\delta^{-1}\epsilon^{-3})$ iterations. The pseudo-code of this framework is
presented in Algorithm 3. Specifically, our algorithm chooses projected Online
Subgradient Descent (OSD) as the OCO algorithm, which updates $\Delta_{t}^{k}$
in line 3 of Algorithm 3 following the explicit update rule:
$\Delta_{1}^{k}\leftarrow 0$ and
$\Delta_{t}^{k}\leftarrow\Pi_{D}(\Delta_{t-1}^{k}-\eta\tilde{\bm{g}}_{t-1}^{k})$
for $t\geq 2$. Here
$\Pi_{D}({\bm{x}})=\operatorname*{arg\,min}_{\|{\bm{y}}\|\leq
D}\|{\bm{x}}-{\bm{y}}\|$ denotes the projection operator and $\eta$ is the
stepsize tuned by OSD. Regarding notations in Algorithm 3, there are two round
indices $t$ and $k$, and we use the subscript $t$ and superscript $k$, namely
${\bm{x}}_{t}^{k}$, to denote a variable ${\bm{x}}$ in outer loop $k$ and
inner loop $t$.

The selection of O2NC as our base non-private algorithm is deliberate and
influenced by the literature of non-private zeroth-order algorithms in
nonsmooth nonconvex optimization. Intuitively, in the realm of privacy, a
variance-reduction algorithm is more appealing due to its inherently low
sensitivity. However, a straightforward application of variance-reduced SGD
paired with zeroth-order estimators only achieves a sub-optimal dimension
dependence of $O(d^{3/2}\delta^{-1}\epsilon^{-3})$, as shown in (Chen et al.,
2023). A recent advancement by Kornowski & Shamir (2023) has improved the rate
to $O(d\delta^{-1}\epsilon^{-3})$. Central to their achievement is the
observation that finding a $(2\delta,\epsilon)$-stationary point of a
nonsmooth objective $F$ is equivalent to finding a
$(\delta,\epsilon)$-stationary point of its uniform smoothing
$\hat{F}_{\delta}$. Previous zeroth-order algorithms aim to find an
$\epsilon$-stationary point of $\hat{F}_{\delta}$ via smooth optimization
algorithms such as variance-reduced SGD, resulting in an additional smoothness
cost of order $O(\sqrt{d})$. In contrast, the algorithm proposed by Kornowski
& Shamir (2023) leverages O2NC to find a $(\delta,\epsilon)$-stationary point,
achieving a linear dimension dependence.

Informed by the insights of (Kornowski & Shamir, 2023), we adopt O2NC as our
foundational non-private algorithm. Specifically, we adapt Algorithm 3 for
privacy by substituting the gradient oracle ${\cal O}$ in line 5 with a more
carefully designed private oracle. A main challenge in this design is to
minimize _sensitivity_ , which is required to ensure privacy. In the algorithm
proposed by Kornowski & Shamir (2023), the gradient oracle is simply the
zeroth-order gradient estimator,
$\tilde{\bm{g}}_{t}^{k}=\frac{d}{2\delta}(f({\bm{w}}_{t}^{k}+\delta{\bm{u}},z_{t}^{k})-f({\bm{w}}_{t}^{k}+\delta{\bm{u}},z_{t}^{k})){\bm{u}}$,
whose sensitivity is $O(dL)$. A straightforward method to ensure privacy for
this algorithm is by directly adding Gaussian noise with variance
$O(d^{2}L^{2}/\rho^{2})$. While this might seem intuitive, it leads to
significantly worse data complexity. Specifically, the resulting rate is
$O(d^{3/2}\rho^{-1}\delta^{-1}\epsilon^{-3})$, which is worse by a factor of
$\epsilon^{-1}$ when compared to our proposed algorithm - and importantly
_does not_ admit any value of $\rho$ for which we obtain the non-private
convergence rate. For interested readers, we include the detailed analysis of
this naive approach in Appendix E.

In contrast, we designed a more refined private gradient oracle in Algorithm
4. According to Lemma 3.1 and 3.2, the sensitivity of ${\bm{g}}_{1}^{k}$ is
$O(dL/B_{1})$, while that of ${\bm{d}}_{t}^{k}$ is
$O(dL\|{\bm{w}}_{t}^{k}-{\bm{w}}_{t-1}^{k}\|/B_{2}\delta)$. Setting
$B_{1}=T,B_{2}=1$, and using Remark 4.1 with $D=\delta/T$, both
${\bm{g}}_{1}^{l}$ and ${\bm{d}}_{t}^{k}$ have sensitivity $O(dL/T)$. With
these settings, we can apply the tree mechanism, a useful technique to release
sums of private algorithms, ensuring that the variance-reduced gradient
$\tilde{\bm{g}}_{t}^{k}$ achieves $(\alpha,\alpha\rho^{2}/2)$-RDP.
Specifically, the tree mechanism adds noise of order
$\tilde{O}(d^{2}L^{2}/\rho^{2}T^{2})$ to each $\tilde{\bm{g}}_{t}^{k}$.
Compared to the aforementioned naive approach, our refined approach reduces
noise by a factor of $T^{2}$, thus resulting in the desired data complexity.

######  Remark 4.1.

Note that
${\bm{w}}_{t+1}^{k}={\bm{x}}_{t+1}^{k}+s_{t+1}^{k}\Delta_{t+1}^{k}={\bm{w}}_{t}^{k}+(1-s_{t}^{k})\Delta_{t}^{k}+s_{t+1}^{k}\Delta_{t+1}^{k}$.
Therefore, if the OCO algorithm has domain bounded by $D$ (i.e.,
$\|\Delta_{t}^{k}\|\leq D$ for all $t,k$), then
$\|{\bm{w}}_{t+1}^{k}-{\bm{w}}_{t}^{k}\|\leq 2D$. In general, for all
$t,t^{\prime}\in[T]$, $\|{\bm{w}}_{t}^{k}-{\bm{w}}_{t^{\prime}}^{k}\|\leq
2|t-t^{\prime}|D$.

Algorithm 4 Private variance-reduced gradient oracle ${\cal O}$

1:Input: dataset ${\cal Z}$, constants $B_{1},B_{2}$

2:Initialize: Partition ${\cal Z}$ into $KT$ subsets: $Z_{1}^{k}$ of size
$B_{1}$ for $k\in[K]$ and $Z_{t}^{k}$ of size $B_{2}$ for $t=[2,K],k\in[K]$.
The total data size is $|{\cal Z}|=M=K(B_{1}+B_{2}(T-1))$.

3:Upon receiving round index $k,t$ and parameters ${\bm{w}}_{t}^{k}$:

4:if $t=1$ then

5: Query
${\bm{g}}_{1}^{k}\leftarrow\textsc{Grad}_{f,\delta}({\bm{w}}_{1}^{k},Z_{1}^{k})$.

6:else

7: Query
${\bm{d}}_{t}^{k}\leftarrow\textsc{Diff}_{f,\delta}({\bm{w}}_{t}^{k},{\bm{w}}_{t-1}^{k},Z_{t}^{k})$
and compute ${\bm{g}}_{t}^{k}\leftarrow{\bm{g}}_{t-1}^{k}+{\bm{d}}_{t}^{k}$.

8:end if

9:Return
$\tilde{\bm{g}}_{t}^{k}\leftarrow\tilde{\bm{g}}_{t}^{k}+\textsc{Tree}(t)$.

1:Input: Index $t\in[T]$, global variables $\sigma_{1},\ldots,\sigma_{T}$.

2:If $t=1$, set $\textsc{Noise}\leftarrow\\{\\}$.

3:Sample $\xi_{t}\sim N(0,\sigma_{t}^{2}I)$ and store $\xi_{t}$ in Noise.

4:Return $\sum_{(\cdot,i)\in\textsc{Node}(t)}\xi_{i}$.

5:function Node(t)

6: Initialize: Set $k\leftarrow 0$ and $S\leftarrow\\{\\}$.

7: for $i=0,\ldots,\lceil\log_{2}(t)\rceil$ while $k<t$ do

8: Set $k^{\prime}\leftarrow k+2^{\lceil\log_{2}(t)\rceil-i}$. If
$k^{\prime}\leq t$, store $S\leftarrow S\cup\\{(k+1),k^{\prime}\\}$ and update
$k\leftarrow k^{\prime}$.

9: end for

10: Return $S$.

11:end function

Algorithm 5 Tree Mechanism

###  4.2 Privacy Guarantee

To ensure the privacy of the Online-to-Nonconvex conversion, we use a variant
of the tree mechanism, as defined in Algorithm 5, to privately aggregate the
sum of ${\bm{g}}_{1}^{k}$ and ${\bm{d}}_{t}^{k}$. The privacy guarantee of the
tree mechanism is presented in Theorem 4.3, and the proof is presented in
Append C.1. Intuitively, the tree mechanism says if each of the algorithms
${\cal M}_{1},\ldots,{\cal M}_{n}$ requires $\sigma^{2}$ noise for privacy,
then the sum $\sum_{i=1}^{n}{\cal M}_{i}$ only needs $O(\ln(n)\sigma^{2})$
noise for the same level of privacy. With Theorem 4.3, we determine the
minimal noise required to ensure privacy for Algorithm 3 in Corollary 4.4, and
we evaluate the total noise added by the tree mechanism in Corollary 4.5.

######  Remark 4.2.

To better understand the Node function in Algorithm 5, consider a binary tree
of depth $\lceil\log_{2}(t)\rceil$. $\textsc{Node}(t)$ returns the largest
node $n_{i}$ in each layer $i$, if exists, such that $n_{j}<n_{i}\leq t$
starting from the top level. As an example,
$\textsc{Node}(7)=\\{(1,4),(5,6),(7,7)\\}$ and $\textsc{Node}(8)=\\{(1,8)\\}$.
In particular, note that $|\textsc{node}(t)|\leq\lceil\log_{2}(t)\rceil\leq
2\ln(t)$.

Next, we present the main privacy theorem for the tree mechanism as presented
in Algorithm 5.

######  Theorem 4.3.

Let ${\cal X}$ be state space and ${\cal Z}^{(1)},\ldots,{\cal Z}^{(n)}$ be
dataset spaces, and denote ${\cal Z}^{(1:i)}={\cal
Z}^{(1)}\times\dotsm\times{\cal Z}^{(i)}$. Let ${\cal M}^{(i)}:{\cal
X}^{i-1}\times{\cal Z}^{(i)}\to{\cal X}$ be a sequence of algorithms for
$i\in[n]$, and let ${\cal A}:{\cal Z}^{(1:n)}\to{\cal X}^{n}$ be the algorithm
that, given a dataset $Z_{1:n}\in{\cal Z}^{(1:n)}$, sequentially computes
${\bm{x}}_{i}=\sum_{j=1}^{i}{\cal
M}^{(j)}({\bm{x}}_{1:j-1},Z_{i})+\textsc{Tree}(i)$ for $i\in[n]$ and then
outputs ${\bm{x}}_{1:n}$. Suppose for all $i\in[n]$ and neighboring
$Z_{1:n},Z_{1:n}^{\prime}\in{\cal Z}^{(1:n)}$, $\|{\cal
M}^{(i)}({\bm{x}}_{1:i-1},Z_{i})-{\cal
M}^{(i)}({\bm{x}}_{1:i-1},Z_{i}^{\prime})\|\leq s_{i}$ for all auxiliary
inputs ${\bm{x}}_{1:i-1}\in{\cal X}^{i-1}$. Then for all $\alpha>1$, ${\cal
A}$ is $(\alpha,\alpha\rho^{2}/2)$-RDP where

$\rho\leq\sqrt{2\ln n}\cdot\max_{b\in[n],i\leq b}\frac{s_{i}}{\sigma_{b}}.$

In our case, ${\cal X}$ is the collection of weights ${\bm{x}}$ for
$f({\bm{x}},z)$, ${\cal Z}^{(1)}$ is the collection of all possible batches
$Z_{1}^{k}$ of size $B_{1}$ defined in Algorithm 3 and ${\cal Z}^{(t)}$ for
$t\geq 2$ is the collection of all possible batches $Z_{t}^{k}$ of size
$B_{2}$. Moreover, ${\cal M}^{(1)}$ corresponds to Grad that computes
${\bm{g}}_{1}^{k}$ and ${\cal M}^{(t)}$ corresponds to Diff that computes
${\bm{d}}_{t}^{k}$. Upon substituting these specific definition into Theorem
4.3, we have the following privacy guarantees.

######  Corollary 4.4.

Suppose $f({\bm{x}},z)$ is differentiable and $L$-Lipschitz in ${\bm{x}}$ and
the domain of ${\cal A}$ is bounded by $D={\delta}/{T}$. Let $B_{1},B_{2}$
satisfies $B_{1}\geq TB_{2}/2$. Then for any $\alpha>1,\rho>0$, Algorithm 3 is
$(\alpha,\alpha\rho^{2}/2)$-RDP if we set the noises $\sigma_{1:T}$ in the
tree mechanism as

$\sigma_{t}=\sigma:=\frac{\sqrt{2\ln T}4dL}{B_{2}T\rho}.$

######  Corollary 4.5.

Following the assumptions and definitions in Corollary 4.4, for all $t\in[T]$,

$\mathbb{E}\|\textsc{Tree}(t)\|^{2}\leq
2\ln(t)d\sigma^{2}\leq\left(\frac{8\ln(T)d^{3/2}L}{B_{2}T\rho}\right)^{2}.$

###  4.3 Convergence Analysis

To start the convergence analysis, we revisit the convergence result of the
non-private O2NC algorithm as presented in Lemma 4.6 whose proof is included
in Appendix D for completeness. Building upon the observation in Corollary
2.3, our objective shifts to finding a $(\delta,\epsilon)$-stationary point of
the uniform smoothing $\hat{F}_{\delta}$, as opposed to directly optimizing
$F$. This approach leads to the formulation of Corollary 4.7. Missing proofs
in this section are deferred to Appendix D.

######  Lemma 4.6.

For any function $F:\mathbb{R}^{d}\to\mathbb{R}$ that is differentiable and
$F({\bm{x}}_{1})-\inf_{{\bm{x}}}F({\bm{x}})\leq F^{*}$, if the domain of the
OCO algorithm ${\cal A}$ is bounded by $D=\delta/T$, then

$\mathbb{E}\|\nabla
F(\overline{\bm{w}})\|_{\delta}\leq\frac{F^{*}}{DKT}+\sum_{k=1}^{K}\frac{\mathbb{E}\mathrm{Reg}_{T}({\bm{u}}^{k})}{DKT}+\sum_{k=1}^{K}\sum_{t=1}^{T}\frac{\mathbb{E}\langle\nabla
F({\bm{w}}_{t}^{k})-\tilde{\bm{g}}_{t}^{k},\Delta_{t}^{k}-{\bm{u}}^{k}\rangle}{DKT}.$

where ${\bm{u}}^{k}=-D\frac{\sum_{t=1}^{T}\nabla
F({\bm{w}}_{t}^{k})}{\|\sum_{t=1}^{T}\nabla F({\bm{w}}_{t}^{k})\|}$.

######  Corollary 4.7.

Suppose $F:\mathbb{R}^{d}\to\mathbb{R}$ is differentiable, $L$-Lipschitz, and
$F({\bm{x}}_{1})-\inf_{\bm{x}}F({\bm{x}})\leq F^{*}$, and suppose the domain
of ${\cal A}$ is bounded by $D=\delta/T$. Then

$\mathbb{E}\|\nabla
F(\overline{\bm{w}})\|_{2\delta}\leq\frac{F^{*}+2L\delta}{DKT}+\sum_{k=1}^{K}\frac{\mathbb{E}\mathrm{Reg}_{T}(\hat{\bm{u}}^{k})}{DKT}+\sum_{k=1}^{K}\sum_{t=1}^{T}\frac{\mathbb{E}\langle\nabla\hat{F}_{\delta}({\bm{w}}_{t}^{k})-\tilde{\bm{g}}_{t}^{k},\Delta_{t}^{k}-\hat{\bm{u}}^{k}\rangle}{DKT}.$

where
$\hat{\bm{u}}^{k}=-D\frac{\sum_{t=1}^{T}\nabla\hat{F}_{\delta}({\bm{w}}_{t}^{k})}{\|\sum_{t=1}^{T}\nabla\hat{F}_{\delta}({\bm{w}}_{t}^{k})\|}$.

Next, we introduce a key result in our convergence analysis. At its core,
Lemma 4.8 suggests that the variance of the non-private gradient oracle,
defined as ${\bm{g}}_{t}^{k}$ in Algorithm 4, is approximately $O(dL^{2}/T)$.
This result leads to the non-private term of $O(d\delta^{-1}\epsilon^{-3})$ in
the data complexity, matching the optimal rate in non-private contexts.
Together with Corollary 4.5, this lemma implies the main result as stated in
Theorem 4.9.

######  Lemma 4.8.

Suppose $f({\bm{x}},z)$ is differentiable and $L$-Lipschitz in ${\bm{x}}$ and
the domain of ${\cal A}$ is bounded by $D={\delta}/{T}$, then the variance of
the gradient oracle ${\cal O}$ (Algorithm 4) is bounded by

$\mathbb{E}\|\nabla\hat{F}_{\delta}({\bm{w}}_{t}^{k})-{\bm{g}}_{t}^{k}\|^{2}\leq\frac{16dL^{2}}{B_{1}}+\frac{64dL^{2}}{B_{2}T}.$

######  Theorem 4.9.

Suppose $f({\bm{x}},z)$ is differentiable and $L$-Lipschitz in ${\bm{x}}$,
$F({\bm{x}}_{1})-\inf_{\bm{x}}F({\bm{x}})\leq F^{*}$. Then for any
$\delta,\epsilon>0$ and $\alpha>1,\rho>0$, there exists

$M=\tilde{O}\left(d\left(\frac{F^{*}L^{2}}{\delta\epsilon^{3}}+\frac{L^{3}}{\epsilon^{3}}\right)+d^{3/2}\left(\frac{F^{*}L}{\rho\delta\epsilon^{2}}+\frac{L^{2}}{\rho\epsilon^{2}}\right)\right)$

such that upon running Algorithm 3 with projected OSD as the OCO algorithm,
using Algorithm 4 as the private oracle, and setting $\sigma_{t}$ as defined
in Corollary 4.4 and
$B_{1}=T+1,B_{2}=1,D=\frac{\delta}{T},T=\min\\{(\frac{\sqrt{d}L\delta
M}{F^{*}+L\delta})^{2/3},(\frac{d^{3/2}L\delta
M}{(F^{*}+L\delta)\rho})^{1/2}\\},K=\frac{M}{2T}$, the algorithm outputs an
$(\alpha,\alpha\rho^{2}/2)$-RDP $(\delta,\epsilon)$-stationary point with $M$
data points.

###### Proof.

Since $B_{1}=T+1,B_{2}=1$ satisfy $B_{1}\geq TB_{2}/2$, Corollary 4.4 implies
the privacy guarantee. For the convergence analysis, Corollary 4.7 states that

$\mathbb{E}\|\nabla
F(\overline{\bm{w}})\|_{2\delta}\leq\frac{F^{*}+2L\delta}{DKT}+\sum_{k=1}^{K}\frac{\mathbb{E}\mathrm{Reg}_{T}(\hat{\bm{u}}^{k})}{DKT}+\sum_{k=1}^{K}\sum_{t=1}^{T}\frac{\mathbb{E}\langle\nabla\hat{F}_{\delta}({\bm{w}}_{t}^{k})-\tilde{\bm{g}}_{t}^{k},\Delta_{t}^{k}-\hat{\bm{u}}^{k}\rangle}{DKT}.$

Recall that given a sequence of stochastic vectors
${\bm{v}}_{1},\ldots,{\bm{v}}_{T}$, the regret of projected OSD is bounded by
$\mathbb{E}[\mathrm{Reg}_{T}({\bm{u}})]\leq
D\sqrt{\sum_{t=1}^{T}\mathbb{E}\|{\bm{v}}_{t}\|^{2}}$ (Orabona, 2019). In our
case, ${\bm{v}}_{t}=\tilde{\bm{g}}_{t}^{k}$. We can bound

$\displaystyle\mathbb{E}\|\tilde{\bm{g}}_{t}^{k}\|^{2}$ $\displaystyle\leq
3\mathbb{E}\|{\bm{g}}_{t}^{k}-\nabla\hat{F}_{\delta}({\bm{w}}_{t}^{k})\|^{2}+3\mathbb{E}\|\nabla\hat{F}_{\delta}({\bm{w}}_{t}^{k})\|^{2}+3\mathbb{E}\|\textsc{Tree}(t)\|^{2}$
$\displaystyle\leq
3\cdot\frac{80dL^{2}}{B_{2}T}+3L^{2}+3\cdot\left(\frac{8\ln(T)d^{3/2}L}{B_{2}T\rho}\right)^{2},$

where the first term is bounded by Lemma 4.8 with $B_{1}\geq TB_{2}/2$, the
second by Lipschitzness of $\hat{F}_{\delta}$ (Lemma 2.2 (i)), and the third
by Corollary 4.5. Consequently, we bound the regret by

$\mathbb{E}[\mathrm{Reg}_{T}(\hat{\bm{u}}^{k})]\lesssim
DL\sqrt{T}\left(\frac{\sqrt{d}}{\sqrt{B_{2}T}}+1+\frac{d^{3/2}}{B_{2}T\rho}\right).$
(1)

Next, note that $\|\Delta_{t}^{k}-\hat{\bm{u}}^{k}\|\leq 2D$. Following the
same previous bounds, we have

$\displaystyle\mathbb{E}\langle\nabla\hat{F}_{\delta}({\bm{w}}_{t}^{k})-\tilde{\bm{g}}_{t}^{k},\Delta_{t}^{k}-\hat{\bm{u}}^{k}\rangle$
$\displaystyle\leq
2D\mathbb{E}[\|\nabla\hat{F}_{\delta}({\bm{w}}_{t}^{k})-{\bm{g}}_{t}^{k}\|+\|\textsc{Tree}(t)\|]$
$\displaystyle\lesssim
D\left(\frac{\sqrt{d}L}{\sqrt{B_{2}T}}+\frac{d^{3/2}L}{B_{2}T\rho}\right).$
(2)

Upon substituting equation 1 and equation 2 into Corollary 4.7, we have

$\displaystyle\mathbb{E}\|\nabla F(\overline{\bm{w}})\|_{2\delta}$
$\displaystyle\lesssim\frac{F^{*}+L\delta}{DKT}+\frac{L}{\sqrt{T}}\left(\frac{\sqrt{d}}{\sqrt{B_{2}T}}+1+\frac{d^{3/2}}{B_{2}T\rho}\right)+\left(\frac{\sqrt{d}L}{\sqrt{B_{2}T}}+\frac{d^{3/2}L}{B_{2}T\rho}\right)$
Upon setting $B_{1}=T+1,B_{2}=1,D=\frac{\delta}{T}$, the data size is
$M=K(B_{1}+B_{2}(T-1))=2KT$ and
$\displaystyle\lesssim\frac{(F^{*}+L\delta)T}{\delta
M}+\frac{\sqrt{d}L}{\sqrt{T}}+\frac{d^{3/2}L}{T\rho}$ Upon setting
$T=\min\\{(\frac{\sqrt{d}L\delta
M}{F^{*}+L\delta})^{2/3},(\frac{d^{3/2}L\delta
M}{(F^{*}+L\delta)\rho})^{1/2}\\}$, we achieve the desired bound
$\displaystyle\lesssim\left(\frac{F^{*}dL^{2}}{\delta
M}\right)^{1/3}+\left(\frac{dL^{3}}{M}\right)^{1/3}+\left(\frac{F^{*}d^{3/2}L}{\rho\delta
M}\right)^{1/2}+\left(\frac{d^{3/2}L^{2}}{\rho M}\right)^{1/2}.$

Equivalently, the right hand side is bounded by $\epsilon$ if
$M=\max\\{\frac{F^{*}dL^{2}}{\delta\epsilon^{3}},\frac{dL^{3}}{\epsilon^{3}},\frac{F^{*}d^{3/2}L}{\rho\delta\epsilon^{2}},\frac{d^{3/2}L^{2}}{\rho\epsilon^{2}}\\}$.
∎

##  5 Conclusion

This paper presents a novel zeroth-order algorithm for private nonsmooth
nonconvex optimization. We prove that, given a dataset of size $M$, our
algorithm finds a $(\delta,\epsilon)$-stationary point while achieving
$(\alpha,\alpha\rho^{2}/2)$-RDP privacy guarantee so long as
$M=\tilde{\Omega}\left(d(\frac{F^{*}L^{2}}{\delta\epsilon^{3}}+\frac{L^{3}}{\epsilon^{3}})+d^{3/2}(\frac{F^{*}L}{\rho\delta\epsilon^{2}}+\frac{L^{2}}{\rho\epsilon^{2}})\right)$.
Notably, this is the first algorithm for the private nonsmooth nonconvex
optimization problem.

For future research, there are several intriguing directions. First, we are
interested in exploring methods that could eliminate the need to sample $d$
uniform vectors per data point, a limitation we delve into in Section 3.
Additionally, the design of efficient first-order private algorithms for
nonsmooth nonconvex optimization stands out as an area of potential
exploration. Finally, the optimality of the current rate is still uncertain,
and finding the lower bounds remains an open problem.

## References

  * Arjevani et al. (2019) Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth.  Lower bounds for non-convex stochastic optimization.  _arXiv preprint arXiv:1912.02365_ , 2019.
  * Arjevani et al. (2020) Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridharan.  Second-order information in non-convex stochastic optimization: Power and limitations.  In _Conference on Learning Theory_ , pp. 242–299, 2020.
  * Arora et al. (2023) Raman Arora, Raef Bassily, Tomás González, Cristóbal Guzmán, Michael Menart, and Enayat Ullah.  Faster rates of convergence to stationary points in differentially private optimization.  2023\.
  * Bassily et al. (2014) Raef Bassily, Adam Smith, and Abhradeep Thakurta.  Private empirical risk minimization: Efficient algorithms and tight error bounds.  In _2014 IEEE 55th Annual Symposium on Foundations of Computer Science_ , pp. 464–473. IEEE, 2014.
  * Bassily et al. (2019) Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta.  Private stochastic convex optimization with optimal rates.  In _Proceedings of the 33rd International Conference on Neural Information Processing Systems_ , pp. 11282–11291, 2019.
  * Bassily et al. (2021a) Raef Bassily, Cristóbal Guzmán, and Michael Menart.  Differentially private stochastic optimization: New results in convex and non-convex settings.  _Advances in Neural Information Processing Systems_ , 34, 2021a.
  * Bassily et al. (2021b) Raef Bassily, Cristóbal Guzmán, and Anupama Nandi.  Non-euclidean differentially private stochastic convex optimization.  In _Conference on Learning Theory_ , pp. 474–499. PMLR, 2021b.
  * Bertsekas (1973) Dimitri P Bertsekas.  Stochastic optimization problems with nondifferentiable cost functionals.  _Journal of Optimization Theory and Applications_ , 12(2):218–231, 1973.
  * Carmon et al. (2019) Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford.  Lower bounds for finding stationary points i.  _Mathematical Programming_ , pp. 1–50, 2019.
  * Cesa-Bianchi & Lugosi (2006) Nicolo Cesa-Bianchi and Gábor Lugosi.  _Prediction, learning, and games_.  Cambridge university press, 2006.
  * Chan et al. (2011) T-H Hubert Chan, Elaine Shi, and Dawn Song.  Private and continual release of statistics.  _ACM Transactions on Information and System Security (TISSEC)_ , 14(3):1–24, 2011.
  * Chaudhuri et al. (2011) Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate.  Differentially private empirical risk minimization.  _Journal of Machine Learning Research_ , 12(3), 2011.
  * Chen et al. (2023) Lesi Chen, Jing Xu, and Luo Luo.  Faster gradient-free algorithms for nonsmooth nonconvex stochastic optimization, 2023.
  * Cutkosky & Orabona (2019) Ashok Cutkosky and Francesco Orabona.  Momentum-based variance reduction in non-convex sgd.  In _Advances in Neural Information Processing Systems_ , pp. 15210–15219, 2019.
  * Cutkosky et al. (2023) Ashok Cutkosky, Harsh Mehta, and Francesco Orabona.  Optimal stochastic non-smooth non-convex optimization through online-to-non-convex conversion.  In _International Conference on Machine Learning (ICML)_ , 2023.
  * Duchi et al. (2012) John C Duchi, Peter L Bartlett, and Martin J Wainwright.  Randomized smoothing for stochastic optimization.  _SIAM Journal on Optimization_ , 22(2):674–701, 2012.
  * Duchi et al. (2015) John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono.  Optimal rates for zero-order convex optimization: The power of two function evaluations.  _IEEE Transactions on Information Theory_ , 61(5):2788–2806, 2015.  doi: 10.1109/TIT.2015.2409256.
  * Dwork et al. (2006) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of cryptography conference_ , pp. 265–284. Springer, 2006.
  * Dwork et al. (2010) Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum.  Differential privacy under continual observation.  In _Proceedings of the forty-second ACM symposium on Theory of computing_ , pp. 715–724, 2010.
  * Fang et al. (2018) Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang.  Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator.  In _Advances in Neural Information Processing Systems_ , pp. 689–699, 2018.
  * Feldman et al. (2020) Vitaly Feldman, Tomer Koren, and Kunal Talwar.  Private stochastic convex optimization: optimal rates in linear time.  In _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , pp. 439–449, 2020.
  * Flaxman et al. (2005) Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan.  Online convex optimization in the bandit setting: gradient descent without a gradient.  In _Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms_ , pp. 385–394, 2005.
  * Ghadimi & Lan (2013) Saeed Ghadimi and Guanghui Lan.  Stochastic first-and zeroth-order methods for nonconvex stochastic programming.  _SIAM Journal on Optimization_ , 23(4):2341–2368, 2013.
  * Goldstein (1977) A. A. Goldstein.  Optimization of lipschitz continuous functions.  _Math. Program._ , 13(1):14–22, dec 1977.  ISSN 0025-5610.  doi: 10.1007/BF01584320.  URL https://doi.org/10.1007/BF01584320.
  * Hazan (2019) Elad Hazan.  Introduction to online convex optimization.  _arXiv preprint arXiv:1909.05207_ , 2019.
  * Jain & Thakurta (2014) Prateek Jain and Abhradeep Guha Thakurta.  (near) dimension independent risk bounds for differentially private learning.  In _International Conference on Machine Learning_ , pp. 476–484. PMLR, 2014.
  * Jain et al. (2012) Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta.  Differentially private online learning.  In _Conference on Learning Theory_ , pp. 24–1. JMLR Workshop and Conference Proceedings, 2012.
  * Kifer et al. (2012) Daniel Kifer, Adam Smith, and Abhradeep Thakurta.  Private convex empirical risk minimization and high-dimensional regression.  In _Conference on Learning Theory_ , pp. 25–1. JMLR Workshop and Conference Proceedings, 2012.
  * Kornowski & Shamir (2022) Guy Kornowski and Ohad Shamir.  Oracle complexity in nonsmooth nonconvex optimization.  _Journal of Machine Learning Research_ , 23(314):1–44, 2022.
  * Kornowski & Shamir (2023) Guy Kornowski and Ohad Shamir.  An algorithm with optimal dimension-dependence for zero-order nonsmooth nonconvex stochastic optimization, 2023.
  * Lin et al. (2022) Tianyi Lin, Zeyu Zheng, and Michael I. Jordan.  Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization, 2022.
  * Mania et al. (2018) Horia Mania, Aurelia Guy, and Benjamin Recht.  Simple random search of static linear policies is competitive for reinforcement learning.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.
  * Mironov (2017) Ilya Mironov.  Rényi differential privacy.  In _2017 IEEE 30th Computer Security Foundations Symposium (CSF)_ , pp. 263–275. IEEE, 2017.
  * Nelson (2010) Barry L. Nelson.  Optimization via simulation over discrete decision variables.  In _Risk and Optimization in an Uncertain World_ , pp. 193–207. INFORMS, September 2010.  doi: 10.1287/educ.1100.0069.  URL https://doi.org/10.1287/educ.1100.0069.
  * Orabona (2019) Francesco Orabona.  A modern introduction to online learning.  _arXiv preprint arXiv:1912.13213_ , 2019.
  * Shamir (2017) Ohad Shamir.  An optimal algorithm for bandit and zero-order convex optimization with two-point feedback.  _Journal of Machine Learning Research_ , 18(52):1–11, 2017.
  * Talwar et al. (2014) Kunal Talwar, Abhradeep Thakurta, and Li Zhang.  Private empirical risk minimization beyond the worst case: The effect of the constraint set geometry.  _arXiv preprint arXiv:1411.5417_ , 2014.
  * Tian et al. (2022) Lai Tian, Kaiwen Zhou, and Anthony Man-Cho So.  On the finite-time complexity and practical computation of approximate stationarity concepts of lipschitz functions.  In _International Conference on Machine Learning_ , pp. 21360–21379. PMLR, 2022.
  * Tran & Cutkosky (2022) Hoang Tran and Ashok Cutkosky.  Momentum aggregation for private non-convex ERM.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=x56v-UN7BjD.
  * Wainwright (2019) Martin J. Wainwright.  _High-Dimensional Statistics: A Non-Asymptotic Viewpoint_.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.  doi: 10.1017/9781108627771.
  * Wang et al. (2017) Di Wang, Minwei Ye, and Jinhui Xu.  Differentially private empirical risk minimization revisited: faster and more general.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , pp. 2719–2728, 2017.
  * Wang et al. (2019a) Di Wang, Changyou Chen, and Jinhui Xu.  Differentially private empirical risk minimization with non-convex loss functions.  In _International Conference on Machine Learning_ , pp. 6526–6535. PMLR, 2019a.
  * Wang et al. (2019b) Lingxiao Wang, Bargav Jayaraman, David Evans, and Quanquan Gu.  Efficient privacy-preserving stochastic nonconvex optimization.  _arXiv preprint arXiv:1910.13659_ , 2019b.
  * Yousefian et al. (2012) Farzad Yousefian, Angelia Nedić, and Uday V. Shanbhag.  On stochastic gradient and subgradient methods with adaptive steplength sequences.  _Automatica_ , 48(1):56–67, 2012.  ISSN 0005-1098.
  * Zhang et al. (2020) Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Ali Jadbabaie, and Suvrit Sra.  Complexity of finding stationary points of nonsmooth nonconvex functions.  2020\.
  * Zhang et al. (2022) Qinzi Zhang, Hoang Tran, and Ashok Cutkosky.  Differentially private online-to-batch for smooth losses.  In _Advances in Neural Information Processing Systems_ , volume 35, 2022.
  * Zhou et al. (2020) Yingxue Zhou, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Arindam Banerjee.  Private stochastic non-convex optimization: Adaptive algorithms and tighter generalization bounds.  _arXiv preprint arXiv:2006.13501_ , 2020.
  * Zinkevich (2003) Martin Zinkevich.  Online convex programming and generalized infinitesimal gradient ascent.  In _Proceedings of the 20th International Conference on Machine Learning (ICML-03)_ , pp. 928–936, 2003.

##  Appendix A Proofs in Section 2

###  A.1 Proof of Lemma 2.2

See 2.2

###### Proof.

For simplicity, we drop the subscript $\delta$ of $\hat{h}_{\delta}$. By
Jensen’s inequality and Lipschitzness,

$\displaystyle\|\hat{h}({\bm{x}})-\hat{h}({\bm{y}})\|\leq\mathbb{E}_{\bm{v}}\|h({\bm{x}}+\delta{\bm{v}})-h({\bm{y}}+\delta{\bm{v}})\|\leq
L\|{\bm{x}}-{\bm{y}}\|,$ (i)
$\displaystyle\|\hat{h}({\bm{x}})-h({\bm{x}})\|\leq\mathbb{E}_{\bm{v}}\|h({\bm{x}}+\delta{\bm{v}})-h({\bm{x}})\|\leq
L\|\delta{\bm{v}}\|\leq L\delta.$ (ii)

Next, since $h$ is Lipschitz, $h$ is almost every differentiable by
Rademacher’s theorem and the uniform smoothing $\hat{h}$ is also almost
everywhere differentiable by (Bertsekas, 1973, Proposition 2.4). Moreover, it
holds that $\nabla\hat{h}({\bm{x}})=\mathbb{E}_{\bm{v}}[\nabla
h({\bm{x}}+\delta{\bm{v}})]$. Denote $\triangle$ as the symmetric difference,
i.e., $A\triangle B=(A\setminus B)\cup(B\setminus A)$, and let
$S=B({\bm{x}},\delta)\triangle B({\bm{y}},\delta)$. Then

$\displaystyle\|\nabla\hat{h}({\bm{x}})-\nabla\hat{h}({\bm{y}})\|$
$\displaystyle=\|\mathbb{E}_{{\bm{v}}\sim{\cal U}_{\mathbb{B}}}[\nabla
h({\bm{x}}+\delta{\bm{v}})-\nabla h({\bm{y}}+\delta{\bm{v}})]\|$
$\displaystyle=\left\|\int_{B({\bm{x}},\delta)}\frac{\nabla
h({\bm{v}})}{\operatorname{vol}(B({\bm{x}},\delta))}\,d{\bm{v}}-\int_{B({\bm{y}},\delta)}\frac{\nabla
h({\bm{v}})}{\operatorname{vol}(B({\bm{y}},\delta))}\,d{\bm{v}}\right\|$
$\displaystyle=\left\|\int_{S}\frac{\nabla
h({\bm{v}})}{\operatorname{vol}(\delta\mathbb{B})}\,d{\bm{v}}\right\|\leq\int_{S}\frac{\|\nabla
h({\bm{v}})\|}{\operatorname{vol}(\delta\mathbb{B})}\,d{\bm{v}}\leq\frac{\operatorname{vol}(S)L}{\operatorname{vol}(\delta\mathbb{B})}\leq\frac{\sqrt{d}L}{\delta}\|{\bm{x}}-{\bm{y}}\|,$

where the second last inequality follows from $\|\nabla h({\bm{v}})\|\leq L$,
and the last follows from Lemma A.1.

Finally, by definition of expectation,

$\displaystyle\mathbb{E}_{{\bm{v}}\sim{\cal U}_{\mathbb{B}}}[\nabla
h({\bm{x}}+\delta{\bm{v}})]=\frac{\int_{\mathbb{B}}\nabla_{\bm{x}}f({\bm{x}}+\delta{\bm{v}})\,d{\bm{v}}}{\operatorname{vol}(\mathbb{B})},$
$\displaystyle\mathbb{E}_{{\bm{u}}\sim{\cal
U}_{\SS}}[h({\bm{x}}+\delta{\bm{u}}){\bm{u}}]=\frac{\int_{\SS}f({\bm{x}}+\delta{\bm{u}}){\bm{u}}\,d{\bm{u}}}{\operatorname{vol}(\SS)}.$

By Stokes’ theorem,

$\displaystyle\int_{\mathbb{B}}\nabla_{\bm{x}}f({\bm{x}}+\delta{\bm{v}})\,d{\bm{v}}=\int_{\SS}f({\bm{x}}+\delta{\bm{u}}){\bm{u}}\,d{\bm{u}}$

We then establish the first equality in (iv) by
$\operatorname{vol}(\mathbb{B})/\operatorname{vol}(\SS)=\delta/d$. Next, let
$p$ be a Rademacher random variable and ${\bm{u}}^{\prime}={\bm{u}}/p$.
Observe that ${\bm{u}}^{\prime}\sim{\cal U}_{\SS}$ as well. Therefore,

$\displaystyle\mathbb{E}_{{\bm{u}}\sim{\cal
U}_{\SS}}[\tfrac{d}{\delta}h({\bm{x}}+\delta{\bm{u}}){\bm{u}}]$
$\displaystyle=\mathbb{E}_{p,{\bm{u}}^{\prime}}[\tfrac{d}{\delta}h({\bm{x}}+\delta
p{\bm{u}}^{\prime})p{\bm{u}}^{\prime}]$
$\displaystyle=\tfrac{1}{2}\mathbb{E}_{{\bm{u}}^{\prime}}[\tfrac{d}{\delta}h({\bm{x}}+\delta{\bm{u}}){\bm{u}}+\tfrac{d}{\delta}h({\bm{x}}-\delta{\bm{u}})(-{\bm{u}})].$

This proves the second equality in (iv). ∎

######  Lemma A.1.

Let ${\bm{x}},{\bm{y}}\in\mathbb{R}^{d}$ and $S=B({\bm{x}},\delta)\triangle
B({\bm{y}},\delta)$, then
$\frac{\operatorname{vol}(S)}{\operatorname{vol}(\delta\mathbb{B})}\leq\frac{\sqrt{d}}{\delta}\|{\bm{x}}-{\bm{y}}\|$.

###### Proof.

Let $D=\|{\bm{x}}-{\bm{y}}\|$, $V_{d}(r)$ be the volume of an $d$-ball in
$\mathbb{R}^{d}$, and $U_{d}(h,r)$ be the volume of the cap of an $d$-ball of
height $h$. Observe that for $D\leq 2\delta$,

$\frac{\operatorname{vol}(S)}{\operatorname{vol}(\delta\mathbb{B})}=2\cdot\frac{U_{d}(\delta+\frac{D}{2},\delta)-U_{d}(\delta-\frac{D}{2},\delta)}{V_{d}(\delta)}.$

Next, we compute the value of $U_{d}(h,r)$.

$U_{d}(h,r)=\int_{0}^{h}V_{d-1}(\sqrt{r^{2}-(r-t)^{2}})\,dt.$

Recall that the volume of an $d$-ball is
$V_{d}(r)=\frac{\pi^{d/2}}{\Gamma(d/2+1)}r^{n}$. Therefore,

$\displaystyle\frac{\operatorname{vol}(S)}{\operatorname{vol}(\delta\mathbb{B})}$
$\displaystyle=\frac{\frac{\pi^{(d-1)/2}}{\Gamma((d-1)/2+1)}\int_{\delta-\frac{D}{2}}^{\delta+\frac{D}{2}}(2\delta
t-t^{2})^{\frac{d-1}{2}}\,dt}{\frac{\pi^{d/2}}{\Gamma(d/2+1)}\delta^{d}}$
$\displaystyle=\frac{\Gamma(\frac{d}{2}+1)}{\sqrt{\pi}\Gamma(\frac{d-1}{2}+1)}\int_{\delta-\frac{D}{2}}^{\delta+\frac{D}{2}}\left(\frac{2t}{\delta}-\frac{t^{2}}{\delta^{2}}\right)^{\frac{d-1}{2}}\frac{1}{\delta}\,dt$
$\displaystyle=\frac{\Gamma(\frac{d}{2}+1)}{\sqrt{\pi}\Gamma(\frac{d-1}{2}+1)}\int_{1-\frac{D}{2\delta}}^{1+\frac{D}{2\delta}}(2u-u^{2})^{\frac{d-1}{2}}\,du.$
($t=\delta u$)

Note that $2u-u^{2}\leq 1$ for all $u\in\mathbb{R}$, so the integral is
bounded by
$\int_{1-\frac{D}{2\delta}}^{1+\frac{D}{2\delta}}1\,du=\frac{D}{\delta}$. The
proof then follows from the fact that
$\Gamma(\frac{d}{2}+1)/\Gamma(\frac{d-1}{2}+1)\leq\sqrt{2d}$ (proved in Lemma
A.2 for completeness). ∎

######  Lemma A.2.

For all $n\in\mathbb{N}$,
$\Gamma(\frac{n}{2}+1)/\Gamma(\frac{n-1}{2}+1)\leq\sqrt{2n}$.

###### Proof.

Let $n!!=n(n-2)(n-4)\dotsm=\prod_{k=0}^{\lceil\frac{n}{2}\rceil-1}(n-2k)$,
then by definition of $\Gamma(n+1)=n\gamma(n)$ and
$\Gamma(\frac{1}{2})=\sqrt{\pi}$, we have

$\Gamma(\tfrac{n}{2}+1)=\left\\{\begin{array}[]{ll}\frac{n!!}{2^{n/2}},&\text{$n$
is even}\\\ \frac{\sqrt{\pi}n!!}{2^{(n+1)/2}},&\text{$n$ is
odd}\end{array}\right.$

Consequently, we have

$\frac{\Gamma(\tfrac{n}{2}+1)}{\Gamma(\frac{n-1}{2}+1)}=\left\\{\begin{array}[]{ll}\frac{n!!}{\sqrt{\pi}(n-1)!!},&\text{$n$
is even}\\\ \frac{\sqrt{\pi}n!!}{2(n-1)!!},&\text{$n$ is
odd}\end{array}\right.\leq\frac{n!!}{(n-1)!!}.$

We finish the proof by induction. For $n=1$,
$\frac{1!!}{0!!}=1\leq\sqrt{2\cdot 1}$. For $n=2$,
$\frac{2!!}{1!!}=2\leq\sqrt{2\cdot 2}$. Now assume
$\frac{m!!}{(m-1)!!}\leq\sqrt{2m}$ for all $m\leq n$. Then

$\displaystyle\frac{(n+1)!!}{n!!}=\frac{n+1}{n}\frac{(n-1)!!}{(n-2)!!}\leq\frac{n+1}{n}\sqrt{2(n-1)}=\sqrt{2(n+1)}\frac{\sqrt{(n+1)(n-1)}}{n}\leq\sqrt{2(n+1)}.$

This concludes the proof by induction. ∎

###  A.2 Proof of Corollary 2.3

See 2.3

###### Proof.

Recall that the $\delta$-subdifferential of $\hat{F}_{\delta}$ is defined as
$\partial_{\delta}\hat{F}_{\delta}({\bm{x}})=\operatorname{conv}(\cup_{{\bm{y}}\in
B({\bm{x}},\delta)}\nabla\hat{F}_{\delta}({\bm{y}}))$. In other words, for
each ${\bm{g}}\in\partial_{\delta}\hat{F}_{\delta}({\bm{x}})$, ${\bm{g}}$ is
of form of ${\bm{g}}=\sum\lambda_{i}\nabla\hat{F}_{\delta}({\bm{y}}_{i})$
where $\lambda_{i}$’s are convex coefficients and ${\bm{y}}_{i}\in
B({\bm{x}},\delta)$. (Lin et al., 2022, Theorem 10) has proved that
$\nabla\hat{F}_{\delta}({\bm{y}}_{i})\in\partial_{\delta}F({\bm{y}}_{i})$. In
addition, since $\|{\bm{y}}_{i}-{\bm{x}}\|\leq\delta$, we have
$\partial_{\delta}F({\bm{y}}_{i})\subset\partial_{2\delta}F({\bm{x}})$.
Consequently, we have

$\nabla\hat{F}_{\delta}({\bm{y}}_{i})\in\partial_{\delta}F({\bm{y}}_{i})\subset\partial_{2\delta}F({\bm{x}})$

and thus ${\bm{g}}\in\partial_{2\delta}F({\bm{x}})$ for all
${\bm{g}}\in\partial_{\delta}\hat{F}_{\delta}({\bm{x}})$. We conclude the
proof by recalling Definition 2.1 that

$\|\nabla\hat{F}_{\delta}({\bm{x}})\|_{\delta}=\inf\\{\|{\bm{g}}\|:{\bm{g}}\in\partial_{\delta}\hat{F}_{\delta}({\bm{x}})\\},\quad\|\nabla
F({\bm{x}})\|_{2\delta}=\inf\\{\|{\bm{g}}\|:{\bm{g}}\in\partial_{2\delta}F({\bm{x}})\\}$

and the previous result that
$\|\partial_{\delta}\hat{F}_{\delta}({\bm{x}})\subset\partial_{2\delta}F({\bm{x}})$.
∎

##  Appendix B Proofs in Section 3

See 3.1

###### Proof.

For simplicity, let
${\bm{g}}_{ij}=\frac{d}{2\delta}(f({\bm{x}}+\delta{\bm{u}}_{ij},z_{i})-f({\bm{x}}-\delta{\bm{u}}_{ij},z_{i})){\bm{u}}_{ij}$
so that
$\textsc{Grad}_{f,\delta}({\bm{x}},z_{1:b})=\frac{1}{b}\sum_{i=1}^{b}\frac{1}{d}\sum_{j=1}^{d}{\bm{g}}_{ij}$.
Since $f$ is $L$-Lipschitz, it follows that $\|{\bm{g}}_{ij}\|\leq dL$.

First, by $F({\bm{x}})=\mathbb{E}_{z}[f({\bm{x}},z)]$ and Lemma 2.2 (iv),

$\displaystyle\mathbb{E}_{{\bm{u}},z}[{\bm{g}}_{ij}]=\mathbb{E}_{{\bm{u}}}[\tfrac{d}{2\delta}(F({\bm{x}}+\delta{\bm{u}}_{ij})-F({\bm{x}}-\delta{\bm{u}}_{ij})){\bm{u}}_{ij}]=\nabla\hat{F}_{\delta}({\bm{x}}).$

Taking the average over $i,j$ gives
$\mathbb{E}[\textsc{Grad}_{f,\delta}({\bm{x}},z_{1:b})]=\nabla\hat{F}_{\delta}({\bm{x}})$.

Next, let $\overline{\bm{g}}_{i}=\frac{1}{d}\sum_{j=1}^{d}{\bm{g}}_{ij}$ and
observe that
$\mathbb{E}[\overline{\bm{g}}_{i}]=\nabla\hat{F}_{\delta}({\bm{x}})$. Since
$\overline{\bm{g}}_{i}-\nabla\hat{F}_{\delta}({\bm{x}})$ are mean-zero and
independent for all $i$, we have

$\displaystyle\mathbb{E}[\langle\overline{\bm{g}}_{i}-\nabla\hat{F}_{\delta}({\bm{x}}),\overline{\bm{g}}_{i^{\prime}}-\nabla\hat{F}_{\delta}({\bm{x}})\rangle]$
$\displaystyle=\mathbb{E}_{z_{i^{\prime}}}[\langle\mathbb{E}_{z_{i}}[\overline{\bm{g}}_{i}-\nabla\hat{F}_{\delta}({\bm{x}})],\overline{\bm{g}}_{i^{\prime}}-\nabla\hat{F}_{\delta}({\bm{x}})\rangle|z_{i^{\prime}}]=0.$

In other words, all cross-terms are $0$. Therefore,

$\displaystyle\mathbb{E}\|\textsc{Grad}_{f,\delta}({\bm{x}},z_{1:b})-\nabla\hat{F}_{\delta}({\bm{x}})\|^{2}$
$\displaystyle=\textstyle\frac{1}{b^{2}}\sum_{i=1}^{b}\mathbb{E}\|\overline{\bm{g}}_{i}-\nabla\hat{F}_{\delta}({\bm{x}})\|^{2}$
$\displaystyle\leq\textstyle\frac{1}{b^{2}}\sum_{i=1}^{b}2\mathbb{E}\|\overline{\bm{g}}_{i}-\nabla\hat{f}_{\delta}({\bm{x}},z_{i})\|^{2}+2\mathbb{E}\|\nabla\hat{f}({\bm{x}},z_{i})-\nabla\hat{F}_{\delta}({\bm{x}})\|^{2}.$
(3)

We first evaluate the second term. By Lemma 2.2 (i),
$\hat{f}_{\delta}(\cdot,z_{i})$ and $F_{\delta}$ are $L$-Lipschitz, which
implies that $\|\nabla\hat{f}_{\delta}({\bm{x}},z_{i})\|\leq L$ and
$\|\nabla\hat{F}_{\delta}({\bm{x}})\|\leq L$. Consequently,
$\mathbb{E}\|\nabla\hat{f}({\bm{x}},z_{i})-\nabla\hat{F}_{\delta}({\bm{x}})\|^{2}\leq(2L)^{2}$.
Next, note that ${\bm{g}}_{ij}-\nabla\hat{f}_{\delta}({\bm{x}},z_{i})|z_{i}$
are mean-zero and independent for all $j$. Therefore,

$\displaystyle\mathbb{E}\|\overline{\bm{g}}_{i}-\nabla\hat{f}_{\delta}({\bm{x}},z_{i})\|^{2}$
$\displaystyle=\textstyle\frac{1}{d^{2}}\sum_{j=1}^{d}\mathbb{E}\|{\bm{g}}_{ij}-\nabla\hat{f}_{\delta}({\bm{x}},z_{i})\|^{2}\leq\frac{(d+1)^{2}L^{2}}{d}.$

The last inequality follows from
$\|{\bm{g}}_{ij}-\nabla\hat{f}_{\delta}({\bm{x}},z_{i})\|\leq\|{\bm{g}}_{ij}\|+\|\nabla\hat{f}_{\delta}({\bm{x}},z_{i})\|\leq(d+1)L$.
Upon substituting back into equation 3, we have

$\textstyle\mathbb{E}\|\textsc{Grad}_{f,\delta}({\bm{x}},z_{1:b})-\nabla\hat{F}_{\delta}({\bm{x}})\|^{2}\leq\frac{2}{b}\left(\frac{(d+1)^{2}L^{2}}{d}+(2L)^{2}\right)\leq\frac{16dL^{2}}{b}.$

Finally, let ${\bm{g}}^{\prime}_{ij},\overline{\bm{g}}^{\prime}_{i}$ be
defined in the same way as ${\bm{g}}_{ij},\overline{\bm{g}}_{i}$ but using
$z^{\prime}_{1:b}$. Since $z_{1:b},z^{\prime}_{1:b}$ are neighboring,
$\overline{\bm{g}}_{i}-\overline{\bm{g}}_{i}^{\prime}=0$ for all but one $i$.
Let $k$ be the index of the different data point. Then

$\textstyle\|\textsc{Grad}_{f,\delta}({\bm{x}},z_{1:b})-\textsc{Grad}_{f,\delta}({\bm{x}},z^{\prime}_{1:b})\|=\frac{1}{b}\|\overline{\bm{g}}_{k}-\overline{\bm{g}}_{k}^{\prime}\|\leq\frac{1}{bd}\sum_{j=1}^{d}\|{\bm{g}}_{kj}-{\bm{g}}_{kj}^{\prime}\|\leq\frac{2dL}{b}.\qed$

See 3.2

###### Proof.

Let
${\bm{d}}_{ij}=\tfrac{d}{\delta}(f({\bm{x}}+\delta{\bm{u}}_{ij},z_{i})-f({\bm{y}}+\delta{\bm{u}}_{ij},z_{i})){\bm{u}}_{ij}$.
Then it follows that
$\textsc{Diff}_{f,\delta}({\bm{x}},{\bm{y}},z_{1:b})=\frac{1}{b}\sum_{i=1}^{b}\frac{1}{d}\sum_{j=1}^{d}{\bm{d}}_{ij}$.
Since $f$ is $L$-Lipschitz, it also holds that
$\|{\bm{d}}_{ij}\|\leq\frac{dL}{\delta}\|{\bm{x}}-{\bm{y}}\|$.

First, by $F({\bm{x}})=\mathbb{E}_{z}[f({\bm{x}},z)]$ and Lemma 2.2 (iv),

$\displaystyle\mathbb{E}_{{\bm{u}},z}[{\bm{d}}_{ij}]=\mathbb{E}_{{\bm{u}}}[\tfrac{d}{\delta}(F({\bm{x}}+\delta{\bm{u}}_{ij})-F({\bm{y}}+\delta{\bm{u}}_{ij}){\bm{u}}_{ij}]=\nabla\hat{F}_{\delta}({\bm{x}})-\nabla\hat{F}_{\delta}({\bm{y}}).$

Taking the average over $i,j$ gives
$\mathbb{E}_{{\bm{u}},z}[\textsc{Diff}_{f,\delta}({\bm{x}},{\bm{y}},z_{1:b})]=\nabla\hat{F}_{\delta}({\bm{x}})-\nabla\hat{F}_{\delta}({\bm{y}})$.

Next, let $\overline{\bm{d}}_{i}=\frac{1}{k}\sum_{j=1}^{k}{\bm{d}}_{ij}$,
$\Delta_{F}=\nabla\hat{F}_{\delta}({\bm{x}})-\nabla\hat{F}_{\delta}({\bm{y}})$,
and
$\Delta_{f}(z_{i})=\nabla\hat{f}_{\delta}({\bm{x}},z_{i})-\nabla\hat{f}_{\delta}({\bm{y}},z_{i})$.
Observe that $\mathbb{E}[\overline{\bm{d}}_{i}]=\Delta_{F}$ and
$\mathbb{E}[{\bm{d}}_{ij}|z_{i}]=\Delta_{f}(z_{i})$. Since
$\overline{\bm{d}}_{i}-\Delta_{F}$ are independent and mean-zero for all $i$,
we have

$\displaystyle\mathbb{E}\|\textsc{Diff}_{f,\delta}({\bm{x}},{\bm{y}},z_{1:b})-[\nabla\hat{F}_{\delta}({\bm{x}})-\nabla\hat{F}_{\delta}({\bm{y}})]\|^{2}$
$\displaystyle=\textstyle\frac{1}{b^{2}}\sum_{i=1}^{b}\mathbb{E}\|\overline{\bm{d}}_{i}-\Delta_{F}\|^{2}$
$\displaystyle\leq\textstyle\frac{1}{b^{2}}\sum_{i=1}^{b}2\mathbb{E}\|\overline{\bm{d}}_{i}-\Delta_{f}(z_{i})\|^{2}+2\mathbb{E}\|\Delta_{f}(z_{i})-\Delta_{F}\|^{2}.$
(4)

We first evaluate the second term. By Lemma 2.2 (iii),
$\hat{f}_{\delta},F_{\delta}$ are $\frac{\sqrt{d}L}{\delta}$-smooth, which
implies that
$\|\Delta_{f}(z_{i})\|,\|\Delta_{F}\|\leq\frac{\sqrt{d}L}{\delta}\|{\bm{x}}-{\bm{y}}\|$.
Consequently,
$\mathbb{E}\|\Delta_{f}(z_{i})-\Delta_{F}\|^{2}\leq(\frac{2\sqrt{d}L}{\delta}\|{\bm{x}}-{\bm{y}}\|)^{2}$.
Next, since ${\bm{d}}_{ij}-\Delta_{f}(z_{i})|z_{i}$ are mean-zero and
independent for all $j$,

$\displaystyle\mathbb{E}\|\overline{\bm{d}}_{i}-\Delta_{f}(z_{i})\|^{2}$
$\displaystyle\leq\textstyle\frac{1}{d^{2}}\sum_{j=1}^{d}\mathbb{E}\|{\bm{d}}_{ij}-\Delta_{f}(z_{i})\|^{2}\leq\frac{(2d^{2}+2d)L^{2}}{d\delta^{2}}\|{\bm{x}}-{\bm{y}}\|^{2}.$

The last inequality follows from
$\|{\bm{d}}_{ij}\|\leq\frac{dL}{b}\|{\bm{x}}-{\bm{y}}\|$ and
$\|\Delta_{f}(z_{i})\|\leq\frac{\sqrt{d}L}{\delta}\|{\bm{x}}-{\bm{y}}\|$.
Therefore, upon substituting back into equation 4, we have

$\textstyle\mathbb{E}\|\textsc{Diff}_{f,\delta}({\bm{x}},{\bm{y}},z_{1:b})-[\nabla\hat{F}_{\delta}({\bm{x}})-\nabla\hat{F}_{\delta}({\bm{y}})]\|^{2}\leq\frac{16dL^{2}}{b\delta^{2}}\|{\bm{x}}-{\bm{y}}\|^{2}.$

Finally, let ${\bm{d}}^{\prime}_{ij},\overline{\bm{d}}^{\prime}_{i}$ be
defined in the same way as ${\bm{d}}_{ij},\overline{\bm{d}}_{i}$ but using
$z^{\prime}_{1:b}$. Since $z_{1:b},z^{\prime}_{1:b}$ are neighboring,
$\overline{\bm{d}}_{i}-\overline{\bm{d}}_{i}^{\prime}=0$ for all but one $i$.
Let $k$ be the index of the different data point. Then

$\textstyle\|\textsc{Diff}_{f}({\bm{x}},{\bm{y}},z_{1:b})-\textsc{Diff}_{f}({\bm{x}},{\bm{y}},z_{1:b}^{\prime})\|=\frac{1}{b}\|\overline{\bm{d}}_{k}-\overline{\bm{d}}_{k}^{\prime}\|\leq\frac{2dL}{b\delta}\|{\bm{x}}-{\bm{y}}\|.\qed$

##  Appendix C Proofs in Section 4.2

###  C.1 Proof of Theorem 4.3

Before we prove the theorem, we first prove a more general composition of RDP
mechanisms. For two datasets $Z,Z^{\prime}\in{\cal Z}$, we denote
$Z\simeq_{q}Z^{\prime}$ if $Z,Z^{\prime}$ are neighbors and they differ at the
$q$-th entry.

######  Lemma C.1.

For any domain ${\cal Z}$, let ${\cal R}^{(i)}:{\cal
S}^{(1)}\times\dotsm\times{\cal S}^{(i-1)}\times{\cal Z}\to{\cal S}^{(i)}$ be
a sequence of algorithms such that ${\cal R}^{(i)}({\bm{x}}_{1:i-1},\cdot)$ is
$(\alpha,\epsilon_{i})$-RDP for all auxiliary inputs ${\bm{x}}_{1:i-1}\in{\cal
S}^{(i)}\times\dotsm\times{\cal S}^{(i-1)}$. Let $f_{{\cal
R}^{(i)}({\bm{x}}_{1:i-1},Z)}$ be the distribution of ${\cal
R}^{(i)}({\bm{x}}_{1:i-1},Z)$. Suppose each dataset $Z\in{\cal Z}$ has $m$
data, and for each $q\in[m]$, let

$\textsc{In}(q):=\\{i\in[n]:f_{{\cal R}^{(i)}(\cdot,Z)}=f_{{\cal
R}^{(i)}(\cdot,Z^{\prime})},\,\forall
Z\simeq_{q}Z^{\prime}\\},\quad\textsc{Out}(q):=[n]\setminus\textsc{In}(q).$

Let ${\cal A}_{n}:{\cal Z}\to{\cal S}^{(1)}\times\dotsm\times{\cal S}^{(n)}$
be the algorithm that given a dataset $Z\in{\cal Z}$ sequentially computes
${\bm{x}}_{i}={\cal R}^{(i)}({\bm{x}}_{1:i-1},z_{i})$ for $i\in[n]$ and then
outputs ${\bm{x}}_{1:n}$. Then ${\cal A}_{n}$ is $(\alpha,\epsilon)$-RDP,
where

$\textstyle\epsilon\leq\max_{q\in[m]}\sum_{i\in\textsc{Out}(q)}\epsilon_{i}.$

###### Proof.

Suppose $Z\simeq_{q}Z^{\prime}$ and let $P,Q$ be the distributions of ${\cal
A}_{n}(Z),{\cal A}_{n}(Z^{\prime})$ respectively. Note that
$P=P_{1}\times\dotsm\times P_{n}$ where $P_{i}$ is the distribution of ${\cal
A}_{i}(Z)$ given ${\cal A}_{i-1}(Z)$, i.e.,
$P_{i}({\bm{x}}_{i}|{\bm{x}}_{1:i-1})=f_{{\cal
R}^{(i)}({\bm{x}}_{1:i-1},Z)}({\bm{x}}_{i})$. Similarly,
$Q=Q_{1}\times\dotsm\times Q_{n}$ where
$Q_{i}({\bm{x}}_{i}|{\bm{x}}_{1:i-1})=f_{{\cal
R}^{(i)}({\bm{x}}_{1:i-1},Z^{\prime})}({\bm{x}}_{i})$.

For all $i\in\textsc{In}(q)$,
$P_{i}(\cdot|{\bm{x}}_{1:i-1})=Q_{i}(\cdot|{\bm{x}}_{1:i-1})$ for all
${\bm{x}}_{1:i-1}$ by definition of $\textsc{In}(q)$; and for all
$i\in\textsc{Out}(q)$, since ${\cal R}^{(i)}({\bm{x}}_{1:i-1},\cdot)$ is
$(\alpha,\epsilon_{i})$-RDP,
$D_{\alpha}(P_{i}(\cdot|{\bm{x}}_{1:i-1})\|Q_{i}(\cdot|{\bm{x}}_{1:i-1})\leq\epsilon_{i}$.
Therefore,

$\displaystyle\int
P_{i}({\bm{x}}_{i}|{\bm{x}}_{1:i-1})^{\alpha}Q_{i}({\bm{x}}_{i}|{\bm{x}}_{1:i-1})^{1-\alpha}\,d{\bm{x}}_{i}$
$\displaystyle=\exp({(\alpha-1)D_{\alpha}(P_{i}(\cdot|{\bm{x}}_{1:i-1})\|Q_{i}(\cdot|{\bm{x}}_{1:i-1})})\leq\left\\{\begin{array}[]{ll}1,&i\in\textsc{In}(q),\\\
e^{(\alpha-1)\epsilon_{i}},&i\in\textsc{Out}(q).\end{array}\right.$

We then conclude the proof by recursively integrating from $d{\bm{x}}_{n}$ to
$d{\bm{x}}_{1}$:

$e^{(\alpha-1)D_{\alpha}(P\|Q)}=\int\prod
P_{i}({\bm{x}}_{i}|{\bm{x}}_{1:i-1})^{\alpha}Q_{i}({\bm{x}}_{i}|{\bm{x}}_{1:i-1})^{1-\alpha}\,d{\bm{x}}_{n}\dotsm
d{\bm{x}}_{1}\leq\prod_{i\in\textsc{Out}(q)}e^{(\alpha-1)\epsilon_{i}}.\qed$

Next, we introduce several tree notations. Let $k\in\mathbb{N}_{0}$ and
consider a complete binary tree with $n=2^{k}$ leaves. Leaves are indexed by
$i\in[n]$ (or $(i,i)$ interchangeably) in an ascending order from left to
right, and every other node is indexed by $(i,j)$ where $i$ is its left-most
child leaf and $j$ is its right-most child leaf. Let ${\mathbb{T}}$ be the set
of all nodes, and let $<$ be a total order on ${\mathbb{T}}$ such that
$(a,b)<(c,d)$ if either $b<d$ or $b=d,a<c$. In other words, we compare
rightmost child first and break tie with leftmost child. We assume
$({\mathbb{T}},<)$ is sorted in ascending order, then it’s valid to label a
sequence w.r.t. ${\mathbb{T}}$ (e.g., we can rewrite
$a_{1},\ldots,a_{|{\mathbb{T}}|}$ as $a_{(i,j)}$ for $(i,j)\in{\mathbb{T}}$).
We denote $a_{(c,d)<(a,b)}$ as a short-hand notation of
$\\{a_{(c,d)}:(c,d)<(a,b)\\}$. Now we are ready to prove the theorem.

See 4.3

###### Proof.

For any $n\in\mathbb{N}$, define ${\mathbb{T}}$ as he tree set with
$2^{\lceil\log_{2}n\rceil}$ leaves. Let ${\cal Z}={\cal Z}^{(1:n)}$ and
$S^{(a,b)}={\cal X}$ for all $(a,b)\in{\mathbb{T}}$. For each
$(a,b)\in{\mathbb{T}}$, define ${\cal R}^{(a,b)}:(\prod_{(c,d)<(a,b)}{\cal
S}^{(c,d)})\times{\cal Z}\to{\cal S}^{(a,b)}$ as

${\cal R}^{(a,b)}({\bm{y}}_{(c,d)<(a,b)},Z_{1:n})=\sum_{i=a}^{b}{\cal
M}^{(i)}({\bm{x}}_{1:i-1},Z_{i})+\xi_{b},$ (5)

where ${\bm{x}}_{j}=\sum_{(c,d)\in\textsc{Node}(j)}{\bm{y}}_{(c,d)}$ for each
$j\in[i-1]$ and $\xi_{b}\sim N(0,\sigma_{b}^{2}I)$. We can check that
${\bm{x}}_{j}$ is well-defined: for all $j\leq b$ and for all
$(c,d)\in\textsc{Node}(j)$, we have $(c,d)<(a,b)$ by definition of Node and
thus ${\bm{x}}_{1:i-1}$ can be computed from ${\bm{y}}_{(i,j)<(a,b)}$ for all
$i\in[a,b]$.

Next, since for all neighboring $Z_{1:n},Z_{1:n}^{\prime}\in{\cal Z}$,
$\|{\cal M}^{(i)}({\bm{x}}_{1:i-1},Z_{i})-{\cal
M}^{(i)}({\bm{x}}_{1:i-1},Z_{i}^{\prime})\|\leq s_{i}$, ${\cal
R}^{(a,b)}({\bm{y}}_{(c,d)<(a,b)},\cdot)$ has sensitivity bounded by
$s_{(a,b)}:=\max_{i\in[a,b]}s_{i}$. Therefore, upon adding Gaussian noise
${\cal N}(0,\sigma_{b}^{2}I)$, ${\cal
R}^{(a,b)}({\bm{y}}_{(c,d)<(a,b)},\cdot)$ is $(\alpha,\epsilon_{(a,b)})$-RDP
where $\epsilon_{(a,b)}={\alpha s_{(a,b)}^{2}}/{2\sigma_{b}^{2}}$.

Now we are ready to apply Lemma C.1. Let ${\cal A}_{\cal R}:{\cal
Z}\to\prod{\cal S}^{(a,b)}$ be the composition of ${\cal R}$, i.e., given
dataset $Z_{1:n}$ sequentially computes ${\bm{y}}_{(a,b)}={\cal
R}^{(a,b)}({\bm{y}}_{(c,d)<(a,b)},Z_{1:n})$ and outputs
${\bm{y}}_{(a,b)\in{\mathbb{T}}}$. Then by Lemma C.1, ${\cal A}_{\cal R}$ is
$(\alpha,\epsilon)$-RDP where

$\epsilon\leq\max_{q}\sum_{(a,b)\in\textsc{Out}(q)}\epsilon_{(a,b)}=\max_{q}\sum_{(a,b)\in\textsc{Out}(q)}\max_{i\in[a.b]}\frac{\alpha
s_{i}^{2}}{2\sigma_{b}^{2}}.$

Observe that node $(a,b)\in\textsc{Out}(q)$ if and only if the $q$-th data in
$Z_{1:n}$ is in $Z_{i}$ and $i\in[a,b]$. Since there is exactly one such node
in each of $\lceil\log_{2}n\rceil+1$ layers in the binary tree associated with
${\mathbb{T}}$, we have $|\textsc{Out}(q)|=\lceil\log_{2}n\rceil+1\leq 2\ln
n$. Consequently,

$\epsilon=\frac{\alpha\rho^{2}}{2}\leq\alpha\ln n\cdot\max_{b\in[n],i\leq
b}\frac{s_{i}^{2}}{\sigma_{b}^{2}}.$

Finally, we conclude the proof by claiming that algorithm ${\cal A}$ defined
in the theorem can be derived from ${\cal A}_{\cal R}$ after post-processing.
Observe that $\sum_{(a,b)\in\textsc{Node}(i)}\sum_{j=a}^{b}=\sum_{j=1}^{i}$,
so by equation 5,

$\displaystyle{\bm{x}}_{i}=\sum_{(a,b)\in\textsc{Node}(i)}{\bm{y}}_{(a,b)}$
$\displaystyle=\sum_{(a,b)\in\textsc{Node}(i)}\left(\sum_{j=a}^{b}{\cal
M}^{(j)}({\bm{x}}_{1:j-1},Z_{j})+\xi_{b}\right)$
$\displaystyle=\sum_{j=1}^{i}{\cal
M}^{(j)}({\bm{x}}_{1:j-1},Z_{j})+\textsc{Tree}(i).$

Therefore, ${\cal A}$ is indeed a post-processing of ${\cal A}_{\cal R}$,
which concludes the proof. ∎

###  C.2 Proof of Corollary 4.4

See 4.4

###### Proof.

Since the private oracle defined in Algorithm 4 uses disjoint data in
different iteration $k\in[K]$, Algorithm 3 is a post-processing of
$\\{(\tilde{\bm{g}}_{1}^{k},\ldots,\tilde{\bm{g}}_{T}^{k})\\}_{k\in[K]}$.
Therefore, it suffices to prove that for each $k\in[K]$, the composition
$(\tilde{\bm{g}}_{1}^{k},\ldots,\tilde{\bm{g}}_{T}^{k})$ is
$(\alpha,\alpha\rho^{2}/2)$-RDP.

The key is to observe that
$(\tilde{\bm{g}}_{1}^{k},\ldots,\tilde{\bm{g}}_{T}^{k})$ can be written as the
adaptive composition in Theorem 4.3. Let ${\bm{g}}_{1}^{k}={\cal
M}^{(1)}(Z_{1}^{k})\triangleq\textsc{Grad}_{f,\delta}({\bm{w}}_{1}^{k},Z_{1}^{k})$
and ${\bm{d}}_{i}^{k}={\cal
M}^{(i)}(\tilde{\bm{g}}_{1:i-1}^{k},Z_{i}^{k})\triangleq\textsc{Diff}_{f,\delta}({\bm{w}}_{i}^{k},{\bm{w}}_{i-1}^{k},Z_{i}^{k})$.
This is well-defined because ${\bm{w}}_{i}^{k}$ is a post-processing of
$\tilde{\bm{g}}_{1:i-1}^{k}$ by construction of O2NC. Therefore,
${\bm{g}}_{t}^{k}={\bm{g}}_{1}^{k}+\sum_{i=2}^{t}{\bm{d}}_{i}^{k}=\sum_{i=1}^{t}{\cal
M}^{(i)}(\tilde{\bm{g}}_{1:i-1}^{k},Z_{i}^{k})$, and Theorem 4.3 can be
applied.

By Lemma 3.1, the sensitivity of ${\cal M}^{(1)}$ is bounded by
$s_{1}=\frac{2dL}{B_{1}}$. By Remark 4.1 and Lemma 3.2, the sensitivity of
${\cal M}^{(i)}(\tilde{\bm{g}}_{1:i-1}^{k},\cdot)$ is bounded by
$s_{i}=\frac{2dL}{B_{2}\delta}\|{\bm{w}}_{i}^{k}-{\bm{w}}_{i-1}^{k}\|\leq\frac{4dL}{B_{2}T}$
for all $i\geq 2$. Since we assume $B_{1}\geq TB_{2}/2$, it holds that
$s_{1}\leq s_{t}$ for all $t\geq 2$. Therefore, upon setting
$\sigma_{t}={\sqrt{2\ln T}s_{2}}/{\rho}$ for all $t\in[T]$, Theorem 4.3
implies that $(\tilde{\bm{g}}_{1}^{k},\ldots\tilde{\bm{g}}_{T}^{k})$ is
$(\alpha,\alpha\rho^{\prime 2}/2)$-RDP where

$\rho^{\prime}\leq\sqrt{2\ln T}\cdot\max_{b\in[n],i\leq
n}\frac{s_{i}}{\sigma_{b}}\leq\sqrt{2\ln
T}\cdot\frac{s_{2}}{\sigma_{2}}=\rho.\qed$

###  C.3 Proof of Corollary 4.5

See 4.5

###### Proof.

Recall that $\textsc{Tree}(t)=\sum_{(\cdot,i)\in\textsc{Node}(t)}\xi_{i}$.
Since $\xi_{i}$’s are independent and $\xi_{i}\sim{\cal
N}(0,\sigma_{i}^{2}I)$,

$\mathbb{E}\|\textsc{Tree}(t)\|^{2}=\sum_{(\cdot,i)\in\textsc{Node}(t)}\mathbb{E}\|\xi_{i}\|^{2}=\sum_{(\cdot,i)\in\textsc{Node}(t)}d\sigma_{i}^{2}\leq
2\ln(t)d\sigma^{2}.$

The last inequality follows from Remark 4.2 that $|\textsc{Node}(t)|\leq
2\ln(t)$. We then conclude the proof by substituting the value of $\sigma$
defined in Corollary 4.4. ∎

##  Appendix D Missing Proofs in Section 4.3

See 4.6

###### Proof.

First, by fundamental theorem of calculus, we have

$\displaystyle F({\bm{x}}_{t+1}^{k})-F({\bm{x}}_{t}^{k})$
$\displaystyle=\int_{0}^{1}\langle\nabla
F({\bm{x}}_{t}^{k}+t({\bm{x}}_{t+1}^{k}-{\bm{x}}_{t}^{k})),{\bm{x}}_{t+1}^{k}-{\bm{x}}_{t}^{k}\rangle\,dt$
$\displaystyle=\int_{0}^{1}\langle\nabla
F({\bm{x}}_{t}^{k}+t\Delta_{t}^{k}),\Delta_{t}^{k}\rangle\,dt=\mathbb{E}_{s_{t}^{k}}\langle\nabla
F({\bm{w}}_{t}^{k}),\Delta_{t}^{k}\rangle.$

Next, upon taking the telescopic sum (and recall $x_{1}^{k+1}=x_{T+1}^{k}$),
we have

$\displaystyle\mathbb{E}F({\bm{x}}_{T+1}^{K})-F({\bm{x}}_{1}^{1})$
$\displaystyle=\sum_{k=1}^{K}\sum_{t=1}^{T}\mathbb{E}[F({\bm{x}}_{t+1}^{k})-F({\bm{x}}_{t}^{k})]=\sum_{k=1}^{K}\sum_{t=1}^{T}\mathbb{E}\langle\nabla
F({\bm{w}}_{t}^{k}),\Delta_{t}^{k}\rangle.$

Note that $\langle\nabla
F({\bm{w}}_{t}^{k}),\Delta_{t}^{k}\rangle=\langle\nabla
F({\bm{w}}_{t}^{k}),{\bm{u}}^{k}\rangle+\langle\tilde{\bm{g}}_{t}^{k},\Delta_{t}^{k}-{\bm{u}}^{k}\rangle+\langle\nabla
F({\bm{w}}_{t}^{k})-\tilde{\bm{g}}_{t}^{k},\Delta_{t}^{k}-{\bm{u}}^{k}\rangle$.
Therefore, by definition of ${\bm{u}}^{k}$ and
$\mathrm{Reg}_{T}({\bm{u}}^{k})$,

$\sum_{t=1}^{T}\langle\nabla
F({\bm{w}}_{t}^{k}),\Delta_{t}^{k}\rangle=-D\left\|\sum_{t=1}^{T}\nabla
F({\bm{w}}_{t}^{k})\right\|+\mathrm{Reg}_{T}({\bm{u}}^{k})+\sum_{t=1}^{T}\langle\nabla
F({\bm{w}}_{t}^{k})-\tilde{\bm{g}}_{t}^{k},\Delta_{t}^{k}-{\bm{u}}^{k}\rangle.$

Upon rearranging the inequality and applying
$F({\bm{x}}_{T+1}^{K})-F({\bm{x}}_{1}^{1})\leq F^{*}$, we have

$\displaystyle\sum_{k=1}^{K}D\mathbb{E}\left\|\sum_{t=1}^{T}\nabla
F({\bm{w}}_{t}^{k})\right\|$ $\displaystyle\leq
F^{*}+\sum_{k=1}^{K}\mathbb{E}\mathrm{Reg}_{T}({\bm{u}}^{k})+\mathbb{E}\sum_{k=1}^{K}\sum_{t=1}^{T}\langle\nabla
F({\bm{w}}_{t}^{k})-\tilde{\bm{g}}_{t}^{k},\Delta_{t}^{k}-{\bm{u}}_{t}^{k}\rangle.$

Finally, note that $\|{\bm{w}}_{t}^{k}-\overline{w}^{k}\|\leq DT=\delta$, so
$\|\nabla F(\overline{w}^{k})\|_{\delta}\leq\|\frac{1}{T}\sum_{t=1}^{T}\nabla
F({\bm{w}}_{t}^{k})\|$ by definition of $\|\cdot\|_{\delta}$. Moreover,
$\mathbb{E}\|\nabla
F(\overline{\bm{w}})\|_{\delta}=\mathbb{E}[\frac{1}{K}\sum_{i=1}^{K}\|\nabla
F(\overline{w}^{k})\|_{\delta}]$. Therefore, dividing both sides of the
inequality by $DKT$ concludes the proof. ∎

See 4.7

###### Proof.

By Lemma 2.2, $\hat{F}_{\delta}$ is differentiable. Next, since
$\|\hat{F}_{\delta}-F\|\leq L\delta$,

$\hat{F}_{\delta}({\bm{x}}_{1})-\inf_{\bm{x}}\hat{F}_{\delta}({\bm{x}})\leq
F({\bm{x}}_{1})-\inf_{\bm{x}}F({\bm{x}})+2L\delta=F^{*}+2L\delta.$

Hence, upon applying Lemma 4.6 on the uniform smoothing $\hat{F}_{\delta}$, we
have

$\mathbb{E}\|\hat{F}_{\delta}(\overline{\bm{w}})\|_{\delta}\leq\frac{F^{*}+2L\delta}{DKT}+\sum_{k=1}^{K}\frac{\mathbb{E}\mathrm{Reg}_{T}(\hat{\bm{u}}^{k})}{DKT}+\sum_{k=1}^{K}\sum_{t=1}^{T}\frac{\mathbb{E}\langle\nabla\hat{F}_{\delta}({\bm{w}}_{t}^{k})-\tilde{\bm{g}}_{t}^{k},\Delta_{t}^{k}-\hat{\bm{u}}^{k}\rangle}{DKT}.$

Finally, by Corollary 2.3, $\mathbb{E}\|F(\overline{\bm{w}})\|_{2\delta}$ is
also bounded by RHS, which concludes the proof. ∎

See 4.8

###### Proof.

First, we recall a martingale concentration bound. Let
${\bm{v}}_{1},\ldots,{\bm{v}}_{n}$ be a sequence of random vectors and let
${\cal F}_{i}=\sigma({\bm{v}}_{1:i})$ be the $\sigma$-algebra generated by
${\bm{v}}_{1:i}$. If $\mathbb{E}[{\bm{v}}_{i}|{\cal F}_{i-1}]=0$, then for all
cross terms $i\leq j$, $v_{i}\in{\cal F}_{j-1}$ and thus
$\mathbb{E}\langle{\bm{v}}_{i},{\bm{v}}_{j}\rangle=\mathbb{E}_{{\cal
F}_{j-1}}\langle{\bm{v}}_{i},\mathbb{E}[{\bm{v}}_{j}|{\cal
F}_{j-1}]\rangle=0$. Consequently,

$\textstyle\mathbb{E}\|\sum_{i=1}^{n}{\bm{v}}_{i}\|^{2}=\sum_{i=1}^{n}\mathbb{E}\|{\bm{v}}_{i}\|^{2}.$

In our case, note that
$\nabla\hat{F}({\bm{w}}_{t}^{k})=\nabla\hat{F}({\bm{w}}_{1}^{k})+\sum_{i=2}^{t}\nabla\hat{F}({\bm{w}}_{t}^{k})-\nabla\hat{F}({\bm{w}}_{t-1}^{k})$
and recall that
${\bm{g}}_{t}^{k}={\bm{g}}_{1}^{k}+\sum_{i=2}^{t}{\bm{d}}_{i}$. Therefore, by
the concentration inequality and Lemma 3.1 and 3.2,

$\displaystyle\mathbb{E}\|\nabla\hat{F}({\bm{w}}_{t}^{k})-{\bm{g}}_{t}^{k}\|^{2}$
$\displaystyle\leq\mathbb{E}\|\nabla\hat{F}({\bm{w}}_{1}^{k})-{\bm{g}}_{1}^{k}\|^{2}+\sum_{i=2}^{t}\mathbb{E}\|\nabla\hat{F}({\bm{w}}_{i}^{k})-\nabla\hat{F}({\bm{w}}_{i-1}^{k})-{\bm{d}}_{i}^{k}\|^{2}$
$\displaystyle\leq\frac{16dL^{2}}{B_{1}}+\sum_{i=2}^{t}\frac{16dL^{2}}{B_{2}\delta^{2}}\mathbb{E}\|{\bm{w}}_{i}^{k}-{\bm{w}}_{i-1}^{k}\|^{2}.$

We conclude the proof by Remark 4.1 that
$\|{\bm{w}}_{i}^{k}-{\bm{w}}_{i-1}^{k}\|\leq 2D\leq\frac{2\delta}{T}$. ∎

##  Appendix E Comparison with naive approach

Algorithm 6 Naive private gradient oracle

1:Input: dataset ${\cal Z}$, constant $B$, noise $\sigma$

2:Initialize: Partition ${\cal Z}$ into $KT$ subsets $Z_{t}^{k}$ of size $B$.
The data size is $|{\cal Z}|=M=BKT$.

3:Upon receiving round index $k,t$ and parameter ${\bm{w}}_{t}^{k}$:

4:Sample ${\bm{u}}_{1},\ldots,{\bm{u}}_{B}\sim\mathrm{Uniform}(\SS)$ i.i.d.

5:${\bm{g}}_{t}^{k}\leftarrow\frac{1}{B}\sum_{i=1}^{B}\frac{d}{2\delta}(f({\bm{w}}_{t}^{k}+\delta{\bm{u}}_{i},z_{i})-f({\bm{w}}_{t}^{k}-\delta{\bm{u}}_{i},z_{i})){\bm{u}}_{i}$
where $z_{i}$ is the $i$-th data in $Z_{t}^{k}$.

6:Return $\tilde{\bm{g}}_{t}^{k}\leftarrow{\bm{g}}_{t}^{k}+\xi_{t}^{k}$ where
$\xi_{t}^{k}\sim{\cal N}(0,\sigma^{2}I)$ i.i.d.

To concrete the discussion from Section 4.1, we’ll delve into the analysis of
the naive private algorithm built on O2NC. Specifically, this algorithm
replaces the gradient oracle (as seen in line 5 of Algorithm 3) with a direct
zeroth-order estimator, as defined in Algorithm 6. As a remark,
${\bm{g}}_{t}^{k}$ is an unbiased estimator and
$\mathbb{E}\|{\bm{g}}_{t}^{k}\|^{2}\lesssim L^{2}(\frac{d}{B}+1)$, according
to (Kornowski & Shamir, 2023) Remark 6. Moreover, following the same argument
as the sensitivity bound in Lemma 3.1, the sensitivity of ${\bm{g}}_{t}^{k}$
is bounded by $O(dL/B)$. Consequently, if we set $\sigma=dL/B\rho$, each
$\tilde{\bm{g}}_{t}^{k}$ achieves $(\alpha,\alpha\rho^{2}/2)$-RDP.

Although the algorithm appears more straightforward, its convergence analysis
is less favorable. Following the proof idea of Theorem 4.9, we first recall
the result in Corollary 4.7:

$\mathbb{E}\|\nabla
F(\overline{\bm{w}})\|_{2\delta}\leq\frac{F^{*}+2L\delta}{DKT}+\sum_{k=1}^{K}\frac{\mathbb{E}\mathrm{Reg}_{T}(\hat{\bm{u}}^{k})}{DKT}+\sum_{k=1}^{K}\sum_{t=1}^{T}\frac{\mathbb{E}\langle\nabla\hat{F}_{\delta}({\bm{w}}_{t}^{k})-\tilde{\bm{g}}_{t}^{k},\Delta_{t}^{k}-\hat{\bm{u}}^{k}\rangle}{DKT}.$

Recall that $\mathbb{E}[\mathrm{Reg}_{T}(\hat{\bm{u}}^{k})]\leq
D\sqrt{\sum_{t=1}^{T}\mathbb{E}\|\tilde{\bm{g}}_{t}^{k}\|^{2}}$. Therefore, we
can bound the regret of OSD by

$\displaystyle\mathbb{E}[\mathrm{Reg}_{T}(\hat{\bm{u}}^{k})]$
$\displaystyle\leq\textstyle
D\sqrt{\sum_{t=1}^{T}\mathbb{E}\|{\bm{g}}_{t}^{k}\|^{2}+\mathbb{E}\|\xi_{t}^{k}\|^{2}}$
$\displaystyle\lesssim\textstyle
D\sqrt{\sum_{t=1}^{T}L^{2}(\frac{d}{B}+1)+\frac{d^{3}L^{2}}{B^{2}\rho^{2}}}$
$\displaystyle\lesssim\textstyle
DL\sqrt{T}\left(\frac{\sqrt{d}}{\sqrt{B}}+1+\frac{d^{3/2}}{B\rho}\right).$

Next, we bound the sum of inner product. It’s important to note that
$\mathbb{E}\langle\nabla\hat{F}_{\delta}({\bm{w}}_{t}^{k})-\tilde{\bm{g}}_{t}^{k},\Delta_{t}^{k}\rangle=0$
because $\Delta_{t}^{k}$ is independent of $Z_{t}^{k}$. Therefore, using the
martingale concentration bound, we have

$\displaystyle\textstyle\sum_{t=1}^{T}\mathbb{E}\langle\nabla\hat{F}_{\delta}({\bm{w}}_{t}^{k})-\tilde{\bm{g}}_{t}^{k},\Delta_{t}^{k}-\hat{\bm{u}}^{k}\rangle$
$\displaystyle=\textstyle\mathbb{E}\langle\sum_{t=1}^{T}\nabla\hat{F}_{\delta}({\bm{w}}_{t}^{k})-\tilde{\bm{g}}_{t}^{k},-\hat{\bm{u}}^{k}\rangle$
$\displaystyle\leq\textstyle
D\sqrt{\sum_{t=1}^{T}\mathbb{E}\|\nabla\hat{F}_{\delta}({\bm{w}}_{t}^{k})-{\bm{g}}_{t}^{k}\|^{2}+\mathbb{E}\|\xi_{t}^{k}\|^{2}}$
$\displaystyle\lesssim\textstyle
DL\sqrt{T}\left(\frac{\sqrt{d}}{\sqrt{B}}+1+\frac{d^{3/2}}{B\rho}\right).$

Upon substituting back into Corollary 4.7, we have

$\displaystyle\mathbb{E}\|\nabla F(\overline{\bm{w}})\|_{2\delta}$
$\displaystyle\lesssim\frac{F^{*}+L\delta}{DKT}+\frac{L}{\sqrt{T}}\left(\frac{\sqrt{d}}{\sqrt{B}}+1+\frac{d^{3/2}}{B\rho}\right)$
Upon replacing $D=\delta/T$ and $M=KBT$, we have
$\displaystyle\lesssim\frac{(F^{*}+L\delta)BT}{\delta
M}+\frac{\sqrt{d}L}{\sqrt{BT}}+\frac{L}{\sqrt{T}}+\frac{d^{3/2}L}{B\sqrt{T}\rho}$
To achieve the optimal non-private rate $O(d\delta^{-1}\epsilon^{-3})$, we
need to set $B=1$. Therefore, upon setting $T=\min\\{(\frac{\sqrt{d}L\delta
M}{F^{*}+L\delta})^{2/3},(\frac{d^{3/2}L\delta
M}{(F^{*}+L\delta)\rho})^{2/3}\\}$, we have
$\displaystyle\lesssim\left(\frac{(F^{*}+L\delta)dL^{2}}{\delta
M}\right)^{1/3}+\left(\frac{(F^{*}+L\delta)d^{3/2}L^{2}}{\rho\delta
M}\right)^{1/3}.$

Equivalently, $\mathbb{E}\|\nabla
F(\overline{\bm{w}})\|_{2\delta}\leq\epsilon$ if
$M=\Omega\left(d(\frac{F^{*}L^{2}}{\delta\epsilon^{3}}+\frac{L^{3}}{\epsilon^{3}})+d^{3/2}(\frac{F^{*}L^{2}}{\rho\delta\epsilon^{3}}+\frac{L^{3}}{\rho\epsilon^{3}})\right)$,
whose dominating term is $\Omega(d^{3/2}\rho^{-1}\delta^{-1}\epsilon^{-3})$.
In contrast, our carefully designed algorithm only requires
$\tilde{\Omega}(d\delta^{-1}\epsilon^{-3}+d^{3/2}\rho^{-1}\delta^{-1}\epsilon^{-2})$
samples, as proved in Theorem 4.9. Notably, the naive algorithm suffers an
additional cost of $\epsilon^{-1}$ for privacy.