# Practical and Private (Deep) Learning Without Sampling or Shuffling

Peter Kairouz Google. {kairouz, mcmahan, shuangsong, omthkkr, athakurta,
<EMAIL_ADDRESS>Brendan McMahan11footnotemark: 1 Shuang
Song11footnotemark: 1 Om Thakkar11footnotemark: 1 Abhradeep
Thakurta11footnotemark: 1 Zheng Xu11footnotemark: 1

###### Abstract

We consider training models with differential privacy (DP) using mini-batch
gradients. The existing state-of-the-art, Differentially Private Stochastic
Gradient Descent (DP-SGD), requires _privacy amplification by sampling or
shuffling_ to obtain the best privacy/accuracy/computation trade-offs.
Unfortunately, the precise requirements on exact sampling and shuffling can be
hard to obtain in important practical scenarios, particularly federated
learning (FL). We design and analyze a DP variant of Follow-The-Regularized-
Leader (DP-FTRL) that compares favorably (both theoretically and empirically)
to amplified DP-SGD, while allowing for much more flexible data access
patterns. DP-FTRL does not use any form of privacy amplification.

##  1 Introduction

Differentially private stochastic gradient descent (DP-SGD) [67, 6, 1] has
become state-of-the-art in training private (deep) learning models [1, 52, 25,
57, 27, 70]. It operates by running stochastic gradient descent [61] on noisy
mini-batch gradients111Gradient 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_ [42, 6, 1, 72, 76, 23, 30] 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 [39,
5].

We propose a new online learning [32, 64] 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 [66, 36, 69, 54].

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 step222One can also create a mini-batch with
Poisson sampling [1, 51, 76], except the batch size is now a random variable.
For brevity, we focus on the fixed batch setting. $t$, then privacy
amplification by sampling [42, 6, 1, 72] allows one to scale down the noise to
$\sigma_{t}\cdot(k/n)$, while still ensuring $\varepsilon_{t}$-differential
privacy.333A similar argument holds for amplification by shuffling [23, 30],
when the data are uniformly shuffled at the beginning of every epoch.We do not
consider privacy amplification by iteration [28] 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 [1, 57, 70] 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) [47], 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 [75, 46, 16]. The main idea in DP-FTRL is to use the _tree
aggregation trick_ [22, 13] 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 [5, 59]
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
[5] 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.

###  1.1 Problem Formulation

Suppose we have a stream of data samples
$D=[d_{1},\ldots,d_{n}]\in\mathcal{D}^{n}$, where $\mathcal{D}$ is the domain
of data samples, and a loss function
$\ell:\mathcal{C}\times\mathcal{D}\to\mathbb{R}$, where
$\mathcal{C}\in\mathbb{R}^{p}$ is the space of all models. We consider the
following two problem settings.

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}$:

$R_{D}(\mathcal{A};\theta^{*})=\frac{1}{n}\sum\limits_{t=1}^{n}\ell(\theta_{t};d_{t})-\frac{1}{n}\sum\limits_{t=1}^{n}\ell(\theta^{*};d_{t}).$
(1)

We consider the algorithm $\mathcal{A}$ low-regret if
$R_{D}(\mathcal{A};\theta^{*})=o(1)$. To ensure a low-regret algorithm, we
will assume $\left\|\nabla\ell(\theta;d)\right\|_{2}\leq L$ for any data
sample $d$, and any models $\theta\in\mathcal{C}$. We consider both
_adversarial regret_ , where the data sample $d_{t}$ are drawn adversarially
based on the past output $\\{\theta_{1},\ldots,\theta_{t}\\}$ [32], and
_stochastic regret_ [33], where the data samples in $D$ are drawn i.i.d. from
some fixed distribution $\tau$.

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

${\sf
PopRisk}(\mathcal{A})\,=\mathbb{E}_{d\sim\tau}\ell(\widehat{\theta};d)-\min\limits_{\theta\in\mathcal{C}}\mathbb{E}_{d\sim\tau}\ell(\theta;d).$
(2)

All the algorithms in this paper guarantee differential privacy [21, 20] and
Rényi differential privacy [53] (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 [71], 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 [71],
Definition 1.1 can capture the regular replacement version of DP (originally
defined in [21], 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$.

######  Definition 1.1 (Differential privacy).

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

$\displaystyle\mathop{\mathbf{Pr}}[\mathcal{A}(D)\in S]$ $\displaystyle\leq
e^{\varepsilon}\cdot\mathop{\mathbf{Pr}}[\mathcal{A}(D^{\prime})\in
S]+\delta,\ \ \text{and}$
$\displaystyle\mathop{\mathbf{Pr}}[\mathcal{A}(D^{\prime})\in S]$
$\displaystyle\leq e^{\varepsilon}\cdot\mathop{\mathbf{Pr}}[\mathcal{A}(D)\in
S]+\delta,$

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.

###  1.2 Our Contributions

Table 1:  Best known regret guarantees for dataset size $n$ and model dimension $p$. Here, high probability means w.p. at least $1-\beta$ over the the randomness of the algorithm. The expected regret is an expectation over the random choice of the data set and the randomness of the algorithm.  Class | Adversarial Regret | Stochastic Regret
---|---|---
| Expected | High probability | Expected | High probability
Least-squares (and linear) |  $O\left(\left(\frac{1}{\sqrt{n}}+\frac{\sqrt{p}}{\varepsilon n}\right)\cdot\right.$ $\left.{\sf polylog}\left(\frac{1}{\delta},n\right)\right)$ [3] |  Same as general convex |  $O\left(\left(\frac{1}{\sqrt{n}}+\frac{\sqrt{p}}{\varepsilon n}\right)\cdot\right.$ $\left.{\sf polylog}\left(\frac{1}{\delta},n\right)\right)$ [3] |  $O\left(\left(\frac{1}{\sqrt{n}}+\frac{\sqrt{p}}{\varepsilon n}\right)\cdot\right.$ $\left.{\sf polylog}\left(\frac{1}{\delta},n,\frac{1}{\beta}\right)\right)$ [Theorem 5.3]
General convex | Constrained and unconstrained: $O\left(\left(\frac{1}{\sqrt{n}}+\frac{p^{1/4}}{\sqrt{\varepsilon n}}\right)\cdot{\sf polylog}\left(\frac{1}{\delta},n,\frac{1}{\beta}\right)\right)$ [Theorem 5.1]

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 [49, 46, 64, 32] for online
convex optimization (OCO). We also provide a variant called the momentum DP-
FTRL that has superior performance in practice. [3] provided a instantiation
of DP-FTRL specific to linear losses. [65] provided an algorithm similar to
DP-FTRL, where instead of just linearizing the loss, a quadratic approximation
to the regularized loss was used.

Regret guarantees: In the adversarial OCO setting (Section 5.1), compared to
prior work [38, 65, 3], DP-FTRL has the following major advantages. First, it
improves the best known regret guarantee in [65] by a factor of
$\sqrt{\varepsilon}$ (from
$\widetilde{O}\left(\sqrt{\frac{\sqrt{p}}{\varepsilon^{2}n}}\right)$ to
$\widetilde{O}\left(\sqrt{\frac{\sqrt{p}}{\varepsilon n}}\right)$, when
$\varepsilon\leq 1$). This improvement is significant because it
_distinguishes centrally private OCO from locally private_ [73, 26, 42]
OCO444Although not stated formally in the literature, a simple argument shows
that locally private SGD [18] can achieve the same regret as in [65].. Second,
unlike [65], DP-FTRL (and its analysis) extends to the unconstrained setting
$\mathcal{C}=\mathbb{R}^{p}$. Also, in the case of composite losses [17, 75,
46, 48], i.e., where the loss functions are of the form
$\ell(\theta;d_{t})+r_{t}(\theta)$ with $r:\mathcal{C}\to\mathbb{R}^{+}$
(e.g., $\|\cdot\|_{1}$) being a convex regularizer, DP-FTRL has a regret
guarantee for the losses $\ell(\theta;d_{t})$’s of form: (regret bound without
the $r_{t}$’s) $+\frac{1}{n}\sum\limits_{t=1}^{n}r_{t}(\theta^{*})$.

In the stochastic OCO setting (Section 5.2), we show that for least-square
losses (where
$\ell(\theta;d_{t})=(y_{t}-\langle\mathbf{x}_{t},\theta\rangle)^{2}$ with
$d_{t}=(\mathbf{x}_{t},y_{t})$) and linear losses (when
$\ell(\theta;d_{t})=\langle d_{t},\theta\rangle$), a variant of DP-FTRL
achieves regret of the form
$O\left(\left(\frac{1}{\sqrt{n}}+\frac{\sqrt{p}}{\varepsilon
n}\right)\cdot{\sf
polylog}\left(\frac{1}{\delta},n,\frac{1}{\beta}\right)\right)$ with
probability $1-\beta$ over the randomness of algorithm. Our guarantees are
strictly high-probability guarantees, i.e., the regret only depends on ${\sf
polylog}(1/\beta)$.

Population risk guarantees: In Section 5.3, using the standard online-to-batch
conversion [12, 63], 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 [7, 8, 29] 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.

To shed light on the empirical efficacy of DP-FTRL (in comparison) to DP-SGD,
in Section 4.2, we show that a variant of DP-SGD (with correlated noise) can
be viewed as an equivalent formulation of DP-FTRL in the unconstrained setting
( $\mathcal{C}=\mathbb{R}^{p}$). In the case of traditional DP-SGD [6], the
scale of the noise added per-step $t\in[n]$ is asymptotically same as that of
DP-FTRL once $t=\omega(n)$.

##  2 Errata and Fixes for the ICML 2021 version

In this section we provide an errata for the ICML-2021 proceedings version
[40] of this paper. For the no-tree-restart case of DP-FTRL, the privacy
accounting of Theorem D.2 in [40] 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.

##  3 Background

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

######  Definition 3.1 (Rényi differential privacy).

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:

$\displaystyle\frac{1}{\alpha-1}\log\mathop{\mathbf{E}}_{s\sim\mathcal{A}(D)}{\left(\frac{\mathop{\mathbf{Pr}}\left[\mathcal{A}(D)=s\right]}{\mathop{\mathbf{Pr}}\left[\mathcal{A}(D^{\prime})=s\right]}\right)^{\alpha}}$
$\displaystyle\leq\varepsilon,\ \ \text{and}$
$\displaystyle\frac{1}{\alpha-1}\log\mathop{\mathbf{E}}_{s\sim\mathcal{A}(D^{\prime})}{\left(\frac{\mathop{\mathbf{Pr}}\left[\mathcal{A}(D^{\prime})=s\right]}{\mathop{\mathbf{Pr}}\left[\mathcal{A}(D)=s\right]}\right)^{\alpha}}$
$\displaystyle\leq\varepsilon.$

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

To answer a query $f(D)$ with $\ell_{2}$ sensitivity $L$, i.e.,
$\max_{\text{neighboring }D,D^{\prime}}\|f(D)-f(D^{\prime})\|_{2}\leq L$, the
Gaussian mechanism [21] returns $f(D)+\mathcal{N}(0,L^{2}\sigma^{2})$, which
guarantees $\left(\sqrt{1.25\log(2/\delta)}/\sigma,\delta\right)$-differential
privacy [21, 19] and $(\alpha,\alpha/2\sigma^{2})$-RDP [53].

DP-SGD and Privacy Amplification: Differentially-private stochastic gradient
descent (DP-SGD) is a common algorithm to solve private optimization problems.
The basic idea is to enforce a bounded $\ell_{2}$ norm of individual gradient,
and add Gaussian noise to the gradients used in SGD updates. Specifically,
consider a dataset $D=\\{d_{1},\dots,d_{n}\\}$ and an objective function of
the form $\sum_{i=1}^{n}\ell(\theta;d_{i})$ for some loss function $\ell$. DP-
SGD uses an update rule

$\displaystyle\theta_{t+1}\leftarrow\theta_{t}-\frac{\eta}{|\mathcal{B}|}\left(\sum_{i\in\mathcal{B}}{\sf
clip}\left(\nabla_{\theta}\ell(\theta_{t};d_{i}),L\right)+\mathcal{N}(0,L^{2}\sigma^{2})\right)$

where ${\sf clip}\left(v,L\right)$ projects $v$ to the $\ell_{2}$-ball of
radius $L$, and $\mathcal{B}\subseteq[n]$ represents a mini-batch of data.

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 [6, 1, 72] 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.

Tree-based Aggregation: Consider the problem of privately releasing prefix sum
of a data stream, i.e., given a stream $D=(d_{1},d_{2},\dots,d_{T})$ such that
each $d_{i}\in\mathbb{R}^{p}$ has $\ell_{2}$ norm bounded by $L$, we aim to
release $s_{t}=\sum_{i=1}^{t}d_{i}$ for all $t\in[1,T]$ under differential
privacy. Dwork et al. [22] and Chan et al. [13] proposed a tree-based
aggregation algorithm to solve this problem. Consider a complete binary tree
$\mathcal{T}$ with leaf nodes as $d_{1}$ to $d_{T}$, and internal nodes as the
sum of all leaf nodes in its subtree. To release the exact prefix sum $s_{t}$,
we only need to sum up $O\left(\log(t)\right)$ nodes. To guarantee
differential privacy for releasing the tree $\mathcal{T}$, since any $d_{i}$
appears in $\log(T)$ nodes in $\mathcal{T}$, using composition, we can add
Gaussian noise of standard deviation of the order
$L\sqrt{\log(T)\log(1/\delta)}/\varepsilon$ to guarantee
$(\varepsilon,\delta)$-differential privacy.

Smith and Thakurta [65] 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.

##  4 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) [67, 6] can be
viewed of as an instantiation of DP-FTRL under appropriate choice of learning
rate.

Critically, _our privacy guarantees for DP-FTRL hold when the data $D$ are
processed in an arbitrary (even adversarially chosen) order,_ and do not
depend on the convexity of the loss functions. The utility guarantees, i.e.,
the regret and the excess risk guarantees require convex losses (i.e.,
$\ell(\cdot;\cdot)$ is convex in the first parameter). In the presentation
below, we assume differentiable losses for brevity. The arguments extend to
non-differentiable convex losses via standard use of sub-differentials [64,
32].

###  4.1 Algorithm Description

The main idea of DP-FTRL is based on three observations: i) For online convex
optimization, to bound the regret, for a given loss function
$\ell(\theta;d_{t})$ (i.e., the loss at time step $t$), it suffices for the
algorithm to operate on a linearization of the loss at $\theta_{t}$ (the model
output at time step $t$):
$\widetilde{\ell}(\theta;d_{t})=\langle\nabla_{\theta}\ell(\theta_{t};d_{t}),\theta-\theta_{t}\rangle$,
ii) Under appropriate choice of $\lambda$, optimizing for
$\theta_{t+1}=\arg\min\limits_{\theta\in\mathcal{C}}\sum\limits_{i=1}^{t}\widetilde{\ell}(\theta;d_{t})+\frac{\lambda}{2}\left\|\theta\right\|_{2}^{2}$
over $\theta\in\mathcal{C}$ gives a good model at step $t+1$, and iii) For all
$t\in[n]$, one can privately keep track of
$\sum\limits_{i=1}^{t}\widetilde{\ell}(\theta;d_{t})$ using the now standard
_tree aggregation protocol_ [22, 13]. While a variant of this idea was used in
[65] under the name of _follow-the-approximate-leader_ , one key difference is
that they used a quadratic approximation of the regularized loss, i.e.,
$\ell(\theta;d_{t})+\frac{\lambda}{t}\left\|\theta\right\|_{2}^{2}$. This
formulation results in a more complicated algorithm, sub-optimal regret
analysis, and failure to maintain structural properties (like sparsity)
introduced by composite losses [17, 75, 46, 48].

