Private Adaptive Gradient Methods for Convex Optimization

Introduction

While the success of stochastic gradient methods for solving empirical risk minimization has motivated their adoption across much of machine learning, increasing privacy risks in data-intensive tasks have made applying them more challenging [DMNS06]: gradients can leak users’ data, intermediate models can compromise individuals, and even final trained models may be non-private without substantial care. This motivates a growing line of work developing private variants of stochastic gradient descent (SGD), where algorithms guarantee differential privacy by perturbing individual gradients with random noise [DJW13, ST13a, ACGMMTZ16, DJW18, BFTT19, FKT20]. Yet these noise addition procedures typically fail to reflect the geometry underlying the optimization problem, which in non-private cases is essential: for high-dimensional problems with sparse parameters, mirror descent and its variants [BT03, NJLS09] are essential, while in the large-scale stochastic settings prevalent in deep learning, AdaGrad and other adaptive variants [DHS11] provide stronger theoretical and practical performance. Even more, methods that do not adapt (or do not leverage geometry) can be provably sub-optimal, in that there exist problems where their convergence is much slower than adaptive variants that reflect appropriate geometry [LD19].

To address these challenges, we introduce Pagan (Private AdaGrad with Adaptive Noise), a new differentially private variant of stochastic gradient descent and AdaGrad. Our main contributions center on a few ideas. Standard methods for privatizing adaptive algorithms that add isometric (typically Gaussian) noise to gradients necessarily reflect the worst-case behavior of functions to be optimized and eliminate the geometric structure one might leverage for improved convergence. By carefully adapting noise to the actual gradients at hand, we can both achieve convergence rates that reflect the observed magnitude of the gradients—similar to the approach of [BHR07] in the non-private case—which can yield marked improvements over the typical guarantees that depend on worst-case magnitudes. (Think, for example, of a standard normal variable: its second moment is 1, while its maximum value is unbounded.) Moreover, we propose a new private adaptive optimization algorithm that analogizes AdaGrad, showing that under certain natural distributional assumptions for the problems—similar to those that separate AdaGrad from non-adaptive methods [LD19]—our private versions of adaptive methods significantly outperform the standard non-adaptive private algorithms. Additionally, we prove several lower bounds that both highlight the importance of geometry in the problems and demonstrate the tightness of the bounds our algorithms achieve. Finally, we provide several experiments on real-world and synthetic datasets that support our theoretical results, demonstrating the improvements of our private adaptive algorithm (Pagan) over DP-SGD and other private adaptive methods.

In more recent work, Yu et al. [YZCL21] use PCA to decompose gradients into two orthogonal subspaces, allowing separate learning rate treatments in the subspaces, and achieve promising empirical results, but they provide no provable convergence bounds. Also related to the current paper is Pichapati et al.’s AdaClip algorithm [PSYRK20]; they obtain parallels to Bartlett et al.’s non-private convergence guarantees [BHR07] for private SGD. In contrast to our analysis here, their analysis applies to smooth non-convex functions, while our focus on convex optimization allows more complete convergence guarantees and associated optimality results.

Preliminaries and notation

We suppress dependence on $\mathcal{S}$ and simply write $f(x)$ when the dataset is clear from context. We use the standard definitions of differential privacy [DMNS06, DKMMN06]:

A randomized algorithm $M$ is $(\varepsilon,\delta)$-differentially private if for all neighboring datasets $\mathcal{S},\mathcal{S}^{\prime}\in\mathcal{Z}^{n}$ and all measurable $O$ in the output space of $M$,

If $\delta=0$, then $M$ is $\varepsilon$-differentially private.

It will also be useful to discuss the tail properties of random variables and vectors:

We also frequently use different norms and geometries, so it is useful to recall Lipschitz continuity:

A convex function $\Phi$ is $G$-Lipschitz over an open set $\mathcal{W}$ if and only if $\|\Phi^{\prime}(w)\|_{*}\leq G$ for any $w\in\mathcal{W}$ and $\Phi^{\prime}(w)\in\partial\Phi(w)$, where $\left\|{y}\right\|_{*}=\sup\{x^{\top}y\mid\left\|{x}\right\|\leq 1\}$ is the dual norm of $\left\|{\cdot}\right\|$ [HUL93].

Private Adaptive Gradient Methods

