Private Stochastic Convex Optimization with Optimal Rates

Introduction

The first work to address the population loss for SCO with differential privacy (DP-SCO) is . It gives bounds based on two natural approaches. The first approach is to use the generalization properties of differential privacy itself to bound the gap between the empirical and population losses , and thus derive bounds for SCO from bounds on ERM. This approach leads to a suboptimal bound (specifically For clarity, in the introduction we focus on the dependence on $d$ and $n$ and $\epsilon$ for $(\epsilon,\delta)$-DP. We suppress the dependence on $\delta$ and on parameters of the loss function such as Lipschitz constant and the constraint set radius., $\approx\max\left(\tfrac{d^{\frac{1}{4}}}{\sqrt{n}},\tfrac{\sqrt{d}}{\epsilon n}\right)$ [4, Sec. F]). For the important case when $d=\Theta(n)$ and $\epsilon=\Theta(1)$ this results in the bound of $\Omega(n^{-\frac{1}{4}})$ on excess population loss. The second approach relies on generalization properties of stability to bound the gap between the empirical and population losses . Stability is ensured by adding a strongly convex regularizer to the empirical loss . This technique also yields a suboptimal bound on the excess population loss $\approx(d^{\frac{1}{4}}/\sqrt{\epsilon\,n})$.

There are two natural lower bounds that apply to DP-SCO. The lower bound of $\Omega(\sqrt{1/n})$ for the excess loss of non-private SCO applies for DP-SCO. Further it is not hard to show that lower bounds for DP-ERM translate to essentially the same lower bound for DP-SCO, leading to a lower bound of $\Omega(\frac{\sqrt{d}}{\epsilon n})$ (see Appendix C for the proof).

In this work, we address the gap between the known bounds for DP-SCO. Specifically, we show that the optimal rate of $O\left(\sqrt{\frac{1}{n}}+\frac{\sqrt{d}}{\epsilon n}\right)$ is achievable, matching the known lower bounds. In particular, we obtain the statistically optimal rate of $O(1/\sqrt{n})$ whenever $d=O(n)$. This is in contrast to the situation for DP-ERM where the cost of privacy grows with the dimension for all $n$.

In our first result we show that, under relatively mild smoothness assumptions, this rate is achieved by a variant of the standard noisy mini-batch SGD. The classical analyses for non-private SCO depend crucially on making only one pass over the dataset. However, a single pass noisy SGD is not sufficiently accurate as we need a non-trivial amount of noise in each step to carry out the privacy analysis. We rely instead on generalization properties of uniform stability . Unlike in , our analysis of stability is based on extension of recent stability analysis of SGD to noisy SGD. In this analysis, the stability parameter degrades with the number of passes over the dataset, while the empirical loss decreases as we make more passes. In addition, the batch size needs to be sufficiently large to ensure that the noise added for privacy is small. To satisfy all these constraints the parameters of the scheme need to be tuned carefully. Specifically we show that $\approx\min(n,n^{2}\epsilon^{2}/d)$ steps of SGD with a batch size of $\approx\max(\sqrt{\epsilon n},1)$ are sufficient to get all the desired properties.

Finally, we show that Objective Perturbation also achieves optimal bounds for DP-SCO. However, objective perturbation is only known to satisfy privacy under some additional assumptions, most notably, Hessian being rank $1$ on all points in the domain. The generalization analysis in this case is based on the uniform stability of the solution to strongly convex ERM. Aside from extending the analysis of this approach to population loss, we show that it can lead to algorithms for DP-SCO that use only near-linear number of gradient evaluations (whenever these assumptions hold). In particular, we give a variant of objective perturbation in conjunction with the stochastic variance reduced gradient descent (SVRG) with only $O(n\log n)$ gradient evaluations. We remark that the known lower bounds for uniform convergence hold even under those additional assumptions invoked in objective perturbation. Finding algorithms with near-linear running time in the general setting of SCO is a natural avenue for future research.

Our work highlights the importance of uniform stability as a tool for analysis of this important class of problems. We believe it should have applications to other differentially private statistical analyses.