Algorithm 1 $\mathcal{A}_{\sf FTRL}$: Differentially Private Follow-The-
Regularized-Leader (DP-FTRL)

0: Data set: $D=[d_{1},\cdots,d_{n}]$ arriving in a stream, in an arbitrary
order; constraint set: $\mathcal{C}$, noise scale: $\sigma$, regularization
parameter: $\lambda$, clipping norm: $L$.

1:
$\theta_{1}\leftarrow\operatorname*{arg\,min}\limits_{\theta\in\mathcal{C}}\frac{\lambda}{2}\left\|\theta\right\|_{2}^{2}$.
Output $\theta_{1}$.

2: $\mathcal{T}\leftarrow{\texttt{InitializeTree}}\,(n,\sigma^{2},L)$.

3: for $t\in[n]$ do

4: Let $\nabla_{t}\leftarrow{\sf
clip}\left(\nabla_{\theta}\ell(\theta_{t};d_{t}),L\right)$, where ${\sf
clip}\left(\boldsymbol{v},L\right)=\boldsymbol{v}\cdot\min\left\\{\frac{L}{\left\|\boldsymbol{v}\right\|_{2}},1\right\\}$,
taking $\nabla_{\theta}\ell(\theta;\bot)=\mathbf{0}$.

5: $\mathcal{T}\leftarrow{\texttt{AddToTree}}\,(\mathcal{T},t,\nabla_{t})$.

6: $\boldsymbol{s}_{t}\leftarrow{\texttt{GetSum}}\,(\mathcal{T},t)$, i.e.,
estimate $\sum\limits_{i=1}^{t}\nabla_{i}$ via tree-aggregation protocol.

7:
$\theta_{t+1}\leftarrow\arg\min\limits_{\theta\in\mathcal{C}}\langle\boldsymbol{s}_{t},\theta\rangle+\frac{\lambda}{2}\|\theta\|^{2}_{2}$.
Output $\theta_{t+1}$.

8: end for

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 [34] 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 [65] 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[0,1]$ with
Line 7 in Algorithm 1 replaced by

$\boldsymbol{v}_{t}\leftarrow\gamma\cdot\boldsymbol{v}_{t-1}+\boldsymbol{s}_{t},\text{
}\theta_{t+1}\leftarrow\arg\min\limits_{\theta\in\mathcal{C}}\langle\boldsymbol{v}_{t},\theta\rangle+\frac{\lambda}{2}\|\theta-\theta_{0}\|^{2}_{2}$

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$.

######  Theorem 4.1 (Privacy guarantee).

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)$.

DP-FTRL’s memory footprint as compared to DP-SGD: At any given iteration, the
cost of computing the mini-batch gradients is exactly the same for both DP-
FTRL and DP-SGD. The only difference between the memory usage of DP-FTRL as
compared to DP-SGD is that DP-FTRL needs to keep track of worst-case
$(\log_{2}(t)+2)$ past gradient/noise information vectors (in
$\mathbb{R}^{p}$) for iteration $t$. Note that these are precomputed objects
that can be stored in memory.

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

In this section, we use the equivalence of non-private SGD and FTRL [48] to
establish equivalence between DP-SGD with privacy amplification (a variant of
noisy-SGD) and DP-FTRL in the unconstrained case, i.e.,
$\mathcal{C}=\mathbb{R}^{p}$. We further compare them based on the noise
variance added at the same privacy level of $(\varepsilon,\delta)$-DP. For the
brevity of presentation, we only make the comparison in the setting with
$\varepsilon=O(1)$.

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

$\theta_{t+1}\leftarrow\theta_{t}-\eta\cdot\left(\nabla_{\theta}\ell\left(\theta_{t};d_{t}\right)+\boldsymbol{a}_{t}\right),$
(3)

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)$
[6]. 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 [34]. Because of these,
and due to the fact that privacy amplification by sampling [42] 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.

##  5 Regret and Population Risk Guarantees

In this section we consider the setting when loss function $\ell$ is convex in
its first parameter, and provide for DP-FTRL: i) Adversarial regret guarantees
for general convex losses, ii) Tighter stochastic regret guarantees for least-
squares and linear losses, and iii) Population risk guarantees via online-to-
batch conversion. All our guarantees are high-probability over the randomness
of the algorithm, i.e., w.p. at least $1-\beta$, the error only depends on
${\sf polylog}(1/\beta)$.

