Privacy Amplification by Iteration

Introduction

Differential privacy is a standard concept for capturing privacy of statistical algorithms. In its original formulation, (pure) differential privacy is parameterized by a single real number—the so-called privacy budget—which characterizes the privacy loss of an individual contributor to the input dataset.

As applications of differential privacy start to proliferate, they bring to the fore the problem of administering the privacy budget, with specific emphasis on privacy composition and privacy amplification.

Privacy composition enables modular design and analysis of complex and heterogeneous algorithms from simpler building blocks by controlling the total privacy budget of their combination. Improving on “naïve” composition, which simply (but very consequentially!) states that the privacy budgets of composition blocks sum up, “advanced” composition theorems allow subadditive accumulation of the privacy budgets. All existing proofs of advanced composition theorems assume that all intermediate outputs are revealed, whether the composite mechanism requires it or not.

Privacy amplification goes even further by bounding the privacy budget—for select mechanisms—of a combination to be less than the privacy budget of its parts. The only systematically studied instance of this phenomenon is privacy amplification by sampling . In its basic form, for $\varepsilon=O(1)$, an $\varepsilon$-differentially private mechanism applied to a secretly sampled $p$ fraction of the input satisfies $O(p\varepsilon)$-differential privacy. More recent results demonstrate that privacy can be amplified in proportion to $p^{2}$ (for a Gaussian additive noise mechanism and appropriate relaxations of differential privacy).

This work introduces a new amplification argument—amplification by iteration—that in certain contexts can be seen as an alternative to privacy amplification by sampling. As an exemplar of the kind of algorithms we wish to analyze, we consider noisy stochastic gradient descent for a smooth and convex objective.

Our first contribution is a general theorem that states that, under certain conditions on an iterative process, the process shrinks the Rényi divergence between distributions. We will focus on the simplest form of these conditions in which the mechanism is a composition of a sequence of contractive (or $1$-Lipschitz) maps and an additive Gaussian noise mechanism. This is a natural setting for several differentially private optimization algorithms. A more general treatment that allows other Banach spaces and noise distributions appears in Section 3.3.

We note that in this result we measure the divergence only between the final steps, in other words, the intermediate steps of the iteration are not revealed. This theorem is a special case of our more general result Theorem 22. This result translates a metric assumption of bounded distance between $x_{0}$ and $x^{\prime}_{0}$ to an information-theoretic conclusion of bounded Rényi divergence between $X_{T}$ and $X^{\prime}_{T}$. While standard facts about the Gaussian distribution allow one to make such a statement for a one-step process, the intermediate arbitrary contractive steps essentially rule out a first principles approach to proving such a theorem. We use a careful induction argument that rests on controlling the “distance” between $X_{t}$ and $X^{\prime}_{t}$. We start by measuring the metric distance when $t=0$ and gradually transform this to an information theoretic divergence at $t=T$. We interpolate between these two using a new hybrid distance measure that we refer to as shifted divergence. We believe that this notion should find additional applications in the analyses of stochastic processes. Our bounds are tight (with no loss in constants) and show that the worst-case for such a result is when all the contractive maps are the identity map.

This result has some surprising implications. Consider an iterative mechanism that processes one input record at a time, $n$ iterations in total. The immediate application of this result to this mechanism leads to the following observation about individuals’ privacy loss. The person whose record was processed last experiences privacy loss afforded by the Gaussian noise added at the last iteration. At the same time, the person whose record was processed first suffers the least amount of privacy loss, equal to $1/n$ of the last one’s. Importantly, the order in which the inputs were considered need not be random or secret for this analysis to be applicable. In contrast, privacy amplification by sampling depends crucially on the sample’s randomness and secrecy.

We outline some applications of this analysis in privacy-preserving machine learning via convex optimization.

In this setting records are stored locally, and the parties engage in a distributed computation to train a model . Using amplification by sampling as in DP-SGD by Abadi et al. would require keeping secret the set of parties taking part in each step of the algorithm. When the communication channel is not trusted, hiding whether or not a party takes part in a certain step would essentially require all parties to communicate in all steps, leading to an unreasonable amount of communication. In addition, the assumption that the sample of parties participating in each step is a random subset may itself be difficult to enforce in many settings.

