# The Trade-Offs of Private Prediction

Laurens van der Maaten∗ Awni Hannun
Facebook AI Research, New York
<EMAIL_ADDRESS>
Both authors contributed equally to the paper.

###### Abstract

Machine learning models leak information about their training data every time
they reveal a prediction. This is problematic when the training data needs to
remain private. Private prediction methods limit how much information about
the training data is leaked by each prediction. Private prediction can also be
achieved using models that are trained by private training methods. In private
prediction, both private training and private prediction methods exhibit
trade-offs between privacy, privacy failure probability, amount of training
data, and inference budget. Although these trade-offs are theoretically well-
understood, they have hardly been studied empirically. This paper presents the
first empirical study into the trade-offs of private prediction. Our study
sheds light on which methods are best suited for which learning setting.
Perhaps surprisingly, we find private training methods outperform private
prediction methods in a wide range of private prediction settings.

##  1 Introduction

Machine learning models are frequently trained on data that needs to remain
private, even though the predictions produced by those models are revealed to
the outside world. For example, a hotel recommendation model may be trained on
hotel reservation data that its users should not have access to. Unless proper
care is taken, a user of a hotel recommendation service may be able to extract
hotel reservation data of other users from the recommendations they receive,
which would result in a privacy violation [7, 16, 37, 38, 44]. Such privacy
violations may happen even when users do not have direct access to the model
parameters but only to model predictions: several studies have demonstrated
that it is possible to reconstruct model parameters from a series of model
predictions [6, 29, 39].

The goal of _private prediction_ is to prevent such privacy violations by
limiting the amount of information about the training data that can be
obtained from a series of model predictions [11]. Private prediction methods
[4, 9, 11, 32] perturb the predictions of non-private models to obfuscate any
information that can be inferred about the data used to trained those models.
_Private training_ methods [1, 3, 8, 23, 31, 42, 40] can be used to obtain
private predictions as well. In particular, private training guarantees that
model parameters reveal little information about the training data. As a
result, the predictions of privately trained models do not leak information
about the training data either.

Both private prediction and private training methods exhibit a range of trade-
offs when they are used in a private prediction setting. Specifically, there
exist trade-offs between the accuracy of the predictions, the privacy level
that can be guaranteed, the probability of a privacy failure, the number of
predictions that is revealed publicly (_i.e._ , the inference budget), and the
amount of training data. While these trade-offs are theoretically well
understood, little is known about them empirically. Prior empirical studies
evaluate only private training methods and do not consider the private
prediction setting [20, 21]. This paper performs an empirical study into the
trade-offs of private prediction. We aim to provide guidance to practitioners
on which private prediction methods are most suitable for a given learning
setting. Perhaps surprisingly, we find that private training methods offer a
better privacy-accuracy trade-off than private prediction methods in many
practical learning settings.

##  2 Problem Statement

Consider a private machine learning model $\phi(\mathbf{x};\theta)$ with
parameters $\theta$ that given a $D$-dimensional input vector,
$\mathbf{x}\in\mathbb{R}^{D}$, produces a probability vector over $C$ classes
$\mathbf{y}\in\Delta^{C}$. Herein, $\Delta^{C}$ represents the
$(C\\!-\\!1)$-dimensional probability simplex. The parameters $\theta$ were
obtained by fitting the model on a training set of $N$ labeled examples,
$\mathcal{D}=\\{(\mathbf{x}_{1},\mathbf{y}_{1}),\dots,(\mathbf{x}_{N},\mathbf{y}_{N})\\}$,
that needs to remain private.

We consider the common scenario in which machine learning model $\phi(\cdot)$
is provided as a service to other parties by the model owner. Specifically,
someone provides a vector $\hat{\mathbf{x}}$ to the owner of the model, who
uses it to compute $\hat{\mathbf{y}}=\phi(\hat{\mathbf{x}};\theta)$ and
publicly reveals the prediction $\hat{\mathbf{y}}$. From the perspective of
the model owner, there is an inherent risk here that whoever observes
$(\hat{\mathbf{x}},\hat{\mathbf{y}})$ obtains information about the private
training set $\mathcal{D}$ through the model query: prediction
$\hat{\mathbf{y}}$ carries information about parameters $\theta$ that, in
turn, carries information about the private training set $\mathcal{D}$.

The model owner is interested in limiting the amount of information that
others can learn about the private training set $\mathcal{D}$ via an
_inference budget_ of $B$ queries,
$\mathcal{Q}=\\{\hat{\mathbf{x}}_{1},\dots,\hat{\mathbf{x}}_{B}\\}$, to model
$\phi(\cdot)$. Specifically, the model owner aims to provide an
$(\epsilon,\delta)$-differential privacy guarantee [12] on the information
that is leaked about $\mathcal{D}$ by releasing $B$ predictions:

$Pr\left[\phi\left(\hat{\mathbf{x}}_{b};\theta(\mathcal{D})\right)\subseteq\mathcal{Y}_{b}:b=1,\ldots,B\right]\leq
e^{\epsilon}Pr\left[\phi\left(\hat{\mathbf{x}}_{b};\theta(\mathcal{D}^{\prime})\right)\subseteq\mathcal{Y}_{b}:b=1,\ldots,B\right]+\delta,$
(1)

for $\epsilon\geq 0$ and $\delta\geq 0$,
$\forall\mathcal{Y}_{b}\subseteq\Delta^{C}$, $\forall\mathcal{Q}$ with
$|\mathcal{Q}|=B$, and for all datasets $\mathcal{D}$ and
$\mathcal{D}^{\prime}$ that differ in only one training example. Herein, we
adopt the short-hand notation $\theta(\mathcal{D})$ to indicate the parameters
$\theta$ that were obtained by training the model on training set
$\mathcal{D}$. The model owner can limit the amount of information that the
predictions leak about training set $\mathcal{D}$ in two primary ways:

  1. 1.

The model owner can perform private training [4, 9, 11, 32] of model
$\phi(\cdot)$. Differentially private training guarantees that the model
parameters $\theta$ reveal little information about training set
$\mathcal{D}$. Because differential privacy is closed under post-processing
[10], the model owner can reveal $B=\infty$ predictions (or the model
parameters) and still maintain the property in Equation 1.

  2. 2.

The model owner can perform private prediction [1, 3, 8, 23, 31, 42, 40] using
a model $\phi^{\prime}(\cdot)$ that is not itself differentially private.
Private prediction methods construct $\phi(\cdot)$ from $\phi^{\prime}(\cdot)$
in a way that limits the amount of information that $\phi(\cdot)$ reveals
about $\mathcal{D}$ through $B$ predictions.

##  3 Methods

This study performs an empirical analysis of both private training and private
prediction methods. We adopt a regularized empirical risk minimization
framework in which we minimize:

$J(\theta;\mathcal{D})=\frac{1}{N}\sum_{n=1}^{N}\ell(\phi^{\prime}(\mathbf{x}_{n};\theta),\mathbf{y}_{n})+\lambda
R(\theta)$ (2)

with respect to $\theta$, where $\ell(\cdot)$ is a loss function, $R(\cdot)$
is a regularizer, and $\lambda\geq 0$ is a regularization parameter. Some of
the private prediction methods that we study make one or more of the following
assumptions to obtain the privacy guarantee in Equation 1:

  1. 1.

The loss function $\ell(\cdot)$ is strictly convex, continuous, and
differentiable everywhere.

  2. 2.

The regularizer $R(\theta)$ is $1$-strongly convex, continuous, and
differentiable everywhere w.r.t. $\theta$.

  3. 3.

The non-randomized model $\phi^{\prime}(\cdot)$ is linear in $\mathbf{x}$,
that is, $\phi^{\prime}(\mathbf{x};\theta)=\theta^{\top}\mathbf{x}$.

  4. 4.

The loss function $\ell(\cdot)$ is Lipschitz with a constant $K$, that is,
$\|\nabla l\|_{2}\leq K$.

  5. 5.

The inputs are contained in the unit $L_{2}$ ball, that is,
$\|\mathbf{x}\|_{2}\leq 1$ for all $\mathbf{x}$.

Detailed algorithms of all methods and proofs of all theorems are presented in
the appendix.

###  3.1 Private Training

We consider three private training methods in this study: (1) the model
sensitivity method, (2) loss perturbation, and (3) differentially private
stochastic gradient descent (SGD).

Model sensitivity. A simple private training method is for the model owner to
add noise to the model parameters in order to hide information about the
training data that is captured in those parameters. The model sensitivity
method [8] constructs differentially private parameters $\theta$ by adding
noise to the minimizer of $J(\cdot)$. Specifically, we extend [8] to multi-
class linear models with $\theta\in\mathbb{R}^{D\times C}$ and sample the
noise matrix $\mathbf{B}$ from $p(\mathbf{B})\propto
e^{-\beta\|\mathbf{B}\|_{F}}$. To satisfy the property in Equation 1, we
choose $\beta=\frac{N\lambda\epsilon}{2K}$. In practice, we adopt the multi-
class logistic loss which has a Lipschitz constant $K=\sqrt{2}$.

######  Theorem 1.

Given assumptions 1, 2, 3, 4, and 5, the model sensitivity method is
$(\epsilon,0)$-differentially private.

By changing $p(\mathbf{B})$ to a zero-mean isotropic Gaussian distribution
with standard deviation $\sigma=\frac{2K\alpha}{N\lambda\sqrt{2\epsilon}}$ for
an $\alpha$ that depends on $\epsilon$ and $\delta$, we can also obtain
$(\epsilon,\delta)$-differentially private models for $\delta>0$ [2].

######  Theorem 2.

Given assumptions 1, 2, 3, 4, and 5, the Gaussian model sensitivity method is
$(\epsilon,\delta)$-differentially private for $\delta\in(0,1)$.

Loss perturbation. Rather than perturbing the learned parameters after
training, the model owner can instead randomly perturb the loss function that
is minimized during training to obtain a differentially private model [8, 23].
We extend the loss perturbation method of [8, 23] to multi-class
classification by minimizing the following randomly perturbed loss function:

$J^{\prime}(\theta;\mathcal{D})=\frac{1}{N}\sum_{n=1}^{N}\ell(\phi^{\prime}(\mathbf{x}_{n};\theta),\mathbf{y}_{n})+\frac{\lambda}{N}R(\theta)+\frac{1}{N}\text{tr}(\mathbf{B}^{\top}\theta)+\frac{1}{2}\rho\lVert\theta\rVert_{F}^{2},$
(3)

where $\text{tr}(\cdot)$ represents the trace of a square matrix. The noise
matrix $\mathbf{B}$ is sampled from $p(\mathbf{B})\propto
e^{-\beta\|\mathbf{B}\|_{F}}$. The scale parameter of the noise distribution
$\beta=\frac{\epsilon}{2K}$, and the parameter $\rho$ that governs the
additional $L_{2}$ regularization is set such that
$\rho\geq\frac{2LC}{\epsilon}$. The constant $L$ is an upper bound on the
eigenvalues of the Hessian of $\ell(\cdot)$, that is,
$\lambda_{\max}(\nabla^{2}\ell(\theta^{\top}\mathbf{x},\mathbf{y}))\leq L$ for
all $\theta,\mathbf{x}$ and $\mathbf{y}$. We use a multi-class logistic loss,
which has a Hessian with eigenvalues bounded by $L=\frac{1}{2}$ (see
appendix).

######  Theorem 3.

Given a convex loss function $\ell(\cdot)$, a convex regularizer $R(\cdot)$
with continuous Hessians, assumptions 3, 4, and 5, and assuming that
$\lambda_{\max}(\nabla^{2}\ell)\leq L$, the loss perturbation method is
$(\epsilon,0)$-differentially private.

By changing noise distribution $p(\mathbf{B})$ into a zero-mean isotropic
Gaussian distribution with standard deviation
$\sigma=\frac{K}{\epsilon}\sqrt{8\ln(2/\delta)+4\epsilon}$, we can also obtain
$(\epsilon,\delta)$-differential privacy for $\delta>0$ [23].

######  Theorem 4.

Given a convex loss $\ell(\cdot)$, a convex regularizer $R(\cdot)$ with
continuous Hessians, assumptions 3, 4, and 5, and assuming that
$\lambda_{\max}(\nabla^{2}\ell)\leq L$, the Gaussian loss perturbation method
is $(\epsilon,\delta)$-differentially private.