###  5.1 Adversarial Regret for (Composite) Losses

The theorem here gives a regret guarantee for Algorithm 1 against a _fully
adaptive_ [64] adversary who chooses the loss function $\ell(\theta;d_{t})$
based on $[\theta_{1},\ldots,\theta_{t}]$, but without knowing the internal
randomness of the algorithm. See Appendix C.1 for a more general version of
Theorem 5.1, and its proof.

######  Theorem 5.1 (Regret guarantee).

Let $\theta$ be any model in $\mathcal{C}$, $[\theta_{1},\ldots,\theta_{n}]$
be the outputs of Algorithm $\mathcal{A}_{\sf FTRL}$ (Algorithm 1), and let
$L$ be a bound on the $\ell_{2}$-Lipschitz constant of the loss functions.
Setting $\lambda$ optimally and plugging in the noise scale $\sigma$ from
Theorem 4.1 to ensure $(\varepsilon,\delta)$-differential privacy, we have
that for any $\theta^{*}\in\mathcal{C}$, w.p. at least $1-\beta$ over the
randomness of $\mathcal{A}_{\sf FTRL}$, the regret

$\displaystyle R_{D}(\mathcal{A}_{\sf FTRL};\theta^{*})=$ $\displaystyle\qquad
O\left(L\left\|\theta^{*}\right\|_{2}\cdot\left(\frac{1}{\sqrt{n}}+\sqrt{\frac{p^{1/2}\ln^{2}(1/\delta)\ln(1/\beta)}{\varepsilon
n}}\right)\right).$

Extension to composite losses: Composite losses [17, 46, 48] refer to the
setting where in each round, the algorithm is provided with a function
$f_{t}(\theta)=\ell(\theta;d_{t})+r_{t}(\theta)$ with
$r_{t}:\mathcal{C}\to\mathbb{R}^{+}$ being a convex regularizer that does not
depend on the data sample $d_{t}$. The $\ell_{1}$-regularizer,
$r_{t}(\theta)=\|\theta\|_{1}$, is perhaps the most important practical
example, playing a critical role in high-dimensional statistics (e.g., in the
LASSO method) [9], as well as for applications like click-through-rate (CTR)
prediction where very sparse models are needed for efficiency [50]. In order
to operate on composite losses, we simply replace Line 7 of Algorithm
$\mathcal{A}_{\sf FTRL}$ with

$\theta_{t+1}\leftarrow\arg\min\limits_{\theta\in\mathcal{C}}\langle\boldsymbol{s}_{t},\theta\rangle+{\sum\limits_{i=1}^{t}r_{i}(\theta)}+\frac{\lambda}{2}\|\theta\|^{2}_{2},$

which can be solved in closed form in many important cases such as $\ell_{1}$
regularization. We obtain Corollary 5.2, analogous to [48, Theorem 1] in the
non-private case. We do not require any assumption (e.g., Lipschitzness) on
the regularizers beyond convexity since we _only linearize the losses_ in
Algorithm $\mathcal{A}_{\sf FTRL}$. It is worth mentioning that [65] is
fundamentally incompatible with this type of guarantee.

######  Corollary 5.2.

Let $\theta$ be any model in $\mathcal{C}$, $[\theta_{1},\ldots,\theta_{n}]$
be the outputs of Algorithm $\mathcal{A}_{\sf FTRL}$ (Algorithm 1), and $L$ be
a bound on the $\ell_{2}$-Lipschitz constant of the loss functions. W.p. at
least $1-\beta$ over the randomness of the algorithm, for any
$\theta^{*}\in\mathcal{C}$, assuming $\mathbf{0}\in\mathcal{C}$, we have:

$R_{D}(\mathcal{A}_{\sf FTRL};\theta^{*})\leq\frac{L\sigma\sqrt{p\lceil\lg
n\rceil\ln(n/\beta)}+L^{2}}{\lambda}+\frac{\lambda}{2n}\left\|\theta^{*}\right\|_{2}^{2}+\frac{1}{n}\sum\limits_{t=1}^{n}r_{t}(\theta^{*}).$

###  5.2 Stochastic Regret for Least-squared Losses

In this setting, for each data sample $d_{i}=(\mathbf{x}_{i},y_{i})$ (with
$\mathbf{x}_{i}\in\mathbb{R}^{p}$ and $y_{i}\in\mathbb{R}$) in the data set
$D=\\{d_{1},\ldots,d_{n}\\}$, the corresponding loss takes the least-squares
form555A similar argument as in Theorem 5.3 can be used in the setting where
the loss functions are linear, $\ell(\theta;d)=\langle\theta,d\rangle$ with
$d\in\mathbb{R}^{p}$ and $\left\|d\right\|_{2}\leq L$.:
$\ell(\theta;d_{i})=(y_{i}-\langle\mathbf{x}_{i},\theta\rangle)^{2}$. We also
assume that each data sample $d_{i}$ is drawn i.i.d. from some fixed
distribution $\tau$.

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

######  Theorem 5.3 (Stochastic regret for least-squared losses).

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$, let
$L=\max\limits_{\mathbf{x}\in\mathcal{D}}\left\|\mathbf{x}\right\|_{2}$, and
let $\max\limits_{y\sim\mathcal{D}}|y|\leq 1$. Let $\theta^{*}\in\mathcal{C}$,
$\mu=\max\limits_{\theta\in\mathcal{C}}\left\|\theta\right\|_{2}$, and
$\rho=\max\\{\mu,\mu^{2}\\}$. Then $\mathcal{A}_{\textsf{FTRL-LS}}$ provides
$(\varepsilon,\delta)$-differentially privacy while outputting
$[\theta_{1},\ldots,\theta_{n}]$ s.t. w.p. at least $1-\beta$ for any
$\theta^{*}\in\mathcal{C}$,
$\mathbb{E}_{D}\left[R_{D}(\mathcal{A}_{\textsf{FTRL-LS}};\theta^{*})\right]=$

$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 [3] can be extended to show a similar regret guarantee _in
expectation only_ , whereas ours is a high-probability guarantee.

###  5.3 Excess Risk via Online-to-Batch Conversion

Using the online-to-batch conversion [12, 63], 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)$.

##  6 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.

Minibatch DP-FTRL: So far, for simplicity we have focused on DP-FTRL with
model updates corresponding to new gradient from a single sample. However, in
practice, instead of computing the gradient on a single data sample $d_{t}$ at
time step $t$, we will estimate gradient over a batch
$M_{t}=\left\\{d^{(1)}_{t},\ldots,d^{(q)}_{t}\right\\}$ as
$\nabla_{t}=\frac{1}{q}\sum\limits_{i=1}^{q}{\sf
clip}\left(\nabla_{\theta}\ell\left(\theta_{t};d^{(1)}_{t}\right),L\right)$.
This immediately implies the number of steps per epoch to be $\lceil
n/q\rceil$. Furthermore, since the $\ell_{2}$-sensitivity in each batch gets
scaled down to $\frac{L}{q}$ instead of $L$ (as in Algorithm $\mathcal{A}_{\sf
FTRL}$). We take the above two observations into consideration in our privacy
accounting.

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.

##  7 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
sourced666https://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.

###  7.1 Experimental Setup

Datasets: We conduct our evaluation on three image classification tasks, MNIST
[45], CIFAR-10 [44], EMNIST (ByMerge split) [15]; and a next word prediction
task on StackOverflow data set [55]. 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 [57]. For StackOverflow, we use
the one-layer LSTM network described in [60]. 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 [31], 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.

(a) MNIST

(b) CIFAR-10

(c) EMNIST (ByMerge)

Figure 1: Privacy/accuracy trade-offs for DP-SGD (private baseline), DP-SGD
without amplification (label “DP-SGD (no-amp)”), and DP-FTRLM on MNIST (mini-
batch size 250), CIFAR-10 (mini-batch size 500), and EMNIST (mini-batch size
500). “4x” in the label denotes four times computation cost (by increasing
batch size four times). All algorithms use 5 epochs of training for the
smaller batch size and 20 epochs for the larger batch size, handled by DP-
FTRL-TreeRestart for FTRL.

###  7.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.

(a)

(b)

(c)

Figure 2: (a) Accuracy on StackOverflow under different privacy epsilon by
varying noise multiplier and batch sizes. (b) Test accuracy of DP-SGDM and DP-
FTRLM with various noise multipliers for StackOverflow. (c) Relationship
between user-level privacy $\varepsilon$ (when
$\delta\approx\nicefrac{{1}}{{\text{population}}}$) and computation cost
(report goal) for two fixed accuracy targets (see legend) on the StackOverflow
data set.

###  7.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 [51], 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$.

