# Generalized PTR: User-Friendly Recipes for Data-Adaptive Algorithms with
Differential Privacy

Rachel Redberg  Yuqing Zhu  Yu-Xiang Wang
University of California  Santa Barbara
{rredberg, yuqingzhu<EMAIL_ADDRESS>

###### Abstract

The “Propose-Test-Release” (PTR) framework (Dwork and Lei, 2009) is a classic
recipe for designing differentially private (DP) algorithms that are data-
adaptive, i.e. those that add less noise when the input dataset is “nice”. We
extend PTR to a more general setting by privately testing _data-dependent
privacy losses_ rather than _local sensitivity_ , hence making it applicable
beyond the standard noise-adding mechanisms, e.g. to queries with unbounded or
undefined sensitivity. We demonstrate the versatility of generalized PTR using
private linear regression as a case study. Additionally, we apply our
algorithm to solve an open problem from “Private Aggregation of Teacher
Ensembles (PATE)” (Papernot et al., 2017, 2018) — privately releasing the
entire model with a delicate data-dependent analysis.

##  1 Introduction

The guarantees of differential privacy (DP) (Dwork et al., 2006) are based on
worst-case outcomes across all possible datasets. A common paradigm is
therefore to add noise scaled by the _global sensitivity_ of a query $f$, i.e.
the maximum change in $f$ between any pair of neighboring datasets.

A given dataset $X$ might have a _local sensitivity_ that is much smaller than
the global sensitivity, in which case we can hope to add a smaller amount of
noise (calibrated to the local rather than the global sensitivity) while
achieving the same privacy guarantee. However, this must not be undertaken
naïvely – the local sensitivity is a dataset-dependent function and so
calibrating noise to the local sensitivity could leak information about the
dataset (Nissim et al., 2007).

The “Propose-Test-Release” (PTR) framework (Dwork and Lei, 2009) resolves this
issue by introducing a test to privately check whether a proposed bound on the
local sensitivity is valid. Only if the test “passes” is the output released
with noise calibrated to the proposed bound on the local sensitivity.

PTR is a powerful and flexible tool for designing data-adaptive DP algorithms,
but it has several limitations. First, it applies only to noise-adding
mechanisms which calibrate noise according to the sensitivity of a query.
Second, the test in “Propose-Test-Release” is computationally expensive for
all but a few simple queries such as privately releasing the median or mode.
Third, while some existing works (Decarolis et al., 2020; Kasiviswanathan et
al., 2013; Liu et al., 2021) follow the approach of testing “nice” properties
of a dataset before exploiting these properties in a private release to PTR
111We refer to these as PTR-like methods. , there has not been a systematic
recipe for _discovering_ which properties should be tested.

In this paper, we propose a generalization of PTR which addresses these
limitations. The centerpiece of our framework is a differentially private test
on the _data-dependent privacy loss_. This test does not directly consider the
local sensitivity of a query and is therefore not limited to additive noise
mechanisms. Moreover, in many cases, the test can be efficiently implemented
by privately releasing a high-probability upper bound, thus avoiding the need
to search an exponentially large space of datasets. Furthermore, the
derivation of the test itself often spells out exactly what properties of the
input dataset need to be checked, which streamlines the design of data-
adaptive DP algorithms.

Our contributions are summarized as follows:

  1. 1.

We propose a generalization of PTR which can handle algorithms beyond noise-
adding mechanisms. Generalized PTR allows us to plug in _any_ data-dependent
DP analysis to construct a high-probability DP test that adapts to favorable
properties of the input dataset – without painstakingly designing each test
from scratch.

  2. 2.

We demonstrate that many existing examples of PTR and PTR-like algorithms can
be unified under the generalized PTR framework, sometimes resulting in a
tighter analysis (see an example of report-noisy-max in Sec A.1).

  3. 3.

We show that one can publish a DP model through privately upper-bounding a
one-dimensional statistic — no matter how complex the output space of the
mechanism is. We apply this result to solve an open problem from PATE
(Papernot et al., 2017, 2018).

  4. 4.

Our results broaden the applicability of private hyper-parameter tuning (Liu
and Talwar, 2019; Papernot and Steinke, 2021) in enabling joint-parameter
selection of DP-specific parameters (e.g., noise level) and native parameters
of the algorithm (e.g., learning rate, regularization weight), which may
jointly affect the data-dependent DP losses.

##  2 Related Work

Data-dependent DP algorithms. Privately calibrating noise to the local
sensitivity is a well-studied problem. One approach is to add noise calibrated
to the smooth sensitivity (Nissim et al., 2007), an upper bound on the local
sensitivity which changes slowly between neighboring datasets. An alternative
to this – and the focus of our work – is Propose-Test-Release (PTR) (Dwork and
Lei, 2009), which works by calculating the distance $\mathcal{D}_{\beta}(X)$
to the nearest dataset to $X$ whose local sensitivity violates a proposed
bound $\beta$. The PTR algorithm then adds noise to $\mathcal{D}_{\beta}(X)$
before testing whether this privately computed distance is sufficiently large.

PTR spin-offs abound. Notable examples include stability-based methods
(Thakurta and Smith, 2013) (stable local sensitivity of $0$ near the input
data) and privately releasing upper bounds of local sensitivity
(Kasiviswanathan et al., 2013; Liu et al., 2021; Decarolis et al., 2020). We
refer readers to Chapter 3 of Vadhan (2017) for a concise summary of these
classical results. Recent work (Wang et al., 2022) has provided Rényi DP
bounds for PTR and demonstrated its applications to robust DP-SGD. Our work
(see Section 5.2) also considers applications of PTR in data-adaptive private
deep learning: Instead of testing the local sensitivity of each gradient step
as in Wang et al. (2022), our PTR-based PATE algorithm tests the data-
dependent privacy loss as a whole.

Liu et al. (2021) proposed a new variant called High-dimensional Propose-Test-
Release (HPTR). HPTR provides a systematic way of solving DP statistical
estimation problems by using the exponential mechanism (EM) with carefully
constructed scores based on certain one-dimensional robust statistics, which
have stable local sensitivity bounds. HPTR focuses on designing data-adaptive
DP mechanisms from scratch; our method, in contrast, converts existing
randomized algorithms (including EM and even some that do not satisfy DP) into
those with formal DP guarantees. Interestingly, our proposed method also
depends on a one-dimensional statistic of direct interest: the data-dependent
privacy loss.

Data-dependent DP losses. The flip side of data-dependent DP algorithms is the
study of data-dependent DP losses (Papernot et al., 2018; Soria-Comas et al.,
2017; Wang, 2017), which fix the randomized algorithm but parameterize the
resulting privacy loss by the specific input dataset. For example: In the
simple mechanism that adds Laplace noise with parameter $b$, data-dependent DP
losses are $\epsilon(X)=\Delta_{\text{LS}}(X)/b$. The data-dependent DP losses
are often much smaller than the DP loss, but they themselves depend on the
data and thus may reveal sensitive information; algorithms satisfying a data-
dependent privacy guarantee are not formally DP with guarantees any smaller
than that of the worst-case. Existing work has considered privately publishing
these data-dependent privacy losses (Papernot et al., 2018; Redberg and Wang,
2021), but notice that privately publishing these losses does not improve the
DP parameter of the given algorithm. Part of our contribution is to resolve
this conundrum by showing that a simple post-processing step of the privately
released upper bound of $\epsilon(\text{Data})$ gives a formal DP algorithm.

Private hyper-parameter tuning. Our work has a nice connection with private
hyper-parameter tuning. Prior work (Liu and Talwar, 2019; Papernot and
Steinke, 2021) requires each candidate configuration to be released with the
same DP (or Rényi DP) parameter set. Another hidden assumption is that the
parameters must not be privacy-correlated (i.e., parameter choice will not
change the privacy guarantee). Otherwise we need to use the largest DP bound
across all candidates. For example, Liu and Talwar (2019) show that if each
mechanism (instantiated with one group of hyper-parameters) is
$(\epsilon,0)$-DP, then running a random number of mechanisms and reporting
the best option satisfies $(3\epsilon,0)$-DP. Our work directly generalizes
the above results by (1) considering a wide range of hyper-parameters, either
privacy-correlated or not; and (2) requiring only that individual candidates
to have a _testable_ data-dependent DP.

##  3 Preliminaries

Datasets $X,X^{\prime}\in\mathcal{X}$ are neighbors if they differ by no more
than one datapoint – i.e., $X\simeq X^{\prime}$ if $d(X,X^{\prime})\leq 1$. We
will define $d(\cdot)$ to be the number of coordinates that differ between two
datasets of the same size $n$: $d(X,Y)=\\#\\{i\in[n]:X_{i}\neq Y_{i}\\}$.

We use $||\cdot||$ to denote the radius of the smallest Euclidean ball that
contains the input set, e.g. $||\mathcal{X}||=\sup_{x\in\mathcal{X}}||x||$.

The parameter $\phi$ denotes the privacy parameters associated with a
mechanism (e.g. noise level, regularization). $\mathcal{M}_{\phi}$ is a
mechanism parameterized by $\phi$. For mechanisms with continuous output
space, we will take $\text{Pr}[\mathcal{M}(X)=y]$ to be the probability
density function of $\mathcal{M}(X)$ at $y$.

######  Definition 3.1 (Differential privacy (Dwork et al., 2006)).

Fix $\epsilon,\delta\geq 0$. A randomized algorithm
$\mathcal{M}:\mathcal{X}\rightarrow\mathcal{S}$ satisfies
$(\epsilon,\delta)$-DP if for all neighboring datasets $X\simeq X^{\prime}$
and for all measurable sets $S\subset\mathcal{S}$,

$\text{Pr}\big{[}\mathcal{M}(X)\in S\big{]}\leq
e^{\epsilon}\text{Pr}\big{[}\mathcal{M}(X^{\prime})\in S\big{]}+\delta.$

Suppose we wish to privately release the output of a real-valued function
$f:\mathcal{X}\rightarrow\mathcal{R}$. We can do so by calculating the _global
sensitivity_ $\Delta_{GS}$, calibrating the noise scale to the global
sensitivity and then adding sampled noise to the output.

######  Definition 3.2 (Local / Global sensitivity).

The local $\ell_{*}$-sensitivity of a function $f$ is defined as
$\Delta_{LS}(X)=\max\limits_{X\simeq X^{\prime}}||f(X)-f(X^{\prime})||_{*}$
and the global sensitivity of $f$ is $\Delta_{GS}=\sup_{X}\Delta_{LS}(X)$.

###  3.1 Propose-Test-Release

Calibrating the noise level to the local sensitivity $\Delta_{LS}(X)$ of a
function would allow us to add less noise and therefore achieve higher utility
for releasing private queries. However, the local sensitivity is a data-
dependent function and naïvely calibrating the noise level to $\Delta_{LS}(X)$
will not satisfy DP.

PTR resolves this issue in a three-step procedure: propose a bound on the
local sensitivity, privately test that the bound is valid (with high
probability), and if so calibrate noise according to the bound and release the
output.

PTR privately computes the distance $\mathcal{D}_{\beta}(X)$ between the input
dataset $X$ and the nearest dataset $X^{\prime\prime}$ whose local sensitivity
exceeds the proposed bound $\beta$:

$\displaystyle\mathcal{D}_{\beta}(X)=\min\limits_{X^{\prime\prime}}\\{d(X,X^{\prime\prime}):\Delta_{LS}(X^{\prime\prime})>\beta\\}.$

Algorithm 1 Propose-Test-Release (Dwork and Lei, 2009)

1: Input: Dataset $X$; privacy parameters $\epsilon,\delta$; proposed bound
$\beta$ on $\Delta_{LS}(X)$; query function
$f:\mathcal{X}\rightarrow\mathbb{R}$.

2: if
$\mathcal{D}_{\beta}(X)+\text{Lap}\left(\frac{1}{\epsilon}\right)\leq\frac{\log(1/\delta)}{\epsilon}$
then output $\perp$,

3: else release $f(X)+\text{Lap}\left(\frac{\beta}{\epsilon}\right)$.

######  Theorem 3.3.

Algorithm 1 satisfies ($2\epsilon,\delta$)-DP. (Dwork and Lei, 2009)

Rather than proposing an arbitrary threshold $\beta$, one can also privately
release an upper bound of the local sensitivity and calibrate noise according
to this upper bound. This was used for node DP in graph statistics
(Kasiviswanathan et al., 2013), and for fitting topic models using spectral
methods (Decarolis et al., 2020).

##  4 Generalized PTR

This section introduces the generalized PTR framework. We first formalize the
notion of _data-dependent_ differential privacy that conditions on an input
dataset $X$.

######  Definition 4.1 (Data-dependent privacy).

Suppose we have $\delta>0$ and a function
$\epsilon:\mathcal{X}\rightarrow\mathbb{R}$. We say that mechanism
$\mathcal{M}$ satisfies ($\epsilon(X),\delta$) data-dependent DP222We will
sometimes write that $\mathcal{M}(X)$ satisfies $\epsilon(X)$ data-dependent
DP with respect to $\delta$. for dataset $X$ if for all possible output sets
$S$ and neighboring datasets $X^{\prime}$,

$\displaystyle\text{Pr}\big{[}\mathcal{M}(X)\in S\big{]}$ $\displaystyle\leq
e^{\epsilon(X)}\text{Pr}\big{[}\mathcal{M}(X^{\prime})\in S\big{]}+\delta,$
$\displaystyle\text{Pr}\big{[}\mathcal{M}(X^{\prime})\in S\big{]}$
$\displaystyle\leq e^{\epsilon(X)}\text{Pr}\big{[}\mathcal{M}(X)\in
S\big{]}+\delta.$

In generalized PTR, we propose a value $\phi$ for the randomized algorithm
$\mathcal{M}$, which could be a noise scale or regularization parameter – or a
set including both. For example, $\phi=(\lambda,\gamma)$ in Example 4.4. We
then say that $\mathcal{M}_{\phi}$ is the mechanism $\mathcal{M}$
parameterized by $\phi$, and $\epsilon_{\phi}(X)$ its data-dependent DP.

The following example illustrates how to derive the data-dependent DP for a
familiar friend – the Laplace mechanism.

######  Example 4.2.

(_Data-dependent DP of Laplace Mechanism._) Given a function
$f:\mathcal{X}\rightarrow\mathbb{R}$, we will define

$\displaystyle\mathcal{M}_{\phi}(X)=f(X)+\text{Lap}\left(\phi\right).$

We then have

$\displaystyle\log\dfrac{\emph{Pr}[\mathcal{M}_{\phi}(X)=y]}{\emph{Pr}[\mathcal{M}_{\phi}(X^{\prime})=y]}$
$\displaystyle\leq\dfrac{|f(X)-f(X^{\prime})|}{\phi}.$

Maximizing the above calculation over all possible outputs $y$ and using
Definition 4.1,

$\displaystyle\epsilon_{\phi}(X)=\max\limits_{X^{\prime}:X^{\prime}\simeq
X}\frac{|f(X)-f(X^{\prime})|}{\phi}=\frac{\Delta_{LS}(X)}{\phi}.$

The data-dependent DP $\epsilon_{\phi}(X)$ is a function of both the dataset
$X$ and the parameter $\phi$. Maximizing $\epsilon_{\phi}(X)$ over $X$
recovers the standard DP guarantee of running $\mathcal{M}$ with parameter
$\phi$.

Algorithm 2 Generalized Propose-Test-Release

1: Input: Dataset $X$; mechanism
$\mathcal{M}_{\phi}:\mathcal{X}\rightarrow\mathcal{R}$ and its privacy budget
$\epsilon,\delta$; $(\hat{\epsilon},\hat{\delta})$-DP test $\mathcal{T}$;
false positive rate $\leq\delta^{\prime}$; data-dependent DP function
$\epsilon_{\phi}(\cdot)$ w.r.t. $\delta$.

2: if not $\mathcal{T}(\mathcal{X})$ then output $\perp$,

3: else release $\theta=\mathcal{M}_{\phi}(X).$

######  Theorem 4.3 (Privacy guarantee of generalized PTR).

Consider a proposal $\phi$ and a data-dependent DP function
$\epsilon_{\phi}(X)$ w.r.t. $\delta$. Suppose that we have an
($\hat{\epsilon},\hat{\delta}$)-DP test
$\mathcal{T}:\mathcal{X}\rightarrow\\{0,1\\}$ such that when
$\epsilon_{\phi}(X)>\epsilon$,

$\displaystyle\mathcal{T}(X)=\begin{cases}0\text{ \>with probability
}1-\delta^{\prime},\\\ 1\text{\> with probability
}\delta^{\prime}.\end{cases}$

Then Algorithm 2 satisfies
($\epsilon+\hat{\epsilon},\delta+\hat{\delta}+\delta^{\prime}$)-DP.

###### Proof sketch.

There are three main cases to consider:

  1. 1.

We decide not to run $\mathcal{M}_{\phi}$.

  2. 2.

We decide to run $\mathcal{M}_{\phi}$ and $\epsilon_{\phi}(X)>\epsilon$;

  3. 3.

We decide to run $\mathcal{M}_{\phi}$ and $\epsilon_{\phi}(X)\leq\epsilon$.

In the first case, the decision to output $\perp$ is post-processing of an
$(\hat{\epsilon},\hat{\delta})$-DP mechanism and inherits its privacy
guarantees. The second case occurs when the $(\hat{\epsilon},\hat{\delta})$-DP
test "fails" (produces a false positive) and occurs with probability at most
$\delta^{\prime}$. The third case is a composition of an
$(\hat{\epsilon},\hat{\delta})$-DP algorithm and an ($\epsilon,\delta$)-DP
algorithm. ∎

Generalized PTR is a _strict_ generalization of Propose-Test-Release. For some
function $f$, define $\mathcal{M}_{\phi}$ and $\mathcal{T}$ as follows:

$\displaystyle\mathcal{M}_{\phi}(X)=f(X)+\text{Lap}(\phi);$
$\displaystyle\mathcal{T}(X)=\begin{cases}0&\text{ if\>\>
}\mathcal{D}_{\beta}(X)+\text{Lap}\left(\frac{1}{\epsilon}\right)>\frac{\log(1/\delta)}{\epsilon},\\\
1&\text{ otherwise.}\\\ \end{cases}$

Notice that our choice of parameterization is $\phi=\frac{\beta}{\epsilon}$,
where $\phi$ is the scale of the Laplace noise. In other words, we know from
Example 4.2 that $\epsilon_{\phi}(X)>\epsilon$ exactly when
$\Delta_{LS}(X)>\beta$.

For noise-adding mechanisms such as the Laplace mechanism, the sensitivity is
proportional to the privacy loss (in both the global and local sense, i.e.
$\Delta_{GS}\propto\epsilon$ and $\Delta_{LS}\propto\epsilon(X)$). Therefore
for these mechanisms the only difference between privately testing the local
sensitivity (Algorithm 1) and privately testing the data-dependent DP (Theorem
4.3) is a change of parameterization.

###  4.1 Limitations of local sensitivity

Why do we want to generalize PTR beyond noise-adding mechanisms? Compared to
classic PTR, the generalized PTR framework allows us to be more flexible in
both the type of test conducted and also the type of mechanism whose output we
wish to release. For many mechanisms, the local sensitivity either does not
exist or is only defined for specific data-dependent quantities (e.g., the
sensitivity of the score function in the exponential mechanism) rather than
the mechanism’s output.

The following example illustrates this issue.

######  Example 4.4 (Private posterior sampling).

Let $\mathcal{M}:\mathcal{X}\times\mathcal{Y}\to\Theta$ be a private posterior
sampling mechanism (Minami et al., 2016; Wang et al., 2015; Gopi et al., 2022)
for approximately minimizing $F_{X}(\theta)$.

$\mathcal{M}$ samples $\theta\sim P(\theta)\propto
e^{-\gamma(F_{X}(\theta)+0.5\lambda||\theta||^{2})}$ with parameters
$\gamma,\lambda$. Note that $\gamma,\lambda$ cannot be appropriately chosen
for this mechanism to satisfy DP without going through a sensitivity
calculation of $\arg\min F_{X}(\theta)$. In fact, the global and local
sensitivity of the minimizer is unbounded even in linear regression problems,
i.e when $F_{X}(\theta)=\frac{1}{2}||y-X\theta||^{2}.$

Output perturbation algorithms do work for the above problem when we
regularize, but they are known to be suboptimal in theory and in practice
(Chaudhuri et al., 2011). In Section 5.4 we demonstrate how to apply
generalized PTR to achieve a data-adaptive posterior sampling mechanism.

Even in the cases of noise-adding mechanisms where PTR seems to be applicable,
it does not lead to a tight privacy guarantee. Specifically, by an example of
privacy amplification by post-processing (Example A.1 in the appendix), we
demonstrate that the local sensitivity does not capture all sufficient
statistics for data-dependent privacy analysis and thus is loose.

###  4.2 Which $\phi$ to propose

The main limitation of generalized PTR is that one needs to “propose” a good
guess of parameter $\phi$. Take the example of $\phi$ being the noise level in
a noise-adding mechanism. Choosing too small a $\phi$ will result in a useless
output $\perp$, while choosing too large a $\phi$ will add more noise than
necessary. Finding this ’Goldilocks’ $\phi$ might require trying out many
different possibilities – each of which will consume privacy budget.

This section introduces a method to jointly tune privacy parameters (e.g.,
noise scale) along with parameters related only to the utility of an algorithm
(e.g., learning rate or batch size in stochastic gradient descent) – while
avoiding the $\perp$ output.

Algorithm 3 takes a list of parameters as input, runs generalized PTR with
each of the parameters, and returns the output with the best utility. We show
that the privacy guarantee with respect to $\epsilon$ is independent of the
number of $\phi$ that we try.

Formally, let $\phi_{1},...,\phi_{k}$ be a set of hyper-parameters and
$\tilde{\theta}_{i}\in\\{\perp,\text{Range}(\mathcal{M})\\}$ denotes the
output of running generalized PTR on a private dataset $X$ with $\phi_{i}$.
Let $X_{val}$ be a public validation set and $q(\tilde{\theta}_{i})$ be the
score of evaluating $\tilde{\theta}_{i}$ with $X_{val}$ (e.g., validation
accuracy). The goal is to select a pair $(\tilde{\theta}_{i}$, $\phi_{i})$
such that DP model $\tilde{\theta}_{i}$ maximizes the validation score.

The generalized PTR framework with privacy calibration is described in
Algorithm 3. The privacy guarantee of Algorithm 3 is an application of Liu and
Talwar (2019).

Algorithm 3 PTR with hyper-parameter selection

1: Input: Privacy budget per PTR algorithm ($\epsilon^{*},\delta^{*}$), cut-
off $T$, parameters $\phi_{1:k}$, flipping probability $\tau$ and validation
score function $q(\cdot)$.

2: Initialize the set $S=\varnothing$.

3: Draw $G$ from a geometric distribution $\mathcal{D}_{\tau}$ and let
$\hat{T}=\text{min}(T,G)$.

4: for i = 1 ,…, $\hat{T}$ do

5: pick a random $\phi_{i}$ from $\phi_{1:k}$.

6: evaluate $\phi_{i}$: $(\tilde{\theta}_{i},q(\tilde{\theta}_{i}))\leftarrow$
Algorithm 2($\phi_{i},(\epsilon^{*},\delta^{*})$).

7: $S\leftarrow S\cup\\{\tilde{\theta}_{i},q(\tilde{\theta}_{i})\\}$.

8: end for

9: Output the highest scored candidate from $S$.

######  Theorem 4.5 ( Theorem 3.4 Liu and Talwar (2019) ).

Fix any $\tau\in[0,1],\delta_{2}>0$ and let
$T=\frac{1}{\tau}\log\frac{1}{\delta_{2}}$. If each oracle access to Algorithm
2 is $(\epsilon^{*},\delta^{*})$-DP, then Algorithm 3 is
$(3\epsilon^{*}+3\sqrt{2\delta^{*}},\sqrt{2\delta^{*}}T+\delta_{2})$-DP.

The theorem implies that one can try a random number of $\phi$ while paying a
constant $\epsilon$. In practice, we can roughly set $\tau=\frac{1}{10k}$ so
that the algorithm is likely to test all $k$ parameters. We emphasize that the
privacy and the utility guarantee (stated in the appendix) is not our
contribution. But the idea of applying generalized PTR to enforce a uniform DP
guarantee over all choices of parameters with a data-dependent analysis is
new, and in our opinion, significantly broadens the applicability to generic
hyper-parameter tuning machinery from Liu and Talwar (2019).

###  4.3 Construction of the DP test

Classic PTR uses the Laplace mechanism to construct a differentially private
upper bound of $\mathcal{D}_{\beta}(X)$, the distance from input dataset $X$
to the closest dataset whose local sensitivity exceeds the proposed bound
$\beta$. The tail bound of the Laplace distribution then ensures that if
$\mathcal{D}_{\beta}(X)=0$ (i.e. if $\Delta_{LS}(X)>\beta$), then the output
will be released with only a small probability $\delta$.

The following theorem shows that we could instead use a differentially private
upper bound of the data-dependent DP $\epsilon_{\phi}(X)$ in order to test
whether to run the mechanism $\mathcal{M}_{\phi}$.

######  Theorem 4.6 (Generalized PTR with private upper bound).

Suppose we have a differentially private upper bound of $\epsilon_{\phi}(X)$
w.r.t. $\delta$ such that with probability at least $1-\delta^{\prime}$,
$\epsilon_{\phi}^{P}(X)>\epsilon_{\phi}(X)$. Further suppose we have an
$(\hat{\epsilon},\hat{\delta})$-DP test $\mathcal{T}$ such that

$\displaystyle T(X)$ $\displaystyle=\begin{cases}1&\text{ if
}\epsilon_{\phi}^{P}(X)<\epsilon,\\\ 0&\text{ otherwise}.\end{cases}$

Then Algorithm 2 is
$(\epsilon+\hat{\epsilon},\delta+\hat{\delta}+\delta^{\prime})$-DP.

In Section 5.2, we demonstrate that one can upper bound the data-dependent DP
through a modification of the smooth sensitivity framework applied on
$\epsilon_{\phi}(X)$. Moreover, in Section 5.4 we provide a direct application
of Theorem 4.6 with private linear regression by making use of the per-
instance DP technique (Wang, 2017).

The applications in Section 5 are illustrative of two distinct approaches to
constructing the DP test for generalized PTR:

  1. 1.

Private sufficient statistics release (used in the private linear regression
example of Section 5.4) specifies the data-dependent DP as a function of the
dataset and privately releases each data-dependent component.

  2. 2.

The second approach (used in the PATE example of Section 5.2) uses the smooth
sensitivity framework to privately release the data-dependent DP as a whole,
and then construct a high-confidence test using the Gaussian mechanism.

These two approaches cover most of the scenarios arising in data-adaptive
analysis. For example, in the appendix we demonstrate the merits of
generalized PTR in handling data-adaptive private generalized linear models
(GLMs) using private sufficient statistics release. Moreover, sufficient
statistics release together with our private hyper-parameter tuning (Algorithm
3) can be used to construct data-adaptive extensions of DP-PCA and Sparse-DP-
ERM (see details in the future work section).

##  5 Applications

In this section, we put into action our approaches to construct the DP test
and provide applications in private linear regression and PATE.

###  5.1 Private Linear Regression

(a) Bike dataset

(b) Elevators dataset

Figure 1: Differentially private linear regression algorithms on UCI datasets.
$y$-axis reports the MSE error with confidence intervals. $\epsilon$ is
evaluated with $\delta=1e-6$.

######  Theorem 5.1 ((Wang, 2017)).

For input data $X\in\mathcal{X}$ and $Y\in\mathcal{Y}$, define the following:

  * •

$\lambda_{\min}(X)$ denotes the smallest eigenvalue of $X^{T}X$;

  * •

$||\theta_{\lambda}^{*}||$ is the magnitude of the solution
$\theta_{\lambda}^{*}=(X^{T}X+\lambda I)^{-1}X^{T}Y$;

  * •

and
$L(X,\mathbf{y}):=||\mathcal{X}||(||\mathcal{X}||||\theta_{\lambda}^{*}||+||\mathcal{Y}||)$
is the local Lipschitz constant, denoted $L$ in brief.

For brevity, denote $\lambda^{*}=\lambda+\lambda_{\min}(X)$. The algorithm
used in Example 4.4 with parameter $\phi=(\lambda,\gamma)$ obeys
$(\epsilon_{\phi}(Z),\delta)$ data-dependent DP for each dataset $Z=(X,Y)$
with $\epsilon_{\phi}(Z)$ equal to

$\sqrt{\frac{\gamma L^{2}\log(2/\delta)}{\lambda^{*}}}+\frac{\gamma
L^{2}}{2(\lambda^{*}+||\mathcal{X}||^{2})}+\frac{1+\log(2/\delta)||\mathcal{X}||^{2}}{2(\lambda^{*})}.$

Notice that the data-dependent DP is a function of
$(\lambda_{\min},L,||\theta_{\lambda}^{*}||,\lambda,\gamma)$, where
$(\lambda_{\min},L,||\theta_{\lambda}^{*}||)$ are data-dependent quantities.
One can apply the generalized PTR framework as in the following example.

######  Example 5.2 (OPS with PTR).

We demonstrate here how to apply generalized PTR to the one-posterior sample
(OPS) algorithm, a differentially private mechanism which outputs one sample
from the posterior distribution of a Bayesian model with bounded log-
likelihood.

  * •

Propose $\phi=(\lambda,\gamma)$.

  * •

Based on $(\lambda,\gamma)$, differentially privately release
$\lambda_{min},||\theta_{\lambda}^{*}||,L$ with privacy budget
$(\epsilon,\delta/2)$.

  * •

Condition on a high probability event (with probability at least $1-\delta/2$)
of $\lambda_{min},||\theta_{\lambda}^{*}||,L$, test if
${\color[rgb]{0,0,1}\epsilon_{\phi}^{P}(X)}$ is smaller than the predefined
privacy budget $(\hat{\epsilon},\hat{\delta})$, where $\epsilon_{\phi}^{P}(X)$
denotes the sanitized data-dependent DP.

  * •

Based on the outcome of the test, decide whether to release $\theta\propto
e^{-\frac{\gamma}{2}||Y-X\theta||^{2}+\lambda||\theta||^{2}}$.

######  Theorem 5.3.

The algorithm outlined in Example 5.2 satisfies
$(\epsilon+\hat{\epsilon},\delta+\hat{\delta})$-DP.

The main idea of the above algorithm boils down to privately releasing all
data-dependent quantities in data-dependent DP, constructing high-probability
confidence intervals of these quantities, and then deciding whether to run the
mechanism $\mathcal{M}$ with the proposed parameters. We defer the details of
the privacy calibration of data-dependent quantities to the appendix.

One may ask why we cannot directly tune privacy parameters ($\lambda,\gamma$)
based on the sanitized data-dependent DP. This is because, in many scenarios,
data-dependent quantities depend on the choice of privacy parameters, e.g.,
$||\theta_{\lambda}^{*}||$ is a complicated function of $\lambda$. Thus, the
optimization on $\lambda$ becomes a circular problem — to solve $\lambda$, we
need to sanitize $||\theta_{\lambda}^{*}||$, which needs to choose a $\lambda$
to begin with. Alternatively, generalized PTR provides a clear and flexible
framework to test the validity of privacy parameters adapted to the dataset.

######  Remark 5.4.

The above “circular” issue is even more serious for generalized linear models
(GLMs) beyond linear regression. The data-dependent DP there involves a local
strong-convexity parameter, a complex function of the regularizer $\lambda$
and we only have zeroth-order access to. In the appendix, we demonstrate how
to apply generalized PTR to provide a generic solution to a family of private
GLMs where the link function satisfies a self-concordance assumption.

We next apply Algorithm 3 for Example 5.2 with UCI regression datasets.
Standard z-scoring is applied and each data point is normalize with a
Euclidean norm of 1. We consider $(60\%,10\%,30\%)$ splits for training,
validation and testing test.

Baselines

  * •

Output Perturbation (Outpert) (Chaudhuri et al., 2011):
$\theta=(X^{T}X+\lambda I)^{-1}X^{T}\bf{y}$. Release
$\hat{\theta}=\theta+\bf{b}$ with an appropriate $\lambda$, where $\bf{b}$ is
a Gaussian random vector.

  * •

Posterior sampling (OPS). Sample $\hat{\theta}\sim P(\theta)\propto
e^{-\gamma(F(\theta)+0.5\lambda||\theta||^{2})}$ with parameters
$\gamma,\lambda$.

  * •

Adaptive posterior sampling (AdaOPS) (Wang, 2018). Run OPS with
$(\lambda,\gamma)$ chosen adaptively according to the dataset.

Outpert and OPS serve as two non-adaptive baselines. In particular, we
consider OPS-Balanced (Wang, 2018), which chooses $\lambda$ to minimize a
data-independent upper bound of empirical risk and dominates other OPS
variants. AdaOPS is one state-of-the-art algorithm for adaptive private
regression, which automatically chooses $\lambda$ by minimizing an upper bound
of the data-dependent empirical risk.

We implement OPS-PTR as follows: propose a list of $\lambda$ through grid
search (we choose $k=30$ and $\lambda$ ranges from $[2.5,2.5^{10}]$ on a
logarithmic scale); instantiate Algorithm 3 with $\tau=0.1k$,
$T=\frac{1}{\tau}\log(1/\delta_{2})$ and $\delta_{2}=1/2\delta$; calibrate
$\gamma$ to meet the privacy requirement for each $\lambda$. sample
$\hat{\theta}$ using $(\lambda,\gamma)$ and return the one with the best
validation accuracy. Notice that we use a “no $\perp$” variant of Algorithm 2
as the calibration of $\gamma$ is clear given a fixed $\lambda$ and privacy
budget (see more details in the appendix). We can propose various combinations
of $(\lambda,\gamma)$ for more general applications.

Figure 1 demonstrates how the MSE error of the linear regression algorithms
varies with the privacy budget $\epsilon$. OutPert suffers from the large
global sensitivity of output $\theta$. OPS performs well but does not benefit
from the data-dependent quantities. AdaOPS is able to adaptively choose
$(\lambda,\gamma)$ based on the dataset, but suffers from the estimation error
of the data-dependent empirical risk. On the other hand, OPS-PTR selects a
$(\lambda,\gamma)$ pair that minimizes the empirical error on the validation
set directly, and the privacy parameter $\gamma$ adapts to the dataset thus
achieving the best result.

###  5.2 PATE

In this section, we apply the generalized PTR framework to solve an open
problem from the Private Aggregation of Teacher Ensembles (PATE) (Papernot et
al., 2017, 2018) — privately publishing the entire model through privately
releasing data-dependent DP losses. Our algorithm makes use of the smooth
sensitivity framework (Nissim et al., 2007) and the Gaussian mechanism to
construct a high-probability test of the data-dependent DP. The one-
dimensional statistical nature of data-dependent DP enables efficient
computations under the smooth sensitivity framework. Thus, this approach is
generally applicable for other private data-adaptive analysis beyond PATE.

PATE is a knowledge transfer framework for model-agnostic private learning. In
this framework, an ensemble of teacher models is trained on the disjoint
private data and uses the teachers’ aggregated consensus answers to supervise
the training of a “student” model agnostic to the underlying machine-learning
algorithms. By publishing only the aggregated answers and by the careful
analysis of the “consensus”, PATE has become a practical technique in recent
private model training.

The tight privacy guarantee of PATE heavily relies on a delicate data-
dependent DP analysis, for which the authors of PATE use the smooth
sensitivity framework to privately publish the data-dependent privacy cost.
However, it remains an open problem to show that the released model is DP
under data-dependent analysis. Our generalized PTR resolves this gap by
carefully testing a private upper bound of the data-dependent privacy cost.
Our algorithm is fully described in Algorithm 4, where the modification over
the original PATE framework is highlighted in blue.

Algorithm 4 takes the input of privacy budget
$(\epsilon^{\prime},\hat{\epsilon},\delta)$, unlabeled public data $x_{1:T}$
and $K$ teachers’ predictions on these data. The parameter $\epsilon$ denotes
the privacy cost of publishing the data-dependent DP and $\epsilon^{\prime}$
is the predefined privacy budget for testing. $n_{j}(x_{i})$ denotes the the
number of teachers that agree on label $j$ for $x_{i}$ and $C$ denotes the
number of classes. The goal is to privately release a list of plurality
outcomes — $\text{argmax}_{j\in[C]}n_{j}(x_{i})$ for $i\in[T]$ — and use these
outcomes to supervise the training of a “student” model in the public domain.
The parameter $\sigma_{1}$ denotes the noise scale for the vote count.

In their privacy analysis, Papernot et al. (2018) compute the data-dependent
$\mathrm{RDP}_{\sigma_{1}}(\alpha,X)$ of labeling the entire group of student
queries. $\mathrm{RDP}_{\sigma_{1}}(\alpha,X)$ can be orders of magnitude
smaller than its data-independent version if there is a strong agreement among
teachers. Note that $\mathrm{RDP}_{\sigma_{1}}(\alpha,X)$ is a function of the
RDP order $\alpha$ and the dataset $X$, analogous to our Definition 4.1 but
subject to RDP (Mironov, 2017).

######  Theorem 5.5 ((Papernot et al., 2018)).

If the top three vote counts of $x_{i}$ are $n_{1}>n_{2}>n_{3}$ and
$n_{1}-n_{2},n_{2}-n_{3}\gg\sigma_{1}$, then the data-dependent RDP of
releasing $\text{argmax}_{j}\\{n_{j}+\mathcal{N}(0,\sigma_{1}^{2})\\}$
satisfies $(\alpha,\exp\\{-2\alpha/{\sigma_{1}^{2}}\\}/\alpha)$-RDP and the
data-independent RDP (using the Gaussian mechanism) satisfies
$(\alpha,\frac{\alpha}{\sigma_{1}^{2}})$-RDP.

Algorithm 4 PATE with generalized PTR

1: Input: Unlabeled public data $x_{1:T}$, aggregated teachers prediction
$n(\cdot)$, privacy parameter $\hat{\epsilon},\epsilon^{\prime},\delta$, noisy
parameter $\sigma_{1}.$

2: Set $\alpha=\frac{2\log(2/\delta)}{\hat{\epsilon}}+1$,
$\sigma_{s}=\sigma_{2}=\sqrt{\frac{3\alpha+2}{\hat{\epsilon}}},\delta_{2}=\delta/2,$
smoothness parameter $\beta=\frac{0.2}{\alpha}$.

3: Compute noisy labels:
${y_{i}}^{p}\leftarrow\text{argmax}_{j\in[C]}\\{n_{j}(x_{i})+\mathcal{N}(0,\sigma_{1}^{2})\\}$
for all $i\in[1:T]$.

4: $\mathrm{RDP}_{\sigma_{1}}(\alpha,X)\leftarrow$ data-dependent RDP at the
$\alpha$-th order.

5: $SS_{\beta}(X)\leftarrow$ the smooth sensitivity of
$\mathrm{RDP}_{\sigma_{1}}^{\text{upper}}(\alpha,X)$.

6: Privately release
$\mu:=\log(SS_{\beta}(X))+\beta\cdot\mathcal{N}(0,\sigma_{2}^{2})+\sqrt{2\log(2/\delta_{2})}\cdot\sigma_{2}\cdot\beta$

7: $\mathrm{RDP}_{\sigma_{1}}^{\text{upper}}(\alpha)\leftarrow$ an upper bound
of data-dependent RDP through Lemma 5.6.

8: $\epsilon_{\sigma_{1}}\leftarrow$ DP guarantee converted from
$\mathrm{RDP}_{\sigma_{1}}^{\text{upper}}(\alpha).$

9: If $\epsilon^{\prime}\geq\epsilon_{\sigma_{1}}$ return a student model
trained using $(x_{1:T};y_{1:T}^{p})$.

10: Else return $\perp$.

However, $\mathrm{RDP}_{\sigma_{1}}(\alpha,X)$ is data-dependent and thus
cannot be revealed. The authors therefore privately publish the data-dependent
RDP using the smooth sensitivity framework (Nissim et al., 2007). The smooth
sensitivity calculates a smooth upper bound on the local sensitivity of
$\mathrm{RDP}_{\sigma_{1}}(\alpha,X)$, denoted as $SS_{\beta}(X)$, such that
$SS_{\beta}(X)\leq e^{\beta}SS_{\beta}(X^{\prime})$ for any neighboring
dataset $X$ and $X^{\prime}$. By adding Gaussian noise scaled by the smooth
sensitivity (i.e., release
$\epsilon_{\sigma_{1}}(\alpha,X)+SS_{\beta}(X)\cdot\mathcal{N}(0,\sigma_{s}^{2})$),
the privacy cost is safely published.

Unlike most noise-adding mechanisms, the standard deviation $\sigma_{s}$
cannot be published since $SS_{\beta}(X)$ is a data-dependent quantity.
Moreover, this approach fails to provide a valid privacy guarantee of the
noisy labels obtained through the PATE algorithm, as the published privacy
cost could be smaller than the real privacy cost. Our solution in Algorithm 4
looks like the following:

  * •

Privately release an upper bound of the smooth sensitivity $SS_{\beta}(X)$
with $e^{\mu}$.

  * •

Conditioned on a high-probability event of $e^{\mu}$, publish the data-
dependent RDP with $\mathrm{RDP}_{\sigma_{1}}^{\text{upper}}(\alpha)$.

  * •

Convert $\mathrm{RDP}_{\sigma_{1}}^{\text{upper}}(\alpha)$ back to the
standard DP guarantee using RDP to DP conversion at $\delta/2$.

  * •

Test if the converted DP is above the predefined budget $\epsilon^{\prime}$.

The following lemma states that
$\mathrm{RDP}_{\sigma_{1}}^{\text{upper}}(\alpha)$ is a valid upper bound of
the data-dependent RDP.

(a) High consensus and strong data-dependent DP

(b) Low consensus and low data-dependent DP

Figure 2: Privacy and utility tradeoffs with PATE. When $\sigma_{1}$ is
aligned, three algorithms provide the same utility. $y$-axis plots the privacy
cost of labeling $T=200$ public data with $\delta=10^{-5}$. The left figure
considers the high-consensus case, where the data-adaptive analysis is
preferred.

######  Lemma 5.6 (Private upper bound of data-dependent RDP).

We are given a RDP function $\mathrm{RDP}(\alpha,X)$ and a $\beta$-smooth
sensitivity bound $SS(\cdot)$ of $\mathrm{RDP}(\alpha,X)$. Let $\mu$ (defined
in Algorithm 4) denote the private release of $\log(SS_{\beta}(X))$. Let the
$(\beta,\sigma_{s},\sigma_{2})$-GNSS mechanism be

$\scriptstyle\mathrm{RDP}^{\text{upper}}(\alpha):=\mathrm{RDP}(\alpha,X)+SS_{\beta}(X)\cdot\mathcal{N}(0,\sigma_{s}^{2})+\sigma_{s}\sqrt{2\log(\frac{2}{\delta_{2}})}e^{\mu}$

Then, the release of $\mathrm{RDP}^{\text{upper}}(X)$ satisfies
$(\alpha,\frac{3\alpha+2}{2\sigma_{s}^{2}})$-RDP for all
$1<\alpha<\frac{1}{2\beta}$; w.p. at least $1-\delta_{2}$,
$\mathrm{RDP}^{\text{upper}}(\alpha)$ is an upper bound of
$\mathrm{RDP}(\alpha,X)$.

The proof (deferred to the appendix) makes use of the facts that: (1) the log
of $SS_{\beta}(X)$ has a bounded global sensitivity $\beta$ through the
definition of smooth sensitivity; (2) releasing
$\mathrm{RDP}_{\sigma_{1}}(\alpha,X)+SS_{\beta}(X)\cdot\mathcal{N}(0,\sigma_{s}^{2})$
is $(\alpha,\frac{\alpha+1}{\sigma_{s}^{2}})$-RDP (Theorem 23 from Papernot et
al. (2018)).

Now, we are ready to state the privacy guarantee of Algorithm 4.

######  Theorem 5.7.

Algorithm 4 satisfies $(\epsilon^{\prime}+\hat{\epsilon},\delta)$-DP.

In the proof, the choice of $\alpha$ ensures that the cost of the $\delta/2$
contribution (used in the RDP-to-DP conversion) is roughly $\hat{\epsilon}/2$.
Then the release of $\mathrm{RDP}_{\sigma_{1}}^{\text{upper}}(\alpha)$ with
$\sigma_{s}=\sqrt{\frac{2+3\alpha}{\hat{\epsilon}}}$ accounts for another cost
of $(\epsilon/2,\delta/2)$-DP.

Empirical results. We next empirically evaluate Algorithm 4 (PATE-PTR) on the
MNIST dataset. Following the experimental setup from Papernot et al. (2018),
we consider the training set to be the private domain, and the testing set is
used as the public domain. We first partition the training set into $400$
disjoint sets and $400$ teacher models, each trained individually. Then we
select $T=200$ unlabeled data from the public domain, with the goal of
privately labeling them. To illustrate the behaviors of algorithms under
various data distributions, we consider two settings of unlabeled data, high-
consensus and low-consensus. In the low-consensus setting, we choose $T$
unlabeled data such that there is no high agreement among teachers, so the
advantage of data-adaptive analysis is diminished. We provide further details
on the distribution of these two settings in the appendix.

Baselines. We consider the Gaussian mechanism as a data-independent baseline,
where the privacy guarantee is valid but does not take advantage of the
properties of the dataset. The data-dependent DP ( Papernot et al. (2018))
serves as a non-private baseline, which requires further sanitation. Note that
these two baselines provide different privacy analyses of the same algorithm
(see Theorem 5.5).

Figure 2 plots privacy-utility tradeoffs between the three approaches by
varying the noise scale $\sigma_{1}$. The purple region denotes a set of
privacy budget choices ($\hat{\epsilon}+\epsilon^{\prime}$ used in Algorithm
4) such that the utility of the three algorithms is aligned under the same
$\sigma_{1}$. In more detail, the purple region is lower-bounded by
$\hat{\epsilon}+\epsilon_{\sigma_{1}}$. We first fix
$\sigma_{s}=\sigma_{2}=15$ such that $\hat{\epsilon}$ is fixed. Then we
empirically calculate the average of $\epsilon_{\sigma_{1}}$ (the private
upper bound of the data-dependent DP) over $10$ trials. Running Algorithm 4
with any choice of $\hat{\epsilon}+\epsilon^{\prime}$ chosen from the purple
region implies $\epsilon^{\prime}>\epsilon_{\sigma_{1}}$. Therefore, PATE-PTR
will output the same noisy labels (with high probability) as the two
baselines.

Observation As $\sigma_{1}$ increases, the privacy loss of the Gaussian
mechanism decreases, while the data-dependent DP curve does not change much.
This is because the data-dependent DP of each query is a complex function of
both the noise scale and the data and does not monotonically decrease when
$\sigma_{1}$ increases (see more details in the appendix). However, the data-
dependent DP still dominates the Gaussian mechanism for a wide range of
$\sigma_{1}$. Moreover, PATE-PTR nicely interpolates between the data-
independent DP guarantee and the non-private data-adaptive DP guarantee. In
the low-consensus case, the gap between the data-dependent DP and the DP
guarantee of the Gaussian mechanism unsurprisingly decreases. Meanwhile, PATE-
PTR (the purple region) performs well when the noise scale is small but
deteriorates when the data-independent approach proves more advantageous. This
example demonstrates that using PTR as a post-processing step to convert the
data-dependent DP to standard DP is effective when the data-adaptive approach
dominates others.

##  6 Limitations and Future Work

One weakness of generalized PTR is that it requires a case-specific privacy
analysis. Have we simply exchanged the problem of designing a data-adaptive DP
algorithm with the problem of analyzing the data-dependent privacy loss? We
argue that this limitation is inherited from classic PTR. In situations where
classic PTR is not applicable, we’ve outlined several approaches to
constructing the DP test for our framework (see Sections 4.3 and 5.2).

Furthermore, the data-dependent privacy loss is often more straightforward to
compute than local sensitivity, and often exists in intermediate steps of
classic DP analysis already. Most DP analysis involves providing a high-
probability tail bound of the privacy loss random variable. If we stop before
taking the max over the input dataset, then we get a data-dependent DP loss
right away (as in Example 4.2).

There are several exciting directions for applying generalized PTR to more
problems. Sufficient statistics release and our private hyperparameter tuning
(Algorithm 3) can be used to construct data-adaptive extensions of DP-PCA
(Dwork et al., 2014) and Sparse-DP-ERM (Kifer et al., 2012). For DP-PCA we
could use our Algorithm 3 to tune the variance of the noise added to the
spectral gap; for Sparse-DP-ERM we would test the restricted strong convexity
parameter (RSC), i.e. not adding additional regularization if the RSC is
already large.

##  7 Conclusion

Generalized PTR extends the classic “Propose-Test-Release” framework to a more
general setting by testing the data-dependent privacy loss of an input
dataset, rather than its local sensitivity. In this paper we’ve provided
several examples – private linear regression with hyperparameter selection and
PATE – to illustrate how generalized PTR can enhance DP algorithm design via a
data-adaptive approach.

### Acknowledgments

The work was partially supported by NSF Award # 2048091 and the Google
Research Scholar Award. Yuqing was supported by the Google PhD Fellowship.

###### Contents

  1. 1 Introduction
  2. 2 Related Work
  3. 3 Preliminaries
    1. 3.1 Propose-Test-Release
  4. 4 Generalized PTR
    1. 4.1 Limitations of local sensitivity
    2. 4.2 Which $\phi$ to propose
    3. 4.3 Construction of the DP test
  5. 5 Applications
    1. 5.1 Private Linear Regression
    2. 5.2 PATE
  6. 6 Limitations and Future Work
  7. 7 Conclusion
  8. A Omitted examples in the main body
    1. A.1 Limits of the classic PTR in private binary voting
    2. A.2 Self-concordant generalized linear model (GLM)
    3. A.3 Differentially privately release $\lambda_{min}\left(\nabla^{2}F(\theta)\right)$
    4. A.4 Other applications of generalized PTR
  9. B Omitted proofs in Section 4
  10. C Experimental details
    1. C.1 Experimental details in private linear regression
    2. C.2 Details of PATE case study
  11. D Omitted proofs in private GLM
    1. D.1 Per-instance DP of GLM

##  Appendix A Omitted examples in the main body

In this appendix, we provide more examples to demonstrate the merits of
generalized PTR. We focus on a simple example of post-processed Laplace
mechanism in Section A.1 and then an example on differentially private
learning of generalized linear models in Section 4. In both cases, we observe
that generalized PTR provides data-adaptive algorithms with formal DP
guarantees, that are simple, effective and not previously proposed in the
literature (to the best of our knowledge).

###  A.1 Limits of the classic PTR in private binary voting

The following example demonstrates that classic PTR does not capture
sufficient data-dependent quantities even when the local sensitivity exists
and can be efficiently tested.

######  Example A.1.

Consider a binary class voting problem: $n$ users vote for a binary class
$\\{0,1\\}$ and the goal is to output the class that is supported by the
majority. Let $n_{i}$ denote the number of people who vote for the class $i$.
We consider the report-noisy-max mechanism:

$\displaystyle\mathcal{M}(X):\text{argmax}_{i\in[0,1]}n_{i}(X)+Lap(b),$

where $b=1/\epsilon$ denotes the scale of Laplace noise.

In the example, we will (1) demonstrate the merit of data-dependent DP; and
(2) empirically compare classic PTR with generalized PTR.

We first explicitly state the data-dependent DP.

######  Theorem A.2.

The data-dependent DP of the above example is

$\epsilon(X):=\max_{X^{\prime}}\\{|\log\frac{p}{p^{\prime}}|,|\log\frac{1-p}{1-p^{\prime}}|\\},$

where $p:=\Pr[n_{0}(X)+Lap(1/\epsilon)>n_{1}(X)+Lap(1/\epsilon)]$ and
$p^{\prime}:=\Pr[n_{0}(X^{\prime})+Lap(1/\epsilon)>n_{1}(X^{\prime})+Lap(1/\epsilon)]$.
There are four possible neighboring datasets
$X^{\prime}:n_{0}(X^{\prime})=\max(n_{0}(X)\pm
1,0),n_{1}(X^{\prime})=n_{1}(X)$ or
$n_{0}(X^{\prime})=n_{0}(X),n_{1}(X^{\prime})=\max(n_{1}(X)\pm 1,0)$.

In Figure 3(a), we empirically compare the above data-dependent DP with the
Laplace mechanism by varying the gap between the two vote counts
$|n_{0}(X)-n_{1}(X)|$. The noise scale is fixed to $\epsilon=10$. The data-
dependent DP substantially improves over the standard DP if the gap is large.
However, the data-dependent DP is a function of the dataset. We next
demonstrate how to apply generalized PTR to exploit the data-dependent DP.

Notice that the probability
$n_{0}(X)+Lap(1/\epsilon)>n_{1}(X)+Lap(1/\epsilon)$ is equal to the
probability that a random variable $Z:=X-Y$ exceeds
$\epsilon(n_{1}(X)-n_{0}(X))$, where $X,Y$ are two independent $\text{Lap}(1)$
distributions. We can compute the pdf of $Z$ through the convolution of two
Laplace distributions, which implies $f_{X-Y}(z)=\dfrac{1+|z|}{4e^{|z|}}$. Let
$t$ denote the difference between $n_{1}(X)$ and $n_{0}(X)$, i.e.,
$t=n_{1}(X)-n_{0}(X)$. Then we have

$p=\mathrm{Pr}[Z>\epsilon\cdot t]=\frac{2+\epsilon\cdot t}{4\exp(\epsilon\cdot
t)}$

Similarly,
$p^{\prime}=\dfrac{2+\epsilon\cdot(t+\ell)}{4\exp(\epsilon\cdot(t+\ell))}$,
where $\ell\in[-1,1]$ denotes adding or removing one data point to construct
the neighboring dataset $X^{\prime}$. Therefore, we can upper bound
$\log(p/{p^{\prime}})$ by

$\displaystyle\log\frac{p}{p^{\prime}}$ $\displaystyle=\frac{2+\epsilon\cdot
t}{4\exp(\epsilon\cdot
t)}\cdot\frac{4\exp(\epsilon(t+\ell))}{2+\epsilon\cdot(t+\ell)}$
$\displaystyle\leq\epsilon\cdot\log\bigg{(}\frac{2+\epsilon
t}{2+\epsilon(t+1)}\bigg{)}$
$\displaystyle=\epsilon\log\bigg{(}1-\frac{\epsilon}{2+\epsilon(t+1)}\bigg{)}$

Then we can apply generalized PTR by privately lower-bounding $t$.

On the other hand, the local sensitivity $\Delta_{LS}(X)$ of this noise-adding
mechanism is $0$ if $t>1$. Specifically, if the gap is larger than one, adding
or removing one user will not change the result. To apply classic PTR, we let
$\gamma(X)$ denote the distance to the nearest dataset $X^{{}^{\prime\prime}}$
such that $\Delta_{LS}>0$ and test if
$\gamma(X)+\text{Lap}(1/\epsilon)>\frac{\log(1/\delta)}{\epsilon}$. Notice in
this example that $\gamma(X)=\max(t-1,0)$ can be computed efficiently. We
provide the detailed implementation of these approaches.

  1. 1.

Gen PTR: lower bound $t$ with
$t^{p}=t-\frac{log(1/\delta)}{\tilde{\epsilon}}+\text{Lap}(1/\tilde{\epsilon})$.
Calculate an upper bound of data-dependent DP $\epsilon^{p}$ using Theorem A.2
with $t^{p}$. The algorithm then tests if $\epsilon^{p}$ is within an
predefined privacy budget $\epsilon^{\prime}$. If the test passes, the
algorithm returns $\text{argmax}_{i\in[0,1]}n_{i}(X)+Lap(1/\epsilon)$
satisfies $(\tilde{\epsilon}+\epsilon^{\prime},\delta)$-DP.

  2. 2.

classic PTR: lower bound $t$ with
$t^{p}=t-\frac{log(1/\delta)}{\tilde{\epsilon}}+\text{Lap}(1/\tilde{\epsilon})$.
If $t^{p}>1$, classic PTR outputs the ground-truth result else returns a
random class. This algorithm satisfies $(\tilde{\epsilon},\delta)$-DP.

  3. 3.

Laplace mechanism.
$\mathcal{M}(X):\text{argmax}_{i\in[0,1]}n_{i}(X)+Lap(1/\epsilon)$.
$\mathcal{M}$ is $(\epsilon,\delta)$-DP.

(a) data-dependent DP vs Laplace mechanism

(b) Privacy-utility tradeoff between three approaches.

Figure 3: In Figure 3(a), we compare the privacy guarantee by varying the gap.
In Figure 3(b) We fix $t=n_{0}(X)-n_{1}(X)=100$ and compare privacy cost when
the accuracy is aligned. Gen-PTR with any choice of privacy budget
($\tilde{\epsilon}+\epsilon^{\prime}$) chosen from the purple region would
achieve the same utility as Laplace mechanism but with a smaller privacy cost.
The curve of Gen-PTR is always below than that of the classic PTR, which
implies that Gen-PTR can result a tighter privacy analysis when the utility is
aligned.

We argue that though the Gen-PTR and the classic PTR are similar in privately
lower-bounding the data-dependent quantity $t$, the latter does not capture
sufficient information for data-adaptive analysis. That is to say, only
testing the local sensitivity restricts us from learning helpful information
to amplify the privacy guarantee if the test fails. In contrast, our
generalized PTR, where privacy parameters and the local sensitivity
parameterize the data-dependent DP, can handle those failure cases nicely.

To confirm this conjecture, Figure 3(b) plots a privacy-utility trade-off
curve between these three approaches. We consider a voting example with
$n_{0}(X)=n_{1}(X)+100$ and $t=100$, chosen such that the data-adaptive
analysis is favorable.

In Figure 3(b), we vary the noise scale $b=1/\epsilon$ between $[0,0.5]$. For
each choice of $b$, we plot the privacy guarantee of three algorithms when the
error rate is aligned. For Gen-PTR, we set $\tilde{\epsilon}=\frac{1}{2b}$ and
empirically calculate $\epsilon^{p}$ over $100000$ trials.

In the plot, when $\epsilon\ll\frac{\log(1/\delta)}{t}$, the classic PTR is
even worse than the Laplace mechanism. This is because the classic PTR is
likely to return $\perp$ while the Laplace mechanism returns
$\text{argmax}_{i\in[0,1]}n_{i}(X)+\text{Lap}(1/\epsilon)$, which contains
more useful information. Compared to the Laplace mechanism, Gen-PTR requires
an extra privacy allocation $\tilde{\epsilon}$ to release the gap $t$.
However, it still achieves an overall smaller privacy cost when the error rate
$\leq 10^{-5}$ (the purple region). Meanwhile, Gen-PTR dominates the classic
PTR (i.e., the dashed black curve is always below the blue curve). Note that
the classic PTR and the Gen-PTR utilize the gap information differently: the
classic PTR outputs $\perp$ if the gap is not sufficiently large, while the
Gen-PTR encodes the gap into the data-dependent DP function and tests the
data-dependent DP in the end. This empirical result suggests that testing the
local sensitivity can be loosely compared to testing the data-dependent DP.
Thus, Gen-PTR could provide a better privacy-utility trade-off.

###  A.2 Self-concordant generalized linear model (GLM)

In this section, we demonstrate the effectiveness and flexibility of
generalized PTR in handling a family of GLMs where the link function satisfies
a self-concordance assumption. This section is organized as follows:

  * •

Introduce a family of GLMs with the self-concordance property.

  * •

Introduce a general output perturbation algorithm for private GLMs.

  * •

Analyze the data-dependent DP of GLMs with the self-concordance property.

  * •

Provide an example of applying our generalized PTR framework to logistic
regression.

Consider the empirical risk minimization problem of the generalized linear
model

$\theta^{*}=\text{argmin}_{\theta}\sum_{i=1^{n}}l_{i}(\theta)+r(\theta),$

where $l:\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}$ belongs to a family
of convex GLMs: $l_{i}(\theta)=l(y,x_{i}^{T}\theta)$. Let
$r:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be a regularization function.