(a) For privacy failure probability $\delta=0$. (b) For privacy failure
probability $\delta=10^{-5}$.

Figure 1: Test accuracy on MNIST dataset as a function of privacy loss
$\epsilon$ for inference budget $B=100$. In 1b, $\epsilon$ ranges between $0$
and $1$ because of limitations in some methods when $\delta>0$.

Differentially private SGD (DP-SGD). Rather than _post hoc_ perturbation of
the final model parameters or _pre hoc_ perturbation of the loss, the DP-SGD
method limits the influence of individual examples in parameter updates [1].
DP-SGD draws a batch $\mathcal{B}$ of training examples uniformly at random
and computes the gradient $\mathbf{g}_{n}=\frac{\partial
J\left(\theta;\\{(\mathbf{x}_{n},\mathbf{y}_{n})\\}\right)}{\partial\theta}$
for each example in the batch. It clips the resulting per-example gradients to
have a norm bound of $\nu$, aggregates the clipped gradients over the batch,
and adds Gaussian noise to obtain a private, approximate parameter gradient
$\tilde{\mathbf{g}}$:

$\tilde{\mathbf{g}}=\frac{1}{|\mathcal{B}|}\left[\sum_{n\in\\{1,\dots,|\mathcal{B}|\\}}\left(\frac{\mathbf{g}_{n}}{\max\left(1,\frac{\lVert\mathbf{g}_{n}\rVert_{2}}{\nu}\right)}\\\
\right)+\mathcal{N}(\mathbf{0},\sigma^{2}\nu^{2}\mathbf{I})\right],$ (4)

where $\sigma^{2}\nu^{2}$ is the variance of the Gaussian, $\mathbf{0}$ is an
appropriately sized vector of zeros, and $\mathbf{I}$ an appropriately sized
identity matrix. The resulting $\tilde{\mathbf{g}}$ is used to perform the
parameter update. Akin to the model sensitivity method, choosing
$\sigma=\frac{1}{\epsilon}\sqrt{2\ln(1.25/\delta)}$ makes each
$\tilde{\mathbf{g}}$ vector $(\epsilon,\delta)$-differentially private with
respect to the examples in batch $\mathcal{B}$. The privacy amplification
theorem [22] states that $\tilde{\mathbf{g}}$ is
$(q\epsilon,q\delta)$-differentially private with respect to examples from
$\mathcal{D}$, with $q=\nicefrac{{|\mathcal{B}|}}{{N}}$.

Privacy guarantees on the parameters learnt by DP-SGD after $M$ parameter
updates can be obtained via a “moments accountant”. We use the moments
accountant of [31], which uses an analysis based on Rényi differential privacy
[30] to compute the noise scale $\sigma$ required for a given privacy loss
$\epsilon$, privacy failure probability $\delta$, number of parameter updates
$M$, batch size $|\mathcal{B}|$, and training set size $N$.

###  3.2 Private Prediction

We consider two private prediction methods in this study: (1) the prediction
sensitivity method and (2) the subsample-and-aggregate method.

Prediction sensitivity. The prediction sensitivity method adds noise to the
logits, $\hat{\mathbf{l}}=\phi^{\prime}(\hat{\mathbf{x}};\theta)$, predicted
by the model. Specifically, it returns $\hat{\mathbf{l}}+\mathbf{b}$, where
the noise vector $\mathbf{b}\in\mathbb{R}^{C}$ is sampled from
$p(\mathbf{b})\propto e^{-\beta\|\mathbf{b}\|_{2}}$. Given an inference budget
$B$, we use standard composition [12] and set
$\beta=\frac{N\lambda\epsilon}{2KB}$.

######  Theorem 5.

Given assumptions 1, 2, 3, 4, and 5, the prediction sensitivity method is
$(\epsilon,0)$-differentially private.

We can obtain $(\epsilon,\delta)$-differentially private predictions for
$\delta>0$ by sampling $\mathbf{b}$ from a zero-mean isotropic Gaussian
distribution [2]. Assuming $\delta>0$ also allows the use of the advanced
composition theorem [14, 15]. We set the standard deviation to
$\sigma=\frac{2K\alpha^{*}}{N\lambda\epsilon^{*}}$, where $\alpha^{*}$ depends
on per-sample privacy values $\epsilon^{*}$ and $\delta^{*}$ that are found
using a search algorithm (see appendix for details).

######  Theorem 6.

Given assumptions 1, 2, 3, 4, and 5, the Gaussian prediction sensitivity
method is $(\epsilon,\delta)$-differentially private for $\delta\in(0,1)$.

When the budget $B$ is small, the $\sigma$ obtained with standard composition
can be smaller than that obtained with advanced composition. In experiments,
we always choose the smaller $\sigma$ of the two.

(a) For privacy failure probability $\delta=0$. (b) For privacy failure
probability $\delta=10^{-5}$.

Figure 2: Test accuracy on MNIST dataset as function of inference budget $B$
for privacy loss $\epsilon=1$.

Subsample-and-aggregate. Subsample-and-aggregate methods train $T$ models on
$T$ subsets of $\mathcal{D}$, and perform differentially private aggregation
of the predictions produced by the resulting models [4, 11, 32, 33]. We focus
on the method of Dwork & Feldman [11] in this study. That technique: (1)
partitions the training dataset $\mathcal{D}$ into $T$ disjoint subsets of
size $\lfloor\nicefrac{{|\mathcal{D}|}}{{T}}\rfloor$, (2) trains $T$
classifiers
$\\{\phi^{\prime}_{1}(\cdot;\theta_{1}),\dots,\phi^{\prime}_{T}(\cdot;\theta_{T})\\}$
on these subsets where $\phi^{\prime}_{t}(\cdot)$ outputs a one-hot vector of
size $C$, and (3) applies a soft majority voting across the $T$ classifiers at
inference time. Hence, it predicts label $\hat{\mathbf{y}}$ for input
$\hat{\mathbf{x}}$ with probability proportional to
$\exp(\beta\cdot|\\{t:t\in\\{1,\dots,T\\},\phi^{\prime}_{t}(\hat{\mathbf{x}};\theta_{t})=\hat{\mathbf{y}}\\}|)$.
The parameter $\beta$ acts as an “inverse temperature” in the voting: privacy
increases but accuracy decreases as $\beta$ goes to zero. Using the standard
compositional properties of differential privacy [12], this procedure achieves
$(\epsilon,0)$-differential privacy with an inference budget of $B$ by setting
$\beta=\epsilon/B$.

######  Theorem 7.

The subsample-and-aggregate method with $\beta=\epsilon/B$ is
$(\epsilon,0)$-differentially private.

If we allow $\delta>0$, we can use the advanced composition theorem [14, 15]
in subsample-and-aggregate to achieve $(\epsilon,\delta)$-differential privacy
with noise scale $\beta$ inversely proportional to the square of $B$.

######  Theorem 8.

The subsample-and-aggregate method with
$\beta=\max(\beta^{\prime},\beta^{\prime\prime})$, where
$\beta^{\prime}=\epsilon/B$ and
$\beta^{\prime\prime}=\sqrt{2/B}\left(\sqrt{\ln(1/\delta)+\epsilon}-\sqrt{\ln(1/\delta)}\right)$,
is $(\epsilon,\delta)$-differentially private.

Figure 3: Test accuracy on MNIST dataset as a function of privacy failure
probability, $\delta$, for privacy $\epsilon=1$ and inference budget $B=100$.

Figure 4: Test accuracy on MNIST-1M dataset as a function of training set
size, $N$, for privacy $(\epsilon,\delta)=(1,0)$ and inference budget $B=100$.

##  4 Experiments

We evaluate the five private prediction methods in experiments with linear
models on the MNIST [26] dataset (4.2) and convolutional networks on the
CIFAR-10 [24] dataset (4.3). Code reproducing our experiments is available
from https://github.com/facebookresearch/private_prediction.

###  4.1 Experimental Setup

In all experiments, we choose the loss function $\ell$ to be the multi-class
logistic loss. When training linear models, we minimize the loss using L-BFGS
[45] with a line search that checks the Wolfe conditions [41] for all methods
except the DP-SGD method. We trained all models using $L_{2}$-regularization
except when using the DP-SGD or subsample-and-aggregate methods. (We note that
these two methods have implicit regularization via gradient noise and
ensembling, respectively.) We selected regularization parameter $\lambda$ via
cross-validation in a range between $10^{-5}$ and $5\cdot 10^{-1}$. We choose
the clip value $\nu$ in DP-SGD by cross-validating over a range from $5\cdot
10^{-4}$ to $5\cdot 10^{-1}$. For simplicity, we ignore the privacy leakage
due to cross-validation and hyperparameter tuning in our analysis. Unless
noted otherwise, we perform subsample-and-aggregate with $T=256$ models.

To evaluate the quality of our models, we measure their classification
accuracy on the test set. Because private prediction methods are inherently
noisy, we repeat every experiment $100$ times using the same train-test split.
We report the average accuracy corresponding standard deviation in all result
plots.

###  4.2 Results: Linear Models

We first evaluate the performance of linear models on the MNIST handwritten
digit dataset [26].

Accuracy as a function of privacy loss. Figure 1 displays the accuracy of the
models on the test set (higher is better) as a function of the privacy loss
$\epsilon$ (lower values imply more privacy) for an inference budget of
$B=100$. The results are presented for two values of the privacy failure
probability: $\delta=0$ in Figure 1a and $\delta=10^{-5}$ in Figure 1b (DP-SGD
does not support $\delta=0$). Recall that most methods support both $\delta=0$
and $\delta>0$ by choosing different noise distributions or a different
privacy analysis.

Figure 1 shows that the subsample-and-aggregate method outperforms the other
methods for most values of $\epsilon$ in the $\delta=0$ regime, but is less
competitive when $\delta=10^{-5}$ (higher probability of privacy failure).
Loss perturbation performs best for small values of $\epsilon$ (much privacy)
when $\delta=0$. Model sensitivity underperforms the other two methods when
$\delta=0$ but is slightly more competitive when $\delta=10^{-5}$ due to the
use of a Gaussian noise distribution. DP-SGD outperforms all other methods
when $\delta=10^{-5}$. Prediction sensitivity performs poorly across the
board.

(a) As a function of number of dimensions, $D$. (b) As a function of number of
classes, $C$.

Figure 5: Test accuracy on MNIST dataset for privacy $(\epsilon,\delta)=(1,0)$
and inference budget $B=100$.

Accuracy as a function of inference budget. Figure 1 shows experimental
results for a particular choice of inference budget ($B=100$). In private
prediction methods, the amount of privacy provided changes when this budget
changes. To investigate this trade-off, Figure 2 displays accuracy as a
function of the inference budget, $B$, for a privacy loss setting of
$\epsilon=1$. As before, we show results for privacy failure probability
$\delta=0$ (Figure 2a) and $\delta=10^{-5}$ (Figure 2b). In the plots, private
training methods are horizontal lines because the amount of information they
leak does not depend on $B$.

The results show that the subsample-and-aggregate method outperforms other
private prediction methods in the low-budget regime when $\delta=0$. However,
this advantage vanishes when the number of inferences that needs to be
supported, $B$, grows. Specifically, loss perturbation outperforms subsample-
and-aggregate at $B\gtrapprox 80$ predictions. The advantage also disappears
when a small privacy failure probability is allowed. For $\delta=10^{-5}$, two
private training methods (loss perturbation and DP-SGD) perform at least as
good as subsample-and-aggregate for all inference-budget values. We also note
that both loss perturbation and model sensitivity benefit greatly from making
$\delta$ non-zero.

Accuracy as a function of privacy failure probability. Figure 4 studies the
effect of varying the privacy failure probability, $\delta$, for a privacy
loss of $\epsilon=1$ and inference budget $B=100$. The results show that loss
perturbation, DP-SGD, and model sensitivity work well even at very small
values of $\delta$. By contrast, prediction sensitivity appears to require
unacceptably high values of $\delta$ to obtain acceptable accuracy. The
subsample-and-aggregate method benefits the most from increasing $\delta$.