Our approach does not need the order of participating parties to be random or hidden. It is sufficient to hide the model itself until a certain number of update steps are applied. This approach then allows significantly reducing communication costs to be proportional to the size of the mini-batch (the number of records consumed by each update). Additionally, our approach can amplify privacy even when the noise added in each step is too small to guarantee much privacy. This is in contrast to amplification by sampling, which requires the unamplified privacy cost to be small to start with: a starting $\varepsilon$ becomes $\approx q\varepsilon(1+\exp(\varepsilon))$ which is close to $2q\varepsilon$ for small $\varepsilon$ but grows quickly, and for instance, precludes setting $\varepsilon\geq 1/q$ for small $q$. Our main result applies for arbitrary $\sigma$ so that even if each $\sigma$ is very small (say, $1/\sqrt{n}$) the final privacy is non-vacuous. A smaller noise scale then permits a smaller size of each mini-batch, further reducing the communication cost. On the negative side, the privacy guarantee we get varies between examples: examples used early in the SGD get stronger privacy than those occurring late.

Multi-query setting.

Public/private data.

The setting in which some public data from the same distribution as private data is available has been recently identified as promising and practically important . The public corpus can be based on opt-in population, such as a product’s developers or early testers, data shared by volunteers , or be released through a legal process .

We remark that our technique requires that the optimized functions satisfy a mild smoothness assumption. However, as we show, in our applications we can always achieve the desired level of smoothness by convolving the optimized functions with the Gaussian kernel. Such convolution introduces an additional error but this error is dominated by the error necessary to ensure privacy.

Organization.

The rest of the paper is organized as follows. After discussing some additional related work, we start with some preliminaries in Section 2. We present our main technique in Section 3. Section 4 shows how this technique can be applied to versions of the noisy stochastic gradient descent algorithm. Finally, in Section 5, we apply this framework to derive the applications mentioned above.

1 Related Work

The field of differentially private convex optimization spans almost a decade . Many of these results are optimal under different regimes such as empirical loss, population loss, the low-dimensional setting ($d\ll n$) or the high-dimensional setting $d\gg n$. Some of the algorithms (e.g., output perturbation and objective perturbation ) require finding a global optimum of an optimization problem to argue privacy and utility, while the others are based on the variants of noisy stochastic gradient descent. In this section we restrict ourselves to only the population loss, and allow comparisons to algorithms that can be implemented with one pass of stochastic gradient descent over the data set $S$ for a direct comparison (which is close to the typical application of optimization algorithms in machine learning). We note that our analysis technique also applies to multi-pass and batch versions of gradient descent. In this setting our algorithm achieves close to optimal bounds on population loss (see Table 1 for details).

In this table we also compare the local differential privacy of the algorithms . In several settings (such as distributed learning) we want the published outcome of the optimization algorithm to satisfy a strong level of (central) differential privacy while still guaranteeing $\varepsilon_{\sf local}$ differential privacy. Local differential privacy protects the user’s data even from the aggregating server or an adversary who can obtain the complete transcript of communication between the server and the user.

We note that some architectures may not be compatible with all privacy-preserving techniques or guarantees. For instance, we assume secrecy of intermediate computations, which rules out sharing intermediate updates (which is a standard step in federated learning ). In contrast, analyses based on secrecy of the sample (e.g., ) require that either data be stored centrally (thus eliminating local differential privacy guarantees) or all-to-all communications.

Preliminaries

We recall definitions and tools from the learning theory, probability theory, and differential privacy and define the notion of shifted divergence. In the process we set up the notation that we will use throughout the paper.

In order to argue differential privacy we place certain assumptions on the loss function. To that end, we need the following two definitions of Lipschitz continuity and smoothness.

2 Probability Measures

We say a distribution $\mu$ is absolutely continuous with respect to $\nu$ if $\mu(A)=0$ whenever $\nu(A)=0$ for all measurable sets $A$. We will denote this by $\mu\ll\nu$.

Given two distributions $\mu$ and $\nu$ on a Banach space $(\mathcal{Z},\|\cdot\|)$, one can define several notions of distance between them. The first family of distances we consider is independent of the norm:

Let $1<\alpha<\infty$ and $\mu,\nu$ be measures with $\mu\ll\nu$. The Rényi divergence of order $\alpha$ between $\mu$ and $\nu$ is defined as