We now define the self-concordance property.

######  Definition A.3 (Generalized self-concordance (Bach, 2010)).

A convex and three-times differentiable function
$f:\Theta\rightarrow\mathbb{R}$ is $R$-generalized-self-concordant on an open
nonempty convex set $\Theta^{*}\subset\Theta$ with respect to norm $\|\cdot\|$
if for all $u\in\Theta^{*}$ and all $v\in\mathbb{R}^{d}$,

$\nabla^{3}f(u)[v,v,v]\leq 2R\|v\|(\nabla^{2}f(u)[v,v]).$

The closer R is to 0, the “nicer” — more self-concordant — the function is. A
consequence of (generalized) self-concordance is the spectral (multiplicative)
stability of Hessian to small perturbations of parameters.

######  Lemma A.4 (Stability of Hessian(Nesterov and Nemirovskii, 1994,
Theorem 2.1.1), (Bach, 2010, Proposition 1)).

Let $H_{\theta}:=\nabla^{2}F_{s}(\theta)$. If $F_{s}$ is $R$-self-concordant
at $\theta$, then for any $v$ such that $R\|v\|_{H_{\theta}}<1$, we have that

$\displaystyle(1-R\|v\|_{H_{\theta}})^{2}\nabla^{2}F_{s}(\theta)$
$\displaystyle\prec\nabla^{2}F_{s}(\theta+v)$
$\displaystyle\prec\frac{1}{(1-R\|v\|_{H_{\theta}})^{2}}\nabla^{2}F_{s}(\theta).$

