Practical and Private (Deep) Learning without Sampling or Shuffling

Introduction

Differentially private stochastic gradient descent (DP-SGD) has become state-of-the-art in training private (deep) learning models . It operates by running stochastic gradient descent on noisy mini-batch gradientsGradient computed on a subset of the training examples, also called a mini-batch., with the noise calibrated such that it ensures differential privacy. The privacy analysis heavily uses tools like privacy amplification by sampling/shuffling to obtain the best privacy/utility trade-offs. Such amplification tools require that each mini-batch is a perfectly (uniformly) random subset of the training data. This assumption can make practical deployment prohibitively hard, especially in the context of distributed settings like federated learning (FL) where one has little control on which subset of the training data one sees at any time .

We propose a new online learning based DP algorithm, differentially private follow-the-regularized-leader (DP-FTRL), that has privacy/utility/computation trade-offs that are competitive with DP-SGD, and does not rely on privacy amplification. DP-FTRL significantly outperforms un-amplified DP-SGD at all privacy levels. In the higher-accuracy / lower-privacy regime, DP-FTRL outperforms even amplified DP-SGD. We emphasize that in the context of ML applications, using a DP mechanism even with a large $\varepsilon$ is practically much better for privacy than using a non-DP mechanism .

Privacy amplification and its perils: At a high-level, DP-SGD can be thought of as an iterative noisy state update procedure for $T$ steps operating over mini-batches of the training data. For a time step $t\in[T]$ and an arbitrary mini-batch of size $k$ from a data set $D$ of size $n$, let $\sigma_{t}$ be the standard deviation of the noise needed in the $t^{th}$ update to satisfy $\varepsilon_{t}$-differential privacy. If the mini-batch is chosen u.a.r. and i.i.d. from $D$ at each time stepOne can also create a mini-batch with Poisson sampling , except the batch size is now a random variable. For brevity, we focus on the fixed batch setting. $t$, then privacy amplification by sampling allows one to scale down the noise to $\sigma_{t}\cdot(k/n)$, while still ensuring $\varepsilon_{t}$-differential privacy.A similar argument holds for amplification by shuffling , when the data are uniformly shuffled at the beginning of every epoch.We do not consider privacy amplification by iteration in this paper, as it only applies to smooth convex functions. Such amplification is crucial for DP-SGD to obtain state-of-the-art models in practice when $k\ll n$.

There are two major bottlenecks for such deployments: i) For large data sets, achieving uniform sampling/shuffling of the mini-batches in every round (or epoch) can be prohibitively expensive in terms of computation and/or engineering complexity, ii) In distributed settings like federated learning (FL) , uniform sampling/shuffling may be infeasible to achieve because of widely varying available population at each time step. Our work answers the following question in affirmative: Can we design an algorithm that does not rely on privacy amplification, and hence allows data to be accessed in an arbitrary order, while providing privacy/utility/computation trade-offs competitive with DP-SGD?

DP-FTRL and amplification-free model training: DP-FTRL can be viewed as a differentially private variant of the follow-the-regularized-leader (FTRL) algorithm . The main idea in DP-FTRL is to use the tree aggregation trick to add noise to the sum of mini-batch gradients, in order to ensure privacy. Crucially, it deviates from DP-SGD by adding correlated noise across time steps, as opposed to independent noise. This particular aspect of DP-FTRL allows it to get strong privacy/utility trade-off without relying on privacy amplification.

Federated Learning (FL) and DP-FTRL: There has been prior work detailing challenges for obtaining strong privacy guarantees that incorporate limited availability of participating clients in real-world applications of federated learning. Although there exist techniques like the Random Check-Ins that obtain privacy amplification for FL settings, implementing such techniques may still require clients to keep track of the number of training rounds being completed at the server during their period(s) of availability to be able to uniformly randomize their participation. On the other hand, since the privacy guarantees of DP-FTRL (Algorithm 1) do not depend on any type of privacy amplification, it does not require any local/central randomness apart from noise addition to the model updates.

Appendices A and Section 3 describe additional related work and background, respectively.

Regret Minimization: At every time step $t\in[n]$, while observing samples $[d_{1},\ldots,d_{t-1}]$, the algorithm $\mathcal{A}$ outputs a model $\theta_{t}\in\mathcal{C}$ which is used to predict on example $d_{t}$. The performance of $\mathcal{A}$ is measured in terms of regret against an arbitrary post-hoc comparator $\theta^{*}\in\mathcal{C}$:

Excess Risk Minimization: In this setting, we look at the problem of minimizing the excess population risk. Assuming the data set $D$ is sampled i.i.d. from a distribution $\tau$, and the algorithm $\mathcal{A}$ outputs $\widehat{\theta}\in\mathcal{C}$, we want to minimize

All the algorithms in this paper guarantee differential privacy and Rényi differential privacy (See Section 3 for details). The definition of a single data record can be one training example (a.k.a., example level privacy), or a group of training examples from one individual (a.k.a., user level privacy). Except for the empirical evaluations in the FL setting, we focus on example level privacy. The specific definition of differential privacy (DP) we use is in Definition 1.1, which is semantically similar to the traditional add/remove notion of DP , where two data sets are neighbors if their symmetric difference is one. In particular, it is a special instantiation of [24, Definition II.3]. An advantage of Definition 1.1 is that it allows capturing the notion of neighborhood defined by addition/removal of single data record in the data set, without having the necessity to change the number of records of the data set ($n$). Since the algorithms in this paper are motivated from natural streaming/online algorithms, Definition 1.1 is convenient to operate with. Similar to the traditional add/remove notion , Definition 1.1 can capture the regular replacement version of DP (originally defined in , where the notion of neighborhood is defined by replacing any data record with its worst-case alternative), by incurring up to a factor of two in the privacy parameters $\varepsilon$ and $\delta$.

Let $\mathcal{D}$ be the domain of data records, $\bot\not\in\mathcal{D}$ be a special element, and let $\widehat{\mathcal{D}}=\mathcal{D}\cup\{\bot\}$ be the extended domain. A randomized algorithm $\mathcal{A}:\widehat{\mathcal{D}}^{n}\to\mathcal{S}$ is $(\varepsilon,\delta)$-differentially private if for any data set $D\in\widehat{\mathcal{D}}^{n}$ and any neighbor $D^{\prime}\in\widehat{\mathcal{D}}^{n}$ (formed from $D$ by replacing one record with $\bot$), and for any event $S\in\mathcal{S}$, we have

where the probability is over the randomness of $\mathcal{A}$.

In Algorithm 1 we treat $\bot$ specially, namely assuming it always produces a zero gradient.

2 Our Contributions

Our primary contribution in this paper is a private online learning algorithm: differentially private follow-the-regularized leader (DP-FTRL) (Algorithm 1). We provide tighter privacy/utility trade-offs based on DP-FTRL (see Table 1 for a summary), and show how it can be easily adapted to train (federated) deep learning models, with comparable, and sometimes even better privacy/utility/computation trade-offs as DP-SGD. We summarize these contributions below.

DP-FTRL algorithm: We provide DP-FTRL, a differentially private variant of the Follow-the-regularized-leader (FTRL) algorithm for online convex optimization (OCO). We also provide a variant called the momentum DP-FTRL that has superior performance in practice. provided a instantiation of DP-FTRL specific to linear losses. provided an algorithm similar to DP-FTRL, where instead of just linearizing the loss, a quadratic approximation to the regularized loss was used.

Population risk guarantees: In Section 5.3, using the standard online-to-batch conversion , we obtain a population risk guarantee for DP-FTRL. For general Lipschitz convex losses, the population risk for DP-FTRL in Theorem C.5 is same as that in [6, Appendix F] (up to logarithmic factors), but the advantage of DP-FTRL is that it is a single pass algorithm (over the data set $D$), as opposed to requiring $n$ passes over the data. Thus, we provide the best known population risk guarantee for a single pass algorithm that does not rely on convexity for privacy. While the results in have a tighter (and optimal) excess population risk of $\widetilde{\Theta}(1/\sqrt{n}+\sqrt{p}/(\varepsilon n))$, they either require convexity to ensure privacy for a single pass algorithm, or need to make $n$-passes over the data. For restricted classes like linear and least-squared losses, DP-FTRL can achieve the optimal population risk via the tighter stochastic regret guarantee. Whether DP-FTRL can achieve the optimal excess population risk in the general convex setting is left as an open problem.

Empirical contributions: In Sections 6 and 7 we study some trade-offs between privacy/utility/computation for DP-FTRL and DP-SGD. We conduct our experiments on four benchmark data sets: MNIST, CIFAR-10, EMNIST, and StackOverflow. We start by fixing the computation available to the techniques, and observing privacy/utility trade-offs. We find that DP-FTRL achieves better utility compared to DP-SGD for moderate to large $\varepsilon$. In scenarios where amplification cannot be ensured (e.g., due to practical/implementation constraints), DP-FTRL provides substantially better performance as compared to unamplified DP-SGD. Moreover, we show that with a modest increase in the computation cost, DP-FTRL, without any need for amplification, can match the performance of amplified DP-SGD. Next, we focus on privacy/computation trade-offs for both the techniques when a utility target is desired. We show that DP-FTRL can provide better trade-offs compared to DP-SGD for various accuracy targets, which can result in significant savings in privacy/computation cost as the size of data sets becomes limited.

Errata and Fixes for the ICML 2021 version

