# Differentially Private Non-convex Learning for Multi-layer Neural Networks

Hanpu Shen  UCI  Cheng-Long Wang  KAUST  Zihang Xiang  KAUST  Yiming Ying
University at Albany  Di Wang  KAUST

###### Abstract

This paper focuses on the problem of Differentially Private Stochastic
Optimization for (multi-layer) fully connected neural networks with a single
output node. In the first part, we examine cases with no hidden nodes,
specifically focusing on Generalized Linear Models (GLMs). We investigate the
well-specific model where the random noise possesses a zero mean, and the link
function is both bounded and Lipschitz continuous. We propose several
algorithms and our analysis demonstrates the feasibility of achieving an
excess population risk that remains invariant to the data dimension. We also
delve into the scenario involving the ReLU link function, and our findings
mirror those of the bounded link function. We conclude this section by
contrasting well-specified and misspecified models, using ReLU regression as a
representative example.

In the second part of the paper, we extend our ideas to two-layer neural
networks with sigmoid or ReLU activation functions in the well-specified
model. In the third part, we study the theoretical guarantees of DP-SGD in
Abadi et al. (2016) for fully connected multi-layer neural networks. By
utilizing recent advances in Neural Tangent Kernel theory, we provide the
first excess population risk when both the sample size and the width of the
network are sufficiently large. Additionally, we discuss the role of some
parameters in DP-SGD regarding their utility, both theoretically and
empirically.

###### Index Terms:

differential privacy, non-convex learning, DP-ERM

##  I Introduction

In the domain of machine learning, extracting knowledge from data harboring
sensitive attributes is an evolving concern. Such a task mandates algorithms
that can proficiently interpret the data while upholding established privacy
benchmarks. Differential privacy (DP) [1], in this context, has gained
traction as a seminal framework for statistical data protection. Recognized
widely in contemporary research, DP ensures that individual data remains non-
retrievable post-analysis, offering a robust defense mechanism against privacy
infractions. This underscores a burgeoning interest in devising learning
architectures where DP considerations are intrinsically woven into the
analytic process.

Stochastic Optimization (SO) and its empirical form, Empirical Risk
Minimization (ERM), are the most fundamental models in machine learning and
statistics. They have numerous applications in fields such as medicine,
finance, genomics, and social science. However, these applications often
involve sensitive data, making it essential to design differentially private
algorithms for SO and ERM, corresponding to the problems of DP-SO and DP-ERM,
respectively. While DP-SO and DP-ERM have been extensively studied for more
than a decade, most of the existing work considers the case where the loss
function is convex. The problem of DP-SO and DP-ERM with non-convex loss
functions remains far from well-understood due to their complex nature.
Although there is some preliminary work, such as [2, 3, 4, 5], there are still
two critical issues. Firstly, most of the existing work adopts the gradient
norm of the population risk function to measure the utility, which is quite
different from the convex case where we use the excess population risk
instead. However, using the gradient norm is inadequate for indicating how
close the private model is to the optimal solution [6]. Secondly, while
recently there has been some work considering the excess population risk for
non-convex loss functions [3], most research has narrowly focused on general
non-convex loss functions, overlooking the intricacies of neural network
structures. To address these issues, this paper provides the first
comprehensive and theoretical study of DP Fully Connected Neural Networks
(with a single output node) and presents several bounds of excess population
risk. Specifically, our contributions can be summarized as follows:

  1. 1.

In the first part of the paper, we focus on the simplest neural network
structure: neural networks without hidden nodes, aptly referred to as non-
convex Generalized Linear Models (GLMs). We first address the well-specified
model that is characterized by zero-mean random noise, combined with bounded
and Lipschitz link functions. For this setup, we introduce an
$(\epsilon,\delta)$-DP algorithm and demonstrate its efficacy with an output
upper bound
$\tilde{O}(\frac{1}{\sqrt{n}}+\min\\{\frac{1}{(n\epsilon)^{\frac{2}{3}}},\frac{\sqrt{\theta}}{n\epsilon}\\})$.
Here $\theta$ is an upper bound on the expected rank of the data matrix and
$n$ is the sample size. We then broaden our study to cases with unbounded link
functions, specifically when employing the ReLU activation function. In this
scenario, we establish that an upper bound of
$\tilde{O}(\frac{1}{\sqrt{n}}+\min\\{\frac{\sqrt{d}}{n\epsilon},\frac{1}{(n\epsilon)^{\frac{2}{3}}}\\})$
is feasible. Subsequently, our attention pivots to the misspecified model. To
delineate its nuances vis-à-vis the well-specified model, we spotlight the
ReLU activation function as a representative case. Within this scope, we
innovate a distinct version of DP Gradient Descent, showcasing a sample
complexity of
$\tilde{O}(\max\\{\frac{\sqrt{d}}{\epsilon\alpha},\frac{d}{\alpha^{2}}\\})$.
This sample complexity guarantees that the difference between the population
risk of our private estimator and $c\cdot\textrm{opt}$ is no more than
$\alpha$, where opt is the optimal value of population risk and $c>0$ is some
constant.

  2. 2.

Next, we extend our ideas to the problem of privately learning two-layer
neural networks. Specifically, we consider the well-specified model and study
the cases where the activation functions are either sigmoid or ReLU. Our main
contribution is to establish the sample complexity required to achieve an
error of $\alpha$ for excess population risk. For the sigmoid case, we show
that the sample complexity is
$O((\frac{kC_{1}}{\alpha})^{2C_{1}}\frac{1}{\epsilon^{2}})$, where $k$ is the
number of hidden nodes and $C_{1}$ is a positive constant. For the ReLU case
with $k$ hidden nodes, we show that the sample complexity is
$O(4^{C_{2}\frac{k}{\alpha}}\frac{1}{\epsilon^{2}})$, where $C_{2}$ is a
positive constant.

  3. 3.

In the last part, we consider general multi-layer fully connected neural
networks. Rather than introducing new methods, we delve into the theoretical
guarantees of the standard DP-SGD as detailed in [7]. Drawing upon recent
advancements in the Neural Tangent Kernel (NTK), we present the inaugural
excess population risk bound for networks where both the width of each layer
and the sample size are sufficiently large. In essence, this bound is composed
of three elements: an approximation error attributable to NTK, an error
arising from the Gaussian noise introduced in every iteration, and a combined
term representing the convergence rate and sampling error. Building on our
theoretical framework, we then delve into the intricate interplay and trade-
offs between various parameters. We also provide experimental studies to
corroborate our theoretical findings.

Due to the space limit, some additional sections and all omitted proofs are
included in Appendix.

##  II Related Work

As we mentioned earlier, there is a long list of work on DP-SO and DP-ERM.
Thus, here we only mention the theoretical work that is close to ours.

Private non-convex learning. In DP-SCO/DP-ERM with convex loss functions, the
excess population risk is commonly used to measure the utility. However, in
the non-convex case, there are three general ways to measure the utility. The
first approach is based on the first-order stationary condition, such as the
gradient $\ell_{2}$-norm of the population risk function [2, 5, 8, 9, 10, 11].
However, there are some issues with this measure. Firstly, previous work has
shown that the gradient norm tends to 0 as the sample size $n$ goes to
infinity, but there is no guarantee that such a private estimator will be
close to any non-degenerate local minimum [6]. Secondly, the gradient-norm
estimator is not always consistent with the excess empirical (population) risk
of the loss function [3].

The second approach considers using the second-order stationary condition as
the measure, which involves considering both the norm of the gradient and the
Hessian matrix minimal eigenvalue of the population risk function [3, 12]. The
motivation for this approach is based on the fact that for many machine
learning problems, such as matrix completion and dictionary learning, any
second-order stationary point is a local minimum of the problem, and all the
local minima are the global minimum. Thus, finding a global minimum is
equivalent to finding a second-order stationary point. However, the main
disadvantage of this measure is that it is only reasonable for some problems,
and it is unknown whether general neural networks satisfy the above property.

The third approach is to directly use the excess population risk, which is
similar to the convex case, and our work is along with this direction.
However, most of the previous work only considers some specific class of loss
functions, such as Polyak-Lojasiewicz loss [13]. [3] provided the first study
of DP-ERM with general non-convex loss, but their bound is $O(\frac{d}{(\log
n)\epsilon})$, which is quite large. Compared to their results, our work
considers general neural networks and provides improved bounds.

DP-GLM. DP-SO/DP-ERM with Generalized Linear loss (DP-GLL) and DP-GLM have
received considerable attention in recent years. For convex loss functions,
[14] provided the first study on DP-GLL and showed that in the unconstrained
case, the error bound can achieve $\tilde{O}(\frac{1}{\sqrt{n}\epsilon})$ in
general, which is quite different from the bound
$O(\frac{\sqrt{d}}{n\epsilon})$ for general convex DP-ERM. Later, [15] studied
the same problem and showed that in the constrained case, the error bound
could only depend on the Gaussian width of the underlying constraint set. For
the unconstrained setting, [5] showed an improved bound of
$O(\frac{\sqrt{\theta}}{n\epsilon})$, where $\theta$ is the rank of the
expectation of the data matrix. For constrained DP-GLM, [9] considered various
settings where the loss could be smooth/non-smooth and in the $\ell_{p}$ space
for general $1\leq p\leq 2$. Recently, [16] studied the optimal rates of DP-
GLM in the unconstrained setting. Specifically, when the loss is smooth and
non-negative but not necessarily Lipschitz, it showed the optimal rate of
$\tilde{O}(\frac{1}{\sqrt{n}}+\min\\{\frac{1}{(n\epsilon)^{2/3}},\frac{\sqrt{d}}{n\epsilon}\\})$.
When the loss is Lipschitz, the optimal rate is
$\tilde{O}(\frac{1}{\sqrt{n}}+\min\\{\frac{1}{\sqrt{n\epsilon}},\frac{\sqrt{\theta}}{n\epsilon}\\})$.
For non-convex losses, [5, 9] provided bounds that are independent of the
dimension for the gradient $\ell_{2}$-norm of the population risk function.
[3, 17] studied the excess population risk for some specific GLMs and showed
that their bound can be only logarithmic in the dimension. However, they need
to assume the constraint set is an $\ell_{1}$-norm ball, while our work does
not require such an assumption.

##  III Preliminaries

######  Definition 1 (Differential Privacy [1]).

Given a data universe $\mathcal{X}$, we say that two datasets
$D,D^{\prime}\subseteq\mathcal{X}$ are neighbors if they differ by only one
data record, which is denoted as $D\sim D^{\prime}$. A randomized algorithm
$\mathcal{A}$ is $(\epsilon,\delta)$-differentially private (DP) if for all
neighboring datasets $D,D^{\prime}$ and for all events $S$ in the output space
of $\mathcal{A}$, we have

$\text{Pr}(\mathcal{A}(D)\in S)\leq
e^{\epsilon}\text{Pr}(\mathcal{A}(D^{\prime})\in S)+\delta.$

######  Lemma 1 (Gaussian Mechanism).

Given any function $q:\mathcal{X}^{n}\rightarrow\mathbb{R}^{d}$, the Gaussian
mechanism is defined as $q(D)+\xi$ where
$\xi\sim\mathcal{N}(0,\frac{2\Delta^{2}_{2}(q)\log(1.25/\delta)}{\epsilon^{2}}\mathbb{I}_{d})$,
where $\Delta_{2}(q)$ is the $\ell_{2}$-sensitivity of the function $q$, i.e.,
$\Delta_{2}(q)=\sup_{D\sim D^{\prime}}||q(D)-q(D^{\prime})||_{2}.$ Gaussian
mechanism preserves $(\epsilon,\delta)$-DP for $0<\epsilon,\delta<1$.

######  Definition 2 (DP-SO [18]).

Given a dataset $D=\\{z_{1},\cdots,z_{n}\\}$ from a data universe
$\mathcal{Z}$ where each $z_{i}=(x_{i},y_{i})$ with a feature vector $x_{i}$
and a label/response $y_{i}$ is i.i.d. sampled from some unknown distribution
$\mathcal{P}$, a convex constraint set $\mathcal{W}\subseteq\mathbb{R}^{d}$,
and a (non-convex) loss function
$\ell:\mathcal{W}\times\mathcal{Z}\mapsto\mathbb{R}$. Differentially Private
Stochastic Optimization (DP-SO) is to find a model $w^{\text{priv}}$ to
minimize the population risk, i.e.,
$L_{\mathcal{P}}(w)=\mathbb{E}_{(x,y)\sim\mathcal{P}}[\ell(w;x,y)]$ with the
guarantee of being differentially private.111Note that in this paper, we
consider the improper learning case, that is $w^{\text{priv}}$ may not be in
$\mathcal{W}$. The utility of $w^{\text{priv}}$ is measured by the (expected)
excess population risk
$\mathbb{E}L_{\mathcal{P}}(w^{\text{priv}})-\min_{w\in\mathbb{\mathcal{W}}}L_{\mathcal{P}}(w),$
where the expectation takes over the randomness of the algorithm and the input
data. Besides the population risk, we can also measure the empirical risk of
dataset $D$: $\hat{L}(w,D)=\frac{1}{n}\sum_{i=1}^{n}\ell(w,z_{i}).$

It is notable that besides the error bound, to better demonstrate our results,
we may also consider the sample complexity to achieve a fixed error $\alpha$
to measure the utility of DP algorithms.

######  Definition 3.

A function $f(\cdot)$ is $G$-Lipschitz if for all
$w,w^{\prime}\in\mathcal{W}$, $|f(w)-f(w^{\prime})|\leq
G\|w-w^{\prime}\|_{2}$.

######  Definition 4.

A function $f(\cdot)$ is $\beta$-smooth on $\mathcal{W}$ if for all
$w,w^{\prime}\in\mathcal{W}$, $f(w^{\prime})\leq f(w)+\langle\nabla
f(w),w^{\prime}-w\rangle+\frac{\beta}{2}\|w^{\prime}-w\|_{2}^{2}.$

######  Definition 5.

A function $f(\cdot)$ is $\alpha$-strongly convex on $\mathcal{W}$ if for all
$w,w^{\prime}\in\mathcal{W}$, $f(w^{\prime})\geq f(w)+\langle\nabla
f(w),w^{\prime}-w\rangle+\frac{\alpha}{2}\|w^{\prime}-w\|_{2}^{2}.$

######  Definition 6.

A random matrix $\Phi\in\mathbb{R}^{k\times d}$ satisfies
$(\alpha,\beta)$-Johnson-Lindentrauss (JL) property if for any
$u,v\in\mathbb{R}^{d}$ and any $\alpha>0$ we have $\mathbb{P}[|\langle\Phi
u,\Phi v\rangle-\langle u,v\rangle|>\alpha\|u\|_{2}\|v\|_{2}]\leq\beta,$ where
the probability takes over the randomness of the distribution of $\Phi$.

Specifically, when $R\in\mathbb{R}^{k\times d}$ is a random Gaussian matrix
with $k=O(\frac{\log 1/\beta}{\alpha^{2}})$ each entry is i.i.d. sampled from
$\mathcal{N}(0,1)$. Then the matrix $A=\frac{1}{\sqrt{k}}R$ satisfies
$(\alpha,\beta)$-JL property.

##  IV Private Non-convex GLMs

###  IV-A Well-specified Model

####  IV-A1 Bounded Link Function Case

In this section, we will examine the problem of Generalized Linear Models
(GLMs), which are neural networks without hidden layers and with a single
output neuron. Specifically, we will begin by considering a simplified
scenario in which the statistical model is well-specified,222In the
literature, the well-specified setting is also extensively referred to as the
”noisy teacher” setting [19] or the well-structured noise model [20] meaning
that the Bayes optimal classifier satisfies $\mathbb{E}[y|x]=\sigma(\langle
w^{*},x\rangle)$ for some underlying parameter $w^{*}\in\mathbb{R}^{d}$ and
non-convex link function $\sigma$:

$y=\sigma(\langle w^{*},x\rangle)+\zeta,$ (1)

where $\zeta$ is random noise with zero mean. In the following, we will
introduce several assumptions that will be used throughout this section.

######  Assumption 1.

Assume there exist constants $W,G,B=O(1)$ such that $\|w^{*}\|_{2}\leq W$,
$y\in[-B,B]$ and the link function $\sigma:\mathbb{R}\mapsto[-B,B]$ is
$G$-Lipschitz and non-monotone decreasing. We also assume $\|x\|_{2}\leq 1$.
333For simplicity, here we assume $\|x\|_{2}\leq 1$, and for the range of
$\sigma$ we use the same $B$ as the range of $y$, we can easily extend our
results to general cases.

The assumption of $\|w^{*}\|_{2}\leq W$ for a given known $W$ is a recurring
theme in the literature on private learning and statistical estimation.
Notably, even in linear models where $\sigma$ serves as the identity function,
this presumption consistently appears in prior research [21, 22].

In fact, many activation functions that are commonly used in neural networks
satisfy Assumption 1, such as sigmoid function
$\sigma(x)=\frac{1}{1+\exp(-x)}$ and tanh function
$\sigma(x)=\frac{\exp(x)-\exp(-x)}{\exp(x)+\exp(-x)}$.

Under the well-specified model (1), we consider the expected squared error as
the population risk function, i.e.,
$L_{\mathcal{P}}(w)=\mathbb{E}_{(x,y)\sim\mathcal{P}}(\sigma(\langle
w,x\rangle)-y)^{2}.$

To solve the problem, the most natural idea is to approximate the population
function $L_{\mathcal{P}}(w)$ by some convex stochastic function. Motivated by
[23, 24], here we consider the following surrogate (convex) loss function:

$\ell(w;x,y)=\int_{0}^{\langle w,x\rangle}(\sigma(z)-y)dz.$ (2)

The following result shows that the loss $\ell$ is convex, Lipschitz and
smooth:

######  Lemma 2.

Under Assumption 1, for any $(x,y)\sim\mathcal{P}$, function $\ell(\cdot;x,y)$
is convex and $2B$-Lipschitz. Moreover, if $\sigma$ has (sub)gradient
anywhere, then the rank of the Hessian matrix for $\ell(\cdot;x,y)$ is 1, and
$\ell(\cdot;x,y)$ is $G$-smooth.

Algorithm 1 DP non-convex GLM

0: Private dataset: $D$ = $\\{({x}_{i},y_{i})\\}_{i=1}^{n}$, link function
$\sigma$ satisfying Assumption 1 and has (sub)gradient anywhere; privacy
parameters $0<\epsilon,\delta\leq 1$, upper bound $\theta$ of the expected
rank of data matrix.

1: If $\epsilon>\frac{\theta^{\frac{3}{2}}}{n}$, run Algorithm 2. Otherwise,
run Algorithm 3.

In the following, we use the notations
$L^{\ell}(w;D)=\frac{1}{n}\sum_{i=1}^{n}\ell(w;x_{i},y_{i})$ and
$L^{\ell}_{\mathcal{P}}(w)=\mathbb{E}[\ell(w;x,y)]$ to represent the empirical
risk and population risk functions for the loss $\ell$ in (2), respectively.
The following lemma, given by [24], shows that the optimal parameter $w^{*}$
is also the minimizer of $L^{\ell}_{\mathcal{P}}(\cdot)$. Moreover, for any
$w$, the excess population risk of $w$ is dominated by the excess population
risk of loss $\ell(w;x,y)$.

######  Lemma 3.

For any $w\in\mathbb{R}^{d}$, we have
$L_{\mathcal{P}}(w)-L_{\mathcal{P}}(w^{*})\leq
2G(L^{\ell}_{\mathcal{P}}(w)-L^{\ell}_{\mathcal{P}}(w^{*})).$

Thus, motivated by Lemma 3, now we aim to find a private estimator
$w^{priv}\in\mathbb{R}^{d}$ to minimize $L^{\ell}_{\mathcal{P}}(w)$. Moreover,
we can see from the form of the loss $\ell$ and Lemma 2 that if $\sigma$ has
subgradient anywhere, then $\ell(\cdot)$ will be a generalized linear loss,
i.e., $\ell(w;x,y)=g(\langle w,x\rangle,y)$ where $g(\cdot,y)$ is convex,
$2B$-Lipschitz, and $G$-smooth. Therefore, we can use unconstrained DP-SO
algorithms for convex generalized linear loss to $\ell$ to obtain a private
estimator. Here, we adopt the Phased SGD method for convex GLM in [9] (see
Algorithm 2 for details). Furthermore, motivated by [16], we propose a new
method that uses a JL matrix to preprocess the data and then performs
Algorithm 2 over the projected data. Note that using Phased SGD is crucial for
our analysis of two-layer neural networks in later sections (see Remark 2 for
details). The entire algorithm is provided in Algorithm 1.

Algorithm 2 Phased SGD for non-convex GLM

0: Private dataset: $D$ = $\\{({x}_{i},y_{i})\\}_{i=1}^{n}$, link function
$\sigma$ satisfying Assumption 1 and has (sub)gradient anywhere; privacy
parameters $0<\epsilon,\delta\leq 1$.

1: Denote the loss function $\ell$ as $\ell(w;x,y)=\int_{0}^{\langle
w,x\rangle}(\sigma(z)-y)dz$.

2: Set $k=\lceil\log_{2}(n)\rceil$, partite the whole dataset S into $k$
subsets $\\{D_{1},\cdots,D_{k}\\}$. Denote $n_{i}$ as the number of samples in
$D_{i}$, i.e., $|D_{i}|=n_{i}$ where $n_{i}=\lfloor 2^{-i}n\rfloor$. Take a
random initial vector $w_{0}\in\mathcal{W}$.

3: for $i=1,\cdots,k$ do

4: Let $\eta_{i}=\frac{\eta}{4^{i}}$ and $w_{i}^{1}=w_{i-1}$.

5: for $t=1,\cdots,n_{i}$ do