If instead we assume $F_{s}$ is $R$-generalized-self-concordant at $\theta$
with respect to norm $\|\cdot\|$, then

$\displaystyle
e^{-R\|v\|}\nabla^{2}F_{s}(\theta)\prec\nabla^{2}F_{s}(\theta+v)\prec
e^{R\|v\|}\nabla^{2}F_{s}(\theta)$

The two bounds are almost identical when $R\|v\|$ and $R\|v\|_{\theta}$ are
close to $0$. In particular, for $x\leq 1/2$, we have that $e^{-2x}\leq
1-x\leq e^{-x}$.

In particular, the loss function of binary logistic regression is
$1$-generalized self-concordant.

######  Example A.5 (Binary logistic regression).

Assume $\|x\|_{2}\leq 1$ for all $x\in\mathcal{X}$ and $y\in\\{-1,1\\}$. Then
binary logistic regression with datasets in $\mathcal{X}\times\mathcal{Y}$ has
a log-likelihood of
$F(\theta)=\sum_{i=1}^{n}\log(1+e^{-y_{i}x_{i}^{T}\theta}).$ The univariate
function $l:=\log(1+\exp(\cdot))$ satisfies

$|l^{\prime\prime\prime}|=\left|\frac{\exp{(\cdot)}(1-\exp{(\cdot)})}{(1+\exp{(\cdot)})^{3}}\right|\leq\frac{\exp{(\cdot)}}{(1+\exp{(\cdot)})^{2}}:=l^{\prime\prime}.$

