Chapter 6: Private Optimization

Consider a data set D = {d₁,…,d_n} drawn from some domain $D*$⁠, and a loss function $ℒ(θ;D)=∑i=1nℓ(θ;di)$⁠, where θ ∈ ℝ^p is the model, and $ℓ:ℝp×D$ is the loss function on individual data samples. In this chapter, we will focus on algorithms for estimating (6.1) while preserving (ε,δ)-differential privacy, where $C⊆ℝp$ is the constraint set

The above formulation is often called the Empirical Risk Minization (ERM), and is powerful enough to capture a large class of learning tasks. For example, i) in linear regression the data record is d_i = (x_i,y_i) (with x_i ∈ ℝ^d being the feature vector, and y_i being the response) and the loss function is ℓ(θ;d_i) = (y_i−⟨x_i,θ⟩)², ii) in logistic regression the loss function is $ℓ(θ;di)=ln(1+e−yi〈xi,θ〉)$⁠, and iii) in the case of deep networks with binary cross entropy, the loss function is $ℓ(θ;di)=ln(1+e−yi·hθ(xi))$⁠, where h_θ (⋅) is the network parameterized by the model weights θ. ERM frameworks also allow a direct a direct way of minimizing the population loss (a.k.a. true risk or the test accuracy), i.e,

In (6.2), $T$ is a distribution over the domain $D$⁠. If the data set D is drawn i.i.d. from the distribution $T$⁠, it is then not hard to show by the so-called uniform convergence theorem [SSSS09] that the following holds for any $θ∈C$⁠, with probability at least 1 − β over the randomness of D. In (6.3), L is the ℓ₂-Lipschitz constant (Defnition 6.1) on the individual loss functions ℓ(⋅;⋅) w.r.t. the first parameter, and $‖C‖2$ is the ℓ₂-diameter of the constraint set $C$⁠. Hence, if one can estimate θ* well with differential privacy, then it immediately implies a strong bound on the true riskⁱ. In this chapter, we will hence focus on solving the ERM problem (defined in (6.1)) with differential privacy.

To begin with, we need the following properties of (convex) function that we will be using throughout the chapter. In each of the algorithms, and the corresponding analysis, we will explicitly state which properties of the function we are assuming.

Definition 6.1 (L-Lipschitz continuity). A function$f:C→ℝ$is L-Lipschitz w.r.t. the ℓ_q-norm if the following is true for any$θ1,θ2∈C$⁠:

Unless mentioned explicitly, we will assume Lipschitzness w.r.t. the ℓ₂-norm.

Definition 6.2 (γ-Smoothness). A function$f:C→ℝ$is γ-smooth, if the following is true for any$θ1,θ2∈C$ :

Definition 6.3 (Δ-Strong convexity). A function$f:C→ℝ$is Δ-strongly convex, if the following is true for any$θ1,θ2∈C$and for any α ∈ (0,1] :

If Δ = 0, we say that the function f is convex. If f is differentiable, we can replace the condition in (6.6) with,

The chapter is organized as follows. We will first discuss DP-ERM algorithms that satisfy pure ε-differential privacy. The specific algorithms we will discuss are i) Exponential mechanism [MT07; BST14], and ii) Objective perturbation [CMS11; KST12]. Then, we will move on to discuss DP-ERM algorithms that satisfy (ε,δ) differential privacy. There, we will focus our attention on a couple of algorithms, namely, differentially private (stochastic) gradient descent (DP-SGD) [BST14; Aba+16; TTZ14a] and differentially private follow the regularized leader (DPFTRL) [Kai+21b; ST13a; AS17]. We will then provide a (ε,δ)-differentially private algorithm for the high-dimensional setting where the dimensionality p≫n. This algorithm is called the private Frank-Wolfe [TTZ15]. Finally, we will demonstrate how (and when) these algorithms provide optimal privacy/utility trade-offs by visiting some of the lower bounding techniques in DP-ERM.

Note: All the results in this section are in the add/remove model of differential privacy (see Section 1.4.1 of Chapter 1). They can be easily translated to the replacement model by paying a factor of two in the privacy parameters via standard methods [DR+14].