Differentially private empirical risk minimization (ERM) is a well-studied area spanning over a decade . Aside from and work in the local model of DP these works focus on achieving optimal empirical risk bounds under privacy. Our work builds heavily on algorithms and analyses developed in this line of work while contributing additional insights.

Preliminaries

where the expectation is taken only over the internal randomness of $\mathcal{A}$.

We will use the following simple generalization property of stability that upper bounds the expectation of population loss. Our bounds on excess population loss can also be shown to hold (up to log factors) with high probability using the results from .

where the expectation is taken over the choice of $S\sim\mathcal{D}^{n}$, and any internal randomness in $\mathcal{A}$.

A randomized algorithm $\mathcal{A}$ is $(\epsilon,\delta)$-differentially private if, for any pair of datasets $S$ and $S^{\prime}$ differ in exactly one data point, and for all events $\mathcal{O}$ in the output range of $\mathcal{A}$, we have

where the probability is taken over the random coins of $\mathcal{A}$. For meaningful privacy guarantees, the typical settings of the privacy parameters are $\epsilon<1$ and $\delta\ll 1/n$.

An $(\epsilon,\delta)$-DP-SCO algorithm is a SCO algorithm that satisfies $(\epsilon,\delta)$-differential privacy.

Private SCO via Mini-batch Noisy SGD

Algorithm 1 is $(\epsilon,\delta)$-differentially private.

The proof follows from [1, Theorem 1], which gives a tight privacy analysis for mini-batch NSGD via the Moments Accountant technique and privacy amplification via sampling. We note that the setting of the mini-batch size in Step 2 of Algorithm 1 satisfies the condition in [1, Theorem 1] (we obtain here an explicit value for the universal constants in the aforementioned theorem in that reference). We also note that the setting of the Gaussian noise in is not normalized by the mini-batch size, and hence the noise variance reported in [1, Theorem 1] is larger than our setting of $\sigma^{2}$ by a factor of $m^{2}$. ∎

The population loss attained by $\mathcal{A}_{\sf NSGD}$ is given by the next theorem.

Let $\mathcal{D}$ be any distribution over $\mathcal{Z},$ and let $S\sim\mathcal{D}^{n}$. Suppose $\beta\leq\frac{L}{M}\cdot\min\left(\sqrt{\frac{n}{2}},\frac{\epsilon\,n}{2\sqrt{2d\log(1/\delta)}}\right)$. Let $T=\min\left(\frac{n}{8},~\frac{\epsilon^{2}\,n^{2}}{32\,d\,\log(1/\delta)}\right)$ and $\eta=\frac{M}{L\,\sqrt{T}}$. Then,

Before proving the above theorem, we first state and prove the following useful lemmas.

Let $S\in\mathcal{Z}^{n}$. Suppose the parameter set $\mathcal{W}$ is convex and $M$-bounded. For any $\eta>0,$ the excess empirical loss of $\mathcal{A}_{\sf NSGD}$ satisfies

where the expectation is taken with respect to the choice of the mini-batch (step 5) and the independent Gaussian noise vectors $\mathbf{G}_{1},\ldots,\mathbf{G}_{T}$.

The proof follows from the classical analysis of the stochastic oracle model (see, e.g., ).In particular, we can show that

where the last term captures the additional empirical error due to privacy. The statement now follows from the setting of $\sigma^{2}$ in Algorithm 1. ∎

The following lemma is a simple extension of the results on uniform stability of GD methods that appeared in and [17, Lemma 4.3] to the case of mini-batch noisy SGD. For completeness, we provide a proof in Appendix A.

By Lemma 2.2, $\alpha$-uniform stability implies that the expected population loss is upper bounded by $\alpha$ plus the expected empirical loss. Hence, by combining Lemma 3.3 with Lemma 3.4, we have

Private SCO for Non-smooth Losses

