Differentially Private SGD with Non-Smooth Losses

Introduction

Stochastic gradient descent (SGD) algorithms are widely employed to train a wide range of machine learning (ML) models such as SVM, logistic regression, and deep neural networks. It is an iterative algorithm which replaces the true gradient on the entire training data by a randomized gradient estimated from a random subset (mini-batch) of the available data. As opposed to gradient descent algorithms, this reduces the computational burden at each iteration trading for a lower convergence rate . There is a large amount of work considering the optimization error (convergence analysis) of SGD and its variants in the linear case as well as the general setting of reproducing kernel Hilbert spaces .

At the same time, data collected often contain sensitive information such as individual records from schools and hospitals, financial records for fraud detection, online behavior from social media and genomic data from cancer diagnosis. Modern ML algorithms can explore the fine-grained information about data in order to make a perfect prediction which, however, can lead to privacy leakage . To a large extent, SGD algorithms have become the workhorse behind the remarkable progress of ML and AI. Therefore, it is of pivotal importance for developing privacy-preserving SGD algorithms to protect the privacy of the data. Differential privacy (DP) has emerged as a well-accepted mathematical definition of privacy which ensures that an attacker gets roughly the same information from the dataset regardless of whether an individual is present or not. Its related technologies have been adopted by Google , Apple , Microsoft and the US Census Bureau .

For a randomized algorithm (e.g., SGD) $\mathcal{A}$ to solve the above ERM problem, let $\mathcal{A}(S)$ be the output of algorithm $\mathcal{A}$ based on the dataset $S$. Then, its statistical generalization performance is measured by the excess (population) risk, i.e., the discrepancy between the expected risk $\mathcal{R}(\mathcal{A}(S))$ and the least possible one in $\mathcal{W}$, which is defined by

Our key idea to handle general Hölder smooth losses is to establish the approximate non-expansiveness of the gradient mapping, and the refined boundedness of the iterates of SGD algorithms when domain $\mathcal{W}$ is unbounded. This allows us to show the uniform argument stability of the iterates of SGD algorithms with high probability w.r.t. the internal randomness of the algorithm (not w.r.t. the data $S$), and consequently estimate the generalization error of differentially private SGD with non-smooth losses.

Organization of the Paper. The rest of the paper is organized as follows. The formulation of SGD algorithms and the main results are given in Section 2. We provide the proofs in Section 3 and conclude the paper in Section 4.

Problem Formulation and Main Results

For a randomized learning algorithm $\mathcal{A}:\mathcal{Z}^{n}\rightarrow\mathcal{W}$, let $\mathcal{A}(S)$ denote the model produced by running $\mathcal{A}$ over the training dataset $S$. We say two datasets $S$ and $S^{\prime}$ are neighboring datasets, denoted by $S\simeq S^{\prime}$, if they differ by a single datum. We consider the following high-probabilistic version of the uniform argument stability (UAS), which is an extension of the UAS in expectation .

We say an algorithm $\mathcal{A}$ has $\Delta_{\mathcal{A}}$-UAS with probability at least $1-\gamma$ ($\gamma\in(0,1)$) if

where $\delta_{\mathcal{\mathcal{A}}}(S,S^{\prime}):=\|\mathcal{A}(S)-\mathcal{A}(S^{\prime})\|_{2}.$

We will use UAS to study generalization bounds with high probability. In particular, the following lemma as a straightforward extension of Corollary 8 in establishes the relationship between UAS and generalization errors. The proof is given in the Appendix for completeness.

Then there exists a constant $c>0$ such that for any distribution $\mathcal{D}$ over $\mathcal{Z}$ and any $\gamma\in(0,1)$, there holds

Differential privacy is a de facto standard privacy measure for a randomized algorithm $\mathcal{A}.$

We say a randomized algorithm $\mathcal{A}$ satisfies $(\epsilon,\delta)$-DP if, for any two neighboring datasets $S$ and $S^{\prime}$ and any event $E$ in the output space of $\mathcal{A}$, there holds

In particular, we call it satisfies $\epsilon$-DP if $\delta=0$.

Although the concept of $(\epsilon,\delta)$-DP is widely used in privacy-preserving methods, its composition and subsampling amplification results are relatively loose, which are not suitable for iterative SGD algorithms. Based on the Rényi divergence, the work proposed Rényi differential privacy (RDP) as a relaxation of DP to achieve tighter analysis of composition and amplification mechanisms.