6: Update
$w_{i}^{t+1}=w_{i}^{t}-\eta_{i}\nabla\ell(w_{i}^{t};x_{i}^{t},y_{i}^{t})=w_{i}^{t}-\eta_{i}(\sigma(\langle
w_{i}^{t},x_{i}^{t}\rangle)-y_{i}^{t})x_{i}^{t}$, where
$(x_{i}^{t},y_{i}^{t})$ is the $t$-th sample of $D_{i}$.

7: end for

8: Denote $w_{i}=\bar{w}_{i}+\zeta_{i}$, where
$\bar{w}_{i}=\frac{1}{n_{i}}\sum_{t=1}^{n_{i}}w_{i}^{t}$ and
$\zeta_{i}\sim\mathcal{N}(0,\tau_{i}^{2}\mathbb{I}_{d})$ with
$\tau_{i}=\frac{8B\eta_{i}\sqrt{\log\frac{1}{\delta}}}{\epsilon}$.

9: end for

In the following, we will show the utility. We denote $\theta$ as the upper
bound of $\mathbb{E}_{D\sim\mathcal{P}^{n}}[\text{Rank}(V)]$, where $V$ is a
matrix whose columns are an eigenbasis for $\sum_{i=1}^{n}x_{i}x_{i}^{T}$.
Note that we always have
$\mathbb{E}_{D\sim\mathcal{P}^{n}}[\text{Rank}(V)]\leq n$.

Algorithm 3 DP-Projected Phased SGD for non-convex GLM

0: Private dataset: $D$ = $\\{({x}_{i},y_{i})\\}_{i=1}^{n}$, link function
$\sigma$ satisfying Assumption 1 and has (sub)gradient anywhere; privacy
parameters $0<\epsilon,\delta\leq 1$.

1: Sample a JL matrix $\Phi\in\mathbb{R}^{m\times d}$, and denote
$\tilde{D}=\\{(\Phi x_{1},y_{1}),\cdots,(\Phi x_{n},y_{n})\\}$.

2: Run Algorithm 2 on the projected dataset $\tilde{D}$, i.e., in Line 6 of
Algorithm 2, update  $w_{i}^{t+1}=w_{i}^{t}-\eta_{i}(\sigma(\langle
w_{i}^{t},\tilde{x}_{i}^{t}\rangle)-y_{i}^{t})\tilde{x}_{i}^{t},$ where
$(\tilde{x}_{i}^{t},y_{i}^{t})$ is the $t$-th sample of $\tilde{D}_{i}$. And
in Line 8, $\zeta_{i}\sim\mathcal{N}(0,\tau_{i}^{2}\mathbb{I}_{m})$ with
$\tau_{i}=\frac{16B\eta_{i}\sqrt{\log\frac{2}{\delta}}}{\epsilon}$. Denote the
output as $w_{k}$.

3: return $\hat{w}=\Phi^{T}w_{k}$

######  Theorem 1.

Under Assumption 1 and if $\sigma$ has (sub)gradient anywhere, for any
$0<\epsilon,\delta<1$, Algorithm 2 is $(\epsilon,\delta)$-DP. Moreover, when
$\eta=O(\min\\{\frac{\epsilon}{\sqrt{\theta\log\frac{1}{\delta}}},\frac{1}{\sqrt{n}}\\})\leq\frac{2}{G}$,
we have

$\mathbb{E}L_{\mathcal{P}}(w_{k})-L_{\mathcal{P}}(w^{*})\leq
O\big{(}\frac{1}{\sqrt{n}}+\frac{\sqrt{\theta\log\frac{1}{\delta}}}{n\epsilon}\big{)}.$

######  Theorem 2.

Under Assumption 1 and if $\sigma$ has (sub)gradient everywhere, let
$m=O(\log(n/\delta)(n\epsilon)^{\frac{2}{3}})$, then Algorithm 3 is
$(\epsilon,\delta)$-DP for any $0<\epsilon,\delta<\frac{1}{2G}$. Moreover,
when
$\eta=O(\min\\{\frac{\epsilon}{\sqrt{m\log\frac{1}{\delta}}},\frac{1}{\sqrt{n}}\\})\leq
1$, we have

$\mathbb{E}L_{\mathcal{P}}(\hat{w})-L_{\mathcal{P}}(w^{*})\leq\tilde{O}\big{(}\frac{\sqrt{\log\frac{1}{\delta}}}{({n\epsilon})^{\frac{2}{3}}}+\frac{1}{\sqrt{n}}\big{)},$

where the Big-$\tilde{O}$ notation omits the term of $\log(n/\delta)$.

######  Remark 1.

The output of Algorithm 1 achieves an error of
$\tilde{O}(n^{-\frac{1}{2}}+\min{\\{\sqrt{\theta}}{(n\epsilon)^{-1}},{({n\epsilon})^{-\frac{2}{3}}\\}})$.
This rate appears to be better than the lower bound for DP convex and
Lipschitz Generalized Linear loss (DP-GLL) [16], which is near-optimal at
$O(n^{-\frac{1}{2}}+\min{\\{\sqrt{\theta}}{(n\epsilon)^{-1}},({n\epsilon})^{-\frac{1}{2}}\\})$.
However, these results are not contradictory, as [16] considers a more general
class of loss functions. In fact, the above lower bound for DP-GLL only holds
for the case where $L_{\mathcal{P}}(w)=\mathbb{E}[|y-\langle w,x\rangle|]$,
while our problem mainly focuses on the squared loss
$L_{\mathcal{P}}(w)=\mathbb{E}[(y-\sigma(\langle w,x\rangle))^{2}]$.
Therefore, the lower bound does not apply to our problem.

Additionally, [16] considers the smooth and non-negative generalized linear
loss, which is not necessarily Lipschitz, and shows that the near-optimal rate
is
$\tilde{O}(n^{-\frac{1}{2}}+\min\\{(n\epsilon)^{-\frac{2}{3}},{\sqrt{d}(n\epsilon)^{-1}}\\})$.
Again, these results are not contradictory to ours.

####  IV-A2 More General Link Functions

One issue with the previous approach is that the link function $\sigma$ should
have a subgradient everywhere so that the surrogate function $\ell(\cdot;x,y)$
is smooth by Lemma 2. However, unlike the convex case, this assumption may not
always hold since some non-convex functions may have no subgradient at some
point. We will address this case and demonstrate that it is possible to
achieve the same bounds as in Theorem 1 and Theorem 2 (but with higher time
complexity).

Since the surrogate loss function in this case becomes non-smooth, the issue
lies in finding a method to make it smooth. To illustrate our approach, we
first recall the Moreau envelope smoothing technique that can be used to make
a non-smooth function smooth [25]. Let $\mathcal{M}$ be a (potentially
unbounded) closed interval, $y\in\mathbb{R}$ and $\beta>0$. Consider a
function $\ell:\mathcal{M}\mapsto\mathbb{R}$. The $\beta$-Moreau envelop of
$\ell$ is defined as

$\ell_{\beta}(x)=\min_{u\in\mathcal{M}}[\ell(u)+\frac{\beta}{2}|u-x|^{2}].$

Denote the proximal operator with respect to $\ell$ as

$\text{prox}_{\ell}^{\beta}(x)=\arg\min_{u\in\mathcal{M}}[\ell(u)+\frac{\beta}{2}|u-m|^{2}].$

If $\ell$ is a convex function, then its Moreau envelop has the following
properties:

######  Lemma 4.

Let $\ell:\mathcal{M}\mapsto\mathbb{R}$ be a convex function and
$G$-Lipschitz. Then the following hold: a) $\ell_{\beta}$ is convex,
$2G$-Lipschitz and $\beta$-smooth.
b)$\ell_{\beta}^{\prime}(x)=\beta[x-\text{prox}_{\ell}^{\beta}(x)]$. c) For
all $x\in\mathcal{M}$,
$\ell_{\beta}(x)\leq\ell(x)\leq\ell_{\beta}(x)+\frac{G^{2}}{2\beta}$.

Note that the previous Moreau envelope is for one-dimensional functions while
our surrogate loss $\ell$ is $d$ dimensional. Thus, for fixed $(x,y)$, we
denote $g^{y}(\langle x,w\rangle)=\ell(w;x,y)$ in (2) and we calculate the
Moreau envelop of $g^{y}(\cdot)$ instead, which is denoted as
$g^{y}_{\beta}(\cdot)$. By Lemma 4 and since $\ell$ is Lipschitz and convex,
we have $g^{y}_{\beta}$ is $2B$-Lipschitz and $\beta$-smooth. Thus, we have
the following fact.

######  Lemma 5.

For any fixed $(x,y)$, denote $\ell(w;x,y)=g^{y}(\langle x,w\rangle)$ and
$g_{\beta}^{y}(\cdot)$ as the Moreau envelop of $g^{y}(\cdot)$ with parameter
$\beta$ and $\mathcal{M}=\mathbb{R}$. Let
$f_{\beta}(w;x,y)=g_{\beta}^{y}(\langle w,x\rangle)$, then we have $f_{\beta}$
is $2B$-Lipschitz, $\beta$-smooth and
$|f_{\beta}(w;x,y)-\ell(w;x,y)|\leq\frac{2B^{2}}{\beta}$ for all
$w\in\mathbb{R}^{d}$.

Algorithm 4 $\mathcal{O}_{\beta,\gamma}:$ Gradient Oracle for
$f_{\beta}(w;x,y)$

0: Parameter vector $w\in\mathbb{R}^{d}$, data sample $(x,y)$ associate with
$g_{\beta}^{y}(\cdot).$

1: Let $m=\langle w,x\rangle$ and
$\mathcal{Q}=[m-\frac{4B}{\beta},m+\frac{4B}{\beta}]$.

2: Let $T=\frac{144B^{2}}{\gamma^{2}}$.

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

4: $y_{t+1}=w_{t}-\eta_{t}(\sigma(w_{t})-y+\beta(w_{t}-m))$ where
$\eta_{t}=\frac{2}{\beta(t+1)}$.

5: $w_{t+1}=y_{t+1}$ if $y_{t+1}\in\mathcal{Q}$, $w_{t+1}=m-\frac{4B}{\beta}$
if $y_{t+1}<m-\frac{4B}{\beta}$ and $w_{t+1}=m+\frac{4B}{\beta}$ otherwise.

6: end for

7: Denote $\bar{w}=\sum_{t=1}^{T}\frac{2t}{T(T+1)}x_{t}$.

8: Return $x\beta[m-\bar{w}]$.

One possible approach based on Lemma 5 is to obtain a smooth loss function
$f_{\beta}(w;x,y)$, and then use Algorithm 2 and Algorithm 3 to obtain private
estimators that achieve a small excess population risk for $f_{\beta}(w;x,y)$,
i.e.,
$\mathbb{E}[f_{\beta}(w;x,y)]-\min_{w\in\mathbb{R}^{d}}\mathbb{E}[f_{\beta}(w;x,y)]$.
However, there is a challenge: To use Algorithm 2, we need to calculate the
gradient of $f_{\beta}(w;x,y)$, which is inefficient as it is hard to compute
the proximal operator explicitly by Lemma 4. In the convex GLM case, [9] used
the bisection method to calculate $\nabla f_{\beta}(w;x,y)$. However, this
approach cannot be used here as it requires access to the function
$g^{y}(\cdot)$, which involves integration for our problem and is difficult to
compute accurately. In the following, we propose an algorithm that can
efficiently approximate $\nabla f_{\beta}(w;x,y)$.

The idea is that by our definition we have $\nabla f_{\beta}(w;x,y)=xg^{\prime
y}_{\beta}(\langle w,x\rangle)$, where $g^{\prime
y}_{\beta}(m)=\beta[m-\text{prox}_{g}^{\beta}(m)].$ Thus, it is sufficient to
approximate $\text{prox}_{\ell}^{\beta}(x)$ for given $x$. Recall that by the
definition
$\text{prox}_{g}^{\beta}(m)=\arg\min_{u\in\mathbb{R}}[g^{y}(u)+\frac{\beta}{2}|u-m|^{2}].$
We can show that
$\text{prox}_{g}^{\beta}(m)\in\mathcal{Q}=[m-\frac{4B}{\beta},m+\frac{4B}{\beta}]$
which indicates that

$\text{prox}_{g}^{\beta}(m)=\arg\min_{u\in\mathcal{Q}}[g^{y}(u)+\frac{\beta}{2}|u-m|^{2}]$

Thus, we can use the projected gradient descent (PGD) to solve the above
strongly convex objective function, see Algorithm 4 for details. By the
convergence rate of PGD we have the following lemma.

######  Lemma 6.

Given any $\beta,\gamma>0$. Then the gradient oracle
$\mathcal{O}_{\beta,\gamma}$ for $f_{\beta}(w;x,y)$ in Algorithm 4 satisfies
that $\|\nabla
f_{\beta}(w;x,y)-\mathcal{O}_{\beta,\gamma}(w;x,y)\|_{2}\leq\gamma$ for any
fixed $w,x,y$. Moreover, $\mathcal{O}_{\beta,\gamma}$ has running time
$O(d\frac{B^{2}}{\gamma^{2}})$.

Algorithm 5 Phased SGD for general non-convex GLM

0: Private dataset: $D$ = $\\{({x}_{i},y_{i})\\}_{i=1}^{n}$, link function
$\sigma$ satisfies Assumption 1 and is differentiable; privacy parameters
$0<\epsilon,\delta\leq 1$.

1: Set $k=\lceil\log_{2}(n)\rceil$, partite the whole dataset S into k subsets
$\\{D_{1},\cdots,D_{k}\\}$. Denote $n_{i}$ as the number of samples in
$D_{i}$, i.e., $|D_{i}|=n_{i}$ where $n_{i}=\lfloor 2^{-i}n\rfloor$. Take a
random initial vector $w_{0}\in\mathcal{W}$.

2: for $i=1,\cdots,k$ do

3: Let $\eta_{i}=\frac{\eta}{4^{i}}$ and $w_{i}^{1}=w_{i-1}$.

4: for $t=1,\cdots,n_{i}$ do

5: Recall the oracle in Algorithm 4 for
$f_{\beta}(w_{i}^{t};x_{i}^{t},y_{i}^{t})$ in Lemma 5 with error $\gamma$ and
denote it as $\tilde{\nabla}f_{\beta}(w_{i}^{t};x_{i}^{t},y_{i}^{t})$. Update
$w_{i}^{t+1}=w_{i}^{t}-\eta_{i}\tilde{\nabla}f_{\beta}(w_{i}^{t};x_{i}^{t},y_{i}^{t})$,
where $(x_{i}^{t},y_{i}^{t})$ is the $t$-th sample of $D_{i}$.

6: end for

7: Denote $w_{i}=\bar{w}_{i}+\zeta_{i}$, where
$\bar{w}_{i}=\frac{1}{n_{i}}\sum_{t=1}^{n_{i}}w_{i}^{t}$ and
$\zeta_{i}\sim\mathcal{N}(0,\tau_{i}^{2}\mathbb{I}_{d})$ with
$\tau_{i}=\frac{10BR\eta_{i}\sqrt{\log\frac{1}{\delta}}}{\epsilon}$.

8: end for

Algorithm 6 DP-Projected Phased SGD for general non-convex GLM

0: Private dataset: $D$ = $\\{({x}_{i},y_{i})\\}_{i=1}^{n}$, link function
$\sigma$ satisfies Assumption 1 and is differentiable; privacy parameters
$0<\epsilon,\delta\leq 1$.

1: Sample a fast JL matrix $\Phi\in\mathbb{R}^{m\times d}$, and denote
$\tilde{D}=\\{(\Phi x_{1},y_{1}),\cdots,(\Phi x_{n},y_{n})\\}$.

2: Run Algorithm 5 on the projected dataset $\tilde{D}$, where in Line 8,
$\zeta_{i}\sim\mathcal{N}(0,\tau_{i}^{2}\mathbb{I}_{m})$ with
$\tau_{i}=\frac{20B\eta_{i}\sqrt{\log\frac{2}{\delta}}}{\epsilon}$ and replace
$B$ by $2B$ in Algorithm 4. Denote the output as $w_{k}$.

3: return $\hat{w}=\Phi^{T}w_{k}$

Using the previous Lemma 6, one possible approach is to use the approximate
oracle in Algorithm 2, which is the main idea behind Algorithm 5. However,
there is another issue: if we use the same proof as in the previous case where
the link function has a subgradient everywhere, we can only obtain an upper
bound that depends on $\|w_{\beta}^{*}\|_{2}$, where
$w_{\beta}^{*}=\arg\min_{w\in\mathbb{R}^{d}}\mathbb{E}[f_{\beta}(w;x,y)]$.
This phenomenon has also been observed in GLMs with convex and non-smooth loss
functions [9]. Fortunately, we can conduct a finer analysis of the theoretical
guarantee of Algorithm 2 and show that we can obtain an upper bound that
depends on $W$ instead of $\|w_{\beta}^{*}\|_{2}$. Similar to the above
results, we have the following two results.

######  Theorem 3.

Under Assumption 1, for any $0<\epsilon,\delta\leq 1$, Algorithm 5 is
$(\epsilon,\delta)$-DP. Moreover, when
$\eta=O(\min\\{\frac{\epsilon}{\sqrt{\theta\log\frac{1}{\delta}}},\frac{1}{\sqrt{n}}\\})\leq\frac{2}{\beta}$,
$\gamma=O(\frac{1}{n\log n})$ and $\beta=O(\sqrt{n})$. Then we have

$\mathbb{E}L_{\mathcal{P}}(w_{k})-L_{\mathcal{P}}(w^{*})\leq
O\big{(}\frac{\sqrt{\theta\log\frac{1}{\delta}}}{n\epsilon}+\frac{1}{\sqrt{n}}\big{)}.$
(3)

######  Theorem 4.

Under Assumption 1 and let
$m=O(\log(\frac{n}{\delta})(n\epsilon)^{\frac{2}{3}})$, Algorithm 6 is
$(\epsilon,\delta)$-DP for any $0<\epsilon,\delta\leq 1$. Moreover, when
$\eta=O(\min\\{\frac{\epsilon}{\sqrt{m\log\frac{1}{\delta}}},\frac{1}{\sqrt{n}}\\})\leq\frac{1}{\beta}$,
$\gamma=O(n\log n)$ and $\beta=O(\sqrt{n})$ then we have

$\mathbb{E}L_{\mathcal{P}}(w_{k})-L_{\mathcal{P}}(w^{*})\leq\tilde{O}\big{(}\frac{1}{\sqrt{n}}+\frac{\sqrt{\log\frac{1}{\delta}}}{(n\epsilon)^{\frac{2}{3}}}\big{)}.$

####  IV-A3 ReLU Link Function

In the previous sections, we focused on the case where the link function in
model (1) satisfies Assumption 1. Although this assumption includes several
commonly used activation functions, it excludes the ReLU function where
$\sigma(x)=\max\\{0,x\\}$ due to the boundedness assumption of $\sigma$. Here,
we will consider the ReLU link function as it is a standard activation
function in neural networks.

Similar to Assumption 1, we still assume that $\|w^{*}\|_{2}\leq W$,
$\|x\|_{2}\leq 1$, and $y\in[-B,B]$. Note that since ReLU is Lipschitz, we can
still use Lemma 3, and it is sufficient to consider the problem of minimizing
$L^{\ell}_{\mathcal{P}}(w)$. However, the main difficulty now is that the
surrogate loss function $\ell(w;x,y)$ is no longer Lipschitz over the whole
space $\mathbb{R}^{d}$, as $\nabla\ell(w;x,y)=(\sigma(\langle w,x\rangle)-y)x$
is unbounded. Thus, our above methods cannot be used for the ReLU case, as all
of them need to assume that $\ell(w;x,y)$ is Lipschitz over the whole space.
This is due to the fact that $\bar{w}$ and $w_{i}^{t}$ in Algorithm 2 may not
lie in the constraint set $\mathcal{W}$.

To address the issue, we make the key observation that although the surrogate
loss function $\ell(w;x,y)$ is not Lipschitz over the whole space, it will be
Lipschitz over bounded sets. Specifically, for any $w$ with $\|w\|_{2}\leq W$,
we have $\|\nabla\ell(w;x,y)\|_{2}\leq W+B$. Based on this observation, we
propose to constrain $w$ over a bounded domain during updates. To achieve
this, we adopt the DP version of projected gradient descent (DP-PGD)
introduced in [18], which adds noise to the gradient and performs the
projection operation after updating the model, thereby enforcing $w$ to be
bounded during each iteration. Building on Algorithm 3, we preprocess the data
with a JL matrix and project all feature vectors onto an $m$-dimensional space
before applying DP-PGD. Finally, we lift the private estimator to the original
space after the DP-PGD algorithm. See Algorithm 7 for the full details.

Algorithm 7 DP-Projected GD for ReLU Regression

0: Private dataset: $D$ = $\\{({x}_{i},y_{i})\\}_{i=1}^{n}$, ReLU link
function $\sigma(w)=\max\\{0,w\\}$; privacy parameters $0<\epsilon,\delta\leq
1$.

1: Sample a JL matrix $\Phi\in\mathbb{R}^{m\times d}$, and denote
$\tilde{D}=\\{(\Phi x_{1},y_{1}),\cdots,(\Phi x_{n},y_{n})\\}$.

2: for $t=1,\cdots,T$ do

3: Update $\tilde{w}_{t+1}$ as
$\tilde{w}_{t+1}=\Pi_{\tilde{W}}[\tilde{w}_{t}-\eta(\frac{1}{n}\sum_{i=1}^{n}(\max\\{0,\langle\tilde{w}_{t},\Phi
x_{i}\rangle\\}-y_{i})\Phi x_{i}+\zeta_{t})],$ where
$\zeta\sim\mathcal{N}(0,\sigma^{2}\mathbb{I}_{m})$ with
$\sigma^{2}=\frac{32(4W+B)^{2}T\log\frac{2}{\delta}}{n^{2}\epsilon^{2}}$,
$\tilde{W}=\\{w\in\mathbb{R}^{m}|\|w\|_{2}\leq 2W\\}$ and $\Pi$ is the
projection operator.