In this section, we consider the setting where the convex loss is non-smooth. First, we show a generic reduction to the smooth case by employing the smoothing technique known as Moreau-Yosida regularization (a.k.a. Moreau envelope smoothing) . Given an appropriately smoothed version of the loss, we obtain the optimal population loss w.r.t. the original non-smooth loss function. Computing the smoothed loss via this technique is generally computationally inefficient. Hence, we move on to describe a computationally efficient algorithm for the non-smooth case with essentially optimal population loss. Our construction is based on an adaptation of our noisy SGD algorithm $\mathcal{A}_{\sf NSGD}$ (Algorithm 1) that exploits some useful properties of Moreau-Yosida smoothing technique that stem from its connection to proximal operations.

Moreau envelope has direct connection with the proximal operator of a function defined below.

It follows that the Moreau envelope $f_{\beta}$ can be written as

The following lemma states some useful, known properties of Moreau envelope.

$f_{\beta}$ is convex, $2L$-Lipschitz, and $\beta$-smooth.

$\forall\mathbf{w}\in\mathcal{W}\quad f_{\beta}(\mathbf{w})\leq f(\mathbf{w})\leq f_{\beta}(\mathbf{w})+\frac{L^{2}}{2\,\beta}.$

$\forall\mathbf{w}\in\mathcal{W}\quad\nabla f_{\beta}(\mathbf{w})=\beta\,\left(\mathbf{w}-{\sf prox}_{f/\beta}(\mathbf{w})\right).$

The convexity and $\beta$-smoothness together with properties 2 and 3 are fairly standard and the proof can be found in the aforementioned references. The fact that $f_{\beta}$ is $2L$-Lipschitz follows easily from property 3. We include the proof of this fact in Appendix B for completeness.

Let $\overline{\mathbf{w}}_{T}$ be the output of $\mathcal{A}_{\sf NSGD}$. Using property 1 of Lemma 4.3 together with Theorem 3.2, we have

Now, by property 2 of Lemma 2 and the setting of $\beta$ in the theorem statement, for every $\mathbf{w}\in\mathcal{W}$, we have

Putting these together gives the stated result. ∎

Computing the Moreau envelope of a function is computationally inefficient in general. However, by property 3 of Lemma 4.3, we note that evaluating the gradient of Moreau envelope at any point can be attained by evaluating the proximal operator of the function at that point. Evaluating the proximal operator is equivalent to minimizing a strongly convex function (see Definition 4.2). This can be approximated efficiently, e.g., via gradient descent. Since our $\mathcal{A}_{\sf NSGD}$ algorithm (Algorithm 1) requires only sufficiently accurate gradient evaluations, we can hence use an efficient, approximate proximal operator to approximate the gradient of the smoothed losses. The gradient evaluations in $\mathcal{A}_{\sf NSGD}$ will thus be replaced with such approximate gradients evaluated via the approximate proximal operator. The resulting algorithm, referred to as $\mathcal{A}_{\sf ProxGD}$, will approximately minimize the smoothed empirical loss without actually computing the smoothed losses.

This fact follows from the fact that ${\sf prox}_{f/\beta}(\mathbf{w})=\arg\min\limits_{\mathbf{v}\in\mathcal{W}}g_{\mathbf{w}}(\mathbf{v}),$ where $g_{\mathbf{w}}(\mathbf{v})\triangleq\frac{1}{\beta}\,f(\mathbf{v})+\frac{1}{2}\|\mathbf{v}-\mathbf{w}\|^{2}$. This is minimization of $1$-strongly convex and $2\,M$-Lipschitz function over $\mathcal{W}$, The Lipschitz constant follows from the fact that $\beta\geq L/M$. Hence, one can run ordinary Gradient Descent to obtain an approximate minimizer. From a standard result on convergence of GD for strongly convex and Lipschitz functions , in $\tau$ gradient steps we obtain an approximate $\mathbf{v}_{\tau}$ satisfying $g_{\mathbf{w}}(\mathbf{v}_{\tau})-g_{\mathbf{w}}(\mathbf{v}^{*})\leq\frac{8\,M^{2}}{\tau}$, where $\mathbf{v}^{*}=\arg\min\limits_{\mathbf{v}\in\mathcal{W}}g_{\mathbf{w}}(\mathbf{v})$. Since $g_{\mathbf{w}}$ is $1$-strongly convex, we get $\|\mathbf{v}_{\tau}-\mathbf{v}^{*}\|\leq\sqrt{\frac{8\,M^{2}}{\tau}}$.