Accuracy as a function of training set size. Accuracy and privacy are also
influenced by the number of training examples, $N$. Figure 4 studies this
influence for privacy $(\epsilon,\delta)=(1,0)$ and inference budget $B=100$
on a dataset of up to one million digit images that were generated using
InfiMNIST [27]. (We do not include DP-SGD because it does not support
$\delta=0$.) The results show that subsample-and-aggregate is more suitable
for settings in which few training examples are available (small $N$) because
of the regularizing effect of averaging predictions over $T$ models. However,
it benefits less from increasing the training set size when $T$ remains fixed
(recall that $T=256$). When $N$ is large, loss perturbation and model
sensitivity perform well because the scale of the noise that needs to be added
to obtain a certain value of $\epsilon$ decreases as $N$ increases.

Accuracy as a function of number of dimensions. Accuracy and privacy may also
vary with model capacity, which in linear models can be influenced via the
number of input dimensions, $D$. Figure 5a presents the results of experiments
in which we varied $D$ by applying PCA on the digit images. The figure shows
that loss perturbation and model sensitivity are more competitive when the
model has low capacity to memorize examples ($D$ is small), because this
implies less parameter noise is needed.

Accuracy as a function of number of classes. Figure 5b investigates accuracy
as a function of the number of classes, $C$. In this experiment, a digit
classification problem with $C^{\prime}<C$ classes only considers the first
$C^{\prime}$ digits in the MNIST dataset (digits $0$ to $C^{\prime}-1$).
Unsurprisingly, the accuracy of all methods decreases as the number of classes
increases due to the increase in the problem’s Bayes error. The relative
ranking of the methods appears to be largely independent of the number of
classes.

Accuracy as a function of hyperparameters. Figure 6 studies the effect of: (1)
the $L_{2}$-regularization parameter, $\lambda$, in loss perturbation and (2)
the number of models, $T$, in subsample-and-aggregate. The results show that
models overfit to the perturbation when $\lambda$ is too small, but underfit
when $\lambda$ is too large. The optimal value for $\lambda$ depends on
$\epsilon$. Similarly, larger values of $T$ lead to higher accuracies but
accuracy deteriorates for very large values of $T$ due to overfitting. We note
that increasing $T$ also increases computational requirements for training and
inference, which grow as $O(T)$.

(a) Loss perturbation: As a function of $\lambda$. (b) Subsample-and-
aggregate: As a function of $T$.

Figure 6: Test accuracy on MNIST dataset for privacy failure probability
$\delta=0$ and budget $B=100$.

###  4.3 Results: Convolutional Networks

We also evaluated the DP-SGD and subsample-and-aggregate methods111Other
private prediction methods cannot be used here because deep networks violate
assumptions 1 and 3. on the CIFAR-10 dataset [24] using a ResNet-20 model
(with “type A” blocks [17]) as $\phi^{\prime}(\cdot)$. To facilitate the
computation of per-example gradients in DP-SGD, we replaced batch
normalization by group normalization [43]. A non-private version of the
resulting model achieves a test accuracy of $86.6\%$ on CIFAR-10. All
convolutional networks are trained using SGD with a batch size of 600, with an
initial learning rate of $0.1$. In all experiments, the learning rate was
divided by $10$ thrice after equally spaced numbers of epochs. We use standard
data augmentation during training: _viz._ , random horizontal flipping and
random crop resizing. The $T=16$ models used in subsample-and-aggregate were
trained for 500 epochs. Because privacy loss increases with number of epochs
in DP-SGD, we trained our DP-SGD models for only 100 epochs. As before, we set
the clip value $\nu$ in DP-SGD via cross-validation.

Figure 7 shows the accuracy of the resulting models as a function of privacy
loss, $\epsilon$, for inference budget $B=10$ (Figure 7a); and as a function
of inference budget, $B$, for privacy loss $\epsilon=1$ (Figure 7b). All
results are for a privacy failure probability of $\delta=10^{-5}$. The results
in the figure show that the subsample-and-aggregate method outperforms DP-SGD
training in some regimes: in particular, when $B$ is small and $\epsilon$ is
large. In most other situations, however, DP-SGD appears to be the best method
to obtain private predictions from a ResNet-20: for privacy loss $\epsilon=1$,
it surpasses subsample-and-aggregate for $B\gtrapprox 5$ predictions. In terms
of accuracy, both methods lead to substantial losses in accuracy compared to a
non-private model: even at a relatively large privacy loss of $\epsilon=5$,
the best private model underperforms its non-private counterpart by at least
$30\%$.

tableEffect of six hyperparameters (columns) on privacy, accuracy, and
computational properties (rows): $\nearrow$ indicates that a property value
goes up with the hyperparameter, $\searrow$ that it goes down,
$\curvearrowright$ that it goes up and then down, and $\cdots$ that it remains
unchanged. Effects for method-independent hyperparameters are in the left
columns: the number of training examples $N$, the number of classes $C$, and
the number of dimensions $D$. Effects for method-specific hyperparameters are
in the right columns: the inference budget $B$, the number of models $T$, and
the $L_{2}$-regularization parameter $\lambda$.  $\mathbf{N}$ $\mathbf{C}$
$\mathbf{D}$ $\mathbf{B}$ $\mathbf{T}$ $\boldsymbol{\lambda}$ Privacy loss
($\epsilon$) $\searrow$ $\nearrow$ $\nearrow$ $\nearrow$ $\searrow$ $\searrow$
Privacy failure probability ($\delta$) $\searrow$ $\cdots$ $\cdots$ $\nearrow$
$\cdots$ $\searrow$ Accuracy $\nearrow$ $\searrow$ $\nearrow$ $\searrow$
$\curvearrowright$ $\curvearrowright$ Training time $\nearrow$ $\nearrow$
$\nearrow$ $\cdots$ $\nearrow$ $\cdots$ Inference time $\cdots$ $\nearrow$
$\nearrow$ $\cdots$ $\nearrow$ $\cdots$

##  5 Discussion

The results of our experiments demonstrate that there exist a range of complex
trade-offs in private prediction. We summarize these trade-offs in Table 4.3.
The table provides an overview of how privacy, accuracy, and computation are
affected by increases in variables such as the number of training examples,
the inference budget, the number of input dimensions, the amount of
regularization, _etc._ We hope that this overview provides practitioners some
guidance on the trade-offs of private prediction.

(a) As a function of privacy loss, $\epsilon$, for $B=10$. (b) As a function
of inference budget, $B$, for $\epsilon=1$.

Figure 7: Test accuracy on CIFAR-10 dataset of ResNet-20 with group
normalization for $\delta=10^{-5}$.

A perhaps surprising result of our study is that private training methods are
often a better alternative for private prediction than private prediction
methods. Methods such as subsample-and-aggregate appear to be most competitive
for small inference budgets (tens or hundreds of test examples) and for small
training sets, but tend to be surpassed by private training methods otherwise.
We surmise that the main reason for this observation is that inference-budget
accounting is fairly naive: the privacy guarantees assume that privacy loss
grows linearly ($\delta=0$) or with the square root ($\delta>0$) of the number
of inferences, which may be overly pessimistic. Inference-budget accounting
may be improved, _e.g._ , using accounting mechanisms akin to those in the
PATE family of algorithms [34, 36].

Another way in which private prediction methods may be improved is by making
stronger assumptions about the models with which they are used. In particular,
the subsample-and-aggregate method is the only method that treats models as a
pure black box. This is an advantage in the sense that it provides flexibility
compared to private training methods that support only a small family of
models: for example, subsample-and-aggregate could also be used to make
private predictions for decision trees. But the flexibility of subsample-and-
aggregate is also a weakness because it may cause the privacy guarantees to be
too pessimistic. Indeed, it may be possible to improve private prediction
methods for specific models by making additional assumptions about those
models (linearity, smoothness, _etc._) or by adapting the models to make them
more suitable for private training or prediction [35].

## Broader Impact

To date, there are a large number of machine-learning systems that are trained
on data that needs to remain private or confidential but that expose
predictions to the outside world. Examples of such systems include cloud
services, content-ranking systems, and recommendation services. In controlled
settings, experiments have shown that it may be possible to extract private
information from such predictions. Yet, the machine-learning community
currently has limited understanding of how much private information can be
leaked from such services and how this information leakage can be limited.
Over the past decade, a range of methods has been developed that aim to limit
information leakage but these methods have primarily been studied
theoretically. Indeed, little is known about their empirical performance in
terms of the inevitable privacy-accuracy trade-off. This work helps to improve
that understanding. As such, we believe this study helps anyone whose data is
used to train modern machine-learning systems. In particular, our study can
help the developers of those systems to better understand the privacy risks in
their systems and may also help them find better operating points on the
privacy-accuracy spectrum.

## Acknowledgements

We thank Ilya Mironov, Davide Testuginne, Mark Tygert, Mike Rabbat, and Aaron
Roth for helpful feedback on early versions of this paper.

## References

  * [1] M. Abadi, A. Chu, I. Goodfellow, H. McMahan, I. Mironov, K. Talwar, and L. Zhang.  Deep learning with differential privacy.  In Proceedings of the CCS, pages 308–318, 2016.
  * [2] B. Balle and Y.-X. Wang.  Improving the gaussian mechanism for differential privacy.  In Proceedings of International Conference on Machine Learning, 2018\.
  * [3] R. Bassily, A. Smith, and A. Thakurta.  Differentially private empirical risk minimization: Efficient algorithms and tight error bounds.  Technical report, 2014.
  * [4] R. Bassily, O. Thakkar, and A. G. Thakurta.  Model-agnostic private learning.  In Advances in Neural Information Processing Systems (NeurIPS), volume 31, 2018.
  * [5] S. Boyd, S. P. Boyd, and L. Vandenberghe.  Convex optimization.  Cambridge university press, 2004.
  * [6] N. Carlini, M. Jagielski, and I. Mironov.  Cryptanalytic extraction of neural network models.  In arXiv:2003.04884, 2020.
  * [7] N. Carlini, C. Liu, Ú. Erlingsson, J. Kos, and D. Song.  The secret sharer: Evaluating and testing unintended memorization in neural networks.  In 28th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 19), pages 267–284, 2019.
  * [8] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate.  Differentially private empirical risk minimization.  Journal of Machine Learning Research, 12:1069–1109, 2011.
  * [9] Y. Dagan and V. Feldman.  PAC learning with stable and private predictions.  In arXiv 1911.10541, 2019.
  * [10] C. Dwork.  Differential privacy.  Encyclopedia of Cryptography and Security, pages 338–340, 2011\.
  * [11] C. Dwork and V. Feldman.  Privacy-preserving prediction.  In Proceedings of the Conference on Learning Theory (COLT), pages 1693–1702, 2018.
  * [12] C. Dwork, F. McSherry, K. Nissim, and A. Smith.  Calibrating noise to sensitivity in private data analysis.  In Theory of cryptography conference, pages 265–284. Springer, 2006\.
  * [13] C. Dwork, A. Roth, et al.  The algorithmic foundations of differential privacy.  Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014.
  * [14] C. Dwork and G. N. Rothblum.  Concentrated differential privacy.  arXiv preprint arXiv:1603.01887, 2016.
  * [15] C. Dwork, G. N. Rothblum, and S. Vadhan.  Boosting and differential privacy.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 51–60. IEEE, 2010.
  * [16] M. Fredrikson, S. Jha, and T. Ristenpart.  Model inversion attacks that exploit confidence information and basic countermeasures.  In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 1322–1333, 2015.
  * [17] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In CVPR, 2016.
  * [18] R. A. Horn and C. R. Johnson.  Topics in matrix analysis.  Cambridge University Press, 1994.
  * [19] R. A. Horn and C. R. Johnson.  Matrix analysis.  Cambridge University Press, 2012.
  * [20] R. Iyengar, J. P. Near, D. Song, O. Thakkar, A. Thakurta, and L. Wang.  Towards practical differentially private convex optimization.  In 2019 IEEE Symposium on Security and Privacy (SP), pages 299–316. IEEE, 2019.
  * [21] B. Jayaraman and D. Evans.  Evaluating differentially private machine learning in practice.  In Proceedings of the USENIX Security Symposium, 2019.
  * [22] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith.  What can we learn privately?  SIAM Journal on Computing, 40(3):793–826, 2011.
  * [23] D. Kifer, A. Smith, and A. Thakurta.  Private convex empirical risk minimization and high-dimensional regression.  In Proceedings of the Conference on Learning Theory (COLT), 2012\.
  * [24] A. Krizhevsky.  Learning multiple layers of features from tiny images, 2009.
  * [25] M. Kružík.  Bauer’s maximum principle and hulls of sets.  Calculus of Variations and Partial Differential Equations, 11(3):321–332, 2000.
  * [26] Y. LeCun and C. Cortes.  The MNIST database of handwritten digits, 1998.
  * [27] G. Loosli, S. Canu, and L. Bottou.  Training invariant support vector machines using selective sampling.  In L. Bottou, O. Chapelle, D. DeCoste, and J. Weston, editors, Large Scale Kernel Machines, pages 301–320. MIT Press, Cambridge, MA., 2007\.
  * [28] F. McSherry and K. Talwar.  Mechanism design via differential privacy.  In Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 94–103. IEEE, 2007.
  * [29] S. Milli, L. Schmidt, A. D. Dragan, and M. A. W. Hardt.  Model reconstruction from model explanations.  In Proceedings of the Conference on Fairness, Accountability, and Transparency, 2019.
  * [30] I. Mironov.  Renyi differential privacy.  In Proceedings of the Computer Security Foundations Symposium (CSF), 2019.
  * [31] I. Mironov, K. Talwar, and L. Zhang.  Renyi differential privacy of the sampled Gaussian mechanism.  In arXiv 1908.10530, 2019.
  * [32] A. Nandi and R. Bassily.  Privately answering classification queries in the agnostic PAC model.  In arXiv 1907.13553, 2019.
  * [33] K. Nissim, S. Raskhodnikova, and A. Smith.  Smooth sensitivity and sampling in private data analysis.  In STOC, 2007.
  * [34] N. Papernot, M. Abadi, U. Erlingsson, I. Goodfellow, and K. Talwar.  Semi-supervised knowledge transfer for deep learning from private training data.  arXiv preprint arXiv:1610.05755, 2016.
  * [35] N. Papernot, S. Chien, S. Song, A. Thakurta, and U. Erlingsson.  Making the shoe fit: Architectures, initializations, and tuning for learning with privacy, 2019.
  * [36] N. Papernot, S. Song, I. Mironov, A. Raghunathan, K. Talwar, and Ú. Erlingsson.  Scalable private learning with PATE.  arXiv preprint arXiv:1802.08908, 2018.
  * [37] A. Sablayrolles, M. Douze, Y. Ollivier, C. Schmid, and H. Jégou.  White-box vs black-box: Bayes optimal strategies for membership inference.  In Proceedings of the International Conference on Machine Learning (ICML), 2019.
  * [38] R. Shokri, M. Stronati, C. Song, and V. Shmatikov.  Membership inference attacks against machine learning models.  In 2017 IEEE Symposium on Security and Privacy (SP), pages 3–18. IEEE, 2017.
  * [39] F. Tramèr, F. Zhang, A. Juels, M. K. Reiter, and T. Ristenpart.  Stealing machine learning models via prediction APIs.  In Proceedings of the USENIX Security Symposium, pages 601–618, 2016.
  * [40] D. Wang, M. Ye, and J. Xu.  Differentially private empirical risk minimization revisited: Faster and more general.  In Advances in Neural Information Processing Systems, 2017.
  * [41] P. Wolfe.  Convergence conditions for ascent methods.  SIAM Review, 11:226–000, 1969.
  * [42] X. Wu, F. Li, A. Kumar, K. Chaudhuri, S. Jha, and J. F. Naughton.  Bolt-on differential privacy for scalable stochastic gradient descent-based analytics.  In Proceedings of the International Conference on Management of Data, 2017.
  * [43] Y. Wu and K. He.  Group normalization.  In Proceedings of European Conference on Computer Vision, 2018.
  * [44] S. Yeom, I. Giacomelli, M. Fredrikson, and S. Jha.  Privacy risk in machine learning: Analyzing the connection to overfitting.  In CSF, 2018.
  * [45] C. Zhu, R. H. Byrd, P. Lu, and J. Nocedal.  L-BFGS-B: Algorithm 778: L-BFGS-B, FORTRAN routines for large scale bound constrained optimization.  ACM Transactions on Mathematical Software, 23:550–560, 1997.