In this section, we study and develop Pasan and Pagan, differentially private versions of Stochastic Gradient Descent (SGD) with adaptive stepsize (Algorithm 1) and Adagrad [DHS11] (Algorithm 2). The challenge in making these algorithms private is that adding isometric Gaussian noise—as is standard in the differentially private optimization literature—completely eliminates the geometrical properties that are crucial for the performance of adaptive gradient methods. We thus add noise that adapts to gradient geometry while maintaining privacy. More precisely, our private versions of adaptive optimization algorithms proceed as follows: to privatize the gradients, we first project them to an ellipsoid capturing their geometry, then adding non-isometric Gaussian noise whose covariance corresponds to the positive definite matrix $A$ that defines the ellipsoid. Finally, we apply the adaptive algorithm’s step with the private gradients. We present our private versions of SGD with adaptive stepsizes and Adagrad in Algorithms 1 and 2, respectively.

Before analyzing the utility of these algorithms, we provide their privacy guarantees in the following lemma (see Appendix B.1 for its proof).

There exist constants $\bar{\varepsilon}$ and $c$ such that, for any $\varepsilon\leq\bar{\varepsilon}$, and with $T=c{n^{2}}/{b^{2}}$, Algorithm 1 and Algorithm 2 are $(\varepsilon,\delta)$-differentially private.

The moments of the Lipschitz constant $G$ will be central to our convergence analyses, and to that end, for $p\geq 1$ we define the shorthand

The quantity $G_{p}(C)$ are the $p$th moments of the gradients in the Mahalanobis norm $\left\|{\cdot}\right\|_{C}$; they are the key to our stronger convergence guarantees and govern the error in projecting our gradients. In most standard analyses of private optimization (and stochastic optimization more broadly), one takes $C=I$ and $p=\infty$, corresponding to the assumption that $F(\cdot,z)$ is $G$-Lipschitz for all $z$ and that subgradients $F^{\prime}(x,z)$ are uniformly bounded in both $x$ and $z$. Even when this is the case—which may be unrealistic—we always have $G_{p}(C)\leq G_{\infty}(C)$, and in realistic settings there is often a significant gap; by depending instead on appropriate moments $p$, we shall see it is often possible to achieve far better convergence guarantees than would be possible by relying on uniformly bounded moments. (See also Barber and Duchi’s discussion of these issues in the context of mean estimation [BD14].)

As this bound shows, while $G_{\infty}$ is infinite in this example, $G_{p}$ is finite. As a result, our analysis extends to settings in which the stochastic gradients are not uniformly bounded. $\Diamond$

While we defined $G_{p}(C)$ by taking expectation with respect to the original distribution $P$, we mainly focus on empirical risk minimization and thus require the empirical Lipschitz constant for a given dataset $\mathcal{S}$:

A calculation using Chebyshev’s inequality and that $p$-norms are increasing immediately gives the next lemma:

Let $\mathcal{S}$ be a dataset with $n$ points sampled from distribution $P$. Then with probability at least $1-1/n$, we have

It is possible to get bounds of the form $\hat{G}_{p}(\mathcal{S};C)\lesssim G_{kp}(C)$ with probability at least $1-1/n^{k}$ using Khintchine’s inequalities, but this is secondary for us.

Given these moment bounds, we can characterize the convergence of both algorithms, defering proofs to Appendix B.

Let $\mathcal{S}\in\mathcal{Z}^{n}$ and $C\succ 0$ be diagonal, $p\geq 1$, and assume that $\hat{G}_{p}(\mathcal{S};C)\leq G_{2p}(C)$. Consider running Pasan (Algorithm 1) with $\alpha=\textup{diam}_{2}(\mathcal{X})$, $T=cn^{2}/b^{2}$, $A_{k}=\frac{1}{B^{2}}C$, whereWe provide the general statement of this theorem for positive $B$ in Appendix B.4

and $c$ is the constant in Lemma 3.1. Then

where the expectation is taken over the internal randomness of the algorithm.

To gain intuition for these bounds, note that for large enough $p$, the bound from Theorem 1 is approximately

2 Convergence of Pagan

Having established our bounds for Pasan, we now proceed to present our results for Pagan (Algorithm 2). In the non-private setting, adaptive gradient methods such as Adagrad are superior to SGD for constraint sets such as $\mathcal{X}=^{d}$ where $\textup{diam}_{\infty}(\mathcal{X})\ll\textup{diam}_{2}(\mathcal{X})$. Following this, our bounds in this section will depend on $\textup{diam}_{\infty}(\mathcal{X})$.

Let $\mathcal{S}\in\mathcal{Z}^{n}$ and $C\succ 0$ be diagonal, $p\geq 1$, and assume that $\hat{G}_{p}(\mathcal{S};C)\leq G_{2p}(C)$. Consider running Pagan (Algorithm 2) with $\alpha=\textup{diam}_{\infty}(\mathcal{X})$, $T=cn^{2}/b^{2}$, $A_{k}=\frac{1}{B^{2}}C$, where