4: end for

5: return $\bar{w}=\frac{\sum_{t=1}^{T}\Phi^{T}\tilde{w}_{T}}{T}$.

######  Theorem 5.

Algorithm 7 is $(\epsilon,\delta)$-DP for any $0<\epsilon,\delta\leq 1$ under
the previous assumptions and
$m=O(\log(\frac{n}{\delta})(n\epsilon)^{\frac{2}{3}})$. Moreover, take
$\eta=O(\frac{1}{\sqrt{T}})\leq\frac{1}{2}$ and
$T=O(\min\\{n,\frac{n^{2}\epsilon^{2}}{{m\log 1/\delta}}\\})$, in Algorithm 7
we have

$\mathbb{E}L_{\mathcal{P}}(\bar{w})-L_{\mathcal{P}}(w^{*})\leq\tilde{O}\big{(}\frac{1}{\sqrt{n}}+\frac{1\sqrt{\log
1/\delta}}{(n\epsilon)^{\frac{2}{3}}}\big{)}.$

By combining the error bound of DP-PGD in [18] with our analysis, we obtain a
bound of
$\tilde{O}(n^{-\frac{1}{2}}+\min\\{\sqrt{d}(n\epsilon)^{-1},(n\epsilon)^{-\frac{2}{3}}\\})$.
This bound is worse than those derived in the previous section because the
ReLU link function is not Lipschitz over $\mathbb{R}^{d}$. It is worth noting
that [16] also employs DP-PGD for convex generalized linear loss and obtains
the same bound. However, their analysis assumes the loss function to be non-
negative, whereas our loss function $\ell$ in (2) does not satisfy this
assumption.

###  IV-B Misspecified Model

In previous sections, we focused on model (1) where
$\mathbb{E}[y|x]=\sigma(\langle w^{*},x\rangle)$. However, such an assumption
is quite strong. Instead of the well-specified model, we always encounter the
misspecified one that does not directly impose any probability condition on
the label generating process. 444This setting is also known as the agnostic
setting in literature [26, 27]. Since the zero-mean random noise assumption
does not hold, we cannot apply Lemma 3, which transforms the original
population risk to the population risk of a convex surrogate loss. As a
result, none of the above methods can be used in this case. A natural question
is, what are the theoretical behaviors of GLMs in the misspecified model?

In fact, even in the non-private case, the problem of GLMs in the misspecified
model is quite challenging and is still not well understood in general. Thus,
rather than considering upper bounds for general loss functions, we aim to
illustrate the differences with the well-specified model by examining specific
losses. In particular, we will study ReLU regression in the misspecified
model.

Similar to the previous section, we will still examine the squared population
risk function
$L_{\mathcal{P}}(w)=\mathbb{E}_{(x,y)\sim\mathcal{P}}(\sigma(\langle
w,x\rangle)-y)^{2}$. It is noteworthy that [28] shows that in the absence of
distributional assumptions on the marginal distribution of $x$, i.e.,
$\mathcal{P}_{x}$, finding a parameter $w$ such that $L_{\mathcal{P}}(w)\leq
O(L_{\mathcal{P}}(w^{*}))+\alpha$ with some small error $\alpha$ is NP-hard
even in the non-private case. Therefore, compared to the well-specified model,
we need additional assumptions on $\mathcal{P}_{x}$, and we will concentrate
on the following isotropic log-concave distributions, which include uniform
distribution over $[0,1]^{d}$ and Bernoulli distribution.

######  Assumption 2.

We assume the marginal distribution of $x$ is isotropic log-concave, i.e.,
$\mathbb{E}_{\mathcal{P}_{x}}[x]=0$ and
$\mathbb{E}_{\mathcal{P}_{x}}[xx^{T}]=\mathbb{I}_{d}$, and its density
function $f$ satisfies $f(\lambda x+(1-\lambda)y)\geq
f(x)^{\lambda}f(y)^{1-\lambda}$ for every $x,y\in\text{Supp}(\mathcal{P}_{x})$
and $\lambda\in[0,1]$. Moreover, we assume $\|x\|_{2}\leq\sqrt{d}$ and
$y\in[-B,B]$.

To illustrate our idea, we first provide some notations. For any function
$f:\mathbb{R}^{d}\mapsto\mathbb{R}$ and distribution $\mathcal{P}$ for
$(x,y)$, we denote
$\chi_{\mathcal{P}}^{f}=\mathbb{E}_{x\sim\mathcal{P}_{\mathcal{X}}}[f(x)x]$,
$\chi_{\mathcal{P}}^{\sigma_{w}}=\mathbb{E}_{x\sim\mathcal{P}_{\mathcal{X}}}[\sigma(\langle
w,x\rangle)x]$ and $\chi_{\mathcal{P}}=\mathbb{E}_{\mathcal{P}}[yx]$. Our
method is motivated by the following observations. Firstly, we can show that
if $\mathcal{P}_{\mathcal{X}}$ is isotropic, then for any vector $w$ the
distance between $\chi_{\mathcal{P}}^{\sigma_{w}}$ and $\chi_{\mathcal{P}}$ is
bounded by $\sqrt{L_{\mathcal{P}}(w)}$, i.e.,
$\|\chi_{\mathcal{P}}^{\sigma_{w}}-\chi_{\mathcal{P}}\|_{2}\leq\sqrt{L_{\mathcal{P}}(w)}$.
Secondly, for ReLU regression, there exists a constant $\mu>0$ such that
$\sigma$ is $\mu$-strongly convex w.r.t $\mathcal{P}_{\mathcal{X}}$ if the
marginal distribution is isotopic and log-concave [26], i.e., for any $w,v$ we
have
$\langle\chi_{\mathcal{P}}^{\sigma_{w}}-\chi_{\mathcal{P}}^{\sigma_{v}},w-v\rangle\geq\mu\|w-v\|_{2}^{2}.$

Under Assumption 2 and the above strong convexity we can show that for any
vector $w$,

$\displaystyle\mathbb{E}_{\mathcal{P}}[(\sigma(\langle
w,x\rangle)-\sigma(\langle w^{*},x\rangle))^{2}]\leq
O(\|\chi_{\mathcal{P}}^{\sigma_{w}}-\chi_{\mathcal{P}}^{\sigma_{w^{*}}}\|^{2}_{2})$
$\displaystyle\leq
O(\|\chi_{\mathcal{P}}^{\sigma_{w}}-\chi_{\mathcal{P}}\|_{2}^{2}+\|\chi_{\mathcal{P}}^{\sigma_{w^{*}}}-\chi_{\mathcal{P}}\|_{2}^{2})$
$\displaystyle=O(\|\chi_{\mathcal{P}}^{\sigma_{w}}-\chi_{\mathcal{P}}\|_{2}^{2}+L_{\mathcal{P}}(w^{*})).$

Thirdly, by the triangle inequality we can easily find that
$L_{\mathcal{P}}(w)\leq
O(L_{\mathcal{P}}(w^{*})+\mathbb{E}_{\mathcal{P}}[(\sigma(\langle
w,x\rangle)-\sigma(\langle w^{*},x\rangle))^{2}])$. Thus, in total we have for
any vector $w$, $L_{\mathcal{P}}(w)\leq
O(L_{\mathcal{P}}(w^{*})+\|\chi^{\sigma_{w}}-\chi_{\mathcal{P}}\|_{2}^{2}).$
Moreover, we can easily get that $\chi^{\sigma_{w}}-\chi_{\mathcal{P}}$ is the
gradient of the population risk function of the surrogate loss function in
(2), i.e., $\nabla
L^{\ell}_{\mathcal{P}}(w)=\chi^{\sigma_{w}}-\chi_{\mathcal{P}}$. Thus, it is
sufficient for us to find a private estimator $w$ to make $\|\nabla
L^{\ell}_{\mathcal{P}}(w)\|_{2}$ be as small as possible.

Although some previous studies have addressed finding a first-order stationary
point privately for population risk functions, such as [2, 29, 30], their
methods cannot be applied to our function $L_{\mathcal{P}}^{\ell}$ because
they assume that the loss is Lipschitz over $\mathbb{R}^{d}$, which is not the
case for our loss. To overcome this challenge, we present a new algorithm,
Adaptive DP Batched Gradient Descent (Algorithm 8). The main idea is to
partition the dataset into several subsets and, in each iteration, use one
subset for private Gradient Descent. Although our loss function $\ell(w;x,y)$
is not uniformly Lipschitz over $\mathbb{R}^{d}$, we can still find that
$\|\nabla\ell(w_{t-1};x,y)\|_{2}\leq\sqrt{d}\|w_{t-1}\|_{2}+B$, whose upper
bound only depends on the current model $w_{t-1}$. Therefore, we can still use
the Gaussian mechanism with sensitivity $2(\|w_{t-1}\|_{2}+B)$ to the gradient
to ensure $(\epsilon,\delta)$-DP. Our algorithm is fundamentally different
from previous DP-GD based methods [18, 13], as the Gaussian noise added also
depends on the current model. In general, our method can provide a tighter
bound, as $\|w_{t-1}\|_{2}$ becomes smaller as $t$ increases, which implies
that we add smaller noise to the gradient.

Algorithm 8 Adaptive DP Batched Gradient Descent

0: Private dataset: $D$ = $\\{({x}_{i},y_{i})\\}_{i=1}^{n}$, ReLU link
function $\sigma$; privacy parameters $0<\epsilon,\delta\leq 1$.

1: Partite the data $D$ into $T$ subsets $\\{D_{1},\cdots,D_{T}\\}$ where
$m=|D_{i}|=\frac{n}{T}$.

2: Denote the loss function $\ell$ as $\ell(w;x,y)=\int_{0}^{\langle
w,x\rangle}(\sigma(z)-y)dz$. Initialize $w_{0}=0$.

3: for $i=1,\cdots,T$ do

4: Let $w_{i}=w_{i-1}-\eta(\nabla
L^{\ell}(w_{i-1};D_{i})+\zeta_{i-1})=w_{i-1}-\eta(\frac{1}{m}\sum_{x\in
D_{i}}(\max\\{0,\langle w_{i-1},x_{i}\rangle\\}-y_{i})x_{i}+\zeta_{i-1})$,
where $\zeta_{i-1}\sim\mathcal{N}(0,\sigma_{i-1}^{2}I_{d})$ with
$\sigma_{i-1}=\frac{8(\sqrt{d}\|w_{t-1}\|_{2}+B)^{2}\log(1.25/\delta)}{m^{2}\epsilon^{2}}$.

5: end for

6: return $w_{T}$

Combining with all the above ideas, we can show the following result for
Algorithm 8.

######  Theorem 6.

Consider ReLU regression and assume Assumption 2 holds. For any
$0<\epsilon,\delta<1$, Algorithm 8 is $(\epsilon,\delta)$-DP. Moreover denote
$w_{\ell}^{*}=\arg\min_{w\in\mathbb{R}^{d}}L^{\ell}_{\mathcal{P}}(w)$ with
$\ell$ in (2). For any error $\alpha\in(0,\|w_{\ell}^{*}\|_{2})$, if $n$ is
sufficiently large such that
$n\geq\tilde{\Omega}(\max\\{\frac{d\|w^{*}_{\ell}\|_{2}\sqrt{\log\frac{1}{\delta}\log\frac{1}{\zeta}}}{\epsilon\alpha},\frac{\|w_{\ell}^{*}\|_{2}^{2}d\log^{4}\frac{1}{\zeta}}{\alpha^{2}}\\})$,
setting $T=O(\log(\|w_{\ell}^{*}\|_{2}))$ and $\eta\leq\frac{1}{16}$ in
Algorithm 8 we have the following with probability at least $1-\zeta$ with
$\zeta\geq\exp(-O(\sqrt{d}))$

$L_{\mathcal{P}}(w_{T})\leq 2(1+2\mu)L_{\mathcal{P}}(w^{*})+\alpha.$

In Theorem 6, we demonstrate that for ReLU regression under Assumption 2, the
sample complexity required to achieve $L_{\mathcal{P}}(w)-c\cdot
L_{\mathcal{P}}(w^{*})\leq\alpha$ with some $c>0$ is
$\tilde{O}(\max\\{\frac{d}{\epsilon\alpha},\frac{d}{\alpha^{2}}\\})$. There
are several differences in comparison to the results in previous sections.
Firstly, here we can only obtain a bound for
$L_{\mathcal{P}}(w)-O(L_{\mathcal{P}}(w^{*}))$ instead of the original excess
population risk. In fact, this big-$O$ term is necessary, as [27] provides
hardness results for $L_{\mathcal{P}}(w)-L_{\mathcal{P}}(w^{*})\leq\alpha$
with $\alpha\in(0,1)$, even if the underlying distribution is the standard
Gaussian. The second difference is that unlike the previous results, where
sample complexities are independent of $d$, the sample complexity here depends
linearly on $d$. This dependency results from two factors: the magnitude of
noise added depends on $\sqrt{d}$, and the estimation error of $\|\nabla
L^{\ell}(w;D)\|_{2}$ introduces an additional $d$ factor. We cannot use the
same strategy as in Algorithm 2 since projecting the data will alter the
sample distribution and destroy the strongly convex property. Therefore, even
in the non-private case, there is still a factor of $d$ in the sample
complexity.

##  V Extension to Two-layer Neural Networks

In this section, we present an extension of our previous methods to one-hidden
layer fully connected neural networks. Our focus is mainly on the cases where
the activation functions are either sigmoid or ReLU. We restrict ourselves to
the well-specified model. Before presenting the details, we start by extending
our model (1) to a bounded noise setting in a high dimensional feature space.
We assume $\mathcal{K}$ is a kernel function in a Reproducing Kernel Hilbert
Space (RKHS) $\mathcal{H}\subseteq\mathbb{R}^{k}$ with some $k$, and
$\psi(\cdot)\in\mathbb{R}^{k}$ is the corresponding feature map satisfying
$|\psi(x)|_{2}\leq 1$ for all $x\in\mathcal{P}_{\mathcal{X}}$. We consider the
following model:

$y=\sigma(\langle w^{*},\psi(x)\rangle+\phi(x))+\zeta,$ (4)

where $w^{*}\in\mathcal{H}$ is the underlying parameter with
$\|w^{*}\|_{2}\leq W$, $\phi(x)$ is a noise function which satisfies
$|\phi(x)|\leq M$, $\zeta$ is a random noise whose mean is 0 and $\sigma$ is a
(non-convex) link function. Note that in the case of $\phi(x)=0$ and $\psi$ is
the identity function, (4) is equivalent to model (1). Similar to the previous
section, here we consider the squared loss where
$L_{\mathcal{P}}(h)=\mathbb{E}_{(x,y)\sim\mathcal{P}}[(h(x)-y)^{2}]$ for any
function $h$ 555Note that since we need to estimate both $w^{*}$ and $\phi$,
here we use a function instead of vector in the previous section. and we want
to minimize the excess population risk:

$L_{\mathcal{P}}(h)-\min_{h}L_{\mathcal{P}}(h)=\mathbb{E}_{(x,y)\sim\mathcal{P}}[(h(x)-\sigma(\langle
w^{*},\psi(x)\rangle+\phi(x)))^{2}].$

We consider the model (4) because, as we will show later, for some one-hidden
layer neural networks, we can always find $w^{*}$, $\psi(\cdot)$, and $M$ to
approximate the hidden layer, and the link function $\sigma$ can be viewed as
the activation function of the output layer. We first present the following
assumption for this section.

######  Assumption 3.

We assume that there exist constants $W,G=O(1)$ such that $\|w^{*}\|_{2}\leq
W$, $y\in[0,1]$666Note that here we assume $y$ and $\sigma$ is in $[0,1]$ is
that there are commonly used in practice. We can extend to any bounded
interval. and the link function $\sigma:\mathbb{R}\mapsto[0,1]$ is
$G$-Lipschitz and non-monotone decreasing, and has sub-gradient everywhere.
Moreover, in model (4) we assume $\|\psi(x)\|_{2}\leq 1$ and
$\|\phi(x)\|_{2}\leq M$ for every $x\sim\mathcal{P}_{x}$.

To minimize the population risk, similar to the previous section, we consider
the surrogate loss

$\ell(w;x,y)=\int_{0}^{\langle w,\psi(x)\rangle}(\sigma(z)-y)dz.$ (5)

By Lemma 2 we can see the $\ell$ is $1$-Lipschitz and $G$-smooth. Similar to
Lemma 3, the following lemma shows the relation between the original
population risk and the population risk for the surrogate loss.

######  Lemma 7.

For any $w\in\mathcal{H}$ we have

$L_{\mathcal{P}}(w)-\min_{h}L_{\mathcal{P}}(h)\leq
4G(L^{\ell}_{\mathcal{P}}(w)-L^{\ell}_{\mathcal{P}}(w^{*}))+2G^{2}M^{2}+4GM.$

By Lemma 7, we can see that it is sufficient to find a private model that
minimizes the difference between $L^{\ell}_{\mathcal{P}}(w)$ and
$L^{\ell}_{\mathcal{P}}(w^{*})$. To achieve this goal, we can use a similar
algorithm as presented in Algorithm 1, with the main difference being the use
of $\tilde{D}={(\psi(x_{i}),y_{i})}_{i=1}^{n}$ instead of the raw data. For
more details, please refer to Algorithm 9. Similar to Theorem 1 and 2 we have
the following result.

Algorithm 9 DP Two-layer Neural Networks

0: Private dataset: $D$ = $\\{({x}_{i},y_{i})\\}_{i=1}^{n}$, link function
$\sigma$ satisfies Assumption 3; privacy parameters $0<\epsilon,\delta\leq 1$,
$\theta$ is an upper bound of the expected rank
$\sum_{i=1}^{n}\psi(x_{i})\psi(x_{i})^{T}$.

1: Denote the data $\tilde{D}=\\{(\psi(x_{i}),y_{i})\\}_{i=1}^{n}$. If
$\epsilon>\frac{\theta}{n}$, run Algorithm 2 with $\tilde{D}$. Otherwise run
Algorithm 3 with $\tilde{D}$.

######  Theorem 7.

Under Assumption 3, for any $0<\epsilon,\delta\leq 1$, Algorithm 9 is
$(\epsilon,\delta)$-DP. Moreover we have its output $w$ satisfies

$\displaystyle\mathbb{E}L_{\mathcal{P}}(w)-\min_{h}L_{\mathcal{P}}(h)\leq\tilde{O}(\min\\{\frac{\sqrt{\theta\log\frac{1}{\delta}}}{n\epsilon},\frac{\sqrt{\log\frac{1}{\delta}}}{\sqrt{n\epsilon}}\\}$
$\displaystyle+\frac{1}{\sqrt{n}}+M^{2}+M),$

where $\theta$ is an upper bound on the expected rank of
$\sum_{i=1}^{n}\psi(x_{i})\psi(x_{i})^{T}$ if
$\eta=O(\min\\{\frac{\epsilon}{\sqrt{\theta\log\frac{1}{\delta}}},\frac{1}{\sqrt{n}}\\})\leq\frac{1}{G}$
in Algorithm 2 and
$\eta=O(\min\\{\frac{\epsilon}{\sqrt{m\log\frac{1}{\delta}}},\frac{1}{\sqrt{n}}\\})\leq\frac{1}{G}$
in Algorithm 3 with $m=O(\log(n/\delta)n\epsilon)$.

######  Remark 2.

It is worth noting that the rate of sample size $n$ in Theorem 7 is lower than
that in Theorem 1 ($n^{-\frac{1}{2}}$ v.s. $n^{-\frac{2}{3}}$). This is due to
that in the noiseless case ($M=0$), $w^{*}$ is also a global minimizer of
$L^{\ell}_{\mathcal{P}}(w)$, which is not the case in model (4). Therefore, we
cannot rely on this property and the smooth Lipschitz condition to demonstrate
that the error caused by projecting onto a lower space is
$\tilde{O}(\frac{1}{m})$. Instead, we can only use the Lipschitz condition to
obtain an error of $\tilde{O}(\frac{1}{\sqrt{m}})$.

One question is as we know
$L^{\ell}_{\mathcal{P}}(w)-L^{\ell}_{\mathcal{P}}(w^{*})\leq
L^{\ell}_{\mathcal{P}}(w)-\min_{w\in\mathbb{R}^{k}}L^{\ell}_{\mathcal{P}}(w)$,
why we do not consider to bound the latter term? Actually, considering the
latter term will make us get an error that depends on $\|w^{*}_{\ell}\|_{2}$
with $w^{*}_{\ell}=\arg\min_{w\in\mathbb{R}^{k}}L^{\ell}_{\mathcal{P}}(w)$,
whose upper bound is unknown. Thus, we need to analyze
$L^{\ell}_{\mathcal{P}}(w)-L^{\ell}_{\mathcal{P}}(w^{*})$ directly.
Fortunately, by giving a finer analysis for the Phased SGD we can get such an
upper bound.

Assuming that the term $\phi(x)$ is a noise function that is bounded by a
sufficiently small constant $M$, Theorem 7 implies that if a function $f$ can
be approximated by an element of an appropriate RKHS, then Algorithm 7 can be
used to obtain a private estimator. This is formalized in the following
corollary.

######  Definition 7 ($(M,W)$-Uniform Approximation).