##  Appendix A Preliminaries

As a reminder, we denote by $\phi(\mathbf{x};\theta)$ a machine learning model
with parameters $\theta$ that given a $D$-dimensional input vector,
$\mathbf{x}\in\mathbb{R}^{D}$, produces a probability vector over $C$ classes
$\mathbf{y}\in\Delta^{C}$, where $\Delta^{C}$ represents the
$(C\\!-\\!1)$-dimensional probability simplex. The parameters $\theta$ are
obtained by fitting the model on a training set of $N$ labeled examples,
$\mathcal{D}=\\{(\mathbf{x}_{1},\mathbf{y}_{1}),\dots,(\mathbf{x}_{N},\mathbf{y}_{N})\\}$.

In the following we aim to bound the privacy loss on the training set
$\mathcal{D}$ given a budget of $B$ queries,
$\mathcal{Q}=\\{\hat{\mathbf{x}}_{1},\dots,\hat{\mathbf{x}}_{B}\\}$, to the
model $\phi(\cdot)$.

We adopt a regularized empirical risk minimization framework in which we
minimize:

$J(\theta;\mathcal{D})=\frac{1}{N}\sum_{n=1}^{N}\ell(\phi^{\prime}(\mathbf{x}_{n};\theta),\mathbf{y}_{n})+\lambda
R(\theta).$ (5)

with respect to $\theta$, where $\ell(\cdot)$ is a loss function, $R(\cdot)$
is a regularizer, and $\lambda\geq 0$ is a regularization parameter. Some of
the methods make one or more of the following assumptions:

  1. 1.

The loss function $\ell(\cdot)$ is strictly convex, continuous, and
differentiable everywhere.

  2. 2.

The regularizer $R(\theta)$ is $1$-strongly convex, continuous, and
differentiable everywhere w.r.t. $\theta$.

  3. 3.

The model $\phi^{\prime}(\cdot)$ is linear, _i.e._ ,
$\phi^{\prime}(\mathbf{x};\theta)=\theta^{\top}\mathbf{x}$.

  4. 4.

The loss function $\ell(\cdot)$ is Lipschitz with a constant $K$, _i.e._ ,
$\|\nabla l\|_{2}\leq K$.

  5. 5.

The inputs are contained in the unit $L_{2}$ ball, _i.e._
$\|\mathbf{x}\|_{2}\leq 1$ for all $\mathbf{x}$.

In the following, we denote by $\|\mathbf{A}\|_{F}$ the Frobenius norm of the
matrix $\mathbf{A}$, _i.e._ :

$\|\mathbf{A}\|_{F}=\left(\sum_{i,j}\mathbf{A}_{ij}^{2}\right)^{\nicefrac{{1}}{{2}}}.$
(6)

We use Lemma 1 in the privacy proofs for the model and prediction sensitivity
methods.

######  Lemma 1.

Given assumptions 1, 2, 3, 4, and 5, and letting
$\theta_{1}\\!=\\!\operatorname*{arg\,min}_{\theta}J(\theta;\mathcal{D})$ and
$\theta_{2}\\!=\\!\operatorname*{arg\,min}_{\theta}J(\theta;\mathcal{D}^{\prime})$,
the sensitivity is bounded as
$\|\theta_{1}-\theta_{2}\|_{F}\leq\frac{2K}{N\lambda}$.

###### Proof.

To bound the sensitivity, let $G(\theta)=J(\theta;\mathcal{D})$ and
$g(\theta)=J(\theta;\mathcal{D}^{\prime})-J(\theta;\mathcal{D})$. Note that
$\theta_{1}=\operatorname*{arg\,min}_{\theta}G(\theta)$ and
$\theta_{2}=\operatorname*{arg\,min}_{\theta}G(\theta)+g(\theta)$. Given
Assumptions 1 and 2, we can apply Lemma 7 of [8] to get:

$\|\theta_{1}-\theta_{2}\|_{F}\leq\frac{1}{\lambda}\max_{\theta}\|\nabla
g(\theta)\|_{F}.$ (7)

Next we bound $\|\nabla g(\theta)\|_{F}$. Let $\mathbf{x},\mathbf{y}$ and
$\mathbf{x}^{\prime},\mathbf{y}^{\prime}$ be the differing examples in
$\mathcal{D}$ and $\mathcal{D}^{\prime}$. Using assumption 3, we have:

$g(\theta)=\frac{1}{N}(\ell(\theta^{\top}\mathbf{x},\mathbf{y})-\ell(\theta^{\top}\mathbf{x}^{\prime},\mathbf{y}^{\prime})).$
(8)

Thus:

$\nabla
g(\theta)=\frac{1}{N}(\nabla\ell(\theta^{\top}\mathbf{x},\mathbf{y})\mathbf{x}^{\top}-\nabla\ell(\theta^{\top}\mathbf{x}^{\prime},\mathbf{y}^{\prime})\mathbf{x}^{\prime\top}),$
(9)

and:

$\displaystyle\|\nabla g(\theta)\|_{F}$
$\displaystyle=\frac{1}{N}\left\|\nabla\ell(\theta^{\top}\mathbf{x},\mathbf{y})\mathbf{x}^{\top}-\nabla\ell(\theta^{\top}\mathbf{x}^{\prime},\mathbf{y}^{\prime})\mathbf{x}^{\prime\top}\right\|_{F}$
$\displaystyle\leq\frac{1}{N}\left(\left\|\nabla\ell(\theta^{\top}\mathbf{x},\mathbf{y})\mathbf{x}^{\top}\right\|_{F}+\left\|\nabla\ell(\theta^{\top}\mathbf{x}^{\prime},\mathbf{y}^{\prime})\mathbf{x}^{\prime\top}\right\|_{F}\right)$
$\displaystyle\leq\frac{1}{N}\left(\left\|\nabla\ell(\theta^{\top}\mathbf{x},\mathbf{y})\right\|_{2}\left\|\mathbf{x}\right\|_{2}+\left\|\nabla\ell(\theta^{\top}\mathbf{x}^{\prime},\mathbf{y}^{\prime})\right\|_{2}\left\|\mathbf{x}^{\prime}\right\|_{2}\right)$
$\displaystyle\leq\frac{1}{N}K\left(\left\|\mathbf{x}\right\|_{2}+\left\|\mathbf{x}^{\prime}\right\|_{2}\right)$
$\displaystyle\leq\frac{2K}{N}.$

We use the triangle inequality in the third step, the fact that $\|{\bf u}{\bf
v}^{\top}\|_{F}=\|{\bf u}\|_{2}\|{\bf v}\|_{2}$ in the fourth step, and
assumptions 4 and 5 in steps five and six respectively. Thus we have:

$\|\nabla g(\theta)\|_{F}\leq\frac{2K}{N}.$ (10)

Combining Equations 7 and 10 yields:

$\|\theta_{1}-\theta_{2}\|_{F}\leq\frac{2K}{N\lambda},$ (11)

completing the proof. ∎

For the perturbations used by the sensitivity methods, we sample noise from
the distribution:

$p(\mathbf{B})=\frac{1}{z}e^{-\beta\|\mathbf{B}\|_{F}},$ (12)

where $z$ is a normalizing constant. When $\delta>0$ we use a zero-mean
isotropic Gaussian distribution with a standard deviation of $\sigma$:

$p(\mathbf{B})=\frac{1}{z}e^{-\frac{1}{2\sigma^{2}}\|\mathbf{B}\|^{2}_{F}},$
(13)

where $z$ is a normalizing constant.

##  Appendix B Private Training

###  B.1 Model Sensitivity

We generalize the sensitivity method of [8] to the setting of multi-class
classification. The multi-class model sensitivity method achieves
$\epsilon$-differential privacy with respect to the dataset $\mathcal{D}$ when
releasing the model parameters $\theta$. In this case, the budget of test
examples is infinite since the model itself is differentially private. The
model sensitivity method is given in Algorithm 1.

Algorithm 1 Multi-class model sensitivity.

Inputs: Privacy parameter $\epsilon$, regularization parameter $\lambda$, and
dataset $\mathcal{D}$.

Output: $\theta_{\textrm{priv}}$, the $\epsilon$-differentially private
classifier.

Sample $\mathbf{B}$ from the distribution in Equation 12 with
$\beta=\frac{N\lambda\epsilon}{2K}$.

Compute
$\theta_{\textrm{priv}}=\operatorname*{arg\,min}_{\theta}J(\theta;\mathcal{D})+\mathbf{B}$.

######  Theorem 1.

Given assumptions 1, 2, 3, 4, and 5, the model sensitivity method in Algorithm
1 is $\epsilon$-differentially private.