Here we follow the convention that $\frac{0}{0}=0$. If $\mu\not\ll\nu$, we define the Rényi divergence to be $\infty$. Rényi divergence of orders $\alpha=1,\infty$ is defined by continuity.

The following hold for any $\alpha\in(1,\infty)$, and distributions $\mu,\mu^{\prime},\nu,\nu^{\prime}$:

As usual, we denote by $\mu\ast\nu$ the convolution of $\mu$ and $\nu$, that is the distribution of the sum $X+Y$ where we draw $X\sim\mu$ and $Y\sim\nu$ independently.

We will also need the following “norm-aware” statistical distance:

The $\infty$-Wasserstein distance between distributions $\mu$ and $\nu$ on a Banach space $(\mathcal{Z},\|\cdot\|)$ is defined as

where $(x,y)\sim\gamma$ means that the essential supremum is taken relative to measure $\gamma$ over $\mathcal{Z}\times\mathcal{Z}$ parameterized by $(x,y)$. Here $\Gamma(\mu,\nu)$ is the collection of couplings of $\mu$ and $\nu$, i.e., the collection of measures on $\mathcal{Z}\times\mathcal{Z}$ with marginals $\mu$ and $\nu$ on the first and second factors respectively.

The following is immediate from the definition.

The following are equivalent for any distributions $\mu$, $\nu$ over $\mathcal{Z}$:

There exists jointly distributed r.v.’s $(U,V)$ such that $U~{}\sim\mu$, $V\sim\nu$ and $\Pr[\|U-V\|\leq s]=1$.

There exists jointly distributed r.v.’s $(U,W)$ such that $U~{}\sim\mu$, $U+W\sim\nu$ and $\Pr[\|W\|\leq s]=1$.

Next we define a hybridHere we use a budgeted version of the definition, putting a hard constraint on the $W_{\infty}$ portion of the distance, as it is most convenient for reasoning about differential privacy. A Lagrangian version of the definition may be more natural in other applications. between these two families of distances that plays a central role in our work.

Let $\mu$ and $\nu$ be distributions defined on a Banach space $(\mathcal{Z},\|\cdot\|)$. For parameters $z\geq 0$ and $\alpha\geq 1$, the $z$-shifted Rényi divergence between $\mu$ and $\nu$ is defined as

The following follows from the definition:

The shifted Rényi divergences satisfy the following for any $\mu,\nu$, and any $\alpha\in(1,\infty)$:

For a noise distribution $\zeta$ over a Banach space $(\mathcal{Z},\|\cdot\|)$ we measure the magnitude of noise by considering the function that for $a>0$, measures the largest Rényi divergence of order $\alpha$ between $\zeta$ and the same distribution $\zeta$ shifted by a vector of length at most $a$:

3 (Rényi ) Differential Privacy

The notion of differential privacy (11) is by now a de facto standard for statistical data privacy . At a semantic level, the privacy guarantee ensures that an adversary learns almost the same thing about an individual independent of the individual’s presence or absence in the data set. The parameters $(\varepsilon,\delta)$ quantify the amount of information leakage. A common choice of these parameters is $\varepsilon\approx 0.1$ and $\delta=1/n^{\omega(1)}$, where $n$ refers to the size of the dataset.

A randomized algorithm $\mathcal{A}$ is$(\varepsilon,\delta)$-differentially private ($(\varepsilon,\delta)$-DP) if, for all neighboring data sets $S$ and $S^{\prime}$ and for all events $\mathcal{O}$ in the output space of $\mathcal{A}$, we have

The notion of neighboring data sets is domain-dependent, and it is commonly taken to capture the contribution of a single individual. In the simplest case $S$ and $S^{\prime}$ differ in one record, or equivalently, $d_{H}(S,S^{\prime})=1$, where $d_{H}(S,S^{\prime})$ is the Hamming distance. We also define

An algorithm $\mathcal{A}$ operating on a sequence of data points $x_{1},\ldots,x_{n}$ is said to satisfy $(\varepsilon,\delta)$-differentially privacy at index $i$ if for any pair of sequences that differ in the $i$th position, and for any event $\mathcal{O}$ in the output space of $\mathcal{A}$, we have

Another related model of privacy is local differential privacy . In this model each user executes a differentially private algorithm on their individual input which is then used for arbitrary subsequent computation (we omit the formal definition as it is not used in our work).