Let $f$ be a function mapping from domain $\mathcal{X}$ to $\mathbb{R}$ and
$\mathcal{P}_{\mathcal{X}}$ be a distribution over $\mathcal{X}$. Let
$\mathcal{K}$ be a kernel function with corresponding RKHS
$\mathcal{H}\subseteq\mathbb{R}^{k}$ and feature vector $\psi$. We say $f$ is
$(M,B)$-uniformly approximated by $\mathcal{K}$ over
$\mathcal{P}_{\mathcal{X}}$ if there exists some $w^{*}\in\mathcal{H}$ with
$\|w^{*}\|_{2}\leq W$ such that for all $x\sim\mathcal{P}_{\mathcal{X}}$ we
have $|f(x)-\langle w^{*},\psi(x)\rangle|\leq M.$

######  Corollary 1.

Consider a distribution $\mathcal{P}$ such that $\mathbb{E}[y|x]=\sigma(f(x))$
where $\sigma$ is a known $G$-Lipshcitz and increasing function, and $f$ is
$(M,W)$-approxiamted by some kernel function $\mathcal{K}$ and feature map
$\psi$ such that $\mathcal{K}(x,x^{\prime})\leq 1$. The function
$h(x)=\sigma(\langle w,\psi(x)\rangle)$ for the output $w$ in Algorithm 9
achieves the same error bound as in Theorem 7.

Next, we will apply Corollary 1 to some neural network models by using some
recent results on approximation theory for neural networks [20]. We consider
the following one-hidden layer neural networks with $k$-hidden units and one
output node:

$y=\mathcal{N}_{2}(x)+\zeta,\text{ where
}\mathcal{N}_{2}:x\mapsto\sigma_{2}(\sum_{t=1}^{k}b_{t}\sigma_{1}(\langle
a_{t},x\rangle)).$ (6)

Here we assume $\|x\|_{2}=1$, $\|a_{t}\|_{2}=1$ for each $t$ and $\|b\|_{2}=1$
where $b=(b_{1},\cdots,b_{k})$, and $\sigma_{1},\sigma_{2}$ are two activation
functions. Here $\sigma_{2}$ satisfies the properties in Assumption 3 and
$\sigma_{1}$ could be either Sigmod and ReLU activation functions. In the
following, we provide sample complexities to achieve an error of $\alpha$ for
these two cases.

######  Theorem 8.

Consider samples $\\{(x_{i},y_{i})\\}_{i=1}^{n}$ are i.i.d. drawn from
distribution $\mathcal{P}$ such that $\mathbb{E}[y|x]=\mathcal{N}_{2}(x)$ with
$\sigma_{2}:\mathbb{R}\mapsto[0,1]$ is a known $G$-Lipshcitz and increasing
function and $\sigma_{1}$ is the sigmoid function. Then when
$n=O((\frac{kG}{\alpha})^{2C}\frac{\log
1/\delta}{\epsilon}+(\frac{Gk}{\alpha})^{C}\frac{\sqrt{\theta\log
1/\delta}}{\epsilon})$ with some constant $C>0$ we have

$\mathbb{E}L_{\mathcal{P}}(h)-\min_{h}L_{\mathcal{P}}(h)=\mathbb{E}L_{\mathcal{P}}(h)-L_{\mathcal{P}}(\mathcal{N}_{2})\leq\alpha.$

Here $h(x)=\sigma(\langle w,\psi(x)\rangle)$ for some feature map $\psi(x)\in
R^{D_{m}}$ with $D_{m}=\tilde{O}(d^{O(\log\frac{k}{\alpha})})$ and $w$ is the
output of Algorithm 9 with the feature map $\psi(\cdot)$.

######  Theorem 9.

Consider samples $\\{(x_{i},y_{i})\\}_{i=1}^{n}$ are i.i.d. drawn from
distribution $\mathcal{P}$ such that $\mathbb{E}[y|x]=\mathcal{N}_{2}(x)$ with
$\sigma_{2}:\mathbb{R}\mapsto[0,1]$ is a known $G$-Lipshcitz and increasing
function and $\sigma_{1}$ is the ReLU function. Then when
$n=O(4^{C(\frac{Gk}{\alpha})}\frac{\log
1/\delta}{\epsilon}+2^{C(\frac{Gk}{\alpha})}\frac{\sqrt{\theta\log
1/\delta}}{\epsilon})$ with some constant $C>0$ we have

$\mathbb{E}L_{\mathcal{P}}(h)-\min_{h}L_{\mathcal{P}}(h)=\mathbb{E}L_{\mathcal{P}}(h)-L_{\mathcal{P}}(\mathcal{N}_{2})\leq\alpha.$

Here $h(x)=\sigma(\langle w,\psi(x)\rangle)$ for some feature map $\psi(x)\in
R^{D_{m}}$ with $D_{m}={O}(\frac{\sqrt{k}}{\alpha}d^{O(\frac{k}{\alpha})})$
and $w$ is the output $w$ of Algorithm 9 with the feature map $\psi(\cdot)$.

######  Remark 3.

The results for one-hidden layer neural networks are quite intricate. Firstly,
the sample complexity now depends on $\text{poly}(k)$ in the sigmoid case and
depends on the exponential of $k$ and $\frac{1}{\alpha}$ in the ReLU case,
which is due to the approximation errors using feature maps. However, it is
noteworthy that, similar to the GLM case, the sample complexities are still
independent of the data dimension. The second difference is that Algorithm 9
is inefficient in the ReLU case, as the dimension of the feature map will be
exponential. Hence, developing efficient algorithms for privately learning
one-hidden layer networks will remain an open problem.

##  VI Private Multi-layer Neural Networks via DP-SGD

In previous sections, we examined GLMs and one-hidden layer neural networks,
but there are three critical issues with those results: (1) While we proposed
several new algorithms, DP-SGD based methods [7] are preferred in practice for
private neural network training. Can we obtain utility guarantees for vanilla
DP-SGD in [7]? Alternatively, how do different factors such as the number of
nodes, clipping threshold, and iteration number impact the utility
theoretically? (2) Most of the aforementioned results rely on the well-
specified model assumption and the squared loss in population risk, which can
be too stringent in practice. Can we provide utility analysis without these
assumptions? (3) Previous methods for one-hidden layer networks heavily depend
on their specific forms and cannot be extended to general multi-layer
structures. To address these issues, we study the utility of the projected
version of DP-SGD for general multi-layer neural networks in this section.

We consider fully connected neural networks with depth (number of layers) $L$,
width $m$ in each layer, and input data dimension $d$. Such a network could be
represented by its weight matrices at each layer: For $L\geq 2$, let
$\mathbf{W}_{1}\in\mathbb{R}^{m\times d}$ be the weight matrix between the
input layer and the first hidden layer, $\mathbf{W}_{l}\in\mathbb{R}^{m\times
m}$ with $l=2,\cdots,L-1$ as the weight matrices between hidden layers and
$\mathbf{W}_{L}\in\mathbb{R}^{1\times m}$ be the weight matrix between the
last hidden layer to the output layer.777For simplicity, we assume the widths
of each hidden layer are the same. Our result can be extended to the setting
where the widths of each layer are not equal in the same order. For simplicity
we denote $\mathbf{W}=(\mathbf{W}_{1},...,\mathbf{W}_{L})$. Then the neural
network on sample $x$ can be written as

$f(\mathbf{W},x)=(\sqrt{m})\cdot\mathbf{W}_{L}\sigma(\mathbf{W}_{L-1}\sigma(\mathbf{W}_{L-2}...\sigma(\mathbf{W}_{1}x)...)),$

where $\sigma(\cdot)$ is the entry-wise activation function. In this paper,
for convenience, we only consider the ReLU activation function
$\sigma(s)=\max\\{0,s\\}$, which is arguably one of the most difficult
activation functions to analyze due to its non-smoothness. The general
analysis framework is able to extend to other activation functions like tanh,
and sigmoid, as long as the function is smooth almost everywhere.

Besides the neural network, we also have a non-negative, differentiable, and
$S$-Lipschitz convex loss function $\ell(f(\mathbf{W},x),y)$ (denoted as
$\ell(\mathbf{W};x,y)$) which measures the difference between the prediction
of network and the ground truth. In total, now our excess population risk is
defined as
$\mathbb{E}_{(\mathbf{x},y)\sim\mathcal{D}}\ell(\mathbf{W};x,y)-\min_{\mathbf{W}\in\mathcal{W}}\mathbb{E}_{(\mathbf{x},y)\sim\mathcal{D}}\ell(\mathbf{W};x,y).$
We consider the following assumption throughout the whole part, which is
commonly used in the previous work on analyzing theoretical behaviors of
multi-layer neural networks such as [31, 32].

######  Assumption 4.

Assume $||x||_{2}\leq 1$ for all $x\in\mathcal{P}_{x}$ and the parameter space
of the network is $\mathcal{W}=\mathcal{B}(\mathbf{0},R)$, i.e., for all
$\mathbf{W}\in\mathcal{W}:||\mathbf{W}_{l}||_{F}\leq R$, for all $l\in[L].$

We aim to provide an upper bound on the excess population risk for DP-SGD in
Algorithm 10 instead of developing new algorithms. Note that there are slight
differences between Algorithm 10 and the one in [7]. First, in the first step
of Algorithm 10, the initial weight matrices are i.i.d. sampled from a
specific Gaussian distribution, which is crucial for our utility analysis.
Secondly, in step 6, we need to perform the projection after using the noisy
and clipped sub-sampled gradients to update our weight matrices. In fact, the
projection step is also necessary for our analysis. Finally, instead of using
the weight matrices in the last iteration, our output is the average of all
the intermediate weight matrices. We use the average for convenience of
analysis, but we can still obtain a similar utility for the last iteration
weight matrices by using the same strategy as in [33].

The main idea of our utility analysis is based on recent developments in the
Neural Tangent Kernel (NTK) technique [34], which explains the generalization
behaviors and provides theoretical guarantees for SGD in overparameterized
neural networks. To introduce the idea of NTK, we first recall the definition
of a Neural Tangent Random Feature function.

######  Definition 8 (Neural Tangent Random Feature).

Let $\mathbf{W}^{(0)}$ be generated via the initialization process in
Algorithm 10. Then the Neural Tangent Random Feature (NTRF) function is
defined as

$f_{ntk}(\mathbf{W},\boldsymbol{x})=f(\mathbf{W}^{(0)},\boldsymbol{x})+\left\langle\partial_{\mathbf{W}}f(\mathbf{W}^{(0)},\boldsymbol{x}),\mathbf{W}\right\rangle.$

Consider the parameter space $\mathcal{B}(\mathbf{W}^{(0)},\omega)$, the
corresponding NTRF function class is denoted as

$\displaystyle\mathcal{F}(\mathbf{W^{(0)}},\omega)=\\{f_{ntk}(\mathbf{W},x):\mathbf{W}\in\mathcal{B}(\mathbf{W}^{(0)},\omega),||x||_{2}\leq
1\\}.$

Note that an NTRF function is linear. The idea of using NTK to analyze the
generalization performance of overparameterized neural networks is based on
the observation that the dynamic of wide neural networks under SGD is similar
to that of the corresponding local linearization. In detail, let $W^{(t)}$
denotes the updated parameter vector after the $t$-th iteration, and
$L_{f}=\sum_{(x,y)\in{D}}\ell(f(W^{(t)};x),y)$ denotes the sum of loss with
respect to $f$. Via continuous time gradient descent we have $W^{(t+\Delta
t)}-W^{(t)}=-\eta\Delta t\frac{\partial L(t)}{\partial W}$. Since
$\frac{\partial f(W^{(t)},D_{\mathcal{X}})}{\partial
t}=\nabla_{W}f(W^{(t)},D_{\mathcal{X}})\frac{\partial W^{(t)}}{\partial t}$,
and by chain role $\frac{\partial W^{(t)}}{\partial
t}=-\eta\nabla_{W}f(W^{(t)},D_{\mathcal{X}})^{T}\nabla_{f(W^{(t)},D_{\mathcal{X}})}L$,
where

$f(W^{(t)},D_{\mathcal{X}})=vec([f(W^{(t)},x_{i})]_{x\in[n]})$

is the vector of $f(W^{(t)},x_{i})$. The evolution of the neural network $f$
and $f_{ntk}$ can be written by

$\displaystyle\underbrace{\frac{\partial f(W^{(t)},D_{\mathcal{X}})}{\partial
t}=-\eta\Theta_{t}(D_{\mathcal{X}},D_{\mathcal{X}})\nabla_{f}L_{f(W^{(t)},D_{\mathcal{X}})}}_{Gradient\
of\ Neural\ Network},$ $\displaystyle\underbrace{\frac{\partial
f_{ntk}(W^{(t)},D_{\mathcal{X}})}{\partial
t}=-\eta\Theta_{0}(D_{\mathcal{X}},D_{\mathcal{X}})\nabla_{f}L_{f_{ntk}(W^{(t)},D_{\mathcal{X}})}}_{Gradient\
of\ Local\ Linearization},$

where
$\Theta_{0}(\mathcal{X},\mathcal{X})=\mathbb{E}_{W^{(0)}}\nabla_{W}f(W^{(0)},D_{\mathcal{X}})\nabla_{W}f(W^{(0)},D_{\mathcal{X}})^{T}$
is the NTK matrix and
${\Theta}_{t}(D_{\mathcal{X}},D_{\mathcal{X}})=\nabla_{W}f(W^{(t)},D_{\mathcal{X}})\nabla_{W}f(W^{(t)},D_{\mathcal{X}})^{T}$
is the empirical NTK. Recently, [35] gives the first non-asymptotic
convergence rate for the NTK matrix $\Theta_{t}$ and shows
$||{\Theta}_{t}-\Theta_{0}||_{F}\to 0$ when $m$ is sufficiently large, i.e.,
the empirical NTK is proved to converge to a deterministic kernel under the
infinite width setting [34] with high probability. Based on this, when $m$ is
sufficiently large, from the above two equations we can see a basic idea to
approximate the gradients of neural networks is using their linearizations,
which are convex. Moreover, we can also control the difference between
$f({W}^{(t)},x)$ and $f_{ntk}({W}^{(t)},x)$ by the term
$||\Theta_{t}-\Theta_{0}||_{F}$. Thus, via NTK, analyzing the utility of SGD
for neural networks will become similar to analyzing the utility of SGD for
convex loss. Motivated by the above intuition, we finally get the following
theorem for the utility of Algorithm 10.

######  Theorem 10.

There exist constants $c_{1},c_{2}$ so that given the number of steps T and
$q=M/n$, for any $\epsilon<c_{1}q^{2}T$, Algorithm 10 is
$(\epsilon,\delta)$-DP for any $0<\delta<1$ if we have $\sigma_{t}\geq
c_{2}\frac{qC\sqrt{T\log(1/\delta)}}{|B_{t}|\epsilon}$. Moreover, for any
$\xi\in(0,e^{-1}],0<\gamma_{1},\gamma<1$, and $R>0$, there exists

$m^{*}(\xi,R,L,S,T,C)=\widetilde{\Omega}(\textrm{Poly}(S,L,R)T^{7}C^{-8}[\log(1/\xi)]^{3})$

such that if $C\leq O(\min\\{SL\sqrt{m},R\\})$, $m\geq m^{*}$ ,
$M\geq\Omega(\log\frac{T}{\gamma_{1}})$ and
$n\geq\tilde{\Omega}(\frac{C(\sqrt{L}m+\sqrt{md})\sqrt{T\log(1/\gamma)\log(1/\delta)}}{R\epsilon})$,
then with probability at least $1-\xi-\gamma-\gamma_{1}$ over the randomness
of the algorithm, the excess population risk
$L_{\mathcal{D}}(\hat{\mathbf{W}})-\min_{\mathbf{W}\in\mathcal{W}}L_{\mathcal{D}}(\mathbf{W})$
of the output in Algorithm 10 with step size
$\eta=\Theta(\frac{\sqrt{L}R}{C\sqrt{mT}})$ is upper bounded by

$\displaystyle\underbrace{\sqrt{\frac{\log(\frac{1}{\xi})}{T}}}_{Convergence\
rate}+\underbrace{\inf_{f\in\mathcal{F}(\mathbf{W}^{(0)},\frac{R}{\sqrt{m}})}\\{\frac{1}{T}\sum_{i=1}^{T}\ell(f(\mathbf{x}_{i}),y_{i})\\}}_{Approximation\
error}$
$\displaystyle+SL^{\frac{3}{2}}R\cdot\widetilde{O}(\underbrace{\frac{\max(L,\frac{d}{m})\log(\frac{1}{\gamma})\log(\frac{1}{\delta})m^{2}\sqrt{T}}{n^{2}\epsilon^{2}}}_{Privacy\
error}).$ (7)

######  Remark 4.

Compared to the results in previous sections, Theorem 10 provides a more
complex upper bound. This upper bound is composed of three terms: The first
term represents the sum of convergence rate and sampling error. The second
term is the minimum value of
$\frac{1}{T}\sum_{i=1}^{T}\ell(f(\mathbf{x}_{i}),y_{i})$ among all reference
functions in the NTRF function class. This term arises due to the
approximation error caused by using NTRF functions to approximate neural
networks. The last term corresponds to the error resulting from the addition
of extra noise to gradients to ensure differential privacy. It is notable that
when $\epsilon=\infty$, i.e., when in the non-private case, our result will be
$O({\inf_{f\in\mathcal{F}(\mathbf{W}^{(0)},\frac{R}{\sqrt{m}})}\\{\frac{1}{T}\sum_{i=1}^{T}\ell(f(\mathbf{x}_{i}),y_{i})\\}}+\frac{1}{\sqrt{T}})$.
Moreover, when $m,T\to\infty$, the error will tend to zero.

######  Remark 5.

Compared to the convex case, the impact of parameters $T$ and $m$ on the bound
in Theorem 10 is more complicated. For network width $m$, if it is large
enough, then $f_{ntk}(\mathbf{W}^{(0)},x)$ will converge to a well-trained
neural network, as pointed out by [36, 34, 37]. In the interpolation regime,
the training error can be zero, which means the approximation error tends to
zero as $m$ becomes sufficiently large. However, $m$ cannot be arbitrarily
large because the privacy error depends on $\text{poly}(m)$. As for parameter
$T$, it should not be too large or too small. When $T$ is large, the privacy
error increases, and when $T$ is small, the convergence error becomes large.
Furthermore, the upper bound is independent of the clipping threshold $C$
because we assume that $C\leq R$ and the step size $\eta$ depends on
$\frac{1}{C}$ (which implies that $C$ cannot be too small). Thus, when $C$ is
in some range, it will not have a significant impact on performance. However,
the effect of $C$ when it is large or small remains an open problem.

######  Remark 6.

The main weakness of Theorem 10 is the assumption of $n\geq O(m)$, which
contradicts the overparameterized setting in NTK theory, where the number of
nodes could be far greater than the sample size $n$. To address this weakness,
recent studies have proposed additional assumptions on the gradient or loss of
neural networks, such as low-rank gradients [8] and restricted Lipschitz
continuity [38]. However, all of these works only analyze the excess
population risk for convex loss functions. Since we can show, via NTK theory,
that the loss function is locally convex and has a bounded gradient with large
enough $m$ with high probability, we believe that it is possible to remove the
dependency on the number of weights in the utility by combining our
theoretical analysis with those assumptions. This will be left as future work.

###  VI-A Experimental Investigation

Algorithm 10 DP-SGD for Multi-layer Neural Networks

0: : Private dataset: $D$, convex set $\mathcal{W}=\mathcal{B}(\mathbf{0},R)$.
Parameters: learning rate $\eta$, mini-batch size $M$, iteration $T$, privacy
parameter $\epsilon\leq 1$, $\delta\leq 1/n^{2}$, clipping constant $C$.

1: Generate each entry of $\mathbf{W}_{l}^{(0)}$ independently from
$N(0,2/m)$, $l\in[L-1]$. Generate each entry of $\mathbf{W}_{L}^{(0)}$
independently from $N(0,1/m)$.

2: for $t=0$ to $T-1$ do

3: For each data $(x_{i},y_{i})\in D$ sample it probability $p$. Denote the
batch as $B_{t}$.

4: For each $(x_{j}^{(t)},y_{j}^{(t)})\in B_{t}$, denote
$g_{t}(\mathbf{x}_{j}^{(t)})=\nabla\ell(\mathbf{W}^{(t)};\mathbf{x}_{j}^{(t)},y_{j}^{(t)}).$

5: Let
$\tilde{g}_{t}({x}_{j}^{(t)})=g_{t}({x}_{j}^{(t)})/\max(1,\frac{||g_{t}({x}_{j}^{(t)})||_{2}}{C}).$

6: Update weight matrices as
$\mathbf{W^{(t+1)}}=\Pi_{\mathcal{W}}(\mathbf{W}^{(t)}-\eta\cdot(\frac{1}{|B_{t}|}\sum_{(x^{(t)}_{j},y_{j}^{(t)})\in
B_{t}}{\tilde{g}_{t}}({x}_{j}^{(t)})+\mathbf{G}_{t}))$, where
$\mathbf{G}_{t}\sim\mathcal{N}(\mathbf{0},\sigma^{2}\mathbb{I})$ drawn
independently each iteration.

7: end for

8: return
$\tilde{\mathbf{W}}_{priv}=\frac{1}{T}\sum_{t=1}^{T}\mathbf{W}^{(t)}$

In order to validate the usefulness of the aforementioned theorem and
investigate the effect of hyperparameters on the error, as mentioned in Remark
5, we conducted experiments using a three-layer MLP model on the MNIST
dataset. The training set comprised 60,000 samples, with each sample
represented by a 784-dimensional vector.

Figure 1: Results of the first term in Theorem 8.

Figure 2:  Impact of Clipping Constant.

Figure 3:  Impact of network width $m$.

Figure 4:  Impact of training iteration $T$.

Figure 5:  Impact of sample size $n$.

  1. 1.