##  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 [34] 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

  * Abadi et al. [2016] Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In _Proc. of the 2016 ACM SIGSAC Conf. on Computer and Communications Security (CCS’16)_ , pages 308–318, 2016.
  * Abernethy et al. [2019] Jacob Abernethy, Young Hun Jung, Chansoo Lee, Audra McMillan, and Ambuj Tewari.  Online learning via the differential privacy lens.  In _NeurIPS_ , 2019.
  * Agarwal and Singh [2017] Naman Agarwal and Karan Singh.  The price of differential privacy for online learning.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pages 32–40, 2017.
  * Asoodeh et al. [2020] Shahab Asoodeh, Jiachun Liao, Flavio P Calmon, Oliver Kosut, and Lalitha Sankar.  A better bound gives a hundred rounds: Enhanced privacy guarantees via f-divergences.  In _2020 IEEE International Symposium on Information Theory (ISIT)_ , pages 920–925. IEEE, 2020.
  * Balle et al. [2020] Borja Balle, Peter Kairouz, Brendan McMahan, Om Dipakbhai Thakkar, and Abhradeep Thakurta.  Privacy amplification via random check-ins.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Bassily et al. [2014] Raef Bassily, Adam Smith, and Abhradeep Thakurta.  Private empirical risk minimization: Efficient algorithms and tight error bounds.  In _Proc. of the 2014 IEEE 55th Annual Symp. on Foundations of Computer Science (FOCS)_ , pages 464–473, 2014.
  * Bassily et al. [2019] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta.  Private stochastic convex optimization with optimal rates.  In _Advances in Neural Information Processing Systems_ , pages 11279–11288, 2019.
  * Bassily et al. [2020] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar.  Stability of stochastic gradient descent on nonsmooth convex losses.  _arXiv preprint arXiv:2006.06914_ , 2020.
  * Bhlmann and van de Geer [2011] Peter Bhlmann and Sara van de Geer.  _Statistics for High-Dimensional Data: Methods, Theory and Applications_.  Springer Publishing Company, Incorporated, 2011.  ISBN 3642201911.
  * Bonawitz et al. [2019] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konecny, Stefano Mazzocchi, H Brendan McMahan, et al.  Towards federated learning at scale: System design.  _arXiv preprint arXiv:1902.01046_ , 2019.
  * Canonne et al. [2020] Clément Canonne, Gautam Kamath, and Thomas Steinke.  The discrete gaussian for differential privacy.  _arXiv preprint arXiv:2004.00010_ , 2020.
  * Cesa-Bianchi et al. [2002] Nicoló Cesa-Bianchi, Alex Conconi, and Claudio Gentile.  On the genomeralization ability of on-line learning algorithms.  In _Advances in neural information processing systems_ , pages 359–366, 2002.
  * Chan et al. [2011] T.-H. Hubert Chan, Elaine Shi, and Dawn Song.  Private and continual release of statistics.  _ACM Trans. on Information Systems Security_ , 14(3):26:1–26:24, November 2011.
  * Chaudhuri et al. [2011] Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate.  Differentially private empirical risk minimization.  _Journal of Machine Learning Research_ , 12(Mar):1069–1109, 2011.
  * Cohen et al. [2017] Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik.  Emnist: Extending mnist to handwritten letters.  _2017 International Joint Conference on Neural Networks (IJCNN)_ , 2017.  doi: 10.1109/ijcnn.2017.7966217.
  * Duchi et al. [2011] John Duchi, Elad Hazan, and Yoram Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  _Journal of machine learning research_ , 12(7), 2011.
  * Duchi et al. [2010] John C Duchi, Shai Shalev-Shwartz, Yoram Singer, and Ambuj Tewari.  Composite objective mirror descent.  In _COLT_ , pages 14–26. Citeseer, 2010.
  * Duchi et al. [2013] John C. Duchi, Michael I. Jordan, and Martin J. Wainwright.  Local privacy and statistical minimax rates.  In _54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA_ , pages 429–438. IEEE Computer Society, 2013.  doi: 10.1109/FOCS.2013.53.  URL https://doi.org/10.1109/FOCS.2013.53.
  * Dwork and Roth [2014] Cynthia Dwork and Aaron Roth.  The algorithmic foundations of differential privacy.  _Foundations and Trends in Theoretical Computer Science_ , 9(3–4):211–407, 2014.
  * Dwork et al. [2006a] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor.  Our data, ourselves: Privacy via distributed noise generation.  In _Advances in Cryptology—EUROCRYPT_ , pages 486–503, 2006a.
  * Dwork et al. [2006b] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In _Proc. of the Third Conf. on Theory of Cryptography (TCC)_ , pages 265–284, 2006b.  URL http://dx.doi.org/10.1007/11681878_14.
  * Dwork et al. [2010] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum.  Differential privacy under continual observation.  In _Proc. of the Forty-Second ACM Symp. on Theory of Computing (STOC’10)_ , pages 715–724, 2010.
  * Erlingsson et al. [2019] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta.  Amplification by shuffling: From local to central differential privacy via anonymity.  In _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 2468–2479. SIAM, 2019.
  * Erlingsson et al. [2020a] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, and Abhradeep Thakurta.  Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation.  _CoRR_ , abs/2001.03618, 2020a.  URL https://arxiv.org/abs/2001.03618.
  * Erlingsson et al. [2020b] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, and Abhradeep Thakurta.  Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation.  _CoRR_ , abs/2001.03618, 2020b.
  * Evfimievski et al. [2003] Alexandre Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant.  Limiting privacy breaches in privacy preserving data mining.  In _Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems_ , pages 211–222, 2003.
  * Facebook [2020] Facebook.  Introducing opacus: A high-speed library for training pytorch models with differential privacy, 2020.
  * Feldman et al. [2018] Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta.  Privacy amplification by iteration.  In _59th Annual IEEE Symp. on Foundations of Computer Science (FOCS)_ , pages 521–532, 2018.
  * Feldman et al. [2020a] Vitaly Feldman, Tomer Koren, and Kunal Talwar.  Private stochastic convex optimization: Optimal rates in linear time.  In _Proc. of the Fifty-Second ACM Symp. on Theory of Computing (STOC’20)_ , 2020a.
  * Feldman et al. [2020b] Vitaly Feldman, Audra McMillan, and Kunal Talwar.  Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling.  _arXiv preprint arXiv:2012.12803_ , 2020b.
  * Google [2019] Google.  Tensorflow-privacy.  https://github.com/tensorflow/privacy, 2019.
  * Hazan [2019] Elad Hazan.  Introduction to online convex optimization.  _arXiv preprint arXiv:1909.05207_ , 2019.
  * Hazan and Kale [2014] Elad Hazan and Satyen Kale.  Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization.  _The Journal of Machine Learning Research_ , 15(1):2489–2512, 2014.
  * Honaker [2015] James Honaker.  Efficient Use of Differentially Private Binary Trees.  In _Theory and Practice of Differential Privacy (TPDP 2015), London, UK_ , 2015.
  * Iyengar et al. [2019] Roger Iyengar, Joseph P Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang.  Towards practical differentially private convex optimization.  In _2019 IEEE Symposium on Security and Privacy (SP)_ , 2019.
  * Jagielski et al. [2020] Matthew Jagielski, Jonathan Ullman, and Alina Oprea.  Auditing differentially private machine learning: How private is private sgd?  _arXiv preprint arXiv:2006.07709_ , 2020.
  * Jain and Thakurta [2014] Prateek Jain and Abhradeep Guha Thakurta.  (near) dimension independent risk bounds for differentially private learning.  In _International Conference on Machine Learning_ , pages 476–484, 2014.
  * Jain et al. [2012] Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta.  Differentially private online learning.  In _Proc. of the 25th Annual Conf. on Learning Theory (COLT)_ , volume 23, pages 24.1–24.34, June 2012.
  * Kairouz et al. [2019] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al.  Advances and open problems in federated learning.  _arXiv preprint arXiv:1912.04977_ , 2019.
  * Kairouz et al. [2021] Peter Kairouz, Brendan Mcmahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu.  Practical and private (deep) learning without sampling or shuffling.  In _Proceedings of the 38th International Conference on Machine Learning_ , pages 5213–5225, 2021.
  * Kalai and Vempala [2005] Adam Kalai and Santosh Vempala.  Efficient algorithms for online decision problems.  _Journal of Computer and System Sciences_ , 71(3):291–307, 2005.
  * Kasiviswanathan et al. [2008] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith.  What can we learn privately?  In _49th Annual IEEE Symp. on Foundations of Computer Science (FOCS)_ , pages 531–540, 2008.
  * Kifer et al. [2012] Daniel Kifer, Adam Smith, and Abhradeep Thakurta.  Private convex empirical risk minimization and high-dimensional regression.  In _Conference on Learning Theory_ , pages 25–1, 2012.
  * Krizhevsky [2009] Alex Krizhevsky.  Learning multiple layers of features from tiny images, 2009.
  * LeCun et al. [1998] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * McMahan [2011] Brendan McMahan.  Follow-the-regularized-leader and mirror descent: Equivalence theorems and l1 regularization.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , pages 525–533, 2011.
  * McMahan et al. [2017a] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA_ , pages 1273–1282, 2017a.  URL http://proceedings.mlr.press/v54/mcmahan17a.html.
  * McMahan [2017] H. Brendan McMahan.  A survey of algorithms and analysis for adaptive online learning.  _Journal of Machine Learning Research_ , 18(90):1–50, 2017.  URL http://jmlr.org/papers/v18/14-428.html.
  * McMahan and Streeter [2010] H. Brendan McMahan and Matthew Streeter.  Adaptive bound optimization for online convex optimization.  In _Proceedings of the 23rd Annual Conference on Learning Theory (COLT)_ , 2010.
  * McMahan et al. [2013] H Brendan McMahan, Gary Holt, David Sculley, Michael Young, Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, et al.  Ad click prediction: a view from the trenches.  In _Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 1222–1230, 2013.
  * McMahan et al. [2017b] H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang.  Learning differentially private recurrent language models.  _arXiv preprint arXiv:1710.06963_ , 2017b.
  * McMahan et al. [2018] H Brendan McMahan, Galen Andrew, Ulfar Erlingsson, Steve Chien, Ilya Mironov, Nicolas Papernot, and Peter Kairouz.  A general approach to adding differential privacy to iterative training procedures.  _arXiv preprint arXiv:1812.06210_ , 2018.
  * Mironov [2017] Ilya Mironov.  Rényi differential privacy.  In _2017 IEEE 30th Computer Security Foundations Symposium (CSF)_ , pages 263–275. IEEE, 2017.
  * Nasr et al. [2021] Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini.  Adversary instantiation: Lower bounds for differentially private machine learning.  In _IEEE S and P (Oakland)_ , 2021.
  * Overflow [2018] Stack Overflow.  The Stack Overflow Data, 2018.  https://www.kaggle.com/stackoverflow/stackoverflow.
  * Papernot et al. [2020a] Nicolas Papernot, Steve Chien, Shuang Song, Abhradeep Thakurta, and Ulfar Erlingsson.  Making the shoe fit: Architectures, initializations, and tuning for learning with privacy, 2020a.  URL https://openreview.net/forum?id=rJg851rYwH.
  * Papernot et al. [2020b] Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Úlfar Erlingsson.  Tempered sigmoid activations for deep learning with differential privacy.  _arXiv preprint arXiv:2007.14191_ , 2020b.
  * Pichapati et al. [2019] Venkatadheeraj Pichapati, Ananda Theertha Suresh, Felix X Yu, Sashank J Reddi, and Sanjiv Kumar.  Adaclip: Adaptive clipping for private sgd.  _arXiv preprint arXiv:1908.07643_ , 2019.
  * Ramaswamy et al. [2020] Swaroop Ramaswamy, Om Thakkar, Rajiv Mathews, Galen Andrew, H. Brendan McMahan, and Françoise Beaufays.  Training production language models without memorizing user data, 2020\.
  * Reddi et al. [2020] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečnỳ, Sanjiv Kumar, and H Brendan McMahan.  Adaptive federated optimization.  _arXiv preprint arXiv:2003.00295_ , 2020.
  * Robbins and Monro [1951] Herbert Robbins and Sutton Monro.  A stochastic approximation method.  _The annals of mathematical statistics_ , pages 400–407, 1951.
  * Shalev-Shwartz [2012] Shai Shalev-Shwartz.  Online learning and online convex optimization.  _Foundations and Trends in Machine Learning_ , 4(2):107–194, 2012.
  * Shalev-Shwartz et al. [2009] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan.  Stochastic convex optimization.  In _COLT 2009 - The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009_ , 2009.  URL http://www.cs.mcgill.ca/%7Ecolt2009/papers/018.pdf#page=1.
  * Shalev-Shwartz et al. [2011] Shai Shalev-Shwartz et al.  Online learning and online convex optimization.  _Foundations and trends in Machine Learning_ , 4(2):107–194, 2011.
  * Smith and Thakurta [2013] Adam Smith and Abhradeep Thakurta.  (nearly) optimal algorithms for private online learning in full-information and bandit settings.  In _Advances in Neural Information Processing Systems_ , pages 2733–2741, 2013.
  * Song and Shmatikov [2019] Congzheng Song and Vitaly Shmatikov.  Auditing data provenance in text-generation models.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 196–206, 2019.
  * Song et al. [2013] Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate.  Stochastic gradient descent with differentially private updates.  In _2013 IEEE Global Conference on Signal and Information Processing_ , pages 245–248. IEEE, 2013.
  * Thakkar et al. [2019] Om Thakkar, Galen Andrew, and H. Brendan McMahan.  Differentially private learning with adaptive clipping.  _CoRR_ , abs/1905.03871, 2019.  URL http://arxiv.org/abs/1905.03871.
  * Thakkar et al. [2020] Om Thakkar, Swaroop Ramaswamy, Rajiv Mathews, and Françoise Beaufays.  Understanding unintended memorization in federated learning.  _arXiv preprint arXiv:2006.07490_ , 2020.
  * Tramèr and Boneh [2021] Florian Tramèr and Dan Boneh.  Differentially private learning needs better features (or much more data).  In _International Conference on Learning Representations (ICLR)_ , 2021.
  * Vadhan [2017] Salil Vadhan.  The complexity of differential privacy.  In _Tutorials on the Foundations of Cryptography_ , pages 347–450. Springer, 2017.
  * Wang et al. [2019] Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan.  Subsampled rényi differential privacy and analytical moments accountant.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 1226–1235. PMLR, 2019.
  * Warner [1965] Stanley L. Warner.  Randomized response: A survey technique for eliminating evasive answer bias.  _J. of the American Statistical Association_ , 60(309):63–69, 1965.
  * Wu et al. [2017] Xi Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey F. Naughton.  Bolt-on differential privacy for scalable stochastic gradient descent-based analytics.  In Semih Salihoglu, Wenchao Zhou, Rada Chirkova, Jun Yang, and Dan Suciu, editors, _Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD_ , 2017.
  * Xiao [2010] Lin Xiao.  Dual averaging methods for regularized stochastic learning and online optimization.  _The Journal of Machine Learning Research_ , 11:2543–2596, 2010.
  * Zhu and Wang [2019] Yuqing Zhu and Yu-Xiang Wang.  Poission subsampled rényi differential privacy.  In _International Conference on Machine Learning_ , pages 7634–7642. PMLR, 2019.