In this section, we provide algorithms for solving the ERM problem in (6.1) under ε-differential privacy.

The first algorithm we look at is based on the classic exponential mechanism [MT07]. Later we will see that this algorithm is indeed optimal for the case when for any data sample $d∈D$⁠, the loss function ℓ(θ;d) is convex and L-Lipschitz in its first parameter, within the convex constraint set $C$⁠.

Algorithm 1$Aexp−samp$⁠: Exponential mechanism based convex optimization

Require: Data set of size n: D, loss function: ℓ, constraint set: $C$⁠, ℓ₂-Lipschitz constant: L, privacy parameter: ε

1. $ℒ(θ;D)←∑i=1nℓ(θ;di)$⁠.

2. Sample and output a point θ^priv from the constraint set $C$ w.p. ∝ $exp(−ε2L‖C‖2·ℒ(θ;D))$⁠.

First, we show that Algorithm $Aexp-samp$ is ε-differentially private. The proof will go via fairly standard arguments used in analyzing exponential mechanism. A vanilla analysis of the sampling distribution in the algorithm would require the loss ℓ(θ;⋅) to be bounded in terms of its value. However, by using a fixed anchoring point θ₀, it suffices to operate with the Lipschitzness assumption.

Theorem 6.4.Algorithm 1 is ε-differentially private.

Proof. Consider the kernel $μ(θ;D)=exp(−ε2L‖C‖2·ℒ(θ;D))$ of the probability distribution in Algorithm $Aexp-samp$⁠. Let $θ0∈C$ be any fixed model parameter. Now, notice that the sampling distribution generated by μ(θ) is identical to the distribution generated by the following kernel: $μ^(θ;D)=exp(−ε2L‖C‖2·(ℒ(θ;D)−ℒ(θ0;D)))$⁠. Hence, in the rest of the proof we will only consider $μ^(θ;D)$⁠.

Consider any two neighboring data sets D and D′. Let d be the data record on which they differ. W.l.o.g., data set D has data record d, and D′ does not. For any θ, θ₀, we have the following.

To ensure differential privacy we need to make sure that for any measurable set $S⊆C$⁠, the following is true.

By (6.8), for any $θ∈C,e−ε/2≤μ(θ;D)μ(θ;D′)≤e−ε/2$⁠. Hence, the condition in (6.9) is immediately satisfied. This completes the proof.

In Theorem 6.5 we show that for Algorithm 1, the excess empirical risk is bounded by $O(pL‖C‖2ε)$⁠. In the proof, we will heavily use convexity property of the loss function ℓ(⋅;⋅) to show this bound.

Note: The following simpler bound is easy to prove without relying on convexity: Let $B$ be a unit ball centered at the origin. If $rB⊆C$⁠, then the excess empirical risk is bounded by $O(pL‖C‖2ε·ln(εnL‖C‖2r))$⁠. We leave the proof of this statement as an exercise. This result is significant because it shows that one can obtain both DP guarantee, and strong excess empirical risk bounds just by assuming the loss function to be L-Lipschitz within the constraint set.

Theorem 6.5.Let θ^priv be the output of Algorithm 1 above. Then, we have the following guarantee on the expected excess risk. (The expectation is over the randomness of the algorithm.)

Here, $θ*∈argminθ∈Cℒ(θ;D)$⁠.

Proof. Consider any differential cone Ω centered at θ*. We will first bound the excess empirical risk, conditioned on θ^priv ∈ Ω. Since the bound will be true for any Ω, by the law of total expectation, the guarantee in the theorem statement immediately follows.

Let Γ ≥ 0 be a fixed parameter to be defined later. For the purpose of brevity, let $f(θ)=ℒ(θ;D)−ℒ(θ*;D)$⁠. We first split Ω into different levels A_i’s, where each A_i is defined as follows:

Notice that A₁ corresponds to the region, where the excess empirical risk f(θ) ≤ Γ. Instead of directly computing the probability of θ^priv lying outside A₁, we will individually compute the probability of θ^priv being in each of A_i, i > 1 individually, and then take an union bound over these probabilities. Typically, this line of argument is referred to as the “peeling argument”.