###### Proof.

We bound the privacy loss in terms of the sensitivity of the minimizer of
$J(\cdot)$ (Equation 5) in the Frobenius norm and then apply Lemma 1. We
denote by $\mathcal{A}$ the application of differential privacy mechanism,
_i.e._ a run of Algorithm 1.

For all datasets $\mathcal{D}$ and $\mathcal{D}^{\prime}$ which differ by one
example, we have:

$\displaystyle\log\frac{p(\mathcal{A}(\mathcal{D})=\theta)}{p(\mathcal{A}(\mathcal{D}^{\prime})=\theta)}$
$\displaystyle=\log\frac{e^{-\beta\|\theta_{1}+\mathbf{B}\|_{F}}}{e^{-\beta\|\theta_{2}+\mathbf{B}\|_{F}}}$
$\displaystyle=\beta\left(\|\theta_{2}+\mathbf{B}\|_{F}-\|\theta_{1}+\mathbf{B}\|_{F}\right)$
$\displaystyle\leq\beta\|\theta_{1}-\theta_{2}\|_{F},$

where we use the triangle inequality, and the fact that:
$\theta_{1}=\operatorname*{arg\,min}_{\theta}J(\theta;\mathcal{D})$ and
$\theta_{2}=\operatorname*{arg\,min}_{\theta}J(\theta;\mathcal{D}^{\prime})$.
Thus:

$\log\frac{p(\mathcal{A}(\mathcal{D})=\theta)}{p(\mathcal{A}(\mathcal{D}^{\prime})=\theta)}\leq\beta\|\theta_{1}-\theta_{2}\|_{F}.$
(14)

Combining Equation 14 with Lemma 1 yields:

$\log\frac{p(\mathcal{A}(\mathcal{D})=\theta)}{p(\mathcal{A}(\mathcal{D}^{\prime})=\theta)}\leq\beta\|\theta_{1}-\theta_{2}\|_{F}\leq\frac{\beta
2K}{N\lambda}.$ (15)

Thus if we choose $\beta=\frac{N\lambda\epsilon}{2K}$, we achieve
$\epsilon$-differential privacy. ∎

The model sensitivity method in Algorithm 1 is
$(\epsilon,\delta)$-differentially private with $\delta=0$. By letting
$\delta>0$, we can use noise from a Gaussian distribution.

Algorithm 2 Analytic Gaussian mechanism [2].

Inputs: Privacy parameters $\epsilon$ and $\delta$.

Output: Scalar $\alpha$ used to compute the variance of the Guassian noise
distribution.

Let $\delta_{0}=\Phi(0)-e^{\epsilon}\Phi(-\sqrt{2\epsilon})$.

if $\delta\geq\delta_{0}$ then

Define $B_{\epsilon}^{+}(v)=\Phi(\sqrt{\epsilon
v})-e^{\epsilon}\Phi(-\sqrt{\epsilon(v+2)})$.

Find $v^{*}=\sup\\{v\in\mathbb{R}_{\geq 0}:B_{\epsilon}^{+}(v)\leq\delta\\}$.

Let $\alpha=\sqrt{1+\nicefrac{{v^{*}}}{{2}}}-\sqrt{\nicefrac{{v^{*}}}{{2}}}$.

else

Define $B_{\epsilon}^{-}(u)=\Phi(-\sqrt{\epsilon
u})-e^{\epsilon}\Phi(-\sqrt{\epsilon(u+2)})$.

Find $u^{*}=\inf\\{u\in\mathbb{R}_{\geq 0}:B_{\epsilon}^{-}(u)\leq\delta\\}$.

end if

We use the analytic Gaussian mechanism of [2], which results in better privacy
parameters at the same noise scale than the standard Gaussian mechanism [13].
We rely on Algorithm 2, a subroutine of Algorithm 1 from [2], in order to
compute the $\alpha$ required by the analytic Gaussian mechanism. Following
[2], we note that $B_{\epsilon}^{+}(v)$ and $B_{\epsilon}^{-}(u)$ are
monotonic functions and use binary search to find the value of $v^{*}$ and
$u^{*}$ in Algorithm 2 up to arbitrary precision.

Algorithm 3 Multi-class Gaussian model sensitivity.

Inputs: Privacy parameters $\epsilon$ and $\delta$, regularization parameter
$\lambda$, and dataset $\mathcal{D}$.

Output: $\theta_{\textrm{priv}}$, the $(\epsilon,\delta)$-differentially
private classifier.

Compute $\alpha$ using Algorithm 2.

Sample $\mathbf{B}$ from the distribution in Equation 13 with
$\sigma=\frac{2K\alpha}{N\lambda\sqrt{2\epsilon}}$.

Compute
$\theta_{\textrm{priv}}=\operatorname*{arg\,min}_{\theta}J(\theta;\mathcal{D})+\mathbf{B}$.

######  Theorem 2.

Given assumptions 1, 2, 3, 4, and 5, the Gaussian model sensitivity method in
Algorithm 3 is $(\epsilon,\delta)$-differentially private for
$\delta\in(0,1)$.

###### Proof.

From Lemma 1, we have a bound on the sensitivity of
$\theta(\mathcal{D})=\operatorname*{arg\,min}_{\theta^{\prime}}J(\theta^{\prime};\mathcal{D})$:

$\max_{\mathcal{D},\mathcal{D}^{\prime}}\|\theta(\mathcal{D})-\theta(\mathcal{D}^{\prime})\|_{F}\leq\frac{2K}{N\lambda}.$
(16)

We apply Theorem 8 of [2] which states that for any $\epsilon\geq 0$ and
$\delta\in(0,1)$, the Gaussian mechanism with standard deviation $\sigma$
provides $(\epsilon,\delta)$-differential privacy if and only if:

$\Phi\left(\frac{\Delta_{2}f}{2\sigma}-\frac{\epsilon\sigma}{\Delta_{2}f}\right)-e^{\epsilon}\Phi\left(-\frac{\Delta_{2}f}{2\sigma}-\frac{\epsilon\sigma}{\Delta_{2}f}\right)\leq\delta,$
(17)

where $\Delta_{2}f$ is the $L_{2}$ sensitivity of the function
$f(\mathcal{D})$, and $\Phi(\cdot)$ is the cumulative distribution function
(CDF) of the standard univariate Gaussian distribution.

Combining the upper bound on $\Delta_{2}f$ from Equation 16 with Theorem 9 of
[2] shows that the Gaussian model sensitivity method in Algorithm 3 is
$(\epsilon,\delta)$-differentially private. ∎

###  B.2 Loss Perturbation

We generalize the loss perturbation method of [8] to the multi-class setting.
We use the slighly modified mobjective of [23]:

$J(\theta;\mathcal{D})=\frac{1}{N}\sum_{n=1}^{N}\ell(\phi^{\prime}(\mathbf{x}_{n};\theta),\mathbf{y}_{n})+\frac{\lambda}{N}R(\theta),$
(18)

where we assume that both $\ell(\cdot)$ and $R(\cdot)$ are convex with
continuous Hessians and that $\phi^{\prime}(\cdot)$ is linear. The multi-class
loss perturbation method is given in Algorithm 4 where the function
$\text{tr}(\mathbf{A})$ is the trace of a square matrix $\mathbf{A}$.

Algorithm 4 Multi-class loss perturbation.

Inputs: Privacy parameter $\epsilon$ and dataset $\mathcal{D}$.

Output: $\theta_{\textrm{priv}}$, the $\epsilon$-differentially private
classifier.

Set $\rho\geq\frac{2LC}{\epsilon}$.

Sample $\mathbf{B}$ from the distribution in Equation 12 with
$\beta=\frac{\epsilon}{2K}$.

Compute
$\theta_{\textrm{priv}}=\operatorname*{arg\,min}_{\theta}J(\theta;\mathcal{D})+\frac{1}{N}\text{tr}(\mathbf{B}^{\top}\theta)+\frac{\rho}{2N}\|\theta\|_{F}^{2}$.

We require additional notation to state and prove the privacy theorem of
Algorithm 4. First, we let $\textnormal{vec}(\mathbf{A})$ denote the
vectorization of the matrix $\mathbf{A}$ constructed by stacking the rows of
$\mathbf{A}$ into a vector. If $\mathbf{A}\in\mathbb{R}^{n\times m}$ then
$\textnormal{vec}(\mathbf{A})\in\mathbb{R}^{nm}$. Second, we rely on the
standard Kronecker product which we denote by the symbol $\otimes$. For two
vectors we have
$\mathbf{u}\otimes\mathbf{v}=\textnormal{vec}(\mathbf{u}\mathbf{v}^{\top})$.
We let $\lambda_{\max}(\mathbf{A})$ denote the maximum eigenvalue of a
symmetric matrix $\mathbf{A}$.

######  Theorem 3.

Given a convex loss $\ell(\cdot)$, a convex regularizer $R(\cdot)$ with
continuous Hessians, assumptions 3, 4, and 5, and assuming that
$\lambda_{\max}(\nabla^{2}\ell)\leq L$, the loss perturbation method in
Algorithm 4 is $\epsilon$-differentially private.

###### Proof.

The proof structure here closely follows that of Theorem 9 in [8] and Theorem
2 in [23] with the appropriate generalizations to account for the multi-class
setting.

Let $\mathbf{w}=\textnormal{vec}(\theta)$ and
$\mathbf{b}=\textnormal{vec}(\mathbf{B})$. We aim to bound the ratio of the
two densities:

$\frac{g(\theta_{\text{priv}}\mid\mathcal{D})}{g(\theta_{\text{priv}}\mid\mathcal{D}^{\prime})}=\frac{g(\mathbf{w}_{\text{priv}}\mid\mathcal{D})}{g(\mathbf{w}_{\text{priv}}\mid\mathcal{D}^{\prime})}.$
(19)

By the same argument used in the proof of Theorem 9 of [8], there is a
bijection from $\mathbf{w}_{\text{priv}}$ to $\mathbf{b}$ for every
$\mathcal{D}$. Hence the ratio in Equation 19 can be written as:

$\frac{g(\mathbf{w}_{\textnormal{priv}}\mid\mathcal{D})}{g(\mathbf{w}_{\textnormal{priv}}\mid\mathcal{D}^{\prime})}=\frac{\mu(\mathbf{b}\mid\mathcal{D})}{\mu(\mathbf{b}^{\prime}\mid\mathcal{D}^{\prime})}\cdot\frac{|\det(\mathbf{J}(\mathbf{w}_{\textnormal{priv}}\rightarrow\mathbf{b}\mid\mathcal{D}))|^{-1}}{|\det(\mathbf{J}(\mathbf{w}_{\textnormal{priv}}\rightarrow\mathbf{b}^{\prime}\mid\mathcal{D}^{\prime}))|^{-1}},$
(20)

where $\mu(\cdot)$ is the conditional noise density given dataset
$\mathcal{D}$ and
$\mathbf{J}(\mathbf{w}_{\textnormal{priv}}\rightarrow\mathbf{b}\mid\mathcal{D})$
is the Jacobian of the mapping from $\mathbf{w}_{\textnormal{priv}}$ to
$\mathbf{b}$ for a given $\mathcal{D}$.

We bound each term in Equation 20, starting with a bound on the ratio of the
determinants of the Jacobians.

For any $\mathbf{w}_{\textnormal{priv}}$ and $\mathcal{D}$, we can solve for
the noise term $\mathbf{b}$ added to the objective in Algorithm 4:

$\mathbf{b}=-\lambda\nabla
R(\mathbf{w}_{\textnormal{priv}})-\sum_{i=1}^{N}\nabla\ell\otimes\mathbf{x}_{i}-\rho\mathbf{w}_{\textnormal{priv}},$
(21)

where we use the short-hand $\nabla_{\mathbf{a}}\ell(\mathbf{a})=\nabla\ell$.
By assumption 3, we have $\nabla_{\theta}\ell=\nabla\ell\mathbf{x}^{\top}$ and
hence $\nabla_{\mathbf{w}}\ell=\nabla\ell\otimes\mathbf{x}$.

We can differentiate Equation 21 to get:

$\nabla\mathbf{b}=-\lambda\nabla^{2}R(\mathbf{w}_{\textnormal{priv}})-\sum_{i=1}^{N}\nabla^{2}\ell\otimes(\mathbf{x}_{i}\mathbf{x}_{i}^{\top})-\rho\mathbf{I}_{DC},$
(22)