In this section we provide an errata for the ICML-2021 proceedings version of this paper. For the no-tree-restart case of DP-FTRL, the privacy accounting of Theorem D.2 in was erroneous, as it incorrectly computed the sensitivity of the complete binary tree. Specifically, the analysis did not take into account that if DP-FTRL is executed across multiple epochs of the training data, then a single user can both contribute to multiple leaf nodes in the tree, and can contribute more than once to a single non-leaf node. In Section D we provide corrected versions of the theorem, and also provide corrected empirical evaluation for MNIST, CIFAR-10, and EMNIST based on this (these were the only empirical results affected). These experiments are detailed in Section 7, and the corresponding appendices. Qualitatively, when DP-FTRL and DP-SGD (the amplified version) are compared for large number of epochs of training, the crossover point (w.r.t. $\varepsilon$) where DP-FTRL outperforms DP-SGD shifts to a larger value. However, for small number of epochs of training, the crossover point remains unchanged.

Background

Differential Privacy: Throughout the paper, we use the notion of approximate differential privacy and Rényi differential privacy (RDP) . For meaningful privacy guarantees, $\varepsilon$ is assumed to be a small constant, and $\delta\ll 1/|D|$.

Analogous to the definitiion of $(\varepsilon,\delta)$-differential privacy in Definition 1.1, a randomized algorithm $\mathcal{A}$ is $(\alpha,\varepsilon)$-RDP if the condition on $\mathcal{A}(D)$ and $\mathcal{A}(D^{\prime})$ in Definition 1.1 are replaced with the following:

Abadi et al. and Mironov have shown that an $(\alpha,\varepsilon)$-RDP algorithm guarantees $\left(\varepsilon+\frac{\log(1/\delta)}{\alpha-1},\delta\right)$-differential privacy. Follow-up works provide tighter conversions. We used the conversion in in our experiments.

Using the analysis of the Gaussian mechanism, we know that such an update step guarantees $(\alpha,\alpha/2\sigma^{2})$-RDP with respect to the mini-batch $\mathcal{B}$. By parallel composition, running one epoch with disjoint mini-batches guarantees $(\alpha,\alpha/2\sigma^{2})$-RDP. On the other hand, previous works has shown that if $\mathcal{B}$ is chosen uniformally at random from $[n]$, or if we use poisson sampling to collect a batch of samples $\mathcal{B}$, then one step would guarantee $\left(\alpha,O\left(\alpha/2\sigma^{2}\cdot(|\mathcal{B}|/n)^{2}\right)\right)$-RDP.

Smith and Thakurta used this aggregation algorithm to build a nearly optimal algorithms for private online learning. Importantly, this work showed the privacy guarantee holds even for adaptively chosen sequences $\{d_{t}\}_{t=1}^{T}$, which is crucial for model training tasks.

Private Follow-The-Regularized-Leader

In this section, we provide the formal description of the DP-FTRL algorithm (Algorithm 1) and its privacy analysis. We then show that a variant of differentially private stochastic gradient descent (DP-SGD) can be viewed of as an instantiation of DP-FTRL under appropriate choice of learning rate.

Later in the paper, we provide two variants of DP-FTRL (momentum DP-FTRL, and DP-FTRL for least square losses) which will have superior privacy/utility trade-offs for certain problem settings.

DP-FTRL is formally described in Algorithm 1. There are three functions, InitializeTree , AddToTree , GetSum , that correspond to the tree-aggregation algorithm. At a high-level, InitializeTree initializes the tree data structure $\mathcal{T}$, AddToTree allows adding a new gradient $\nabla_{t}$ to $\mathcal{T}$, and GetSum returns the prefix sum $\sum\limits_{i=1}^{t}\nabla_{i}$ privately. In our experiments (Section 7), we use the iterative estimator from to obtain the optimal estimate of the prefix sums in GetSum . Please refer to Appendix B.1 for the formal algorithm descriptions.

It can be shown that the error introduced in DP-FTRL due to privacy is dominated by the error in estimating $\sum\limits_{i=1}^{t}\nabla_{t}$ at each $t\in[n]$. It follows from that for a sequence of (adaptively chosen) vectors $\{\nabla_{t}\}_{t=1}^{n}$, if we perform ${\texttt{AddToTree}}\,(\mathcal{T},t,\nabla_{t})$ for each $t\in[n]$, then we can write ${\texttt{GetSum}}\,(\mathcal{T},t)=\sum_{i=1}^{t}\nabla_{i}+\boldsymbol{b}_{t}$ where $\boldsymbol{b}_{t}$ is normally distributed with mean zero, and $\forall t\in[n],\left\|\boldsymbol{b}_{t}\right\|_{2}\leq L\sigma\sqrt{p\lceil\lg(n)\rceil\ln(n/\beta)}$ w.p. at least $1-\beta$.

Momentum Variant: We find that using a momentum term $\gamma\in$ with Line 7 in Algorithm 1 replaced by

gives superior empirical privacy/utility trade-off compared to the original algorithm when training non-convex models. Throughout the paper, we refer to this variant as momentum DP-FTRL, or DP-FTRLM. Although we do not provide formal regret guarantee for this variant, we conjecture that the superior empirical performance is due to the following reason. The noise added by the tree aggregation algorithm is always bounded by $O(\sqrt{p\ln(1/\delta)}\cdot\ln(n)/\varepsilon)$. However, the noise at time step $t$ and $t+1$ can differ by a factor of $O(\sqrt{\ln n})$. This creates sudden jumps in between the output models comparing to DP-SGD. The momentum can smooth out these jumps.

Privacy analysis: In Theorem 4.1, we provide the privacy guarantee for Algorithm 1 and its momentum variant (with proof in Appendix B.2). In Appendix D, we extend it to multiple passes over the data set $D$, and batch sizes $>1$.

Algorithm 1 (and its momentum variant) guarantees $\left(\alpha,\frac{\alpha\lceil\lg(n+1)\rceil}{2\sigma^{2}}\right)$-Rényi differential privacy, where $n$ is the number of samples in $D$. Setting $\sigma=\frac{\sqrt{2\lceil\lg(n+1)\rceil\ln(1/\delta)}}{\varepsilon}$, one can guarantee $(\varepsilon,\delta)$-differential privacy, for $\varepsilon\leq 2\ln(1/\delta)$.

2 Comparing the Noise Added by DP-SGD with privacy amplification, and DP-FTRL

Let $D=\{d_{1},\dots,d_{n}\}$ be the data set of size $n$. Consider a general noisy-SGD algorithm with update rule

where $\eta$ is the learning rate and $\boldsymbol{a}_{t}$ is some random noise. DP-SGD with privacy amplification, that achieves $(\varepsilon,\delta)$-DP, can be viewed as a special case, where $d_{t}$ is sampled u.a.r. from $D$, and $\boldsymbol{a}_{t}$ is drawn i.i.d. from $\mathcal{N}\left(0,O\left(\frac{L^{2}\ln(1/\delta)}{n\varepsilon^{2}}\right)\right)$ . If we expand the recursive relation, we can see that the total amount of noise added to the estimation of $\theta_{t+1}$ is $\eta\sum\limits_{i=1}^{t}\boldsymbol{a}_{i}=\mathcal{N}\left(0,O\left(\frac{\eta^{2}L^{2}t\cdot\ln(1/\delta)}{n\varepsilon^{2}}\right)\right)$.

For DP-FTRL, define $\boldsymbol{b}_{0}=0$, and let $\boldsymbol{b}_{t}$ be the noise added by the tree-aggregation algorithm at time step $t$ of Algorithm $\mathcal{A}_{\sf FTRL}$. We can show that DP-FTRL, that achieves $(\varepsilon,\delta)$-DP, is equivalent to (3), where i) the noise $\boldsymbol{a}_{t}=\boldsymbol{b}_{t}-\boldsymbol{b}_{t-1}$, ii) the data samples $d_{t}$’s are drawn in sequence from $D$, and iii) the learning rate $\eta$ is set to be $\frac{1}{\lambda}$, where $\lambda$ is the regularization parameter in Algorithm $\mathcal{A}_{\sf FTRL}$. In this variant of noisy SGD, the total noise added to the model is $\eta\sum\limits_{i=1}^{t}\boldsymbol{a}_{i}=\eta\boldsymbol{b}_{t}=\mathcal{N}\left(0,O\left(\frac{\eta^{2}L^{2}\cdot\ln(1/\delta)\cdot\ln^{2}(n)}{\varepsilon^{2}}\right)\right)$. The variance of the noise in $\boldsymbol{b}_{t}$ follows from the following two facts: i) Theorem 4.1 provides the explicit noise variance ($L^{2}\sigma^{2}$) to be added to ensure $(\varepsilon,\delta)$-differential privacy to the tree-aggregation scheme in Algorithm 1 (Algorithm $\mathcal{A}_{\sf FTRL}$), and ii) The ${\texttt{GetSum}}\,(\mathcal{T},t)$ operation in Algorithm $\mathcal{A}_{\sf FTRL}$, only requires $O(\ln(n))$ nodes of the binary tree in the tree-aggregation scheme.

Under the same form of the update rule, we can roughly (as the noise is not independent in the DP-FTRL case) compare the two algorithms. When $t=\Omega(n)$, the noise of DP-SGD with privacy amplification matches that of DP-FTRL up to factor of ${\sf polylog}\left(n\right)$. As a result, we expect (and as corroborated by the population risk guarantees) sampled DP-SGD and DP-FTRL to perform similarly. (In Appendix B.3 we provide a formal equivalence.)