and $c$ is the constant in Lemma 3.1. Then

where the expectation is taken over the internal randomness of the algorithm.

To gain intuition, we again consider the large $p$ case, where Theorem 2 simplifies to roughly

In analogy with Theorem 1, the first term $R_{\textup{ada}}(T)$ is the standard error for non-private Adagrad after $T$ iterations [DHS11]—and hence unimprovable [LD19]—while the second is the privacy cost. In some cases, we may have $\textup{diam}_{\infty}(\mathcal{X})=\textup{diam}_{2}(\mathcal{X})/\sqrt{d}$, so private Adagrad can offer significant improvements over SGD whenever the matrix $C$ has polynomially decaying diagonal.

To clarify the advantages and scalings we expect, we may consider an extremely stylized example with sub-Gaussian distributions. Assume now—in the context of Example A1—that we are optimizing the random linear function $F(x;Z)=\langle x,Z\rangle$, where $Z$ has independent $\sigma_{j}^{2}$-sub-Gaussian compoments. In this case, by assuming that $p=\log d$ and taking $C_{jj}=\sigma_{j}^{-4/3}$ and $b=1$, Theorem 2 guarantees that Pagan (Algorithm 2) has convergence

On the other hand, for Pasan (Algorithm 1), with $p=\log d$, $b=1$, the choice $C_{jj}=\sigma_{j}^{-1}$ optimizes the bound of Theorem 1 and yields

Comparing these results, two differences are salient: $\textup{diam}_{\infty}(\mathcal{X})$ replaces $\textup{diam}_{2}(\mathcal{X})$ in Eq. (7), which can be an improvement by as much as $\sqrt{d}$, while $(\sum_{j=1}^{d}\sigma_{j}^{2/3})^{3/2}$ replaces $\sum_{j=1}^{d}\sigma_{j}$, and Hölder’s inequality gives

Depending on gradient moments, there are situations in which Pagan offers significant improvements; these evidently depend on the expected magnitudes of the gradients and noise, as the $\sigma_{j}$ terms evidence. As a special case, consider $\mathcal{X}=[-1,+1]^{d}$ and assume $\{\sigma_{j}\}_{j=1}^{d}$ decrease quickly, e.g. $\sigma_{j}=1/j^{3/2}$. In such a setting, the upper bound of Pagan is roughly $\frac{\mathsf{poly}(\log d)}{n\varepsilon}$ while Pasan achieves $\frac{\sqrt{d}}{n\varepsilon}$.

Some approaches to unknown moments

As the results of the previous section demonstrate, bounding the gradient moments allows us to establish tighter convergence guarantees; it behooves us to estimate them with accuracy sufficient to achieve (minimax) optimal bounds.

The results of Section 3 suggest optimal choices for $C$ under sub-Gaussian assumptions on the vectors $z$, where in our stylized cases of $\sigma_{j}$-sub-Gaussian entries, $C_{j}=\sigma_{j}^{-4/3}$ minimizes our bounds. Unfortunately, it is hard in general to estimate $\sigma_{j}$ even without privacy [Duc19]. Therefore, we make the following bounded moments ratio assumption, which relates higher moments to lower moments to allow estimation of moment-based parameters (even with privacy).

When $z$ satisfies Def. 4.1, we can provide a private procedure (Algorithm 3) that provides good approximation to the second moment of coordinates of $z_{j}$—and hence higher-order moments—allowing the application of a minimax optimal Pagan algorithm. We defer the proof to Appendix C.

and $\max_{1\leq j\leq d}\sigma_{j}=1$. Then Algorithm 3 is $(\varepsilon,\delta)$-DP and outputs $\hat{\sigma}$ such that with probability $1-\beta$,

Moreover, when condition (8) holds, Pagan (Alg. 2) with $\hat{C}_{j}=(r\hat{\sigma}_{j})^{-4/3}/4$, $p=\log d$ and $b=1$ has convergence

Lower bounds for private optimization

As one of our foci here is for data with varying norms, we prove lower bounds for sub-Gaussian data—the strongest setting for our upper bounds. In particular, we shall consider linear functionals $F(x;z)=z^{T}x$, where the entries $z_{j}$ of $z$ satisfy $|z_{j}|\leq\sigma_{j}$ for a prescribed $\sigma_{j}$; this is sufficient for the data $Z$ to be $\frac{\sigma_{j}^{2}}{4}$-sub-Gaussian [Ver19]. Moreover, our upper bounds are conditional on the observed sample $\mathcal{S}$, and so we focus on this setting in our lower bounds, where $|g_{j}|\leq\sigma_{j}$ for all subgradients $g\in\partial F(x;z)$ and $j\in[d]$.