##  Appendix A Other Related Work

Differentially private empirical risk minimization (ERM) and private online
learning are well-studied areas in the privacy literature [14, 43, 38, 65, 67,
6, 37, 1, 51, 74, 3, 2, 7, 35, 58, 68, 29, 57]777This is only a small
representative subset of the literature.. The connection between private ERM
and private online learning was first explored in [38], and the idea of using
stability induced by differential privacy for designing low-regret algorithms
was explored in [41, 3, 2]. 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

###  B.1 Details of the Tree Aggregation Scheme

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

  1. 1.

${\texttt{InitializeTree}}\,(n,\sigma^{2},L)$: Initialize a complete binary
tree $\mathcal{T}$ with $2^{\lceil\lg(n)\rceil}$ leaf nodes, with each node
being sampled i.i.d. from
$\mathcal{N}(0,L^{2}\sigma^{2}\cdot\mathbb{I}_{p\times p})$.

  2. 2.

${\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.

  3. 3.

${\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.

    1. (a)

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.

    2. (b)

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.

    3. (c)

Return $\boldsymbol{s}$.

Incorporating the iterative estimator from [34]: 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 [34]. 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. [34] 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 [34] 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.

  1. 3.

${\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.

    1. (a)

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.

    2. (b)

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

      1. i.

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.

      2. ii.

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}$.

      3. iii.

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

$\boldsymbol{s}_{[x:z]}\leftarrow\frac{\boldsymbol{r}^{\prime}_{[x:z]}}{2-(x-z+1)^{-1}},\
\ \text{where}\ \
\boldsymbol{r}^{\prime}_{[x:z]}\leftarrow\boldsymbol{r}_{[x:z]}+\frac{\boldsymbol{r}^{\prime}_{[x:y]}+\boldsymbol{r}^{\prime}_{[y+1:z]}}{2}\text{
and $y=\lfloor(x+z)/2\rfloor$},$ (4)

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

      4. iv.

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

    3. (c)

Return $\boldsymbol{s}$.

###  B.2 Proof of Theorem 4.1

###### Proof.

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 [20],[53,
Corollary 3], and adaptive RDP composition [53, Proposition1] to complete the
proof.

While the original work on tree aggregation [22, 13] 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)

######  Theorem B.1.

Consider data set $D=\\{d_{1},\ldots,d_{n}\\}$, model space
$\mathcal{C}=\mathbb{R}^{p}$ and initial model $\theta_{0}={\mathbf{0}}^{p}$.
For $t\in[n]$, let the update of Noisy-SGD be $\theta^{\textsf{Noisy-
SGD}}_{t+1}\leftarrow\theta_{t}-\eta\cdot\left(\nabla_{\theta}\ell\left(\theta_{t}^{\textsf{Noisy-
SGD}};d_{t}\right)+\boldsymbol{a}_{t}\right)$, where $\boldsymbol{a}_{t}$’s
are noise random variables. Let the DP-FTRL (Algorithm 1) updates be
$\theta^{\textsf{DP-
FTRL}}_{t+1}\leftarrow\operatorname*{arg\,min}\limits_{\theta\in\mathbb{R}^{p}}\sum\limits_{i=1}^{t}\nabla_{\theta}\ell\left(\theta^{\textsf{DP-
FTRL}}_{i};d_{i}\right)+\langle\boldsymbol{b}_{t},\theta\rangle+\frac{1}{2\eta}\left\|\theta\right\|_{2}^{2}$,
where $\boldsymbol{b}_{t}$’s are the noises added by the tree-aggregation
mechanism.

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}$.

###### Proof.

Consider the non-private SGD and FTRL. Recall that the SGD update is
$\theta^{\sf SGD}_{t+1}\leftarrow\theta^{\sf
SGD}_{t}-\eta\nabla_{\theta}\ell(\theta^{\sf SGD}_{t};d_{t})$, where $\eta$ is
the learning rate. Opening up the recurrence, we have $\theta^{\sf
SGD}_{t+1}\leftarrow\theta_{0}-\eta\sum\limits_{i=1}^{t}\nabla_{\theta}\ell(\theta^{\sf
SGD}_{i};d_{i})$. If $\theta^{\sf SGD}_{0}=\mathbf{0}^{p}$, then equivalently
$\theta^{\sf
SGD}_{t+1}\leftarrow\operatorname*{arg\,min}\limits_{\theta\in\mathbb{R}^{p}}\langle\sum\limits_{i=1}^{t}\nabla_{\theta}\ell(\theta^{\sf
SGD}_{i};d_{i}),\theta\rangle+\frac{1}{2\eta}\left\|\theta\right\|_{2}^{2}$.
This is identical to the update rule of the non-private FTRL (i.e., with
$\sigma$ set to $0$ in DP-FTRL) with regularization parameter $\lambda$ set to
$\frac{1}{\eta}$.

Now we consider the Noisy-SGD and DP-FTRL. Recall that Noisy-SGD has update
rule $\theta^{\textsf{Noisy-SGD}}_{t+1}\leftarrow\theta^{\textsf{Noisy-
SGD}}_{t}-\eta\left(\nabla_{\theta}\ell(\theta^{\textsf{Noisy-
SGD}}_{t};d_{t})+\boldsymbol{a}_{t}\right)$, where $\boldsymbol{a}_{t}$ is the
Gaussian noise added at time step $t$. Similar as before, this rule can be
written as

$\displaystyle\theta^{\textsf{Noisy-
SGD}}_{t+1}\leftarrow\operatorname*{arg\,min}\limits_{\theta\in\mathbb{R}^{p}}\langle\sum\limits_{i=1}^{t}\nabla_{\theta}\ell(\theta^{\textsf{Noisy-
SGD}}_{i};d_{i}),\theta\rangle+\langle\sum_{i=1}^{t}\boldsymbol{a}_{i},\theta\rangle+\frac{1}{2\eta}\left\|\theta\right\|_{2}^{2}.$
(5)