It is worth noting that the above calculation overestimates the variance of $\boldsymbol{b}_{t}$ used for DP-FTRL in the above analysis. If we look carefully at the tree-aggregation scheme, it should be evident that $\boldsymbol{b}_{t}\sim\mathcal{N}\left(0,O\left(\frac{\eta^{2}L^{2}\cdot\ln(1/\delta)\cdot\ln(n)\cdot\nu}{\varepsilon^{2}}\right)\right)$, where $\nu\in\left[\lceil\lg(n+1)\rceil\right]$ is the number of ones in the binary representation of $t\in[n]$. Furthermore, the variance is reduced by a factor of $\approx\sqrt{2}$ by using techniques from . Because of these, and due to the fact that privacy amplification by sampling is most effective at smaller values of $\varepsilon$, in our experiments we see that DP-FTRL is competitive to DP-SGD with amplification, even when there is a ${\sf polylog}(n)$ gap in our analytical noise variance computation.

Regret and Population Risk Guarantees

2 Stochastic Regret for Least-squared Losses

A straightforward modification of DP-FTRL, $\mathcal{A}_{\textsf{FTRL-LS}}$ (Algorithm 2 in Appendix C.2), achieves the following.

$O\left(L^{2}\rho^{2}\left(\sqrt{\frac{\ln(n)}{n}}+\frac{\sqrt{p\ln^{5}(n/\beta)\cdot\ln(1/\delta)}}{\varepsilon n}\right)\right).$

The arguments of can be extended to show a similar regret guarantee in expectation only, whereas ours is a high-probability guarantee.

3 Excess Risk via Online-to-Batch Conversion

Using the online-to-batch conversion , from Theorem 5.1, we can obtain a population risk guarantee $O\left(\left(\sqrt{\frac{{\ln(1/\beta)}}{n}}+\sqrt{\frac{p^{1/2}\ln^{2}(1/\delta)\ln(1/\beta)}{\varepsilon n}}\right)\right)$, where $\beta$ is the failure probability. (See Appendix C.3 for a formal statement.) For least squares and linear losses, using the regret guarantee in Theorem 5.3 and online-to-batch conversion, one can actually achieve the optimal population risk (up to logarithic factors) $O\left(\sqrt{\frac{\ln(n)\ln(1/\beta)}{n}}+\frac{\sqrt{p\ln^{5}(n/\beta)\cdot\ln(1/\delta)}}{\varepsilon n}\right)$.

Practical Extensions

In this section we consider two practical extensions to Algorithm 1 that are important for real-world use, and are considered in our empirical evaluations.

Multiple participations: While Algorithm 1 is stated for a single epoch of training, i.e., where each sample in the data set is used once for obtaining a gradient update, there can be situations where $E>1$ epochs of training are preferred. We consider three algorithm variants that support this:

DP-FTRL-TreeRestart: The simplest approach, discussed in detail Section D.1, is to simply use separate trees for each epoch, and compose the privacy costs using strong composition.

DP-FTRL-NoTreeRestart: This approach, considered in detail in Section D.2, allows a single aggregation tree to span multiple epochs (possibly even processing data in an arbitrary order as long as each $d_{i}$ occurs in at most $E$ steps). This requires a more nuanced privacy analysis, as the same training example occurs in multiple leaf nodes, and further can influence interior nodes multiple times, increasing the sensitivity.

DP-FTRL-SometimesRestart: One can combine the above ideas, which can yield improved privacy/utility tradeoffs. For example (as in the experiments of Section F.2), one can perform 100 epochs of training, resetting the tree every 20 epochs, using the analysis for DP-FTRL-NoTreeRestart within each group of 20 epochs with a shared aggregation tree, and then combining these 5 blocks via strong composition as in Section D.1. This approach is discussed in depth in Section D.3.

Empirical Evaluation

We provide an empirical evaluation of DP-FTRL on four benchmark data sets, and compare its performance with the state-of-the-art DP-SGD on three axes: (1) Privacy, measured as an $(\varepsilon,\delta)$-DP guarantee on the mechanism, (2) Utility, measured as (expected) test set accuracy for the trained model under the DP guarantee, and (3) Computation cost, which we measure in terms of mini-batch size and number of training iterations. The code is open sourcedhttps://github.com/google-research/federated/tree/master/dp_ftrl for FL experiments, and https://github.com/google-research/DP-FTRL for centralized learning..

First, we evaluate the privacy/utility trade-offs provided by each technique at fixed computation costs. Second, we evaluate the privacy/computation trade-offs each technique can provide at fixed utility targets. A natural application for this is distributed frameworks such as FL, where the privacy budget and a desired utility threshold can be fixed, and the goal is to satisfy both constraints with the least computation. Computational cost is of critical importance in FL, as it can get challenging to find available clients with increasing mini-batch size and/or number of training rounds.

We show the following results: (1) DP-FTRL provides superior privacy/utility trade-offs than unamplified DP-SGD, (2) For a modest increase in computation cost, DP-FTRL (that does not use any privacy amplification) can match the privacy/utility trade-offs of amplified DP-SGD for all privacy regimes, and further (3) For regimes with large privacy budgets, DP-FTRL achieves higher accuracy than amplified DP-SGD even at the same computation cost, (4) For realistic data set sizes, DP-FTRL can provide superior privacy/computation trade-offs compared to DP-SGD.

Datasets: We conduct our evaluation on three image classification tasks, MNIST , CIFAR-10 , EMNIST (ByMerge split) ; and a next word prediction task on StackOverflow data set . Since StackOverflow is naturally keyed by users, we assume training in a federated learning setting, i.e., using the Federated Averaging optimizer for training over users in StackOverflow. The privacy guarantee is thus user-level, in contrast to the example-level privacy for the other three datasets (see Definition 1.1).

For all experiments with DP, we set the privacy parameter $\delta$ to $10^{-5}$ on MNIST and CIFAR-10, and $10^{-6}$ on EMNIST and StackOverflow, s.t. $\delta<n^{-1}$, where $n$ is the number of users in StackOverflow (or examples in the other data sets).

Model Architectures: For all the image classification tasks, we use small convolutional neural networks as in prior work . For StackOverflow, we use the one-layer LSTM network described in . See Appendix E.1 for more details.

Optimizers: We consider DP-FTRL with mini-batch model updates, and multiple epochs. In the centralized training experiments, we use DP-FTRL-TreeRestart in this section with a small number of epochs. In Appendix F.2, we provides more results for DP-FTRL-SometimesRestart for a larger number of epochs. For StackOverflow, we always use DP-FTRL-TreeRestart and there are less than five restarts even for 1000 clients per round due to the large population. We provide a privacy analysis for both approaches in Appendix D. We also consider the momentum variant DP-FTRLM, and find that DP-FTRLM with momentum $0.9$ always outperforms DP-FTRL. Similarly, for DP-SGD , we consider its momentum variant (DP-SGDM), and report the best-performing variant in each task. See Appendix E.2 for a comparison of the two optimizers for both techniques.

2 Privacy/Utility Trade-offs with Fixed Computation

In Figure 1, we show accuracy / privacy tradeoffs (by varying the noise multiplier) at fixed computation costs. Since both DP-FTRL and DP-SGD require clipping gradients from each sample and adding noise to the aggregated update in each iteration, we consider the number of iterations and the minibatch size as a proxy for computation cost. For each experiment, we run five independent trials, and plot the mean and standard deviation of the final test accuracy at different privacy levels. We provide details of hyperparameter tuning for all the techniques in Appendix F.1.

DP-SGD is the state-of-the-art technique used for private deep learning, and amplification by subsampling (or shuffling) forms a crucial component in its privacy analysis. Thus, we take amplified DP-SGD (or its momentum variant when performance is better) at a fixed computation cost as our baseline. We fix the (samples in mini-batch, training iterations) to (250, 1200) for MNIST, (500, 500) for CIFAR-10, and (500, 6975) for EMNIST. These number of steps correspond to $5$ epochs for the smaller batch size and $20$ epochs for the larger batch size. Our goal is to achieve equal or better tradeoffs without relying on any privacy amplification. As has been mentioned before, we use the DP-FTRL-TreeRestart variant of DP-FTRL in this section. Additionally, we make use of a trick where we add additional nodes to the aggregation tree to ensure we can use the root as a low-variance estimate of the total gradient sum for each epoch; details are given in Appendix D.3.1. The privacy computation follows from Appendix D.2.1 and D.3.1.

DP-SGD without any privacy amplification (“DP-SGD (no-amp)”) cannot achieve this: For all the data sets, the accuracy with DP-SGD (no-amp) at the highest $\varepsilon$ in Figure 1 is worse than the accuracy of the DP-SGD baseline even at its lowest $\varepsilon$. Further, if we increase the computation by four times (increasing the mini-batch size by four times), the privacy/utility trade-offs of “DP-SGD (no-amp) 4x” are still substantially worse than the private baseline.

For DP-FTRLM at the same computation cost as our DP-SGD baseline, as the privacy parameter $\varepsilon$ increases, the relative performance of DP-FTRLM improves for each data set, even outperforming the baseline for larger values of $\varepsilon$. Further, if we increase the batch size by four times for DP-FTRLM, its privacy-utility trade-off almost always matches or outperforms the amplified DP-SGD baseline, affirmatively answering this paper’s primary question. In particular, for CIFAR-10 (Figure 1(b)), “DP-FTRLM 4x” provides superior performance than the DP-SGD even for the lowest $\varepsilon$.