We next apply the modified output perturbation algorithm to privately release
$\theta^{*}$. The algorithm is simply:

  1. 1.

Solve

$\theta^{*}=\text{argmin}_{\theta}\sum_{i=1}^{n}l_{i}(\theta)+r(\theta).$

  2. 2.

Release

$\hat{\theta}=\theta^{*}+Z,$

where $\gamma>0$ is a tuning parameter and
$Z\sim\mathcal{N}(0,\gamma^{-1}(\sum_{i=1}^{n}\nabla^{2}l_{i}(\theta)+\nabla^{2}r(\theta))^{-1}).$

The data-dependent DP of the above procedure is stated as follows.

######  Theorem A.6 (Data-dependent DP of GLM).

Denote the smooth part of the loss function
$F_{s}=\sum_{i=1}^{n}l(y_{i},<x_{i},\cdot>)+r_{s}(\cdot)$. Assume the
following:

  1. 1.

The GLM loss function $l$ is convex, three-times continuously differentiable
and $R$-generalized-self-concordant w.r.t. $\|\cdot\|_{2}$,

  2. 2.

$F_{s}$ is locally $\alpha$-strongly convex w.r.t. $\|\cdot\|_{2}$,

  3. 3.

and in addition, denote
$L:=\sup_{\theta\in[\theta^{*},\tilde{\theta}^{*}]}|l^{\prime}(y,x^{T}\theta)|$,
$\beta:=\sup_{\theta\in[\theta^{*},\tilde{\theta}^{*}]}|l^{\prime\prime}(y,x^{T}\theta)|$.
That is, $\ell(\cdot)$ is $L$-Lipschitz and $\beta$-smooth.