Since Ω is a differential cone, and f(θ) is continuous on $C$⁠, it follows that within $Ω∩C$⁠, f(θ) only depends on ‖θ − θ* ‖₂. Centered at θ*, let r₁, r₂,… be the end boundaries for the sets A₁, A₂,… respectively. Hence, one can redefine (6.10) as follows.

In Claim 6.6 we show that due to convexity of f(θ), the gap between successive r_i’s (i.e., r_i − r_i−1) is decreasing for i ≥ 3.

Claim 6.6.Convexity of f(θ) implies that r_i − r_i−1 ≤ r_i−1 − r_i−2for all i ≥ 3.

Proof. Since θ* is the minimizer of f(θ) within the constraint set $C$⁠, and since f(θ) is convex, we have the following any two $θ1,θ2∈C∩Ω$ with f(θ₂) ≥ f(θ₁) : ‖θ₂ − θ*‖₂ ≥ ‖θ₁ − θ*‖₂. This immediately implies the claim.

Now, recall the volume of any of the A_i is given by $Vol(Ai)= const ·∫ri−1rirp−1dr$⁠. Hence, we have the following:

The last two inequalities in (6.12) follows directly from Claim 6.6. Recall the definition of Γ. Hence we have the following for the excess empirical risk f(θ^priv) ≥ 4Γ, conditioned on $θpriv ∈C∩Ω$⁠. In the following, we remove the conditioning for brevity.

The last inequality in (6.14) follows from the fact that $(i−1)p≤3p·(2i−1)p$ for all i ≥ 4. Hence for every t > 0, if we choose $Γ=2L‖C‖2ε·((p+1)ln(3)+t)$⁠, then we have the following.

Since (6.15) is true for all t ≥ 0, we have the required bound as a corollary.

It is not obvious how to implement Algorithm 1 efficiently. Even before that we need to decide on how we measure computational complexity. In this section, and in the rest of the chapter, we will measure the complexity in terms of number of oracle calls to the gradients of individual loss function ▽ℓ(θ;d). This is consistent with the standard optimization literature [Bub15].

Since the loss functions ℓ(⋅;⋅) are convex in the first parameter, Step 2 of Algorithm 1 results in sampling from a log-concave distribution. Classic results from sampling theory [LV06] allows sampling efficiently from these distribution, albeit the convergence is usually in the total-variation-distance (TVD). In order to guarantee ε-differential privacy, it is necessary to have the sampling distribution to converge to the true distribution induced by Step 2 of Algorithm 1 in the ℓ_∞-distance. [BST14], which got improved by [MV21], provides algorithms with ℓ_∞-distance convergence and oracle complexity of $O(nε poly (p))$⁠.

While the utility analysis of Algorithm 1 heavily relies on convexity, the privacy analysis does not. The privacy analysis only assumes that ℓ(θ;d) is L-Lipschitz w.r.t. the ℓ₂-norm. As it will be more obvious in the later parts of this chapter, such a property is rare in algorithms designed for DP optimization. However, the general philosophy regarding the design of DP optimization algorithms that the reader should keep in mind is that, it is always desirable that the privacy property of an algorithm should rely on minimal set of assumptions, which in particular should be enforceable/efficiently testable. It is okay to make stronger assumptions for the corresponding utility analysis. Convexity, unfortunately, is not an efficiently testable property in general.

The utility bound obtained in Theorem 6.5 is indeed optimal. One can use use standard machinery of the so-called “packing argument” [HT10; BST14] to achieve the lower bound.

While Algorithm $Aexp−samp$ is optimal for pure ε-DP (i.e., with δ = 0), any natural extension of $Aexp−samp$ is not known to be optimal in the case of (ε,δ)-DP. In this section we will see an algorithm that is simultaneously optimal for both ε DP and (ε,δ)-DP. Additionally, this algorithm will be computationally efficient in regards to oracle complexity. The algorithm is called objective perturbation (Algorithm 2) [CMS11; KST12]. Along with the loss function ℓ(θ;⋅) being L-Lipschitz w.r.t. ℓ₂-norm, it requires two additional properties: i) ℓ(θ;⋅) should be twice continuously differentiable, ii) $λmax(∇θ2ℓ(θ;·))≤λmax$⁠, and iii)