The number of epochs used here is relatively small. We chose to consider this setting as the advantage of DP-FTRL is more significant in such regime. In Appendix F.2, we consider running $100$ epochs on CIFAR-10 and $50$ epochs on EMNIST using the DP-FTRL-SometimesRestart variant. The results demonstrate similar trends, except that the “cross-over” point of $\varepsilon$ after which DP-FTRL outperforms DP-SGD shifts right (but is still $<15$).

We observe similar results for StackOverflow with user-level DP in Figure 2(a). We fix the computation cost to 100 clients per round (also referred to as the report goal), and $1600$ training rounds. DP-SGDM (or more precisely in this case, DP-FedAvg with server momentum) is our baseline. For DP-SGDM without privacy amplification (DP-SGDM no-amp), the privacy/accuracy trade-off never matches that of the DP-SGDM baseline, and gets significantly worse for lower $\varepsilon$. With a 4x increase in report goal, DP-SGDM no-amp nearly matches the privacy/utility trade-off of the DP-SGD baseline, outperforming it for larger $\varepsilon$.

For DP-FTRLM, with the same computation cost as the DP-SGDM baseline, it outperforms the baseline for the larger $\varepsilon$, whereas for the four-times increased report goal, it provides a strictly better privacy/utility trade-off. We conclude DP-FTRL provides superior privacy/utility trade-offs than unamplified DP-SGD, and for a modest increase in computation cost, it can match the performance of DP-SGD, without the need for privacy amplification.

3 Privacy/Computation Trade-offs with Fixed Utility

For a sufficiently large data set / population, better privacy vs. accuracy trade-offs can essentially always be achieved at the cost of increased computation. Thus, in this section we slice the privacy/utility/computation space by fixing utility (accuracy) targets, and evaluating how much computation (report goal) is necessary to achieve different $\varepsilon$ for StackOverflow. Our non-private baseline achieves an accuracy of 25.15%, and we fix 24.5% (2.6% relative loss) and 23% (8.6% relative loss) as our accuracy targets. Note that from the accuracy-privacy trade-offs presented in Figure 2(a), achieving even 23% for either DP-SGD or DP-FTRL will result in a large $\varepsilon$ for the considered report goals.

For each target, we tune hyperparameters (see Appendix G.1 for details) for both DP-SGDM and DP-FTRLM at a fixed computation cost to obtain the maximum noise scale for each technique while ensuring the trained models meet the accuracy target. Specifically, we fix a report goal of 100 clients per round for 1600 training rounds, and tune DP-SGD and DP-FTRL for 15 noise multipliers, ranging from $(0,0.3)$ for DP-SGD, and $(0,1.13)$ for DP-FTRL. At this report goal, for noise multiplier $0.3$, DP-SGD provides $\sim 19\%$ accuracy at $\varepsilon\sim 18.2$, whereas for noise multiplier $1.13$ DP-FTRL provides $\sim 21\%$ accuracy at $\varepsilon\sim 18.7$. We provide the results in Figure 2(b).

For each target accuracy, we choose the largest noise multiplier for each technique that results in the trained model achieving the accuracy target. For accuracies (23%, 24.5%), we select noise multipliers (0.035, 0.007) for DP-SGDM, and (0.387, 0.149) for DP-FTRLM, respectively. This data allows us to evaluate the privacy/computation trade-offs for both techniques, assuming the accuracy stays constant as we scale up the noise and report goal together (maintaining a constant signal-to-noise ratio while improving $\varepsilon$). This assumption was introduced and validated by , which showed that keeping the clipping norm bound, training rounds, and the scale of the noise added to the model update constant, increasing the report goal does not change the final model accuracy.

We plot the results in Figure 2(c). We see that for utility target 24.5% and $\delta=10^{-6}$, DP-FTRLM achieves any privacy $\varepsilon\in(0,50)$ at a lower computational cost than DP-SGDM. For utility target 23%, we observe the same behavior for $\varepsilon>8.8$.

Conclusion

In this paper we introduce the DP-FTRL algorithm, which we show to have the tightest known regret guarantees under DP, and have the best known excess population risk guarantees for a single pass algorithm on non-smooth convex losses. For linear and least-squared losses, we show DP-FTRL actually achieves the optimal population risk. Furthermore, we show on benchmark data sets that DP-FTRL, which does not rely on any privacy amplification, can outperform amplified DP-SGD at large values of $\varepsilon$, and be competitive to it for all ranges of $\varepsilon$ for a modest increase in computation cost (batch size). This work leaves two main open questions: i) Can DP-FTRL achieve the optimal excess population risk for all convex losses in a single pass?, and ii) Can one tighten the empirical gap between DP-SGD and DP-FTRL at smaller values of $\varepsilon$, possibly via a better estimator of the gradient sums from the tree data structure?

Acknowledgements

We would specially thank Thomas Steinke for providing us with dynamic programming based privacy accounting scheme (and its associated proof) for DP-FTRL-NoTreeRestart. We would also like to thank Adam Smith for suggesting the use of for variance reduction, Vinith Suriyakumar for noticing an error in a reported empirical result, and Yin-Tat Lee for independently finding the privacy accounting bug in multi-pass DP-FTRL-NoTreeRestart. We would additionally like to thank Borja Balle and Satyen Kale for the helpful discussions through the course of this project.

References

Appendix A Other Related Work

Differentially private empirical risk minimization (ERM) and private online learning are well-studied areas in the privacy literature This is only a small representative subset of the literature.. The connection between private ERM and private online learning was first explored in , and the idea of using stability induced by differential privacy for designing low-regret algorithms was explored in . To the best of our knowledge, this paper for the first time explores the idea using a purely online learning algorithm for training deep learning models, without relying on any stochasticity in the data for privacy.

Appendix B Missing Details from Section 4

In this section we provide the formal details of the tree aggregation scheme used in Algorithm 1 (Algorithm $\mathcal{A}_{\sf FTRL}$).

${\texttt{AddToTree}}\,(\mathcal{T},t,\boldsymbol{v})$: Add $\boldsymbol{v}$ to all the nodes along the path to the root of $\mathcal{T}$, starting from $t$-th leaf node.

${\texttt{GetSum}}\,(\mathcal{T},t)$: Let $[\texttt{node}_{1},\ldots,\texttt{node}_{h}]$ be the list of nodes from the root of $\mathcal{T}$ to the $t$-th leaf node, with $\texttt{node}_{1}$ being the root node and $\texttt{node}_{h}$ being the leaf node.

Initialize $\boldsymbol{s}\leftarrow{\bf 0}^{p}$ and convert $t$ to binary in $h$ bit representation $[b_{1},\ldots,b_{h}]$, with $b_{1}$ being the most significant bit.

For each $j\in[h]$, if $b_{j}=1$, then add the value in left sibling of $\texttt{node}_{j}$ to $\boldsymbol{s}$. Here if $\texttt{node}_{j}$ is the left child, then it is treated as its own left sibling.

Incorporating the iterative estimator from : Here, we state a variant of the ${\texttt{GetSum}}\,(\mathcal{T},t)$ function (called ${\texttt{GetSumReducedVariance}}\,(\mathcal{T},t)$) based on the variance reduction technique used in . The main idea is as follows: In the estimator for ${\texttt{GetSum}}\,(\mathcal{T},t)$ above, each $\texttt{node}_{j}$ refers to a noisy/private estimate of all the nodes in the sub-tree of $\mathcal{T}$ rooted at $\texttt{node}_{j}$. Notice that one can obtain independent estimates of the same, with one for each level of the sub-tree rooted at $\texttt{node}_{j}$, by summing up the nodes at the corresponding level. Of course, the variance of each of these estimates will be different. provided an estimator to combine these independent estimates in order to lower the overall variance in the final estimate. In the following, we provide the formal description of ${\texttt{GetSumReducedVariance}}\,(\mathcal{T},t)$. The text colored in blue is the only difference from ${\texttt{GetSum}}\,(\mathcal{T},t)$. The recurrent updating rule in Equation 4 only use the nodes “below” the current node to reduce the variance as we can not access the future gradients for a streaming algorithm. In practice, the value of the left node of a sub-tree $\boldsymbol{r}^{\prime}_{[x:y]}$ is stored in the worst-case $\log_{2}(t)+1$ memory and only the right node will be recursively calculated on the fly.

${\texttt{GetSumReducedVariance}}\,(\mathcal{T},t)$: Let $[\texttt{node}_{1},\ldots,\texttt{node}_{h}]$ be the list of nodes from the root of $\mathcal{T}$ to the $t$-th leaf node, with $\texttt{node}_{1}$ being the root node and $\texttt{node}_{h}$ being the leaf node.

Initialize $\boldsymbol{s}\leftarrow{\bf 0}^{p}$ and convert $t$ to binary in $h$ bit representation $[b_{1},\ldots,b_{h}]$, with $b_{1}$ being the most significant bit.

For each $j\in[h]$, if $b_{j}=1$, then do the following.

Indexing the leaf nodes $1,2,\dots$, for any two leaf node indices $\texttt{left}\leq\texttt{right}$, let $r_{\texttt{left}:\texttt{right}}\leftarrow$ value in $\mathcal{T}$ corresponding to the least common ancestor of left and right.

For the sub-tree rooted at the left sibling of $\texttt{node}_{j}$ (or $\texttt{node}_{j}$ itself if it is the left child), let $[a:b]$ be the indices of the leaf nodes in this subtree of $\mathcal{T}$.