where $\mathbf{I}_{DC}$ is the $DC$-dimensional identity matrix.

Without loss of generality, let $\mathcal{D}^{\prime}$ contain one more
example than $\mathcal{D}$ which we denote by
$\mathbf{x}^{\prime},\mathbf{y}^{\prime}$, _i.e._
$\mathcal{D}^{\prime}=\mathcal{D}\cup\\{(\mathbf{x}^{\prime},\mathbf{y}^{\prime})\\}$.
We define the matrices $\mathbf{A}$ and $\mathbf{E}$ as:

$\mathbf{A}=\lambda\nabla^{2}R(\mathbf{w}_{\textnormal{priv}})+\sum_{i=1}^{N}\nabla^{2}\ell\otimes(\mathbf{x}_{i}\mathbf{x}_{i}^{\top})+\rho\mathbf{I}_{DC},$
(23)

and:

$\mathbf{E}=\nabla^{2}\ell\otimes(\mathbf{x}^{\prime}\mathbf{x}^{\prime\top}).$
(24)

Thus:

$\frac{|\det(\mathbf{J}(\mathbf{w}_{\textnormal{priv}}\rightarrow\mathbf{b}^{\prime}\mid\mathcal{D}^{\prime}))|}{|\det(\mathbf{J}(\mathbf{w}_{\textnormal{priv}}\rightarrow\mathbf{b}\mid\mathcal{D}))|}=\frac{|\det(\mathbf{A}+\mathbf{E})|}{|\det(\mathbf{A})|}.$
(25)

Given that $\nabla^{2}\ell\in\mathbb{R}^{C\times C}$ we know that
$\text{Rank}(\nabla^{2}\ell)\leq C$. Since
$\text{Rank}(\mathbf{x}\mathbf{x}^{\top})=1$, we have that
$\text{Rank}(\nabla^{2}\ell\otimes(\mathbf{x}\mathbf{x}^{\top}))\leq C$ [18],
and thus $\text{Rank}(\mathbf{E})\leq C$. Thus we can apply Lemma 2 to bound
the ratio:

$\frac{|\det(\mathbf{A}+\mathbf{E})|}{|\det(\mathbf{A})|}\leq(1+\lambda_{\max}(\mathbf{A}^{-1}\mathbf{E}))^{C}.$
(26)

Given that $R(\cdot)$ and $\ell(\cdot)$ are convex, the eigenvalues of
$\mathbf{A}$ are at least $\rho$, and thus
$\lambda_{\max}(\mathbf{A}^{-1}\mathbf{E})\leq\frac{1}{\rho}\lambda_{\max}(\mathbf{E})$.
Given the assumption that $\lambda_{\max}(\nabla^{2}\ell)\leq L$ and by
assumption 5 $\lambda_{\max}(\mathbf{x}\mathbf{x}^{\top})\leq 1$, we have that
$\lambda_{\max}(\nabla^{2}\ell\otimes(\mathbf{x}\mathbf{x}^{\top}))\leq L$
[18], thus $\lambda_{\max}(\mathbf{E})\leq L$. Combining these observations
with Equations 25 and 26, we have a bound on the ratio:

$\frac{|\det(\mathbf{J}(\mathbf{w}_{\textnormal{priv}}\rightarrow\mathbf{b}^{\prime}\mid\mathcal{D}^{\prime}))|}{|\det(\mathbf{J}(\mathbf{w}_{\textnormal{priv}}\rightarrow\mathbf{b}\mid\mathcal{D}))|}\leq\left(1+\frac{L}{\rho}\right)^{C}.$
(27)

Since $\rho\geq\frac{2LC}{\epsilon}$, we have:

$\left(1+\frac{L}{\rho}\right)^{C}\leq\left(1+\frac{\epsilon}{2C}\right)^{C}\leq
e^{\epsilon/2},$ (28)

using the identity $1+x\leq e^{x}$ for all $x$. Thus we have a final bound on
the ratio:

$\frac{|\det(\mathbf{J}(\mathbf{w}_{\textnormal{priv}}\rightarrow\mathbf{b}^{\prime}\mid\mathcal{D}^{\prime}))|}{|\det(\mathbf{J}(\mathbf{w}_{\textnormal{priv}}\rightarrow\mathbf{b}\mid\mathcal{D}))|}\leq
e^{\epsilon/2}.$ (29)

Next, we bound the ratio
$\frac{\mu(\mathbf{b}\mid\mathcal{D})}{\mu(\mathbf{b}^{\prime}\mid\mathcal{D}^{\prime})}$.
From Equation 21 we have:

$\mathbf{b}^{\prime}-\mathbf{b}=\nabla\ell\otimes\mathbf{x}^{\prime}.$ (30)

Thus:

$\|\mathbf{b}^{\prime}\|_{2}-\|\mathbf{b}\|_{2}\leq\|\mathbf{b}^{\prime}-\mathbf{b}\|_{2}=\left\|\nabla\ell\otimes\mathbf{x}^{\prime}\right\|_{2}\leq\|\nabla\ell\|_{2}\|\mathbf{x}^{\prime}\|_{2}\leq
K,$ (31)

where we use the triangle inequality in the first step, the fact that
$\|\mathbf{u}\otimes\mathbf{v}\|_{2}=\|\mathbf{u}\mathbf{v}^{\top}\|_{F}=\|\mathbf{u}\|_{2}\|\mathbf{v}\|_{2}$
in the third step, and assumptions 4 and 5 in the fifth step. Following the
argument in the proof of Theorem 9 of [8], we have:

$\frac{\mu(\mathbf{b}\mid\mathcal{D})}{\mu(\mathbf{b}^{\prime}\mid\mathcal{D}^{\prime})}\leq
e^{\frac{\epsilon}{2K}(\|\mathbf{b}\|_{2}-\|\mathbf{b}^{\prime}\|_{2})}.$ (32)

Combining Equations 31 and 32, we have:

$\frac{\mu(\mathbf{b}\mid\mathcal{D})}{\mu(\mathbf{b}^{\prime}\mid\mathcal{D}^{\prime})}\leq
e^{\epsilon/2}.$ (33)

Finally, combining Equations 20, 29 and 33, yields:

$\frac{g(\mathbf{w}_{\textnormal{priv}}\mid\mathcal{D})}{g(\mathbf{w}_{\textnormal{priv}}\mid\mathcal{D}^{\prime})}=\frac{\mu(\mathbf{b}\mid\mathcal{D})}{\mu(\mathbf{b}^{\prime}\mid\mathcal{D}^{\prime})}\cdot\frac{|\det(\mathbf{J}(\mathbf{w}_{\textnormal{priv}}\rightarrow\mathbf{b}\mid\mathcal{D}))|^{-1}}{|\det(\mathbf{J}(\mathbf{w}_{\textnormal{priv}}\rightarrow\mathbf{b}^{\prime}\mid\mathcal{D}^{\prime}))|^{-1}}\leq
e^{\epsilon/2}e^{\epsilon/2}\leq e^{\epsilon},$ (34)

completing the proof. ∎

We can use noise from a Gaussian distribution by letting $\delta>0$ [23]. We
generalize the approach of [23] to the multi-class setting.

Algorithm 5 Multi-class Gaussian loss perturbation.

Inputs: Privacy parameters $\epsilon$ and $\delta$, and dataset $\mathcal{D}$.

Output: $\theta_{\textrm{priv}}$, the $(\epsilon,\delta)$-differentially
private classifier.

Set $\rho\geq\frac{2LC}{\epsilon}$.

Sample $\mathbf{B}$ from the distribution in Equation 13 with
$\sigma=\frac{K}{\epsilon}\sqrt{8\log(2/\delta)+4\epsilon}$.

Compute
$\theta_{\textrm{priv}}=\operatorname*{arg\,min}_{\theta}J(\theta,\mathcal{D})+\frac{1}{N}\text{tr}(\mathbf{B}^{\top}\theta)+\frac{\rho}{2N}\|\theta\|_{F}^{2}$.

######  Theorem 4.

Given a convex loss $\ell(\cdot)$, a convex regularizer $R(\cdot)$ with
continuous Hessians, assumptions 3, 4, and 5, and assuming that
$\lambda_{\max}(\nabla^{2}\ell)\leq L$, the loss perturbation method in
Algorithm 5 is $(\epsilon,\delta)$-differentially private.

###### Proof.

Let $\mathbf{w}=\textnormal{vec}(\theta)$ and
$\mathbf{b}=\textnormal{vec}(\mathbf{B})$. We aim to bound the ratio of the
two densities:

$\frac{g(\theta_{\text{priv}}\mid\mathcal{D})}{g(\theta_{\text{priv}}\mid\mathcal{D}^{\prime})}=\frac{g(\mathbf{w}_{\text{priv}}\mid\mathcal{D})}{g(\mathbf{w}_{\text{priv}}\mid\mathcal{D}^{\prime})},$
(35)

with probability at least $1-\delta$.

As in Theorem 3, there is a bijection from $\mathbf{w}_{\text{priv}}$ to
$\mathbf{b}$ for every $\mathcal{D}$. Hence the ratio in Equation 35 can be
written as:

$\frac{g(\mathbf{w}_{\textnormal{priv}}\mid\mathcal{D})}{g(\mathbf{w}_{\textnormal{priv}}\mid\mathcal{D}^{\prime})}=\frac{\mu(\mathbf{b}\mid\mathcal{D})}{\mu(\mathbf{b}^{\prime}\mid\mathcal{D}^{\prime})}\cdot\frac{|\det(\mathbf{J}(\mathbf{w}_{\textnormal{priv}}\rightarrow\mathbf{b}\mid\mathcal{D}))|^{-1}}{|\det(\mathbf{J}(\mathbf{w}_{\textnormal{priv}}\rightarrow\mathbf{b}^{\prime}\mid\mathcal{D}^{\prime}))|^{-1}},$
(36)

where $\mu(\cdot)$ is the conditional noise density given dataset
$\mathcal{D}$ and
$\mathbf{J}(\mathbf{w}_{\textnormal{priv}}\rightarrow\mathbf{b}\mid\mathcal{D})$
is the Jacobian of the mapping from $\mathbf{w}_{\textnormal{priv}}$ to
$\mathbf{b}$ for a given $\mathcal{D}$.

From Equation 29 in the proof of Theorem 3, we have that:

$\frac{|\det(\mathbf{J}(\mathbf{w}_{\textnormal{priv}}\rightarrow\mathbf{b}\mid\mathcal{D}))|^{-1}}{|\det(\mathbf{J}(\mathbf{w}_{\textnormal{priv}}\rightarrow\mathbf{b}^{\prime}\mid\mathcal{D}^{\prime}))|^{-1}}\leq
e^{\epsilon/2}.$ (37)

Following the same arguments as the proof of Theorem 2 in [23], we have with
at least probability $1-\delta$:

$\frac{\mu(\mathbf{b}\mid\mathcal{D})}{\mu(\mathbf{b}^{\prime}\mid\mathcal{D}^{\prime})}\leq
e^{\frac{1}{2\beta^{2}}\left(\beta K\sqrt{8\log(2/\delta)}+K^{2}\right)}.$
(38)

If we choose $\beta\geq\frac{K}{\epsilon}\sqrt{8\log(2/\delta)+4\epsilon}$
then:

$\frac{\mu(\mathbf{b}\mid\mathcal{D})}{\mu(\mathbf{b}^{\prime}\mid\mathcal{D}^{\prime})}\leq
e^{\epsilon/2}.$ (39)

Combining Equations 36, 37 and 39 yields:

$\frac{g(\mathbf{w}_{\textnormal{priv}}\mid\mathcal{D})}{g(\mathbf{w}_{\textnormal{priv}}\mid\mathcal{D}^{\prime})}\leq
e^{\epsilon},$ (40)

with probability at least $1-\delta$, completing the proof.

∎

######  Lemma 2.

Given symmetric and positive semidefinite matrices, $\mathbf{A}$ and
$\mathbf{E}$, if $\mathbf{A}$ is full rank, and $\mathbf{E}$ has rank at most
$C$, then:

$\frac{\det(\mathbf{A}+\mathbf{E})}{\det{\mathbf{A}}}\leq(1+\lambda_{\max}(\mathbf{A}^{-1}\mathbf{E}))^{C},$
(41)