Algorithm 2$Aobj−pert$⁠: Objective Perturbation

Require: Data set of size n: D, loss function: ℓ, ℓ₂-Lipschitz constant: L, constraint set: $C$⁠, ℓ₂-regularization: Δ, noise multiplier: λ.

1. $ℒ(θ;D)←∑i=1nℓ(θ;di)$⁠.

2. $θpriv ←argminθ∈Cℒ(θ;D)+Δ2‖θ‖22+〈b,θ〉$⁠, where $b~G(L·λ)$ and $G(σ):=exp(−‖x‖2σ)∫x∈ℝdexp(−‖x‖2σ)$⁠.

3. Outputθ^priv.

In Theorem 6.7 we provide the privacy guarantee for Algorithm 2. Notice that the regularization parameter Δ has to be lower bounded to ensure DP. As it will be clear later, this lower bound is much lower than that what one would set to get an optimal excess empirical risk bound. In Theorem 6.7, we only provide the privacy analysis for the setting where the constraint set $C=ℝp$⁠. While the privacy guarantee holds for any convex constraint set $C⊆ℝp$⁠, the proof is much more involved and requires measure theoretic arguments. We encourage curious readers to look at [KST12] for more details.

The proof of Theorem 6.7 will provide a curious connection to exponential mechanism, which was not known earlier, prior to this book chapter.

Theorem 6.7.Let the loss function ℓ(θ; d) be twice continuously differentiable for all$θ∈C$⁠, and for all$d∈D$⁠. Furthermore, $∀θ∈C,∀d∈D:‖∇ℓ(θ;d)‖2≤L,λmax(∇2ℓ(θ;d))≤λmax$⁠, and$rank(∇θ2ℓ(θ;d))≤r$⁠. If we set the noise multiplier λ = 2/ε, and the regularization parameter$Δ≥rλmax1−exp(−ε/2),$⁠, then Algorithm 2 (Algorithm$Aobj-pert$) satisfies ε-differential privacy.

Proof for the special case when$C=ℝp$⁠. Consider the regularized loss function $J(θ;D)=ℒ(θ;D)+Δ2‖θ‖22$⁠. Consider the following probability distribution:

Additionally, let $bD(θ)=∇J(θ;D)$⁠. Since, $J(θ;D)$ is a strictly convex function, the mapping is a bijection. Let ν_D(b) be the induced distribution on the random variable b_D(θ). By the Radon-Nikodym theorem [Bil08], we have the following:

Notice that the induced distribution v_D(b) is independent of the data set D. Hence, from here on we will remove the subscript D in the rest of the proof, and refer the distribution as ν(b). Going back to (6.16), we want to understand the differential privacy property of μ_D(θ). For two neighboring data sets D and D′, and at a given θ, we have the following:

We can easily bound term A in (6.18) by the ℓ₂-Lipschitz property of the loss function ℓ(⋅;⋅). By definition of b_D(θ), we have the following:

Therefore, by triangle inequality, the term A in (6.18) is upper bounded by $exp(ε2)$⁠. Next, we will bound term B in (6.18). For the purpose of brevity, let $W=∇2J(θ;D′)$ and $W′=∇2J(θ;D′)$⁠. We prove the following claim.

Claim 6.8.Under the assumptions of Theorem 6.7, we have$det(W′)det(W)≤ΔΔ−rλmax$⁠.

Proof. Since the rank of any ▽²ℓ(θ; d) is upper bounded by r, it follows that the matrix E = W′ − W has rank at most r. Let σ₁ ≥ σ₂ ≥ … ≥ σ_p ≥ Δ be the eigenvalues of the matrix W, and $σ1′≥σ2′≥…≥σp′≥Δ$ correspondingly for W′. Recall that $det(W)=∏i=1pσi$⁠. Therefore, we have the following.

The inequality in (6.20) follows from the fact that each of the eigenvalues are lower bounded by Δ. The first inequality in (6.22) follows from the fact that $∀i∈[p],|σi′−σi|≤rλmax$⁠. The last inequality in (6.22) follows from fact that Δ ≥ rλ_max. This completes the proof.