We then have the data-dependent DP

$\epsilon(Z)\leq\frac{R(L+\beta)}{\alpha}(1+\log(2/\delta))+\frac{\gamma
L^{2}}{\alpha}+\sqrt{\frac{\gamma L^{2}}{\alpha}\log(2/\delta)}.$

The proof follows by taking an upper bound of the per-instance DP loss
(Theorem D.1) $\epsilon(Z,z)$ over $z=(x,y)\in(\mathcal{X},\mathcal{Y})$.

Notice that the Hessians can be arbitrarily singular and $\alpha$ could be
$0$, which leads to an infinite privacy loss without additional assumptions.
Thus, we will impose an additional regularization of form
$\frac{\lambda}{2}||\theta||^{2}$, which ensures that for any dataset $F_{S}$
is $\lambda$-strongly convex.

This is not yet DP because it is still about a fixed dataset. We also need a
pre-specified privacy budget $(\epsilon,\delta)$. We next demonstrate how to
apply the generalized PTR to provide a general solution to the above GLM,
using logistic regression as an example.

######  Remark A.7 (Logistic regression).

For logistic regression, we know $L\leq 1$, $\beta\leq 1/4$ and if
$\|x\|_{2}\leq 1$, it is $1$-generalized self-concordant. For any dataset
$Z=(X,y)$, the data-dependent DP $\epsilon(X)$ w.r.t. $\delta$ can be
simplified to:

$\frac{1.25}{\alpha}(1+\log(2/\delta))+\frac{\gamma}{\alpha}+\sqrt{\frac{\gamma}{\alpha}\log(2/\delta)}$

Now, the data-dependent DP is a function of $\alpha$ and $\gamma$, where
$\alpha$ denotes the local strong convexity at $\theta_{\lambda}^{*}$ and
$\gamma$ controls the noise scale. We next show how to select these two
parameters adapted to the dataset.

######  Example A.8.

We demonstrate here how we apply generalized PTR to output perturbation of the
logistic regression problem.

  1. 1.

Take an exponential grid of parameters $\\{\lambda\\}$ and propose each
$\lambda$.

  2. 2.

Solve for
$\theta_{\lambda}^{*}=\text{argmin}_{\theta}F(\theta)+\lambda\|\theta\|^{2}/2$

  3. 3.

Calculate the smallest eigenvalue
$\lambda_{\min}(\nabla^{2}F(\theta_{\lambda}^{*}))$ (e.g., using power
method).

  4. 4.

Differentially privately release $\lambda_{\min}$ with
$\lambda_{\min}^{p}:=\max\\{\lambda_{\min}+\frac{\sqrt{\log(4/\delta)}}{\epsilon/2}\cdot\Delta_{GS}\cdot
Z-\frac{\sqrt{2\log(4/\delta)\cdot\log(1/\delta)}\Delta_{GS}}{\epsilon/2},0\\}$,
where $\Delta_{GS}$ denote the global sensitivity of $\lambda_{\min}$ using
Theorem A.11.

  5. 5.

Let $\epsilon^{p}(\cdot)$ be instantiated with $\epsilon(X)$ w.r.t. $\delta$
from Remark A.7, where $\alpha=\lambda_{\min}^{p}+\lambda$. Then, conditioned
on a high probability event, $\epsilon^{p}(\cdot)$ (a function of $\gamma$) is
a valid DP bound that holds for all datasets and all parameters $\gamma$.

  6. 6.

Calculate the maximum $\gamma$ such that
$\epsilon_{\delta/2}^{p}(\gamma)\leq\epsilon/2$.

  7. 7.

Release
$\hat{\theta}\sim\mathcal{N}(\theta_{\lambda}^{*},\gamma^{-1}\nabla^{2}F_{s}(\theta_{\lambda}^{*})^{-1})$.

  8. 8.

Evaluate the utility on the validation set and return the $(\lambda,\gamma)$
pair that leads to the highest utility.

######  Theorem A.9.

For each proposed $\lambda$, the algorithm that releases
$\hat{\theta}\sim\mathcal{N}(\theta_{\lambda}^{*},\gamma^{-1}\nabla^{2}F_{s}(\theta_{\lambda}^{*})^{-1})$
is $(\epsilon,2\delta)$-DP.

###### Proof.

The proof follows the recipe of generalized PTR with private upper bound
(Example 4.6). First, the release of
$\lambda_{\min}(\nabla^{2}F(\theta_{\lambda}^{*}))$ is
$(\epsilon/2,\delta/2)$-DP. Then, with probability at least $1-\delta$,
$\epsilon_{\delta}^{p}(\cdot)>\epsilon_{\delta}(X)$ holds for all $X$ and
$\gamma$. Finally, $\gamma$ is chosen such that the valid upper bound is
$(\epsilon/2,\delta/2)$-DP. ∎

For the hyper-parameter tuning on $\lambda$ (Steps 1 and 8), we can use
Algorithm 3 to evaluate each $\lambda$.

Unlike Example 5.2, the
$\lambda_{\text{min}}(\nabla^{2}F(\theta_{\lambda}^{*}))$ is a complicated
data-dependent function of $\lambda$. Thus, we cannot privately release the
data-dependent quantity
$\lambda_{\text{min}}(\nabla^{2}F(\theta_{\lambda}^{*}))$ without an input
$\lambda$. The PTR approach allows us to test a number of different $\lambda$
and hence get a more favorable privacy-utility trade-off.

An interesting perspective of this algorithm for logistic regression is that
increasing the regularization $\alpha$ is effectively increasing the number of
data points within the soft “margin”333If we think of logistic regression as a
smoothed version of SVM, then increasing $\alpha$ leads to more support
vectors. The “margin” is “softer” in logistic regression, but qualitatively
the same. of separation, hence a larger contribution to the Hessian from the
loss function.

######  Remark A.10.

The PTR solution for GLMs follows a similar recipe: propose a regularization
strength $\lambda$; construct a lower bound of the strong convexity $\alpha$
at the optimal solution $\theta_{\lambda}^{*}$; and test the validity of data-
dependent DP using Theorem D.1.

Before moving on to other applications of generalized PTR, we will show how to
differentially privately release $\lambda_{min}$ according to the requirements
of the logistic regression example.

###  A.3 Differentially privately release
$\lambda_{min}\left(\nabla^{2}F(\theta)\right)$

To privately release $\lambda_{min}{\nabla^{2}F(\theta)}$, we first need to
compute its global sensitivity. Once we have that then we can release it
differentially privately using either the Laplace mechanism or the Gaussian
mechanism.

######  Theorem A.11 (Global sensitivity of the minimum eigenvalue at the
optimal solution).

Let $F(\theta)=\sum_{i=1}^{n}f_{i}(\theta)+r(\theta)$ and
$\tilde{F}(\theta)=F(\theta)+f(\theta)$ where $f_{1},...,f_{n}$ are loss
functions corresponding to a particular datapoint $x$. Let
$\theta^{*}=\text{argmin}_{\theta}F(\theta)$ and
$\tilde{\theta}^{*}=\text{argmin}_{\theta}\tilde{F}(\theta)$. Assume $f$ is
$L$-Lipschitz and $\beta$-smooth, $r(\theta)$ is $\lambda$-strongly convex,
and $F$ and $\tilde{F}$ are $R$-self-concordant. If in addition, $\lambda\geq
RL$, then we have

$\sup_{X,x}(\lambda_{min}(\nabla^{2}F(\theta_{\lambda}^{*}))-\lambda_{min}(\nabla^{2}\tilde{F}(\tilde{\theta_{\lambda}^{*}})))\leq
2RL+\beta.$

###### Proof.

$\begin{split}\lambda_{min}&(\nabla^{2}F(\theta_{\lambda}^{*}))-\lambda_{min}(\nabla^{2}\tilde{F}(\tilde{\theta_{\lambda}^{*}}))\\\
&=(\lambda_{min}(\nabla^{2}F(\theta_{\lambda}^{*}))-\lambda_{min}(\nabla^{2}\tilde{F}(\theta_{\lambda}^{*})))\\\
&+(\lambda_{min}(\nabla^{2}\tilde{F}(\theta_{\lambda}^{*}))-\lambda_{min}(\nabla^{2}\tilde{F}(\tilde{\theta_{\lambda}^{*}}))).\end{split}$
(1)

We first bound the part on the left. By applying Weyl’s lemma
$\lambda(X+E)-\lambda(X)\leq||E||_{2}$, we have

$\sup_{x}||\nabla^{2}F(\theta_{\lambda}^{*})-\nabla^{2}\tilde{F(\theta_{\lambda}^{*}})||_{2}=||\nabla^{2}f(\theta_{\lambda}^{*})||_{2}\leq\beta$
(2)

In order to bound the part on the right, we apply the semidefinite ordering
using self-concordance, which gives

$e^{-R\|\tilde{\theta_{\lambda}^{*}}-\theta_{\lambda}^{*}\|}\nabla^{2}\tilde{F}(\tilde{\theta_{\lambda}^{*}})\prec\nabla^{2}\tilde{F}(\theta_{\lambda}^{*})\prec
e^{R\|\tilde{\theta_{\lambda}^{*}}-\theta_{\lambda}^{*}\|}\nabla^{2}\tilde{F}(\tilde{\theta_{\lambda}^{*}}).$

By the Courant-Fischer Theorem and the monotonicity theorem, we also have that
for the smallest eigenvalue

$\begin{split}e^{-R\|\tilde{\theta_{\lambda}^{*}}-\theta_{\lambda}^{*}\|}&\lambda_{\min}\left(\nabla^{2}\tilde{F}(\tilde{\theta_{\lambda}^{*}})\right)\leq\lambda_{\min}\left(\nabla^{2}\tilde{F}(\theta_{\lambda}^{*})\right)\\\
&\leq
e^{R\|\tilde{\theta_{\lambda}^{*}}-\theta_{\lambda}^{*}\|}\lambda_{\min}\left(\nabla^{2}\tilde{F}(\tilde{\theta_{\lambda}^{*}})\right).\end{split}$
(3)

Moreover by Proposition D.2, we have that

$\|\tilde{\theta_{\lambda}^{*}}-\theta_{\lambda}^{*}\|_{2}\leq\frac{\|\nabla
f(\tilde{\theta^{*}}_{\lambda})\|}{\lambda_{\min}\left(\nabla^{2}\tilde{F}(\tilde{\theta_{\lambda}^{*}})\right)}\leq\frac{L}{\lambda_{\min}\left(\nabla^{2}\tilde{F}(\tilde{\theta_{\lambda}^{*}})\right)}.$

If
$\lambda_{\min}\left(\nabla^{2}\tilde{F}(\tilde{\theta_{\lambda}^{*}})\right)\geq
RL$, then use that $e^{x}-1\leq 2x$ for $x\leq 1$. Substituting the above
bound to (3) then to (1) together with (2), we get a data-independent global
sensitivity bound of

$\lambda_{min}(\nabla^{2}F(\theta_{\lambda}^{*}))-\lambda_{min}(\nabla^{2}\tilde{F}(\tilde{\theta_{\lambda}^{*}}))\leq
2RL+\beta$

as stated. ∎

######  Proposition A.12.

Let $\|\cdot\|$ be a norm and $\|\cdot\|_{*}$ be its dual norm. Let
$F(\theta)$, $f(\theta)$ and $\tilde{F}(\theta)=F(\theta)+f(\theta)$ be proper
convex functions and $\theta^{*}$ and $\tilde{theta}^{*}$ be their minimizers,
i.e., $0\in\partial F(\theta^{*})$ and
$0\in\partial\tilde{F}(\tilde{theta}^{*})$. If in addition, $F,\tilde{F}$ is
$\alpha,\tilde{\alpha}$-strongly convex with respect to $\|\cdot\|$ within the
restricted domain
$\theta\in\\{t\theta^{*}+(1-t)\tilde{\theta}^{*}\;|\;t\in[0,1]\\}$. Then there
exists $g\in\partial f(\theta^{*})$ and $\tilde{g}\in\partial
f(\tilde{\theta}^{*})$ such that

$\|\theta^{*}-\tilde{\theta}^{*}\|\leq\min\left\\{\frac{1}{\alpha}\|\tilde{g}\|_{*},\frac{1}{\tilde{\alpha}}\|g\|_{*}\right\\}.$

###### Proof.

Apply the first order condition to $F$ restricted to the line segment between
$\tilde{\theta}^{*}$ and $\theta^{*}$, we get

$\displaystyle F(\tilde{\theta}^{*})\geq F(\theta^{*})+\langle\partial
F(\theta^{*}),\tilde{\theta}^{*}-\theta^{*}\rangle+\frac{\alpha}{2}\|\tilde{\theta}^{*}-\theta^{*}\|^{2}$
(4) $\displaystyle F(\theta^{*})\geq F(\tilde{\theta}^{*})+\langle\partial
F(\tilde{\theta}^{*}),\theta^{*}-\tilde{\theta}^{*}\rangle+\frac{\alpha}{2}\|\tilde{\theta}^{*}-\theta^{*}\|^{2}$
(5)

Note by the convexity of $F$ and $f$, $\partial\tilde{F}=\partial F+\partial
f$, where $+$ is the Minkowski Sum. Therefore,
$0\in\partial\tilde{F}(\tilde{\theta}^{*})$ implies that there exists
$\tilde{g}$ such that $\tilde{g}\in\partial f(\tilde{\theta}^{*})$ and
$-\tilde{g}\in\partial F(\tilde{\theta}^{*})$. Take $-\tilde{g}\in\partial
F(\tilde{\theta}^{*})$ in Equation 10 and $0\in\partial F(\theta^{*})$ in
Equation 9 and add the two inequalities, we obtain

$\displaystyle 0$
$\displaystyle\geq\langle-\tilde{g},\theta^{*}-\tilde{\theta}^{*}\rangle+\alpha\|\tilde{\theta}^{*}-\theta^{*}\|^{2}$
$\displaystyle\geq-\|\tilde{g}\|_{*}\|\theta^{*}-\tilde{\theta}^{*}\|+\alpha\|\tilde{\theta}^{*}-\theta^{*}\|^{2}.$