The starting point for our lower bounds for stochastic optimization over $\mathcal{X}_{\infty}$ is the following lower bound for the problem of estimating the sign of the mean of a dataset. This will then imply our main lower bound for private optimization. We defer the proof of this result to Appendix D.1.

where $\bar{z}=\frac{1}{n}\sum_{i=1}^{n}z_{i}$ is the mean of the dataset. Letting $x^{\star}_{\mathcal{S}}\in\mathop{\rm argmin}_{x\in\mathcal{X}_{\infty}}f(x;\mathcal{S})$, we have the following result.

Proof For a given dataset $\mathcal{S}$, the minimizer $x^{\star}_{j}=\mathop{\rm sign}(\bar{z}_{j})$. Therefore for every $x$ we have

As $\mathop{\rm sign}(M(\mathcal{S}))$ is $(\varepsilon,\delta)$-DP by post-processing, the claim follows from Proposition 1 by taking expectations. ∎

Recalling the upper bounds that Pagan achieves in Section 3.2, Theorem 4 establishes the tightness of these bounds to within logarithmic factors.

The following bound follows by appropriate re-scaling of the data points in Theorem 5.3 in [BST14]

Using Proposition 2, we can establish the tight lower bounds—to within logarithmic factors—for Pasan (Section 3). We defer the proof to Appendix D.3.

Experiments

We conclude the paper with several experiments to demonstrate the performance of Pagan and Pasan algorithms. We perform experiments both on synthetic data, where we may control all aspects of the experiment, and a real-world example training large-scale private language models.

If our Pagan algorithm indeed captures the aspects of AdaGrad and other adaptive methods, we expect it to outperform other private stochastic optimization methods at the least in those scenarios where AdaGrad improves upon stochastic gradient methods—as basic sanity check. To that end, in our first collection of experiments, we compare Pagan against standard implementations of private AdaGrad and SGD methods. We also compare our method against Projected DP-SGD (PDP-SGD) [ZWB20], which projects the noisy gradients into the (low-dimensional) subspace of the top $k$ eigenvectors of the second moment of gradients.

We compare several algorithms in this experiment: non-private AdaGrad; the naive implementations of private SGD (Pasan, Alg. 1) and AdaGrad (Pagan, Alg. 2), with $A_{k}=I$; Pagan with the optimal diagonal matrix scaling $A_{k}$ we derive in Section 3.2; and Zhou et al.’s PDP-SGD with ranks $k=20$ and $k=50$. In our experiments, we use the parameters $n=5000$, $d=100$, $\sigma_{j}=j^{-3/2}$, $\tau=0.01$, and the batch size for all methods is $b=70$. As optimization methods are sensitive to stepsize choice even non-privately [AD19], we run each method with different values of initial stepsize in $\{0.005,0.01,0.05,0.1,0.15,0.2,0.4,0.5,1.0\}$ to find the best stepsize value. Then we run each method $T=30$ times and report the median of the loss as a function of the iterate with 95% confidence intervals.

Figure 1 demonstrates the results of this experiment. Each plot shows the loss of the methods against iteration count in various privacy regimes. In the high-privacy setting (Figure 1(a)), the performance of all private methods is worse than the non-private algorithms, though Pagan (Alg. 2) seems to be outperforming other algorithms. As we increase the privacy parameter—reducing privacy preserved—we see that Pagan quickly starts to enjoy faster convergence, resembling non-private AdaGrad. different for non-private methods). In contrast, the standard implementation of private AdaGrad—even in the moderate privacy regime with $\varepsilon=4$—appears to obtain the slower convergence of SGD rather than the adaptive methods. This is consistent with the predictions our theory makes: the isometric Gaussian noise addition that standard private stochastic gradient methods (e.g. Pasan and variants) employ eliminates the geometric properties of gradients (e.g., sparsity) that adaptive methods can—indeed, must [LD19]—leverage for improved convergence.

2 Training Private Language Models on WikiText-2

We use Abadi et al.’s moments accountant analysis [ACGMMTZ16] to track the privacy losses of each of the methods. In each experiment, for Pagan and Pasan we use gradients trained for one epoch on a held-out dataset (a subset of the WikiText 103 dataset [MXBS17] which does not intersect with WikiText-2) to estimate moment bounds and gradient norms, as in Section 4; these choices—while not private—reflect the common practice that we may have access to public data that provides a reasonable proxy for the actual moments on our data. Moreover, our convergence guarantees in Section 3 are robust in the typical sense of stochastic gradient methods [NJLS09], in that mis-specifying the moments by a multiplicative constant factor yields only constant factor degradation in convergence rate guarantees, so we view this as an acceptable tradeoff in practice. It is worth noting that we ignore the model trained over the public data and use that one epoch solely for estimating the second moment of gradients.