The update rule of DP-FTRL can be written as

$\displaystyle\theta^{\textsf{DP-
FTRL}}_{t+1}\leftarrow\operatorname*{arg\,min}\limits_{\theta\in\mathbb{R}^{p}}\langle\sum\limits_{i=1}^{t}\nabla_{\theta}\ell\left(\theta^{\textsf{DP-
FTRL}}_{i};d_{i}\right),\theta\rangle+\langle\boldsymbol{b}_{t},\theta\rangle+\frac{\lambda}{2}\left\|\theta\right\|_{2}^{2},$
(6)

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

###  C.1 Proof of Theorem 5.1

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

######  Theorem C.1 (Regret guarantee (Theorem 5.1 in detail)).

Let $[\theta_{1},\ldots,\theta_{n}]$ be the outputs of Algorithm
$\mathcal{A}_{\sf FTRL}$ (Algorithm 1), and $L$ be a bound on the
$\ell_{2}$-Lipschitz constant of the loss functions. W.p. at least $1-\beta$
over the randomness of $\mathcal{A}_{\sf FTRL}$, the following is true for any
$\theta^{*}\in\mathcal{C}$.

$\displaystyle\frac{1}{n}\sum\limits_{t=1}^{n}\ell(\theta_{t};d_{t})-\frac{1}{n}\sum\limits_{t=1}^{n}\ell(\theta^{*};d_{t})\leq\frac{L\sigma\sqrt{p\lceil\lg
n\rceil\ln(n/\beta)}+L^{2}}{\lambda}+\frac{\lambda}{2n}\left(\left\|\theta^{*}\right\|_{2}^{2}-\left\|\theta_{1}\right\|_{2}^{2}\right)$

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

$\displaystyle R_{D}(\mathcal{A}_{\sf
FTRL};\theta^{*})=O\left(L\left\|\theta^{*}\right\|_{2}\cdot\left(\frac{1}{\sqrt{n}}+\sqrt{\frac{p^{1/2}\ln^{2}(1/\delta)\ln(1/\beta)}{\varepsilon
n}}\right)\right).$

###### Proof.

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:

$\displaystyle\widetilde{\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}}_{J_{t}^{\sf
np}(\theta)},\qquad\text{where }\nabla_{t}=\nabla\ell(\theta_{t};d_{t}).$

That is, post-hoc we consider the hypothetical application of non-private FTRL
to the same sequence of _linearized_ loss functions
$f_{t}(\widetilde{\theta})=\langle\nabla_{t},\widetilde{\theta}\rangle=\langle\nabla\ell(\theta_{t};d_{t}),\widetilde{\theta}\rangle$
seen in the private training run. In the following, we will first bound how
much the models output by $\mathcal{A}_{\sf FTRL}$ deviate from models output
by the hypothetical non-private FTRL discussed above. Then, we invoke standard
regret bound for FTRL, while accounting for the deviation of the models output
by $\mathcal{A}_{\sf FTRL}$.

To bound $\left\|\widetilde{\theta}_{t+1}-\theta_{t+1}\right\|_{2}$, we apply
Lemma C.2. We set $\phi_{1}(\theta)=J_{t}^{\sf np}(\theta)/\lambda$,
$\phi_{2}(\theta)=J_{t}^{\sf priv}(\theta)/\lambda$, and both $\|\cdot\|$ and
its dual as the $\ell_{2}$ norm. We thus have
$\Psi(\theta)=\langle\boldsymbol{b}_{t},\theta\rangle/\lambda$, with
$\boldsymbol{b}_{t}/\lambda$ being its subgradient. Therefore,

$\left\|\widetilde{\theta}_{t+1}-\theta_{t+1}\right\|_{2}\leq\frac{\left\|\boldsymbol{b}_{t}\right\|_{2}}{\lambda}.$
(7)

######  Lemma C.2 (Lemma 7 from [48] restated).

Let $\phi_{1}:\mathcal{C}\to\mathbb{R}$ be a convex function (defined over
$\mathcal{C}\subseteq\mathbb{R}^{p}$) s.t.
$\theta_{1}\in\operatorname*{arg\,min}\limits_{\theta\in\mathcal{C}}\phi_{1}(\theta)$
exists. Let $\Psi(\theta)$ be a convex function s.t.
$\phi_{2}(\theta)=\phi_{1}(\theta)+\Psi(\theta)$ is 1-strongly convex w.r.t.
$\|\cdot\|$-norm. Let
$\theta_{2}\in\operatorname*{arg\,min}\limits_{\theta\in\mathcal{C}}\phi_{2}(\theta)$.
Then for any $\boldsymbol{b}$ in the subgradient of $\Psi$ at $\theta_{1}$,
the following is true:
$\|\theta_{1}-\theta_{2}\|_{*}\leq\|\boldsymbol{b}\|_{*}$. Here
$\|\cdot\|_{*}$ is the dual-norm of $\|\cdot\|$.

We can now easily bound the regret. By standard linear approximation “trick”
from the online learning literature [62, 32], we have the following. For
$\nabla_{t}=\nabla_{\theta}\ell(\theta_{t};d_{t})$,

$\displaystyle\frac{1}{n}\sum\limits_{t=1}^{n}\ell(\theta_{t};d_{t})-\frac{1}{n}\sum\limits_{t=1}^{n}\ell(\theta^{*};d_{t})$
$\displaystyle\leq\frac{1}{n}\sum\limits_{t=1}^{n}\langle\nabla_{t},\theta_{t}-\theta^{*}\rangle$
$\displaystyle=\frac{1}{n}\sum\limits_{t=1}^{n}\langle\nabla_{t},\theta_{t}-\widetilde{\theta}_{t}+\widetilde{\theta}_{t}-\theta^{*}\rangle$
$\displaystyle=\underbrace{\frac{1}{n}\sum\limits_{t=1}^{n}\langle\nabla_{t},\widetilde{\theta}_{t}-\theta^{*}\rangle}_{A}+\underbrace{\frac{1}{n}\sum\limits_{t=1}^{n}\langle\nabla_{t},\theta_{t}-\widetilde{\theta}_{t}\rangle}_{B}.$
(8)

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$,

$\displaystyle B$
$\displaystyle\leq\frac{1}{n}\sum\limits_{t=1}^{n}\left\|\nabla_{t}\right\|_{2}\cdot\left\|\widetilde{\theta}_{t}-\theta_{t}\right\|_{2}\leq\frac{1}{n}\sum\limits_{t=1}^{n}L\cdot\left\|\widetilde{\theta}_{t}-\theta_{t}\right\|_{2}\leq\frac{L\sigma\sqrt{p\lceil\lg
n\rceil\ln(n/\beta)}}{\lambda}.$ (9)

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)$.

Algorithm 2 $\mathcal{A}_{\textsf{FTRL-LS}}$: Differentially Private Follow-
The-Regularized-Leader (DP-FTRL) for least-squared losses

0: Data set: $D=\\{(\mathbf{x}_{1},y_{1}),\cdots,(\mathbf{x}_{n},y_{n})\\}$
arriving in a stream, constraint set: $\mathcal{C}$, noise scale: $\sigma$,
regularization parameter: $\lambda$, upper bound on
$\left\\{\left\|\mathbf{x}_{t}\right\|_{2}\right\\}_{t=1}^{n}:L$.

1:
$\theta_{1}\leftarrow\operatorname*{arg\,min}\limits_{\theta\in\mathcal{C}}\frac{\lambda}{2}\left\|\theta\right\|_{2}^{2}$.
Output $\theta_{1}$.

2: $\mathcal{T}_{\sf
bias}\leftarrow{\texttt{InitializeTreeBias}}\,(n,\sigma^{2},L)$,
$\mathcal{T}_{\sf
cov}\leftarrow{\texttt{InitializeTreeCov}}\,(n,\sigma^{2},L^{2})$.

3: for $t\in[n]$ do

4: Let $\boldsymbol{v}_{t}\leftarrow y_{t}\cdot\mathbf{x}_{t}$, and
$M_{t}\leftarrow\mathbf{x}_{t}\mathbf{x}_{t}^{\top}$.

5: $\mathcal{T}_{\sf
bias}\leftarrow{\texttt{AddToTreeBias}}\,(\mathcal{T}_{\sf
bias},t,\boldsymbol{v}_{t})$ and $\mathcal{T}_{\sf
cov}\leftarrow{\texttt{AddToTreeCov}}\,(\mathcal{T}_{\sf cov},t,M_{t})$.

6: $\boldsymbol{s}_{t}\leftarrow{\texttt{GetSumBias}}\,(\mathcal{T}_{\sf
bias},t)$, and $W_{t}\leftarrow{\texttt{GetSumCov}}\,(\mathcal{T}_{\sf
cov},t)$.

7:
$\theta_{t+1}\leftarrow\arg\min\limits_{\theta\in\mathcal{C}}\left(\theta^{\top}\cdot
W_{t}\cdot\theta-2\langle\boldsymbol{s}_{t},\theta\rangle\right)+\frac{\lambda}{2}\|\theta\|^{2}_{2}$.
Output $\theta_{t+1}$.

8: end for

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.

######  Theorem C.3 (Privacy guarantee).

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.

######  Theorem C.4 (Stochastic regret for least-squared losses).

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

$\displaystyle\mathbb{E}_{D}\left[R_{D}(\mathcal{A}_{\textsf{FTRL-
LS}};\theta^{*})\right]=\mathbb{E}_{D}\left[\frac{1}{n}\sum\limits_{t=1}^{n}\left(y_{t}-\langle\mathbf{x}_{t},\theta_{t}\rangle\right)^{2}-\left(y_{t}-\langle\mathbf{x}_{t},\theta^{*}\rangle\right)^{2}\right]$
$\displaystyle=$ $\displaystyle
O\left(\frac{p\ln^{2}(n)\ln(n/\beta)\sigma^{2}\cdot\left(L^{2}+L^{4}\mu^{2}+L^{3}\mu\right)}{\lambda
n}+\frac{L^{4}\mu^{2}}{\lambda}+\frac{\lambda\ln(n)}{n}\cdot\left\|\theta^{*}\right\|_{2}^{2}\right).$

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