For $\|\tilde{\theta}^{*}-\theta^{*}\|=0$ the claim is trivially true;
otherwise, we can divide both sides of the above inequality by
$\|\tilde{\theta}^{*}-\theta^{*}\|$ and get
$\|\theta^{*}-\tilde{\theta}^{*}\|\leq\frac{1}{\alpha}\|\tilde{g}\|_{*}$.

It remains to show that
$\|\theta^{*}-\tilde{\theta}^{*}\|\leq\frac{1}{\tilde{\alpha}}\|g\|_{*}$. This
can be obtained by exactly the same arguments above but applying strong
convexity to $\tilde{F}$ instead. Note that we can actually get something
slightly stronger than the statement because the inequality holds for all
$g\in\partial f(\theta^{*})$. ∎

###  A.4 Other applications of generalized PTR

Besides one-posterior sampling for GLMs, there are plenty of examples that our
generalized-PTR could be applied, e.g., DP-PCA (Dwork et al., 2014) and
Sparse-DP-ERM (Kifer et al., 2012) (when the designed matrix is well-behaved).

(Dwork et al., 2014) provides a PTR style privacy-preserving principle
component analysis (PCA). The key observation of (Dwork et al., 2014) is that
the local sensitivity is quite “small” if there is a large eigengap between
the $k$-th and the $k+1$-th eigenvalues. Therefore, their approach (Algorithm
2) chooses to privately release a lower bound of the k-th eigengap ($k$ is
fixed as an input) and use that to construct a high-confidence upper bound of
the local sensitivity.

For noise-adding mechanisms, the local sensitivity is proportional to the
data-dependent loss and generalized PTR is applicable. We can formulate the
data-dependent DP of DP-PCA as follows:

######  Theorem A.13.

For a given matrix $A\in\mathcal{R}^{m\times n}$, assume each row of $A$ has a
bounded $\ell_{2}$ norm being $1$. Let $V_{k}$ denotes the top $k$
eigenvectors of $A^{T}A$ and $d_{k}$ denotes the gap between the $k$-th and
the $k+1$-th eigenvalue. Then releasing $V_{k}V_{k}^{T}+E$, where
$E\in\mathcal{R}^{n\times n}$ is a symmetric matrix with the upper triangle is
i.i.d samples from $\mathcal{N}(0,\sigma^{2})$ satisfies
$(\epsilon(A),\delta)$ data-dependent DP and
$\epsilon(A)=\frac{2\sqrt{\log(1.25/\delta)}}{\sigma(d_{k}-2)}$.

The proof is based on the local sensitivity result from (Dwork et al., 2014)
and the noise calibration of Gaussian mechanism.

We can combine Theorem A.13 with our Algorithm 3 to instantiate the
generalized PTR framework. The improvement over Dwork et al. (2014) will be to
allow joint tuning of the parameter $k$ and the noise variance (added to the
spectral gap $d_{k}$).

##  Appendix B Omitted proofs in Section 4

The utility of Algorithm 3 depends on how many rounds that Algorithm 2 is
invoked. We next provide the utility guarantee of Algorithm 3, which follows a
simplification of the result in the Section A.2 of Papernot and Steinke
(2021).

######  Theorem B.1.

Suppose applying Algorithm 2 with each $\phi_{i}$ has an equal probability to
achieve the highest validation score. Let $\hat{T}$ denotes the number of
invocation of Algorithm 2, where $\hat{T}$ follows a truncated geometric
distribution. Then the expected quantile of the highest score candidate is
given by $\mathbb{E}_{\hat{T}}\bigg{[}1-\frac{1}{\hat{T}+1}\bigg{]}$.

In practice, we can roughly set $\tau=\frac{1}{10k}$ so that the algorithm is
likely to test all $k$ parameters.

###### Proof.

Suppose each oracle access to $Q(X)$ has a probability $1/k$ of achiving the
best validation accuracy. Let $\beta$ denote the probability that
$\mathcal{A}$ (shorthand for Algorithm 3) outputs the best choice of
$\phi_{i}$.

$\displaystyle\beta$ $\displaystyle=1-\mathrm{Pr}[\mathcal{A}(X)\text{is not
best}]$ $\displaystyle=1-\mathbb{E}_{\hat{T}}\bigg{[}\mathrm{Pr}[Q(X)\text{is
not best}]^{\hat{T}}\bigg{]}$
$\displaystyle=1-\mathbb{E}_{\hat{T}}\bigg{[}(1-\frac{1}{k})^{\hat{T}}\bigg{]}.$

Let $f(x)=\mathbb{E}[x^{\hat{T}}]$. Applying a first-order approximation on
$f(1-\frac{1}{k})$, we have $f(1-\frac{1}{k})\approx
f(1)-f^{\prime}(1)\cdot\frac{1}{k}=1-\mathbb{E}[\hat{T}]/k$. Then, if $k$ is
large and we choose $\tau=0.1/k$, $\mathcal{A}$ can roughly return the best
$\phi_{i}$. ∎

##  Appendix C Experimental details

###  C.1 Experimental details in private linear regression

We start with the privacy calibration of the OPS-PTR algorithm.

Algorithm 5 OPS-PTR: One-Posterior Sample with propose-test-release (no-“perp”
version)

1: Input: Data $X,\bf{y}$. Private budget : $\epsilon,\delta$, proposed
regularizer $\lambda$.

2: Calculate the minimum eigenvalue $\lambda_{\text{min}}(X^{T}X)$.

3: Sample $Z\sim\mathcal{N}(0,1)$ and privately release
$\tilde{\lambda}_{\text{min}}=\text{max}\bigg{\\{}\lambda_{\text{min}}+\frac{\sqrt{\log(6/\delta)}}{\epsilon/4}Z-\frac{\sqrt{2\log(6/\delta)\cdot\log(2/\delta)}}{\epsilon/4},0\bigg{\\}}$

4: Calculate $\hat{\theta}=(X^{T}X+\lambda I)^{-1}X^{T}y$.

5: Sample $Z\sim\mathcal{N}(0,1)$ and privately release
$\Delta=\log(||\mathcal{Y}||+||\mathcal{X}||||\hat{\theta}||)+\frac{\log(1+||\mathcal{X}||^{2}/(\lambda+\tilde{\lambda}_{\text{min}}))}{\epsilon/(4\sqrt{6/\delta})}Z+\frac{\log(1+||\mathcal{X}||^{2}/(\lambda+\tilde{\lambda}_{\text{min}}))}{\epsilon/(4\sqrt{2\log(6/\delta)\log(2/\delta)})}$.

6: Set the local Lipschitz $\tilde{L}:=||X||e^{\Delta}.$

7: Calibrate $\gamma$ with Theorem 5.1($\delta/3,\epsilon/2$.)

8: Output $\tilde{\theta}\sim p(\theta|X,\bf{y})\propto
e^{-\frac{\gamma}{2}||\bf{y}-X\theta||^{2}+\lambda||\theta||^{2}}$

Algorithm 5 provides the detailed privacy calibration of the private linear
regression problem.

######  Theorem C.1.

Algorithm 5 is $(\epsilon,2\delta)$-DP.

###### Proof.

There are three data-dependent quantities in Theorem 5.1:
$\lambda_{\text{min}},||\theta_{\lambda}^{*}||$ and $L$. First, notice that
$\lambda_{\text{min}}$ has a global sensitivity of $||\mathcal{X}||^{2}$ by
Weyl’s lemma. Under the assumption $||\mathcal{X}||^{2}\leq 1$, we privately
release $\lambda_{\text{min}}$ using $(\epsilon/4,\delta/3)$ in Step 3. Notice
that with probability at least $1-\delta/2$, $\tilde{\lambda}_{\min}$ is a
lower bound of $\lambda_{\min}$.

Then, we apply Lemma C.2 from Wang (2018) to privately release
$\log(||\mathcal{Y}||+||\mathcal{X}||||\hat{\theta}||)$ using
$(\epsilon/4,\delta/3)$. Note that both the local Lipschitz constant $L$ and
the norm $||\theta_{\lambda}^{*}||$ are functions of
$\log(||\mathcal{Y}||+||\mathcal{X}||||\hat{\theta}||)$. Thus, we can
construct a private upper bound of these by post-processing of $\Delta$.

Then, with probability at least $1-\delta$ (by a union bound over
$\tilde{\lambda}_{\min}$ and $\Delta$), instantiating Theorem 5.1 with
$\tilde{\lambda}_{\min}$ and $\tilde{L}$ provides a valid upper bound of the
data-dependent DP. We then tune the parameter $\gamma$ using the remaining
privacy budget $(\epsilon/2,\delta/3)$. ∎

######  Lemma C.2 (Lemma 12 (Wang, 2018)).

Let $\theta_{\lambda}^{*}$ be the ridge regression estimate with parameter
$\lambda$ and the smallest eigenvalue of $X^{T}X$ be $\lambda_{\text{min}}$,
then the function
$\log(||\mathcal{Y}+||\mathcal{X}||||\theta_{\lambda}^{*}||)$ has a local
sensitivity of
$\log(1+\frac{||\mathcal{X}||^{2}}{\lambda_{\text{min}+\lambda}})$.

###  C.2 Details of PATE case study

######  Definition C.3 (Renyi DP (Mironov, 2017)).

We say a randomized algorithm $\mathcal{M}$ is
$(\alpha,\epsilon_{\mathcal{M}}(\alpha))$-RDP with order $\alpha\geq 1$ if for
neighboring datasets $X,X^{\prime}$

$\displaystyle\mathbb{D}_{\alpha}(\mathcal{M}(X)||\mathcal{M}(X^{\prime})):=$
$\displaystyle\frac{1}{\alpha-1}\log\mathbb{E}_{o\sim\mathcal{M}(X^{\prime})}\bigg{[}\bigg{(}\frac{\mathrm{Pr}[\mathcal{M}(X)=o]}{\mathrm{Pr}[\mathcal{M}(X^{\prime})=o]}\bigg{)}^{\alpha}\bigg{]}\leq\epsilon_{\mathcal{M}}(\alpha).$

At the limit of $\alpha\to\infty$, RDP reduces to $(\epsilon,0)$-DP. We now
define the data-dependent Renyi DP that conditioned on an input dataset $X$.

######  Definition C.4 (Data-dependent Renyi DP (Papernot et al., 2018)).

We say a randomized algorithm $\mathcal{M}$ is
$(\alpha,\epsilon_{\mathcal{M}}(\alpha,X))$-RDP with order $\alpha\geq 1$ for
dataset $X$ if for neighboring datasets $X^{\prime}$

$\displaystyle\mathbb{D}_{\alpha}(\mathcal{M}(X)||\mathcal{M}(X^{\prime})):=$
$\displaystyle\frac{1}{\alpha-1}\log\mathbb{E}_{o\sim\mathcal{M}(X^{\prime})}\bigg{[}\bigg{(}\frac{\mathrm{Pr}[\mathcal{M}(X)=o]}{\mathrm{Pr}[\mathcal{M}(X^{\prime})=o]}\bigg{)}^{\alpha}\bigg{]}\leq\epsilon_{\mathcal{M}}(\alpha,X).$

RDP features two useful properties.

######  Lemma C.5 (Adaptive composition).

$\epsilon_{(\mathcal{M}_{1},\mathcal{M}_{2})}=\epsilon_{\mathcal{M}_{1}}(\cdot)+\epsilon_{\mathcal{M}_{2}}(\cdot)$.

######  Lemma C.6 (From RDP to DP).

If a randomized algorithm $\mathcal{M}$ satisfies
$(\alpha,\epsilon(\alpha))$-RDP, then $\mathcal{M}$ also satisfies
$(\epsilon(\alpha)+\frac{\log(1/\delta)}{\alpha-1},\delta)$-DP for any
$\delta\in(0,1)$.

######  Definition C.7 (Smooth Sensitivity).

Given the smoothness parameter $\beta$, a $\beta$-smooth sensitivity of $f(X)$
is defined as

$SS_{\beta}(X):=\max_{d\geq 0}e^{-\beta
d}\cdot\max_{\tilde{X^{\prime}}:dist(X,\tilde{X^{\prime}})\leq
d}\Delta_{LS}(\tilde{X}^{\prime})$

######  Lemma C.8 (Private upper bound of data-dependent RDP, Restatement of
Theorem 5.6).

] Given a RDP function $\mathrm{RDP}(\alpha,X)$ and a $\beta$-smooth
sensitivity bound $SS(\cdot)$ of $\mathrm{RDP}(\alpha,X)$. Let $\mu$ (defined
in Algorithm 4) denote the private release of $\log(SS_{\beta}(X))$. Let
$(\beta,\sigma_{s},\sigma_{2})$-GNSS mechanism be

$\scriptstyle\mathrm{RDP}^{\text{upper}}(\alpha):=\mathrm{RDP}(\alpha,X)+SS_{\beta}(X)\cdot\mathcal{N}(0,\sigma_{s}^{2})+\sigma_{s}\sqrt{2\log(\frac{2}{\delta_{2}})}e^{\mu}$

Then, the release of $\mathrm{RDP}^{\text{upper}}(X)$ satisfies
$(\alpha,\frac{3\alpha+2}{2\sigma_{s}^{2}})$-RDP for all
$1<\alpha<\frac{1}{2\beta}$; w.p. at least $1-\delta_{2}$,
$\mathrm{RDP}^{\text{upper}}(\alpha)$ is an upper bound of
$\mathrm{RDP}(\alpha,X)$.

###### Proof sketch.

We first show that releasing the smooth sensitivity $SS_{\beta}$ with
$e^{\mu}$ satisfies $(\alpha,\frac{\alpha}{2\sigma_{2}^{2}})$-RDP. Notice that
the log of $SS_{\beta}(X)$ has a bounded global sensitivity $\beta$
(Definition C.7 implies that $|\log SS_{\beta}(X)-\log
SS_{\beta}(X^{\prime})|\leq\beta$ for any neighboring dataset $X,X^{\prime}$).
By Gaussian mechanism, scaling noise with $\beta\sigma_{2}$ to $\log
SS_{\beta}(X)$ is $(\alpha,\frac{\alpha}{2\sigma_{2}^{2}})$-RDP. Therefore,
the release of $\mathrm{RDP}(\alpha,X)$ is
$(\alpha,\epsilon_{s}(\alpha)+\frac{\alpha}{2\sigma_{2}^{2}})$-RDP. Since the
release of $f(X)+SS_{\beta}(X)\cdot\mathcal{N}(0,\sigma_{s}^{2})$ is
$(\alpha,\frac{\alpha+1}{\sigma_{s}^{2}})$-RDP (Theorem 23 from Papernot et
al. (2018)) for $\alpha<\frac{1}{2\beta}$, we have
$\epsilon_{s}(\alpha)+\frac{\alpha}{2\sigma_{2}^{2}}=\frac{3\alpha+2}{2\sigma_{s}^{2}}$.

We next prove the second statement. First, notice that with probability at
least $1-\delta_{2}/2$, $e^{\mu}\geq SS_{\beta}(X)$ using the standard
Gaussian tail bound. Let $E$ denote the event that $e^{\mu}\geq
SS_{\beta}(X)$.

$\displaystyle\mathrm{Pr}\bigg{[}\mathrm{RDP}^{\text{upper}}(\alpha)\leq\mathrm{RDP}(\alpha,X)\bigg{]}$
$\displaystyle=\mathrm{Pr}\bigg{[}\mathrm{RDP}^{\text{upper}}(\alpha)\leq\mathrm{RDP}(\alpha,X)|E\bigg{]}+\mathrm{Pr}\bigg{[}\mathrm{RDP}^{\text{upper}}(\alpha)\leq\mathrm{RDP}(\alpha,X)|E^{c}\bigg{]}$
$\displaystyle\leq\mathrm{Pr}\bigg{[}\mathrm{RDP}^{\text{upper}}(\alpha)\leq\mathrm{RDP}(\alpha,X)|E\bigg{]}+\delta_{2}/2$
$\displaystyle=\underbrace{\mathrm{Pr}\bigg{[}\mathcal{N}(0,\sigma_{s}^{2})\cdot
SS_{\beta(X)}\geq\sigma_{s}\cdot\sqrt{2\log(2/\delta_{2})}e^{\mu}|E\bigg{]}}_{\text{denoted
by}(*)}+\delta_{2}/2$