Starting with Concentrated Differential Privacy , definitions that allow more fine-grained control of the privacy loss random variable have proven useful. The notions of zCDP , Moments Accountant , and Rényi differential privacy (RDP) capture versions of this definition. This approach improves on traditional $(\varepsilon,\delta)$-DP accounting in numerous settings, often leading to significantly tighter privacy bounds as well as being applicable when the traditional approach fails . In the current work, we will use the nomenclature based on the notion of the Rényi divergence (4).

For $1\leq\alpha\leq\infty$ and $\varepsilon\geq 0$, a randomized algorithm $\mathcal{A}$ is $(\alpha,\varepsilon)$-Rényi differentially private, or $(\alpha,\varepsilon)$-RDP if for all neighboring data sets $S$ and $S^{\prime}$ we have

Per-person RDP can be defined in an analogous way. The following two lemmas allow translating Rényi differential privacy to $(\varepsilon,\delta)$-differential privacy, and give a composition rule for RDP.

If $\mathcal{A}$ satisfies $(\alpha,\varepsilon)$-Rényi differential privacy, then for all $\delta\in(0,1)$ it also satisfies $\left(\varepsilon+\frac{\ln(1/\delta)}{\alpha-1},\delta\right)$-differential privacy. Moreover, pure $(\varepsilon,0)$-differential privacy coincides with $(\infty,\varepsilon)$-RDP.

The standard composition rule for Rényi differential privacy, when the outputs of all algorithms are revealed, takes the following form.

If $\mathcal{A}_{1},\dots,\mathcal{A}_{k}$ are randomized algorithms satisfying, respectively, $(\alpha,\varepsilon_{1})$-RDP,…,$(\alpha,\varepsilon_{k})$-RDP, then their composition defined as $(\mathcal{A}_{1}(S),\dots,\mathcal{A}_{k}(S))$ is $(\alpha,\varepsilon_{1}+\dots+\varepsilon_{k})$-RDP. Moreover, the $i$’th algorithm can be chosen on the basis of the outputs of algorithms $\mathcal{A}_{1},\dots,\mathcal{A}_{i-1}$.

4 Contractive Noisy Iteration

We start by recalling the definition of a contraction.

For a Banach space $(\mathcal{Z},\|\cdot\|)$, a function $\psi\colon\mathcal{Z}\to\mathcal{Z}$ is said to be contractive if it is 1-Lipschitz. Namely, for all $x,y\in\mathcal{Z}$,

A canonical example of a contraction is projection onto a convex set in the Euclidean space.

The map $\Pi_{\mathcal{K}}$ is a contraction.

Another example of a contraction, which will be important in our work, is a gradient descent step for a smooth convex function. The following is a standard result in convex optimization ; for completeness, we give a proof in Appendix A.

is contractive as long as $\eta\leq 2/\beta$.

We will be interested in a class of iterative stochastic processes where we alternate between adding noise and applying some contractive map.

Given an initial random state $X_{0}\in\mathcal{Z}$, a sequence of contractive functions $\psi_{t}\colon\mathcal{Z}\to\mathcal{Z}$, and a sequence of noise distributions $\{\zeta_{t}\}$, we define the Contractive Noisy Iteration (CNI) by the following update rule:

where $Z_{t+1}$ is drawn independently from $\zeta_{t+1}$. For brevity, we will denote the random variable output by this process after $T$ steps as $\mbox{CNI}_{T}(X_{0},\{\psi_{t}\},\{\zeta_{t}\})$.

Coupled Descent

In this section, we prove a bound on the Rényi divergence between the outputs of two contractive noisy iterations. Suppose that $X_{0}$ and $X^{\prime}_{0}$ are two random states such that $W_{\infty}(X_{0},X^{\prime}_{0})\leq 1$. The map’s contractivity and the fact that we are adding noise $\zeta$ ensures that $X_{1}$ and $X^{\prime}_{1}$ are $R_{\alpha}(\zeta,1)$-close in $\alpha$-Rényi divergence. By the post-processing property of Rényi divergence, $X_{T}$ and $X^{\prime}_{T}$ are similarly close. Our main theorem says that this can be substantially improved if we do not release the intermediate steps. The noise added in subsequent steps further decreases the Rényi divergence even when contractive steps are taken in between the noise addition.