In our experiments, we evaluate the performance of the trained models with validation- and test-set perplexity. While we propose adaptive algorithms, we still require hyperparameter tuning, and thus perform a hyper-parameter search over three algorithm-specific constants: a multiplier $\alpha\in\{0.1,0.2,0.4,0.8,1.0,10.0,50.0\}$ for step-size, mini-batch size $b=250$, and projection threshold $B\in\{0.05,0.1,0.5,1.0\}$. Each run of these algorithms takes $<$ 4 hours on a standard workstation without any accelerators. We trained the LSTM model above with Pagan and Pasan and compare its performance with DP-SGD [ACGMMTZ16]. We also include completely non-private SGD and AdaGrad for reference. We do not include PDP-SGD [ZWB20] in this experiment as, for our $N=2.1\cdot 10^{6}$ parameter model, computing the low-rank subspace for gradient projection that PDP-SGD requires is quite challenging. Indeed, computing the gradient covariance matrix Zhou et al. [ZWB20] recommend is certainly infeasible. While power iteration or Oja’s method can make computing a $k$-dimensional projection matrix feasible, the additional memory footprint of this $kN$-sized matrix (compared to the original model size $N$) can be prohibitive, restricting us to smaller models or very small $k$. For such small values ($k=50$), our experiments show that PDP-SGD achieves significantly worse error than the algorithms we consider hence we do not include it in the plots. On the other hand, our (diagonal) approach, like diagonal AdaGrad, only requires an additional memory of size $N$.

For each of the privacy levels $\varepsilon\in\{0.5,1,3\}$ we consider, we present the performance of each algorithm in terms of best validation set and test-set perplexity in Figure 2 and Table 1.

We highlight a few messages present in Figure 2. First, Pagan consistently outperforms the non-adaptive methods—though all allow the same hyperparameter tuning—at all privacy levels, excepting the non-private $\varepsilon=+\infty$, where Pagan without clipping is just AdaGrad and its performance is comparable to the non-private stochastic gradient method. Certainly, there remain non-negligible gaps between the performance of the private methods and non-private methods, but we hope that this is a step at least toward effective large-scale private optimization and modeling.

Acknowledgement

The authors like to thank Vitaly Feldman and Jalaj Upadhyay for helpful discussions in the process of preparing this paper and Daniel Levy for comments on an earlier draft. Part of this work was done while HA and AF were interning at Apple.

References

Appendix A Convergence of SGD and AdaGrad with biased gradients estimates

For the sake of our analysis, we find it helpful to first study the convergence of SGD and AdaGrad when the stochastic estimates of the subgradients may be biased and noisy (Algorithms 4 and 5.)

Consider the biased SGD method (Algorithm 4) with a non-increasing sequence of stepsizes $\{\alpha_{k}\}_{k=0}^{T-1}$. Then for any $x^{\star}\in\mathop{\rm argmin}_{\mathcal{X}}f$, we have

Proof We first consider the progress of a single step of the gradient-projected stochastic gradient method. We have

where the error random variable $E_{k}$ is given by

Using that $\langle f^{\prime}(x^{k}),x^{k}-x^{\star}\rangle\leq f(x^{k})-f(x^{\star})$ then yields

Summing for $k=0,\ldots,T-1$, by rearranging the terms and using that the stepsizes are non-increasing, we obtain

Taking expectations from both sides, we have

where the second equality comes from the fact that the two other expectations are zero and the last inequality follows from the Holder’s inequality. ∎ Remark This result holds in the case that $\alpha_{k}$’s are adaptive and depend on observed gradients.

Next theorem states the convergence of biased Adagrad (Algorithm 5).

Consider the biased Adagrad method (Algorithm 5). Then for any $x^{\star}\in\mathop{\rm argmin}_{\mathcal{X}}f$, we have

Proof Recall that $x^{k+1}$ is the projection of $x^{k}-H_{k}^{-1}\hat{g}^{k}$ into $\mathcal{X}$ with respect to $\|.\|_{\mathcal{H}_{k}}$. Hence, since $x^{\star}\in\mathcal{X}$ and projections are non-expansive, we have

Now, expanding the right hand side yields

Now the claim follows using standard techniques for Adagrad (as for example Corollary 4.3.8 in [Duc18]). ∎

Appendix B Proofs of Section 3