where $\lambda_{\max}(\mathbf{A}^{-1}\mathbf{E})$ is the maximum eigenvalue of
$\mathbf{A}^{-1}\mathbf{E}$.

###### Proof.

$\displaystyle\frac{\det(\mathbf{A}+\mathbf{E})}{\det{\mathbf{A}}}$
$\displaystyle=\det{(\mathbf{I}+\mathbf{A}^{-1}\mathbf{E})}$
$\displaystyle=\prod_{c=1}^{C}(1+\lambda_{c}(\mathbf{A}^{-1}\mathbf{E}))$
$\displaystyle\leq(1+\lambda_{\max}(\mathbf{A}^{-1}\mathbf{E}))^{C}.$

In the second step we use the facts that
$\lambda_{i}(\mathbf{I}+\mathbf{A}^{-1}\mathbf{E})=1+\lambda_{i}(\mathbf{A}^{-1}\mathbf{E})$
and that $\mathbf{A}^{-1}\mathbf{E}$ has rank at most $C$ and hence has at
most $C$ nonzero eigenvalues. ∎

##  Appendix C Private Prediction

###  C.1 Prediction Sensitivity

The prediction sensitivity method protects the privacy of the underlying
training dataset, $\mathcal{D}$, by adding a unique noise vector to the logit
predictions, $\phi^{\prime}(\hat{\mathbf{x}};\theta)$, for each test example
$\hat{\mathbf{x}}$.

The prediction sensitivity method is given in Algorithm 6. The algorithm
accepts as input a budget $B$ of test examples and guarantees
$\epsilon$-differential privacy of $\mathcal{D}$ until the budget is exhausted
after which the privacy of $\mathcal{D}$ degrades.

Algorithm 6 Multi-class prediction sensitivity.

Inputs: Privacy parameter $\epsilon$, non-private model
$\phi^{\prime}(\cdot)$, test example $\hat{\mathbf{x}}$, and budget $B$.

Output: $\hat{\mathbf{y}}_{\textrm{priv}}$, the prediction which is
$\epsilon$-differentially private with respect to the training dataset
$\mathcal{D}$.

Sample $\mathbf{b}$ from the distribution in Equation 12 with
$\beta=\frac{N\lambda\epsilon}{2KB}$.

Compute
$\hat{\mathbf{y}}_{\textrm{priv}}=\phi^{\prime}(\hat{\mathbf{x}};\theta)+\mathbf{b}$.

######  Theorem 5.

Given assumptions 1, 2, 3, 4, and 5, the prediction sensitivity method in
Algorithm 6 is $\epsilon$-differentially private.

###### Proof.

The proof proceeds the same way as that of Theorem 1. First, we bound the
privacy loss in terms of the sensitivity of the minimizer of $J(\cdot)$ in the
Frobenius norm and then we apply Lemma 1.

Let $\theta_{1}\\!=\\!\operatorname*{arg\,min}_{\theta}J(\theta;\mathcal{D})$
and
$\theta_{2}\\!=\\!\operatorname*{arg\,min}_{\theta}J(\theta;\mathcal{D}^{\prime})$.
For all datasets $\mathcal{D}$ and $\mathcal{D}^{\prime}$ which differ by one
example and all $\mathbf{x}$, we have:

$\displaystyle\log\frac{p(\mathcal{A}(\mathcal{D},\mathbf{x})=\mathbf{y})}{p(\mathcal{A}(\mathcal{D}^{\prime},\mathbf{x})=\mathbf{y})}$
$\displaystyle=\log\frac{e^{-\beta\|\theta_{1}^{\top}\mathbf{x}+\mathbf{b}\|_{2}}}{e^{-\beta\|\theta_{2}^{\top}\mathbf{x}+\mathbf{b}\|_{2}}}$
$\displaystyle=\beta\left(\|\theta^{\top}_{2}\mathbf{x}+\mathbf{b}\|_{2}-\|\theta_{1}^{\top}\mathbf{x}+\mathbf{b}\|_{2}\right)$
$\displaystyle\leq\beta\|\theta_{1}^{\top}\mathbf{x}-\theta_{2}^{\top}\mathbf{x}\|_{2}$
$\displaystyle\leq\beta\|(\theta_{1}-\theta_{2})^{\top}\mathbf{x}\|_{2},$

where we use the triangle inequality in the second to last step. We also have
that:

$\|(\theta_{1}-\theta_{2})^{\top}\mathbf{x}\|_{2}\leq\|\theta_{1}-\theta_{2}\|_{F}\|\mathbf{x}\|_{2}\leq\|\theta_{1}-\theta_{2}\|_{F},$
(42)

where we use Cauchy-Schwarz in the first inequality and assumption 5 in the
second. Thus:

$\log\frac{p(\mathcal{A}(\mathcal{D},\mathbf{x})=\mathbf{y})}{p(\mathcal{A}(\mathcal{D}^{\prime},\mathbf{x})=\mathbf{y})}\leq\beta\|\theta_{1}-\theta_{2}\|_{F}.$
(43)

Combining Equation 43 with Lemma 1 yields:

$\log\frac{p(\mathcal{A}(\mathcal{D},\mathbf{x})=\mathbf{y})}{p(\mathcal{A}(\mathcal{D}^{\prime},\mathbf{x})=\mathbf{y})}\leq\beta\|\theta_{1}-\theta_{2}\|_{F}\leq\frac{\beta
2K}{N\lambda}.$ (44)

If we choose $\beta=\frac{N\lambda\epsilon}{2K}$, we achieve
$\epsilon$-differential privacy when releasing the predictions on a single
example $\mathbf{x}$. If we choose $\beta=\frac{N\lambda\epsilon}{2KB}$ then
by standard compositional arguments of differential privacy [12] we achieve
$\epsilon$-differential privacy with a budget of $B$ test queries. ∎

Algorithm 7 Multi-class Gaussian prediction sensitivity.

Inputs: Privacy parameters $\epsilon$ and $\delta$, non-private model
$\phi^{\prime}(\cdot)$, test example $\hat{\mathbf{x}}$, and budget $B$.

Output: $\hat{\mathbf{y}}_{\textrm{priv}}$, the prediction which is
$(\epsilon,\delta)$-differentially private with respect to the training
dataset $\mathcal{D}$.

Let $\sigma^{\prime}=\frac{2K\alpha}{N\lambda\sqrt{2\epsilon^{*}}}$ with
$\alpha$ computed using Algorithm 2, $\epsilon^{*}=\epsilon/B$, and
$\delta^{*}=\delta/B$.

Minimize $\sigma^{\prime\prime}=\frac{2K\alpha}{N\lambda\sqrt{2\epsilon^{*}}}$
over $\delta^{\prime}\in(0,\delta-B\delta^{*})$ using linear search where:

$\epsilon^{*}=\sqrt{2/B}\left(\sqrt{\ln(1/\delta^{\prime})+\epsilon}-\sqrt{\ln(1/\delta^{\prime})}\right)$,

$\delta^{*}=(\delta-\delta^{\prime})/B$,

and where $\alpha$ is computed using Algorithm 2.

Sample $\mathbf{b}$ from the distribution in Equation 13 with
$\sigma=\min(\sigma^{\prime},\sigma^{\prime\prime})$.

Compute
$\hat{\mathbf{y}}_{\textrm{priv}}=\phi^{\prime}(\hat{\mathbf{x}};\theta)+\mathbf{b}$.

######  Theorem 6.

Given assumptions 1, 2, 3, 4, and 5, the Gaussian prediction sensitivity
method in Algorithm 7 is $(\epsilon,\delta)$-differentially private for
$\delta\in(0,1)$.

###### Proof.

As in the proof of Theorem 2, we bound the $L_{2}$ sensitivity and apply
Theorem 9 of [2].

Let $\theta_{1}=\operatorname*{arg\,min}_{\theta}J(\theta;\mathcal{D})$ and
similarly
$\theta_{2}=\operatorname*{arg\,min}_{\theta}J(\theta;\mathcal{D}^{\prime})$.
From Theorem 5 we have:

$\max_{\mathcal{D},\mathcal{D}^{\prime},\mathbf{x}}\|\theta_{1}^{\top}\mathbf{x}-\theta_{2}^{\top}\mathbf{x}\|_{2}\leq\frac{2K}{N\lambda}.$
(45)

Recall from our description of the Gaussian model sensitivity method that
Theorem 8 of [2] states that the Gaussian mechanism with standard deviation
$\sigma^{\prime}$ is $(\epsilon^{*},\delta^{*})$-differentially private if and
only if:

$\Phi\left(\frac{\Delta_{2}f}{2\sigma^{\prime}}-\frac{\epsilon^{*}\sigma^{\prime}}{\Delta_{2}f}\right)-e^{\epsilon^{*}}\Phi\left(-\frac{\Delta_{2}f}{2\sigma^{\prime}}-\frac{\epsilon^{*}\sigma^{\prime}}{\Delta_{2}f}\right)\leq\delta^{*},$
(46)

where $\Delta_{2}f$ is the $L_{2}$ sensitivity of $f(\cdot)$.

Combining Equation 45 with Theorem 9 of [2], we can obtain
$(\epsilon^{*},\delta^{*})$-differential privacy on a single prediction by
setting:

$\sigma^{\prime\prime}=\frac{2K\alpha}{N\lambda\sqrt{2\epsilon^{*}}},$ (47)

where $\alpha$ is defined in Algorithm 2.

Theorem 1.1 of [14] states that $B$ compositions of a
$(\epsilon^{*},\delta^{*})$-differentially private mechanism satisfies
$(\epsilon,\delta)$-differential privacy where:

$\epsilon=\sqrt{2B\ln(1/\delta^{\prime})}\epsilon^{*}+B\epsilon^{*}(e^{\epsilon^{*}}-1)/2,$
(48)

and:

$\delta=\delta^{\prime}+B\delta^{*}.$ (49)

We can solve for $\epsilon^{*}$ and $\delta^{*}$ in terms of $\epsilon$,
$\delta$ and $\delta^{\prime}$. Given that $\epsilon$ and $\delta$ are pre-
specified, this leaves $\delta^{\prime}$ to be determined.

Using the fact that $1+x\leq e^{x}$ for all $x$, we have:

$\sqrt{2B\ln(1/\delta^{\prime})}\epsilon^{*}+B(\epsilon^{*})^{2}/2\leq\sqrt{2B\ln(1/\delta^{\prime})}\epsilon^{*}+B\epsilon^{*}(e^{\epsilon^{*}}-1)/2.$
(50)

This is a quadratic in $\epsilon^{*}$ which we can solve to obtain:

$\epsilon^{*}=\sqrt{2/B}\left(\sqrt{\ln(1/\delta^{\prime})+\epsilon}-\sqrt{\ln(1/\delta^{\prime})}\right).$
(51)

We also have:

$\delta^{*}=(\delta-\delta^{\prime})/B.$ (52)

The algorithm will be $(\epsilon,\delta)$-differentially private with respect
to $B$ predictions for any $\epsilon^{*}$ and $\delta^{*}$ which satisfy the
above equations. Thus, for a given $\epsilon$, $\delta$ and $B$, we can choose
$\delta^{\prime}$ which minimizes $\sigma^{\prime\prime}$ in Equation 47 and
achieve $(\epsilon,\delta)$-differential privacy with a budget $B$.

For small values of the budget $B$, the standard composition theorem of
$(\epsilon,\delta)$-differential privacy (_e.g._ , Theorem 3.16 of [10]) may
actually lead to smaller standard deviations in the Gaussian noise
distribution. Combining the standard composition theorem with Equation 45 and
Theorem 9 of [2], we can obtain $(\epsilon,\delta)$-differential privacy on a
single prediction by setting:

$\sigma^{\prime}=\frac{2K\alpha}{N\lambda\sqrt{2\epsilon^{*}}},$ (53)

where $\alpha$ is obtained via Algorithm 2 with $\epsilon^{*}=\epsilon/B$ and
$\delta^{*}\ \delta/B$.

Because both $\sigma^{\prime}$ and $\sigma^{\prime\prime}$ provide the
required differential privacy guarantee, so does the mechanism in Algorithm 7
that sets $\sigma=\min(\sigma^{\prime},\sigma^{\prime\prime})$. ∎

###  C.2 Subsample-and-Aggregate