Estimate $\boldsymbol{s}_{[x:z]}$ representing the sum of the values in leaf nodes $x$ through $z$ recursively as follows:

with base case $\boldsymbol{r}^{\prime}_{[x:x]}=\boldsymbol{r}_{[x:x]}$, which is simply the value at leaf $x$.

Add $\boldsymbol{s}_{[a:b]}$ to $\boldsymbol{s}$.

B.2 Proof of Theorem 4.1

Notice that in Algorithm 1, all accesses to private information is only through the tree data structure $\mathcal{T}$. Hence, to prove the privacy guarantee, it is sufficient to show that for any data set $V=\{\boldsymbol{v}_{1},\ldots,\boldsymbol{v}_{n}\}$ (with each $\left\|\boldsymbol{v}_{i}\right\|_{2}\leq L$), the operations on the tree data structure (i.e., the InitializeTree , AddToTree , GetSum ) provide the privacy guarantees in the Theorem statement. First, notice that each $\boldsymbol{v}_{i}$ affects at most $\lceil\lg(n+1)\rceil$ nodes in the tree $\mathcal{T}$. Additionally, notice that the computation in each node of the tree $\mathcal{T}$ is essentially a summation query. With these two observations, one can use standard properties of Gaussian mechanism ,[53, Corollary 3], and adaptive RDP composition [53, Proposition1] to complete the proof.

While the original work on tree aggregation did not use either Gaussian mechanism or RDP composition, it is not hard to observe that the translation to the current setting is immediate. ∎

B.3 Missing details from Section 4.2 (Comparing Noise in DP-SGD (with amplification) and DP-FTRL)

If we instantiate $\boldsymbol{a}_{t}=\boldsymbol{b}_{t}-\boldsymbol{b}_{t-1}$, and $\eta=\frac{1}{\lambda}$, then for all $t\in[n]$, $\theta^{\textsf{Noisy-SGD}}_{t}=\theta^{\textsf{DP-FTRL}}_{t}$.

The update rule of DP-FTRL can be written as

where $\boldsymbol{b}_{t}$ is the noise that gets added by the tree-aggregation mechanism at time step $t+1$. If we 1) set $\lambda=\frac{1}{\eta}$, 2) draw data samples sequentially from $D$ in Noisy-SGD, and 3) set $\boldsymbol{a}_{t}=\boldsymbol{b}_{t}-\boldsymbol{b}_{t-1}$ so that $\sum\limits_{i=1}^{t}\boldsymbol{a}_{t}=\boldsymbol{b}_{t}$, we can establish the equivalence between (5) and (6). This completes the proof. ∎

Appendix C Missing Details from Section 5

We first present a more detailed version of Theorem 5.1 and then present its proof.

Setting $\lambda$ optimally and plugging in the noise scale $\sigma$ from Theorem 4.1 to ensure $(\varepsilon,\delta)$-differential privacy, we have

Recall that by Algorithm $\mathcal{A}_{\sf FTRL}$, $\theta_{t+1}\leftarrow\operatorname*{arg\,min}\limits_{\theta\in\mathcal{C}}\underbrace{\sum\limits_{i=1}^{t}\langle\nabla_{i},\theta\rangle+\frac{\lambda}{2}\left\|\theta\right\|_{2}^{2}+\langle\boldsymbol{b}_{t},\theta\rangle}_{J_{t}^{\sf priv}(\theta)}$, where the Gaussian noise $\boldsymbol{b}_{t}=\boldsymbol{s}_{t}-\sum\limits_{i=1}^{t}\nabla_{i}$ for $\boldsymbol{s}_{t}$ being the output of ${\texttt{GetSum}}\,(\mathcal{T},t)$. By standard concentration of spherical Gaussians, w.p. at least $1-\beta$, $\forall t\in[n]$, $\left\|\boldsymbol{b}_{t}\right\|_{2}\leq L\sigma\sqrt{p\lceil\lg(n)\rceil\ln(n/\beta)}$. We will use this bound to control the error introduced due to privacy. Now, consider the optimizer of the non-private objective:

One can bound the term $A$ in (8) by [32, Theorem 5.2] and get $A\leq\left(\frac{L^{2}}{\lambda}+\frac{\lambda}{2n}\left(\left\|\theta^{*}\right\|_{2}^{2}-\left\|\theta_{1}\right\|_{2}^{2}\right)\right)$. As for term $B$, using (7) and the concentration on $\boldsymbol{b}_{t}$ mentioned earlier, we have, w.p. at least $1-\beta$,

Combining (8) and (9), we immediately have the first part of of Theorem 5.1. To prove the second part of the theorem, we just optimize for the regularization parameter $\lambda$ and plug in the noise scale $\sigma$ from Theorem 4.1. ∎

C.2 Additional Details for Section 5.2

In Algorithm 2, we present a version of DP-FTRL for least square loss. In this modified algorithm, the functions InitializeTreeBias , AddToTreeBias , and GetSumBias are identical to InitializeTree , AddToTree , and GetSum respectively in Algorithm 1. The functions AddToTreeCov , AddToTreeCov , and GetSumCov are similar to InitializeTree , AddToTree , and GetSum , except that the $p$-dimensional vector versions are replaced by $p\times p$-dimensional matrix version, and the noise in InitializeTreeCov is initialized by symmetric $p\times p$ Gaussian matrices with each entry drawn i.i.d. from $\mathcal{N}\left(0,L^{4}\sigma^{2}\right)$.

We first present the privacy guarantee of Algorithm 2 in Theorem C.3. Its proof is almost identical to that of Theorem 4.1, except that we need to measure the sensitivity of the covariance matrix in the Frobenius norm.

If $\left\|\mathbf{x}\right\|_{2}\leq L$ and $|y|\leq 1$ for all $(\mathbf{x},y)\in\mathcal{D}$ and $\theta\in\mathcal{C}$, then Algorithm 1 (Algorithm $\mathcal{A}_{\sf FTRL}$) satisfies $\left(\alpha,\frac{\alpha\lceil\lg(n)\rceil}{\sigma^{2}}\right)$-RDP. Correspondingly, by setting $\sigma=\frac{2\sqrt{\lceil\lg(n)\rceil\ln(1/\delta)}}{\varepsilon}$ one can satisfy $(\varepsilon,\delta)$-differential privacy guarantee, as long as $\varepsilon\leq 2\ln(1/\delta)$.

In Theorem C.4, we present the regret guarantee for Algorithm 2.

Let $D=\{(\mathbf{x}_{1},y_{1}),\ldots,(\mathbf{x}_{n},y_{n})\}\in\mathcal{D}^{n}$ be a data set drawn i.i.d. from $\tau$, with $L=\max\limits_{\mathbf{x}\in\mathcal{D}}\left\|\mathbf{x}\right\|_{2}$ and $\max\limits_{y\sim\mathcal{D}}|y|\leq 1$. Let $\mathcal{C}$ be the model space and $\mu=\max\limits_{\theta\in\mathcal{C}}\left\|\theta\right\|_{2}$. Let $\theta^{*}$ be any model in $\mathcal{C}$, and $[\theta_{1},\ldots,\theta_{n}]$ be the outputs of Algorithm $\mathcal{A}_{\textsf{FTRL-LS}}$ (Algorithm 2). Then w.p. at least $1-\beta$ (over the randomness of the algorithm), we have

Setting $\lambda$ optimally and plugging in the noise scale $\sigma$ from Theorem C.3 to ensure $(\varepsilon,\delta)$-differential privacy, we have,

$\theta_{t+1}\leftarrow\operatorname*{arg\,min}\limits_{\theta\in\mathcal{C}}\underbrace{\sum\limits_{i=1}^{t}\left(\theta^{\top}\mathbf{x}_{i}\mathbf{x}_{i}^{\top}\theta-2y_{i}\langle\mathbf{x}_{i},\theta\rangle\right)+\frac{\lambda}{2}\left\|\theta\right\|_{2}^{2}+\langle\boldsymbol{b}_{t},\theta\rangle+\theta^{\top}B_{t}\theta}_{J_{t}^{\sf priv}(\theta)}$, where the noise $\boldsymbol{b}_{t}=\sum\limits_{i=1}^{t}y_{i}\mathbf{x}_{i}-\boldsymbol{s}_{t}$ with $\boldsymbol{s}_{t}$ being the output of ${\texttt{GetSumBias}}\,(\mathcal{T}_{\sf bias},t)$, and the noise $B_{t}=W_{t}-\sum\limits_{i=1}^{t}\mathbf{x}_{i}\mathbf{x}_{i}^{\top}$ with $W_{t}$ being the output of ${\texttt{GetSumCov}}\,(\mathcal{T}_{\sf cov},t)$. By standard bound on Gaussian random variables, w.p. at least $1-\beta$, $\forall t\in[n]$, $\left\|\boldsymbol{b}_{t}\right\|_{2}=O\left(L\sigma\sqrt{p\ln(n)\ln(n/\beta)}\right)$ and $\left\|B_{t}\right\|_{2}=O\left(L^{2}\sigma\sqrt{p\ln(n)\ln(n/\beta)}\right)$. We will use this bound to control the error introduced due to privacy.