Condition on the event $E$, $e^{\mu}$ is a valid upper bound of
$SS_{\beta}(X)$, which implies

$(*)\leq\mathrm{Pr}[\mathcal{N}(0,\sigma_{s}^{2})\cdot
SS_{\beta}(X)\geq\sigma_{s}\cdot\sqrt{2\log(2/\delta_{2})}SS_{\beta}(X)|E]\leq\delta_{2}/2$

Therefore, with probability at least $1-\delta_{2}$,
$\mathrm{RDP}^{\text{upper}}(\alpha)\geq\mathrm{RDP}(\alpha,X)$. ∎

######  Theorem C.9 (Restatement of Theorem 5.7).

Algorithm 4 satisfies $(\epsilon^{\prime}+\hat{\epsilon},\delta)$-DP.

###### Proof.

The privacy analysis consists of two components — the privacy cost of
releasing an upper bound of data-dependent RDP
($\epsilon_{\text{upper}}(\alpha):=\epsilon_{s}(\alpha)+\frac{\alpha}{2\sigma_{2}^{2}}$
and the valid upper bound $\epsilon_{\sigma_{1}}^{p}(\alpha)$. First, set
$\alpha=\frac{2\log(2/\delta)}{\epsilon}+1$ and use RDP to DP conversion with
$\delta/2$ ensures that the cost of $\delta/2$ contribution to be roughly
$\epsilon/2$ (i.e., $\frac{\log(2/\delta)}{\alpha-1}=\epsilon/2$). Second,
choosing $\sigma_{s}=\sqrt{\frac{2+3\alpha}{\epsilon}}$ gives us another
$\epsilon/2$. ∎

Experimental details $K=400$ teacher models are trained individually on the
disjoint set using AlexNet model. We set $\sigma_{2}=\sigma_{s}=15.0$. Our
data-dependent RDP calculation and the smooth-sensitivity calculation follow
Papernot et al. (2018). Specifically, we use the following theorem (Theorem 6
from Papernot et al. (2018)) to compute the data-dependent RDP of each
unlabeled data $x$ from the public domain.

######  Theorem C.10 (data-dependent RDP Papernot et al. (2018)).

Let $\tilde{q}\geq\mathrm{Pr}[\mathcal{M}(X)\neq Argmax_{j\in[C]}n_{j}(x)]$,
i.e., an upper bound of the probability that the noisy label does not match
the majority label. Assume $\alpha\leq\mu_{1}$ and $\tilde{q}\leq
e^{(\mu_{2}-1)\epsilon_{2}}/\bigg{(}\frac{\mu_{1}}{\mu_{1}-1}\cdot\frac{\mu_{2}}{\mu_{2}-1}\bigg{)}^{\mu_{2}}$,
then we have:

$\epsilon_{\mathcal{M}}(\alpha,X)\leq\frac{1}{\alpha-1}\log\bigg{(}(1-\tilde{q})\cdot
A(\tilde{q},\mu_{2},\epsilon_{2})^{\alpha-1}+\tilde{q}\cdot
B(\tilde{q},\mu_{1},\epsilon_{1})^{\alpha-1}\bigg{)}$

where
$A(\tilde{q},\mu_{2},\epsilon_{2}):=(1-\tilde{q})/\bigg{(}1-(\tilde{q}e^{\epsilon_{2}})^{\frac{\mu_{2}-1}{\mu_{2}}}\bigg{)}$,
$B(\tilde{q},\mu_{1},\epsilon_{1})=e^{\epsilon_{1}}/\tilde{q}^{\frac{1}{\mu_{1}-1}},\mu_{2}=\sigma_{1}\cdot\sqrt{\log(1/\tilde{q})},\mu_{1}=\mu_{2}+1,\epsilon_{1}=\mu_{1}/\sigma_{1}^{2}$
and $\epsilon_{2}=\mu_{2}/\sigma_{2}^{2}$.

In the experiments, the non-private data-dependent DP baseline is also based
on the above theorem. Notice that the data-dependent RDP of each query is a
function of $\tilde{q}$, where $\tilde{q}$ denotes an upper bound of the
probability where the plurality output does not match the noisy output.
$\tilde{q}$ is a complex function of both the noisy scale and data and is not
monotonically decreasing when $\sigma_{1}$ is increasing.

Simulation of two distributions. The motivation of the experimental design is
to compare three approaches under different data distributions. Notice that
there are $K=400$ teachers, which implies the number of the vote count for
each class will be bounded by $400$. In the simulation of high-consensus
distribution, we choose $T=200$ unlabeled public data such that the majority
vote count will be larger than $150$ (i.e., $\max_{j\in[C]}n_{j}(x)>150$). For
the low-consensus distribution, we choose to select $T$ unlabeled data such
that the majority vote count will be smaller than $150$.

##  Appendix D Omitted proofs in private GLM

###  D.1 Per-instance DP of GLM

######  Theorem D.1 (Per-instance differential privacy guarantee).

Consider two adjacent data sets $Z$ and $Z^{\prime}=[Z,(x,y)]$, and denote the
smooth part of the loss function $F_{s}=\sum_{i=1}^{n}l(y_{i},\langle
x_{i},\cdot\rangle)+r_{s}(\cdot)$ (thus $\tilde{F}_{s}=F_{s}+l(y,\langle
x,\cdot\rangle)$. Let the local neighborhood be the line segment between
$\theta^{*}$ and $\tilde{\theta}^{*}$. Assume

  1. 1.

the GLM loss function $l$ be convex, three-time continuous differentiable and
$R$-generalized-self-concordant w.r.t. $\|\cdot\|_{2}$,

  2. 2.

$F_{s}$ is locally $\alpha$-strongly convex w.r.t. $\|\cdot\|_{2}$,

  3. 3.

and in addition, denote
$L:=\sup_{\theta\in[\theta^{*},\tilde{\theta}^{*}]}|l^{\prime}(y,x^{T}\theta)|$,
$\beta:=\sup_{\theta\in[\theta^{*},\tilde{\theta}^{*}]}|l^{\prime\prime}(y,x^{T}\theta)|$.

Then the algorithm obeys $(\epsilon,\delta)$-pDP for $Z$ and $z=(x,y)$ with
any $0<\delta<2/e$ and

$\epsilon\leq\epsilon_{0}(1+\log(2/\delta))+e^{\frac{RL\|x\|_{2}}{\alpha}}\left[\frac{\gamma
L^{2}\|x\|_{H^{-1}}^{2}}{2}+\sqrt{\gamma
L^{2}\|x\|_{H^{-1}}^{2}\log(2/\delta)}\right]$

where $\epsilon_{0}\leq
e^{\frac{RL\|x\|_{2}}{\alpha}}-1+2\beta\|x\|_{H_{1}^{-1}}^{2}+2\beta\|x\|_{\tilde{H}_{2}^{-1}}^{2}.$
If we instead assume that $l$ is $R$-self concordant. Then the same results
hold, but with all $e^{\frac{RL\|x\|_{2}}{\alpha}}$ replaced with
$(1-RL\|x\|_{H^{-1}})^{2}$.

Under the stronger three-times continuous differentiable assumption, by mean
value theorem, there exists $\xi$ on the line-segment between $\theta^{*}$ and
$\tilde{\theta}^{*}$ such that

$H=\left[\int_{t=0}^{1}\nabla^{2}F_{s}((1-t)\theta^{*}+t\tilde{\theta}^{*})dt\right]=\nabla^{2}F_{s}(\xi).$

The two distributions of interests are
$\mathcal{N}(\theta^{*},[\gamma\nabla^{2}F_{s}(\theta^{*})]^{-1})$ and
$\mathcal{N}(\tilde{\theta}^{*},[\gamma\nabla^{2}F_{s}(\tilde{\theta}^{*})+\nabla^{2}l(y,x^{T}\tilde{\theta}^{*})]^{-1}).$
Denote $[\nabla^{2}F_{s}(\theta^{*})]^{-1}=:\Sigma$ and
$[\nabla^{2}F_{s}(\tilde{\theta}^{*})+\nabla^{2}l(y,x^{T}\tilde{\theta}^{*})]^{-1}=:\tilde{\Sigma}$.
Both the means and the covariance matrices are different, so we cannot use
multivariate Gaussian mechanism naively. Instead we will take the tail bound
interpretation of $(\epsilon,\delta)$-DP and make use of the per-instance DP
framework as internal steps of the proof.

First, we can write down the privacy loss random variable in analytic form

$\displaystyle\log\frac{|\Sigma|^{-1/2}e^{-\frac{\gamma}{2}\|\theta-\theta^{*}\|_{\Sigma^{-1}}^{2}}}{|\tilde{\Sigma}|^{-1/2}e^{-\frac{\gamma}{2}\|\theta-\tilde{\theta}^{*}\|_{\tilde{\Sigma}^{-1}}^{2}}}=\underbrace{\frac{1}{2}\log\left(\frac{|\Sigma^{-1}|}{|\tilde{\Sigma}^{-1}|}\right)}_{(*)}+\underbrace{\frac{\gamma}{2}\left[\|\theta-\theta^{*}\|_{\Sigma^{-1}}^{2}-\|\theta-\tilde{\theta}^{*}\|_{\tilde{\Sigma}^{-1}}^{2}\right]}_{(**)}$

The general idea of the proof is to simplify the expression above and upper
bounding the two terms separately using self-concordance and matrix inversion
lemma, and ultimately show that the privacy loss random variable is dominated
by another random variable having an appropriately scaled shifted
$\chi$-distribution, therefore admits a Gaussian-like tail bound.

To ensure the presentation is readable, we define a few short hands. We will
use $H$ and $\tilde{H}$ to denote the Hessian of $F_{s}$ and $F_{s}+f$
respectively and subscript $1$ $2$ indicates whether the Hessian evaluated at
at $\theta^{*}$ or $\tilde{\theta}^{*}$. $H$ without any subscript or
superscript represents the Hessian of $F_{s}$ evaluated at $\xi$ as previously
used.

$\displaystyle(*)=\frac{1}{2}\log\frac{|H_{1}|}{|H|}\frac{|H|}{|H_{2}|}\frac{|H_{2}|}{|\tilde{H}_{2}|}\leq\frac{1}{2}\left[\log\frac{|H_{1}|}{|H|}+\log\frac{|H|}{|H_{2}|}+\log\frac{|H_{2}|}{|\tilde{H}_{2}|}\right]$

By the $R$-generalized self-concordance of $F_{s}$, we can apply Lemma D.3,

$-\|\theta^{*}-\xi\|_{2}R\leq\log\frac{|H_{1}|}{|H|}\leq
R\|\theta^{*}-\xi\|_{2},\quad-R\|\xi-\tilde{\theta}^{*}\|_{2}\leq\log\frac{|H|}{|H_{2}|}\leq
R\|\xi-\tilde{\theta}^{*}\|_{2}.$

The generalized linear model ensures that the Hessian of $f$ is rank-$1$:

$\nabla^{2}f(\tilde{\theta}^{*})=l^{\prime\prime}(y,x^{T}\tilde{\theta}^{*})xx^{T}$

and we can apply Lemma LABEL:lem:determinant in both ways (taking $A=H_{2}$
and $A=\tilde{H}_{2}$) and obtain

$\frac{|H_{2}|}{|\tilde{H}_{2}|}=\frac{1}{1+l^{\prime\prime}(y,x^{T}\tilde{\theta}^{*})x^{T}H_{2}^{-1}x}=1-l^{\prime\prime}(y,x^{T}\tilde{\theta}^{*})x^{T}\tilde{H}_{2}x$

Note that
$l^{\prime\prime}(y,x^{T}\tilde{\theta}^{*})x^{T}\tilde{H}_{2}^{-1}x$ is the
in-sample leverage-score and
$l^{\prime\prime}(y,x^{T}\tilde{\theta}^{*})x^{T}H_{2}^{-1}x$ is the out-of-
sample leverage-score of the locally linearized problem at
$\tilde{\theta}^{*}$. We denote them by $\mu_{2}$ and $\mu^{\prime}_{2}$
respectively (similarly, for the consistency of notations, we denote the in-
sample and out of sample leverage score at $\theta^{*}$ by $\mu_{1}$ and
$\mu^{\prime}_{1}$ ).

Combine the above arguments we get

$\displaystyle(*)\leq$ $\displaystyle
R\|\theta^{*}-\xi\|_{2}+R\|\xi-\tilde{\theta}^{*}\|_{2}+\log(1-\mu_{2})\leq
R\|\theta^{*}-\tilde{\theta}^{*}\|_{2}+\log(1-\mu_{2})$ (6)
$\displaystyle(*)\geq$
$\displaystyle-R\|\theta^{*}-\tilde{\theta}^{*}\|_{2}-\log(1-\mu_{2}).$ (7)

We now move on to deal with the second part, where we would like to express
everything in terms of $\|\theta-\theta^{*}\|_{H_{1}}$, which we know from the
algorithm is $\chi$-distributed.

$\displaystyle(**)=\frac{\gamma}{2}\left[\|\theta-\theta^{*}\|_{H_{1}}^{2}-\|\theta-\theta^{*}\|_{H_{2}}^{2}+\|\theta-\theta^{*}\|_{H_{2}}^{2}-\|\theta-\tilde{\theta}^{*}\|_{H_{2}}^{2}+\|\theta-\tilde{\theta}^{*}\|_{H_{2}}^{2}-\|\theta-\tilde{\theta}^{*}\|_{\tilde{H}_{2}}^{2}\right]$

By the generalized self-concordance at $\theta^{*}$

$\displaystyle
e^{-R\|\theta^{*}-\tilde{\theta}^{*}\|_{2}}\|\cdot\|_{H_{1}}^{2}\leq\|\cdot\|_{H_{2}}^{2}\leq
e^{R\|\theta^{*}-\tilde{\theta}^{*}\|_{2}}\|\cdot\|_{H_{1}}^{2}$

This allows us to convert from $\|\cdot\|_{H_{2}}$ to $\|\cdot\|_{H_{1}}$, and
as a consequence:

$\left|\|\theta-\theta^{*}\|_{H_{1}}^{2}-\|\theta-\theta^{*}\|_{H_{2}}^{2}\right|\leq[e^{R\|\theta^{*}-\tilde{\theta}^{*}\|_{2}}-1]\|\theta-\theta^{*}\|_{H_{1}}^{2}.$

Also,

$\displaystyle\|\theta-\theta^{*}\|_{H_{2}}^{2}-\|\theta-\tilde{\theta}^{*}\|_{H_{2}}^{2}$
$\displaystyle=\left\langle\tilde{\theta}^{*}-\theta^{*},2\theta-2\theta^{*}+\theta^{*}-\tilde{\theta}^{*}\right\rangle_{H_{2}}=2\langle\theta-\theta^{*},\tilde{\theta}^{*}-\theta^{*}\rangle_{H_{2}}-\|\theta^{*}-\tilde{\theta}^{*}\|_{H_{2}}^{2}$

Therefore

$\displaystyle\left|\|\theta-\theta^{*}\|_{H_{2}}^{2}-\|\theta-\tilde{\theta}^{*}\|_{H_{2}}^{2}\right|$
$\displaystyle\leq
2\|\theta-\theta^{*}\|_{H_{2}}\|\theta^{*}-\tilde{\theta}^{*}\|_{H_{2}}+\|\theta^{*}-\tilde{\theta}^{*}\|_{H_{2}}^{2}$
$\displaystyle\leq
2e^{R\|\tilde{\theta}^{*}-\theta^{*}\|_{2}}\|\theta-\theta^{*}\|_{H_{1}}\|\theta^{*}-\tilde{\theta}^{*}\|_{H}+e^{R\|\tilde{\theta}^{*}-\theta^{*}\|_{2}}\|\theta^{*}-\tilde{\theta}^{*}\|_{H}^{2}.$

Then lastly we have

$\displaystyle
0\geq\|\theta-\tilde{\theta}^{*}\|_{H_{2}}^{2}-\|\theta-\tilde{\theta}^{*}\|_{\tilde{H}_{2}}^{2}$
$\displaystyle=-l^{\prime\prime}(y,x^{T}\tilde{\theta}^{*})\left[\langle
x,\theta-\theta^{*}\rangle+\langle
x,\theta^{*}-\tilde{\theta}^{*}\rangle\right]^{2}$
$\displaystyle\geq-2\beta\|x\|_{H_{1}^{-1}}^{2}\|\theta-\theta^{*}\|_{H_{1}}^{2}-2\beta\|x\|_{H^{-1}}^{2}\|\theta^{*}-\tilde{\theta}^{*}\|_{H}^{2}$
$\left|\|\theta-\tilde{\theta}^{*}\|_{H_{2}}^{2}-\|\theta-\tilde{\theta}^{*}\|_{\tilde{H}_{2}}^{2}\right|\leq
2\beta\|x\|_{H_{1}^{-1}}^{2}\|\theta-\theta^{*}\|_{H_{1}}^{2}+2\beta\|x\|_{H^{-1}}^{2}\|\theta^{*}-\tilde{\theta}^{*}\|_{H}^{2}$

Combine the above derivations, we get

$\displaystyle\left|(**)\right|\leq\frac{\gamma}{2}\left[a\|\theta-\theta^{*}\|_{H_{1}}^{2}+b\|\theta-\theta^{*}\|_{H_{1}}+c\right]$
(8)

where

$\displaystyle a:=$
$\displaystyle\left[e^{R\|\theta^{*}-\tilde{\theta}^{*}\|_{2}}-1+2\beta\|x\|_{H_{1}^{-1}}^{2}\right]$
$\displaystyle b:=$ $\displaystyle
2e^{R\|\theta^{*}-\tilde{\theta}^{*}\|_{2}}\|\theta^{*}-\tilde{\theta}^{*}\|_{H}$
$\displaystyle c:=$
$\displaystyle(e^{R\|\theta^{*}-\tilde{\theta}^{*}\|_{2}}+2\beta\|x\|_{H^{-1}}^{2})\|\theta^{*}-\tilde{\theta}^{*}\|_{H}^{2}$

Lastly, by (6) and $\eqref{eq:der_part2}$,

$\left|\log\frac{p(\theta|Z)}{p(\theta|Z^{\prime})}\right|\leq
R\|\theta^{*}-\tilde{\theta}^{*}\|_{2}+\log(1-\mu_{2})+\frac{\gamma}{2}[aW^{2}+bW+c].$

where according to the algorithm $W:=\|\theta-\theta^{*}\|_{H_{1}}$ follows a
half-normal distribution with $\sigma=\gamma^{-1/2}$.

By standard Gaussian tail bound, we have for all $\delta<2/e$.

$\mathbb{P}(|W|\leq\gamma^{-1/2}\sqrt{\log(2/\delta)})\leq\delta.$

This implies that a high probability upper bound of the absolute value of the
privacy loss random variable $\log\frac{p(\theta|Z)}{p(\theta|Z^{\prime})}$
under $p(\theta|Z)$. By the tail bound to privacy conversion lemma (Lemma
LABEL:lem:tailbound2DP), we get that for any set $S\subset\Theta$
$\mathbb{P}(\theta\in S|Z)\leq e^{\epsilon}\mathbb{P}(\theta\in
S|Z^{\prime})+\delta$ for any $0<\delta<2/e$ and

$\epsilon=R\|\theta^{*}-\tilde{\theta}^{*}\|_{2}+\log(1-\mu_{2})+\frac{\gamma
c}{2}+\frac{a}{2}\log(2/\delta)+\frac{\gamma^{1/2}b}{2}\sqrt{\log(2/\delta)}.$

Denote $v:=\theta^{*}-\tilde{\theta}^{*}$, by strong convexity

$\|v\|_{2}\leq\|\nabla
l(y,x^{T}\theta)[\tilde{\theta}^{*}]\|_{2}/\alpha=|l^{\prime}|\|x\|_{2}/\alpha\leq
L\|x\|_{2}/\alpha$

and

$\|v\|_{H}\leq\|\nabla
l(y,x^{T}\theta)[\tilde{\theta}^{*}]\|_{H^{-1}}=|l^{\prime}|\|x\|_{H^{-1}}\leq
L\|x\|_{H^{-1}}.$

Also use the fact that $|\log(1-\mu_{2})|\leq 2\mu_{2}$ for $\mu_{2}<0.5$ and
$\mu_{2}\leq\beta\|x\|_{\tilde{H}_{2}^{-1}}^{2}$, we can then combine similar
terms and have a more compact representation.

$\epsilon\leq\epsilon_{0}(1+\log(2/\delta))+e^{\frac{RL\|x\|_{2}}{\alpha}}\left[\frac{\gamma
L^{2}\|x\|_{H^{-1}}^{2}}{2}+\sqrt{\gamma
L^{2}\|x\|_{H^{-1}}^{2}\log(2/\delta)}\right]$

where

$\epsilon_{0}\leq
e^{\frac{RL\|x\|_{2}}{\alpha}}-1+2\beta\|x\|_{H_{1}^{-1}}^{2}+2\beta\|x\|_{\tilde{H}_{2}^{-1}}^{2}$

is the part of the privacy loss that does not get smaller as $\gamma$
decreases.

######  Proposition D.2.

Let $\|\cdot\|$ be a norm and $\|\cdot\|_{*}$ be its dual norm. Let
$F(\theta)$, $f(\theta)$ and $\tilde{F}(\theta)=F(\theta)+f(\theta)$ be proper
convex functions and $\theta^{*}$ and $\tilde{theta}^{*}$ be their minimizers,
i.e., $0\in\partial F(\theta^{*})$ and
$0\in\partial\tilde{F}(\tilde{theta}^{*})$. If in addition, $F,\tilde{F}$ is
$\alpha,\tilde{\alpha}$-strongly convex with respect to $\|\cdot\|$ within the
restricted domain
$\theta\in\\{t\theta^{*}+(1-t)\tilde{\theta}^{*}\;|\;t\in[0,1]\\}$. Then there
exists $g\in\partial f(\theta^{*})$ and $\tilde{g}\in\partial
f(\tilde{\theta}^{*})$ such that

$\|\theta^{*}-\tilde{\theta}^{*}\|\leq\min\left\\{\frac{1}{\alpha}\|\tilde{g}\|_{*},\frac{1}{\tilde{\alpha}}\|g\|_{*}\right\\}.$

###### Proof.

Apply the first order condition to $F$ restricted to the line segment between
$\tilde{\theta}^{*}$ and $\theta^{*}$, there are we get

$\displaystyle F(\tilde{\theta}^{*})\geq F(\theta^{*})+\langle\partial
F(\theta^{*}),\tilde{\theta}^{*}-\theta^{*}\rangle+\frac{\alpha}{2}\|\tilde{\theta}^{*}-\theta^{*}\|^{2}$
(9) $\displaystyle F(\theta^{*})\geq F(\tilde{\theta}^{*})+\langle\partial
F(\tilde{\theta}^{*}),\theta^{*}-\tilde{\theta}^{*}\rangle+\frac{\alpha}{2}\|\tilde{\theta}^{*}-\theta^{*}\|^{2}$
(10)

Note by the convexity of $F$ and $f$, $\partial\tilde{F}=\partial F+\partial
f$, where $+$ is the Minkowski Sum. Therefore,
$0\in\partial\tilde{F}(\tilde{\theta}^{*})$ implies that there exists
$\tilde{g}$ such that $\tilde{g}\in\partial f(\tilde{\theta}^{*})$ and
$-\tilde{g}\in\partial F(\tilde{\theta}^{*})$. Take $-\tilde{g}\in\partial
F(\tilde{\theta}^{*})$ in Equation 10 and $0\in\partial F(\theta^{*})$ in
Equation 9 and add the two inequalities, we obtain

$0\geq\langle-\tilde{g},\theta^{*}-\tilde{\theta}^{*}\rangle+\alpha\|\tilde{\theta}^{*}-\theta^{*}\|^{2}\geq-\|\tilde{g}\|_{*}\|\theta^{*}-\tilde{\theta}^{*}\|+\alpha\|\tilde{\theta}^{*}-\theta^{*}\|^{2}.$

For $\|\tilde{\theta}^{*}-\theta^{*}\|=0$ the claim is trivially true,
otherwise, we can divide the both sides of the above inequality by
$\|\tilde{\theta}^{*}-\theta^{*}\|$ and get
$\|\theta^{*}-\tilde{\theta}^{*}\|\leq\frac{1}{\alpha}\|\tilde{g}\|_{*}$.

It remains to show that
$\|\theta^{*}-\tilde{\theta}^{*}\|\leq\frac{1}{\tilde{\alpha}}\|g\|_{*}$. This
can be obtained by exactly the same arguments above but applying strong
convexity to $\tilde{F}$ instead. Note that we can actually get something
slightly stronger than the statement because the inequality holds for all
$g\in\partial f(\theta^{*})$. ∎

A consequence of (generalized) self-concordance is the spectral
(_multiplicative_) stability of Hessian to small perturbations of parameters.

######  Lemma D.3 (Stability of Hessian(Nesterov and Nemirovskii, 1994,
Theorem 2.1.1), (Bach, 2010, Proposition 1)).