The subsample-and-aggregate approach of [11] splits the training dataset
$\mathcal{D}$ into $T$ disjoint subsets of size
$\nicefrac{{|\mathcal{D}|}}{{T}}$. A set of $T$ models,
$\\{\phi^{\prime}_{1}(\cdot;\theta_{1}),\ldots,\phi^{\prime}_{T}(\cdot;\theta_{T})\\}$,
are learned, one for each subset, where $\phi^{\prime}_{t}(\cdot)$ outputs a
one-hot vector of size $C$. To make a prediction, the classifiers are combined
using a soft majority vote. For a given $\mathbf{x}$, the class label
$\mathbf{y}$ is predicted with probability proportional to:

$\exp\left(\beta\cdot|\\{t:t\in\\{1,\dots,T\\},\phi^{\prime}_{t}(\mathbf{x};\theta_{t})=\mathbf{y}\\}|\right).$
(54)

Privacy by classifying with probability proportional to an exponentiated
utility function is known as the exponential mechanism [13] and is due to
[28].

Algorithm 8 Subsample-and-aggregate.

Inputs: Privacy parameters $\epsilon$ and $\delta$, training dataset
$\mathcal{D}$, a number of models $T$, and a set of queries
$\mathcal{Q}=\\{\hat{\mathbf{x}}_{1},\dots,\hat{\mathbf{x}}_{B}\\}$.

Output: $\\{\hat{\mathbf{y}}_{1},\dots\hat{\mathbf{y}}_{B}\\}$, the
predictions which are $\epsilon$-differentially private with respect to the
training dataset $\mathcal{D}$.

Partition $\mathcal{D}$ into $T$ disjoint subsets
$\\{\mathcal{D}_{t}:t=1,\ldots,T\\}$ of size
$\lfloor\nicefrac{{|\mathcal{D}|}}{{T}}\rfloor$.

for all $\mathcal{D}_{t}$ do

Train classifier $\phi^{\prime}_{t}(\cdot;\theta_{t})$ on $\mathcal{D}_{t}$.

end for

if $\delta>0$ then

Set
$\beta=\max\left(\epsilon/B,\sqrt{2/B}\left(\sqrt{\ln(1/\delta)+\epsilon}-\sqrt{\ln(1/\delta)}\right)\right)$.

else

Set $\beta=\epsilon/B$.

end if

for b = 1, …, B do

Sample $\hat{\mathbf{y}}_{b}$ with probability proportional to Equation 54.

end for

######  Theorem 7.

The subsample-and-aggregate method in Algorithm 8 with $\beta=\epsilon/B$ is
$\epsilon$-differentially private.

###### Proof.

Consider any two datasets $\mathcal{D}$ and $\mathcal{D}^{\prime}$ which
differ by at most one example. Since the classifiers
$\phi^{\prime}_{t}(\cdot)$ are trained on disjoint subsets of $\mathcal{D}$,
at most one classifier can change its prediction for any given instance
$\mathbf{x}$ when we switch from training on $\mathcal{D}$ to
$\mathcal{D}^{\prime}$. If we let $\phi^{\prime}_{t}(\cdot;\theta)$ denote
classifiers trained on $\mathcal{D}$ and
$\phi^{\prime}_{t}(\cdot;\theta^{\prime})$ denote classifiers trained on
$\mathcal{D}^{\prime}$, we have:

$\operatorname*{arg\,max}_{\mathcal{D},\mathcal{D}^{\prime},\mathbf{x},\mathbf{y}}\Big{|}|\\{t:t\in\\{1,\dots,T\\},\phi^{\prime}_{t}(\mathbf{x};\theta_{t})=\mathbf{y}\\}|-|\\{t:t\in\\{1,\dots,T\\},\phi^{\prime}_{t}(\mathbf{x};\theta^{\prime}_{t})=\mathbf{y}\\}|\Big{|}\leq
1.$ (55)

In other words, the sensitivity of the majority vote is $1$. For all adjacent
datasets, $\mathcal{D}$ and $\mathcal{D}^{\prime}$, all examples $\mathbf{x}$,
and all class labels $\mathbf{y}$:

$\displaystyle\log$
$\displaystyle\frac{p(\mathcal{A}(\mathbf{x},\mathcal{D})=\mathbf{y})}{p(\mathcal{A}(\mathbf{x},\mathcal{D}^{\prime})=\mathbf{y})}=\log\frac{\exp(\beta\cdot|\\{t:t\in\\{1,\dots,T\\},\phi^{\prime}_{t}(\mathbf{x};\theta_{t})=\mathbf{y}\\}|)}{\exp(\beta\cdot|\\{t:t\in\\{1,\dots,T\\},\phi^{\prime}_{t}(\mathbf{x};\theta^{\prime}_{t})=\mathbf{y}\\}|)}$
(56)
$\displaystyle\leq\beta\cdot|\\{t:t\in\\{1,\dots,T\\},\phi^{\prime}_{t}(\mathbf{x};\theta_{t})=\mathbf{y}\\}|-\beta\cdot|\\{t:t\in\\{1,\dots,T\\},\phi^{\prime}_{t}(\mathbf{x};\theta^{\prime}_{t})=\mathbf{y}\\}|$
(57)
$\displaystyle\leq\beta\Big{|}|\\{t:t\in\\{1,\dots,T\\},\phi^{\prime}_{t}(\mathbf{x};\theta_{t})=\mathbf{y}\\}|-|\\{t:t\in\\{1,\dots,T\\},\phi^{\prime}_{t}(\mathbf{x};\theta^{\prime}_{t})=\mathbf{y}\\}|\Big{|}$
(58) $\displaystyle\leq\beta,$ (59)

where we use Equation 55 in the second to last step.

Thus if we set $\beta=\epsilon/B$, by standard compositional arguments [12],
we achieve $\epsilon$-differential privacy with a budget of $B$ test queries
by predicting $\mathbf{y}$ with probability proportional to Equation 54. ∎

We can achieve a better scaling of $\beta$ with the budget $B$ by letting
$\delta>0$ and relying on the advanced composition theorem [15].

######  Theorem 8.

The subsample-and-aggregate method in Algorithm 8 with
$\beta=\max(\beta^{\prime},\beta^{\prime\prime})$, where
$\beta^{\prime}=\epsilon/B$ and
$\beta^{\prime\prime}=\sqrt{2/B}\left(\sqrt{\ln(1/\delta)+\epsilon}-\sqrt{\ln(1/\delta)}\right)$,
is $(\epsilon,\delta)$-differentially private.

###### Proof.

From Theorem 7, the subsample-and-aggregate method with $B=1$ is
$(\beta,0)$-differentially private.

Theorem 1.1 of [14] states that $B$ compositions of a
$(\beta,0)$-differentially private mechanism satisfies
$\left(\sqrt{2B\ln(1/\delta)}\beta+B\beta(e^{\beta}-1)/2,\delta\right)$. We
can solve for $\beta$ such that the subsample-and-aggregate algorithm with a
budget of $B$ satisfies $(\epsilon,\delta)$-differential privacy. Using the
fact that $1+x\leq e^{x}$ for all $x$, we have:

$\sqrt{2B\ln(1/\delta)}\beta+B\beta^{2}/2\leq\sqrt{2B\ln(1/\delta)}\beta+B\beta(e^{\beta}-1)/2.$
(60)

Hence if $\sqrt{2B\ln(1/\delta)}\beta+B\beta^{2}/2\leq\epsilon$ then the
resulting algorithm will satisfy $(\epsilon,\delta)$-differential privacy.
This is a quadratic in $\beta$ which we can solve to obtain:

$\beta=\sqrt{2/B}\left(\sqrt{\ln(1/\delta)+\epsilon}-\sqrt{\ln(1/\delta)}\right).$
(61)

If this value of $\beta$ is smaller than $\epsilon/B$, we can use Theorem 7
instead and set $\beta=\epsilon/B$. ∎

##  Appendix D Multi-class Logistic Loss

In practice, we need to specify $\ell(\theta^{\top}\mathbf{x},\mathbf{y})$ and
bound $\|\nabla\ell\|_{2}$ for the model sensitivity and loss perturbation
methods. The commonly used multi-class logistic loss is given by:

$\ell(\mathbf{a},\mathbf{y})=\sum_{i=1}^{C}y_{i}\log\frac{e^{a_{i}}}{\sum_{j=1}^{C}e^{a_{j}}},$
(62)

where, for linear models, $\mathbf{a}=\theta^{\top}\mathbf{x}$.

######  Theorem 9.

The Lipschitz constant of the multi-class logistic loss (Equation 62) is
$K=\sqrt{2}$.

###### Proof.

Since $\mathbf{y}\in\Delta^{C}$, we can write Equation 62 as:

$\ell(\mathbf{a},\mathbf{y})=\mathbf{y}^{\top}\mathbf{a}-\log Z,$ (63)

where $Z=\sum_{j=1}^{C}e^{a_{j}}$, which has a gradient given by:

$\nabla\ell=\mathbf{y}-\frac{1}{Z}e^{\mathbf{a}}.$ (64)

By Corollary 1 the maximum $L_{2}$ distance between any two points on the
probability simplex $\sqrt{2}$. Given that both
$\mathbf{y},\frac{1}{Z}e^{\mathbf{a}}\in\Delta^{C}$:

$\|\nabla\ell\|_{2}=\left\|\mathbf{y}-\frac{e^{\mathbf{a}}}{\sum_{j=1}^{C}e^{a_{j}}}\right\|_{2}\leq\sqrt{2}.$
(65)

∎

For the loss perturbation method we also need to bound the eigenvalues and the
rank of the Hessian of Equation 62 with respect to $\mathbf{a}$.

The Hessian of the multi-class logistic loss with respect to $\mathbf{a}$ is
given by:

$\nabla^{2}\ell=\text{diag}(\mathbf{p})-\mathbf{p}\mathbf{p}^{\top},$ (66)

where $\mathbf{p}=\frac{1}{Z}e^{\mathbf{a}}$ [5]. Since
$\nabla^{2}\ell\in\mathbb{R}^{C\times C}$, the rank is at most $C$.

######  Theorem 10.

The eigenvalues of the Hessian of the multi-class logistic loss are bounded by
$0.5$, _i.e._ :

$\lambda_{\max}(\nabla^{2}\ell(\theta,\mathbf{x},\mathbf{y}))\leq 0.5,$ (67)

for all $\theta,\mathbf{x}$ and $\mathbf{y}$.

###### Proof.

The Hessian of the multi-class logistic loss is given by Equation 66. We use
the fact that the eigenvalues of a square matrix $\mathbf{A}$ are contained in
the union of the Gerschgorin discs constructed from the rows of $\mathbf{A}$
[19]. The Gerschgorin disc of the $i$-th row of $\mathbf{A}$ has a center at
$A_{ii}$ and a radius of $\sum_{j\neq i}|A_{ij}|$. Hence, an upper bound on
the $i$-th Gerschgorin disc of
$\text{diag}(\mathbf{p})-\mathbf{p}\mathbf{p}^{\top}$ is given by:

$(p_{i}-p_{i}^{2})+p_{i}\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{C}p_{j}=p_{i}(1-p_{i})+p_{i}(1-p_{i})\leq 0.25+0.25=0.5,$
(68)

where we use the facts that $\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{C}p_{j}=1-p_{i}$ and $(1-p_{i})p_{i}\leq 0.25$ for
$p_{i}\in[0,1]$. Hence:

$\lambda_{\max}(\nabla^{2}\ell)\leq 0.5.$ (69)

∎

We rely on the following Corollary to bound the $L_{2}$ distance between two
points on the probability simplex, $\Delta^{C}$.

######  Corollary 1.

For any two points $\mathbf{u}$ and $\mathbf{v}$ on the
$(C\\!-\\!1)$-dimensional probability simplex their $L_{2}$ distance is no
more than $\sqrt{2}$, _i.e._ :

$\max_{\mathbf{u},\mathbf{v}\in\Delta^{C}}\|\mathbf{u}-\mathbf{v}\|_{2}\leq\sqrt{2}.$
(70)

###### Proof.

Bauer’s maximum principle states that a convex function on a convex set
attains its maximum at an extreme point [25]. The $L_{2}$ norm is a convex
function, the simplex $\Delta^{C}$ is a convex set. The extreme points of the
simplex are when $\mathbf{u}$ and $\mathbf{v}$ are vertices which for
$\Delta^{C}$ implies they are standard basis vectors. The $L_{2}$ distance
between two standard basis vectors is $\sqrt{2}$. ∎