First, we aim to study the NTRF approximation error in the bound of Theorem 10
with different values of $R$ and $m$, which can be approximated by solving the
convex optimization problem
$\inf_{f\in\mathcal{F}(W^{(0)},R/\sqrt{m})}{\frac{1}{|S|}\sum_{(x,y)\in
S}\ell(f(x),y)}$ with projected stochastic gradient descent. In this
particular experiment, we set the width of MLPs for each layer as
$\\{200,500,2000\\}$, respectively. Each model is trained for 200 epochs with
a learning rate of $10^{-2}$. $R/\sqrt{m}$ varies from 0.1 to 1.9 with a step
of 0.2. Figure 1 reports the average results of 10 runs.

  2. 2.

Next, we investigate the impact of the clipping constant $C$ on the testing
loss. To do so, we apply the DP-SGD optimizer to a three-layer MLP model with
a width of 256, and train the model for 200 epochs with a learning rate of
$\eta=0.01$, using a training set of 60,000 samples. We set $\epsilon=1$ and
$\delta=1/n^{2}$. The results are shown in Figure 5.

  3. 3.

In Figure 5, we plot the mean testing error and 95% confidence interval based
on 10 runs of the DP-SGD optimizer with different values of $m$. The optimizer
is applied to a three-layer MLP model trained with a learning rate of 0.01 and
200 epochs, using $n=5,000$, $\epsilon=1$, $\delta=1/n^{2}$, and $C=20$.

  4. 4.

In Figure 5, we plot the testing error mean value and 95% confidence interval
of 10 runs with different value of $T$, which illustrates how the testing loss
will change as $T$ increases with the setting of $n=60,000$ and $m=256$. Other
parameters are the same as above.

  5. 5.

In Figure 5, we plot the impact of n on the testing error of DP-SGD. In this
setting, we choose the parameters satisfying the condition in Theorem 10, with
$m=(n^{\frac{14}{15}})/2,T=50n^{\frac{2}{15}}$, $\epsilon=1,\delta=1/n^{2}$
and $C=20$. It is notable that our parameter setting is to make each term in
the upper bound (10) decrease when $n$ becomes larger.

Analysis. The results presented in the above figures provide insightful
findings on the impact of different hyperparameters on the excess population
risk in DP-SGD-trained neural networks. Figure 1 shows that the approximation
error in the upper bound of Theorem 10 yields a small and meaningful value,
and that increasing the size of the hyperparameter space $R$ results in a
smaller approximation error. Moreover, when the network width $m$ is
increased, the approximation error tends to zero, indicating that the NTRF
space can better fit wider neural networks on the training data. Figure 5
illustrates that when the clipping constant $C$ is chosen from $[1,64]$, the
excess population risk remains unaffected, which aligns with our theoretical
analysis. The curves in Figure 5 and Figure 5 show that the excess population
risk has a trade-off in choosing the network width $m$ and training iteration
$T$, with neither of them being too large or too small. This is consistent
with our theoretical findings and our discussions in Remark 5. Furthermore,
Figure 5 demonstrates that the performance of DP-SGD is similar to that of
non-private SGD when the sample size is sufficiently large. These findings
highlight the importance of carefully tuning hyperparameters in DP-SGD-trained
neural networks and provide valuable guidance for practical applications.

##  VII Conclusion

We presented a comprehensive study on the theoretical guarantees of DP Multi-
layer Neural Networks. We started by considering the case where there are no
hidden nodes, i.e., non-convex Generalized Linear Models. In the well-
specified model, we studied the cases where the link function is Lipschitz and
bounded (such as sigmoid) or unbounded (such as ReLU). We also analyzed ReLU
regression in the misspecified model to highlight its difference from the
well-specified model. Next, we extended our techniques to two-layer neural
networks with sigmoid or ReLU activation functions in the well-specified
model. Finally, we analyzed the standard DP-SGD method for general multi-layer
neural networks and provided an upper bound for the excess population risk.

## References

  * [1] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in Theory of cryptography conference, pp. 265–284, Springer, 2006.
  * [2] D. Wang and J. Xu, “Differentially private empirical risk minimization with smooth non-convex loss functions: A non-stationary view,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 1182–1189, 2019.
  * [3] D. Wang, C. Chen, and J. Xu, “Differentially private empirical risk minimization with non-convex loss functions,” in International Conference on Machine Learning, pp. 6526–6535, PMLR, 2019.
  * [4] L. Wang, B. Jayaraman, D. Evans, and Q. Gu, “Efficient privacy-preserving stochastic nonconvex optimization,” arXiv preprint arXiv:1910.13659, 2019\.
  * [5] S. Song, T. Steinke, O. Thakkar, and A. Thakurta, “Evading the curse of dimensionality in unconstrained private glms,” in International Conference on Artificial Intelligence and Statistics, pp. 2638–2646, PMLR, 2021\.
  * [6] N. Agarwal, Z. Allen-Zhu, B. Bullins, E. Hazan, and T. Ma, “Finding approximate local minima faster than gradient descent,” in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1195–1199, 2017.
  * [7] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308–318, 2016.
  * [8] Y. Zhou, Z. S. Wu, and A. Banerjee, “Bypassing the ambient dimension: Private sgd with gradient subspace identification,” arXiv preprint arXiv:2007.03813, 2020.
  * [9] R. Bassily, C. Guzmán, and M. Menart, “Differentially private stochastic optimization: New results in convex and non-convex settings,” Advances in Neural Information Processing Systems, vol. 34, 2021.
  * [10] Q. Zhang, J. Ma, J. Lou, and L. Xiong, “Private stochastic non-convex optimization with improved utility rates,” in Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, 2021.
  * [11] H. Xiao, Z. Xiang, D. Wang, and S. Devadas, “A theory to instruct differentially-private learning via clipping bias reduction,” in 2023 IEEE Symposium on Security and Privacy (SP), pp. 2170–2189, IEEE Computer Society, 2023.
  * [12] D. Wang and J. Xu, “Escaping saddle points of empirical risk privately and scalably via dp-trust region method,” in Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 90–106, Springer, 2020.
  * [13] D. Wang, M. Ye, and J. 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.
  * [14] P. Jain and A. G. Thakurta, “(near) dimension independent risk bounds for differentially private learning,” in International Conference on Machine Learning, pp. 476–484, PMLR, 2014.
  * [15] S. P. Kasiviswanathan and H. Jin, “Efficient private empirical risk minimization for high-dimensional learning,” in International Conference on Machine Learning, pp. 488–497, PMLR, 2016.
  * [16] R. Arora, R. Bassily, C. Guzmán, M. Menart, and E. Ullah, “Differentially private generalized linear models revisited,” arXiv preprint arXiv:2205.03014, 2022.
  * [17] L. Hu, S. Ni, H. Xiao, and D. Wang, “High dimensional differentially private stochastic optimization with heavy-tailed data,” in Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 227–236, 2022.
  * [18] R. Bassily, A. Smith, and A. Thakurta, “Private empirical risk minimization: Efficient algorithms and tight error bounds,” in Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pp. 464–473, IEEE, 2014.
  * [19] S. Frei, Y. Cao, and Q. Gu, “Agnostic learning of a single neuron with gradient descent,” Advances in Neural Information Processing Systems, vol. 33, pp. 5417–5428, 2020.
  * [20] S. Goel and A. R. Klivans, “Learning neural networks with two nonlinear layers in polynomial time,” in Conference on Learning Theory, pp. 1470–1499, PMLR, 2019.
  * [21] T. T. Cai, Y. Wang, and L. Zhang, “The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy,” The Annals of Statistics, vol. 49, no. 5, pp. 2825–2850, 2021.
  * [22] D. Wang and J. Xu, “On sparse linear regression in the local differential privacy model,” IEEE Transactions on Information Theory, vol. 67, no. 2, pp. 1182–1200, 2020.
  * [23] A. T. Kalai and R. Sastry, “The isotron algorithm: High-dimensional isotonic regression.,” in COLT, Citeseer, 2009.
  * [24] S. M. Kakade, A. T. Kalai, V. Kanade, and O. Shamir, “Efficient learning of generalized linear and single index models with isotonic regression,” in Proceedings of the 24th International Conference on Neural Information Processing Systems, pp. 927–935, 2011.
  * [25] J.-J. Moreau, “Proximité et dualité dans un espace hilbertien,” Bulletin de la Société mathématique de France, vol. 93, pp. 273–299, 1965.
  * [26] I. Diakonikolas, S. Goel, S. Karmalkar, A. R. Klivans, and M. Soltanolkotabi, “Approximation schemes for relu regression,” in Conference on Learning Theory, pp. 1452–1485, PMLR, 2020.
  * [27] S. Goel, S. Karmalkar, and A. Klivans, “Time/accuracy tradeoffs for learning a relu with respect to gaussian marginals,” Advances in Neural Information Processing Systems, vol. 32, 2019.
  * [28] P. Manurangsi and D. Reichman, “The computational complexity of training relu (s),” arXiv preprint arXiv:1810.04207, 2018.
  * [29] Y. Kang, Y. Liu, B. Niu, and W. Wang, “Weighted distributed differential privacy erm: Convex and non-convex,” Computers & Security, vol. 106, p. 102275, 2021.
  * [30] R. Arora, R. Bassily, T. González, C. Guzmán, M. Menart, and E. Ullah, “Faster rates of convergence to stationary points in differentially private optimization,” arXiv preprint arXiv:2206.00846, 2022.
  * [31] Y.-L. Chen, Z. Wang, and M. Kolar, “Provably Training Neural Network Classifiers under Fairness Constraints,” arXiv:2012.15274 [cs, math, stat], Dec. 2020.  arXiv: 2012.15274.
  * [32] Y. Cao and Q. Gu, “Generalization error bounds of gradient descent for learning over-parameterized deep relu networks,” 2019.
  * [33] O. Shamir and T. Zhang, “Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes,” in International conference on machine learning, pp. 71–79, PMLR, 2013.
  * [34] A. Jacot, F. Gabriel, and C. Hongler, “Neural Tangent Kernel: Convergence and Generalization in Neural Networks,” arXiv:1806.07572 [cs, math, stat], Feb. 2020.  arXiv: 1806.07572.
  * [35] S. Arora, S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang, “On exact computation with an infinitely wide neural net,” Advances in Neural Information Processing Systems, vol. 32, 2019.
  * [36] J. Lee, L. Xiao, S. S. Schoenholz, Y. Bahri, R. Novak, J. Sohl-Dickstein, and J. Pennington, “Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2020, p. 124002, Dec. 2020.  arXiv: 1902.06720.
  * [37] J. Lee, Y. Bahri, R. Novak, S. Schoenholz, J. Pennington, and J. Sohl-dickstein, “Deep neural networks as gaussian processes,” in International Conference on Learning Representations, 2018.
  * [38] X. Li, D. Liu, T. Hashimoto, H. A. Inan, J. Kulkarni, Y. T. Lee, and A. G. Thakurta, “When does differentially private learning not suffer in high dimensions?,” arXiv preprint arXiv:2207.00160, 2022.
  * [39] V. Feldman, T. Koren, and K. 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.
  * [40] S. Bubeck et al., “Convex optimization: Algorithms and complexity,” Foundations and Trends® in Machine Learning, vol. 8, no. 3-4, pp. 231–357, 2015.
  * [41] M. Hardt, B. Recht, and Y. Singer, “Train faster, generalize better: Stability of stochastic gradient descent,” in International conference on machine learning, pp. 1225–1234, PMLR, 2016.
  * [42] Z. Allen-Zhu, Y. Li, and Z. Song, “A Convergence Theory for Deep Learning via Over-Parameterization,” arXiv:1811.03962 [cs, math, stat], June 2019.  arXiv: 1811.03962.
  * [43] D. Zou, Y. Cao, D. Zhou, and Q. Gu, “Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks,” arXiv:1811.08888 [cs, math, stat], Dec. 2018.  arXiv: 1811.08888.
  * [44] Y. Cao and Q. Gu, “Generalization bounds of stochastic gradient descent for wide and deep neural networks,” Advances in Neural Information Processing Systems, vol. 32, pp. 10836–10846, 2019.
  * [45] W. Rhee and M. Talagrand, “Uniform bound in the central limit theorem for banach space valued dependent random variables,” Journal of Multivariate Analysis, vol. 20, no. 2, pp. 303–320, 1986.

##  Appendix A Omitted Proofs in Section IV

###### Proof of Lemma 2.

Note that by the definition of $\ell$ we have for any $w$,