$\displaystyle\mathbb{E}_{D}\left[R_{D}(\mathcal{A}_{\textsf{FTRL-
LS}};\theta^{*})\right]=L^{2}\cdot\left\|\theta^{*}\right\|_{2}\cdot
O\left(\left(\sqrt{\frac{\mu^{2}\ln(n)}{n}}+\frac{\sqrt{p\ln^{5}(n/\beta)\cdot\ln(1/\delta)\cdot\max\\{\mu,\mu^{2}\\}}}{\varepsilon
n}\right)\right).$

###### Proof.

Consider the following regret function: $R_{D}(\mathcal{A}_{\textsf{FTRL-
LS}};\theta^{*})=\frac{1}{n}\sum\limits_{t=1}^{n}\left((y_{t}-\langle\theta_{t},\mathbf{x}_{t}\rangle)^{2}-(y_{t}-\langle\theta,\mathbf{x}_{t}\rangle)^{2}\right)$.
We will bound $\mathbb{E}_{D}\left[R_{D}(\mathcal{A}_{\textsf{FTRL-
LS}};\theta^{*})\right]$. Following the notation in the proof of Theorem 5.1,
recall the following two functions.

  * •

$\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

$\displaystyle\left\|\widetilde{\theta}_{t+1}-\theta_{t+1}\right\|_{2}=O\left(\frac{L\sigma+L^{2}\sigma\cdot\mu}{\lambda}\cdot\sqrt{p\ln(n)\ln(n/\beta)}\right).$
(10)

Therefore,

$\displaystyle J_{t}^{\sf
np}(\widetilde{\theta}_{t+1})+\langle\boldsymbol{b}_{t},\widetilde{\theta}_{t+1}\rangle+\widetilde{\theta}_{t+1}^{\top}B_{t}\widetilde{\theta}_{t+1}\geq\underbrace{J_{t}^{\sf
np}(\theta_{t+1})+\langle\boldsymbol{b}_{t},\theta_{t+1}\rangle+\theta_{t+1}^{\top}B_{t}\theta_{t+1}}_{J_{t}^{\sf
priv}(\theta_{t+1})}+\frac{\lambda}{2}\left\|\widetilde{\theta}_{t+1}-\theta_{t+1}\right\|_{2}^{2}$
(11) $\displaystyle\Rightarrow\quad$ $\displaystyle J_{t}^{\sf
np}(\theta_{t+1})-J_{t}^{\sf
np}(\widetilde{\theta}_{t+1})=O\left(\left\|\boldsymbol{b}_{t}\right\|_{2}\cdot\left\|\widetilde{\theta}_{t+1}-\theta_{t+1}\right\|_{2}+\left\|B_{t}\right\|_{2}\cdot\left\|\widetilde{\theta}_{t+1}-\theta_{t+1}\right\|_{2}\cdot\mu\right)$
(12) $\displaystyle\Rightarrow\quad$ $\displaystyle J_{t}^{\sf
np}(\theta_{t+1})-J_{t}^{\sf
np}(\widetilde{\theta}_{t+1})=O\left((p\ln(n)\ln(n/\beta)\sigma^{2})\cdot\frac{L^{2}+L^{4}\mu^{2}+L^{3}\mu}{\lambda}\right).$
(13)

(11) follows from the strong convexity of $J_{t}^{\sf priv}$ and the fact that
that $\theta_{t+1}$ is the minimizer of $J_{t}^{\sf priv}$. (12) follows from
the bounds on $\left\|\boldsymbol{b}_{t}\right\|_{2}$,
$\left\|B_{t}\right\|_{2}$, and (10). We now use Theorem 2 from [63] to bound
$\mathbb{E}_{(\mathbf{x},y)\sim\mathcal{D}}\left[(y-\langle\mathbf{x},\theta_{t+1}\rangle)^{2}+\frac{\lambda}{2}\left\|\theta_{t+1}\right\|_{2}^{2}\right]-\mathbb{E}_{(\mathbf{x},y)\sim\mathcal{D}}\left[(y-\langle\mathbf{x},\theta^{*}\rangle)^{2}+\frac{\lambda}{2}\left\|\theta^{*}\right\|_{2}^{2}\right]$
for any $\theta^{*}\in\mathcal{C}$.

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

$\displaystyle\mathbb{E}_{(\mathbf{x},y)\sim\tau}\left[(y-\langle\mathbf{x},\theta_{t+1}\rangle)^{2}+\frac{\lambda}{2}\left\|\theta_{t+1}\right\|_{2}^{2}\right]-\mathbb{E}_{(\mathbf{x},y)\sim\tau}\left[(y-\langle\mathbf{x},\theta^{*}\rangle)^{2}+\frac{\lambda}{2}\left\|\theta^{*}\right\|_{2}^{2}\right]$
$\displaystyle\leq\frac{2}{t}\cdot\mathbb{E}\left[J_{t}^{\sf
np}\left(\theta_{t+1}\right)-J_{t}^{\sf
np}\left(\widetilde{\theta}_{t+1}\right)\right]+O\left(\frac{L^{4}\mu^{2}}{\lambda}\right)$
$\displaystyle=O\left((p\ln(n)\ln(n/\beta))\sigma^{2})\cdot\frac{L^{2}+L^{4}\mu^{2}+L^{3}\mu}{\lambda
t}+\frac{L^{4}\mu^{2}}{\lambda}\right).$ (14)

(14) immediately implies the following:

$\displaystyle\mathbb{E}_{D}\left[R_{D}(\mathcal{A}_{\textsf{FTRL-
LS}};\theta^{*})\right]$
$\displaystyle=O\left(\left(p\ln^{2}(n)\ln(n/\beta)\sigma^{2}\right)\frac{L^{2}+L^{4}\mu^{2}+L^{3}\mu}{\lambda
n}+\frac{L^{4}\mu^{2}}{\lambda}+\frac{\lambda\ln(n)}{n}\cdot\left\|\theta^{*}\right\|_{2}^{2}\right).$
(15)

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

######  Theorem C.5 (Corollary to Theorem 5.1 and [63]).

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}$),

$\mathbb{E}_{D}\left[{\sf
PopRisk}(\theta^{\texttt{priv}}\,)\,\right]=L\mu\cdot
O\left(\sqrt{\frac{{\ln(1/\beta)}}{n}}+\sqrt{\frac{p^{1/2}\ln^{2}(1/\delta)\ln(1/\beta)}{\varepsilon
n}}\right).$

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
888https://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. .

###  D.1 DP-FTRL with Tree-Restarts (DP-FTRL-TreeRestart)

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 [53].

######  Theorem D.1 (Privacy guarantee for DP-FTRL-TreeRestart).

If $\left\|\nabla_{\theta}\ell(\theta;d)\right\|_{2}\leq L$ for all
$d\in\mathcal{D}$ and $\theta\in\mathcal{C}$, then DP-FTRL (Algorithm 1) with
Tree Restart (DP-FTRL-TreeRestart) for $E$ epochs satisfies
$\left(\alpha,\frac{\alpha
EL^{2}\lceil\lg(n+1)\rceil}{2\sigma^{2}}\right)$-RDP. Correspondingly, by
setting
$\sigma=\frac{\sqrt{EL^{2}\lceil\lg(n+1)\rceil\ln(1/\delta)}}{\varepsilon}$
one can satisfy $(\varepsilon,\delta)$-differential privacy guarantee, as long
as $\varepsilon\leq 2\ln(1/\delta)$.

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.

Algorithm 3 Privacy accounting for DP-FTRL-NoTreeRestart

0: Binary tree for the DP-FTRL algorithm: $\mathcal{T}$, minimum separation:
$\xi$, maximum contributions: $E$.

1: $\rho\leftarrow 0$

2: for each level $\gamma\in\mathcal{T}$ do

3: $k_{\gamma}\leftarrow$ # of nodes in level $\gamma$,
$\mu_{\gamma}\leftarrow\left\lceil\frac{2^{{\sf
height}(\gamma)}}{\xi+1}\right\rceil$, and
$k^{*}_{\gamma}\leftarrow\min\left\\{k,\left\lfloor\frac{E}{\mu_{\gamma}}\right\rfloor\right\\}$.

4: $\zeta_{\gamma}\leftarrow
k^{*}_{\gamma}\cdot\mu_{\gamma}^{2}+\mathbb{1}_{k^{*}_{\gamma}<k}\left(E-k^{*}_{\gamma}\cdot\mu_{\gamma}\right)^{2}$

5: $\rho\leftarrow\rho+\zeta_{\gamma}$.

6: end for

7: return $\rho$.

######  Theorem D.2.

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.

###### Proof.

The proof proceeds by bounding the RDP cost for the release of all the noised
node values at a given level $\gamma\in\mathcal{T}$. By slight abuse of
notation, we treat $\gamma$ as the set of nodes at that level,
$\gamma=\left\\{z_{1},\ldots,z_{k}\right\\}$. For any node $z\in\gamma$, let
$\mathbf{S}_{z}\leftarrow\sum\limits_{i\in\mathcal{N}_{z}}\nabla_{i}$, where
$\mathcal{N}_{z}$ is the set of leaf nodes in the subtree rooted at $z$ and
$\nabla_{i}$ is the gradient of a single training example. We will analyze the
RDP privacy cost of the query
$\mathbf{S}_{\gamma}=\langle\mathbf{S}_{z_{1}},\dots,\mathbf{S}_{z_{k}}\rangle$
with the Gaussian mechanism. The key is to bound the $\ell_{2}$ sensitivity of
$\mathbf{S}_{\gamma}$ and compare that to the noise added.