For $\lambda>1$, $\rho>0$, a randomized mechanism $\mathcal{A}$ satisfies $(\lambda,\rho)$-RDP, if, for all neighboring datasets $S$ and $S^{\prime}$, we have

where $P_{\mathcal{A}(S)}(\theta)$ and $P_{\mathcal{A}(S^{\prime})}(\theta)$ are the density of $\mathcal{A}(S)$ and $\mathcal{A}(S^{\prime})$, respectively.

As $\lambda\rightarrow\infty$, RDP reduces to $\epsilon$-DP, i.e., $\mathcal{A}$ satisfies $\epsilon$-DP if and only if D_{\infty}\big{(}\mathcal{A}(S)||\mathcal{A}(S^{\prime})\big{)}\leq\epsilon for any neighboring datasets $S$ and $S^{\prime}$. Our analysis requires the introduction of several lemmas on useful properties of RDP listed below.

First, we introduce the privacy amplification of RDP by uniform subsampling, which is fundamental to establish privacy guarantees of noisy SGD algorithms. In general, a uniform subsampling scheme first draws a subset with size $pn$ uniformly at random with a subsampling rate $p\leq 1$, and then applies a known randomized mechanism to the subset.

The following adaptive composition theorem of RDP establishes the privacy of a composition of several adaptive mechanisms in terms of that of individual mechanisms. We say a sequence of mechanisms $(\mathcal{A}_{1},\ldots,\mathcal{A}_{k})$ are chosen adaptively if $\mathcal{A}_{i}$ can be chosen based on the outputs of the previous mechanisms $\mathcal{A}_{1}(S),\ldots,\mathcal{A}_{i-1}(S)$ for any $i\in[k]$.

If a mechanism $\mathcal{A}$ consists of a sequence of adaptive mechanisms $(\mathcal{A}_{1},\ldots,\mathcal{A}_{k})$ with $\mathcal{A}_{i}$ satisfying $(\lambda,\rho_{i})$-RDP, $i\in[k]$, then $\mathcal{A}$ satisfies $(\lambda,\sum_{i=1}^{k}\rho_{i})$-RDP.

Lemme 4 tells us that the derivation of the privacy guarantee for a composition mechanism is simple and direct. This is the underlying reason that we adopt RDP in our subsequent privacy analysis. The following lemma allows us to further convert RDP back to $(\epsilon,\delta)$-DP.

If a randomized mechanism $\mathcal{A}$ satisfies $(\lambda,\rho)$-RDP, then $\mathcal{A}$ satisfies $(\rho+\log(1/\delta)/(\lambda-1),\delta)$-DP for all $\delta\in(0,1)$.

The following lemma shows that a post-processing procedure always preserves privacy.

Let $\mathcal{A}:\mathcal{Z}^{n}\rightarrow\mathcal{W}_{1}$ satisfy $(\lambda,\rho)$-RDP and $f:\mathcal{W}_{1}\rightarrow\mathcal{W}_{2}$ be an arbitrary function. Then $f\circ\mathcal{A}:\mathcal{Z}^{n}\rightarrow\mathcal{W}_{2}$ satisfies $(\lambda,\rho)$-RDP.

2 Main Results

We begin by stating the key result on the distance between two iterate trajectories produced by SGD on neighboring datasets. Let

where \Delta_{SGD}(\gamma)=\Big{(}e\big{(}c^{2}_{\alpha,2}T\eta^{\frac{2}{1-\alpha}}+4\big{(}M+L(C_{\alpha}T\eta)^{\frac{\alpha}{2}}\big{)}^{2}\eta^{2}\Big{(}1+\frac{T}{n}(1+c_{\gamma,T})\Big{)}\frac{T}{n}(1+c_{\gamma,T})\big{)}\Big{)}^{1/2}.

If $\mathcal{W}\subseteq\mathcal{B}(0,R)$ with $R>0$, then, for any $\gamma\in(0,1)$, there holds

2.2 Differentially Private SGD with Output Perturbation

To examine the excess population risk $\mathcal{R}(\mathbf{w}_{\text{priv}})-\mathcal{R}(\mathbf{w}^{*})$, we use the following error decomposition:

where $\bar{\mathbf{w}}=\frac{1}{T}\sum_{t=1}^{T}\mathbf{w}_{t}$ is the output of non-private SGD. The first term is due to the added noise $\mathbf{b}$, which can be estimated by the Chernoff bound for Gaussian random vectors. The second term is the generalization error of SGD, which can be handled by the stability analysis. The third term is an optimization error and can be controlled by standard techniques in optimization theory. Finally, the last term can be bounded by $\mathcal{O}(1/\sqrt{n})$ by Hoeffding inequality. The proof of Theorem 9 is given in Subsection 3.2.

Now, we turn our attention to the utility guarantee for the case with a bounded domain.

These together with Theorem 8 and Theorem 9 imply the privacy and utility guarantees in the above theorem. The detailed proof is given in Subsection 3.2.

The private SGD algorithm with output perturbation was studied in under both the Lipschitz continuity and the strong smoothness assumption, where the excess population risk for one-pass private SGD (i.e. the total iteration number $T=n$) with a bounded parameter domain was bounded by \mathcal{O}\big{(}(n\epsilon)^{-\frac{1}{2}}(d\log(1/\delta)^{\frac{1}{4}}\big{)}. As a comparison, we show that the same rate (up to a logarithmic factor) \mathcal{O}\big{(}(n\epsilon)^{-\frac{1}{2}}(d\log(1/\delta))^{\frac{1}{4}}\log^{\frac{1}{2}}(n/\delta)\big{)} can be achieved for general $\alpha$-Hölder smooth losses by taking $T=\mathcal{O}(n^{2-\alpha\over 1+\alpha}+n).$ Our results extend the output perturbation for private SGD algorithms to a more general class of non-smooth losses.

2.3 Differentially Private SGD with Gradient Perturbation

An alternative approach to achieve $(\epsilon,\delta)$-DP is gradient perturbation, i.e., adding Gaussian noise to the stochastic gradient at each update. The detailed algorithm is described in Algorithm 2, whose privacy guarantee is established in the following theorem.

Other than the privacy guarantees, the DP-SGD-Gradient algorithm also enjoys utility guarantees as stated in the following theorem.

Our basic idea to prove Theorem 12 is to use the following error decomposition:

Similar to the proof of Theorem 9, the generalization error $\mathcal{R}(\mathbf{w}_{\text{priv}})-\mathcal{R}_{S}(\mathbf{w}_{\text{priv}})$ can be handled by the UAS bound, the optimization error $\mathcal{R}_{S}(\mathbf{w}_{\text{priv}})-\mathcal{R}_{S}(\mathbf{w}^{*})$ can be estimated by standard techniques in optimization [[, e.g.]]Nem, and the last term $\mathcal{R}_{S}(\mathbf{w}^{*})-\mathcal{R}(\mathbf{w}^{*})$ can be bounded by the Hoeffding inequality. The detailed proof can be found in Subsection 3.3.

We now compare our results with the related work under a bounded domain assumption. The work established the optimal rate $\mathcal{O}(\frac{1}{n\epsilon}{\sqrt{d\log(1/\delta)}}+\frac{1}{\sqrt{n}})$ for the excess population risk of private SCO algorithm in either smooth case ($\alpha=1$) or non-smooth case ($\alpha=0$). However, their algorithm has a large gradient complexity \mathcal{O}\Big{(}n^{4.5}\sqrt{\epsilon}+\frac{n^{6.5}\epsilon^{4.5}}{(d\log(\frac{1}{\delta}))^{2}}\Big{)}. The work proposed a private phased ERM algorithm for SCO, which can achieve the optimal excess population risk for non-smooth losses with a better gradient complexity of the order $\mathcal{O}(n^{2}\log(1/{\delta}))$. The very recent work improved the gradient complexity to $\mathcal{O}(n^{2})$. As a comparison, we show that SGD with gradient complexity $\mathcal{O}(n^{2-\alpha\over 1+\alpha}+n)$ is able to achieve the optimal (up to logarithmic terms) excess population risk $\mathcal{O}(\frac{1}{n\epsilon}{\sqrt{d\log(1/\delta)}}+\frac{1}{\sqrt{n}})$ for general $\alpha$-Hölder smooth losses. Our results match the existing gradient complexity for both the smooth case in and the Lipschitz continuity case . An interesting observation is that our algorithm can achieve the optimal utility guarantee with the linear gradient complexity $\mathcal{O}(n)$ for $\alpha\geq 1/2$, which shows that a relaxation of the strong smoothness from $\alpha=1$ to $\alpha\geq 1/2$ does not bring any harm in both the generalization and computation complexity.

Now, we give a sufficient condition for the existence of $\beta$ in Theorem 11 under a specific parameter setting.

Let $n\geq 18$, $T=n$ and $\delta=1/{n^{2}}$. If $\epsilon\geq\frac{7(n^{\frac{1}{3}}-1)+4\log(n)n+7}{2n(n^{\frac{1}{3}}-1)},$ then there exists $\beta\in(0,1)$ such that Algorithm 2 satisfies $(\epsilon,\delta)$-DP.

Privacy parameters $\epsilon$ and $\delta$ together quantify the privacy risk. $\epsilon$ is often called the privacy budget controlling the degree of privacy leakage. A larger value of $\epsilon$ implies higher privacy risk. Therefore, the value of $\epsilon$ depends on how much privacy the user needs to protect. Theoretically, the value of $\epsilon$ is less than 1. However, in practice, to obtain the desired utility, a larger privacy budget, i.e., $\epsilon\geq 1$, is always acceptable . For instance, Apple uses a privacy budget $\epsilon=8$ for Safari Auto-play intent detection, and $\epsilon=2$ for Health typeshttps://www.apple.com/privacy/docs/Differential_Privacy_Overview.pdf. Parameter $\delta$ is the probability with which $e^{\epsilon}$ fails to bound the ratio between the two probabilities in the definition of differential privacy, i.e., the probability of privacy protection failure. For meaningful privacy guarantees, according to the value of $\delta$ should be much smaller than $1/n$. In particular, we always choose $\delta=1/n^{2}$. For DP-SGD-Gradient algorithm, another constant we should discuss is $\beta$ which depends on the choice of the number of iterations $T$, size of training data $n$, privacy parameters $\epsilon$ and $\delta$. The appearance of this parameter is due to the use of subsampling result for RDP (see Lemma 3). The condition in Lemma 13 ensures the existence of $\beta\in(0,1)$ such that Algorithm 2 satisfies DP. In practical applications, we search in $(0,1)$ for all $\beta$ that satisfy the RDP conditions in Theorem 11. Note that the closer the $\beta$ is to $1/2$, the smaller the variance of the noise added to the algorithm in each iteration. Therefore, we choose the value that is closest to $1/2$ of all $\beta$ that meets the RDP conditions as the value of $\beta$.

We end this section with a final remark on the challenges of proving DP for Algorithm 2 when $\mathcal{W}$ is unbounded.

Proofs of Main Results

Before presenting the detailed proof, we first introduce some useful lemmas on the concentration behavior of random variables.

Let $X$ be a sub-Gaussian random variable with mean $\mu$ and sub-Gaussian parameter $v^{2}$. Then, for any $t\geq 0$, we have, with probability at least 1-\exp\big{(}-t^{2}/(2v^{2})\big{)}, that $X-\mu\leq t$.

Our stability analysis for unbounded domain requires the following lemma on the self-bounding property for Hölder smooth losses.

Finally, we consider the case $\alpha\in(0,1)$. According to the self-bounding property and the convexity, we know

Therefore, for $\alpha\in(0,1)$ there holds

where the last inequality used Young’s inequality $ab\leq\frac{1}{p}a^{p}+\frac{1}{q}b^{q}$ with $\frac{1}{p}+\frac{1}{q}=1.$ Putting the above inequality into (5), we have

Taking a summation of the above inequality, we get

The desired result follows directly from (6), (7) and (8) for different values of $\alpha.$ ∎

With the above preparation, we are now ready to prove Theorem 7.

Case 1: If $i_{t}\neq i$, Lemma 21 implies that

Case 2: If $i_{t}=i$, it follows from the elementary inequality $(a+b)^{2}\leq(1+p)a^{2}+(1+1/p)b^{2}$ that

According to the definition of Hölder smoothness and Lemma 20, we know

Combining the above two cases and (9) together, we have

Since $\mathbf{w}_{1}=\mathbf{w}_{1}^{\prime}$ and $\eta_{t}=\eta$, we further get

For any $0<\gamma<\exp(-t/3n)$, with probability at least $1-\frac{\gamma}{n}$, there holds

Plug the above two inequalities back into (3.1), and let c_{\gamma,t}=\max\Big{\{}\sqrt{\frac{3\log(n/{\gamma})}{t/n}},\frac{3\log(n/{\gamma})}{t/n}\Big{\}}. Then, for any $\gamma\in(0,1)$, with probability at least $1-\frac{\gamma}{n}$, we have

Let $p=\frac{1}{\frac{t}{n}(1+c_{\gamma,t})}$. Then we know $(1+p)^{\frac{t}{n}(1+c_{\gamma,t})}\leq e$ and therefore

This together with the inequality c^{2}_{\alpha,t}\leq\big{(}M+L(C_{\alpha}t\eta)^{\frac{\alpha}{2}}\big{)}^{2} due to Lemma 20, we have, with probability at least $1-\frac{\gamma}{n}$, that

By taking a union bound of probabilities over $i=1,\ldots,n$, with probability at least $1-\gamma$, there holds

2 Proofs on Differentially Private SGD with Output Perturbation

We first prove Theorem 8 on the privacy guarantee of Algorithm 1.

Now, we turn to the utility guarantees of Algorithm 1. Recall that the excess population risk $\mathcal{R}(\mathbf{w}_{\text{priv}})-\mathcal{R}(\mathbf{w}^{*})$ can be decomposed as follows ($\bar{\mathbf{w}}=\frac{1}{T}\sum_{t=1}^{T}\mathbf{w}_{t}$)

We now introduce three lemmas to control the first three terms on the right hand side of (12). The following lemma controls the error resulting from the added noise.

If $\mathcal{W}\subseteq\mathcal{B}(0,R)$ with $R>0$, then, with probability at least $1-\frac{\gamma}{4}$, we have

Further, by the convexity of a norm and Lemma 20, we know

Putting the above inequality and (14) back into (3.2) yields

(b) The proof for the unbounded domain case is similar to that of the bounded domain. Since $\|\mathbf{w}_{t}\|_{2}\leq R$ for $t\in[T]$ in this case, then

Plugging (16) and (14) back into (3.2) yield the result in part (b). ∎

In the following lemma, we use the stability of SGD to control the generalization error $\mathcal{R}(\bar{\mathbf{w}})-\mathcal{R}_{S}(\bar{\mathbf{w}})$.

If $\mathcal{W}\subseteq\mathcal{B}(0,R)$ with $R>0$, then, with probability at least $1-\frac{\gamma}{4}$, we have

(a) Consider the unbounded domain case. Part (a) in Theorem 7 implies, with probability at least $1-\frac{\delta}{2}$, that

Since $\gamma\geq 4\delta$, then we know (17) holds with probability at least $1-\frac{\gamma}{8}$. According to the result $\|\bar{\mathbf{w}}\|_{2}\leq\sqrt{C_{\alpha}T\eta}$ by (15) and Lemma 1 with $G=\sqrt{C_{\alpha}T\eta}$ together, we derive the following inequality with probability at least $1-\frac{\gamma}{8}-\frac{\gamma}{8}=1-\frac{\gamma}{4}$

where $c>0$ is a constant. The proof of part (a) is completed.

(b) For the case $\mathcal{W}\subseteq\mathcal{B}(0,R)$, the proof follows a similar argument as part (a). Indeed, part (b) in Theorem 7 implies, with probability at least $1-\frac{\gamma}{8}$, that

Note that $\|\bar{\mathbf{w}}\|_{2}\leq R$ in this case, then combining (18) and Lemma 1 with $G=R$ together, with probability at least $1-\frac{\gamma}{4}$, we have

where $c>0$ is a constant. This completes the proof of part (b). ∎

In the following lemma, we use techniques in optimization theory to control the optimization error $\mathcal{R}_{S}(\bar{\mathbf{w}})-\mathcal{R}_{S}(\mathbf{w}^{*})$.

If $\mathcal{W}\subseteq\mathcal{B}(0,R)$ with $R>0$, then, with probability at least $1-\frac{\gamma}{4}$, we have

Similarly, for any $z\in\mathcal{Z}$, we have

Now, combining Lemma 17 with (3.2) and noting $\eta>1/T$, we get the following inequality with probability at least $1-\frac{\gamma}{8}$

According to Lemma 16, with probability at least $1-\frac{\gamma}{8}$, there holds

Since $0\leq\frac{2\alpha}{1+\alpha}\leq 1$, Lemma 19 implies the following inequality for any $t=1,\ldots,T$

Rearranging the above inequality and using (21), we derive

Now, plugging (22), (23) and (3.2) back into (3.2), we derive

with probability at least $1-\frac{\gamma}{4}$, which completes the proof of part (a).

Now, we are in a position to prove the utility guarantee for DP-SGD-Output algorithm. First, we give the proof for the unbounded domain case (i.e. Theorem 9).

Combining part (a) in Lemmas 22, 23, 24 and (27) together, with probability at least $1-\gamma$, the population excess risk can be bounded as follows

Plugging \Delta_{\text{SGD}}(\delta/2)=\mathcal{O}\Big{(}\sqrt{T}\eta^{\frac{1}{1-\alpha}}+\frac{(T\eta)^{1+\frac{\alpha}{2}}\log(n/\delta)}{n}\Big{)} and $\sigma=\mathcal{O}(\frac{\sqrt{\log(1/\delta)}\Delta_{\text{SGD}}(\delta/2)}{\epsilon})$ back into (3.2), we have

Taking the derivative of $\frac{1}{T\eta}+T^{\frac{1+\alpha}{2}}\sqrt{\frac{\log(1/\gamma)}{n}}\eta^{\frac{1+\alpha}{2}}$ w.r.t $\eta$ and setting it to , then we have \eta=n^{\frac{1}{3+\alpha}}/\big{(}T(\log(1/\gamma))^{\frac{1}{3+\alpha}}\big{)}. Putting this $\eta$ back into (3.2), we obtain

To achieve the best rate with a minimal computational cost, we choose the smallest $T$ such that $\frac{n^{\frac{(2-\alpha)(1+\alpha)}{2(1-\alpha)(3+\alpha)}}}{T^{\frac{1+\alpha}{2(1-\alpha)}}}=\mathcal{O}(\frac{1}{n^{\frac{2}{3+\alpha}}})$, $\frac{n^{\frac{1+\alpha}{(1-\alpha)(3+\alpha)}}}{T^{\frac{(1+\alpha)^{2}}{2(1-\alpha)}}}=\mathcal{O}(\frac{1}{n^{\frac{(4+\alpha)(1+\alpha)}{2(3+\alpha)}}})$ and $\frac{n^{\frac{2+\alpha-\alpha^{2}}{2(3+\alpha)(1-\alpha)}}}{T^{\frac{1+\alpha}{2(1-\alpha)}}}+\frac{1}{n^{\frac{2}{3+\alpha}}}+\frac{n^{\frac{1}{3+\alpha}}}{T}=\mathcal{O}(\frac{1}{n^{\frac{1}{3+\alpha}}})$. Hence, we set $T\asymp n^{\frac{-\alpha^{2}-3\alpha+6}{(1+\alpha)(3+\alpha)}}$ if $0\leq\alpha\leq\frac{\sqrt{73}-7}{4}$, and $T\asymp n$ else. Now, putting the choice of $T$ back into (3.2), we derive

Without loss of generality, we assume the first term of the above utility bound is less than 1. Therefore, with probability at least $1-\gamma$, there holds

Finally, we provide the proof of utility guarantee for the DP-SGD-Output algorithm when $\mathcal{W}\subseteq\mathcal{B}(0,R)$ (i.e. Theorem 10).

The proof is similar to that of Theorem 9. Indeed, plugging part (b) in Lemmas 22, 23, 24 and (27) back into (12), with probability at least $1-\gamma$, the population excess risk can be bounded as follows

Consider the tradeoff between $1/\eta$ and $\eta$. Taking the derivative of \big{(}\frac{T\log(n/\delta)\log(n)\log(1/\gamma)}{n}+\frac{T\sqrt{d\log(1/\delta)}\log(n/\delta)(\log(1/\gamma))^{1/4}}{n\epsilon}\big{)}\eta $+\frac{1}{T\eta}$ w.r.t $\eta$ and setting it to , we have \eta=1/\Big{(}T\max\Big{\{}\frac{\sqrt{\log(n/\delta)\log(n)\log(1/\gamma)}}{\sqrt{n}},\frac{\big{(}d\log(1/\delta)\big{)}^{1/4}\sqrt{\log(n/\delta)}(\log(1/\gamma))^{1/8}}{\sqrt{n\epsilon}}\Big{\}}\Big{)}. Then putting the value of $\eta$ back into (3.2), we obtain

Similarly, we choose the smallest $T$ such that $\frac{n^{\frac{1}{2(1-\alpha)}}}{T^{\frac{1+\alpha}{2(1-\alpha)}}}=\mathcal{O}(\frac{1}{\sqrt{n}})$. Hence, we set $T\asymp n^{\frac{2-\alpha}{1+\alpha}}$ if $\alpha<\frac{1}{2}$, and $T\asymp n$ else. Since $\frac{1}{4}\geq\frac{1-2\alpha}{2(1-\alpha)}$, we have

It is reasonable to assume the first term is less than $1$ here. Therefore, with probability at least $1-\gamma$, there holds

3 Proofs on Differential Privacy of SGD with Gradient Perturbation

We now turn to the analysis for DP-SGD-Gradient algorithm (i.e. Algorithm 2) and provide the proofs for Theorems 11 and 12. We start with the proof of Theorem 11 on the privacy guarantee for Algorithm 2.

Lemma 3 with $p=\frac{1}{n}$ implies that $\mathcal{G}_{t}$ satisfies \Big{(}\lambda,\frac{\lambda\beta\epsilon}{T\big{(}\frac{\log(1/\delta)}{(1-\beta)\epsilon}+1\big{)}}\Big{)}-RDP if the following conditions hold

Let $\lambda=\frac{\log(1/\delta)}{(1-\beta)\epsilon}+1$. We obtain that $\mathcal{G}_{t}$ satisfies $(\frac{\log(1/\delta)}{(1-\beta)\epsilon}+1,\frac{\beta\epsilon}{T})$-RDP. Then by the post-processing property of DP (see Lemma 6), we know $\mathbf{w}_{t+1}$ also satisfies $(\frac{\log(1/\delta)}{(1-\beta)\epsilon}+1,\frac{\beta\epsilon}{T})$-RDP for any $t=0,...,T-1$. Furthermore, according to the adaptive composition theorem of RDP (see Lemma 4), Algorithm 2 satisfies $(\frac{\log(1/\delta)}{(1-\beta)\epsilon}+1,\beta\epsilon)$-RDP. Finally, by Lemma 5, the output of Algorithm 2 satisfies $(\epsilon,\delta)$-DP as long as (32) and (33) hold. ∎

Now, we turn to the generalization analysis of Algorithm 2. First, we estimate the generalization error $\mathcal{R}(\mathbf{w}_{\text{priv}})-\mathcal{R}_{S}(\mathbf{w}_{\text{priv}})$ in (4).

where $c>0$ is a constant. The proof is completed. ∎

The following lemma gives an upper bound for the second term $\mathcal{R}_{S}(\mathbf{w}_{\text{priv}})-\mathcal{R}_{S}(\mathbf{w}^{*})$ in (4).

To estimate the term $\mathcal{R}_{S}(\mathbf{w}_{\text{priv}})-\mathcal{R}_{S}(\mathbf{w}^{*})$, we decompose it as

In addition, Hoeffding inequality (see Lemma 16) implies, with probability at least $1-\frac{\gamma}{9}$, that

Therefore, with probability at least $1-\frac{\gamma}{9}$, there holds

Putting (35), (36) and (37) back into (34), we obtain, with probability at least $1-\frac{\gamma}{3}$, that

Now, we are ready to prove the utility theorem for DP-SGD-Gradient algorithm.

The Hoeffding inequality implies, with probability at least $1-\frac{\gamma}{3}$, that

Combining Lemma 25, Lemma 26 and the above inequality together, with probability at least $1-\gamma$, we obtain

To choose a suitable $\eta$ and $T$ such that the algorithm achieves the optimal rate, we consider the trade-off between $1/\eta$ and $\eta$. We take the derivative of \frac{1}{T\eta}+\eta\big{(}\frac{Td\log(1/\delta)\sqrt{\log(1/\gamma)}}{n^{2}\epsilon^{2}}+\frac{T\log(n)\log(n/\gamma)\log(1/\gamma)}{n}\big{)} w.r.t $\eta$ and set it to , then we have \eta=1/T\cdot\max\big{\{}\frac{\sqrt{\log(n)\log(n/\gamma)\log(1/\gamma)}}{\sqrt{n}},\frac{\sqrt{d\log(1/\delta)}(\log(1/\gamma))^{\frac{1}{4}}}{n\epsilon}\big{\}}. Putting the value of $\eta$ back into (3.3), we obtain

In addition, if $n=\mathcal{O}(T^{\frac{1+\alpha}{2-\alpha}})$, then there holds

The above bound matches the optimal rate \mathcal{O}\big{(}\frac{\sqrt{d\log(1/\delta)}}{n\epsilon}+\frac{1}{\sqrt{n}}\big{)}. Furthermore, we want the algorithm to achieve the optimal rate with a low computational cost. Therefore, we set $T\asymp n^{\frac{2-\alpha}{1+\alpha}}$ if $\alpha<\frac{1}{2}$, and $T\asymp n$ else. The proof is completed.

Finally, we give the proof of Lemma 13 on the existence of $\beta$ for Algorithm 2 to be $(\epsilon,\delta)$-DP.

We give sufficient conditions for the existence of $\beta\in(0,1)$ such that RDP conditions (32) and (33) hold with $\sigma^{2}=\frac{14(M+LR^{\alpha})^{2}\lambda}{\beta n\epsilon}$ and $\lambda=\frac{2\log(n)}{(1-\beta)\epsilon}+1$ in Theorem 11. Condition (32) with $T=n$ and $\delta=\frac{1}{n^{2}}$ is equivalent to

If \big{(}1+\frac{7}{1.34n\epsilon}\big{)}^{2}<\frac{28(2\log(n)+\epsilon)}{1.34n\epsilon^{2}}, then $f(\beta)\geq 0$ for all $\beta$. Then (32) holds for any $\beta\in(0,1)$. If \big{(}1+\frac{7}{1.34n\epsilon}\big{)}^{2}\geq\frac{28(2\log(n)+\epsilon)}{1.34n\epsilon^{2}}, then $\beta\in(0,\beta_{1}]\cup[\beta_{2},+\infty)$ such that the above condition holds, where \beta_{1,2}=\frac{1}{2}\Big{(}\big{(}1+\frac{7}{1.34n\epsilon}\big{)}\mp\sqrt{\big{(}1+\frac{7}{1.34n\epsilon}\big{)}^{2}-\frac{28(2\log(n)+\epsilon)}{1.34n\epsilon^{2}}}\Big{)} are two roots of $f(\beta)=0$.

Now, we consider the second RDP condition. Plugging $\sigma^{2}=\frac{14(M+LR^{\alpha})^{2}\lambda}{\beta n\epsilon}$ back into (33), we derive

To guarantee (40), it suffices that the following three inequalities hold

We set $\lambda=\frac{2\log(n)}{(1-\beta)\epsilon}+1$ in the above three inequalities. Since $\lambda>1$, then (41) holds if $\beta\leq 7\log(n)/9n\epsilon$. Eq. (42) reduces to $\beta\leq 1-\frac{2\log(n)}{(n^{1/3}-1)\epsilon}$. Moreover, (43) is equivalent to the following inequality

There exists at least one $\beta$ such that $g(\beta)\leq 0$ if $(1+\frac{7}{2n(n^{1/3}-1)\epsilon})^{2}-\frac{14(2\log(n)+\epsilon)}{n(n^{1/3}-1)\epsilon^{2}}\geq 0$, which can be ensured by the condition $\epsilon\geq\frac{7}{2n(n^{1/3}-1)}+2\sqrt{\frac{7\log(n)}{n(n^{1/3}-1)}}$. Furthermore, $g(\beta)\leq 0$ for all $\beta\in[\beta_{3},\beta_{4}]$, where \beta_{3,4}=\frac{1}{2}\Big{(}\big{(}1+\frac{7}{2n(n^{1/3}-1)\epsilon}\big{)}\mp\sqrt{\big{(}1+\frac{7}{2n(n^{1/3}-1)\epsilon}\big{)}^{2}-\frac{14(2\log(n)+\epsilon)}{n\big{(}n^{1/3}-1\big{)}\epsilon^{2}}}\Big{)} are two roots of $g(\beta)=0$. Finally, note that

Conditions (45) and (46) ensure the existence of at least one consistent $\beta\in(0,1)$ such that (39), (41), (42), (43) and (44) hold, which imply that (32) and (33) hold. The proof is completed. ∎

Conclusion

Acknowledgement. This work was done while Puyu Wang was a visiting student at SUNY Albany. The corresponding author is Yiming Ying, whose work is supported by NSF grants IIS-1816227 and IIS-2008532. The work of Hai Zhang is supported by NSFC grant U1811461.

References