$\displaystyle\nabla\ell(w;x,y)=(\sigma(\langle w,x\rangle-y)\cdot x,$
$\displaystyle\nabla^{2}\ell(w;x,y)=\sigma^{\prime}(\langle w,x\rangle\cdot
xx^{T},$

where $\sigma^{\prime}(\cdot)$ is a subgradient of $\sigma$. Since $\sigma$ is
increasing, we have $\sigma^{\prime}(\cdot)\geq 0$. Therefore we have
$\nabla^{2}\ell(w;x,y)\succ 0$ and $\ell(\cdot;x,y)$ is convex and its Hessian
matrix has rank at most 1. Since $\|\nabla\ell(w;x,y)\|_{2}\leq 2BR$ and
$\nabla^{2}\ell(w;x,y)\prec GR^{2}I_{d}$, $\ell(\cdot;x,y)$ is $2B$-Lipschitz
and $G$-smooth. ∎

###### Proof of Lemma 3 .

For any fixed $x$ we have

$\displaystyle\mathbb{E}_{y}[\ell(w;x,y)]-\mathbb{E}_{y}[\ell(w^{*};x,y)]=\mathbb{E}_{y}\int_{\langle
w^{*},x\rangle}^{\langle w,x\rangle}(\sigma(z)-y)dz$
$\displaystyle=\int_{\langle w^{*},x\rangle}^{\langle
w,x\rangle}(\sigma(z)-\mathbb{E}_{y}y)dz=\int_{\langle
w^{*},x\rangle}^{\langle w,x\rangle}(\sigma(z)-\sigma(\langle
w^{*},x\rangle))dz$ $\displaystyle=\int_{\langle w^{*},x\rangle}^{\langle
w,x\rangle}\frac{\sigma^{\prime}(z)(\sigma(z)-\sigma(\langle
w^{*},x\rangle))}{\sigma^{\prime}(z)}dz$
$\displaystyle\geq\frac{1}{2G}(\sigma(\langle w,x\rangle)-\sigma(\langle
w^{*},x\rangle))^{2},$

where the last inequality is due to the fact that $\sigma$ is monotonically
increasing and $G$-Lipschitz. Thus, taking the expectation of $x$ we have

$\displaystyle L^{\ell}_{\mathcal{P}}(w)-L^{\ell}_{\mathcal{P}}(w^{*})$
$\displaystyle\geq\frac{1}{2G}\mathbb{E}_{x}(\sigma(\langle
w,x\rangle)-\sigma(\langle w^{*},x\rangle))^{2}$
$\displaystyle=\frac{1}{2G}(L_{\mathcal{P}}(w)-L_{\mathcal{P}}(w^{*})).$

∎

###### Proof of Theorem 1.

Before the proof, we first provide some notations. For any
$u,u^{\prime}\in\mathbb{R}^{d}$, let $\|u\|_{V}=\sqrt{u^{T}VV^{T}u}$ as the
semi-norm of $u$ induced by $V$, and let $\langle
u,u^{\prime}\rangle_{V}=u^{T}VV^{T}u^{\prime}$.

Since $\ell(\cdot;x,y)$ is $2B$-Lipschitz and $G$-smooth, by Theorem 4.4 in
[39] we can see it is $(\epsilon,\delta)$-DP when $\eta\leq\frac{2}{G}$. For
utility, it is sufficient to show that

$\mathbb{E}L_{\mathcal{P}}(w_{k})-L_{\mathcal{P}}(w^{*})\leq
O(GBW(\frac{\sqrt{\theta\log\frac{1}{\delta}}}{n\epsilon}+\frac{1}{\sqrt{n}})).$
(8)

Our proof follows the proof of convex GLM in [9]. We first show the following
lemma.

######  Lemma 8.

For each epoch $i$ we have
$\mathbb{E}[L_{\mathcal{P}}^{\ell}(\bar{w}_{i})-L_{\mathcal{P}}^{\ell}(\bar{w}_{i-1})]\leq\frac{\mathbb{E}\|\bar{w}_{i-1}-w_{i-1}\|_{V}^{2}}{2\eta_{i}n_{i}}+2B^{2}\eta_{i}.$

###### Proof.

For simplicity we omit the subscript $i$ in $w_{i}^{t}$ and $\eta_{i}$. Denote
$\Phi^{t}=\|w^{t}-\bar{w}_{i-1}\|_{V}^{2}$, we have

$\displaystyle\Phi^{t+1}$
$\displaystyle=\Phi^{t}-2\eta\langle\nabla\ell(w^{t};x^{t},y^{t}),w^{t}-\bar{w}_{i-1}\rangle+\eta^{2}\|\nabla\ell(w^{t};x^{t},y^{t})\|_{2}^{2}$
$\displaystyle\leq\Phi^{t}-2\eta\langle\nabla\ell(w^{t};x^{t},y^{t}),w^{t}-\bar{w}_{i-1}\rangle+4\eta^{2}B^{2},$

where the first inequality is due to the fact that
$\nabla\ell(w^{t};x^{t},y^{t})$ in the span of $V$ and $\ell$ is
$2B$-Lipschitz. Thus,

$\langle\nabla\ell(w^{t};x^{t},y^{t}),w^{t}-\bar{w}_{i-1}\rangle\leq\frac{\Phi^{t}-\Phi^{t+1}}{2\eta}+2B^{2}\eta.$

By the convexity of $L_{\mathcal{P}}^{\ell}$ and take the expectation w.r.t
all the data we have

$\displaystyle\mathbb{E}[L_{\mathcal{P}}^{\ell}(w^{t})-L_{\mathcal{P}}^{\ell}(\bar{w}_{i-1})]$
$\displaystyle\leq\mathbb{E}[\langle\nabla
L_{\mathcal{P}}^{\ell}(w^{t}),w^{t}-\bar{w}_{i-1}\rangle]$
$\displaystyle\leq\mathbb{E}[\frac{\Phi^{t}-\Phi^{t+1}}{2\eta}]+2B^{2}\eta.$

Thus, we have

$\displaystyle\mathbb{E}[L_{\mathcal{P}}^{\ell}({\bar{w}_{i}})-L_{\mathcal{P}}^{\ell}(\bar{w}_{i-1})]\leq\frac{\mathbb{E}[\Phi^{1}]}{2\eta
n_{i}}+2B^{2}\eta=\frac{\mathbb{E}\|\bar{w}_{i-1}-w_{i-1}\|_{V}^{2}}{2\eta
n_{i}}+2B^{2}\eta.$

∎

Now we back to our proof. Denote $\bar{w}_{0}=w_{\ell}^{*}$ and
$\zeta_{0}=w_{0}-w_{\ell}^{*}$, where
$w_{\ell}^{*}=\arg\min_{w\in\mathbb{R}^{d}}L_{\mathcal{P}}^{\ell}(w)$, we have

$\displaystyle\mathbb{E}[L_{\mathcal{P}}^{\ell}(w_{k})-L_{\mathcal{P}}^{\ell}(w_{\ell}^{*})]$
$\displaystyle=\mathbb{E}[L_{\mathcal{P}}^{\ell}(w_{k})-L_{\mathcal{P}}^{\ell}(\bar{w}_{k})]+\sum_{i=1}^{k}\mathbb{E}[L_{\mathcal{P}}^{\ell}(\bar{w}_{i})-L_{\mathcal{P}}^{\ell}(\bar{w}_{i-1})]$
$\displaystyle\leq\sum_{i=1}^{k}(\frac{\mathbb{E}\|\zeta_{i-1}\|_{V}^{2}}{2\eta_{i}n_{i}}+2B^{2}\eta_{i})+\mathbb{E}[L_{\mathcal{P}}^{\ell}(w_{k})-L_{\mathcal{P}}^{\ell}(\bar{w}_{k})].$

Note that for all $2\leq i\leq k$, we have

$\mathbb{E}\|\zeta_{i-1}\|_{V}^{2}=\mathbb{E}_{V}[\mathbb{E}_{\zeta_{i-1}}[\zeta^{T}_{i-1}VV^{T}\zeta_{i-1}|V]]\leq\theta\tau_{i-1}^{2}.$

And when $i=1$,
$\mathbb{E}\|\zeta_{i-1}\|_{V}^{2}\leq\|w_{0}-w_{\ell}^{*}\|_{2}^{2}.$ For
$\mathbb{E}[L_{\mathcal{P}}^{\ell}(w_{k})-L_{\mathcal{P}}^{\ell}(\bar{w}_{k})]$
we have

$\mathbb{E}[L_{\mathcal{P}}^{\ell}(w_{k})-L_{\mathcal{P}}^{\ell}(\bar{w}_{k})]\leq
2B\mathbb{E}[\langle\zeta_{k},x\rangle]\leq 2B\tau_{k}\leq
O(\frac{WB\sqrt{\log\frac{1}{\delta}}}{\epsilon n^{\frac{5}{2}}}).$

In total we have

$\displaystyle\sum_{i=1}^{k}(\frac{\mathbb{E}\|\zeta_{i-1}\|_{V}^{2}}{2\eta_{i}n_{i}}+2B^{2}\eta_{i})+\mathbb{E}[L_{\mathcal{P}}^{\ell}(w_{k})-L_{\mathcal{P}}^{\ell}(\bar{w}_{k})]$
$\displaystyle\leq\sum_{i=2}^{k}(\frac{\theta\tau^{2}_{i-1}}{2\eta_{i}n_{i}}+2B^{2}\eta_{i})+\frac{\|w_{0}-w_{\ell}^{*}\|^{2}_{2}}{2\eta_{1}n_{1}}+2B^{2}R^{2}\eta_{1}+O(\frac{WB\sqrt{\log\frac{1}{\delta}}}{\epsilon
n^{\frac{5}{2}}})$ $\displaystyle\leq
O(BW(\frac{\sqrt{\theta\log\frac{1}{\delta}}}{n\epsilon}+\frac{1}{\sqrt{n}})).$

Note that by Lemma 3 we can see that $w_{\ell}^{*}=w^{*}$. Thus we have
$\mathbb{E}L_{\mathcal{P}}(w)-L_{\mathcal{P}}(w^{*})\leq
2G(\mathbb{E}L^{\ell}_{\mathcal{P}}(w)-L^{\ell}_{\mathcal{P}}(w^{*}))\leq
O(GBW(\frac{\sqrt{\theta\log\frac{1}{\delta}}}{n\epsilon}+\frac{1}{\sqrt{n}})).$
∎

###### Proof of Theorem 2.

We first prove the privacy guarantee. Let $\alpha\leq 1$ be a parameter to be
set later. From the JL property we know that with $m=O(\frac{\log
n/\delta}{\alpha^{2}})$, then with probability at least $1-\frac{\delta}{2}$
for all feature vectors we have $\|\Phi
x_{i}\|_{2}\leq(1+\alpha)\|x_{i}\|_{2}\leq 2\|x_{i}\|_{2}$, and $\|\Phi
w^{*}\|_{2}\leq 2\|w^{*}\|_{2}\leq 2W$. In the following we will show if the
previous events hold (which is denoted as $E$) then the Algorithm is
$(\epsilon,\frac{\delta}{2})$-DP.

To see this note that
$\ell(w_{i}^{t};\tilde{x}_{i}^{t},y_{i}^{t})=\ell(w_{i}^{t};\Phi{x}_{i}^{t},y_{i}^{t})$,
we have
$\|\nabla\ell(w_{i}^{t};\tilde{x}_{i}^{t},y_{i}^{t})\|_{2}=\|(\sigma(\langle
w_{i}^{t},\Phi{x}_{i}^{t}\rangle)-y_{i}^{t})\Phi{x}_{i}^{t}\|_{2}\leq 4B$ and
$\ell(w_{i}^{t};\tilde{x}_{i}^{t},y_{i}^{t})$ is $4G$-smooth. Thus, by Theorem
1 it is $(\epsilon,\frac{\delta}{2})$-DP if $\eta\leq\frac{2}{4G}$.

We then show the whole algorithm $\mathcal{A}$ is $(\epsilon,\delta)$-DP.
Consider any event of the output $S$ and any neighboring datasets $D\sim
D^{\prime}$, we have

$\displaystyle\mathcal{P}(\mathcal{A}(D)\in S)=\mathcal{P}(\mathcal{A}(D)\in
S\bigcap E)+\mathcal{P}(\mathcal{A}(D)\in S\bigcap\bar{E})$ $\displaystyle\leq
e^{\epsilon}\mathcal{P}(\mathcal{A}(D^{\prime})\in S\bigcap
E)+\frac{\delta}{2}+\mathcal{P}(\mathcal{A}(D)\in\bar{E})$ $\displaystyle\leq
e^{\epsilon}\mathcal{P}(\mathcal{A}(D^{\prime})\in S)+\delta.$

Next we will show the utility. For simplicity we denote the projected
distribution $\mathcal{P}^{\prime}=\Phi\mathcal{P}$ we first decompose the
excess population risk as the following:

$\displaystyle\mathbb{E}[L_{\mathcal{P}}^{\ell}(\hat{w})]-L_{\mathcal{P}}^{\ell}(w^{*})=\mathbb{E}[L_{\mathcal{P}^{\prime}}^{\ell}(w_{k})]-\mathbb{E}_{\Phi,\tilde{D}}L^{\ell}(\Phi
w^{*},\tilde{D})+\mathbb{E}_{\Phi,\tilde{D}}L^{\ell}(\Phi
w^{*},\tilde{D})-L_{\mathcal{P}}^{\ell}(w^{*}).$

For the second term by Lemma 3 we know $w^{*}$ is also the global minimizer of
$L_{\mathcal{P}}^{\ell}(w^{*})$ and by Lemma 2 we know it is $G$-smooth, thus
we have

$\displaystyle\mathbb{E}_{\Phi,\tilde{D}}L^{\ell}(\Phi
w^{*},\tilde{D})-L_{\mathcal{P}}^{\ell}(w^{*})$
$\displaystyle=\mathbb{E}_{\Phi,(x_{i},y_{i})\sim\mathcal{P}}[g^{y_{i}}(\langle\Phi
w^{*},\Phi x_{i}\rangle)-g^{y_{i}}(\langle w^{*},x_{i}\rangle)]$
$\displaystyle\leq\nabla
L^{\ell}_{\mathcal{P}}(w^{*})+\frac{G}{2}\mathbb{E}\|\langle\Phi w^{*},\Phi
x_{i}\rangle-\langle w^{*},x_{i}\rangle\|_{2}^{2}$
$\displaystyle=\frac{G}{2}\mathbb{E}\|\langle\Phi w^{*},\Phi
x_{i}\rangle-\langle w^{*},x_{i}\rangle\|_{2}^{2}$ (9)

where the last inequality is due to that

$\displaystyle\mathbb{E}_{x_{i},\Phi}|\langle\Phi w^{*},\Phi
x_{i}\rangle-\langle
w^{*},x_{i}\rangle|=\mathbb{E}_{x_{i}}\mathbb{E}_{\Phi}|\langle\Phi w^{*},\Phi
x_{i}\rangle-\langle w^{*},x_{i}\rangle|^{2}\leq\tilde{O}(W\frac{1}{{m}}).$

To bound the first term, we first $\Phi$ and use a similar analysis as in the
proof of Theorem 1. The main difference here we use the following lemma
instead of $\|\bar{w}_{i-1}-w_{i-1}\|_{V}^{2}$. Note that it is always true as
$\|\bar{w}_{i-1}-w_{i-1}\|_{V}^{2}\leq\|\bar{w}_{i-1}-w_{i-1}\|^{2}_{2}$

######  Lemma 9.

For each epoch $i$ we have
$\mathbb{E}[L_{\mathcal{P}^{\prime}}^{\ell}(\bar{w}_{i})-L_{\mathcal{P}^{\prime}}^{\ell}(\bar{w}_{i-1})]\leq\frac{\mathbb{E}\|\bar{w}_{i-1}-w_{i-1}\|_{2}^{2}}{2\eta_{i}n_{i}}+2B^{2}\eta_{i}.$

Denote $\bar{w}_{0}=\Phi w^{*}$ and $\zeta_{0}=w_{0}-\Phi w^{*}$, we have

$\displaystyle\mathbb{E}[L_{\mathcal{P}^{\prime}}^{\ell}(w_{k})]-\mathbb{E}L_{\mathcal{P}^{\prime}}^{\ell}(\Phi
w^{*})$
$\displaystyle=\mathbb{E}[L_{\mathcal{P}^{\prime}}^{\ell}(w_{k})-L_{\mathcal{P}^{\prime}}^{\ell}(\bar{w}_{k})]+\sum_{i=1}^{k}\mathbb{E}[L_{\mathcal{P}^{\prime}}^{\ell}(\bar{w}_{i})-L_{\mathcal{P}^{\prime}}^{\ell}(\bar{w}_{i-1})]$
$\displaystyle\leq\sum_{i=1}^{k}(\frac{\mathbb{E}\|\zeta_{i-1}\|_{2}^{2}}{2\eta_{i}n_{i}}+2B^{2}\eta_{i})+\mathbb{E}[L_{\mathcal{P}^{\prime}}^{\ell}(w_{k})-L_{\mathcal{P}^{\prime}}^{\ell}(\bar{w}_{k})].$

Note that for all $2\leq i\leq k$, we have
$\mathbb{E}\|\zeta_{i-1}\|_{2}^{2}=m\tau_{i-1}^{2}$. For
$\mathbb{E}[L_{\mathcal{P}^{\prime}}^{\ell}(w_{k})-L_{\mathcal{P}^{\prime}}^{\ell}(\bar{w}_{k})]$
we have

$\mathbb{E}[L_{\mathcal{P}^{\prime}}^{\ell}(w_{k})-L_{\mathcal{P}^{\prime}}^{\ell}(\bar{w}_{k})]\leq
2B\mathbb{E}[\langle\zeta_{k},x\rangle]\leq 2B\tau_{k}\leq
O(\frac{WB\sqrt{\log\frac{1}{\delta}}}{\epsilon n^{\frac{5}{2}}}).$

In total we have

$\displaystyle\sum_{i=1}^{k}(\frac{\mathbb{E}\|\zeta_{i-1}\|_{2}^{2}}{2\eta_{i}n_{i}}+2B^{2}\eta_{i})+\mathbb{E}[L_{\mathcal{P}^{\prime}}^{\ell}(w_{k})-L_{\mathcal{P}^{\prime}}^{\ell}(\bar{w}_{k})]$
$\displaystyle\leq\sum_{i=2}^{k}(\frac{m\tau^{2}_{i-1}}{2\eta_{i}n_{i}}+2B^{2}\eta_{i})+\frac{\|w_{0}-\Phi
w^{*}\|^{2}_{2}}{2\eta_{1}n_{1}}+2B^{2}R^{2}\eta_{1}+O(\frac{WB\sqrt{\log\frac{1}{\delta}}}{\epsilon
n^{\frac{5}{2}}})$ $\displaystyle\leq
O(BW(\frac{\sqrt{m\log\frac{1}{\delta}}}{n\epsilon}+\frac{1}{\sqrt{n}})).$

Note that the previous bound only holds when $\|\Phi
x_{i}\|\leq(1+\frac{\log\sqrt{n/\delta}}{m})$ which holds with probability at
least $1-\delta$. Thus we can use the same argument as in the Proof of Lemma 8
in [16] to transform the above result to a result of the expectation w.r.t
$\Phi$ with an additional logarithmic factor. Thus, in total we have

$\mathbb{E}[L_{\mathcal{P}}^{\ell}(\hat{w})]-L_{\mathcal{P}}^{\ell}(w^{*})\leq\tilde{O}(GW\frac{1}{m}+BW(\frac{\sqrt{m\log\frac{1}{\delta}}}{n\epsilon}+\frac{1}{\sqrt{n}}))$

Take $m=O(\log(n/\delta)(n\epsilon)^{\frac{2}{3}})$ we can get
$\mathbb{E}L_{\mathcal{P}}(\hat{w})-L_{\mathcal{P}}(w^{*})\leq
2G(\mathbb{E}L^{\ell}_{\mathcal{P}}(\hat{w})-L^{\ell}_{\mathcal{P}}(w^{*}))\leq\tilde{O}(G^{2}WB(\frac{\sqrt{\log\frac{1}{\delta}}}{({n\epsilon})^{\frac{2}{3}}}+\frac{1}{\sqrt{n}})).$

∎

###### Proof of Lemma 6.

Note that by our definition we have $\nabla f_{\beta}(w;x,y)=xg^{\prime
y}_{\beta}(\langle w,x\rangle)$, where

$g^{\prime y}_{\beta}(m)=\beta[m-\text{prox}_{g}^{\beta}(m)].$ (10)

Next we will provide an algorithm to approximate
$\text{prox}_{\ell}^{\beta}(x)$ for given $x$. Recall that by the definition

$\text{prox}_{g}^{\beta}(m)=\arg\min_{u\in\mathbb{R}}[g^{y}(u)+\frac{\beta}{2}|u-m|^{2}]$

First we will show that
$\text{prox}_{g}^{\beta}(m)\in[m-\frac{4B}{\beta},m+\frac{4B}{\beta}]$. For
simplicity we denote
$u^{*}=\arg\min_{u\in\mathbb{R}}h(u)=\arg\min_{u\in\mathbb{R}}[g^{y}(u)+\frac{\beta}{2}|u-m|^{2}]$.
Then since $u^{*}$ is the minimizer of $h(\cdot)$ we have

$\displaystyle 0\leq
h(m)-h(u^{*})=g^{y}(m)-g^{y}(u^{*})-\frac{\beta}{2}|u^{*}-m|^{2}$
$\displaystyle\iff\frac{\beta}{2}|u^{*}-m|^{2}\leq g^{y}(m)-g^{y}(u^{*}).$

Since we have $g^{y}(\cdot)$ is $2B$-Lipschitz (Lemma 2). Thus,

$\frac{\beta}{2}|u^{*}-m|^{2}\leq g^{(y)}(m)-g^{(y)}(u^{*})\leq
2B|m-u^{*}|\iff|m-u^{*}|\leq\frac{4B}{\beta}.$

That is

$\text{prox}_{g}^{\beta}(m)=\arg\min_{u\in\mathbb{R}}[g^{y}(u)+\frac{\beta}{2}|u-m|^{2}]=\arg\min_{u\in\mathcal{Q}}[g^{y}(u)+\frac{\beta}{2}|u-m|^{2}],$

where $\mathcal{Q}=[m-\frac{4B}{\beta},m+\frac{4B}{\beta}]$. Moreover, on the
constraint set $\mathcal{Q}$, function $h(\cdot)$ is $\beta$-strongly convex
and $2B+4B=6B$-Lipschitz. Thus, from a standard result on convergence of
Gradient Decent for strongly and Lipschitz functions (which corresponds to
Step 3 to 7 in Algorithm 4, note that Step 5 is just the projection onto the
set $\mathcal{Q}$) in [40] we can see that after $T$-steps we have

$\frac{\beta}{2}|\hat{w}-u^{*}|^{2}\leq
h(\hat{w})-h(u^{*})\leq\frac{72B^{2}}{\beta(T+1)}.$

Thus we have $|\hat{w}-u^{*}|\leq\frac{12B}{\beta\sqrt{T}}$. Thus we have
$\|x\beta[\langle w,x\rangle-\hat{w}]-\nabla
f_{\beta}(w;x,y)\|_{2}\leq\frac{12B}{\sqrt{T}}$.

∎

###### Proof of Theorem 3.

We first proof the guarantee of $(\epsilon,\delta)$-DP. Note that unlike
Algorithm 2, here we use an approximation of $\nabla f_{\beta}(w;x,y)$.
Consider a neighboring dataset $D^{\prime}$ of $D$ assume the different
samples are in $D_{i}$ which are denoted as $x_{i}^{t}$ and
$x_{i}^{{}^{\prime}t}$ respectively. Moreover, we denote
$w_{i}^{{}^{\prime}t}$ as the parameters when implementing the algorithm on
$D^{\prime}$. Then by our assumption we have $w_{i}^{t}=w_{i}^{{}^{\prime}t}$
but $w_{i}^{t_{0}}\neq w_{i}^{{}^{\prime}t_{0}}$ when $t_{0}\geq t+1$.
Moreover, for any $t_{0}\geq t+1$ we have

$\displaystyle\|w_{i}^{t_{0}}-w_{i}^{{}^{\prime}t_{0}}\|_{2}\leq\|w_{i}^{t_{0}-1}-\eta_{i}{\nabla}f_{\beta}(w_{i}^{t_{0}-1};x_{i}^{t_{0}-1},y_{i}^{t_{0}-1})-w_{i}^{{}^{\prime}t_{0}-1}+\eta_{i}{\nabla}f_{\beta}(w_{i}^{t_{0}-1};x_{i}^{{}^{\prime}t_{0}-1},y_{i}^{{}^{\prime}t_{0}-1})\|_{2}+2\eta_{i}\gamma$

where $x_{i}^{t_{0}}\neq x_{i}^{{}^{\prime}t_{0}}$ if $t_{0}=t+1$ and
$x_{i}^{t}=x_{i}^{{}^{\prime}t}$ otherwise. Note that since $f_{\beta}$ is
$\beta$-smooth. Thus, by using a similar proof as in [41] we have when
$\eta\leq\frac{2}{\beta}$ and $t_{0}\geq t+2$ we always have

$\displaystyle\|w_{i}^{t_{0}-1}-\eta_{i}{\nabla}f_{\beta}(w_{i}^{t_{0}-1};x_{i}^{t_{0}-1},y_{i}^{t_{0}-1})-w_{i}^{{}^{\prime}t_{0}-1}+\eta_{i}{\nabla}f_{\beta}(w_{i}^{t_{0}-1};x_{i}^{{}^{\prime}t_{0}-1},y_{i}^{{}^{\prime}t_{0}-1})\|_{2}\leq\|w_{i}^{t_{0}-1}-w_{i}^{{}^{\prime}t_{0}-1}\|_{2}.$

Thus, we always have
$\|w_{i}^{t_{0}}-w_{i}^{{}^{\prime}t_{0}}\|_{2}\leq\|w_{i}^{t_{0}-1}-w_{i}^{{}^{\prime}t_{0}-1}\|_{2}+2\eta_{i}\gamma$.

When $t_{0}=t+1$ by using a similar proof as in [41] ans since $f_{\beta}$ is
$2B$-Lipschitz we have
$\|w_{i}^{t_{0}-1}-\eta_{i}{\nabla}f_{\beta}(w_{i}^{t_{0}-1};x_{i}^{t_{0}-1},y_{i}^{t_{0}-1})-w_{i}^{{}^{\prime}t_{0}-1}+\eta_{i}{\nabla}f_{\beta}(w_{i}^{t_{0}-1};x_{i}^{{}^{\prime}t_{0}-1},y_{i}^{{}^{\prime}t_{0}-1})\|_{2}\leq
4B\eta_{i}$. Thus we have $\|w_{i}^{t+1}-w_{i}^{{}^{\prime}t+1}\|_{2}\leq
4B\eta_{i}+2\gamma\eta_{i}$.

In total we have $\|w_{i}^{t_{0}}-w_{i}^{{}^{\prime}t_{0}}\|_{2}\leq
4B\eta_{i}+2\eta_{i}\gamma t_{0}$. And thus
$\|\bar{w}_{i}-\bar{w}^{\prime}_{i}\|\leq 4B\eta_{i}+\gamma\eta_{i}(n+1)\leq
5B\eta_{i}$. Thus, the $\ell_{2}$-norm sensitivity is $5B\eta_{i}$. By the
Gaussian mechanism we have the algorithm is $(\epsilon,\delta)$-DP.

Next we will focus on the utility. We first show the following lemma which
follows [9] for self-completeness:

######  Lemma 10.

Let $\alpha,\eta$ be as in Theorem 3. Then for each phase $i$, we have

$\displaystyle\mathbb{E}[F_{\beta}(\bar{w}_{i})-F_{\beta}(\bar{w}_{i-1})]\leq\frac{\mathbb{E}[\|w_{i-1}-\bar{w}_{i-1}\|_{V}^{2}]}{2\eta_{i}n_{i}}+\frac{5\eta_{i}B^{2}}{2}+\frac{(B\mathbb{E}[\|w_{i-1}-\bar{w}_{i-1}\|_{V}]+1)}{\sqrt{n}\log
n}.$

###### Proof.

For simplicity we denote $F_{\beta}(w)=\mathbb{E}[f_{\beta}(w;x,y)]$ omit the
subscript $i$. Denote $\Phi^{t}=\|w^{t}-\bar{w}_{i-1}\|_{V}^{2}$, we have

$\displaystyle\Phi^{t+1}=\Phi^{t}-2\eta\langle\tilde{\nabla}f_{\beta}(w^{t};x^{t},y^{t}),w^{t}-\bar{w}_{i-1}\rangle_{V}+\eta^{2}\|\tilde{\nabla}f_{\beta}(w^{t};x^{t},y^{t})\|_{V}^{2}$
$\displaystyle\leq\Phi^{t}-2\eta\langle\nabla
f_{\beta}(w^{t};x^{t},y^{t}),w^{t}-\bar{w}_{i-1}\rangle+2\eta\gamma\|w^{t}-\bar{w}_{i-1}\|_{V}+\eta^{2}(\gamma^{2}+4B^{2}),$

where the first inequality is due to the fact that $\nabla
f_{\beta}(w^{t};x^{t},y^{t})$ in the span of $V$. Thus,

$\langle\nabla
f_{\beta}(w^{t};x^{t},y^{t}),w^{t}-\bar{w}_{i-1}\rangle\leq\frac{\Phi^{t}-\Phi^{t+1}}{2\eta}+\gamma\|w^{t}-\bar{w}_{i-1}\|_{V}+\frac{\eta}{2}(\gamma^{2}+4B^{2}).$

Taking the expectation w.r.t all randomness we have

$\langle\nabla
F_{\beta}(w^{t}),w^{t}-\bar{w}_{i-1}\rangle\leq\frac{\mathbb{E}[\Phi^{t}-\Phi^{t+1}]}{2\eta}+\gamma\mathbb{E}\|w^{t}-\bar{w}_{i-1}\|_{V}+\frac{\eta}{2}(\gamma^{2}+4B^{2}).$

By the convexity of $F_{\beta}$ we have $\langle\nabla
F_{\beta}(w^{t}),w^{t}-\bar{w}_{i-1}\rangle\geq\mathbb{E}[F_{\beta}(w^{t})-F_{\beta}(\bar{w}_{i-1})].$
Thus, we have

$\mathbb{E}[F_{\beta}(\bar{w}_{i})-F_{\beta}(\bar{w}_{i-1})]\leq\frac{\mathbb{E}[\Phi^{1}]}{2\eta
n_{i}}+\frac{\gamma}{n_{i}}\mathbb{E}[\sum_{t=1}^{n_{i}}\|w^{t}-\bar{w}_{i-1}\|_{V}]+\frac{\eta}{2}(\gamma^{2}+4B^{2}).$

Next we bound the term $\sum_{t=1}^{n_{i}}\|w^{t}-\bar{w}_{i-1}\|_{V}$:

$\displaystyle\|w^{t}-\bar{w}_{i-1}\|_{V}\leq\|w^{t-1}-\bar{w}_{i-1}\|_{V}+\|w^{t}-w^{t-1}\|_{V}$
$\displaystyle\leq\cdots\leq\|w_{i-1}-\bar{w}_{i-1}\|_{V}+\sum_{j=2}^{t}\|w^{j}-w^{j-1}\|_{V}$
$\displaystyle\leq\sqrt{\Phi^{1}}+\eta(t-1)(2B+\gamma).$

In total we have

$\displaystyle\mathbb{E}[F_{\beta}(\bar{w}_{i})-F_{\beta}(\bar{w}_{i-1})]$
$\displaystyle\leq\frac{\mathbb{E}[\Phi^{1}]}{2\eta
n_{i}}+\alpha\mathbb{E}[\sqrt{\Phi^{1}}+\eta
n_{i}(2B+\gamma)]+\frac{\eta}{2}(\gamma^{2}+4B^{2})$
$\displaystyle\leq\frac{\mathbb{E}[\Phi^{1}]}{2\eta n_{i}}+\frac{5\eta
B^{2}}{2}+\gamma(\mathbb{E}[\sqrt{\Phi^{1}}]+3n_{i}\eta B),$

where the last step follows from the fact that $\gamma=\frac{B}{n\log n}\leq
B$. Since we have $\eta\leq\frac{W}{6B\sqrt{n}}$, we have $3n_{i}\eta
B\leq\sqrt{n}$. In total we have

$\displaystyle\mathbb{E}[F_{\beta}(\bar{w}_{i})-F_{\beta}(\bar{w}_{i-1})]\leq\frac{\mathbb{E}[\Phi^{1}]}{2\eta
n_{i}}+\frac{5\eta
B^{2}}{2}+\frac{(B\mathbb{E}[\sqrt{\Phi^{1}}]+1)}{\sqrt{n}\log n}.$

∎

Now we back to the proof of Theorem 3. Denote $\bar{w}_{0}=w_{\beta}^{*}$ and
$\zeta_{0}=w_{0}-w^{*}$ and by Lemma 10 we have

$\displaystyle\mathbb{E}[F_{\beta}({w}_{k})-F_{\beta}(w^{*})]$
$\displaystyle=\sum_{i=1}^{k}\mathbb{E}[F_{\beta}(\bar{w}_{k})-F_{\beta}(\bar{w}_{k-1})]+\mathbb{E}[F_{\beta}({w}_{k})-F_{\beta}(\bar{w}_{k})]$
$\displaystyle\leq\sum_{i=1}^{k}\frac{\mathbb{E}[\|w_{i-1}-\bar{w}_{i-1}\|_{V}^{2}]}{2\eta_{i}n_{i}}+\frac{5\eta_{i}B^{2}}{2}+\frac{(B\mathbb{E}[\|w_{i-1}-\bar{w}_{i-1}\|_{V}]+1)}{\sqrt{n}\log
n}$
$\displaystyle\qquad+\mathbb{E}[F_{\beta}({w}_{k})-F_{\beta}(\bar{w}_{k})]$
$\displaystyle=\sum_{i=1}^{k}\frac{\mathbb{E}[\|\zeta_{i-1}\|_{V}^{2}]}{2\eta_{i}n_{i}}+\frac{5\eta_{i}B^{2}}{2}+\frac{B\mathbb{E}[\|\zeta_{i-1}\|_{V}]+1}{\sqrt{n}\log
n}+\mathbb{E}[F_{\beta}({w}_{k})-F_{\beta}(\bar{w}_{k})].$

Note that for all $2\leq i\leq k$, we have

$\mathbb{E}\|\zeta_{i-1}\|_{V}^{2}=\mathbb{E}_{V}[\mathbb{E}_{\zeta_{i-1}}[\zeta^{T}_{i-1}VV^{T}\zeta_{i-1}|V]]\leq\theta\tau_{i-1}^{2}.$

And when $i=1$,
$\mathbb{E}\|\zeta_{i-1}\|_{V}^{2}\leq\|w_{0}-w_{\ell}^{*}\|_{2}^{2}$. For
$\mathbb{E}[F_{\beta}({w}_{k})-F_{\beta}(\bar{w}_{k})]$ we have

$\mathbb{E}[F_{\beta}({w}_{k})-F_{\beta}(\bar{w}_{k})]\leq
2BR\mathbb{E}[\langle\zeta_{k},x\rangle]\leq 2B\tau_{k}\leq
O(\frac{WBR\sqrt{\log\frac{1}{\delta}}}{\epsilon n^{\frac{5}{2}}}).$

In total we have

$\displaystyle\mathbb{E}[F_{\beta}({w}_{k})-F_{\beta}(w^{*})]$
$\displaystyle\leq\sum_{i=1}^{k}\frac{\mathbb{E}[\|\zeta_{i-1}\|_{V}^{2}]}{2\eta_{i}n_{i}}+\frac{5\eta_{i}B^{2}}{2}+\frac{B\mathbb{E}[\|\zeta_{i-1}\|_{V}]+1}{\sqrt{n}\log
n}+\mathbb{E}[F_{\beta}({w}_{k})-F_{\beta}(\bar{w}_{k})]$ $\displaystyle\leq
O(B(\|w_{0}-w^{*}\|_{2}^{2}+1)(\frac{\sqrt{\theta\log\frac{1}{\delta}}}{n\epsilon}+\frac{1}{\sqrt{n}}))$
$\displaystyle\qquad+\sum_{i=2}^{k}[\frac{\theta\tau_{i-1}^{2}}{2\eta_{i}n_{i}}+\frac{5\eta_{i}B^{2}}{2}+\frac{B(\sqrt{\theta}\tau_{i-1}+1)}{\sqrt{n}\log
n}]+O(\frac{WB\sqrt{\log\frac{1}{\delta}}}{\epsilon n^{\frac{5}{2}}})$
$\displaystyle\leq
O(W^{2}B(\frac{\sqrt{\theta\log\frac{1}{\delta}}}{n\epsilon}+\frac{1}{\sqrt{n}})).$

Thus, by Lemma 4 we have

$\displaystyle\mathbb{E}[L_{\mathcal{P}}]({w}_{k})-L_{\mathcal{P}}(w^{*})\leq
2G(\mathbb{E}L^{\ell}_{\mathcal{P}}(w)-L^{\ell}_{\mathcal{P}}(w^{*}))$
$\displaystyle\leq
O(GW^{2}B(\frac{\sqrt{\theta\log\frac{1}{\delta}}}{n\epsilon}+\frac{1}{\sqrt{n}})+\frac{GB^{2}}{\beta}).$

Take $\beta=O(\frac{\sqrt{n}B}{W^{2}})$ we can get the result. ∎

###### Proof of Theorem 4.

The proof has the same idea of the proof in Theorem 2. And here we use the
proof of Theorem 3 instead of Theorem 1. For simplicity we omit it here. ∎

###### Proof of Theorem 5.

First we will show the $(\epsilon,\delta)$-DP guarantee. Similar to the proof
of Theorem 2 we know that when $k=O(\frac{\log n/\delta}{\alpha^{2}})$ with
some $\alpha\leq 1$ we have with probability at least $1-\frac{\delta}{2}$,
$\|\Phi x_{i}\|_{2}\leq(1+\alpha)\|x_{i}\|_{2}\leq 2$ and $\|\Phi
w^{*}\|_{2}\leq 2W$. Under this event we can easily calculate the
$\ell_{2}$-norm sensitivity of
$\frac{1}{n}\sum_{i=1}^{n}(\max\\{0,\langle\tilde{w}_{t},\Phi
x_{i}\rangle\\}-y_{i})\Phi x_{i}$, which is $\frac{4(4W+B)}{n}$. Thus the line
2-4 is $(\epsilon,\frac{\delta}{2})$-DP and the whole algorithm is
$(\epsilon,\delta)$-DP.

Next we will show the utility, note that line 2-4 is equivalent to using the
projected gradient descent to $L^{\ell}(w;\tilde{D})$ with
$\ell(w;x,y)=\int_{0}^{\langle w,x\rangle}(\sigma(z)-y)dz.$ Then denote
$\mathcal{P}^{\prime}=\Phi\mathcal{P}$ and
$\tilde{w}=\frac{\sum_{t=1}^{T}\tilde{w}_{t}}{T}$ we have

$\displaystyle\mathbb{E}L^{\ell}_{\mathcal{P}}(\bar{w})-L^{\ell}_{\mathcal{P}}(w^{*})=[\mathbb{E}L^{\ell}_{\mathcal{P}^{\prime}}(\tilde{w}))-\mathbb{E}L^{\ell}(\Phi
w^{*},\tilde{D})]+[\mathbb{E}L^{\ell}(\Phi
w^{*},\tilde{D})]-L^{\ell}_{\mathcal{P}}(w^{*})]$
$\displaystyle\leq[L^{\ell}_{\mathcal{P}^{\prime}}(\tilde{w}))-\min_{w\in\tilde{W}}L^{\ell}_{\mathcal{P}^{\prime}}(w)]+[L^{\ell}_{\mathcal{P}^{\prime}}(\tilde{w}_{T+1}))-L^{\ell}_{\mathcal{P}}(w^{*})].$