While the final result is a statement about Rényi divergences, the shifted Rényi divergences play a crucial role in the proof. We start with an important technical lemma that for the noise addition step, allows one to reduce the shift parameter $z$. We will then show how contractive maps affect the shifted divergence. Armed with these results, we prove the main theorem in Section 3.3.

Let $\mu$,$\nu$ and $\zeta$ be distributions over a Banach space $(\mathcal{Z},\|\cdot\|)$. Then for any $a\geq 0$,

where we have used the post-processing property of Rényi divergence. Note that the distribution $(V,Y)$ is a product distribution, whereas the factors of $(U+W,-W+Y)$ are dependent. Denoting the $p_{X}$ the density function of a random variable $X$, we expand

Taking logs and dividing by $(\alpha-1)$, we get the claim for $z=0$.

The general $z$ case reduces readily to the $z=0$ case. Define

It is easy to see that $\|h_{z}(x)\|\leq z$ for all $x$, and that $\|x-h_{z}(x)\|\leq a$ whenever $\|x\|\leq z+a$.

As before, let $(U,W)$ be r.v.’s from the joint distribution guaranteed by 7. Let $W_{1}\doteq h_{z}(W)$ and $W_{2}\doteq W-W_{1}$. It follows that $\|W_{1}\|\leq z$ and $\|W_{2}\|\leq a$ with probability 1. We write

where we have used the $z=0$ case in the last step. On the other hand,

2 Contractive Maps

We next show that contractive maps cannot increase a shifted divergence. In the lemma below we give a more general version that allows using different contractive maps.

Suppose that $\psi$ and $\psi^{\prime}$ are contractive maps on $(\mathcal{Z},\|\cdot\|)$ and $\sup_{x}\|\psi(x)-\psi^{\prime}(x)\|\leq s$. Then for r.v.’s $X$ and $X^{\prime}$ over $\mathcal{Z}$,

3 Privacy Amplification by Iteration

We are now ready to prove our main result. We prove a general statement that can handle changes in several $\psi$’s; this enables us to easily analyze algorithms that access data points more than onceSince Rényi divergence does not satisfy the triangle inequality, blackbox analyses of such algorithms use the group privacy properties of RDP that can be loose.. Recall that $R_{\alpha}$ is introduced in 10 and measures the maximal Rényi divergence of order $\alpha$ between a noise distribution and its shifted copy.

Let $X_{T}$ and $X^{\prime}_{T}$ denote the output of $\mbox{CNI}_{T}(X_{0},\{\psi_{t}\},\{\zeta_{t}\})$ and $\mbox{CNI}_{T}(X_{0},\{\psi^{\prime}_{t}\},\{\zeta_{t}\})$. Let $s_{t}\doteq\sup_{x}\|\psi_{t}(x)-\psi^{\prime}_{t}(x)\|$. Let $a_{1},\ldots,a_{T}$ be a sequence of reals and let $z_{t}\doteq\sum_{i\leq t}s_{i}-\sum_{i\leq t}a_{i}$. If $z_{t}\geq 0$ for all $t$, then