Since by assumption $Δ≥rλmax1−exp(−ε/2)$⁠, term B in (6.18) is upper bounded by $exp(ε2)$⁠. Hence, we have proved that the sampling distribution in (6.16) satisfies ε-differential privacy. In the rest of the proof we will show that the distribution of θ^priv in Algorithm $Aobj-pert$ is identical to (6.16).

Since we are operating the in the unconstrained space, i.e., $C=ℝd$⁠, we have the following:

By using Radon-Nikodym theorem [Bil08], we have the following distribution on θ^priv :

Here, v(b) is the is the pdf of the distribution on the random variable b, which is proportional to $exp(−ε2L·‖b‖2)$⁠. This completes the proof.

Analogous to Theorem 6.5, we provide the utility guarantee of Algorithm $Aobj−pert$ in Theorem 6.9.

Theorem 6.9.Recall all the parameter choices in Theorem 6.7 for Algorithm 2 (Algorithm$Aobj−pert$). Additionally, assume$rλmax1−exp(−ε/2)≤32·pLε‖C‖2$⁠, where$rank(∇θ2ℓ(θ;d))≤r,∀θ∈C,d∈D$⁠, and$0∈C$⁠. Then, under appropriate choice of the regularization parameter Δ, the following is true:

Proof. Consider the regularized loss function $J(θ;D)=ℒ(θ;D)+Δ2‖θ‖22$⁠, and the noisy regularized loss function $Jnoisy (θ;D)=J(θ;D)+〈b,θ〉$⁠. Let the following be the minimizers for each of the losses: $θpriv =argminθ∈CJnoisy (θ;D)$⁠, $θ^=argminθ∈CJ(θ;D)$⁠, and $θ*=ϵargminθ∈Cℒ(θ;D)$⁠.

By the strong convexity property of $Jnoisy (θ;D)$⁠, the following is true:

In the above (6.28) follows from the fact that $(J(θ^;D)−J(θpriv ;D))≤0$⁠, and the inequality in (6.29) follows via Cauchy-Schwartz. Using (6.28) we immediately have the following inequality, which bounds the difference $J(θpriv ;D)−J(θ^;D)$⁠.

Now, we finally bound $ℒ(θpriv ;D)−ℒ(θ*;D)$ in terms of ∥b∥₂. We have the following:

The first inequality in (6.36) follows from the fact that $J(θ;D)≥J(θ^;D),∀θ∈C$⁠, and the second inequality follows from (6.33). Taking expectation on both sides of (6.36), and optimizing for $Δ=2·E[‖b‖22]‖C‖2$⁠, we have the following:

Given the distribution on b in Algorithm $Aobj−pert$⁠, it is not hard to observe that $‖b‖2~Gamma(p,ε2L)$⁠. Therefore, by standard properties of Gamma distribution, we have $E[‖b‖22]=4pL2ε2+4p2L2ε2≤8p2L2ε2.$⁠. Plugging in this bound in (6.37) completes the proof.

For the privacy analysis in Theorem 6.7, we made these assumptions, beyond just assuming that the loss function ℓ(⋅;⋅) is ℓ₂-Lipschitz bounded. In the following, we discuss the necessity of these assumptions.

Consider a simple problem where the data sample d_i ∈ ℝ, and the loss function ℓ(θ;d_i) = |θ − d_i|, i.e., the ERM problem $argminθ∈ℝ∑i=1n|θ−di|$ is estimating the median of the data set D = {d₁,…,d_n}, with each d_i being unique. For brevity, assume n is odd, so there is a unique median. Clearly, the function is nondifferentiable at θ ∈ {d₁,…,d_n}, and hence non-smooth at those points. We focus on the loss function ℒ(θ; D) at θ = d_med. Notice that the slope of $ℒ(θ;D)$ in the vicinity of d_med is either −1 or +1 . Now, since |b| exponentially distributed (as p = 1), we have Pr[|b| ≤ 1/2] = 1 − exp(−ε/4). If the strong convexity term Δ = 0 in Algorithm $Aobj−pert$⁠, then clearly, with probability at least 1−exp(−ε/4), Algorithm $Aobj−pert$ outputs θ^priv = d_med. As d_med is a data point in the data set D, it is a direct violation of ε-DP. One might argue that non-zero value of strong convexity parameter Δ will improve the situation. To move the minimizer away from d_med, it is necessary that $Δ≥12|dmed|$ to ensure that the absolute value of the slope of the regularizer at d_med is at least 1/2. Since, d_med can be arbitrary close to zero, Δ has to be potentially infinite, which in turn will destroy any utility of the algorithm. This argument shows that smoothness is a necessary condition of Algorithm $Aobj−pert$ to ensure DP.