$\widetilde{\theta}_{t+1}\leftarrow\operatorname*{arg\,min}\limits_{\theta\in\mathcal{C}}\underbrace{\sum\limits_{i=1}^{t}\left(\theta^{\top}\mathbf{x}_{i}\mathbf{x}_{i}^{\top}\theta-2y_{i}\langle\mathbf{x}_{i},\theta\rangle\right)+\frac{\lambda}{2}\left\|\theta\right\|_{2}^{2}}_{J_{t}^{\sf np}(\theta)}$.

By an analogous argument to (7) in the proof of Theorem 5.1, we have

Using Theorem 2 from and (13), we have that w.p. at least $1-\beta$ over the randomness of the algorithm,

We get the regret guarantee in Theorem C.4 by optimizing for $\lambda$. ∎

C.3 Formal Statement of Online-to-batch Conversion for Excess Population Risk

Recall the setting of parameters from Theorem 5.1, and let $\theta^{\texttt{priv}}\,=\frac{1}{n}\sum\limits_{t=1}^{n}\theta_{t}$ (where $[\theta_{1},\ldots,\theta_{n}]$ are outputs of Algorithm $\mathcal{A}_{\sf FTRL}$ (Algorithm 1). If the data set $D$ is drawn i.i.d. from the distribution $\tau$, then we have that w.p. at least $1-\beta$ (over the randomness of the algorithm $\mathcal{A}_{\sf FTRL}$),

Here, $\mu=\max\limits_{\theta\in\mathcal{C}}\left\|\theta\right\|_{2}$ is an upper bound on the norm of any model in $\mathcal{C}$.

Appendix D Multi-pass DP-FTRL: Handling multiple participations

In this section, we provide details of the DP-FTRL-TreeRestart, DP-FTRL-NoTreeRestart, and DP-FTRL-SometimesRestart algorithms introduced in Section 6 for handling data where each example (or user in the case of user-level DP) can be considered in multiple training steps. The privacy accounting code is open sourced https://github.com/tensorflow/privacy/blob/master/tensorflow_privacy/privacy/analysis/tree_aggregation_accountant.py for DP-FTRL-TreeRestart and DP-FTRL-NoTreeRestart dynamic programming. https://github.com/google-research/DP-FTRL/privacy.py for DP-FTRL-NoTreeRestart with given data order and tree completion trick. .

In this approach, we restart tree aggregation at every epoch of training, so each $d_{i}$ contributes at most once to each tree. Since this amounts to adaptive composition of Algorithm 2 for $E$ times, the privacy guarantee for this method can be obtained from Theorem 4.1 and the adaptive sequential composition property of RDP .

When the tree-restart strategy is used, we can use a tree-completion trick to improve performance. The general idea is to add “virtual steps” to complete the binary tree, such that the noise added to the step before restarting is smaller. The details can be found at Appendix D.3.1.

D.2 DP-FTRL without Tree Restarts (DP-FTRL-NoTreeRestart)

In this case, we build a single binary tree over all the iterations of training. In this section we provide the privacy accounting for this DP-FTRL-NoTreeRestart approach, which perhaps surprisingly becomes much more involved compared to the tree restart version. We make the following three assumptions: i) A singe training example contributes only once to a single gradient computation, ii) an example can contribute at most $E$ number of times during the training process, and iii) any two successive appearance of a single training example is ensured to have a minimum separation of $\xi$ iterations of $\mathcal{A}_{\sf FTRL}$ (Algorithm 1). For the clarity of notation, here we will denote the number of iterations of Algorithm $\mathcal{A}_{\sf FTRL}$ with $T$ (instead of $n$), and each $\nabla_{t}$ for $t\in[T]$ corresponds to gradient computation at time step $t$. Additionally, we will refer to be binary tree used in Algorithm 1 (Algorithm $\mathcal{A}_{\sf FTRL}$), with the leaf nodes being the $\nabla_{t}$’s, as $\mathcal{T}$.

In Algorithm 3, we provide a privacy accounting scheme for the above instantiation of Algorithm $\mathcal{A}_{\sf FTRL}$. Later, we provide a tighter privacy accounting via a dynamic programming approach, albeit at a higher computation cost. In all the privacy analysis in this section, we essentially use the standard machinery of Gaussian mechanism with RDP [53, Proposition 7], except we use a specific sensitivity analysis for the tree-aggregation algorithm used in DP-FTRL.

For the DP-FTRL-NoTreeRestart instantiation of Algorithm 1 (Algorithm $\mathcal{A}_{\sf FTRL}$), the privacy accounting scheme in Algorithm 3 ensures $\left(\alpha,\frac{\alpha}{2\sigma^{2}}\cdot\rho\right)$-Renyi differential privacy (RDP), where $\sigma$ is the noise scale in the tree aggregation scheme of Section B.1.

By definition of $E$, $\sum\limits_{i=1}^{k}c(z_{i})\leq E$.

For any node $z\in\mathcal{T}$, the number of leaves in the subtree rooted at $z$ is at most $2^{\sf height(z)}$. Since, each example is allowed to participate every $(\xi+1)$ steps, the number of contributions $c_{i}$ to any $z_{i}\in\gamma$ is upper bounded by $\mu_{\gamma}=\left\lceil\frac{2^{\sf height(\gamma)}}{\xi+1}\right\rceil$.

Applying these two constraints, the following quadratic program can be used to bound $\|c\|^{2}_{2}$:

By KKT conditions, the above is maximized as follows: Letting $k^{*}=\min\left\{k,\left\lfloor\frac{E}{\mu_{\gamma}}\right\rfloor\right\}$, set $c_{1}=\mu_{\gamma}$, $c_{2}=\mu_{\gamma},\ldots,c_{k^{*}}=\mu_{\gamma}$, set $c_{k^{*}+1}=E-k^{*}\mu_{\gamma}$, and set $c_{i}=$ for all $i>(k^{*}+1)$.

is the RDP cost of the complete level $\gamma$.

To complete the proof, it suffices to apply adaptive RDP composition across all the levels of the tree $\mathcal{T}$. ∎

Dynamic programming based improvement to Algorithm 3: Consider the same binary tree $\mathcal{T}$ described above. For any data set $D$, for any fixed individual $x$, and a node $z\in\mathcal{T}$, let $c(z)$ be the total number of participation of $x$ in the sub-tree rooted at $z$. Extending the level-wise argument of the proof of D.2 to the whole tree (as a single application of the Gaussian mechanism), it is not hard to see that DP-FTRL satisfies $\left(\alpha,\frac{\alpha}{2\sigma^{2}}\cdot\sum_{z\in\mathcal{T}}c(z)^{2}\right)$-RDP guarantee. We can upper-bound this by computing $\zeta=\max_{c}\sum\limits_{z\in\mathcal{T}}c(z)^{2}$ subject to $c$ being a realizable assignment under the participation constraints mentioned above. We provide the following program to compute an upper bound on $\zeta$.

Let $\zeta^{*}=\max\limits_{w\in\{0,\ldots,E\}}\zeta(w,0,\xi,T)$ in (17). Above privacy accounting for the DP-FTRL-NoTreeRestart instantiation of Algorithm 1 (Algorithm $\mathcal{A}_{\sf FTRL}$) ensures $\left(\alpha,\frac{\alpha\zeta^{*}}{2\sigma^{2}}\right)$-Rényi differential privacy.

We argue that $\zeta$ in (17) enumerates all the valid configurations of valid cost functions $c$ described above.

First, suppose size is a power of two. Then there is a complete binary tree with size leaves which we think of as being numbered sequentially. We must place contrib contributions at leaves of this tree, with the constraint that there are at least $\xi$ empty leaves following each leaf with a contribution (and, of course, each leaf can only have one contribution). However, the empty leaves after the last contribution can “overflow” by end, i.e., we can imagine end extra empty spaces are added at the end of the tree to satisfy this constraint. In addition the first start leaves must be empty. In other words, start spaces are subtracted from the beginning and end spaces are added to the end of the tree. The value of the tree is the sum over all nodes (leaves and internal) of the square of the number of contributions in the subtree rooted at that node. So a leaf has value $1$ or depending on whether or not it has a contribution and an internal node has value $c^{2}$, where $c$ is the number of contributions at leaves under this node. The function $\zeta\left(\texttt{contrib},\texttt{start},\texttt{end},\texttt{size}\right)$ computes the maximum total value of the tree over an arbitrary placement of contributions satisfying the constraints. Second, if size is not a power of two, then instead of a single complete binary tree, we have multiple complete binary trees of different sizes, which are arranged from largest to smallest. (17) exactly encodes this logic.

The base cases are immediate given the above description of the recursive statement. This completes the proof. ∎

The previous analysis assumes only a gap between two successive participation of any user and does not constrain the data order in any other way. In some special cases, especially the centralized setting, the server takes full control of the training process and can decide which samples to use in each training step. We can thus take advantage of such knowledge for a simpler (in terms of the privacy accounting algorithm but not necessarily the computation time) privacy computation.

Suppose we use stochastic gradient with mini-batch of size $1$. Then for each node in the tree, we can obtain a list of samples that affect the node, which can be used to compute the sensitivity of the node with respect to each sample. Summing up the (squared) sensitivity of every node, we can then take maximum among all samples and get the final (squared) sensitivity. The algorithm for the computing the squared sensitivity is described in Algorithm 4.