For the second term due to Lemma 3 we known $w^{*}$ is the global minimizer of
$L^{\ell}_{\mathcal{P}}(w)$ and thus $\nabla L^{\ell}_{\mathcal{P}}(w^{*})=0$,
moreover we can see $\ell$ is 1-smooth, thus we have

$\displaystyle\mathbb{E}L^{\ell}(\Phi
w^{*},\tilde{D})-L^{\ell}_{\mathcal{P}}(w^{*})\leq\frac{1}{2}\mathbb{E}[|\langle\Phi
w^{*},\Phi x\rangle-\langle w^{*},x\rangle|^{2}]$ $\displaystyle\leq
O(W\alpha^{2})=O(\frac{W{\log n/\delta}}{{m}}).$

For the first term, we have

$\displaystyle\mathbb{E}L^{\ell}_{\mathcal{P}^{\prime}}(\tilde{w}))-\mathbb{E}L^{\ell}(\Phi
w^{*},\tilde{D})=\mathbb{E}L^{\ell}_{\mathcal{P}^{\prime}}(\tilde{w})-\mathbb{E}L^{\ell}_{\mathcal{P^{\prime}}}(\Phi
w^{*})\leq\mathbb{E}L^{\ell}_{\mathcal{P}^{\prime}}(\tilde{w}))-\min_{w\in\tilde{W}}L^{\ell}_{\mathcal{P}^{\prime}}(w)$
$\displaystyle=\mathbb{E}L^{\ell}_{\mathcal{P}^{\prime}}(\tilde{w}))-\mathbb{E}L^{\ell}((\tilde{w},\tilde{D})+\mathbb{E}L^{\ell}((\tilde{w},\tilde{D})-\mathbb{E}L^{\ell}((\tilde{w}^{*},\tilde{D})$

Since $\ell(w;\Phi x_{i},y_{i})$ is a $2(4W+B)$-Lipschitz and $4$-smooth
function and the algorithm is just the PGD for the empirical risk function.
The first term, which is the generalization error is bounded by Lipschitz
times the stability i.e., $O((W+B)^{2}\frac{\eta T}{n})$. The second term is
bounded by the excess empirical risk, we have

$\displaystyle\mathbb{E}[\|\tilde{w}_{t+1}-\tilde{w}^{*}\|_{2}^{2}]\leq\mathbb{E}\|\tilde{w}_{t}-\tilde{w}^{*}-\eta(\nabla
L^{\ell}(\tilde{w}_{t},\tilde{D})+\eta_{t})\|_{2}^{2}$
$\displaystyle\leq\mathbb{E}\|\tilde{w}_{t}-\tilde{w}^{*}\|_{2}^{2}+\eta^{2}\|\nabla
L^{\ell}(\tilde{w}_{t},\tilde{D})\|_{2}^{2}+\eta^{2}\sigma^{2}m-2\eta(L^{\ell}(\tilde{w}_{t},\tilde{D})-L^{\ell}(\tilde{w}^{*},\tilde{D}))$
$\displaystyle\leq\mathbb{E}\|\tilde{w}_{t}-\tilde{w}^{*}\|_{2}^{2}+4\eta^{2}(4W+B)^{2}+\eta^{2}\sigma^{2}m-2\eta(L^{\ell}(\tilde{w}_{t},\tilde{D})-L^{\ell}(\tilde{w}^{*},\tilde{D}))$

Thus, taking the sum for $t=1,\cdots,T$ we have

$L^{\ell}(\tilde{w},\tilde{D})-L^{\ell}(\tilde{w}^{*},\tilde{D})\leq\frac{\mathbb{E}\|\tilde{w}_{1}-\tilde{w}^{*}\|_{2}^{2}}{2\eta
T}+4\eta(4W+B)^{2}+O(\frac{\eta(W+B)^{2}mT\log(1/\delta)}{n^{2}\epsilon^{2}}).$

In total we have

$\mathbb{E}L^{\ell}_{\mathcal{P}^{\prime}}(\tilde{w}))-\mathbb{E}L^{\ell}(\Phi
w^{*},\tilde{D})\leq O(\frac{W^{2}}{\eta
T}+\frac{\eta(W+B)^{2}Tm\log\frac{1}{\delta}}{n^{2}\epsilon^{2}}+(W+B)^{2}\frac{\eta
GT}{n}+\eta(W+B)^{2}).$

Note that the previous bound only holds when $\|\Phi
x_{i}\|\leq(1+\frac{\log\sqrt{n/\delta}}{m})$ which holds with probability at
least $1-\delta$. Thus we can use the same argument as in the Proof of Lemma 8
in [16] to transform the above result to a result of the expectation w.r.t
$\Phi$ with an additional logarithmic factor. Thus we have

$\mathbb{E}L^{\ell}_{\mathcal{P}}(w_{T+1})-L^{\ell}_{\mathcal{P}}(w^{*})\leq\tilde{O}(\frac{W^{2}}{\eta
T}+\frac{\eta(W+B)^{2}Tm\log\frac{1}{\delta}}{n^{2}\epsilon^{2}}+(W+B)^{2}\frac{\eta
T}{n}+\frac{W{\log n/\delta}}{{m}}+\eta(W+B)^{2}).$

Thus, when take
$\eta=\frac{W}{\sqrt{T}\max\\{(W+B),\frac{(W+B)\sqrt{mT\log(1/\delta)}}{n\epsilon}\\}}\leq\frac{W}{(W+B)\sqrt{T}}\leq\frac{1}{2}$
and $T=O(\min\\{n,\frac{n^{2}\epsilon^{2}}{m\log 1/\delta}\\})$ we have

$\mathbb{E}L^{\ell}_{\mathcal{P}}(w_{T+1})-L^{\ell}_{\mathcal{P}}(w^{*})\leq
O(\frac{W(W+B)}{\sqrt{n}}+\frac{W(W+B)\sqrt{m\log
1/\delta}}{n\epsilon}+\frac{W{\log n/\delta}}{{m}}).$

Take $m=O((n\epsilon)^{\frac{2}{3}}\log n/\delta)$ we can get the result. ∎

###### Proof of Theorem 6.

We first show the proof of privacy. Note that since each iteration we use one
data $D_{i}$. Thus, it is sufficient to show the algorithm is
$(\epsilon,\delta)$-DP in the $i$-th iteration with fixed $w_{i-1}$. This is
true since the $\ell_{2}$-norm sensitivity of $\nabla L^{\ell}(w_{i-1};D_{i})$
is $\frac{\sqrt{d}\|w_{i-1}\|_{2}+B}{m}$ based on our assumption.

Next we will focus on the utility. By the concentration property of Gaussian
distribution we know that with probability at least $1-\zeta$, we have
$\|\zeta_{i-1}\|_{2}^{2}\leq
O(d\frac{(\sqrt{d}\|w_{i-1}\|_{2}+B)^{2}\log\frac{1}{\zeta}\log\frac{1}{\delta}}{m^{2}\epsilon^{2}})$.
Thus, with probability at least $1-\zeta$, $\|\zeta_{i-1}\|_{2}^{2}\leq
O(d\frac{(\sqrt{d}\|w_{i-1}\|_{2}+B)^{2}\log\frac{T}{\zeta}\log\frac{1}{\delta}}{m^{2}\epsilon^{2}})$
for all $i=1,\cdots,T$. Below we will always assume this event holds.

Before our proof we first recall the following lemmas:

######  Lemma 11 (Corollary 2.4 of [26]).

If $\mathcal{P}_{\mathcal{X}}$ is isotropic, then for any vector $w$, the
distance between $\chi_{\mathcal{P}}^{\sigma_{w}}$ and $\chi_{\mathcal{P}}$ is
bounded by $\sqrt{L_{\mathcal{P}}(w)}$, i.e.,
$\|\chi_{\mathcal{P}}^{\sigma_{w}}-\chi_{\mathcal{P}}\|_{2}\leq\sqrt{L_{\mathcal{P}}(w)}$.

######  Lemma 12 (Lemma 4.2 in [26]).

Under Assumption 2 , we have $\mathbb{E}_{\mathcal{P}}[(\sigma(\langle
w,x\rangle)-\sigma(\langle
w^{*},x\rangle))^{2}]\leq\mu(\|\chi_{\mathcal{P}}^{\sigma_{w}}-\chi_{\mathcal{P}}^{\sigma_{w^{*}}}\|^{2}_{2})$
with some constant $\mu$.

Thus in total we have

$\displaystyle\mathbb{E}_{\mathcal{P}}[(\sigma(\langle
w,x\rangle)-\sigma(\langle w^{*},x\rangle))^{2}]$
$\displaystyle\leq\mu(\|\chi_{\mathcal{P}}^{\sigma_{w}}-\chi_{\mathcal{P}}^{\sigma_{w^{*}}}\|^{2}_{2})$
$\displaystyle\leq
2\mu(\|\chi_{\mathcal{P}}^{\sigma_{w}}-\chi_{\mathcal{P}}\|_{2}^{2}+\|\chi_{\mathcal{P}}^{\sigma_{w^{*}}}-\chi_{\mathcal{P}}\|_{2}^{2})$
$\displaystyle\leq 2\mu L_{\mathcal{P}}(w^{*})+2\mu\|\nabla
L^{\ell}_{\mathcal{P}}(w)\|_{2}.$ (11)

On the other side by the triangle inequality we have

$L_{\mathcal{P}}(w)\leq
2L_{\mathcal{P}}(w^{*})+2\mathbb{E}_{\mathcal{P}}[(\sigma(\langle
w,x\rangle)-\sigma(\langle w^{*},x\rangle))^{2}].$

In total we have

$L_{\mathcal{P}}(w)\leq 2(1+2\mu)L_{\mathcal{P}}(w^{*})+4\mu\|\nabla
L^{\ell}_{\mathcal{P}}(w)\|_{2}.$

In the following we will bound the term of $\|\nabla
L^{\ell}_{\mathcal{P}}(w_{T})\|_{2}$ in Algorithm 8. We recall the following
lemmas in [26].

######  Lemma 13.

Consider a ball $B(0,r)$ with radius $r$, under Assumption 2, if $\sigma$ is
the sigmod link function. Then as long as

$n\geq\tilde{\Omega}(\frac{d}{\alpha^{2}}\log^{4}\frac{d}{\zeta}(r+1)^{2}),$

we have for fixed $w\in B(0,r)$

$\|\frac{1}{n}\sum_{i=1}^{n}(\sigma(\langle
w,x_{i}\rangle)-y_{i})x_{i}\|_{2}\leq\alpha.$

######  Lemma 14.

As long as $\alpha\leq\|w_{\ell}^{*}\|_{2}$, $\zeta\geq\exp(-O(\sqrt{d}))$ and

$n\geq\tilde{\Omega}(\frac{d}{\mu^{2}}\log\frac{\|w_{\ell}^{*}\|_{2}+1}{\mu\zeta}),$

with probability at least $1-\zeta$ we have for all $w$ such that
$\frac{\alpha}{3}\leq\|w-w_{\ell}^{*}\|_{2}\leq 2\|w_{\ell}^{*}\|_{2}$,

$\langle\nabla L^{\ell}(w;D)-\nabla
L^{\ell}(w_{\ell}^{*};D),w-w_{\ell}^{*}\rangle\geq\tau\|w-w_{\ell}^{*}\|_{2}^{2}+\beta\|\nabla
L^{\ell}(w;D)-\nabla L^{\ell}(w_{\ell}^{*};D)\|_{2}^{2}$

with $\tau=\frac{\mu}{3}$ and $\beta=\frac{1}{8}$.

Now lets back to our proof, we will first show that
$\|w_{i}-w^{*}_{\ell}\|_{2}\leq 2\|w^{*}_{\ell}\|_{2}$ for all $i=0,\cdots,T$
when $n$ is large enough:

######  Lemma 15.

Suppose the event of $\|\zeta_{i-1}\|_{2}^{2}\leq
O(\frac{(\sqrt{d}\|w_{i-1}\|_{2}+B)^{2}\log\frac{T}{\zeta}\log\frac{1}{\delta}}{m^{2}\epsilon^{2}})$
for all $i=1,\cdots,T$ holds, then we have $\|w_{i}-w^{*}_{\ell}\|_{2}\leq
2\|w^{*}_{\ell}\|_{2}$ for all $i=0,\cdots,T$ when
$m\geq\tilde{\Omega}(\sqrt{\frac{1}{\tau}(4\eta+\frac{1}{\tau})}\frac{(\sqrt{d}\|w^{*}_{\ell}\|_{2}+B)\sqrt{\log
1/\delta\log 1/\zeta}}{\epsilon\alpha})$

###### Proof.

We will show it by using induction. This is true for $i=0$ since $w_{0}=0$.
Suppose this is true for some $i-1$, then our goal is to show
$\|w_{i}-w^{*}\|_{2}\leq 2\|w^{*}_{\ell}\|_{2}$. We consider two cases.

The first case is
$2\|w^{*}_{\ell}\|_{2}\geq\|w_{i-1}-w^{*}_{\ell}\|\geq\frac{\alpha}{3}$. Then
we have

$\displaystyle\|w_{i}-w_{\ell}^{*}\|_{2}^{2}=\|w_{i-1}-w_{\ell}^{*}\|_{2}^{2}-\eta\langle\nabla
L^{\ell}(w_{i-1};D_{i})+\zeta_{i-1},w_{i-1}-w_{\ell}^{*}\rangle+\eta^{2}\|\nabla
L^{\ell}(w_{i-1};D_{i})+\zeta_{i-1}\|_{2}^{2}$
$\displaystyle=\|w_{i-1}-w_{\ell}^{*}\|_{2}^{2}-\eta\langle\nabla
L^{\ell}(w_{i-1};D_{i})-\nabla
L^{\ell}(w_{\ell}^{*};D_{i}),w_{i-1}-w_{\ell}^{*}\rangle$
$\displaystyle\qquad+\eta^{2}\|\nabla
L^{\ell}(w_{i-1};D_{i})+\zeta_{i-1}\|_{2}^{2}-\eta\langle\nabla
L^{\ell}(w_{\ell}^{*};D_{i})+\zeta_{i-1},w_{i-1}-w_{\ell}^{*}\rangle$
$\displaystyle\leq(1-\tau\eta)\|w_{i-1}-w_{\ell}^{*}\|_{2}^{2}-\eta\beta\|\nabla
L^{\ell}(w_{i-1};D_{i})-\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}^{2}+2\eta^{2}\|\nabla
L^{\ell}(w_{i-1};D_{i})-\nabla L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}^{2}$
$\displaystyle\qquad+2\eta^{2}\|\nabla
L^{\ell}(w_{\ell}^{*};D_{i})+\zeta_{i-1}\|_{2}^{2}-\eta\langle\nabla
L^{\ell}(w_{\ell}^{*};D_{i})+\zeta_{i-1},w_{i-1}-w_{\ell}^{*}\rangle$
$\displaystyle\leq(1-\tau\eta)\|w_{i-1}-w_{\ell}^{*}\|_{2}^{2}-\eta(\beta-2\eta)\|\nabla
L^{\ell}(w_{i-1};D_{i})-\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}^{2}+4\eta^{2}\|\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}^{2}+4\eta^{2}\|\zeta_{i-1}\|_{2}^{2}$
$\displaystyle\qquad+\frac{\tau\eta}{2}\|w_{i-1}-w_{\ell}^{*}\|_{2}^{2}+\frac{\eta}{\tau}\|\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}^{2}+\frac{\eta}{\tau}\|\zeta_{i-1}\|_{2}^{2}$
$\displaystyle\leq(1-\frac{\tau\eta}{2})\|w_{i-1}-w_{\ell}^{*}\|_{2}^{2}+\eta(4\eta+\frac{1}{\tau})\|\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}^{2}+\eta(4\eta+\frac{1}{\tau})\|\zeta_{i-1}\|_{2}^{2}$
(12)
$\displaystyle=(1-\frac{\tau\eta}{2})\|w_{i-1}-w_{\ell}^{*}\|_{2}^{2}+\eta(4\eta+\frac{1}{\tau})\|\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}^{2}+\tilde{O}(d\eta(4\eta+\frac{1}{\tau})\frac{(\sqrt{d}\|w_{i-1}\|_{2}+B)^{2}\log(1/\delta)\log
1/\zeta}{m^{2}\epsilon^{2}})$
$\displaystyle\leq(1-\frac{\tau\eta}{2}+\tilde{O}(\eta(4\eta+\frac{1}{\tau})\frac{d^{2}\log(1/\delta)\log
1/\zeta}{m^{2}\epsilon^{2}}))\|w_{i-1}-w_{\ell}^{*}\|_{2}^{2}+\eta(4\eta+\frac{1}{\tau})\|\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}^{2}$
$\displaystyle\qquad+\tilde{O}(d\eta(4\eta+\frac{1}{\tau})\frac{(\sqrt{d}\|w_{\ell}^{*}\|_{2}+B)^{2}\log(1/\delta)\log
1/\zeta}{m^{2}\epsilon^{2}}),$ (13)