if we use the approximate proximal operator in Fact 4.6, then it is easy to see that $\mathcal{A}_{\sf ProxGD}$ requires a number of gradient evaluations that is a factor of $n^{2}\,T$ more than $\mathcal{A}_{\sf NSGD}$, where $T=O\left(\max\left(n,~\frac{\epsilon^{2}\,n^{2}}{d\,\log(1/\delta)}\right)\right).$ That is, the total number of gradient evaluations is $n^{2}\cdot T^{2}\cdot m,$ where $m=O\left(\max\left(\sqrt{\epsilon\,n},~\sqrt{\frac{d\,\log(1/\delta)}{\epsilon}}\right)\right)$ is the mini-batch size.

We now argue that privacy, stability, and accuracy of the algorithm are preserved under the approximate proximal operator.

Note that the approximation error in the gradient of the mini-batch (due to the approximate proximal operation) can be viewed as a fixed error term of magnitude at most $\frac{L}{n}$ that is added to the exact gradient of the smoothed loss. It is well-known and easy to see that the effect of this additional approximation error on the standard convergence bounds is that excess empirical loss may grow by at most the error times the diameter of the domain (e.g. ). Hence, compared to the error bound error in Lemma 3.3, the bound we get incurs an additional term of $2LM/n$. Clearly, this additional error is dominated by the other terms in the empirical loss bound in Lemma 3.3, and thus will have no significant impact on the final bound.

This easily follows from the following facts. First, note that the additional approximation error due to gradient approximation is $\frac{L}{n}$. Second, the gradient update w.r.t. the exact gradient of the smoothed loss is non-expansive operation (which is the key fact in proving uniform stability of (stochastic) gradient methods ), and hence the approximation error in the gradient is not going to be amplified by the gradient update step. Hence, for any trajectory of $T$ approximate gradient updates, the accumulated approximation error in the final output $\overline{\mathbf{w}}_{T}$ cannot exceed $\frac{T\,\eta\,L}{n}$. This cannot increase the final uniform stability bound by more than an additive term of $\frac{T\,\eta\,L^{2}}{n}$. Thus, we obtain basically the same bound in Lemma 3.4.

Putting these together, we have argued that $\mathcal{A}_{\sf ProxGD}$ is computationally efficient algorithm that achieves the optimal population loss bound in Theorem 4.4.

Private SCO via Objective Perturbation

In this section, we show that the technique known as objective perturbation can be used to attain optimal population loss for a large subclass of convex, smooth losses. In objective perturbation, the empirical loss is first perturbed by adding two terms: a noisy linear term and a regularization term. As shown in , under some additional assumptions on the Hessian of the loss, an appropriate random perturbation ensures differential privacy. The excess empirical loss of this technique for smooth convex losses was originally analyzed in the aforementioned works, and was shown to be optimal by the lower bound in . We revisit this technique and show that the regularization term added for privacy can be used to attain the optimal excess population loss by exploiting the stability-inducing property of regularization.

The description of the objective perturbation algorithm $\mathcal{A}_{\sf ObjP}$ is given in Algorithm 2. The outline of the algorithm is the same as the one in for the case of $(\epsilon,\delta)$-differential privacy.

The regularization term as appears in $\mathcal{A}_{\sf ObjP}$ is of different scaling than the one that appears in . In particular, the regularization term in is normalized by $n$, whereas here it is not. Hence, whenever the results from are used here, the regularization parameter in their statements should be replaced with $n\lambda$. This presentation choice is more consistent with literature on regularization.

The privacy guarantee of $\mathcal{A}_{\sf ObjP}$ is given in the following theorem, which follows directly from .

Suppose that Assumption 5.1 holds and that the smoothness parameter satisfies $\beta\leq\epsilon\,n\,\lambda$. Then, $\mathcal{A}_{\sf ObjP}$ is $(\epsilon,\delta)$-differentially private.

We now state our main result for this section showing that, with appropriate setting for $\lambda$, $\mathcal{A}_{\sf ObjP}$ yields asymptotically optimal excess population loss.