The proof mainly follows from Theorem 1 in [ACGMMTZ16] where the authors provide a tight privacy bound for mini-batch SGD with bounded gradient using the Moments Accountant technique. Here we do not have the bounded gradient assumption. However, recall that we have

B.2 The proof deferred from Example A1

Note that $\nabla F(x;z)=\nabla g(x)+Z$, and hence we could take $G(Z,C)=\sup_{x\in\mathcal{X}}\|\nabla g(x)\|_{C}+\|Z\|_{C}$. As a result, by Minkowski inequality, we have

B.3 Intermediate Results

Before discussing the proofs of Theorems 1 and 2, we need to state a few intermediate results which will be used in our analysis.

Here, we first bound the bias term. To do so, we use the following lemma:

We will find this lemma useful in our proofs. Another useful lemma that we will use it is the following:

Proof We proceed by induction. The base case that $n=1$ is immediate. Now, let us assume the result holds through index $n-1$, and we wish to prove it for index $n$. The concavity of $\sqrt{\cdot}$ guarantees that $\sqrt{b+a}\leq\sqrt{b}+\frac{1}{2\sqrt{b}}a$, and so

where the first inequality follows from the inductive hypothesis and the second one uses the concavity of $\sqrt{\cdot}$. ∎

B.4 Proof of Theorem 1

We first state a more general version of the theorem here:

Let $\mathcal{S}$ be a dataset with $n$ points sampled from distribution $P$. Let $C$ also be a diagonal and positive definite matrix. Consider running Algorithm 1 with $T=cn^{2}/b^{2}$, $A_{k}=C/B^{2}$ where $B>0$ is a positive real number and $c$ is given by Lemma 3.1. Then, with probability $1-1/n$, we have

where the expectation is taken over the internal randomness of the algorithm.

Proof Let $x^{\star}\in\mathop{\rm argmin}_{x\in\mathcal{X}}f(x;\mathcal{S})$. Also, for simplicity, we suppress the dependence of $f$ on $\mathcal{S}$ throughout the proof. First, by Lemma 3.2, we know that with probability at least $1-1/n$, we have

We consider the setting that this bound holds. Now, note that by Theorem 6 we have

Using Lemma B.1, we immediately obtain the following bound

Next, we substitute the value of $\alpha_{k}$ and use Lemma B.2 to obtain

where the last inequality follows from the fact that $\sqrt{x+y}\leq\sqrt{2}\left(\sqrt{x}+\sqrt{y}\right)$ for nonnegative real numbers $x$ and $y$. Plugging (17) into (16) completes the proof. ∎

B.5 Proof of Theorem 2

We first state the more general version of theorem:

Let $\mathcal{S}$ be a dataset with $n$ points sampled from distribution $P$. Let $C$ also be a diagonal and positive definite matrix. Consider running Algorithm 1 with $T=cn^{2}/b^{2}$ $A_{k}=C/B^{2}$ where $B>0$ is a positive real number and $c$ is given by Lemma 3.1. Then, with probability $1-1/n$, we have

where the expectation is taken over the internal randomness of the algorithm.

Proof Similar to the proof of Theorem 1, we choose $x^{\star}\in\mathop{\rm argmin}_{x\in\mathcal{X}}f(x;\mathcal{S})$. We suppress the dependence of $f$ on $\mathcal{S}$ throughout this proof as well. Again, we focus on the case that the bound

which we know its probability is at least $1-1/n$.

Similar to the proof of Theorem 1, and by using Lemma B.1, we could bound the second term with

Now, it just suffices to bound the first term. Note that

Appendix C Proof of Theorem 3

We begin with the following lemma, which upper bounds the bias from truncation.

Thus, if $Y=|\min(z_{j}^{2},\Delta^{2})-z_{j}^{2}|$ then $P(Y\geq tr^{2}\sigma_{j}^{2})\leq 2e^{-t}$ hence

where the last inequality follows since $\Delta=4r\sigma_{j}\log r$. ∎

The following lemma demonstrates that the random variable $Y_{i}=\min(z_{i,j}^{2},\Delta^{2})$ quickly concentrates around its mean.

Let $Z$ be a random vector satisfying Definition 4.1. Then with probability at least $1-\beta$,

Setting $t=r^{2}\sigma_{j}^{2}\frac{2\sqrt{\log(2/\beta)}}{\sqrt{n}}$ yields the result. ∎

Given Lemmas C.1 and C.2, we are now ready to finish the proof of Theorem 3.