where the first inequality is due to Lemma 14. Thus, we can see that when

$m\geq\tilde{\Omega}(\sqrt{\frac{\eta}{\tau}+\frac{1}{\tau^{2}}}\frac{d\sqrt{\log
1/\delta\log 1/\zeta}}{\epsilon}),$

take $\alpha=\sqrt{\frac{\tau}{9(4\tau\beta+1)}\alpha^{2}}$ in Lemma 13 and
when
$m\geq\tilde{\Omega}(\sqrt{d\frac{1}{\tau}(4\eta+\frac{1}{\tau})}\frac{(\sqrt{d}\|w^{*}_{\ell}\|_{2}+B)\sqrt{\log
1/\delta\log 1/\zeta}}{\epsilon\alpha})$. Then we have

$\|w_{i}-w_{\ell}^{*}\|_{2}^{2}\leq(1-\frac{\tau\eta}{4})\|w_{i-1}-w_{\ell}^{*}\|_{2}^{2}+\frac{2\alpha^{2}}{9}\leq
4\|w_{\ell}^{*}\|_{2}^{2}.$

We then consider case 2 where
$\|w_{i-1}-w_{\ell}^{*}\|_{2}\leq\frac{\alpha}{3}$. Then we have

$\displaystyle\|w_{i}-w^{*}_{\ell}\|_{2}=\|w_{i-1}-w_{\ell}^{*}-\eta(\nabla
L^{\ell}(w_{i-1};D_{i})+\zeta_{i-1}\|_{2}$
$\displaystyle\leq\|w_{i-1}-w_{\ell}^{*}-\eta(\nabla
L^{\ell}(w_{i-1};D_{i})-\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}+\eta\|\zeta_{i-1}\|_{2}+\eta\|\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}$
$\displaystyle\leq\|w_{i-1}-w_{\ell}^{*}\|_{2}+\eta\|\zeta_{i-1}\|_{2}+\eta\|\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}\leq\alpha\leq\|w_{\ell}^{*}\|_{2},$

where the second inequality is due to the convexity of the surrogate loss
$\ell$ such that $\langle\nabla L^{\ell}(w_{i-1};D_{i})-\nabla
L^{\ell}(w_{\ell}^{*};D_{i}),w_{i-1}-w_{\ell}^{*}\rangle\geq 0$. Thus we can
see in both cases we have $\|w_{i}-w^{*}_{\ell}\|_{2}\leq
2\|w_{\ell}^{*}\|_{2}$. Thus we complete the proof. ∎

Next we will proof the main theorem.

Suppose there exists a $\tilde{t}$ such that for $i\leq\tilde{t}$, we have
$\|w_{i-1}-w_{\ell}^{*}\|_{2}\geq\frac{\alpha}{3}$. Now consider in the $i$-th
iteration where $i\leq\tilde{t}$, if
$\|w_{i-1}-w_{\ell}^{*}\|_{2}\leq\|w_{\ell}^{*}\|_{2}$. Then

$\displaystyle\|w_{i}-w_{\ell}^{*}\|_{2}^{2}=\|w_{i-1}-w_{\ell}^{*}\|_{2}^{2}-\eta\langle\nabla
L^{\ell}(w_{i-1};D_{i})+\zeta_{i-1},w_{i-1}-w_{\ell}^{*}\rangle+\eta^{2}\|\nabla
L^{\ell}(w_{i-1};D_{i})+\zeta_{i-1}\|_{2}^{2}$
$\displaystyle=\|w_{i-1}-w_{\ell}^{*}\|_{2}^{2}-\eta\langle\nabla
L^{\ell}(w_{i-1};D_{i})-\nabla
L^{\ell}(w_{\ell}^{*};D),w_{i-1}-w_{\ell}^{*}\rangle$
$\displaystyle+\eta^{2}\|\nabla
L^{\ell}(w_{i-1};D_{i})+\zeta_{i-1}\|_{2}^{2}-\eta\langle\nabla
L^{\ell}(w_{\ell}^{*};D_{i})+\zeta_{i-1},w_{i-1}-w_{\ell}^{*}\rangle$
$\displaystyle\leq(1-\tau\eta)\|w_{i-1}-w_{\ell}^{*}\|_{2}^{2}-\eta\beta\|\nabla
L^{\ell}(w_{i-1};D_{i})-\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}^{2}+2\eta^{2}\|\nabla
L^{\ell}(w_{i-1};D_{i})-\nabla L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}^{2}$
$\displaystyle+2\eta^{2}\|\nabla
L^{\ell}(w_{\ell}^{*};D_{i})+\zeta_{i-1}\|_{2}^{2}-\eta\langle\nabla
L^{\ell}(w_{\ell}^{*};D_{i})+\zeta_{i-1},w_{i-1}-w_{\ell}^{*}\rangle$
$\displaystyle\leq(1-\tau\eta)\|w_{i-1}-w_{\ell}^{*}\|_{2}^{2}-\eta(\beta-2\eta)\|\nabla
L^{\ell}(w_{i-1};D_{i})-\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}^{2}+4\eta^{2}\|\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}^{2}+4\eta^{2}\|\zeta_{i-1}\|_{2}^{2}$
$\displaystyle+\frac{\tau\eta}{2}\|w_{i-1}-w_{\ell}^{*}\|_{2}^{2}+\frac{\eta}{\tau}\|\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}^{2}+\frac{\eta}{\tau}\|\zeta_{i-1}\|_{2}^{2}$
$\displaystyle\leq(1-\frac{\tau\eta}{2})\|w_{i-1}-w_{\ell}^{*}\|_{2}^{2}+\eta(4\eta+\frac{1}{\tau})\|\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}^{2}+\eta(4\eta+\frac{1}{\tau})\|\zeta_{i-1}\|_{2}^{2},$

where the first inequality is due to Lemma 14. Since we have
$\|w_{i-1}-w^{*}\|_{2}\geq\frac{\alpha}{3}$, and take
$\alpha=\sqrt{\frac{\tau^{2}}{9(4\tau\beta+1)}\alpha^{2}}$ in Lemma 13 and
since
$m\geq\tilde{\Omega}(\sqrt{d\frac{1}{\tau}(4\eta+\frac{1}{\tau})}\frac{(B+\sqrt{d}\|w_{\ell}^{*}\|_{2})\sqrt{\log
1/\zeta\log 1/\delta}}{\epsilon\alpha})$ and $\|w_{i-1}\|_{2}\leq
3\|w_{\ell}^{*}\|_{2}$, we have for $i\leq\tilde{t}$

$\displaystyle\|w_{i}-w_{\ell}^{*}\|_{2}^{2}\leq(1-\frac{\tau\eta}{2})^{i}\|w_{0}-w_{\ell}^{*}\|_{2}^{2}+\frac{1}{\tau}(4\eta+\frac{1}{\tau})\frac{\tau^{2}}{9(4\tau\beta+1)}\alpha^{2}+\frac{\alpha^{2}}{9}$
$\displaystyle\leq\|w_{\ell}^{*}\|_{2}^{2}+\frac{2\alpha^{2}}{9}\leq
4\|w_{\ell}^{*}\|_{2}^{2}.$

Thus, we can see that as long as for $i\leq\tilde{t}$,
$\|w_{i}-w^{*}\|_{2}\geq\frac{\alpha}{3}$ and
$\|w_{0}-w_{\ell}^{*}\|\leq\|w_{\ell}^{*}\|_{2}$ (this is true since
$w_{0}=0$) we always have $\|w_{i}-w_{\ell}^{*}\|_{2}\leq
2\|w_{\ell}^{*}\|_{2}$. Thus, we can always use Lemma 14.

Now we consider several cases:

Case 1: If for all $i\leq T$,
$\|w_{i}-w_{\ell}^{*}\|_{2}\geq\frac{\alpha}{3}$. Then by the above inequality
we have

$\|w_{T}-w_{\ell}^{*}\|_{2}^{2}\leq(1-\frac{\tau\eta}{2})^{T}\|w_{0}-w_{\ell}^{*}\|_{2}^{2}+\frac{1}{\tau}(4\eta+\frac{1}{\tau})\frac{\tau^{2}}{9(4\tau\beta+1)}\alpha^{2}+\frac{\alpha^{2}}{9}\\\
\leq(1-\frac{\tau\eta}{2})^{T}\|w_{\ell}^{*}\|_{2}^{2}+\frac{2\alpha^{2}}{9}$

Thus, take
$T=O(\frac{\log(\alpha/\|w_{\ell}^{*}\|_{2})}{\log(1-\frac{\tau\eta)}{2}})=O(\frac{1}{\tau\eta}\log(\|w_{\ell}^{*}\|_{2})$
we have

$\|w_{T}-w^{*}\|_{2}^{2}\leq\frac{2\alpha^{2}}{9}+\frac{2\alpha^{2}}{9}\leq\frac{4\alpha^{2}}{9}.$
(14)

That is $\|w_{T}-w^{*}\|_{2}\leq\frac{2\alpha}{3}$.

Case 2:  If Case 1 does not hold, then if there exist a $\tilde{t}<T$ (we
assume $\tilde{t}$ is the largest one) such that when $i=\tilde{t}$ we have
$\|w_{i}-w_{\ell}^{*}\|_{2}\leq\frac{\alpha}{3}$ and
$\|w_{i}-w_{\ell}^{*}\|_{2}\geq\frac{\alpha}{3}$ for $T\geq i\geq\tilde{t}+1$.
Then

$\displaystyle\|w_{\tilde{t}+1}-w_{\ell}^{*}\|_{2}=\|w_{\tilde{t}}-w_{\ell}^{*}-\eta(\nabla
L^{\ell}(w_{\tilde{t}};D_{i})+\zeta_{\tilde{t}})\|_{2}$
$\displaystyle\leq\|w_{\tilde{t}}-w_{\ell}^{*}-\eta(\nabla
L^{\ell}(w_{\tilde{t}};D_{i})-\nabla
L^{\ell}(w_{\ell}^{*};D_{i}))\|_{2}+\eta\|\zeta_{\tilde{t}}\|_{2}+\eta\|\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}$
$\displaystyle\leq\|w_{\tilde{t}}-w_{\ell}^{*}\|_{2}+\eta\|\zeta_{\tilde{t}}\|_{2}+\eta\|\nabla
L^{\ell}(w_{\ell}^{*};D_{i})\|_{2}\leq\frac{\alpha}{3}+\frac{\alpha}{3}\leq
2\|w_{\ell}^{*}\|_{2},$

where the second inequality is due to the convexity of the surrogate loss
$\ell$ such that $\langle\nabla L^{\ell}(w_{\tilde{t}};D_{i})-\nabla
L^{\ell}(w_{\ell}^{*};D_{i}),w_{\tilde{t}}-w_{\ell}^{*}\rangle\geq 0$. Thus,
we can use the same argument as Case 1 and show that

$\|w_{T}-w_{\ell}^{*}\|^{2}_{2}\leq(1-\frac{\eta\tau}{2})^{T-\tilde{t}-1}\|w_{\tilde{t}+1}-w_{\ell}^{*}\|_{2}^{2}+\frac{2\alpha^{2}}{9}\leq\frac{2}{3}\alpha^{2}.$
(15)

Case 3 If Case 1 and Case 2 do not hold, then that is
$\|w_{T}-w^{*}\|_{2}\leq\frac{\alpha}{3}$.

Thus, in total we must have $\|w_{T}-w_{\ell}^{*}\|_{2}\leq\alpha$ with
probability at least $1-3\zeta$. Note that

$\|\nabla L^{\ell}_{\mathcal{P}}(w_{T})\|_{2}=\|\nabla
L^{\ell}_{\mathcal{P}}(w_{T})-\nabla
L^{\ell}_{\mathcal{P}}(w_{\ell}^{*})\|_{2}\leq\|w_{T}-w_{\ell}^{*}\|_{2}\leq\alpha$.
Thus

$L_{\mathcal{P}}(w)\leq 2(1+2\mu)L_{\mathcal{P}}(w^{*})+4\mu\alpha.$

Take $\alpha=\frac{\alpha}{4\mu}$ we can get the result. ∎

###### Proof of Lemma 7.

We denote

$\tilde{\ell}(w;x,y)=\int_{0}^{\langle
w,\psi(x)\rangle+\phi(x)}(\sigma(z)-y)dz.$

For any fixed $x$ we have

$\displaystyle\mathbb{E}_{y}[\tilde{\ell}(w;x,y)]-\mathbb{E}_{y}[\tilde{\ell}(w^{*};x,y)]=\mathbb{E}_{y}\int_{\langle
w^{*},\psi(x)\rangle+\phi(x)}^{\langle
w,\psi(x)\rangle\phi(x)}(\sigma(z)-y)dz$ $\displaystyle=\int_{\langle
w^{*},\psi(x)\rangle+\phi(x)}^{\langle
w,\psi(x)\rangle\phi(x)}(\sigma(z)-\mathbb{E}_{y}y)dz$
$\displaystyle=\int_{\langle w^{*},\psi(x)\rangle+\phi(x)}^{\langle
w,\psi(x)\rangle\phi(x)}(\sigma(z)-\sigma(\langle
w^{*},\psi(x)\rangle+\phi(x))))dz$ $\displaystyle=\int_{\langle
w^{*},\psi(x)\rangle+\phi(x)}^{\langle
w,\psi(x)\rangle+\phi(x)}\frac{\sigma^{\prime}(z)(\sigma(z)-\sigma(\langle
w^{*},\psi(x)\rangle+\phi(x)))}{\sigma^{\prime}(z)}dz$
$\displaystyle\geq\frac{1}{2G}(\sigma(\langle
w,\psi(x)\rangle+\phi(x))-\sigma(\langle w^{*},\psi(x)\rangle)+\phi(x))^{2}$
$\displaystyle\geq\frac{1}{2G}[\frac{(\sigma(\langle
w,\psi(x)\rangle)-\sigma(\langle
w^{*},\psi(x)\rangle+\psi(x)))^{2}}{2}-(\sigma(\langle
w,x\rangle+\psi(x))-\sigma(\langle w,x\rangle))^{2}]$
$\displaystyle\geq\frac{1}{2G}[\frac{(\sigma(\langle
w,\psi(x)\rangle)-\sigma(\langle
w^{*},\psi(x)\rangle+\psi(x)))^{2}}{2}-G^{2}M^{2}].$

On the other side we have $|\tilde{\ell}(w;x,y)-{\ell}(w;x,y)|=|\int_{\langle
w,\psi(x)\rangle}^{\langle
w,\psi(x)\rangle+\phi(x)}(\sigma(z)-y)dz|\leq|\phi(x)|\leq M$. In total take
the expectation w.r.t $x$ we have

$L_{\mathcal{P}}(w)-L_{\mathcal{P}}(w^{*})\leq
4G(L^{\ell}_{\mathcal{P}}(w)-L^{\ell}_{\mathcal{P}}(w^{*}))+2G^{2}M^{2}+4GM.$

∎

###### Proof of Theorem 7.

It is sufficient for us to only consider the term of
$L^{\ell}_{\mathcal{P}}(w)-L^{\ell}_{\mathcal{P}}(w^{*})$. We can just use
Theorem 1 to get the bound of
$O(\frac{\sqrt{\theta\log\frac{1}{\delta}}}{n\epsilon}+\frac{1}{\sqrt{n}})$.
For the other term, we can following the proof of Theorem 2. The only
difference is that here we do not have (9) as $w^{*}$ is not the global
minimizer of $L^{\ell}_{\mathcal{P}}(w)$. Thus, by the Lispchitz condition we
have

$\displaystyle\mathbb{E}_{\Phi,\tilde{D}}L^{\ell}(\Phi
w^{*},\tilde{D})-L_{\mathcal{P}}^{\ell}(w^{*})=\mathbb{E}_{\Phi,(x_{i},y_{i})\sim\mathcal{P}}[g^{y_{i}}(\langle\Phi
w^{*},\Phi x_{i}\rangle)-g^{y_{i}}(\langle w^{*},x_{i}\rangle)]$
$\displaystyle\leq 2\mathbb{E}_{\Phi,x}|\langle\Phi w^{*},\Phi
x\rangle-\langle w^{*},x\rangle|={O}(W\frac{\log n/\delta}{\sqrt{m}}).$

Thus, similar to the proof of Theorem 2 in total we have

$\displaystyle
L^{\ell}_{\mathcal{P}}(w)-L^{\ell}_{\mathcal{P}}(w^{*})\leq\tilde{O}(W\frac{1}{\sqrt{m}}+W(\frac{\sqrt{m\log\frac{1}{\delta}}}{n\epsilon}+\frac{1}{\sqrt{n}})).$

Take $m=O(\log(n/\delta)n\epsilon)$ we can get the result. ∎

###### Proof of Theorem 8 and 9 .

We first recall the following two lemmas that the neural networks we
considered can be uniformly approximated.

######  Lemma 16 ([20]).

For $\mathcal{N}_{2}$ with the sigmoid function $\sigma_{1}$ and $G$-Lipschitz
function $\sigma_{2}$, there exists a kernel $\mathcal{K}$ with
$\mathcal{K}(x,x^{\prime})\leq 1$ and feature map
$\psi(x)\in\mathbb{R}^{D_{m}}$ ($D_{m}=1+d+\cdots+d^{m}$ and
$m=O(\log(\frac{1}{\alpha_{0}}))$) such that $\mathcal{N}_{2}$ is
$(\sqrt{k}\alpha_{0},(\frac{\sqrt{k}}{\alpha_{0}})^{C})$-uniformly
approximated by kernel $\mathcal{K}$ with some constant $C>0$ for any
$\alpha_{0}$.

######  Lemma 17 ([20]).

For $\mathcal{N}_{2}$ with the ReLU function $\sigma_{1}$ and $G$-Lipschitz