Let $\mathcal{D}$ be any distribution over $\mathcal{Z},$ and let $S\sim\mathcal{D}^{n}$. Suppose that Assumption 5.1 holds. Suppose that $\mathcal{W}$ is $M$-bounded. In $\mathcal{A}_{\sf ObjP},$ set $\lambda=\frac{2\,L}{M}\sqrt{\frac{2}{n}+\frac{4\,d\,\log(1/\delta)}{\epsilon^{2}\,n^{2}}}.$ Then, we have

According to Theorem 5.2, $(\epsilon,\delta)$-differential privacy of $\mathcal{A}_{\sf ObjP}$ entails the assumption that $\beta\leq\epsilon\,n\,\lambda.$ With the setting of $\lambda$ in Theorem 5.3, it would suffice to assume that $\beta\leq\frac{2\,\epsilon\,L}{M}\sqrt{2\,n+4\,d\,\log(1/\delta)}.$

To prove the above theorem, we use the following lemmas.

Let $S\sim\mathcal{Z}^{n}$. Under Assumption 5.1, the excess empirical loss of $\mathcal{A}_{\sf ObjP}$ satisfies

where the expectation is taken over the Gaussian noise in $\mathcal{A}_{\sf ObjP}$.

The next lemma states the well-known stability property of regularized empirical risk minimization.

Proof of Theorem 5.3

where we assume $\frac{\sqrt{10\,d\,\log(1/\delta)}}{\epsilon\,n}\leq 1$ (since otherwise we would have the trivial error).

1 Oracle Efficient Objective Perturbation

Suppose that Assumption 5.1 holds and that the smoothness parameter satisfies $\beta\leq\epsilon\,n\,\lambda$. Then, Algorithm $\mathcal{A}_{\sf ObjP-App}$ is $(\epsilon,\delta)$-differentially private.

Let $\mathbf{w}_{1}=\arg\min\limits_{\mathbf{w}\in\mathcal{W}}\underbrace{\widehat{\mathcal{L}}\left(\mathbf{w};~S\right)+\frac{\langle\mathbf{G},~\mathbf{w}\rangle}{n}+\lambda\|\mathbf{w}\|^{2}}_{\mathcal{J}(\mathbf{w},S)}$, and $\mathbf{w}_{2}=\mathcal{O}(\mathcal{J},\alpha)$, where $\mathcal{O}$ is the optimizer defined in Algorithm $\mathcal{A}_{\sf ObjP-App}$. Notice that one can compute $\widehat{\mathbf{w}}$ from the tuple $(\mathbf{w}_{1},\mathbf{w}_{2}-\mathbf{w}_{1}+\mathbf{H})$ by simple post-processing. Furthermore, the algorithm that outputs $\mathbf{w}_{1}$ is $(\epsilon/2,\delta/2)$-differentially private by Theorem 5.2. In the following, we will bound $\|\mathbf{w}_{2}-\mathbf{w}_{1}\|$ in order to make $(\mathbf{w}_{2}-\mathbf{w}_{1}+\mathbf{H})$ differentially private, conditioned on the knowledge of $\mathbf{w}_{1}$.

As $\mathcal{J}(\mathbf{w},S)$ is $\lambda$-strongly convex, $\mathcal{J}(\mathbf{w}_{2},S)\geq\mathcal{J}(\mathbf{w}_{1},S)+\frac{\lambda}{2}\|\mathbf{w}_{2}-\mathbf{w}_{1}\|^{2}$ so that

Let $\mathcal{D}$ be any distribution over $\mathcal{Z},$ and let $S\sim\mathcal{D}^{n}$. Suppose that Assumption 5.1 holds and that $\mathcal{W}$ is $M$-bounded. In Algorithm $\mathcal{A}_{\sf ObjP-App}$, set $\lambda=\frac{2\,L}{M}\sqrt{\frac{2}{n}+\frac{4\,d\,\log(1/\delta)}{\epsilon^{2}\,n^{2}}}$, $\alpha=\frac{M^{2}\lambda}{n^{2}}$. Then, we have