Let $H_{\theta}:=\nabla^{2}F_{s}(\theta)$. If $F_{s}$ is $R$-self-concordant
at $\theta$. Then for any $v$ such that $R\|v\|_{H_{\theta}}<1$, we have that

$(1-R\|v\|_{H_{\theta}})^{2}\nabla^{2}F_{s}(\theta)\prec\nabla^{2}F_{s}(\theta+v)\prec\frac{1}{(1-R\|v\|_{H_{\theta}})^{2}}\nabla^{2}F_{s}(\theta).$

If instead we assume $F_{s}$ is $R$-generalized-self-concordant at $\theta$
with respect to norm $\|\cdot\|$, then

$e^{-R\|v\|}\nabla^{2}F_{s}(\theta)\prec\nabla^{2}F_{s}(\theta+v)\prec
e^{R\|v\|}\nabla^{2}F_{s}(\theta)$

The two bounds are almost identical when $R\|v\|$ and $R\|v\|_{\theta}$ are
close to $0$, in particular, for $x\leq 1/2$, $e^{-2x}\leq 1-x\leq e^{-x}$.

## References

  * Bach [2010] Francis Bach.  Self-concordant analysis for logistic regression.  _Electronic Journal of Statistics_ , 4:384–414, 2010.
  * Chaudhuri et al. [2011] Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate.  Differentially private empirical risk minimization.  _Journal of Machine Learning Research_ , 12(3), 2011.
  * Decarolis et al. [2020] Chris Decarolis, Mukul Ram, Seyed Esmaeili, Yu-Xiang Wang, and Furong Huang.  An end-to-end differentially private latent dirichlet allocation using a spectral algorithm.  In _International Conference on Machine Learning_ , pages 2421–2431. PMLR, 2020.
  * Dwork and Lei [2009] Cynthia Dwork and Jing Lei.  Differential privacy and robust statistics.  In _ACM symposium on Theory of computing_ , pages 371–380, 2009.
  * Dwork et al. [2006] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of cryptography conference_ , pages 265–284. Springer, 2006.
  * Dwork et al. [2014] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang.  Analyze gauss: optimal bounds for privacy-preserving principal component analysis.  In _Proceedings of the forty-sixth annual ACM symposium on Theory of computing_ , pages 11–20, 2014.
  * Gopi et al. [2022] Sivakanth Gopi, Yin Tat Lee, and Daogao Liu.  Private convex optimization via exponential mechanism.  _arXiv preprint arXiv:2203.00263_ , 2022.
  * Kasiviswanathan et al. [2013] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  Analyzing graphs with node differential privacy.  In _Theory of Cryptography Conference_ , pages 457–476. Springer, 2013.
  * 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. JMLR Workshop and Conference Proceedings, 2012.
  * Liu and Talwar [2019] Jingcheng Liu and Kunal Talwar.  Private selection from private candidates.  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , pages 298–309, 2019.
  * Liu et al. [2021] Xiyang Liu, Weihao Kong, and Sewoong Oh.  Differential privacy and robust statistics in high dimensions.  _arXiv preprint arXiv:2111.06578_ , 2021.
  * Minami et al. [2016] Kentaro Minami, HItomi Arai, Issei Sato, and Hiroshi Nakagawa.  Differential privacy without sensitivity.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Mironov [2017] Ilya Mironov.  Rényi differential privacy.  In _2017 IEEE 30th computer security foundations symposium (CSF)_ , pages 263–275. IEEE, 2017.
  * Nesterov and Nemirovskii [1994] Yurii Nesterov and Arkadii Nemirovskii.  _Interior-point polynomial algorithms in convex programming_.  SIAM, 1994.
  * Nissim et al. [2007] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  Smooth sensitivity and sampling in private data analysis.  In _ACM symposium on Theory of computing (STOC-07)_ , pages 75–84. ACM, 2007.
  * Papernot and Steinke [2021] Nicolas Papernot and Thomas Steinke.  Hyperparameter tuning with renyi differential privacy.  _arXiv preprint arXiv:2110.03620_ , 2021.
  * Papernot et al. [2017] Nicolas Papernot, Martín Abadi, Úlfar Erlingsson, Ian Goodfellow, and Kunal Talwar.  Semi-supervised knowledge transfer for deep learning from private training data.  In _International Conference on Learning Representations (ICLR-17)_ , 2017.
  * Papernot et al. [2018] Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson.  Scalable private learning with pate.  _arXiv preprint arXiv:1802.08908_ , 2018.
  * Redberg and Wang [2021] Rachel Redberg and Yu-Xiang Wang.  Privately publishable per-instance privacy.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Soria-Comas et al. [2017] Jordi Soria-Comas, Josep Domingo-Ferrer, David Sánchez, and David Megías.  Individual differential privacy: A utility-preserving formulation of differential privacy guarantees.  _IEEE Transactions on Information Forensics and Security_ , 12(6):1418–1429, 2017.
  * Thakurta and Smith [2013] Abhradeep Guha Thakurta and Adam Smith.  Differentially private feature selection via stability arguments, and the robustness of the lasso.  In _Conference on Learning Theory_ , pages 819–850. PMLR, 2013.
  * Vadhan [2017] Salil Vadhan.  The complexity of differential privacy.  In _Tutorials on the Foundations of Cryptography_ , pages 347–450. Springer, 2017.
  * Wang et al. [2022] Jiachen T Wang, Saeed Mahloujifar, Shouda Wang, Ruoxi Jia, and Prateek Mittal.  Renyi differential privacy of propose-test-release and applications to private and robust machine learning.  _arXiv preprint arXiv:2209.07716_ , 2022.
  * Wang [2017] Yu-Xiang Wang.  Per-instance differential privacy and the adaptivity of posterior sampling in linear and ridge regression.  _arXiv preprint arXiv:1707.07708_ , pages 48–71, 2017.
  * Wang [2018] Yu-Xiang Wang.  Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain.  _arXiv preprint arXiv:1803.02596_ , 2018.
  * Wang et al. [2015] Yu-Xiang Wang, Stephen Fienberg, and Alex Smola.  Privacy for free: Posterior sampling and stochastic gradient monte carlo.  In _International Conference on Machine Learning_ , pages 2493–2502. PMLR, 2015.