Let $X_{t}$ (resp., $X^{\prime}_{t}$) denote the $t$’th iterate of the $\mbox{CNI}(X_{0},\{\psi_{t}\},\{\zeta_{t}\})$ (resp., $\mbox{CNI}(X_{0},\{\psi^{\prime}_{t}\},\{\zeta_{t}\})$. We argue that for all $t\leq T$,

The base case is $t=0$. By definition, $X_{0}=X^{\prime}_{0}$ and $z_{0}=0$. For the inductive step, let $Z_{t+1}$ denote the random variable drawn from $\zeta_{t+1}$.

This completes the induction step and the proof. ∎

Privacy Guarantees for Noisy Stochastic Gradient Descent

For this baseline algorithm we prove that points that are used earlier have stronger privacy guarantees due to noise injected in subsequent steps.

We can now apply Theorem 22 with $a_{1},\ldots,a_{t-1}=0$ and $a_{t},\ldots,a_{n}=\frac{2\eta L}{n-t+1}$. Note that $s_{t}=2\eta L$ and $s_{i}=0$ for $i\neq t$. In addition, $z_{i}\geq 0$ for all $i\leq n$ and $z_{n}=0$. Hence we obtain that

We now consider privacy guarantees for several variants of this baseline approach. These variants are needed to ensure utility guarantees, that require that the algorithm output one of the iterates randomly. Specifically, we define the algorithm Skip-PNSGD$(S,w_{0},\eta,\sigma)$ as the algorithm that picks randomly and uniformly $t_{0}\in\{0,1,\ldots,\lfloor n/2\rfloor\}$ and then skips the first $t_{0}$ points. That is, it makes only $n-t_{0}$ steps and at step $t$ the update is $w^{\prime}_{t+1}=w_{t}-\eta(\nabla_{w}f(w_{t},x_{t+1+t_{0}})+Z)$. It is easy to see that the privacy guarantees Skip-PNSGD$(S,w_{0},\eta,\sigma)$ are at least as good as those we gave for PNSGD$(S,w_{0},\eta,\sigma)$ in Theorem 23.

where to obtain the inequality in the fourth line we used the fact that for every $a\leq c\leq 1$, $e^{a}\leq 1+a+a^{2}\leq 1+(1+c)a$. ∎

We can now state and prove the privacy guarantees for Stop-PNSGD$(\eta,\sigma)$.

By definition, the output of Stop-PNSGD$(S,w_{0},\eta,\sigma)$ corresponds to picking $T$ randomly and uniformly from $[n]$ and then outputting $X_{T}$. We denote the resulting random variable by $Y_{n}$ and denote $Y^{\prime}_{n}$ the corresponding random variable for $S^{\prime}$. By our assumption, $\sigma\geq L\sqrt{2(\alpha-1)\alpha}$ and therefore for every $t\geq T$,

Hence the conditions of 25 are satisfied with $c=1$. This implies that

In Appendix B, we present a simple analysis of a multiple-pass version of the SGD algorithm. While it gives results that are quantitatively similar to what can be achieved using privacy amplification by sampling results from , the approach here works in the distributed setting and leads to a significantly simpler proof.

Finally, we remark that PNSGD$(S,w_{0},\eta,\sigma)$ and its variants described above satisfy local differential privacy (even without the smoothness assumption). Specifically,

Applications

We now show how to use the algorithms we have analyzed to derive new results for privacy-preserving convex optimization. One of the applications we discussed is concerned with a distributed model, where the input records are spread across users’ devices. In the “Our data, ourselves” model proposed by , each user’s device holds their data, and there is no central trusted party. Under reasonable assumptions on the devices, one can simulate a trusted party by means of a Secure Multi-party Computation protocol. While one can assume that all peer-to-peer channels are encrypted, it is reasonable to assume that an attacker can detect the presence or absence of communication. Additionally, in many settings of interest, bandwidth is at a premium and the number of users is large enough that all-to-all communication becomes an implementation bottleneck.

These constraints rule out algorithms that require all parties to be active in every iteration. Consequently, since the presence or absence of communication may be observed by an adversary, we cannot apply privacy amplification by sampling. While algorithms such as bolt-on differential privacy may be usable in the trusted central party setting, their privacy guarantee is uniform and weaker than ours. Our approach gives some baseline local differential privacy and a stronger global privacy guarantee for most users.

where $F^{*}\doteq\min_{w\in\mathcal{K}}F(w)$ and the expectation is taken over the randomness of $G$.

Note that this result gives a bound on the expected value of $F$ averaged over all the iterates. Equivalently, it can be seen as the expected value of $F(w_{t})$ with the expectation also taken over $t$ being chosen randomly and uniformly from $[T]$. This corresponds to the random stopping of PSGD$(G,w_{0},\eta,T)$. As a result we get the following baseline guarantees for Stop-PNSGD$(S,w_{0},\eta,\sigma)$ we defined in Section 4 (namely, these guarantees do not use our amplification analysis and do not require smoothness).

Hence, we can apply Theorem 28 for $L_{G}=L\sqrt{1+\frac{8d\ln(1.25/\delta)}{\varepsilon^{2}}}$ and $\eta=2R/(L_{G}\sqrt{n})$ to obtain that

2 Per-person Privacy

We will now show how to combine our stronger privacy guarantees for some of the individuals in the dataset with the utility guarantees in Theorem 28.

Our privacy guarantees follow directly from Theorem 23 and 27. Let us denote by Stop$(n/2)$-PNSGD$(S,w_{0},\eta,\sigma)$ the algorithm that runs PNSGD$(S,w_{0},\eta,\sigma)$ with a randomly and uniformly chosen stopping time $T\in\{\lceil n/2\rceil,\ldots,n\}$. Observe that the distribution of the output of Skip-PNSGD$(S,w_{0},\eta,\sigma)$ on $S\sim\mathcal{P}^{n}$ is identical to the output distribution of Stop$(n/2)$-PNSGD$(S,w_{0},\eta,\sigma)$ on $S\sim\mathcal{P}^{n}$. (This is true since in both cases the starting point, the distribution on the number of steps and the stochastic gradient oracle are identical). Stop$(n/2)$-PNSGD$(S,w_{0},\eta,\sigma)$ can be seen as running Stop-PNSGD on $n/2$ points starting from some random point $W_{0}$ (where $W_{0}$ is the output of PNSGD on the first $n/2$ points). The utility guarantees for Stop-PNSGD hold for an arbitrary starting point and therefore the utility guarantees for Stop$(n/2)$-PNSGD are the same as those for Stop-PNSGD (Theorem 29) for a dataset consisting of $n/2$ points. ∎

3 Utility of Public Data

In a variety of settings the algorithm may also have access to a relatively small amount of data from the same distribution that do not require privacy protection. We demonstrate that by using the non-private data points at the end of the training process our per-index privacy guarantees directly lead to substantially improved utility guarantees. In particular, given $\Theta(d\ln(1/\delta)/\varepsilon^{2})$ non-private points the utility guarantees of our algorithm match (up to a constant factor) those of non-private learning on the entire dataset.

4 Multiple Convex Optimizations

For simplicity of presentation we will state this result for solving a fixed set of $k$ tasks with identical parameters. Composition properties of RDP imply that the bounds can be extended to using problems with different parameters and also allow choosing the tasks in an adaptive way (i.e., after observing the outcome of the previous tasks).

By the composition properties of RDP and Theorem 26, we have that the output of $k$ executions of Stop-PNSGD$(S,w_{0},\eta,\sigma)$ satisfies $\left(\alpha,\frac{4k\alpha L^{2}\cdot\ln n}{n\sigma^{2}}\right)$-RDP, whenever $\sigma\geq L\sqrt{2(\alpha-1)\alpha}$. We let $\alpha\doteq\frac{\sigma\sqrt{\ln(1/\delta)}}{L\sqrt{q}}$. Note that this ensures that

Note that for our choice of $\sigma=\frac{4L\sqrt{q\ln(1/\delta)}}{\varepsilon}$ we get that $\alpha=\frac{4\ln(1/\delta)}{\varepsilon}>2$.

By 14, our bound on RDP implies $(\varepsilon,\delta)$-DP as

Given the value of $\sigma$, we obtain the bound on the excess population loss from Theorem 28 in the same way as in the proof of Theorem 29. ∎

5 Removing the Smoothness Assumption

In this section we show that our assumption on the smoothness of the loss function $f({w},x)$ can effectively be removed in several of our applications. We do this by convolving $f$ with the Gaussian distribution of an appropriate variance. While smoothing a non-smooth objective is a standard technique in optimization (e.g., see ) we are not aware of bounds that are stated in the form we need. Specifically, $f$ may be approximated with its convex Lipschitz extension whose existence and properties are established by the following theorem (its proof is deferred to Appendix C):

In our Theorems 30 and 32 we use $\eta\leq\frac{R\varepsilon}{L\sqrt{n\ln(1/\delta)}}$. Therefore we need our smoothness parameter $\beta\leq 2\frac{L\sqrt{n\ln(1/\delta)}}{R\varepsilon}$. This means that it suffices to set $\lambda\doteq\frac{R\varepsilon}{2\sqrt{n\ln(1/\delta)}}$, which by Theorem 33, leads to approximation error of $\frac{LR\varepsilon\sqrt{d}}{2\sqrt{n\ln(1/\delta)}}$. Note that this additional error is dominated by the excess population loss whenever $\ln(1/\delta)\geq\varepsilon$ (which is typically the case). For completeness, we state the immediate corollary of Theorem 33 for per-person privacy formally.

Acknowledgements

We thank Úlfar Erlingsson and Tomer Koren for useful suggestions and insightful discussions of this work.

References

Appendix A Contractivity of Gradient Descent for Smooth Functions

Contractivity of a Gradient Descent step for a smooth convex function is a well-known result in convex optimization (see, e.g., Nesterov ). We reproduce a proof below.

is contractive as long as $\eta<2/\beta$.

for some $z$ on the line joining $w$ and $w^{\prime}$. By smoothness and convexity, the Hessian has eigenvalues in $[0,\beta]$. Thus,

Appendix B Analyzing Multiple-Epoch SGD

In this section, we show how our techniques can be used to prove privacy for a fixed-ordering version of a multiple-epoch SGD algorithm for minimizing a convex $\beta$-smooth loss function where $\eta\leq 2/\beta$. Formally, we consider the following algorithm:

An algorithm similar to this was analyzed by who used privacy amplification by sampling to prove that it satisfies $(\varepsilon,\delta)$-DP when $\sigma^{2}=\frac{32L^{2}\ln(n/\delta)\ln(1/\delta)}{\varepsilon^{2}}$. This analysis can be improved using the techniques of to ensure that $\sigma=\Theta\left(\frac{L\sqrt{\ln(1/\delta)}}{\varepsilon}\right)$ suffices for a suitable range of $\varepsilon$.

The privacy bound for Algorithm 2 follows in a rather straightforward way from Theorem 22.

Under the same assumptions as Theorem 23, projected noisy multiple-epoch SGD (Algorithm 2) satisfies $\left(\alpha,\frac{4\alpha L^{2}}{\sigma^{2}}\right)$-RDP.

Let $S$ and $S^{\prime}$ be two datasets that differ in the $i$’th example. Algorithm 2 run on $S$ (resp., $S^{\prime}$) defines a contractive noise iteration $\mbox{CNI}(X_{0},\{\psi_{t}\},\{\zeta_{t}\})$ (resp., $\mbox{CNI}(X_{0},\{\psi^{\prime}_{t}\},\{\zeta_{t}\})$). Letting $s_{t}\doteq 2\eta L$ if $t\equiv i\pmod{n}$ and 0 otherwise, we observe that $\sup_{w}\|\psi_{t}(w)-\psi^{\prime}_{t}(w)\|\leq s_{t}$ for $t\in[n^{2}]$.

It follows that Algorithm 2 satisfies $(\alpha,\frac{4\alpha L^{2}}{\sigma^{2}})$-RDP as claimed. ∎

Applying 14, with $\alpha=\frac{2\ln(1/\delta)}{\varepsilon}$ and additionally assuming that $\alpha\geq 5$, we conclude that the projected noisy multiple-epoch SGD satisfies $(\varepsilon,\delta)$-DP for $\sigma=\frac{5L\sqrt{\ln(1/\delta)}}{\varepsilon}$. Compared to the approach from , we have a significantly cleaner proof with fewer assumptions on $\sigma$. We remark that the two algorithms differ slightly. Here we fix an ordering and make $n$ passes over the data points in the same order, whereas the algorithm in takes $n^{2}$ steps, each on a uniformly random data point. To obtain utility guarantees for this algorithm one can appeal to standard regret bounds for online algorithms (e.g., see Bubeck ). These bounds imply an upper bound on the empirical loss of the randomly chosen iterate. To obtain bounds on the population loss one can appeal to the generalization properties of differential privacy .

Appendix C Smoothing via Convolution with the Gaussian Kernel

In this section we prove Theorem 33, stated earlier in Section 5.5.

The function $\hat{f}$ satisfies the following properties:

Lipschitzness and convexity: Since the function $f({w})$ is convex and $L$-Lipschitz, the Lipschitz extension function $h({w})$ is also convex and $L$-Lipschitz. Hence, $\hat{f}({w})$ is both convex and $L$-Lipschitz as it is defined as a convolution of $h({w})$ with the Gaussian probability kernel.

Let $p_{Z}$ denote the probability density function of the random variable $Z$. By definition,

where ${\sf TV}$ refers to the total variation distance. To complete the proof note that by Pinsker’s inequality,

Approximation error: For all ${w}\in\mathcal{K}$, $\left|\hat{f}({w})-f({w})\right|\leq L\lambda\sqrt{d}$. By definition,

Together these properties establish the claim of the theorem. ∎