Let $\mathbf{w}_{1}=\arg\min\limits_{\mathbf{w}\in\mathcal{W}}{\widehat{\mathcal{L}}\left(\mathbf{w};~S\right)+\frac{\langle\mathbf{G},~\mathbf{w}\rangle}{n}+\lambda\|\mathbf{w}\|^{2}}$. For $\widehat{\mathbf{w}}$ defined in Step 3 of $\mathcal{A}_{\sf ObjP-App}$, notice that using Theorem 5.3,

when $\alpha=\frac{M^{2}\lambda}{n^{2}}$. Therefore, $\Delta\mathcal{L}\left(\widehat{\mathbf{w}};~\mathcal{D}\right)\leq O\left(M\,L\cdot\max\left(\frac{1}{\sqrt{n}},~\frac{\sqrt{d\,\log(1/\delta)}}{\epsilon\,n}\right)\right)$, which completes the proof. ∎

Let $f_{1},\cdots,f_{n}$ be $\beta$-smooth, $\lambda$-strongly convex functions over $\mathcal{W}$, $\mathcal{F}(\mathbf{w})=\frac{1}{n}\sum\limits_{i=1}^{n}f_{i}(\mathbf{w})$, and $\mathbf{w}^{*}\triangleq\arg\min_{\mathbf{w}\in\mathcal{W}}\mathcal{F}(\mathbf{w})$. Let $\mathbf{y}^{(1)}\in\mathcal{W}$ be an arbitrary initial point. For $t=\{1,2,\cdots\}$, let $\mathbf{w}^{(t)}_{1}=\mathbf{y}^{(t)}$. For $s\in[k]$, let

where $i^{(t)}_{s}$ is drawn uniformly at random from $[n]$, and $\mathbf{y}^{(t+1)}=\frac{1}{k}\sum\limits_{s=1}^{k}\mathbf{w}^{(t)}_{s}$. Then, for $k=20\beta/\lambda$ it holds that:

Acknowledgements

We thank Adam Smith, Thomas Steinke and Jon Ullman for the insightful discussions of the problem at the early stages of this project. We are also grateful to Tomer Koren for bringing the Moreau-Yosida smoothing technique to our attention.

References

Appendix A Proof of Lemma 3.4

Consider $T$ iterations of $\mathcal{A}_{\sf NSGD}$. Let $\mathbf{G}_{1},\ldots,\mathbf{G}_{T}$ denote the noise vectors and $\mathcal{I}_{1},\ldots,\mathcal{I}_{T}\in[n]^{m}$ denote the index sets of the mini-batches selected in the $T$ iterations. Consider any pair of datasets $S=(z_{1},\ldots,z_{k},\ldots,z_{n})$ and $S^{\prime}=(z_{1},\ldots,z^{\prime}_{k},\ldots,z_{n})$ differing in exactly one data point $z_{k}\neq z^{\prime}_{k}$ for some fixed $k\in[n]$. Let $\mathbf{w}_{0},\mathbf{w}_{1},\ldots,\mathbf{w}_{T}$ and $\mathbf{w}_{0},\mathbf{w}^{\prime}_{1},\ldots,\mathbf{w}^{\prime}_{T}$ denote the trajectories of $\mathcal{A}_{\sf NSGD}$ corresponding to input datasets $S$ and $S^{\prime}$, respectively. For any $t\in[T],$ let $\xi_{t}\triangleq\mathbf{w}_{t}-\mathbf{w}^{\prime}_{t}$.

We follow the proof technique of [17, Lemma 4.3]. We prove the following claim via induction on $t$:

where the expectation is taken over $\mathcal{I}_{0},\ldots,\mathcal{I}_{t-1},\mathbf{G}_{0},\ldots,\mathbf{G}_{t-1}$. First, it’s trivial to see that the claim is true for $t=0$. Suppose the claim holds for all $t\leq\tau$. Fix the randomness in $\mathbf{G}_{\tau}$ and $\mathcal{I}_{\tau}$. Let $r$ denote the number of occurrences of the index $k$ (where $S$ and $S^{\prime}$ differ) in $\mathcal{I}_{\tau}$. By the non-expansiveness property of the gradient update step, we have