While convexity is a necessary condition for the proof of privacy in Algorithm $Aobj−pert$⁠, it is possible that one may be able to design variants of $Aobj−pert$ that does not rely on convexity for privacy. Curiously, if one observes the sampling distribution of θ^priv in (6.16), then it would be obvious that removing the scaling term with $(∇2J(θ;D))$ with result in a sampling distribution that can proven to ensure ε-DP without relying on convexity, or even smoothness. (The proof will be a direct extension of the privacy theorem for Algorithm $Aexp−samp$⁠, i.e., Theorem 6.4.) It is an active area of research to design variants of Objective perturbation to be amenable to non-convex losses [NRVW20]. There is not much of an intuition there whether the condition on the regularization parameter Δ should necessarily depend on the rank of the Hessian (r). It may be a slack in the analysis of Theorem 6.7.

While Algorithm $Aobj−pert$ is a mathematically well-defined object, it is unclear how to implement it in practice. In particular, for arbitrary convex losses, any reasonable optimization procedure will not reach the true minimizer θ^priv with finite oracle complexity. Given a pre-specified parameter γ, there are optimization methods [Bub15] that will be ensure that they will output a model θ^† s.t. $‖∇Jnoisy (θ†;D)‖2≤γ$ with O(n/poly(γ)) oracle complexity. (Here $Jnoisy (θ;D)=ℒ(θ;D)+Δ2‖θ‖22+〈b,θ〉$⁠.) In the unconstrained setting $C=ℝp$⁠, because of Δ-strong convexity of $Jnoisy$⁠, it implies $‖θ†−θpriv ‖2=O(γΔ)$⁠. Therefore, one can add an additional DP-friendly noise with standard deviation $O(γΔε)$⁠, to cover for $‖θ†−θpriv ‖2$⁠. For the constrained setting, one can first perform the above procedure on the unconstrained problem, and then project onto the constraint set $C$⁠. For a detailed discussion on this approach, see [Iye+19; BFTT19].

Theorem 6.9 is stated for just Lipschitz convex functions. However, the proof essentially goes via bounding the excess empirical risk for the strongly convex objective $J(θ;D)=ℒ(θ;D)+Δ2‖θ‖22$ (see (6.33)). Using this machinery, one can obtain an excess empirical risk of $O(L2p2Δnε2)$⁠, if each of the individual loss function ℓ(θ; d) is assumed to be Δ-strongly convex. Notice that this bound is tight [BST14]. While Algorithm $Aobj−pert$ requires assumptions like smoothness for the privacy proof, a variant of the exponential mechanism $Aexp−samp$ can also achieve a similar bound, albeit a more complicated analysis. (See Section 4 of [BST14] for more details.)

We will discuss algorithms that are specifically designed to obtain strong privacy/utility trade-offs in the (ε, δ)-DP setting. But it is worth mentioning that Algorithm $Aobj−pert$ can be shown to provide strong privacy/utility trade-offs in the (ε,δ)-DP setting too. The only change that is needed is the following: Change the noise distribution of b to $N(0,O(Lln(1/δ)ε)2·Ip)$⁠. Since Gaussian distribution has a tighter concentration, the excess empirical risk becomes $O(L‖C‖2·pln(1/δ)ε)$⁠. This bound is also known to be tight [BST14]. In Section 6.3 we will study algorithms that achieve similar bounds, however, do not require assumptions like smoothness, or bounded rank of the Hessian. Also, the privacy guarantee of these algorithms will not depend on the convexity of the loss function.