First, privacy follows immediately, as each iteration $t$ is $(\varepsilon/T,\delta/T)$-DP (using standard properties of the Gaussian mechanism [DR14]), so basic composition implies that the final output is $(\varepsilon,\delta)$-DP. We now proceed to prove the claim about utility. Let $\rho_{t}^{2}$ be the truncation value at iterate $t$, i.e., $\rho_{t}=4r\log r/2^{t-1}$. First, note that Lemma C.2 implies that with probability $1-\beta/2$ for every $j\in[d]$

where the last inequality follows since $n\geq 400r^{4}\log(8d/\beta)$. Moreover, for $\sigma_{j}$ such that $\rho_{t}\geq 4r\sigma_{j}\log r$, Lemma C.1 implies that

Let us now prove that if $\sigma_{j}=2^{-k}$ then its value will be set at most at iterate $t=k$. Indeed at iterate $t=k$ we have $\rho_{t}=4r2^{-k}\log r\geq 4r\sigma_{j}\log r$ hence we have that using the triangle inequality and standard concentration resutls for Gaussian distributions that with probability $1-\beta/2$

where the last inequality follows since $n\varepsilon\geq 1000r^{2}T\sqrt{d}\log^{2}r\log(T/\delta)\log(4d/\beta)$. Thus, in this case we get that $\hat{\sigma}_{k,j}^{2}\geq\sigma_{j}^{2}/2\geq 2^{-k-1}$ hence the value of coordinate $j$ will best set at most at iterate $k$ hence $\hat{\sigma}_{j}\geq\sigma_{j}/2$.

On the other hand, we now assume that $\sigma_{j}=2^{-k}$ and show that the value of $\hat{\sigma}_{j}$ cannot be set before the iterate $t=k-3$ and hence $\hat{\sigma}_{j}\leq 2^{-k+3}\leq 8\sigma_{j}$. The above arguments show that at iterate $t$ we have $\hat{\sigma}_{t,j}^{2}\leq 3/2\sigma_{j}^{2}+\frac{1}{10\cdot 2^{2k}}\leq 2^{-2k+1}+\frac{1}{10\cdot 2^{2k}}\leq 2^{-2k+2}$ hence the first part of the claim follows.

To prove the second part, first note that $z_{j}$ is $r\sigma_{j}$-sub-Gaussian, hence using Theorem 2, it is enough to show that $G_{2p}(\hat{C})\leq O(G_{2p}(C))$ and that $\sum_{j=1}^{d}\hat{C}_{j}^{-1/2}\leq O(1)\cdot\sum_{j=1}^{d}C_{j}^{-1/2}$ where $C=(r\sigma_{j})^{-4/3}$ is the optimal choice of $C$ as in the bound (6). The first condition immediately follows from the definition of $G_{2p}$ since $\hat{C}_{j}\leq C_{j}$ for all $j\in[d]$. The latter condition follows immediately since $\frac{1}{2}\max(\sigma_{j},1/d^{2})\leq\hat{\sigma}_{j}$, implying

Appendix D Proofs of Section 5 (Lower bounds)

Let $M$ be $(\varepsilon,\delta)$-DP and $\mathcal{S}=(z_{1},\dots,z_{n})$ where $z_{i}\in\mathcal{Z}=\{-\sigma,\sigma\}^{d}$. Then

We are now ready to complete the proof of Proposition 1 using bucketing-based techniques. First, we assume without loss of generality that $\sigma_{j}\leq 1$ for all $1\leq j\leq d$ (otherwise we can divide by $\max_{1\leq j\leq d}\sigma_{j}$). Now, we define buckets of coordinates $B_{0},\dots,B_{K}$ such that

For $i=K$, we set $B_{K}=\{j:\sigma_{j}\leq 2^{-K}\}$. We let $\sigma_{\max}(B_{i})=\max_{j\in B_{i}}\sigma_{j}$ denote the maximal value of $\sigma_{j}$ inside $B_{i}$. Similarly, we define $\sigma_{\min}(B_{i})=\min_{j\in B_{i}}\sigma_{j}$. Focusing now on the $i$’th bucket, since $\sigma_{j}\geq\sigma_{\min}(B_{i})$ for all $j\in B_{i}$, Lemma D.1 now implies (as $d\log^{2}d\leq(n\varepsilon)^{2}$) the lower bound

To finish the proof of the theorem, it is now enough to prove that

where the second inequality follows since the maximum cannot be achieved for $i=K$ given our choice of $K=10\log d$, and the last inequality follows since $\sigma_{\max}(B_{i})\leq 2\sigma_{\min}(B_{i})$ for all $i\leq K-1$. This proves the claim.

D.2 Proof of Lemma D.1