Consider a simple example where we have four samples indexed with $1,\dots,4$, and use them in the order of $$during training. Representing each node in the tree with a list of samples it contains, we will have five leaf nodes$[(1),(2),(3),(1),(4)]$, two nodes$[(1,2),(3,1)]$in the middle layer, and$(1,2,3,1)$as the root node. The root node, for example, have sensitivity$2$with respect to sample$1$,$1$with respect to$2$and$3$, and with respect to$4$. Summing up over all nodes, the whole tree has sensitivity$\sqrt{8}$with respect to sample$1$,$\sqrt{3}$with respect to$2$and$3$, and$1$with respect to$4$. We take the maximum and conclude that the tree has sensitivity$\sqrt{8}$.

When mini-batch has size larger than $1$, if the batches are formed by the same set of samples across epochs such that one sample affects the same batch, we can simply consider sensitivity with respect to a batch, i.e., $i$ could be used to represent the $i$-th batch instead of the $i$-th sample. If samples might not be grouped in the same way across epochs, then each leaf node would consist of multiple samples that constitute the corresponding batch, and the same computation follows.

Now we consider the time complexity. We need to construct a tree with nodes being lists of samples / batches. Suppose we build the tree layer by layer from leaf to root. Merging two consecutive nodes to form their parent takes $O(m_{i}+m_{j})$ complexity where $m_{i}$ and $m_{j}$ are their sizes. Therefore, forming a layer based on the previous layer takes $O(m)$, where $m$ is the total number of samples / batches across epochs, depending on whether the batches are always formed in the same way through training. The construction of the whole tree thus takes $O(m\log(m))$ time. The sensitivity computation takes $O(m_{i})$ for a node of size $m_{i}$, and thus enumerating through the tree takes $O(m\log(m))$ as well. Therefore, the total time complexity is $O(m\log(m))$. The running time is higher than that of Algorithm 3, but potentially smaller than the dynamic programming version of it.

In our centralized learning experiments, we shuffle the dataset right after each restarting, then keep the same batches and go through them in the same order across epochs. We use the above privacy computation.

D.3 Combining DP-FTRL-TreeRestart and DP-FTRL-NoTreeRestart

In Section 7, we consider the case where the tree is restarted after every epoch. Each user thus participate only in one leaf of the tree in the privacy analysis. However, restarting may cause instability and hurt model utility. On the other hand, if we keep using the same tree through the training process with the privacy analysis in Appendix D.2, each user can affect multiple leaf nodes. The sensitivity is thus high and larger noise is needed under a fixed privacy budget. Given the trade-off, a natural schedule to consider is to restart the tree every few epochs. For example, if we would like to train for $100$ epochs on CIFAR-10 ($n=50000$) with batch size $500$ and achieve $\varepsilon\approx 23.0$, we can either restart every epoch with noise multiplier $\approx 7$, restart every $5$ epochs with noise $\approx 8.5$, restart every $20$ epochs with noise $\approx 12$, or use a single tree (no-restart) with noise $32$. The privacy computation follows from Appendix D.2.1.

Looking at the binary tree of noisy gradients, we can easily see that the amount of noise added to each prefix sum depends on its location in the tree. Specifically, if we consider the original tree-aggregation protocol, to release the prefix sum up to leaf node $i$, the noise will scale with the number of bits that are set in the binary representation of $i$. A natural trick to consider is thus to complete the tree with “virtual steps” such that the noise is the smallest. Consider one of the settings in Figure 1 – running CIFAR-10 ($n=50000$) with batch size $2000$. After one epoch, the tree consists of $25$ nodes. Instead of restarting immediately, we can instead run an additional $7$ “virtual steps” so that the tree is complete with $32$ nodes. The virtual steps can be thought of as adding virtual samples of s, i.e., instead of privately releasing the sum of the past $25$ gradients, we privately release the sum of the $25$ gradients and $7$ s. This way, the additive noise in the last step can improve by a factor of $3$ in the original tree-aggregation protocol, and by roughly a factor of $4$ ($\approx 2.05$ vs. $\approx 0.51$) with the trick from . This can be crucial as the future models will be based on the last noise before restarting.

The virtual steps do not come for free as we have added more nodes in the tree, yet the cost of privacy is less than that of actual gradients, because the virtual samples are fixed to and do not increase the sensitivity. For example, if we use the privacy computation in Algorithm 4 where the complete ordering of samples / batches is known and aim to add $A$ virtual steps, we can append $A$ virtual leaf nodes in the end of the leaf layer with, for example, a special symbol $\star$ to indicate it is a virtual sample. The tree construction steps is exactly the same as before. The only difference is in the sensitivity computation, where we simply ignore the virtual sample $\star$. Taking the example in Appendix D.2.1 where the training uses samples $$, we might add$3$virtual steps to form a tree of$8$leaf nodes$[(1),(2),(3),(1),(4),(\star),(\star),(\star)]$,$4$nodes$[(1,2),(3,1),(4,\star),(\star,\star)]$in the 2nd layer,$[(1,2,3,1),(4,\star,\star,\star)]$in the 3rd layer and$(1,2,3,1,4,\star,\star,\star)$as the root node. This way, sample$1$would have sensitivity$\sqrt{12}$, sample$2$,$3$and$4$would have sensitivity$2$.

There is a trade-off between the scale of the last noise before restarting and the additional privacy cost. For example, we can expect that if the size of the tree is far away from the next power of two, then the additional privacy cost might overwhelm the gain in the noise scale; if the tree is almost complete, then we might expect the trick to help.

Appendix E Omitted Details for Experiment Setup (Section 7.1)

Table 2(a) shows the model architecture for MNIST and EMNIST, Table 2(b) shows that for CIFAR-10, and Table 2(c) shows the neural networks adopted from .

E.2 Comparison of Optimizers with their Momentum Variants

Centralized Learning: Figures 3 and 4 show a comparison between the original and the momentum versions of DP-SGD (denoted by “DP-SGD” and “DP-SGDM”) and DP-FTRL (denoted as “DP-FTRL” and “DP-FTRLM”), respectively. For both DP-SGD and DP-FTRL, we consider both small and large number of epochs (presented in the top and bottom row respectively) on the three centralized example-level DP image classification tasks. The small-epoch setting follows from that in Section 7. The large-epoch setting follows from that in Appendix F.2. The number of epochs is $20$, $100$ and $50$ for MNIST, CIFAR-10 and EMNIST under the smaller batch size and is 4 times that for larger the batch size. For DP-FTRL(M), we use the tree-completion trick D.3.1. On CIFAR-10, we restart every $5$ epochs, and on EMNIST, we restart every epoch – following the setting that achieves the highest accuracy in Figure 9 in Appendix F.2.

In Figure 3, for CIFAR-10, DP-SGDM outperforms DP-SGD for smaller number of epochs, and DP-SGD is better for larger number of epochs. For the other settings, the two variants are similar. In Figure 4, we can see that the accuracy of DP-FTRLM is always at least that of DP-FTRL (sometimes even more).

Therefore, we use DP-SGDM in Section 7 (small-epoch setting) and DP-SGD in Appendix F.2 (large-epoch setting). We use DP-FTRLM in both settings.

Federated Learning: The experiments in Table 3 and Figure 5 show the advantages of the momentum variant for the federated StackOverflow task in practice. We compare DP-SGD and its momentum variant DP-SGDM, DP-FTRL and its momentum variant DP-FTRLM under two different privacy epsilons. Privacy epsilon is infinite when noise multiplier is zero; privacy epsilon is 8.53 when noise multiplier is 0.4 for DP-SGD and DP-SGDM; privacy epsilon is 8.5 when noise multiplier is 2.33 for DP-FTRL and DP-FTRLM. We tune and select the hyperparameter with the best validation accuracy The accuracy for StackOverflow next word prediction task excludes the end of sequence symbol and the out of vocabulary symbol following . The hyperparameters tuning range are described in Section F.1.. We then run the experiment with the specific set of hyperparameters for five times to estimate mean and standard deviation of the accuracy.

The momentum variant helps in two ways for StackOverflow: momentum significantly improve the performance of both SGD and FTRL when the noise is relatively small; moreover, momentum stabilizes DP-FTRL when the noise is relatively large. Note that the tree aggregation method in DP-FTRL use different privacy calculation method compared to DP-SGD. A relatively large noise multiplier has to be used to achieve the same privacy $\varepsilon$ guarantee. While tree aggregation in DP-FTRL exploits the $O(\log n)$ accumulated noise, it also introduces unstable jump for the noise added in each round, which could be mitigated by the momentum $\gamma$ introduced in DP-FTRLM. In the experiments of StackOverflow, we will always use the momentum variant unless otherwise specified.

E.3 Efficient Tree Aggregation

Centralized learning: Figure 6 shows a comparison between the efficient (“FTRLM”) and the original version (“FTRLM-vanilla”) of FTRLM for the three centralized example-level DP image classification tasks. We can see clearly that the efficient version always outperforms the vanilla version. The settings follows from that in Appendix E.2.

Federated learning: Figure 7 shows the advantage of the efficient tree aggregation algorithm in the StackOverflow simulation for the federated learning setting. In Figure 7(b), to meet the targeted StackOverflow test accuracies (23%, 24.5%), the noise multipliers for DP-FTRLM can increase from (0.268, 0.067) to (0.387, 0.149) after implementing the efficient tree aggregation . The noise multipliers are used to generate Figure 7(c).

E.4 Effect of Tree Completion Trick

In the centralized learning experiments in Section 7.2, we also make use of the tree completion trick described in Appendix D.3.1. Figure 8 plot the comparison between the DP-FTRL result presented in Figure 1 and those without the tree completion trick. We can see that the trick always helps in these settings.

Appendix F Omitted Details for Experiments in Section 7.2