Now, we now invoke the randomness in $\mathbf{G}_{\tau}$ and $\mathcal{I}_{\tau}$. Note that $r$ is a Binomial random variable with mean $m/n$. Hence, by taking expectation and using the induction hypothesis, we end up with

Appendix B Proof of Lipschitz property of Moreau envelope (Lemma 4.3)

Fix any $\mathbf{w}\in\mathcal{W}$. We will show that $\|\nabla f_{\beta}(\mathbf{w})\|\leq 2L.$ Define $g(\mathbf{v})\triangleq f(\mathbf{v})+\frac{\beta}{2}\|\mathbf{v}-\mathbf{w}\|^{2},~\mathbf{v}\in\mathcal{W}$. Note that ${\sf prox}_{f/\beta}(\mathbf{w})=\arg\min\limits_{\mathbf{v}\in\mathcal{W}}g(\mathbf{v}).$ Let $\mathbf{v}^{*}$ denote ${\sf prox}_{f/\beta}(\mathbf{w})$. Now, observe that

where the last inequality follows from the fact that $f$ is $L$-Lipschitz. Thus, we get $\|\mathbf{w}-\mathbf{v}^{*}\|\leq 2\,L/\beta.$ By property 3, we have $\|\nabla f_{\beta}(\mathbf{w})\|=\beta\,\|\mathbf{w}-\mathbf{v}^{*}\|$. This together with the above bound gives the desired result.

Appendix C Optimality of Our Bounds

Our upper bounds in Sections 3 and 4 are tight (up to logarithmic factors in $1/\delta$). In particular, our bounds match a lower bound of $\Omega\left(M\,L\cdot\max\left(\frac{1}{\sqrt{n}},~\frac{\sqrt{d}}{n}\right)\right)$ on the excess population loss. The first term is simply the known lower bound on the excess population loss in the non-private setting. The second term follows from the lower bound in on excess empirical loss, and the fact that a lower bound on excess empirical loss implies nearly the same lower bound on the excess population loss. We elaborate on this below.

Fix any $\gamma>0$. Suppose algorithm $\mathcal{A}$ described above exists. We construct algorithm $\mathcal{B}$ as follows:

Given input dataset $S\in\mathcal{Z}^{n},$ let $\mathcal{D}_{S}$ be the empirical distribution induced by $S$.

First, note that $\Delta\widehat{\mathcal{L}}(\mathcal{B};S)\leq\gamma$. This easily follows from the fact that for any $\mathbf{w}$, $\mathcal{L}(\mathbf{w};\mathcal{D}_{S})=\widehat{\mathcal{L}}(\mathbf{w};S)$. In particular, observe that

Next, we show that $\mathcal{B}$ is $(\epsilon,\delta)$-differentially private. Let $S=(z_{1},\ldots,z_{k},\ldots,z_{n}),S^{\prime}=(z_{1},\ldots,z^{\prime}_{k},\ldots,z_{n})$ be neighboring datasets differing in single point whose index is $k\in[n]$. Let $T,T^{\prime}$ be the samples obtained by running $\mathcal{B}$ on $S,S^{\prime},$ respectively, with the same set of random coins in Step 2. More precisely, let $R$ denote the random sampling procedure used in Step 2, and define $T=R(S)$ and $T^{\prime}=R(S^{\prime})$. Let $r$ be the number of times the $k$-th point of the input dataset is sampled by $R$. Hence, $r=\lvert T\Delta T^{\prime}\rvert$, i.e., $r$ is the number of points where $T$ and $T^{\prime}$ differ. By Chernoff’s bound, $r\leq 4\,\log(2/\delta)$ with probability $1-\delta/2$. Let $\mathcal{V}$ be any measurable subset of the range of $\mathcal{B}$. Observe that

where the third inequality follows from the fact that $\mathcal{A}$ is $\left(\frac{\epsilon}{4\,\log(2/\delta)},\frac{\delta}{2}\right)$-differentially private and group differential privacy (e.g. ). This shows that $\mathcal{B}$ is $(\epsilon,\delta)$-differentially private, proving the reduction, and hence, the lower bound.