Instead of proving lower bounds on the error of private mechanisms, it is more convenient for this result to prove lower bounds on the sample complexity required to achieve a certain error. Given a mechanism $M$ and data $\mathcal{S}\in\mathcal{Z}^{n}$, define the error of the mechanism to be:

The error of a mechanism for datasets of size $n$ is $\mathsf{Err}(M,n)=\sup_{\mathcal{S}\in\mathcal{Z}^{n}}\mathsf{Err}(M,\mathcal{S})$.

We let $n^{\star}(\alpha,\varepsilon)$ denote the minimal $n$ such that there is an $(\varepsilon,\delta)$-DP (with $\delta=n^{-\omega(1)}$) mechansim $M$ such that $\mathsf{Err}(M,n^{\star}(\alpha,\varepsilon))\leq\alpha$. We prove the following lower bound on the sample complexity.

If $\left\|{z}\right\|_{\infty}\leq 1$ then

To prove this result, we first state the following lower bound for constant $\alpha$ and $\varepsilon$ which follows from Theorem 3.2 in [TTZ15].

We now prove a lower bound on the sample complexity for small values of $\alpha$ and $\varepsilon$ which implies Proposition 3.

Let $\varepsilon_{0}\leq 0.1$. For $\alpha\leq\alpha_{0}/2$ and $\varepsilon\leq\varepsilon_{0}/2$,

Proof Assume there exists an $(\varepsilon,\delta)$-DP mechanism $M$ such that $\mathsf{Err}(M,n)\leq\alpha$. Then we now show that there is $M^{\prime}$ that is $(\varepsilon_{0},\frac{2\varepsilon_{0}}{\varepsilon}\delta)$-DP with $n^{\prime}=\Theta(\frac{\alpha\varepsilon}{\alpha_{0}\varepsilon_{0}}n)$ such that $\mathsf{Err}(M^{\prime},n^{\prime})\leq\alpha_{0}$. This proves the claim. Let us now show how to define $M^{\prime}$ given $M$. Let $k=\left\lfloor{\log(1+\varepsilon_{0})/\varepsilon}\right\rfloor$. For $\mathcal{S}^{\prime}\in\mathcal{Z}^{n^{\prime}}$, we define $\mathcal{S}$ to have $k$ copies of $\mathcal{S}^{\prime}$ and $(n-kn^{\prime})/2$ users which have $z_{i}=(\sigma,\dots,\sigma)$ and $(n-kn^{\prime})/2$ users which have $z_{i}=(-\sigma,\dots,-\sigma)$. Then we simply define $M^{\prime}(\mathcal{S}^{\prime})=M(\mathcal{S})$. Notice that now we have

Therefore for a given $\mathcal{S}^{\prime}$ we have that:

Thus if $n^{\prime}\geq\frac{2n\alpha}{k\alpha_{0}}$ then

Thus it remains to argue for the privacy of $M^{\prime}$. By group privacy, $M^{\prime}$ is $(k\varepsilon,\frac{e^{k\varepsilon}-1}{e^{\varepsilon}-1}\delta)$-DP, hence our choice of $k$ implies that $k\varepsilon\leq\varepsilon_{0}$ and $\frac{e^{k\varepsilon}-1}{e^{\varepsilon}-1}\delta\leq\frac{2\varepsilon_{0}}{\varepsilon}\delta$. ∎

D.3 Proof of Theorem 5

We assume without loss of generality that $\sigma_{j}\leq 1$ for all $1\leq j\leq d$ (otherwise we can divide by $\max_{1\leq j\leq d}\sigma_{j}$). We follow the bucketing-based technique we had in the proof of Proposition 1. We define buckets of coordinates $B_{0},\dots,B_{K}$ such that

For $i=K$, we set $B_{K}=\{j:\sigma_{j}\leq 2^{-K}\}$. We let $\sigma_{\max}(B_{i})=\max_{j\in B_{i}}\sigma_{j}$ denote the maximal value of $\sigma_{j}$ inside $B_{i}$. Similarly, we define $\sigma_{\min}(B_{i})=\min_{j\in B_{i}}\sigma_{j}$. Focusing now on the $i$’th bucket, since $\sigma_{j}\geq\sigma_{\min}(B_{i})$ for all $j\in B_{i}$, Proposition 2 now implies the lower bound

Since $d\leq(n\varepsilon)^{2}$, taking the maximum over buckets, we get that the error of any mechanism is lower bounded by:

To finish the proof, we only need to show now that

where the second inequality follows since the maximum cannot be achieved for $i=K$ given our choice of $K=10\log d$, and the last inequality follows since $\sigma_{\max}(B_{i})\leq 2\sigma_{\min}(B_{i})$ for all $i\leq K-1$. The claim follows.