In this section we will look at algorithms that achieve optimal privacy/utility tradeoffs under (ε,δ)-DP, while assuming the loss function ℓ(θ;d) being L-Lipschitz in θ, w.r.t. ℓ₂-norm. As we discussed earlier $Aobj−pert$ achieves similar bounds, but require additional assumptions like smoothness, and bounded rank of the Hessian. Algorithmically, the main difference from Algorithms 1 or Algorithm 2 is that we will not argue privacy for the final model θ^priv. Rather, the privacy guarantee will hold for the complete optimization path (i.e., the intermediate models that will get generated. This eventually will imply the (ε, δ)-DP guarantee of the final model θ^priv. Since we “privatize” the complete optimization path, as opposed to arguing privacy for the final model θ^priv, the resulting algorithms operate under weaker privacy assumptions.

DP-SGD [SCS13; BST14; Aba+16] is currently the most widely-used differentially private learning algorithm in practice, with at least two large-scale open source implementations TensorFlow-Privacy [Aba+15], and Opacus [You+21]. Along with its practical success, it also provides optimal privacy/utility trade-offs analytically. While there are various variants of DP-SGD in the literature [SSTT21], the one we will primarily focus on in this chapter is the full-gradient descent version. The presentation of the algorithm (Algorithm 3) will be primarily based on [SSTT21].

There are a few distinctive properties of the algorithm. First, notice the term clipping norm. Unlike Algorithms $Aexp−samp$ and $Aobj−pert$ above, Algorithm $ADP−SGD$ does not assume that the loss function ℓ(θ; d) is ℓ₂-Lipschitz. Rather via the clipping norm bound, in Step 3, it enforces that the ℓ₂-norm of the gradientⁱⁱ of any individual ℓ(θ;d_i) is bounded by L. Second, as we mentioned earlier,

Algorithm 3$ADP−SGD$⁠: Differentially private stochastic gradient descent (DP-SGD)

Require: Data set D = {d₁,…,d_n}, loss function: $ℓ:Rp×D→R$⁠, clipping norm: L, constraint set: $C⊆Rp$⁠, number of iterations: T, noise multiplier: λ, learning rate: η.

1. θ₀ ← 0.

2. fort = 0, …, T − 1 do

3. $gt=∑i=1nclip(∇ℓ(θt;di))$⁠, where $clip(v)=v·min{1,L‖v‖2}$⁠.

4. $θt+1←ΠC(θt−η(gt+N(0,σ2)))$⁠, where $ΠC(v)=argminθ∈C‖v−θ‖2$ and σ = L · λ.

5. end for

6. return$θpriv =1T∑t=1Tθt$⁠.

we will show that the entire optimization path {θ₀,…, θ_T} is (ε,δ)-DP. Third, in Step 6 we output the average of all the models. One can provide similar utility/privacy trade-off for the last iterate too, i.e., θ_T[BST14]. We chose the average model purely for the simplicity of analysis. Fourth, unlike traditional SGD (stochastic gradient descent) [Bub15], where each g_t is computed on a minibatch of examples from the training set D, in Algorithm $ADP−SGD$ we use the complete gradient. As we will discuss later, the privacy/utility trade-off that we will obtain for Algorithm $ADP−SGD$ can also be obtained via using a minibatch of size one in each step t ∈ [T], drawn i.i.d. from D. For the purpose of brevity, we will provide the main analysis in the context of full-batch gradient.

In the following, we first provide the privacy guarantee for Algorithm $ADP−SGD$⁠.

Theorem 6.10.If we choose the noise multiplier$λ=2T(ln(1/δ)+ε)ε$⁠, then Algorithm$ADP−SGD$(Algorithm 3) satisfies (ε,δ)-differential privacy.

Proof. Consider the estimation of any g_t in Step 3 of Algorithm $ADP−SGD$⁠, given θ_t. Let D and D′ be two neighboring data sets, and g_t and $gt′$ be the corresponding gradient estimates at θ_t. Due to the clip(⋅) function, we have the following: $‖gt−gt′‖2≤L$⁠. Therefore, we can think g_t:t ∈ [T] to be a set of T adaptively chosen queries on the data set D, with each query having ℓ₂-sensitivity of L. By standard composition property of Gaussian mechanism (described in Part I of the book), if we choose the noise scale to be $λ=2T(ln(1/δ)+ε)ε$⁠, then the set of {θ₁,…, θ_t} satisfies (ε, δ)-differential privacy.

Next, we move on to prove the utility guarantee of Algorithm $ADP−SGD$⁠. We show the following:

Theorem 6.11.Assume that ∥▽ℓ(θ;d)∥₂ ≤ L for all$d∈D$and$θ∈C$⁠, and$0∈C$Under appropriate choice of the learning rate η, and setting the number of steps$T=n2ε2p$and the noise multiplier$λ=2T(ln(1/δ)+ε)ε$⁠, we have the following:

Proof. We prove the theorem via the standard template for analyzing SGD methods [Bub15]. Recall $θpriv =1T∑t=1Tθt$⁠, where {θ₁,…, θ_T} are the models in each iterate of DP-GD. By convexity, and the standard linearization trick in convex optimization [Bub15], we have:

Let b_t is the Gaussian noise vector added at time step t To bound the error in (6.38), we will use a potential argument w.r.t. the potential function

Recall the update step in Algorithm $ADP−SGD:θt+1←ΠC(θt−η(∇ℒ(θt;D)+bt))$⁠. Since, by assumption the loss function ℓ(θ;d) is ℓ₂-Lipschitz bounded, clip (⋅) does not have any effect. We get the following by simple algebraic manipulation:

where (6.40) follows from the fact that ℓ₂-projection onto a convex constraint set $C$ always reduces the ℓ₂-distance, and (6.43) follows because $bt~N(0,L2λ2)p$ and thus $Ebt[‖bt‖22]=p·L2λ2$⁠. Rearranging the terms in (6.43), we have the following,

Summing up (6.44) for all t ∈ [T], averaging over the T iterations, and combining with (6.38), we get:

Setting η to minimize the RHS, we have

where the equality in (6.47) follows by plugging in $λ=2T(ln(1/δ)+ε)ε$⁠. Now, setting $T=n2ε2p$⁠, we have

This completes the proof.

Notice, Algorithm $ADP−SGD$ reaches an average excess empirical risk of $O˜(pεn)$ in $T=n2ε2p$ steps. For non-smooth, and non-strongly convex losses, this rate of convergence is tight for SGD based methods (up to dependence on dimensionality), i.e., in Θ(1/α²) steps, one can get to an error of α. This demonstrates an important phenomenon. DP does not slow down the rate of convergence in comparison to a non-private SGD method up to the error allowed under privacy constraints. Furthermore, even if we set T → ∞, under appropriate choice of the learning rate η, the excess empirical risk remains the same. This implies, Algorithm $ADP−SGD$ does not need the number of steps T to tuned for optimal privacy/utility trade-off as long as $T≥n2ε2p$⁠. This property is not true in general for iterative DP optimization methods.

The oracle complexity of Algorithm $ADP−SGD$ (for achieving the excess empirical risk in Theorem 6.11) is $n3ε2p$⁠. This because in each of the T steps, Algorithm $ADP−SGD$ performs n gradient evaluations.

One can improve the oracle complexity of Algorithm $ADP−SGD$ via special tool in the DP literature called, privacy amplification by sampling [Kas+08]. Informally, privacy amplification by sampling says that if an algorithm $A$ is $ε0≤12−DP$-DP on a data set D, then on a data set D_samp, where each entry of D is sampled with probability q, $A(Dsamp )$ satisfies O(q⋅ε₀)-DP. One can use this tool to show that essentially at the same level of noise as in Step 4 of Algorithm $ADP−SGD$⁠, one can use g_t = n ⋅ clip(▽ℓ(θ_t;d)) (in Step 3) with d sampled uniformly at random from the data D, independently at each time step T. Since, modulo clipping, the new g_t is an unbiased estimator of the gradient $∇ℒ(θt;D)$⁠, the utility guarantee in Theorem 6.11 remain unchanged. This reduces the oracle complexity by a factor of n for Algorithm $ADP−SGD$⁠. For a focused analysis of privacy amplification via sampling, the reader is referred to Chapter 3.6.