Fix an example $x$ in the training data set and let $c=\langle
c_{1},\ldots,c_{k}\rangle$ be the number of contributions of $x$ to each of
the nodes $z_{1},\dots,z_{k}$. We observe immediately that the $\ell_{2}$
sensitivity of $\mathbf{S}_{\gamma}$ is simply $\|Lc\|_{2}$, where $L$ is the
$\ell_{2}$-Lipschitz constant of the individual loss functions, so it is
sufficient to bound $\|c\|^{2}_{2}$. We note $c$ is bound by two constraints:

  * •

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}$:

$\displaystyle\max\limits_{c_{1},\ldots,c_{k}}\sum_{i=1}^{k}c_{i}^{2},$
$\displaystyle\text{s.t.}\sum\limits_{i=1}^{k}c_{i}\leq E,$
$\displaystyle\forall i\in[k],0\leq c_{i}\leq\mu_{\gamma}$ (16)

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)$.

Thus, $\|c\|^{2}_{2}\leq\zeta$, and the $\ell_{2}$ sensitivity of
$\mathbf{S}_{\gamma}$ is bounded by $L\sqrt{\zeta}$. Recall from Section B.1
we add noise $\mathcal{N}(0,L^{2}\sigma^{2})$ to each node, and hence to
$\mathbf{S}_{\gamma}$. From these to facts and the RDP properties of Gaussian
mechanism [53, Proposition 7], we have that for a given order $\alpha$,

$\frac{\alpha L^{2}\zeta}{2L^{2}\sigma^{2}}=\frac{\alpha\zeta}{2\sigma^{2}}$

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$.

$\displaystyle\zeta\left(\texttt{contrib},\texttt{start},\texttt{end},\texttt{size}\right)$
$\displaystyle=\texttt{contrib}^{2}\cdot\mathbb{I}\left[\texttt{size}\
\text{is a power of}\ 2\right]+$
$\displaystyle\max\limits_{\begin{subarray}{c}i\in\\{0,\ldots,\texttt{contrib}\\}\\\
j\in\\{0,\ldots,\xi\\}\end{subarray}}\left\\{\zeta\left(\texttt{contrib}-i,\texttt{start},j,k\right)+\zeta\left(i,j,\texttt{end},\texttt{size}-k\right)\right\\}$
$\displaystyle\text{where}\ k\ \text{largest power of}\ 2<\texttt{size}.$ (17)

The base cases is:

$\displaystyle\text{\bf if}\
\texttt{start}+\texttt{contrib}\cdot(\xi+1)>\texttt{size}+\texttt{end},\ {\bf
then}\ \zeta(\cdot,\texttt{start},\texttt{end},\texttt{size})=-\infty$
$\displaystyle\zeta(0,\cdot,\cdot,\cdot)=0$
$\displaystyle\zeta(1,\cdot,\cdot,1)=1$ (18)

######  Theorem D.3.

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.

###### Proof.

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 $0$ 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. ∎

####  D.2.1 Analysis for a Simpler Case: DP-FTRL-NoTreeRestart with Given Data
Order

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.

Algorithm 4 Privacy accounting for DP-FTRL-NoTreeRestart with given data order

0: A given data order $[s_{1},\dots,s_{m}]$ where $s_{i}\in[n]$ with $n$ being
the number of samples.

1: $\rho_{i}\leftarrow 0$ for $i\in[n]$ {$\rho_{i}$ will record the squared
sensitivity with respect to sample $i$}

2: Construct the leaf layer of the tree
$\mathcal{L}_{1}=[(s_{1}),\dots,(s_{m})]$

3: $\rho_{s_{i}}\leftarrow 1$ for $s_{i}=s_{1},\dots s_{m}$

4: for $\gamma=2,\dots,\left\lfloor\log_{2}(m)\right\rfloor+1$ do

5: Construct $\mathcal{L}_{\gamma}$ by concatenating every two consecutive
nodes in $\mathcal{L}_{\gamma-1}$, ignoring the rest if
$|\mathcal{L}_{\gamma-1}|$ is not even

6: for every node in $\mathcal{L}_{\gamma}$ do

7: for $i=1,\dots,n$ do

8: $\rho_{i}\leftarrow\rho_{i}+c^{2}$, where $c$ is the count of $i$ in the
node

9: end for

10: end for

11: end for

12: return $\max\limits_{i\in[n]}\rho_{i}$.

Consider a simple example where we have four samples indexed with $1,\dots,4$,
and use them in the order of $[1,2,3,1,4]$ 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 $0$ 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.

####  D.3.1 A Binary Tree Completion Trick and the Privacy Analysis

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 $0$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$ $0$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 [34]. 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 $0$ 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
$[1,2,3,1,4]$, 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)

###  E.1 Additional Details on Model Architectures

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 [60].

Table 2: Model architectures for all experiments.

(a) Model architecture for MNIST and EMNIST. Layer | Parameters
---|---
Convolution | 16 filters of $8\times 8$, strides 2
Convolution | 32 filters of $4\times 4$, strides 2
Fully connected |  $32$ units
Softmax | -

(b) Model architecture for CIFAR-10. Layer | Parameters
---|---
Convolution $\times 2$ | 32 filters of $3\times 3$, strides 1
Max-Pooling |  $2\times 2$, stride 2
Convolution $\times 2$ | 64 filters of $3\times 3$, strides 1
Max-Pooling |  $2\times 2$, stride 2
Convolution $\times 2$ | 128 filters of $3\times 3$, strides 1
Max-Pooling |  $2\times 2$, stride 2
Fully connected |  $128$ units
Softmax | -

(c) Model architecture for StackOverflow. [60] Layer | Output Shape | Parameters
---|---|---
Input | 20 | 0
Embedding | (20, 96) | 960384
LSTM | (20,670) | 2055560
Dense | (20, 96) | 64416
Dense | (20, 10004) | 970388
Softmax | - | -

###  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.

(a) MNIST. $5$ epochs.

(b) CIFAR-10. $5$ epochs.

(c) EMNIST. $5$ epochs.

(d) MNIST, $20$ / $80$ epochs for smaller / larger batch.

(e) CIFAR-10, $100$ / $400$ epochs for smaller / larger batch.

(f) EMNIST, $50$ / $200$ epochs for smaller / larger batch.

Figure 3:  Effect of momentum in DP-SGD. Final test accuracy vs. privacy
(example-level $\varepsilon$) for various noise multipliers. For smaller
number of epochs (top row), DP-SGDM is better for CIFAR-10; for larger number
of epochs (bottom row), DP-SGD is better for CIFAR-10. In the other cases, the
two variants are similar.

(a) MNIST. $5$ epochs.

(b) CIFAR-10. $5$ epochs.

(c) EMNIST. $5$ epochs.

(d) CIFAR-10. $100$ epochs.

(e) EMNIST. $50$ epochs.

Figure 4: Effect of momentum on DP-FTRL. Final test accuracy vs. privacy
(example-level $\varepsilon$) for various noise multipliers. DP-FTRLM
outperforms DP-FTRL.

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 999The accuracy for
StackOverflow next word prediction task excludes the end of sequence symbol
and the out of vocabulary symbol following [60]. 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.

Server Optimizer | Epsilon | Accuracy | Hyperparameters
---|---|---|---
Validation | Test | ServerLR | ClientLR | Clip
DP-SGD | $\infty$ | 19.62 $\pm$ .12 | 20.99 $\pm$ .11 | $3$ | $0.5$ | $1$
DP-SGDM | 23.87 $\pm$ .22 | 24.89 $\pm$ .27 | $3$ | $0.5$ | $1$
DP-FTRL | 19.95 $\pm$ .05 | 21.12 $\pm$ .14 | $3$ | $0.5$ | $1$
DP-FTRLM | 23.89 $\pm$ .03 | 25.15 $\pm$ .07 | $3$ | $0.5$ | $1$
DP-SGD | 7.51 | 16.83 $\pm$ .05 | 18.25 $\pm$ .05 | $3$ | $0.5$ | $0.3$
DP-SGDM | 16.92 $\pm$ .03 | 18.27 $\pm$ .04 | $0.1$ | $0.5$ | $1$
DP-FTRL | 7.83 | 15.04 $\pm$ .16 | 15.46 $\pm$ .39 | $3$ | $0.5$ | $0.3$
DP-FTRLM | 17.78 $\pm$ .08 | 18.86 $\pm$ .15 | $1$ | $0.5$ | $0.3$
Table 3: Validation and test accuracy for the StackOverflow next word
prediction task. Each experiment is run five times to calculate the mean and
standard deviation. Vanilla tree aggregation [22] is used in DP-FTRLM. The
momentum variant DP-FTRLM performs better than DP-FTRL.

(a) Privacy epsilon $\infty$

(b) Privacy epsilon $\sim 8.5$

Figure 5: Training curves show validation accuracy of StackOverflow. The curve
of the best validation accuracy out of the five runs is presented. Vanilla
tree aggregation [22] is used in DP-FTRL-vanilla and DP-FTRLM-vanilla. The
momentum variant converges faster and performs better.

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”) [34] and the original version (“FTRLM-vanilla”) [22] 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.

Figure 6: Comparison of two variants of DP-FTRL with efficient tree
aggregation (“DP-FTRLM”) and vanilla tree aggregation (“DP-FTRLM-vanilla”).

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 [34]. The noise multipliers are used to generate Figure 7(c).

(a)

(b)

(c)

Figure 7: Comparison of two variants of DP-FTRL with efficient tree
aggregation [34] and vanilla tree aggregation [22] on StackOverflow for (a)
test accuracy under different privacy epsilon; (b) test accuracy with various
noise multipliers; (c) relationship between user-level privacy $\varepsilon$
(when $\delta\approx\nicefrac{{1}}{{\text{population}}}$) and computation cost
(report goal) for two fixed accuracy targets (see legend).

###  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.

(a) MNIST

(b) CIFAR-10

(c) EMNIST

Figure 8: The effect of the tree completion trick. Settings are the same as
those in Figure 1.

##  Appendix F Omitted Details for Experiments in Section 7.2

###  F.1 Details of Hyperparameter Tuning

##### Image classification experiments

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 [56].

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.

##### StackOverflow experiments

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 [60]. The one layer LSTM described in [60] 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