For the three image classification experiments, we tune the learning rate ($1/\lambda$ for FTRL) over a grid of the form $\cup_{i\in\{-3,-2,\dots,3\}}\{10^{i},2\times 10^{i},5\times 10^{i}\}$, selecting the value that achieves the highest test accuracy averaged over the last 5 epochs while ensuring this chosen value is not an endpoint of the grid. We use a clipping norm $1.0$ for all the image classification experiments following previous work .

The parameter search for non-private baseline is the same as that for the DP algorithms. We use regular SGD (with and without momentum) for the image classification tasks.

The StackOverflow benchmark dataset of the next word prediction task has 342,477 users (clients) with training 135,818,730 examples. A validation set of 10,000 examples, and a test set of 16,576,035 examples are constructed following . The one layer LSTM described in is used. We compare with DP-FedAvg where DP-SGD is used on server.

There are many hyperparameters in federated learning. We fix the number of total rounds to be 1,600 for StackOverflow, and sample 100 clients per round for DP-SGD, and take 100 clients from the shuffled clients for DP-FTRL to make sure the clients are disjoint across rounds. Note that DP-FTRL would run less than one epoch for StackOverflow. On each client, the number of local epochs is fixed to be one and the batch size is sixteen, and we constrained the maximum number of samples on each client to be 256. The momentum for both DP-SGDM and DP-FTRLM is fixed to 0.9.

In most of the experiments, we will tune server learning rate, client learning rate and clip norm for a certain noise multiplier. We tune a relative large grid (client learning rate in $\{0.1,0.2,0.5,1,2\}$, server learning rate in $\{0.03,0.1,0.3,1,3\}$, clip norm in $\{0.1,0.3,1,3,10\}$) when the noise multiplier is zero. And we have several observation: the best accuracy of clip norm 0.3 and 1.0 are slightly better than larger clip norms, which suggests that clip norm could generally help for this language task; increasing server learning rate could complement decreasing clip norm when clip norm is effective; the largest client learning rate that does not diverge often leads to good final accuracy. As adding noise increases the variance of gradients, we often have to decrease learning rate in practice. Based on this heuristic and the observation from tuning when noise multiplier is zero, we choose client learning rate from $\{0.1,0.2,0.5\}$, server learning rate from $\{0.1,0.3,1,3\}$ and clip norm from $\{0.3,1,3\}$ unless otherwise specified. We use DP-SGD with zero noise for StackOverflow, as gradient clipping can improves accuracy for language tasks.

F.2 Centralized Training with Large Number of Epochs by Interleaving Restarting and Non-restarting

Appendix D.3 describes the idea of interleaving between restarting and non-restarting. Here, we examine how such schedules might affect the model utility. Additionally, we consider the effect of the tree completion trick (Section D.3.1). We consider CIFAR-10 and EMNIST, which are hard datasets that might require a large number of epochs to learn. For CIFAR-10, we fix the batch size to be $500$, number of epochs to be $100$ (thus $10000$ steps in total); for EMNIST, we fix the batch size to be $500$ and number of epochs to be $50$ (thus $69750$ steps in total). On each dataset, similar as in Section 7, we compare DP-SGD with or without amplification, and DP-FTRL(M) with different restarting schedules.

In Figure 9(a), we plot the results for DP-FTRL(M) with non-restarting and restarting every $1$, $5$, $20$ epochs (solid lines), and comparing them with DP-SGD with and without amplification. Additionally, we use the tree completion trick for restarting every $5$ and $20$ epochs (dashed lines). We can see the following.

Neither non-restarting nor restarting every epoch yields accuracy that are comparable to DP-SGD. On the other hand, without the tree completion trick, restarting every $20$ epochs gives much better accuracy, which means that interleaving between restart and non-restart is crucial.

The tree completion trick helps for restarting every $5$ epochs and hurts for restarting every $20$ epochs, demonstrating the trade-off we mentioned before.

Overall, without the tree completion trick, restarting every $5$ epochs with the tree completion trick gives the best accuracy, and we can see a “cross-over” between it and DP-SGD similar as that in Figure 1, yet at a larger $\varepsilon\approx 18$. With the completion trick, restarting every $20$ epochs gives the best accuracy. A “cross-over” happens at $\varepsilon\approx 14$.

Similar as in Figure 1, we can see that DP-FTRL is always better than DP-SGD without amplification.

In Figure 9(b), we plot the results on EMNIST for restarting every $1$, $5$, $25$ epochs and non-restarting. We can observe similar trend as in the CIFAR-10 experiments. Namely, the tree completion tricks helps in some cases, and the best accuracy is achieved by restarting every $5$ epochs with the tree completion trick, which outperforms DP-SGD with amplification starting from $\varepsilon\approx 5$.

F.3 Omitted Details for StackOverflow Experiments

We compare the accuracy of the momentum variant of DP-FTRL with the momentum variant of DP-SGD as baseline under different privacy epsilon. We tune hyperparameters as described in Section F.1 and select the hyperparameters achieve the best validation accuracy for StackOverflow (see Table 4 and Figure 10). DP-FTRLM performs better than DP-SGDM when the epsilon is relatively large, but performs worse when the epsilon is small ($\varepsilon<2.60$ in Table 4). More noise are added to DP-FTRLM to achieve the same privacy epsilon as DP-SGDM. However, DP-FTRLM can result in utility (accuracy) not (much) worse than DP-SGDM without relying on amplification by sampling, which makes it appealing for practical federated learning setting where population and sampling is difficult to estimate . Note that the noise added for both DP-FTRLM and DP-SGDM are considered large for federated learning tasks. The effective noise could be significantly reduced by sampling more clients each round in practice , and more discussion on this front is in Appendix G.

Appendix G Omitted Details for Experiments in Section 7.3

In Section F.3, a significant amount of noise has to be added in both DP-FTRLM and DP-SGDM to achieve nontrivial privacy epsilons, which leads to undesired accuracy degradation. For example, the test accuracy of DP-FTRLM on StackOverflow dataset decreases from $25.15\%$ when $\varepsilon=\infty$ to $20.22\%$ when $\varepsilon=8.5$ when the number of clients per round is fixed at 100. In practical federated learning tasks, the total population is very large and many more clients could be sampled every round. In this section, taking StackOverflow as an example, we study the minimum number of sampled clients per round (report goal in ) to achieve a target accuracy under certain privacy budget.

We first find the largest noise multiplier that would meet the target accuracy based on selecting 100 clients per round. As an extensive grid search over noise multiplier while simultaneously tuning server learning rate, client learning rate and clip norm is computationally intensive, we fix the clip norm to 1 and the client learning rate to 0.5 based on Figure 11. We then tune the server learning rate from $\{0.3,1,3\}$ for each noise multiplier.

We use a grid of ten noise multipliers between ($\varepsilon=\infty$, test accuracy=$24.89$) and $0.3$ ($\varepsilon=18.89$, test accuracy=$18.89$) for DP-SGDM, and between ($\varepsilon=\infty$, test accuracy=$25.15$) and $1.13$ ($\varepsilon=19.74$, test accuracy=$21.33$) for DP-FTRLM. And we further add five noise multipliers between and $0.035$ for DP-SGDM, and between and $0.149$ for DP-FTRLM based on the results of the previous grid search on ten noise multipliers. The test accuracy is presented in Figure 2(b). We set the target test accuracy as $24.5\%$ and select noise multiplier $0.007$ (with server learning rate $3$) for DP-SGDM and noise multiplier $0.149$ (with server learning rate $3$) for DP-FTRLM.

The standard deviation of noise added in each round is proportional to the inverse of the number of clients per round (report goal). The practical federated learning tasks often have a very large population and report goal, and we could simultaneously increase the noise multiplier and report goal, so that the utility (accuracy for classification and prediction tasks) will likely not degrade while the privacy guarantee is improved. The validation accuracy of simulation performance with two different report goals for StackOverflow is presented in Figure 12. The noise multiplier 0.149 is used for DP-FTRLM and 0.007 is used for DP-SGD when report goal is 100, which is the largest noise multiplier to meet the target test accuracy determined by Figure 2(b). We run each experiment for five times and plot the curves for the median validation accuracy, the corresponding test accuracy are $24.73\%$ for DP-SGDM and $24.51\%$ for DP-FTRLM. We then run the same experiments with report goal of 1000, and proportionally increase the corresponding noise multiplier to be 1.49 for DP-FTRLM and 0.07 for DP-SGDM. The performance of 1000 report goal is slightly better with test accuracy $25.19\%$ for DP-SGDM and $24.67\%$ for DP-FTRLM. We will assume the utility will not decrease if report goal and noise multiplier are simultaneously and proportionally increased.

As shown in Table 5, both report goals 100 and 1000 would provide trivial privacy guarantee of large epsilon for the target utility. We have to increase the report goal to $2.06e4$ to get a nontrivial privacy epsilon (less than 10) with DP-FTRLM and the StackOverflow population of $3.42e5$ The best epsilon DP-SGDM can achieve is $10.16$ by increasing report goal to be as large as the population $3.42e5$. Smaller report goal could achieve similar privacy guarantee if the population becomes larger. In Figure 2(c), the relationship between privacy guarantee and report goal for DP-FTRLM and DP-SGDM are presented. DP-FTRLM provides better privacy guarantee by smaller report goal when the privacy epsilon is relatively large or very small. The range where DP-FTRLM outperforms DP-SGDM in report goals and privacy guarantees are larger when the population is relatively small or very large.