# Generalization in the Face of Adaptivity: A Bayesian Perspective

Moshe Shenfeld111The Hebrew University of Jerusalem<EMAIL_ADDRESS>Katrina Ligett222The Hebrew University of Jerusalem<EMAIL_ADDRESS>
###### Abstract

Repeated use of a data sample via adaptively chosen queries can rapidly lead
to overfitting, wherein the issued queries yield answers on the sample that
differ wildly from the values of those queries on the underlying data
distribution. Differential privacy provides a tool to ensure generalization
despite adaptively-chosen queries [DFH+15, BNS+21, JLN+20], but its worst-case
nature means that it cannot, for example, yield improved results for low-
variance queries. In this paper, we give a simple new characterization that
illuminates the core problem of adaptive data analysis. We show explicitly
that the harms of adaptivity come from the covariance between the behavior of
future queries and a Bayes factor-based measure of how much information about
the data sample was encoded in the responses given to past queries. We
leverage this intuition to introduce a new stability notion; we then use it to
prove new generalization results for the most basic noise-addition mechanisms
(Laplace and Gaussian noise addition), with guarantees that scale with the
variance of the queries rather than the square of their range. Our
characterization opens the door to new insights and new algorithms for the
fundamental problem of achieving generalization in adaptive data analysis.

##  1 Introduction

Recent years have seen growing recognition of the role of _adaptivity_ in
causing overfitting and thereby reducing the accuracy of the conclusions drawn
from data. Allowing a data analyst to adaptively choose the queries that she
issues intuitively potentially leads to misleading conclusions because the
results of prior queries might encode information that is specific to the
available data sample (but not relevant to the underlying distribution from
which it was drawn). As a result, future queries might then be chosen to
leverage these sample-specific properties, giving answers on the sample that
differ wildly from the values of those queries on the data distribution. Such
adaptivity has been blamed, in part, for the current reproducibility crisis in
the data-driven sciences [Ioa05, GL16].

A series of works catalyzed by [DFH+15] recently established a formal
framework for understanding and analyzing adaptivity in data analysis, and
introduced a general toolkit for provably preventing the harms of choosing
queries adaptively—that is, as a function of the results of previous queries.
This line of work has established that enforcing that computations obey a
constraint of _differential privacy_ [DMNS06]–which one can interpret as a
robustness or stability requirement on computations—provably limits the extent
to which adaptivity can cause overfitting. Practically, for simple numerical
computations, these results translate into adding a level of noise to the
query results that would be sufficient to ensure _worst-case_ stability of the
_worst-case_ query on the _worst-case_ dataset. The challenge is to choose a
level of noise addition that protects against leaking information about the
input dataset while not overly distorting the results.

In the present paper, we give a simple new characterization (Lemma 3.6) that
shows explicitly that the harms of adaptivity come from the covariance between
the behavior of the future queries and a Bayes factor-based measure of how
much information about the data sample was encoded in the responses given to
past queries. Our characterization gives insight into how differential privacy
protects against adaptivity, and then allows us to step away from this worst-
case approach. What differential privacy accomplishes is that it bounds a
worst-case version of the Bayes factor. But this can be overkill: for the
purposes of statistical validity, we do not care about the _worst-case_ Bayes
factor but its typical case, and even if the results of past queries fully
encoded the data sample, there would only be a risk of overfitting if an
analyst were to _leverage_ this encoded information in her choice of future
queries.

We then build on this characterization to offer new and better generalization
guarantees for simple, existing noise-addition algorithms, via a new stability
notion we introduce (Definition 4.2). In particular, we show (Corollaries 5.5,
5.7) that the addition of Laplace or Gaussian noise protects against
adaptivity even when the size of the available dataset scales only with the
_variance_ of the issued queries on the underlying data distribution. This is
in contrast to the results naturally obtainable via differential privacy,
which suggest that the dataset scale with the square of the _worst-case_
change in query value that could be induced by changing a single input data
element. This also allows us to state generalization guarantees even for
_unbounded_ queries (Theorem 5.3), so long as their tail behavior on the
underlying data distribution is sub-Gaussian. Such guarantees for unbounded
queries could not have been obtained through the toolkit of differential
privacy in a natural fashion—even computationally inefficiently—because of
differential privacy’s worst-case nature; in contrast, the algorithms we
analyze are all computationally efficient.

Compared with the prior state of the art, the insight of Lemma 3.6 can
potentially enable dramatically more queries to be issued against a dataset
before its statistical validity is “spent” and the data must be discarded,
opening the door for future innovations in adaptive data analysis—both
theoretical and practical.

${q}\left(D\right)$${q}\left(s\right)$${M}\left(s,q\right)$sample
stabilitysample accuracydistribution accuracy Figure 1: Distribution accuracy
via sample accuracy and sample stability

${q}\left(D\right)$${q}\left(D^{r}\right)$${M}\left(s,q\right)$Bayes
stabilityposterior accuracydistribution accuracy Figure 2: Distribution
accuracy via posterior accuracy and Bayes stability

#### Our approach

Consider a scientist who wishes to to evaluate a query $q$ on some underlying
data distribution $D$, but who only has access to a sample $s$ from that
distribution. In the context of adaptive data analysis, this fundamental goal,
known as _generalization_ , can be approached according to the diagram in
Figure 2: the goal is for the response $r={M}\left(s,q\right)$ given by the
scientist’s data analysis mechanism $M$ to closely track ${q}\left(D\right)$
(distribution accuracy), and a way to achieve this is via a triangle
inequality—if ${q}\left(s\right)$ is simultaneously close to
${M}\left(s,q\right)$ (a guarantee of sample accuracy) and also close to
${q}\left(D\right)$ (a guarantee of sample stability), together this
immediately yields a distribution accuracy guarantee.

The work of [JLN+20] implicitly offers an alternative triangle-inequality
approach to obtaining distribution accuracy guarantees in the context of
adaptive data analysis, depicted in Figure 2. This approach—detailed in
Section 3—replaces ${q}\left(s\right)$ in the triangle with
${q}\left(D^{r}\right)$ (formally defined in Section 2.1)—namely, the query as
evaluated on the posterior data distribution induced by observing the
response(s) to previous query(s) and updating a prior belief of $D$. If the
present query $q$ behaves similarly on the prior distribution $D$ as it does
on this posterior (a guarantee we call _Bayes Stability_ ; Definition 3.4),
and if the response given by the scientist’s mechanism is also close to
${q}\left(D^{r}\right)$ (a guarantee we call posterior accuracy), together
this implies a guarantee of distribution accuracy (Definition 2.1).333This can
be viewed as a generalization of the _Hypothesis Stability_ notion of [BE02],
which was proven to guarantee on-average generalization [SSSSS10], where the
hypothesis is a post-processing of $r$, and $q$ is the loss function
estimation.

We prove that sample accuracy implies posterior accuracy (Lemma 3.1), and so
the key challenge in achieving distribution accuracy in adaptive settings is
ensuring Bayes stability. Our approach considers the Bayes factor comparing
the prior likelihood of a data element versus its posterior likelihood given
the history of query responses so far. Intuitively, this Bayes factor measures
the extent to which the query-response sequence encodes information that is
particular to the dataset as opposed to the data distribution—this quantity
represents the “potential for overfitting” enabled by past queries. A simple
yet powerful new lemma (Lemma 3.6) shows that bounding the covariance between
a new query and this Bayes factor provably limits the extent to which the
choice of the current query leverages this potential for overfitting.

Leveraging this intuition, in Section 4 we introduce _Linear Bayesian
Indistinguishability (LBI)_ (Definition 4.2), which captures the extent to
which replacing one data element by another would be “noticeable,” given a
particular query-response sequence. This stability loss is thus a function of
particular swapped elements (instead of worst-case), and it also depends on
the actual responses provided by the mechanism. We then build a composition
toolkit (Theorem 4.6) that allows us to track LBI losses over multiple
computations.

The LBI stability measure allows for more careful analysis of the information
encoded by the query-response sequence, which results in distribution accuracy
guarantees that scale as the standard deviation of the queries instead their
range (Theorem 5.1). Furthermore (Theorem 5.3), it can be used to extend
generalization guarantees from bounded queries (Definition 2.2) to sub-
Gaussian queries (Definition 5.2).

#### Related work

_Differential privacy_ [DMNS06] is a privacy notion based on requiring that
the output distributions induced by any two neighboring input datasets
(datasets which differ in one element) satisfy an _indistinguishability_
notion (see Definition 4.1). One natural way to enforce differential privacy
is by directly adding noise to the results of a numeric-valued query, where
the noise is calibrated to the _global sensitivity_ of the function to be
computed—the maximal change in its value between any two neighboring datasets.
[DFH+15, BNS+21] showed that differential privacy is also useful as tool for
ensuring generalization in settings where the queries are chosen adaptively.

Differential privacy essentially provides the optimal asymptotic
generalization guarantees given adaptive queries [HU14, SU15, NSS+18].
However, its optimality is for worst-case adaptive queries, and the guarantees
that it offers only beat the naive intervention—of splitting a dataset so that
each query gets fresh data—when the input dataset is quite huge [JLN+20]. A
worst-case approach makes sense for privacy, but for statistical guarantees
like generalization, we only need statements that hold with high probability,
and only on the actual queries issued.

One cluster of works proposes relaxed privacy definitions (e.g., [GHLP12,
BGKS13, KS14]) that leverage the natural noise introduced by dataset sampling
to achieve more average-case notions of privacy. This builds on intuition that
average-case privacy can be viewed from a Bayesian perspective, by restricting
some distance measure between some prior distribution and some posterior
distribution induced by the mechanism’s behavior. [BF16] connect this Bayesian
intuition to statistical validity, via an approach that discards “unlikely”
databases that do not obey a differential privacy guarantee. Our approach,
reflected in Definition 4.2, does a more subtle accounting, tracking the
extent to which each data element contributes to instability, which allows us
to surface the dependence on the variance of the queries.

Another line of work focuses on giving privacy guarantees that are tailored
(“local”) to the dataset at hand [NRS07, ESS15, Wan19]. [FZ20] elegantly
manage to track the local privacy loss of the elements in the dataset.
However, they use a removal (rather than swapping) flavor of the neighbor
notion in their privacy definition, and so do not enjoy the dependence on the
standard deviation. In this vein on the adaptivity side, creative, specialized
mechanisms have been proposed to achieve adaptive data analysis guarantees
that scale like the standard deviation of the queries [FS17] and that provide
accuracy guarantees for sub-Gaussian queries [BS19]. [FS18] give a more
natural mechanism, but the accuracy guarantee they provide holds only for the
expected error rather than with high probability. We provide accuracy
guarantees that scale with the query variance (technically, with known bounds
on the variance rather than with the actual variance) and hold for sub-
Gaussian queries, but unlike [FS17, BS19], we do not rely on specialized
mechanisms and unlike [FS18], we achieve high-probability results.

[SL19] prove a new notion, _local statistical stability (LSS)_ , is both
necessary and sufficient for generalization under adaptivity. Unfortunately,
LSS does not enjoy natural composition guarantees, and has thus yielded no new
algorithmic insights. Section 6 discusses how the present paper overcomes this
challenge. In more empirically driven approaches, [ZH19] restrict to “natural
analysts” issuing queries with limited internal state and adaptivity, and
[RRS+20] give a mechanism where the dataset is split, one part used for
“guessing” the responses and the other for checking them, and only terminates
when the two differ—in practice, this may answer more than the worst-case
number of queries.

##  2 Preliminaries

###  2.1 Setting

We study datasets, each of fixed size $n\in\mathbb{N}$, whose elements are
drawn from some domain $\mathcal{X}$. We assume there exists some distribution
$D_{\mathcal{X}^{n}}$ defined over the datasets $s\in\mathcal{X}^{n}$, which
in turn induces a distribution $D_{\mathcal{X}}$ over the elements
$x\in\mathcal{X}$ (by sampling a dataset, then uniformly sampling an element
from it). All of the distributions discussed in this subsection are more
formally defined in Appendix A.

We assume there exists a family of functions (_queries_) $\mathcal{Q}$ of the
form $q:\mathcal{X}^{n}\rightarrow\mathbb{R}^{d}$ for some $d\in\mathbb{N}$.
We denote $\mathcal{R}\coloneqq\mathbb{R}^{d}$ and refer to it as the
_range_.444Most of the definitions and claims in this paper can be extended
beyond $\mathbb{R}^{d}$ and the Euclidean norm, but we chose to focus on this
setting due to the variance based bounds achieved in Section 5. We denote
${q}\left(D_{\mathcal{X}^{n}}\right)\coloneqq\underset{S\sim
D_{\mathcal{X}^{n}}}{\mathbb{E}}\left[{q}\left(S\right)\right]$ and think of
it as the “true” value of the query $q$, which we wish to estimate. As is the
case in many machine learning or data-driven science settings, we do not have
direct access to the distribution over datasets, but instead receive a dataset
$s$ sampled from $D_{\mathcal{X}^{n}}$, which can be used to compute
${q}\left(s\right)$—the empirical value of the query. This quantity can be
thought of as a random variable with distribution induced by
$D_{\mathcal{X}^{n}}$, which allows us to refer to the _standard deviation_ of
a query, or to a query having _sub-Gaussian_ distribution (Definition 5.2).

A _mechanism_ $M$ is a (possibly non-deterministic) function
$M:\mathcal{X}^{n}\times\mathcal{Q}\rightarrow\mathcal{R}$ which, given a
dataset $s\in\mathcal{X}^{n}$ and a query $q\in\mathcal{Q}$, provides some
response $r\in\mathcal{R}$. The most trivial mechanism would simply provide
$r={q}\left(s\right)$. In particular, we will study two mechanisms, the
Laplace Mechanism and Gaussian Mechanism (Definitions 2.3 and 2.4,
respectively), each of which adds noise to ${q}\left(s\right)$. A mechanism
induces a distribution over the range of responses
${D_{\mathcal{R}|\mathcal{X}^{n}}^{q}}\left(\cdot\,|\,s\right)$—indicating the
probability that each response $r$ will be the output of the mechanism, given
$s$ and $q$ as input. Combining this with $D_{\mathcal{X}^{n}}$ induces
distributions $D_{\mathcal{R}|\mathcal{X}}^{q}$, $D_{\mathcal{R}}^{q}$,
$D_{\mathcal{X}^{n}|\mathcal{R}}^{q}$ and
$D^{r}\coloneqq{D_{\mathcal{X}|\mathcal{R}}^{q}}\left(\cdot\,|\,r\right)$.
This last distribution, $D^{r}$, is central to our analysis, and it represents
the _posterior distribution_ over the sample elements given an observed
response—a Bayesian update with respect to a prior of $D$.

An _analyst_ $A$ is a (possibly non-deterministic) function
$A:\mathcal{R}^{*}\rightarrow\mathcal{Q}$ which, given a sequence of
responses, provides the next query. An interaction between a mechanism and an
analyst— wherein repeatedly (and potentially adaptively) the analyst generates
a query, then the mechanism generates a response—generates a sequence of $k$
queries and responses for some $k\in\mathbb{N}$, which together we refer to as
a _view_ $v_{k}=\left(r_{1},r_{2},\ldots,r_{k}\right)\in\mathcal{V}_{k}$ (we
omit $k$ when it is clear from the context). In the case of a non-
deterministic analyst, we add its “coin tosses” as the first entry in the
view, in order to ensure each $q_{i}$ is a deterministic function of
$v_{i-1}$, as detailed in Definition A.3; given a view $v\in\mathcal{V}$, we
denote by $\bar{q}_{v}$ the sequence of queries that it induces. Slightly
abusing notation, we denote $v={M}\left(s,A\right)$. The distributions
$D_{\mathcal{R}|\mathcal{X}^{n}}^{q}$, $D_{\mathcal{R}|\mathcal{X}}^{q}$,
$D_{\mathcal{R}}^{q}$, $D_{\mathcal{X}^{n}|\mathcal{R}}^{q}$ and $D^{r}$
naturally extend to versions where a sequence of queries is generated by an
analyst: $D_{\mathcal{V}|\mathcal{X}^{n}}^{A}$,
$D_{\mathcal{V}|\mathcal{X}}^{A}$, $D_{\mathcal{V}}^{A}$,
$D_{\mathcal{X}^{n}|\mathcal{V}}^{A}$, and $D^{v}$.

Notice that $M$ holds $s$ but has no access to $D$. On the other hand, $A$
might have access to $D$, but her only information regarding $s$ comes from
$M$’s responses as represented by $D^{v}$. This intuitively turns some metric
of distance between $D$ and $D^{v}$ into a measure of potential overfitting,
an intuition that we formalize in Definition 3.4 and Lemma 3.6.

###  2.2 Notation

Throughout the paper, calligraphic letters denote domains (e.g.,
$\mathcal{X}$), lower case letters denote elements of domains (e.g.,
$x\in\mathcal{X}$), bold letters denote sets (e.g.,
$\mathbf{x}\subseteq\mathcal{X}$) and capital letters denote random variables
(e.g., $X\sim D_{\mathcal{X}}$).

We omit most superscripts and subscripts when clear from context (e.g.,
${D}\left(r\,|\,s\right)={D_{\mathcal{R}|\mathcal{X}^{n}}^{q}}\left(r\,|\,s\right)$
is the distribution over range elements in $\mathcal{R}$, conditioned on a
particular input dataset $s$, given a query $q$). Unless specified otherwise,
we assume $D_{\mathcal{X}^{n}}$, $n$ and $M$ are fixed, and omit them from
notations and definitions.

Whenever a property is defined with respect to some parameter, if we omit the
parameter from some statement about the property, we mean that the statement
holds for all parameter values (e.g., if the accuracy of a mechanism is
defined with respect to an analyst, when we say that $M$ is accurate we mean
it holds for all analysts).

We use the $\left\lVert\cdot\right\rVert$ notation to denote the Euclidean
norm. Other $p$-norms will be denoted by $\left\lVert\cdot\right\rVert_{p}$.

###  2.3 Definitions

We introduce terminology to describe the accuracy of responses that a
mechanism produces in response to queries.

######  Definition 2.1 (Accuracy of a mechanism).

Given $k\in\mathbb{N}$, a dataset $s$, an analyst $A$ issuing $k$ queries, and
a view $v={M}\left(s,A\right)$, we define three types of output error for the
mechanism:

  * •

Sample error:
${\text{err}_{S}}\left(s,v\right)\coloneqq\underset{i\in\left[k\right]}{\max}\left\lVert
r_{i}-{q_{i}}\left(s\right)\right\rVert$

  * •

Distribution error:
${\text{err}_{D}}\left(s,v\right)\coloneqq\underset{i\in\left[k\right]}{\max}\left\lVert
r_{i}-{q_{i}}\left(D\right)\right\rVert$

  * •

Posterior error:
${\text{err}_{P}}\left(s,v\right)\coloneqq\underset{i\in\left[k\right]}{\max}\left\lVert
r_{i}-{q_{i}}\left(D^{v_{i-1}}\right)\right\rVert$

where $q_{i}$ is the $i$th query and $r_{i}$ is the $i$th response contained
in $v$. These errors can be viewed as random variables with a distribution
that is induced by the underlying distribution $D$ and the internal randomness
of $M$ and $A$.

Given a non-increasing function
$\varphi:\mathbb{R}_{+}\rightarrow\left[0,1\right]$ (we refer to this function
as a tail distribution function), we say $M$ is _${\varphi}\left(\cdot\right)$
-Sample / Distribution / Posterior Accurate_ with respect to $A$, if for all
$\alpha\geq 0$,

$\underset{S\sim
D,V\sim{M}\left(S,A\right)}{\text{Pr}}\left[{\text{err}}\left(S,V\right)>\alpha\right]\leq{\varphi}\left(\alpha\right),$

where ${\text{err}}\left(s,v\right)$ refers to $\text{err}_{S}$ /
$\text{err}_{D}$ / $\text{err}_{P}$, respectively.

Given $\alpha,\beta\geq 0$ we say $M$ is _$\left(\alpha,\beta\right)$ -Sample
/ Distribution / Posterior Accurate_ with respect to $A$ if
${\varphi}\left(\alpha\right)=\beta$.

In this paper, we focus on a particular family of queries known as _linear
queries_ , and simple mechanisms that add Laplace- or Gaussian-distributed
noise.

######  Definition 2.2 (Linear queries).

A function $q:\mathcal{X}^{n}\rightarrow\mathbb{R}^{d}$ is a _linear query_ if
it is defined by a function $q_{1}:\mathcal{X}\rightarrow\mathbb{R}^{d}$ such
that
${q}\left(s\right)\coloneqq\frac{1}{n}\overset{n}{\underset{i=1}{\sum}}{q_{1}}\left(s_{i}\right)$.
For simplicity, we denote $q_{1}$ simply as $q$ throughout. We say $q$ is a
_$\Delta$ -bounded_ query if
$\left\lVert{q}\left(x\right)-{q}\left(y\right)\right\rVert\leq\Delta,$
$\forall x,y\in\mathcal{X}$.

######  Definition 2.3 (Laplace Mechanism).

Given $0\leq\eta$ and a query $q$, the Laplace mechanism with parameter $\eta$
is defined as: ${M}\left(s,q\right)={q}\left(s\right)+\xi$, where $\xi$ is a
random variable with unbiased Laplace
distribution–$\xi\sim\frac{1}{2\eta}e^{-\frac{\left|\xi\right|}{\eta}}$.

######  Definition 2.4 (Gaussian Mechanism).

Given $0\leq\eta$ and a query $q$, the Gaussian mechanism with parameter
$\eta$ is defined as: ${M}\left(s,q\right)={q}\left(s\right)+\xi$, where $\xi$
is a random variable with unbiased Gaussian distribution,
$\xi\sim\frac{1}{\sqrt{2\pi}\eta}e^{-\frac{\xi^{2}}{2\eta^{2}}}$.

##  3 Analyzing adaptivity-driven overfitting

In this section, we give a clean, new characterization of the harms of
adaptivity. Our goal is to bound the distribution error of a mechanism that
responds to queries generated by an adaptive analyst. As described in the
Introduction, this bound will be achieved via a triangle inequality, by
bounding both the posterior accuracy and the Bayes stability; these two
notions are the subject of the next two subsections. Missing proofs from this
section appear in Appendix C.

###  3.1 Posterior Accuracy

The simpler part of the argument is posterior accuracy, which we prove can be
inherited directly from the sample accuracy of a mechanism. This lemma
resembles Lemma 6 in [JLN+20], but has the advantage of being independent of
the range of the queries, which will come in handy in Theorem 5.3. We then
apply this lemma to the Laplace and Gaussian mechanisms.

######  Lemma 3.1 (Sample Accuracy implies Posterior Accuracy).

Given a tail distribution function $\varphi$ and an analyst $A$ issuing linear
queries, if a mechanism $M$ is ${\varphi}\left(\cdot\right)$-Sample Accurate
with respect to $A$, then it is ${\Phi}\left(\cdot\right)$-Posterior Accurate
for
${\Phi}\left(\alpha\right)\coloneqq\underset{c\in\left(0,\alpha\right)}{\inf}\left(\frac{1}{c}\int_{\alpha-c}^{\infty}{\varphi}\left(t\right)dt\right)$.

###### Proof Outline.

For any $v\in\mathcal{V}$, denote
${I}\left(v\right)\coloneqq\underset{i\in\left[k\right]}{\arg\max}\left\lVert
r_{i}-{q_{i}}\left(D^{v}\right)\right\rVert$, and $r_{v}\coloneqq
r_{{I}\left(v\right)},q_{v}\coloneqq q_{{I}\left(v\right)}$. When the view is
a random variable $V$, the corresponding query $Q_{V}$ and response $R_{V}$
are also random variables, and hence we denote them with capital letters. For
any $c\in\left(0,\alpha\right)$,

$\displaystyle\underset{V\sim D}{\text{Pr}}\left[\left\lVert
R_{V}-{Q_{V}}\left(D^{V}\right)\right\rVert>\alpha\right]$
$\displaystyle\leq\underset{V\sim D}{\text{Pr}}\left[\max\left\\{\left\lVert
R_{V}-{Q_{V}}\left(D^{V}\right)\right\rVert-\left(\alpha-c\right),0\right\\}>c\right]$
$\displaystyle\overset{\left(1\right)}{\leq}\frac{1}{c}\underset{V\sim
D}{\mathbb{E}}\left[\max\left\\{\left\lVert
R_{V}-{Q_{V}}\left(D^{V}\right)\right\rVert-\left(\alpha-c\right),0\right\\}\right]$
$\displaystyle\overset{\left(2\right)}{\leq}\frac{1}{c}\underset{V\sim
D,S\sim{D}\left(\cdot\,|\,V\right)}{\mathbb{E}}\left[\max\left\\{\left\lVert
R_{V}-{Q_{V}}\left(S\right)\right\rVert-\left(\alpha-c\right),0\right\\}\right]$
$\displaystyle\overset{\left(3\right)}{=}\frac{1}{c}\int_{0}^{\infty}\underset{S\sim
D,V\sim{M}\left(S,A\right)}{\text{Pr}}\left[\max\left\\{\left\lVert
R_{V}-{Q_{V}}\left(S\right)\right\rVert-\left(\alpha-c\right),0\right\\}>t\right]dt$
$\displaystyle=\frac{1}{c}\int_{\alpha-c}^{\infty}\underset{S\sim
D,V\sim{M}\left(S,A\right)}{\text{Pr}}\left[\left\lVert
R_{V}-{Q_{V}}\left(S\right)\right\rVert>s\right]ds$
$\displaystyle\overset{\left(4\right)}{\leq}\frac{1}{c}\int_{\alpha-c}^{\infty}{\varphi}\left(t\right)dt$

where (1) results from Markov’s inequality, (2) from the triangle inequality,
(3) from the fact that the expectation is taken over a non-negative random
variable and (4) by the definition of sample accuracy (Definition 2.1). ∎

######  Lemma 3.2 (Accuracy of Laplace Mechanism).

Given $\eta>0$ and $k\in\mathbb{N}$, the Laplace mechanism with noise
parameter $\eta$ which receives $k$ queries is
${\varphi}\left(\cdot\right)$-Sample Accurate for
${\varphi}\left(\alpha\right)\coloneqq ke^{-\frac{\alpha}{\eta}}$ and
${\Phi}\left(\cdot\right)$-Posterior Accurate for
${\Phi}\left(\alpha\right)\coloneqq ke^{1-\frac{\alpha}{\eta}}$ for any
$\alpha\geq\eta$.

######  Lemma 3.3 (Accuracy of Gaussian Mechanism).

Given $\eta>0$ and $k\in\mathbb{N}$, the Gaussian mechanism with noise
parameter $\eta$ which receives $k$ queries is
${\varphi}\left(\cdot\right)$-Sample Accurate for
${\varphi}\left(\alpha\right)\coloneqq\frac{k}{2}{\text{erfc}}\left(\frac{\alpha}{\sqrt{2}\eta}\right)\leq\frac{k\eta}{\sqrt{2\pi}\alpha}e^{-\frac{\alpha^{2}}{2\eta^{2}}}$
and ${\Phi}\left(\cdot\right)$-Posterior Accurate for
${\Phi}\left(\alpha\right)\coloneqq\frac{k\alpha}{\sqrt{2\pi}\eta}e^{1-\frac{\alpha^{2}}{2\eta^{2}}}$
for any $\alpha\geq\sqrt{2}\eta$.

###  3.2 Bayes Stability

In order to complete the triangle inequality, we have to define the stability
of the mechanism. Bayes stability captures the concept that the results
returned by a mechanism and the queries selected by the adaptive adversary are
such that the queries behave similarly on the true data distribution and on
the posterior distribution induced by those results. This notion first
appeared in a slightly different form in [JLN+20], under the name _Posterior
Sensitivity_.

######  Definition 3.4 (Bayes Stability).

Given $k\in\mathbb{N}$, a tail distribution function $\psi$, and an analyst
$A$ issuing $k$ queries, we say $M$ is _${\psi}\left(\cdot\right)$ -Bayes
Stable_ with respect to $A$, if for all $\epsilon\geq 0$,

$\underset{S\sim
D,V\sim{M}\left(S,A\right)}{\text{Pr}}\left[\underset{i\in\left[k\right]}{\max}\left\lVert{Q_{i}}\left(D^{V_{i-1}}\right)-{Q_{i}}\left(D\right)\right\rVert>\epsilon\right]\leq{\psi}\left(\epsilon\right).$

Given $\epsilon,\delta\geq 0$, we say $M$ is _$\left(\epsilon,\delta\right)$
-Bayes Stable_ with respect to $A$ if ${\psi}\left(\epsilon\right)=\delta$.

Bayes stability and sample accuracy (implying posterior accuracy) combine via
a triangle inequality to give distribution accuracy.

######  Theorem 3.5 (Main Generalization Theorem).

Given tail distribution functions $\varphi$ and $\psi$ and an analyst $A$, if
a mechanism $M$ is ${\psi}\left(\cdot\right)$-Bayes Stable and
${\varphi}\left(\cdot\right)$-Sample Accurate with respect to $A$, then it is
${\Phi}\left(\cdot\right)$-Distribution Accurate for
${\Phi}\left(\alpha\right)\coloneqq\underset{\epsilon\in\left[0,\alpha\right],c\in\left(0,\alpha-\epsilon\right)}{\inf}\left(\frac{1}{c}\int_{\alpha-\epsilon-c}^{\infty}{\varphi}\left(t\right)dt+{\psi}\left(\epsilon\right)\right)$.

###### Proof.

For any $\epsilon\in\left[0,\alpha\right],c\in\left(0,\epsilon\right)$,

$\displaystyle\underset{\genfrac{}{}{0.0pt}{}{S\sim
D}{V\sim{M}\left(S,A\right)}}{\text{Pr}}$
$\displaystyle\left[\underset{i\in\left[k\right]}{\max}\left\lVert
R_{i}-{Q_{i}}\left(D\right)\right\rVert>\alpha\right]$
$\displaystyle\leq\underset{}{\text{Pr}}\left[\underset{i\in\left[k\right]}{\max}\left\lVert
R_{i}-{Q_{i}}\left(D^{V_{i-1}}\right)\right\rVert+\underset{i\in\left[k\right]}{\max}\left\lVert{Q_{i}}\left(D^{V_{i-1}}\right)-{Q_{i}}\left(D\right)\right\rVert>\alpha\right]$
$\displaystyle\leq\underset{}{\text{Pr}}\left[\underset{i\in\left[k\right]}{\max}\left\lVert
R_{i}-{Q_{i}}\left(D^{V_{i-1}}\right)\right\rVert>\alpha-\epsilon\right]+\underset{}{\text{Pr}}\left[\underset{i\in\left[k\right]}{\max}\left\lVert{Q_{i}}\left(D^{V_{i-1}}\right)-{Q_{i}}\left(D\right)\right\rVert>\epsilon\right]$
$\displaystyle\overset{\left(1\right)}{\leq}\frac{1}{c}\int_{\alpha-\epsilon-c}^{\infty}{\varphi}\left(t\right)dt+{\psi}\left(\epsilon\right),$

where (1) results from Lemma 3.1 and the definition of Bayes Stability
(Definition 3.4). ∎

Since achieving posterior accuracy is relatively straightforward, guaranteeing
Bayes Stability is the main challenge in leveraging this theorem to achieve
distribution accuracy with respect to adaptively chosen queries. The following
lemma gives a useful and intuitive characterization of the quantity that the
Bayes Stability definition requires be bounded. Simply put, the Bayes factor
${K}\left(\cdot,\cdot\right)$ (defined in the lemma) represents the amount of
information leaked about the dataset during the interaction with an analyst,
as encoded by some view $v$. The degree to which a query $q$ overfits to the
dataset is expressed by the correlation between the query and that Bayes
factor. This simple lemma is at the heart of the progress that we make in this
paper, both in our intuitive understanding of adaptive data analysis, and in
the concrete results we show in subsequent sections.

######  Lemma 3.6 (Covariance Stability Lemma).

Given a view $v\in\mathcal{V}$ and a linear query $q$,

${q}\left(D^{v}\right)-{q}\left(D\right)=\underset{X\sim
D}{\text{Cov}}\left({q}\left(X\right),{K}\left(X,v\right)\right),$

where
${K}\left(x,v\right)\coloneqq\frac{{D}\left(x\,|\,v\right)}{{D}\left(x\right)}$
is the Bayes factor of $x$ given $v$.

###### Proof.

We observe

$\displaystyle{q}\left(D^{v}\right)-{q}\left(D\right)$
$\displaystyle=\sum_{x\in\mathcal{X}}{D}\left(x\,|\,v\right){q}\left(x\right)-{q}\left(D\right)$
$\displaystyle=\sum_{x\in\mathcal{X}}{D}\left(x\right){K}\left(x,v\right){q}\left(x\right)-{q}\left(D\right)$
$\displaystyle=\underset{X\sim
D}{\mathbb{E}}\left[{K}\left(X,v\right){q}\left(X\right)\right]-\overset{=1}{\overbrace{\underset{X\sim
D}{\mathbb{E}}\left[{K}\left(X,v\right)\right]}}\cdot\overset{={q}\left(D\right)}{\overbrace{\underset{X\sim
D}{\mathbb{E}}\left[{q}\left(X\right)\right]}}$ $\displaystyle=\underset{X\sim
D}{\text{Cov}}\left({q}\left(X\right),{K}\left(X,v\right)\right).$

From Lemma 3.6, we observe that
$\left\lVert{q}\left(D^{v}\right)-{q}\left(D\right)\right\rVert=0$ can be
achieved not only when ${K}\left(X,v\right)=0$, but also if $q$ is
uncorrelated with ${K}\left(X,v\right)$. Furthermore, if $q$ is a
$\Delta$-bounded linear query,
$\left\lVert{q}\left(D^{v}\right)-{q}\left(D\right)\right\rVert\leq\Delta\cdot{\mathbf{D}_{\text{TV}}}\left(D\|D^{v}\right)$,
where $\mathbf{D}_{\text{TV}}$ is the Total Variation Distance (Definition
B.1). For the interested reader, we also discuss the relationship to the Local
Statistical Stability notion of [SL19] in Appendix F.

##  4 Linear Bayesian Indistinguishability

In order to leverage the insight of Lemma 3.6, we need a stability notion that
bounds the induced distributions over query responses in a manner that depends
on the actual data points and the actual queries (not just the worst case).
For this, we need a distance measure between distributions whose parameter is
outcome-dependent (Definition 4.1). In order to be useful for analyzing
algorithms, the stability notion must also enjoy composition guarantees (which
we show in Theorem 4.6). It also must imply Bayes stability (Definition 3.4).
Here, we choose a particular form of the stability notion (Definition 4.2)
that is tailored to the case of Laplace and Gaussian noise-addition mechanisms
for linear queries, in that it explicitly contains terms corresponding to the
change in the output of the query as a result of swapping the input. Missing
proofs from this section can be found in Appendix D.

We begin with the distance measure between distributions.

######  Definition 4.1 ((Dynamic) Indistinguishable Distributions).

Given $\epsilon,\delta\geq 0$, two probability distributions $D_{0},D_{1}$
over some domain $\mathcal{R}$ will be called
$\left(\epsilon,\delta\right)$-Indistinguishable if for
$i\in\left\\{0,1\right\\}$ and any $\mathbf{r}\subseteq\mathcal{R}$ we have
${D_{i}}\left(\mathbf{r}\right)\leq
e^{\epsilon}{D_{1-i}}\left(\mathbf{r}\right)+\delta$. This is equivalent to
the requirement that the $\delta$-approximate max divergence (Definition B.3)
between $D_{i}$ and $D_{1-i}$ is bounded by $\epsilon$. Similarly, given a
function $f:\mathcal{R}\rightarrow\mathbb{R}_{+}$, distributions $D_{0},D_{1}$
will be called $\left(f,\delta\right)$-Dynamic Indistinguishable if

$\sum_{r\in\mathbf{r}}{D_{i}}\left(r\right)\leq\sum_{r\in\mathbf{r}}e^{{f}\left(r\right)}{D_{1-i}}\left(r\right)+\delta.$

Using this definition, we can propose the new stability measure.

######  Definition 4.2 (Linear Bayesian Indistinguishablity).

Given $\gamma_{1},\gamma_{2},\delta\geq 0$ and a linear query $q$, a mechanism
$M$ will be called _$\left(\gamma_{1},\gamma_{2},\delta\right)$ -Linear
Bayesian Indistinguishable_ with respect to $q$ (or LBI, for short), if for
all $x,y\in\mathcal{X}$ and $s^{\prime}\in\mathcal{X}^{n-1}$,
${D_{\mathcal{R}|\mathcal{X}^{n}}}\left(\cdot\,|\,\left(s^{\prime},x\right)\right)$
and
${D_{\mathcal{R}|\mathcal{X}^{n}}}\left(\cdot\,|\,\left(s^{\prime},y\right)\right)$
are
$\left(\epsilon_{\gamma_{1},\gamma_{2},q,x,y},\delta\right)$-Indistinguishable,
where

$\epsilon_{\gamma_{1},\gamma_{2},q,x,y}\coloneqq\gamma_{1}\left\lVert{q}\left(x\right)-{q}\left(y\right)\right\rVert+\gamma_{2}\left\lVert{q}\left(x\right)-{q}\left(y\right)\right\rVert^{2}.$

Given an analyst $A$ issuing linear queries, $M$ will be called
$\left(\gamma_{1},\gamma_{2},\delta\right)$-LBI with respect to $A$ if
${D_{\mathcal{V}|\mathcal{X}^{n}}}\left(\cdot\,|\,\left(s^{\prime},x\right)\right)$
and
${D_{\mathcal{V}|\mathcal{X}^{n}}}\left(\cdot\,|\,\left(s^{\prime},y\right)\right)$
are
$\left({\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,y\right),\delta\right)$-Dynamic
Indistinguishable, where

${\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,y\right)\coloneqq\gamma_{1}\left\lVert{\bar{q}_{v}}\left(x\right)-{\bar{q}_{v}}\left(y\right)\right\rVert+\gamma_{2}\left\lVert{\bar{q}_{v}}\left(x\right)-{\bar{q}_{v}}\left(y\right)\right\rVert^{2}.$

We write ${\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,y\right)$ to emphasize that
$\ell$ is function of the view for the purposes of dynamic
indistinguishability, but we will also (in the next theorem) emphasize its
role as a function of $x,y$.

This LBI stability notion captures the extent to which replacing one data
element by another would be “noticeable” in its impact on the induced
distribution over issued queries and the responses to those queries. The
function ${\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,y\right)$ is designed to
capture the bounds on this impact that are provided by the addition of
Laplace- or Gaussian-distributed noise. Notice that, given a linear query $q$,
the difference between the distributions induced by $x$ and $y$ over
$\mathcal{R}$ is only a function of ${q}\left(x\right)-{q}\left(y\right)$. As
we discuss in Section 6, other variants of this LBI notion might be useful for
leveraging Lemma 3.6 in other settings.

We prove that LBI mechanisms are Bayes Stable, and hence can be used as the
basis of adaptive data analysis generalization guarantees.

######  Theorem 4.3 (Stability of LBI Mechanism).

Given $\gamma_{1},\gamma_{2},\delta,\sigma\geq 0$, $k\in\mathbb{N}$ and an
analyst $A$ issuing $k$ linear queries with standard deviation bounded by
$\sigma$, if $M$ that receives an iid dataset is
$\left(\gamma_{1},\gamma_{2},\delta\right)$-LBI with respect to any query
issued by $A$, then it is
$\left({\Theta}\left(\tilde{\gamma}_{1},\tilde{\gamma}_{2}\right)+c,\frac{\sigma\left(k\delta+\delta^{\prime}\right)}{c}\right)$-Bayes
Stable for any $c,\delta^{\prime}>0$, where
$\tilde{\gamma}_{1}\coloneqq\gamma_{1}\sqrt{2{\ln}\left(\frac{1}{\delta^{\prime}}\right)}$,
$\tilde{\gamma}_{2}\coloneqq\gamma_{2}+\frac{\gamma_{1}^{2}}{2}$, and

${\Theta}\left(\tilde{\gamma}_{1},\tilde{\gamma}_{2}\right)\coloneqq\underset{v\in\mathcal{V}_{k},i\in\left[k\right]}{\max}\left(\underset{X,Y\sim
D}{\mathbb{E}}\left[\left\lVert{q_{i}}\left(X\right)-{q_{i}}\left(D\right)\right\rVert\left(e^{{\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)}-1\right)\right]\right).$

The $\Theta$ term here is a proxy for the covariance from Lemma 3.6 that is
more amenable to analysis; the quantity inside the $\max$ bounds the extent to
which a query leverages sample information encoded in the responses to
previous queries. Notice that a mechanism is
$\left(\epsilon,\delta\right)$-differentially private with respect to $q$
(Definition B.6), if and only if
$\epsilon_{\gamma_{1},\gamma_{2},q,x,y}\leq\epsilon$ for all $x,y$. In this
case,
${\Theta}\left(\tilde{\gamma}_{1},\tilde{\gamma}_{2}\right)\leq\Delta\left(e^{\epsilon}-1\right)$,
which essentially recovers the result of Lemma 7 in [JLN+20]. Combining this
theorem with Theorem 3.5 shows that LBI and sample accuracy together imply
distribution accuracy.

######  Corollary 4.4 (Accuracy of LBI Mechanism).

Given $\gamma_{1},\gamma_{2},\delta,\delta^{\prime},\sigma\geq 0$,
$k\in\mathbb{N}$, a tail distribution function $\varphi$, and an analyst $A$
issuing $k$ linear queries with standard deviation bounded by $\sigma$, if $M$
that receives an iid dataset is
$\left(\gamma_{1},\gamma_{2},\delta\right)$-LBI and
${\varphi}\left(\cdot\right)$-Sample Accurate with respect to any query issued
by $A$, then it is ${\Phi}\left(\cdot\right)$-Distribution Accurate for
$\tilde{\gamma}_{1}\coloneqq\gamma_{1}\sqrt{2{\ln}\left(\frac{1}{\delta^{\prime}}\right)}$,
$\tilde{\gamma}_{2}\coloneqq\gamma_{2}+\frac{\gamma_{1}^{2}}{2}$, and

${\Phi}\left(\alpha\right)\coloneqq\underset{\genfrac{}{}{0.0pt}{}{b\in\left(0,\alpha-{\Theta}\left(\tilde{\gamma}_{1},\tilde{\gamma}_{2}\right)\right)}{c\in\left(0,\alpha-{\Theta}\left(\tilde{\gamma}_{1},\tilde{\gamma}_{2}\right)-b\right)}}{\inf}\left(\frac{1}{c}\int_{\alpha-{\Theta}\left(\tilde{\gamma}_{1},\tilde{\gamma}_{2}\right)-b-c}^{\infty}{\varphi}\left(t\right)dt+\frac{\sigma\left(k\delta+\delta^{\prime}\right)}{b}\right).$

The proof of Theorem 4.3 consists of two main components. First, we prove in
Lemma 4.5 that the
${\Theta}\left(\tilde{\gamma}_{1},\tilde{\gamma}_{2}\right)$ term appearing in
the theorem statement bounds the covariance defined in Lemma 3.6, and then we
prove a composition theorem (Theorem 4.6) that parallels the composition
theorem for differential privacy [DRV10]. Combining the two completes the
proof.

######  Lemma 4.5.

[LBI implies Bayes Stability] Given $\gamma_{1},\gamma_{2},\delta\geq 0$, an
analyst $A$, and a query $q$, if a mechanism $M$ that receives an iid dataset
is $\left(\gamma_{1},\gamma_{2},\delta\right)$-LBI with respect to $A$, then

$\left\lVert\underset{X\sim
D}{\text{Cov}}\left({q}\left(X\right),{K}\left(X,v\right)\right)\right\rVert\leq\underset{X,Y\sim
D}{\mathbb{E}}\left[\left\lVert{q}\left(X\right)-{q}\left(D\right)\right\rVert\left(e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;X,Y\right)}-1\right)\right]+\frac{\sigma\delta}{{D}\left(v\right)},$

where $\sigma$ is the standard deviation of $q$.

###### Proof outline.

From the definition of LBI, for any $x,y\in\mathcal{X}$,
$s^{\prime}\in\mathcal{X}^{n-1}$, and $v\in\mathcal{V}$,

$e^{-{\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,y\right)}\left({D}\left(v\,|\,\left(s^{\prime},x\right)\right)-\delta\right)\leq{D}\left(v\,|\,\left(s^{\prime},y\right)\right)\leq
e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,y\right)}{D}\left(v\,|\,\left(s^{\prime},x\right)\right)+\delta$
$\Rightarrow\frac{1}{\underset{Y\sim
D}{\mathbb{E}}\left[e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,Y\right)}\right]}\left({D}\left(v\,|\,x\right)-\delta\right)\leq{D}\left(v\right)\leq\underset{Y\sim
D}{\mathbb{E}}\left[e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,Y\right)}\right]{D}\left(v\,|\,x\right)+\delta.$

Using this bound we get

$\displaystyle\left\lVert\underset{X\sim
D}{\text{Cov}}\left({q}\left(X\right),{K}\left(X,v\right)\right)\right\rVert$
$\displaystyle\leq\underset{X\sim
D}{\mathbb{E}}\left[\left\lVert{q}\left(X\right)-{q}\left(D\right)\right\rVert\cdot\frac{1}{{D}\left(v\right)}\left|{D}\left(v\,|\,X\right)-{D}\left(v\right)\right|\right]$
$\displaystyle\leq\underset{X,Y\sim
D}{\mathbb{E}}\left[\left\lVert{q}\left(X\right)-{q}\left(D\right)\right\rVert\frac{1}{{D}\left(v\right)}\left(\left(e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;X,Y\right)}-1\right){D}\left(v\right)+\delta\right)\right]$
$\displaystyle\leq\underset{X,Y\sim
D}{\mathbb{E}}\left[\left\lVert{q}\left(X\right)-{q}\left(D\right)\right\rVert\left(e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;X,Y\right)}-1\right)\right]+\frac{\sigma\delta}{{D}\left(v\right)}.$

######  Theorem 4.6 (Advanced Composition for LBI).

Given $\gamma_{1},\gamma_{2},\delta>0$, $k\in\mathbb{N}$, and an analyst $A$,
if a mechanism $M$ is $\left(\gamma_{1},\gamma_{2},\delta\right)$-LBI with
respect to every query $q$ issued by $A$, then it is
$\left(\tilde{\gamma}_{1},\tilde{\gamma}_{2},k\delta+\delta^{\prime}\right)$-LBI
with respect to $A$ for any $\delta^{\prime}>0$, where
$\tilde{\gamma}_{1}\coloneqq\gamma_{1}\sqrt{2{\ln}\left(\frac{1}{\delta^{\prime}}\right)}$,
and $\tilde{\gamma}_{2}\coloneqq\gamma_{2}+\frac{\gamma_{1}^{2}}{2}$.

###### Proof outline.

We begin by proving the case of $\delta=0$. From the definition, for any
$s^{\prime}\in\mathcal{X}^{n-1},x,y\in\mathcal{X}$ $i\in\left[k\right]$, the
two distributions
${D^{q_{i}}_{\mathcal{R}|\mathcal{X}^{n}}}\left(\cdot\,|\,\left(s^{\prime},x\right)\right)$,
${D^{q_{i}}_{\mathcal{R}|\mathcal{X}^{n}}}\left(\cdot\,|\,\left(s^{\prime},y\right)\right)$
are
$\left(\epsilon_{\gamma_{1},\gamma_{2},q_{i},x,y},0\right)$-Indistinguishable.
From Lemma D.3, this implies the existence of another distribution
$D^{\prime}$ over $\mathcal{R}$ such that for any $r\in\mathcal{R}$,

${\ln}\left(\frac{{D^{q_{i}}}\left(r\,|\,\left(s^{\prime},y\right)\right)}{{D^{\prime}_{i}}\left(r\right)}\right)\leq\gamma_{1}\left\lVert{q_{i}}\left(x\right)-{q_{i}}\left(y\right)\right\rVert~{}~{}~{}~{}\text{and}~{}~{}~{}~{}{\ln}\left(\frac{{D^{\prime}_{i}}\left(r\right)}{{D^{q_{i}}}\left(r\,|\,\left(s^{\prime},x\right)\right)}\right)\leq\gamma_{2}\left\lVert{q_{i}}\left(x\right)-{q_{i}}\left(y\right)\right\rVert^{2},$

which implies

$\underset{R\sim{M}\left(\left(s^{\prime},x\right),q_{i}\right)}{\mathbb{E}}\left[{\ln}\left(\frac{{D^{q_{i}}}\left(R\,|\,\left(s^{\prime},y\right)\right)}{{D^{\prime}_{i}}\left(R\right)}\right)\right]\overset{\left(1\right)}{=}{\mathbf{D}_{1}}\left({D^{q_{i}}}\left(R\,|\,\left(s^{\prime},y\right)\right)\lVert{D^{\prime}_{i}}\left(R\right)\right)\overset{\left(2\right)}{\leq}\frac{\gamma^{2}_{1}}{2}\left\lVert{q_{i}}\left(x\right)-{q_{i}}\left(y\right)\right\rVert^{2}$

where (1) results from the definition of the KL Divergence (B.2) and (2) from
the definition of $D^{\prime}_{i}$ and Lemma B.5.

Denoting

${L_{i}}\left(v_{i}\right)\coloneqq{\ln}\left(\frac{{D^{q_{i}}}\left(r_{i}\,|\,\left(s^{\prime},y\right)\right)}{{D^{\prime}_{i}}\left(r_{i}\right)}\right)-\underset{R\sim{M}\left(\left(s^{\prime},x\right),q_{i}\right)}{\mathbb{E}}\left[{\ln}\left(\frac{{D^{q_{i}}}\left(R\,|\,\left(s^{\prime},y\right)\right)}{{D^{\prime}_{i}}\left(R\right)}\right)\right]$

we get

$\displaystyle{\ln}\left(\frac{{D}\left(v_{k}\,|\,\left(s^{\prime},y\right)\right)}{{D}\left(v_{k}\,|\,\left(s^{\prime},x\right)\right)}\right)$
$\displaystyle=\sum_{i=1}^{k}{\ln}\left(\frac{{D^{q_{i}}}\left(r_{i}\,|\,\left(s^{\prime},y\right)\right)}{{D^{q_{i}}}\left(r_{i}\,|\,\left(s^{\prime},x\right)\right)}\right)$
$\displaystyle\overset{\left(1\right)}{\leq}\sum_{i=1}^{k}\left({L_{i}}\left(v_{i}\right)+\left(\frac{\gamma^{2}_{1}}{2}+\gamma_{2}\right)\left\lVert{q_{i}}\left(x\right)-{q_{i}}\left(y\right)\right\rVert^{2}\right)$
$\displaystyle=\sum_{i=1}^{k}{L_{i}}\left(v_{i}\right)+\left(\frac{\gamma^{2}_{1}}{2}+\gamma_{2}\right)\left\lVert{\bar{q}_{v}}\left(x\right)-{\bar{q}_{v}}\left(y\right)\right\rVert^{2}$

where (1) results from the bound on
$\underset{R\sim{M}\left(\left(s^{\prime},x\right),q_{i}\right)}{\mathbb{E}}\left[{\tilde{L}^{1}_{i}}\left(\left(v_{i-1},R\right)\right)\right]$
and the definition of $D^{\prime}_{i}$.

In order to complete the proof of this case, all that is required is to bound
$\sum_{i=1}^{k}{L_{i}}\left(v_{i}\right)$. This part of the proof uses the
terminology and notation of martingales as presented in Lemma D.4. We define a
probability space $\mathcal{V}_{k}$, a filtration based on the $i$-th prefix
and probability distribution
$V_{i}\sim{D}\left(v_{i}\,|\,\left(s^{\prime},x\right)\right)$ and the random
variables
$Z_{0}=0,{Z_{i}}\left(V_{i}\right)\coloneqq\sum_{j=1}^{i}{L_{i}}\left(V_{i}\right)$
and
${B_{i}}\left(V_{i-1}\right)\coloneqq\gamma_{1}\left\lVert{\bar{q}_{v}}\left(x\right)-{\bar{q}_{v}}\left(y\right)\right\rVert$.

Notice that from the definition, ${L_{i}}\left(V_{i}\right)$ is
$\mathcal{F}_{i}$-measurable and
$\underset{}{\mathbb{E}}\left[{L_{i}}\left(V_{i}\right)\right]=0$, so $Z_{i}$
is a martingale with respect to the defined probability triplet. Since
${B_{i}}\left(V_{i-1}\right)$ is $\mathcal{F}_{i-1}$-measurable and from the
definition of $D^{\prime}_{i}$,
$\left|{L_{i}}\left(V_{i}\right)\right|\leq{B_{i}}\left(V_{i-1}\right)$, the
conditions of Lemma D.4 are met, which implies

$\displaystyle\underset{V_{k}\sim{M}\left(\left(s^{\prime},x\right),A\right)}{\text{Pr}}$
$\displaystyle\left[{\ln}\left(\frac{{D}\left(V_{k}\,|\,\left(s^{\prime},y\right)\right)}{{D}\left(V_{k}\,|\,\left(s^{\prime},x\right)\right)}\right)>{\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v;x,y\right)\right]$
$\displaystyle\overset{\left(1\right)}{\leq}\underset{V_{k}\sim{M}\left(\left(s^{\prime},x\right),A\right)}{\text{Pr}}\left[\sum_{i=1}^{k}{L_{i}}\left(V_{i}\right)>\sqrt{2{\ln}\left(\frac{1}{\delta^{\prime}}\right)\sum_{i=1}^{k}{B_{i}^{2}}\left(V_{i-1}\right)}\right]$
$\displaystyle=\underset{V_{k}\sim{M}\left(\left(s^{\prime},x\right),A\right)}{\text{Pr}}\left[\exists\epsilon>0\,|\,\sum_{i=1}^{k}{L_{i}}\left(V_{i}\right)>\epsilon~{}~{}\text{and}~{}~{}\sqrt{\sum_{i=1}^{k}\left({2B_{i}}\left(V_{i-1}\right)\right)^{2}}\leq\frac{\sqrt{2}\epsilon}{\sqrt{{\ln}\left(\frac{1}{\delta^{\prime}}\right)}}\right]$
$\displaystyle\overset{\left(2\right)}{\leq}{\exp}\left(-2\left(\frac{{\ln}\left(\frac{1}{\delta^{\prime}}\right)}{2}\right)\right)$
$\displaystyle=\delta^{\prime}$

where (1) results from the previous equations and inequalities and (2) from
Lemma D.4 for $A_{i}=-B_{i}$, $\epsilon_{1}=\epsilon$ and
$\epsilon_{2}=\frac{\sqrt{2}\epsilon}{\sqrt{{\ln}\left(\frac{1}{\delta^{\prime}}\right)}}$.

For the case of $\delta>0$, we make use of Lemma D.2, which implies that for
all $i\in\left[k\right]$, there exists some intermediate distribution
$\tilde{D}_{i}$ such that
${\boldsymbol{D}_{\text{TV}}}\left({D}\left(\cdot\,|\,\left(s^{\prime},x\right)\right)\lVert\tilde{D}_{i}\right)\leq\delta$
and
${\boldsymbol{D}_{\infty}}\left(\tilde{D}_{i}\lVert{D}\left(\cdot\,|\,\left(s^{\prime},y\right)\right)\right)\leq\epsilon$.
Combining these distributions defines a distribution $\tilde{D_{\mathcal{V}}}$
over the views. From the triangle inequality,
${\boldsymbol{D}_{\text{TV}}}\left({D_{\mathcal{V}|\mathcal{X}^{n}}}\left(\cdot\,|\,\left(s^{\prime},x\right)\right)\lVert\tilde{D_{\mathcal{V}}}\right)\leq
k\delta$. On the other hand,

${\boldsymbol{D}_{\infty}^{\delta^{\prime}}}\left(\tilde{D_{\mathcal{V}}}\lvert{D_{\mathcal{V}|\mathcal{X}^{n}}}\left(\cdot\,|\,\left(s^{\prime},x\right)\right)\right)\leq\gamma_{1}\sqrt{2{\ln}\left(\frac{1}{\delta^{\prime}}\right)}\left\lVert{\bar{q}_{v}}\left(x\right)-{\bar{q}_{v}}\left(y\right)\right\rVert+\left(\frac{\gamma^{2}_{1}}{2}+\gamma_{2}\right)\left\lVert{\bar{q}_{v}}\left(x\right)-{\bar{q}_{v}}\left(y\right)\right\rVert^{2}.$

Combining the two and applying the triangle inequality again completes the
proof. ∎

Finally, we prove that the Laplace and Gaussian mechanisms are indeed LBI. In
the following section, we will leverage this to prove new generalization
guarantees for these mechanisms.

######  Lemma 4.7.

[Laplace Mechanism is LBI] Given $\eta>0$ and a linear query $q$, if $M$ is a
Laplace mechanism with noise parameter $\eta$ that receives an iid dataset,
then it is $\left(\frac{1}{n\eta},0,0\right)$-LBI with respect to $q$. Given
$k\in\mathbb{N}$ and an analyst $A$ issuing $k$ linear queries, $M$ is
$\left(\frac{1}{n\eta}\sqrt{2{\ln}\left(\frac{1}{\delta}\right)},\frac{1}{2n^{2}\eta^{2}},\delta\right)$-LBI
with respect to $A$ for any $\delta>0$.

######  Lemma 4.8 (Gaussian Mechanism is LBI).

Given $\eta>0$ and a linear query $q$, if $M$ is a Gaussian mechanism with
noise parameter $\eta$ that receives an iid dataset, then for any
$0<\delta\leq 1$ it is
$\left(\frac{1}{n\eta}\sqrt{2{\ln}\left(\frac{1}{\delta}\right)},\frac{1}{2n^{2}\eta^{2}},\delta\right)$-LBI
with respect to $A$.

Given $k\in\mathbb{N}$ and an analyst $A$ issuing $k$ linear queries, $M$ is
$\left(\frac{2}{n\eta}\sqrt{{\ln}\left(\frac{1}{\delta}\right){\ln}\left(\frac{1}{\delta^{\prime}}\right)},\frac{1}{n^{2}\eta^{2}}\left(\frac{1}{2}+{\ln}\left(\frac{1}{\delta}\right)\right),k\delta+\delta^{\prime}\right)$-LBI
with respect to $A$ for any $\delta^{\prime}>0$.

##  5 Variance based Generalization Guarantees

Corollary 4.4 implies that as long as a mechanism maintains sample accuracy,
the only thing required in order to ensure distribution accuracy is Bayes
Stability, which can be achieved using Linear Bayes Indistinguishability (and
in particular by bounding the
${\Theta}\left(\tilde{\gamma}_{1},\tilde{\gamma}_{2}\right)$ term that appears
in Theorem 4.3). In Section 5.1, we leverage this approach to show
generalization guarantees for arbitrary sample-accurate, LBI mechanisms
receiving queries with bounded standard deviation, and in Section 5.2 we
instantiate this approach specifically for the Laplace and Gaussian
Mechanisms. All proofs from this section appear in Appendix E.

###  5.1 General Generalization guarantees

We first show that for sample-accurate, LBI mechanisms receiving
$\Delta$-bounded linear queries with bounded standard deviation $\sigma$, the
resulting distribution accuracy depends on $\sigma$, not on $\Delta$.

######  Theorem 5.1 (Variance-based Generalization Guarantees for Bounded
Linear Queries).

Given $\gamma_{1},\delta,\Delta,\sigma\geq 0$,
$0\leq\gamma_{2}\leq\frac{\gamma^{2}_{1}}{2}$, $k\in\mathbb{N}$, a tail
distribution function $\varphi$, and an analyst $A$ issuing $k$
$\Delta$-bounded linear queries with standard deviation bounded by $\sigma$,
if $M$ that receives an iid dataset is ${\varphi}\left(\cdot\right)$-Sample
Accurate and $\left(\gamma_{1},\gamma_{2},\delta\right)$-LBI with respect to
any query issued by $A$, then for any
$e^{-\frac{1}{4k\gamma^{2}\Delta^{2}}}\leq\delta^{\prime}\leq\frac{1}{e}$, $M$
is ${\Phi}\left(\cdot\right)$-Distribution Accurate for $\epsilon\coloneqq
2\gamma_{1}\sigma^{2}\sqrt{3k\cdot{\ln}\left(\frac{1}{\delta^{\prime}}\right)}$
and

${\Phi}\left(\alpha\right)\coloneqq\underset{\genfrac{}{}{0.0pt}{}{b\in\left(0,\alpha-\epsilon\right)}{c\in\left(0,\alpha-\epsilon-b\right)}}{\inf}\left(\frac{1}{c}\int_{\alpha-\epsilon-
b-c}^{\infty}{\varphi}\left(t\right)dt+\frac{\sigma\left(k\delta+\delta^{\prime}\right)}{b}\right).$

###### Proof Outline.

From Corollary 4.4, it suffices to prove that
${\Theta}\left(\tilde{\gamma}_{1},\tilde{\gamma}_{2}\right)\leq\epsilon$ where
$\tilde{\gamma}_{1}\coloneqq\gamma_{1}\sqrt{2{\ln}\left(\frac{1}{\delta^{\prime}}\right)}$
and $\tilde{\gamma}_{2}\coloneqq\gamma_{2}+\frac{\gamma_{1}^{2}}{2}$. From the
lower bound on $\delta^{\prime}$,
$4k\gamma_{1}^{2}\Delta^{2}{\ln}\left(\frac{1}{\delta^{\prime}}\right)=2k\tilde{\gamma}_{1}^{2}\Delta^{2}\leq
1$.

From the definition of $\ell$ and the bounds on $\gamma_{2},\delta^{\prime}$
and the queries range, for any $i\in\left[k\right]$,

$\displaystyle{\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};x,y\right)$
$\displaystyle\leq\gamma_{1}\left(\sqrt{2{\ln}\left(\frac{1}{\delta^{\prime}}\right)}+\gamma_{1}\sqrt{k}\Delta\right)\left\lVert{\bar{q}_{v_{i-1}}}\left(x\right)-{\bar{q}_{v_{i-1}}}\left(y\right)\right\rVert$
$\displaystyle\leq
2\gamma_{1}\sqrt{{\ln}\left(\frac{1}{\delta^{\prime}}\right)}\left\lVert{\bar{q}_{v_{i-1}}}\left(x\right)-{\bar{q}_{v_{i-1}}}\left(y\right)\right\rVert$
$\displaystyle\leq 1.$

Using this bound we get

$\displaystyle\underset{X,Y\sim
D}{\mathbb{E}}\left[\left(e^{{\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)}-1\right)^{2}\right]$
$\displaystyle\overset{\left(1\right)}{\leq}\underset{X,Y\sim
D}{\mathbb{E}}\left[3{\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}^{2}}\left(v_{i-1};X,Y\right)\right]$
$\displaystyle\overset{\left(2\right)}{\leq}3\underset{X,Y\sim
D}{\mathbb{E}}\left[\left(2\gamma_{1}\sqrt{{\ln}\left(\frac{1}{\delta^{\prime}}\right)}\left\lVert{\bar{q}_{v_{i-1}}}\left(x\right)-{\bar{q}_{v_{i-1}}}\left(y\right)\right\rVert\right)^{2}\right]$
$\displaystyle=12\gamma^{2}_{1}{\ln}\left(\frac{1}{\delta^{\prime}}\right)\underset{X,Y\sim
D}{\mathbb{E}}\left[\left\lVert{\bar{q}_{v_{i-1}}}\left(x\right)-{\bar{q}_{v_{i-1}}}\left(y\right)\right\rVert^{2}\right]$
$\displaystyle\overset{\left(3\right)}{\leq}12k\gamma^{2}_{1}\sigma^{2}{\ln}\left(\frac{1}{\delta^{\prime}}\right),$

where (1) results from the inequality $\left(e^{x}-1\right)^{2}\leq 3x^{2}$
for any $x\leq 1$, (2) from the previous inequality, and (3) from the bound on
the standard deviation.

Furthermore,

$\displaystyle{\Theta}\left(\tilde{\gamma}_{1},\tilde{\gamma}_{2}\right)$
$\displaystyle=\underset{v\in\mathcal{V}_{k},i\in\left[k\right]}{\max}\left(\underset{X,Y\sim
D}{\mathbb{E}}\left[\left\lVert{q_{i}}\left(X\right)-{q_{i}}\left(D\right)\right\rVert\left(e^{{\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)}-1\right)\right]\right)$
$\displaystyle\overset{\left(1\right)}{\leq}\underset{v\in\mathcal{V}_{k},i\in\left[k\right]}{\max}\left(\sqrt{\underset{X\sim
D}{\mathbb{E}}\left[\left\lVert{q_{i}}\left(X\right)-{q_{i}}\left(D\right)\right\rVert^{2}\right]\cdot\underset{X,Y\sim
D}{\mathbb{E}}\left[\left(e^{{\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)}-1\right)^{2}\right]}\right)$
$\displaystyle\overset{\left(1\right)}{\leq}\sigma\sqrt{12k\gamma^{2}_{1}\sigma^{2}{\ln}\left(\frac{1}{\delta^{\prime}}\right)}$
$\displaystyle=2\gamma_{1}\sigma^{2}\sqrt{3k\cdot{\ln}\left(\frac{1}{\delta^{\prime}}\right)},$

where (1) is via the Cauchy-Schwarz inequality and (2) comes from the bound on
the standard deviation of the queries and the previous inequality. ∎

Transitioning from a range-based accuracy guarantee to one based on standard
deviation raises a natural question: can we also provide accuracy guarantees
for unbounded linear queries? Clearly, such guarantees are impossible without
a bound on the tail distribution, even for a single query, so we focus on the
case of sub-Gaussian queries. Notice that this represents an improvement over
what can naturally be achieved via differential privacy, even in comparison to
computationally-inefficient differentially-private mechanisms.

######  Definition 5.2.

Given $\sigma>0$, a random variable $X\in\mathbb{R}$ will be called sub-
Gaussian with parameter $\sigma$ if, for all $\lambda>0$,
$\underset{}{\mathbb{E}}\left[e^{\lambda X}\right]\leq
e^{\lambda^{2}\sigma^{2}}$. If $\underset{}{\mathbb{E}}\left[X\right]=0$, then
$X$ will be called centered.

A random vector $X\in\mathbb{R}^{d}$ will be called sub-Gaussian with
parameter $\sigma$, if for any unit vector $v\in\mathbb{R}^{d}$, $v^{T}X$ is a
sub-Gaussian random variable with parameter $\sigma$.

######  Theorem 5.3 (Variance-based Generalization Guarantees for Sub-Gaussian
Linear Queries).

Given $\gamma_{1},\delta,\sigma\geq 0$,
$0\leq\gamma_{2}\leq\frac{\gamma_{1}^{2}}{2}$, $k\in\mathbb{N}$, a tail
distribution function $\varphi$, and an analyst $A$ issuing $k$ linear queries
into $\mathbb{R}^{d}$ such that all queries issued by $A$ are sub-Gaussian
with parameter $\sigma$, if $M$ that receives an iid dataset is
${\varphi}\left(\cdot\right)$-Sample Accurate and
$\left(\gamma_{1},\gamma_{2},\delta\right)$-LBI with respect to any query
issued by $A$, then for any
$e^{-\frac{1}{156kd\gamma^{2}\sigma^{2}}}\leq\delta^{\prime}\leq\frac{1}{e^{4}}$,
$M$ is ${\Phi}\left(\cdot\right)$-Distribution Accurate for $\epsilon\coloneqq
29\gamma_{1}\sigma^{2}\sqrt{kd\cdot{\ln}\left(\frac{1}{\delta^{\prime}}\right)}$
and

${\Phi}\left(\alpha\right)\coloneqq\underset{\genfrac{}{}{0.0pt}{}{b\in\left(0,\alpha-\epsilon\right)}{c\in\left(0,\alpha-\epsilon-b\right)}}{\inf}\left(\frac{1}{c}\int_{\alpha-\epsilon-
b-c}^{\infty}{\varphi}\left(t\right)dt+\frac{\sigma\left(k\delta+\delta^{\prime}\right)}{b}\right),$

where $d$ is the dimension of the vector space $\mathcal{R}$.

###### Proof Outline.

Denote
$\tilde{\gamma}_{1}\coloneqq\gamma_{1}\sqrt{2{\ln}\left(\frac{1}{\delta^{\prime}}\right)}$,
$\tilde{\gamma}_{2}\coloneqq\gamma_{2}+\frac{\gamma^{2}_{1}}{2}$, and
$\lambda\coloneqq 4\tilde{\gamma}_{1}\sqrt{kd}\sigma$.

Using this notation we get

$\displaystyle\underset{X,Y\sim D}{\mathbb{E}}$
$\displaystyle\left[\left\lVert{q_{i}}\left(X\right)-{q_{i}}\left(D\right)\right\rVert\left({\exp}\left({\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)\right)-1\right)\right]$
$\displaystyle\leq\sigma\left(e^{\lambda}-1\right)\sqrt{\underset{X,Y\sim
D}{\mathbb{E}}\left[{\exp}\left(2\left({\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)-\lambda\right)\right)\right]}$
$\displaystyle~{}~{}~{}~{}+\sigma\sqrt{\underset{X,Y\sim
D}{\mathbb{E}}\left[{\exp}\left(2\left({\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)-\lambda\right)\right)\right]-1}.$

For any $i\in\left[k\right]$, denote
$Z_{i}=\left\lVert{\bar{q}_{v_{i}}}\left(X\right)-{\bar{q}_{v_{i}}}\left(Y\right)\right\rVert$,
using Lemma E.3 we get

$\displaystyle\underset{X\sim
D}{\mathbb{E}}\left[{\exp}\left(2\left({\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)-\lambda\right)\right)\right]$
$\displaystyle=\underset{X\sim
D}{\mathbb{E}}\left[{\exp}\left(2\tilde{\gamma}_{1}Z_{i}+2\tilde{\gamma}_{2}Z_{i}^{2}-2\lambda\right)\right]$
$\displaystyle\leq
1+156\gamma_{1}^{2}kd\sigma^{2}{\ln}\left(\frac{1}{\delta^{\prime}}\right).$

Plugging this back into the previous term we get

$\displaystyle\underset{X,Y\sim D}{\mathbb{E}}$
$\displaystyle\left[\left\lVert{q_{i}}\left(X\right)-{q_{i}}\left(D\right)\right\rVert\left({\exp}\left({\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)\right)-1\right)\right]$
$\displaystyle\overset{\left(1\right)}{\leq}\sigma\left(e^{4\tilde{\gamma}_{1}\sqrt{kd}\sigma}-1\right)\sqrt{1+\overset{\leq
1}{\overbrace{156{\ln}\left(\frac{1}{\delta^{\prime}}\right)kd\gamma_{1}^{2}\sigma^{2}}}}+\sigma\sqrt{156{\ln}\left(\frac{1}{\delta^{\prime}}\right)kd\gamma_{1}^{2}\sigma^{2}}$
$\displaystyle\overset{\left(2\right)}{\leq}16\sigma^{2}\gamma_{1}\sqrt{{\ln}\left(\frac{1}{\delta^{\prime}}\right)kd}+\sigma\sqrt{156{\ln}\left(\frac{1}{\delta^{\prime}}\right)kd\gamma_{1}^{2}\sigma^{2}}$
$\displaystyle\leq
29\gamma_{1}\sigma^{2}\sqrt{kd\cdot{\ln}\left(\frac{1}{\delta^{\prime}}\right)},$

where (1) results from the previous inequalities and the definition of
$\lambda$ and (2) from the lower bound on $\delta^{\prime}$ and the inequality
$e^{x}\leq 1+2x$ for any $0\leq x\leq 1$. ∎

###  5.2 Generalization Guarantees for Laplace and Gaussian Mechanism

We now leverage the results of the previous section to provide quantitative
generalization guarantees for two simple, well-studied mechanisms: Laplace-
and Gaussian-noise addition. Unlike some previous works, our bounds are not
asymptotic. We provide concrete constants, which allows us to see that our
analysis beats the naive sample-splitting approach for a reasonable sample
size and number of queries.

######  Theorem 5.4 (Generalization guarantee for Laplace Mechanism).

Given $\eta,\Delta,\sigma\geq 0$, $k\in\mathbb{N}$, an analyst $A$ issuing $k$
linear queries and a Laplace mechanism $M$ with noise parameter $\eta$ that
receives an iid dataset,

  * •

if all queries issued by $A$ are $\Delta$-bounded and have standard deviation
bounded by $\sigma$, then for any
$e^{-\frac{n^{2}\eta^{2}}{4k\Delta^{2}}}\leq\delta^{\prime}\leq\frac{1}{e}$,
$M$ is ${\Phi}\left(\cdot\right)$-Distribution Accurate for
$\epsilon\coloneqq\frac{2\sigma^{2}}{n\eta}\sqrt{3k\cdot{\ln}\left(\frac{1}{\delta^{\prime}}\right)}$,
and

  * •

if the queries issued by $A$ define a sub-Gaussian random vector with
parameter $\sigma$, then for any
$e^{-\frac{n^{2}\eta^{2}}{156kd\sigma^{2}}}\leq\delta^{\prime}\leq\frac{1}{e^{4}}$,
$M$ is ${\Phi}\left(\cdot\right)$-Distribution Accurate for
$\epsilon\coloneqq\frac{29\sigma^{2}}{n\eta}\sqrt{kd\cdot{\ln}\left(\frac{1}{\delta^{\prime}}\right)}$,

where
${\Phi}\left(\alpha\right)\coloneqq\underset{c\in\left(0,\alpha-\epsilon\right)}{\inf}\left(ke^{\frac{\alpha-\epsilon-\eta-c}{\eta}}+\frac{\sigma\delta^{\prime}}{c}\right)$.

######  Corollary 5.5.

Given $\alpha,\Delta,\sigma>0$, $0<\beta\leq\frac{1}{8}$, $k\in\mathbb{N}$, an
analyst $A$ issuing $k$ linear queries, and a Laplace mechanism $M$ with noise
parameter
$\eta=\frac{\alpha}{2{\ln}\left(\frac{k\sigma}{\min\left\\{\sigma,\alpha\right\\}\beta^{2}}\right)}$
which receives an iid dataset,

  * •

if all queries issued by $A$ are $\Delta$-bounded and have standard deviation
bounded by $\sigma$, then if $n\geq
2{\ln^{\frac{3}{2}}}\left(\frac{k\sigma}{\min\left\\{\sigma,\alpha\right\\}\beta^{2}}\right)\sqrt{k}\cdot\max\left\\{\frac{\Delta}{\alpha},8\sqrt{3}\left(\frac{\sigma}{\alpha}\right)^{2}\right\\}$
then $M$ is $\left(\alpha,\beta\right)$-Distribution Accurate, and

  * •

if the queries issued by $A$ define a sub-Gaussian random vector with
parameter $\sigma$, then if $n\geq
232{\ln^{\frac{3}{2}}}\left(\frac{k\sigma}{\min\left\\{\sigma,\alpha\right\\}\beta^{2}}\right)\sqrt{k}\left(\frac{\sigma}{\alpha}\right)^{2}$
then $M$ is $\left(\alpha,\beta\right)$-Distribution Accurate.

######  Theorem 5.6 (Generalization guarantee for Gaussian Mechanism).

Given $\eta,\Delta,\sigma\geq 0$, $k\in\mathbb{N}$, an analyst $A$ issuing $k$
linear queries and a Gaussian mechanism $M$ with noise parameter $\eta$ that
receives an iid dataset,

  * •

if all queries issued by $A$ are $\Delta$-bounded and have standard deviation
bounded by $\sigma$, then for any $\delta>0$,
$e^{-\frac{n^{2}\eta^{2}}{8k\Delta^{2}{\ln}\left(\frac{1}{\delta}\right)}}\leq\delta^{\prime}\leq\frac{1}{e}$,
$M$ is ${\Phi}\left(\cdot\right)$-Distribution Accurate for
$\epsilon\coloneqq\frac{2\sigma^{2}}{n\eta}\sqrt{6k\cdot{\ln}\left(\frac{1}{\delta}\right){\ln}\left(\frac{1}{\delta^{\prime}}\right)}$,
and

  * •

if the queries issued by $A$ define a sub-Gaussian random vector with
parameter $\sigma$, then for any $\delta>0$,
$e^{-\frac{n^{2}\eta^{2}}{312kd\sigma^{2}}}\leq\delta^{\prime}\leq\frac{1}{e^{4}}$,
$M$ is ${\Phi}\left(\cdot\right)$-Distribution Accurate for
$\epsilon\coloneqq\frac{29\sigma^{2}}{n\eta}\sqrt{2kd\cdot{\ln}\left(\frac{1}{\delta^{\prime}}\right)}$,

where

${\Phi}\left(\alpha\right)\coloneqq\underset{c\in\left(0,\alpha-\epsilon\right)}{\inf}\left(\frac{k\left(\alpha-\epsilon-c\right)}{\sqrt{2\pi}\eta}{\exp}\left(-\frac{\left(\alpha-\epsilon-c\right)^{2}-2\eta^{2}}{2\eta^{2}}\right)+\frac{\sigma\left(k\delta+\delta^{\prime}\right)}{c}\right).$

.

######  Corollary 5.7.

Given $\alpha,\Delta,\sigma>0$, $0<\beta\leq\frac{1}{8}$, $k\in\mathbb{N}$, an
analyst $A$ issuing $k$ linear queries, and a Gaussian mechanism $M$ with
noise parameter
$\eta=\frac{\alpha}{3\sqrt{2{\ln}\left(\frac{\left(k+1\right)\sigma}{\min\left\\{\sigma,\alpha\right\\}\beta^{2}}\right)}}$
which receives an iid dataset,

  * •

if all queries issued by $A$ are $\Delta$-bounded and have standard deviation
bounded by $\sigma$, then if $n\geq
2\sqrt{2}{\ln^{\frac{3}{2}}}\left(\frac{\left(k+1\right)\sigma}{\min\left\\{\sigma,\alpha\right\\}\beta^{2}}\right)\sqrt{k}\cdot\max\left\\{\frac{\Delta}{\alpha},12\sqrt{6}\left(\frac{\sigma}{\alpha}\right)^{2}\right\\}$,
then $M$ is $\left(\alpha,\beta\right)$-Distribution Accurate, and

  * •

if the queries issued by $A$ define a sub-Gaussian random vector with
parameter $\sigma$, then if $n\geq
696{\ln^{\frac{3}{2}}}\left(\frac{k\sigma}{\min\left\\{\sigma,\alpha\right\\}\beta^{2}}\right)\sqrt{k}\left(\frac{\sigma}{\alpha}\right)^{2}$,
then $M$ is $\left(\alpha,\beta\right)$-Distribution Accurate.

These theorems provides significant improvement over similar results that were
achieved using differential privacy (see, e.g., Theorem 13 in [JLN+20], which
is defined for $\Delta=1$) even for the bounded case, by replacing the
$\Delta^{2}$ term with $\sigma^{2}$. This improvement resembles that provided
by Bernstein’s inequality over Hoeffding’s inequality, and similarly can be
extended to higher order moments.

##  6 Discussion

The contribution of this paper is two-fold. In Section 3, we provide a tight
measure of the level of overfitting of some query with respect to previous
responses. In Sections 4 and 5, we demonstrate a possible toolkit to utilize
this measure, and use it to prove new generalization properties of fundamental
noise-addition mechanisms.

There are many possible variations on the approach we take, which each could
lead to interesting additional insights. For example, to capture an analyst
that is non-worst-case in the sense that she “forgets” some of the information
that she has learned about the dataset, both the posterior accuracy and the
Bayes stability could be redefined with respect to the internal state of the
analyst instead of with respect to the full view. This could allow for
improved bounds in the style of [ZH19].

One could also consider variations on the LBI definition. One might use loss
with non-linear dependence on $x,y$ and extend beyond linear queries (in doing
so, one might lose the variance-dependent generalization guarantees). One
could also consider a loss that is not worst-case over $s^{\prime}$ (in which
case the composition guarantees might degrade, as in [SL19]). Another possible
improvement might be achieved by using Rényi Differential Privacy (as in
[FZ20]), to avoid the small degradation that the LBI approach suffers when
analyzing the Gaussian mechanism compared to using a differential privacy-
based analysis (this raises the logarithmic term to the power of 1.5 instead
of 1; see [BS16] for comparison).

##  Appendix A Formal Definitions

######  Definition A.1 (Distributions over $\mathcal{X}^{n}$ and
$\mathcal{R}$).

A distribution $D_{\mathcal{X}^{n}}$, a query $q$, and a mechanism
$M:\mathcal{X}^{n}\times\mathcal{Q}\rightarrow\mathcal{R}$, together induce a
set of distributions over $\mathcal{X}^{n}$, $\mathcal{R}$, and
$\mathcal{X}^{n}\times\mathcal{R}$.

The _conditional distribution_ $D_{\mathcal{R}|\mathcal{X}^{n}}^{q}$ over
$\mathcal{R}$ represents the probability to get $r$ as the output of
${M}\left(s,q\right)$. That is, $\forall s\in\mathcal{X}^{n},r\in\mathcal{R},$

${D_{\mathcal{R}|\mathcal{X}^{n}}^{q}}\left(r\,|\,s\right)\coloneqq\underset{R\sim{M}\left(s,q\right)}{\text{Pr}}\left[R=r\,|\,s\right],$

where the probability is taken over the internal randomness of $M$.

The _joint distribution_ $D_{\left(\mathcal{X}^{n},\mathcal{R}\right)}^{q}$
over $\mathcal{X}^{n}\times\mathcal{R}$ represents the probability to sample a
particular $s$ and get $r$ as the output of ${M}\left(s,q\right)$. That is,
$\forall s\in\mathcal{X}^{n},r\in\mathcal{R}$,

${D_{\left(\mathcal{X}^{n},\mathcal{R}\right)}^{q}}\left(s,r\right)\coloneqq{D_{\mathcal{X}^{n}}}\left(s\right)\cdot{D_{\mathcal{R}|\mathcal{X}^{n}}^{q}}\left(r\,|\,s\right).$

The _marginal distribution_ $D_{\mathcal{R}}^{q}$ over $\mathcal{R}$
represents the prior probability to get output $r$ without any knowledge of
$s$. That is, $\forall r\in\mathcal{R},$

${D_{\mathcal{R}}^{q}}\left(r\right)\coloneqq\sum_{s\in\mathcal{X}^{n}}{D_{\left(\mathcal{X}^{n},\mathcal{R}\right)}^{q}}\left(s,r\right).$

The _product distribution_ $D_{\mathcal{X}^{n}\otimes\mathcal{R}}^{q}$ over
$\mathcal{X}^{n}\times\mathcal{R}$ represents the probability to sample $s$
and get $r$ as the output of ${M}\left(\cdot,q\right)$ independently. That is,
$\forall s\in\mathcal{X},r\in\mathcal{R},$

${D_{\mathcal{X}^{n}\otimes\mathcal{R}}^{q}}\left(s,r\right)\coloneqq{D_{\mathcal{X}^{n}}}\left(s\right)\cdot{D_{\mathcal{R}}^{q}}\left(r\right).$

The _conditional distribution_ $D_{\mathcal{X}^{n}|\mathcal{R}}^{q}$ over
$\mathcal{X}^{n}$ represents the posterior probability that the dataset was
$s$ given that ${M}\left(\cdot,q\right)$ returns $r$. That is, $\forall
s\in\mathcal{X}^{n},r\in\mathcal{R},$

${D_{\mathcal{X}^{n}|\mathcal{R}}^{q}}\left(s\,|\,r\right)\coloneqq\frac{{D_{\left(\mathcal{X}^{n},\mathcal{R}\right)}^{q}}\left(s,r\right)}{{D_{\mathcal{R}}^{q}}\left(r\right)}.$

######  Definition A.2 (Distributions over $\mathcal{X}$ and $\mathcal{R}$).

The _marginal distribution_ $D_{\mathcal{X}}$ over $\mathcal{X}$ represents
the probability to get $x$ by sampling a dataset uniformly at random without
any knowledge of $s$. That is, $\forall x\in\mathcal{X},$

${D_{\mathcal{X}}}\left(x\right)\coloneqq\sum_{s\in\mathcal{X}^{n}}{D_{\mathcal{X}^{n}}}\left(s\right)\cdot{D_{\mathcal{X}|\mathcal{X}^{n}}}\left(x\,|\,s\right),$

where ${D_{\mathcal{X}|\mathcal{X}^{n}}}\left(x\,|\,s\right)$ denotes the
probability to get $x$ by sampling $s$ uniformly at random.

The _joint distribution_ $D_{\left(\mathcal{X},\mathcal{R}\right)}^{q}$ over
$\mathcal{X}\times\mathcal{R}$ represents the probability to get $x$ by
sampling a dataset uniformly at random and also get $r$ as the output of
${M}\left(\cdot,q\right)$ from the same dataset. That is, $\forall
x\in\mathcal{X},r\in\mathcal{R},$

${D_{\left(\mathcal{X},\mathcal{R}\right)}^{q}}\left(x,r\right)\coloneqq\sum_{s\in\mathcal{X}^{n}}{D_{\mathcal{X}^{n}}}\left(s\right)\cdot{D_{\mathcal{X}|\mathcal{X}^{n}}}\left(x\,|\,s\right)\cdot{D_{\mathcal{R}|\mathcal{X}^{n}}^{q}}\left(r\,|\,s\right).$

where ${D_{\mathcal{X}|\mathcal{X}^{n}}}\left(x\,|\,s\right)$ denotes the
probability to get $x$ by sampling $s$ uniformly at random.

The _product distribution_ $D_{\mathcal{X}\otimes\mathcal{R}}^{q}$ over
$\mathcal{X}\times\mathcal{R}$ represents the probability to get $x$ by
sampling a dataset uniformly at random and get $r$ as the output of
${M}\left(\cdot,q\right)$ independently. That is, $\forall
x\in\mathcal{X},r\in\mathcal{R},$

${D_{\mathcal{X}\otimes\mathcal{R}}^{q}}\left(x,r\right)\coloneqq{D_{\mathcal{X}}}\left(x\right)\cdot{D_{\mathcal{R}}^{q}}\left(r\right).$

The _conditional distribution_ $D_{\mathcal{R}|\mathcal{X}}^{q}$ over
$\mathcal{R}$ represents the probability to get $r$ as the output of
${M}\left(\cdot,q\right)$ from a dataset, given the fact that we got $x$ by
sampling the same dataset uniformly at random. That is, $\forall
x\in\mathcal{X},r\in\mathcal{R},$

${D_{\mathcal{R}|\mathcal{X}}^{q}}\left(r\,|\,x\right)\coloneqq\sum_{s\in\mathcal{X}^{n}}{D_{\mathcal{X}^{n}|\mathcal{X}}}\left(s\,|\,x\right)\cdot{D_{\mathcal{R}|\mathcal{X}^{n}}^{q}}\left(r\,|\,s\right).$

The _conditional distribution_ $D_{\mathcal{X}|\mathcal{R}}^{q}$ over
$\mathcal{X}$ represents the probability to get $x$ by sampling a dataset
uniformly at random, given the fact that we got $r$ as the output of
${M}\left(\cdot,q\right)$ from that dataset. That is, $\forall
x\in\mathcal{X},r\in\mathcal{R},$

${D^{r}}\left(x\right)\coloneqq{D_{\mathcal{X}|\mathcal{R}}^{q}}\left(x\,|\,r\right)\coloneqq\sum_{s\in\mathcal{X}^{n}}{D_{\mathcal{X}^{n}|\mathcal{R}}^{q}}\left(s\,|\,r\right)\cdot{D_{\mathcal{X}|\mathcal{X}^{n}}}\left(x\,|\,s\right).$

Although all of these definitions depend on $D_{\mathcal{X}^{n}}$ and $M$, we
typically omit these from the notation for simplicity, and usually omit the
superscripts and subscripts entirely. We include them only when necessary for
clarity. We also use $D$ to denote the probability of a set: for
$\mathbf{r}\subseteq\mathcal{R}$, we define
${D_{\mathcal{R}}^{q}}\left(\mathbf{r}\right)\coloneqq\underset{r\in\mathbf{r}}{\sum}{D_{\mathcal{R}}^{q}}\left(r\right)$.

Though the conditional distributions $D_{\mathcal{R}|\mathcal{X}}^{q}$ and
$D_{\mathcal{X}|\mathcal{R}}^{q}$ were not defined as the ratio between the
joint and marginal distribution, the analogue of Bayes’ rule still holds for
these distributions. A formal proof of this claim can be found in Appendix A
in [SL19].

######  Definition A.3 (Adaptive Mechanism).

Illustrated below, the _adaptive mechanism_
$\text{Adp}_{M}:\mathcal{X}^{n}\times\mathcal{A}\rightarrow\mathcal{V}_{k}$ is
a particular type of mechanism, which inputs an analyst as its query and which
returns a view as its response and is parametrized by a mechanism $M$ and
number of iterations $k$.555This definition can be generalized to a sequence
of mechanisms. Given a dataset $s$ and an analyst $A$ as input, the adaptive
mechanism iterates $k$ times through the process where $A$ sends a query to
$M$ and receives its response to that query on the dataset. The adaptive
mechanism returns the resulting sequence of $k$ responses $v_{k}$. Naturally,
this requires $A$ to match $M$ such that $M$’s range can be $A$’s input, and
vice versa.

If $A$ is randomized, we add one more step at the beginning where
$\text{Adp}_{M}$ randomly generates some bits $c$—$A$’s “coin tosses.” In this
case, $v_{k}\coloneqq\left(c,r_{1},\ldots,r_{ik}\right)$ and $A$ receives the
coin tosses as an input as well. This addition turns $q_{k+1}$ into a
deterministic function of $v_{i}$ for any $i\in\mathbb{N}$, a fact that we
leverage. In this situation, the randomness of $\text{Adp}_{M}$ results both
from the randomness of the coin tosses and from that of the sub-mechanisms. We
will denote ${M}\left(s,A\right)\coloneqq{\text{Adp}_{M}}\left(s,A\right)$ for
simplicity.

Adaptive Mechanism $\text{Adp}_{M}$ Input:
$s\in\mathcal{X}^{n},\,A\in\mathcal{A}$ Output: $v_{k}\in\mathcal{V}_{k}$
$v_{0}\leftarrow\emptyset$ or $c$ for $i\in\left[k\right]$ :
$q_{i}\leftarrow{A}\left(v_{i-1}\right)$
$r_{i}\leftarrow{M}\left(s,q_{i}\right)$
$v_{i}\leftarrow\left(v_{i-1},r_{i}\right)$ return $v_{k}$

##  Appendix B Distance measures between distributions

######  Definition B.1 (Total Variation Distance).

The _total variation distance_ between two probability distributions
$D_{1},D_{2}$ over some domain $\mathcal{R}$ is defined as

${\mathbf{D}_{\text{TV}}}\left(D_{1},D_{2}\right)\coloneqq\underset{\mathbf{r}\in\mathcal{R}}{\max}\left({D_{1}}\left(\mathbf{r}\right)-{D_{2}}\left(\mathbf{r}\right)\right)=\underset{\mathbf{r}\in\mathcal{R}}{\max}\left({D_{2}}\left(\mathbf{r}\right)-{D_{1}}\left(\mathbf{r}\right)\right)=\frac{1}{2}\sum_{r\in\mathcal{R}}\left|{D_{1}}\left(r\right)-{D_{2}}\left(r\right)\right|.$

######  Definition B.2 (KL Divergence).

The _Kullback–Leibler divergence_ (or _KL divergence_) between two probability
distributions $D_{0},D_{1}$ over some domain $\mathcal{R}$ is defined as

${\mathbf{D}_{1}}\left(D_{0}\|D_{1}\right)\coloneqq\underset{R\sim
D_{0}}{\mathbb{E}}\left[{\ln}\left(\frac{{D_{0}}\left(R\right)}{{D_{1}}\left(R\right)}\right)\right].$

######  Definition B.3 (Max Divergence).

Given $\delta\geq 0$, the _$\delta$ -approximate max divergence_ between two
probability distributions $D_{0},D_{1}$ over some domain $\mathcal{R}$ is
defined as

${\mathbf{D}_{\infty}^{\delta}}\left(D_{0}\|D_{1}\right)\coloneqq\max_{\mathbf{r}\subseteq\text{Supp}\left(D_{1}\right)\wedge{D_{0}}\left(\mathbf{r}\right)\geq\delta}{\ln}\left(\frac{{D_{0}}\left(\mathbf{r}\right)-\delta}{{D_{1}}\left(\mathbf{r}\right)}\right).$

The case of $\delta=0$ is simply called Max Divergence.

These two definitions are generalized by the following one.

######  Definition B.4 (Rényi Divergence).

Given $\alpha\in\left[1,\infty\right]$, the _Rényi divergence_ between two
probability distributions $D_{0},D_{1}$ over some domain $\mathcal{R}$ is
defined as

${\mathbf{D}_{\alpha}}\left(D_{0}\|D_{1}\right)\coloneqq\frac{1}{\alpha-1}{\ln}\left(\underset{R\sim
D_{1}}{\mathbb{E}}\left[\left(\frac{{D_{0}}\left(R\right)}{{D_{1}}\left(R\right)}\right)^{\alpha}\right]\right).$

The cases of $\alpha=1,\infty$ are defined using the limit and converge to the
KL / Max divergence respectively.

######  Lemma B.5 (Max Divergence Bound on KL Divergence - Proposition 19 in
[BS16]).

Given $\epsilon>0$, for any two probability distributions $D_{0},D_{1}$ over
the same domain $\mathcal{R}$, if
${\mathbf{D}_{\infty}}\left(D_{0}\|D_{1}\right)\leq\epsilon$ then
${\mathbf{D}_{1}}\left(D_{0}\|D_{1}\right)\leq\frac{\epsilon^{2}}{2}$.

######  Definition B.6 (Differential Privacy [DMNS06]).

Given $\epsilon,\delta\geq 0$ and a query $q$, a mechanism $M$ will be called
_$\left(\epsilon,\delta\right)$ -differentially private with respect to $q$_
if for any two datasets $s_{0},s_{1}\in\mathcal{X}^{n}$ that differ only in
one element, the two distributions defined over $\mathcal{R}$ by
${M}\left(s_{0},q\right)$ and ${M}\left(s_{1},q\right)$ are
$\left(\epsilon,\delta\right)$-indistinguishable.

##  Appendix C Missing parts from Section 3

###### Missing Parts From the Proof of Lemma 3.1.

$\displaystyle\underset{V\sim D}{\text{Pr}}\left[\left\lVert
R_{V}-{Q_{V}}\left(D^{V}\right)\right\rVert>\alpha\right]$
$\displaystyle=\underset{V\sim D}{\text{Pr}}\left[\left\lVert
R_{V}-{Q_{V}}\left(D^{V}\right)\right\rVert>c+\left(\alpha-c\right)\right]$
$\displaystyle\leq\underset{V\sim D}{\text{Pr}}\left[\max\left\\{\left\lVert
R_{V}-{Q_{V}}\left(D^{V}\right)\right\rVert-\left(\alpha-c\right),0\right\\}>c\right]$
$\displaystyle\overset{\left(1\right)}{\leq}\frac{1}{c}\underset{V\sim
D}{\mathbb{E}}\left[\max\left\\{\left\lVert
R_{V}-{Q_{V}}\left(D^{V}\right)\right\rVert-\left(\alpha-c\right),0\right\\}\right]$
$\displaystyle=\frac{1}{c}\underset{V\sim
D}{\mathbb{E}}\left[\max\left\\{\left\lVert
R_{V}-\underset{S\sim{D}\left(\cdot\,|\,V\right)}{\mathbb{E}}\left[{Q_{V}}\left(S\right)\right]\right\rVert-\left(\alpha-c\right),0\right\\}\right]$
$\displaystyle\overset{\left(2\right)}{\leq}\frac{1}{c}\underset{V\sim
D,S\sim{D}\left(\cdot\,|\,V\right)}{\mathbb{E}}\left[\max\left\\{\left\lVert
R_{V}-{Q_{V}}\left(S\right)\right\rVert-\left(\alpha-c\right),0\right\\}\right]$
$\displaystyle=\frac{1}{c}\underset{S\sim
D,V\sim{M}\left(S,A\right)}{\mathbb{E}}\left[\max\left\\{\left\lVert
R_{V}-{Q_{V}}\left(S\right)\right\rVert-\left(\alpha-c\right),0\right\\}\right]$
$\displaystyle\overset{\left(3\right)}{=}\frac{1}{c}\int_{0}^{\infty}\underset{S\sim
D,V\sim{M}\left(S,A\right)}{\text{Pr}}\left[\max\left\\{\left\lVert
R_{V}-{Q_{V}}\left(S\right)\right\rVert-\left(\alpha-c\right),0\right\\}>t\right]dt$
$\displaystyle=\frac{1}{c}\int_{0}^{\infty}\underset{S\sim
D,V\sim{M}\left(S,A\right)}{\text{Pr}}\left[\max\left\\{\left\lVert
R_{V}-{Q_{V}}\left(S\right)\right\rVert,\left(\alpha-c\right)\right\\}>t+\left(\alpha-c\right)\right]dt$
$\displaystyle\overset{\left(s:=t+\left(\alpha-c\right)\right)}{=}\frac{1}{c}\int_{\alpha-c}^{\infty}\underset{S\sim
D,V\sim{M}\left(S,A\right)}{\text{Pr}}\left[\max\left\\{\left\lVert
R_{V}-{Q_{V}}\left(S\right)\right\rVert,\left(\alpha-c\right)\right\\}>s\right]ds$
$\displaystyle=\frac{1}{c}\int_{\alpha-c}^{\infty}\underset{S\sim
D,V\sim{M}\left(S,A\right)}{\text{Pr}}\left[\left\lVert
R_{V}-{Q_{V}}\left(S\right)\right\rVert>s\right]ds$
$\displaystyle\overset{\left(4\right)}{\leq}\frac{1}{c}\int_{\alpha-c}^{\infty}{\varphi}\left(t\right)dt$

where (1) results from Markov’s inequality, (2) from the triangle inequality,
(3) from the fact that the expectation is taken over a non-negative random
variable and (4) by the definition of sample accuracy (Definition 2.1). ∎

###### Proof of Lemma 3.2.

From the definition of the Laplace distribution, for any dataset $s$ and query
$q$,

$\underset{R\sim{M}\left(s,q\right)}{\text{Pr}}\left[\left\lVert
R-{q}\left(s\right)\right\rVert>\alpha\right]=e^{-\frac{\alpha}{\eta}}.$

Combining this with a union bound proves the sample accuracy part.

Invoking Lemma 3.1 with $c=\eta$ implies

${\Phi}\left(\alpha\right)=\underset{c\in\left(0,\alpha\right)}{\inf}\left(\frac{k}{c}\int_{\alpha-c}^{\infty}e^{-\frac{t}{\eta}}dt\right)=\underset{c\in\left(0,\alpha\right)}{\inf}\left(\frac{k\eta}{c}e^{-\frac{\alpha-c}{\eta}}\right)\leq\frac{k\eta}{\eta}e^{-\frac{\alpha-\eta}{\eta}}=ke^{1-\frac{\alpha}{\eta}},$

which proves the posterior accuracy part. ∎

###### Proof of Lemma 3.3.

In the case of a Gaussian distribution, the tail bound function is also known
as the Q-function and for any dataset $s$ and query $q$,

$\underset{R\sim{M}\left(s,q\right)}{\text{Pr}}\left[\left\lVert
R-{q}\left(s\right)\right\rVert>\alpha\right]=\frac{1}{2}{\text{erfc}}\left(\frac{\alpha}{\sqrt{2}\eta}\right)\leq\frac{\eta}{\sqrt{2\pi}\alpha}e^{-\frac{\alpha^{2}}{2\eta^{2}}}.$

Combining this with a union bound proves the sample accuracy part.

Invoking Lemma 3.1 with $c=\alpha-\sqrt{\alpha^{2}-2\eta^{2}}$ implies

${\Phi}\left(\alpha\right)=\underset{c\in\left(0,\alpha\right)}{\inf}\left(\frac{k}{2c}\int_{\alpha-c}^{\infty}{\text{erfc}}\left(\frac{t}{\sqrt{2}\eta}\right)dt\right)\overset{\left(1\right)}{\leq}\underset{c\in\left(0,\alpha\right)}{\inf}\left(\frac{k\eta}{\sqrt{2\pi}c}e^{-\frac{\left(\alpha-c\right)^{2}}{2\eta^{2}}}\right)\overset{\left(2\right)}{\leq}\frac{k\alpha}{\sqrt{2\pi}\eta}e^{1-\frac{\alpha^{2}}{2\eta^{2}}},$

where (1) results from the fact that
$\int_{a}^{\infty}{\text{erfc}}\left(x\right)dx=\frac{e^{-a^{2}}}{\sqrt{\pi}}-a\cdot{\text{erfc}}\left(a\right)\leq\frac{e^{-a^{2}}}{\sqrt{\pi}}$
and (2) from plugging in the definition of $c$ and using the bound on $\alpha$
and the inequality $\sqrt{1+x}\leq 1+\frac{x}{2}$, thus proving the posterior
accuracy part. ∎

##  Appendix D Missing Parts From Section 4

###### Detailed proof of Lemma 4.5.

From the definition of LBI, for any $x,y\in\mathcal{X}$,
$s^{\prime}\in\mathcal{X}^{n-1}$, and $v\in\mathcal{V}$,

$e^{-{\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,y\right)}\left({D}\left(v\,|\,\left(s^{\prime},x\right)\right)-\delta\right)\leq{D}\left(v\,|\,\left(s^{\prime},y\right)\right)\leq
e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,y\right)}{D}\left(v\,|\,\left(s^{\prime},x\right)\right)+\delta.$

Therefore,

$\displaystyle{D}\left(v\right)$
$\displaystyle=\sum_{s^{\prime}\in\mathcal{X}^{n-1}}{D}\left(s^{\prime}\right)\sum_{y\in\mathcal{X}}{D}\left(y\right){D}\left(v\,|\,\left(s^{\prime},y\right)\right)$
$\displaystyle\leq\sum_{s^{\prime}\in\mathcal{X}^{n-1}}{D}\left(s^{\prime}\right)\sum_{y\in\mathcal{X}}{D}\left(y\right)\left(e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,y\right)}{D}\left(v\,|\,\left(s^{\prime},x\right)\right)+\delta\right)$
$\displaystyle=\sum_{y\in\mathcal{X}}{D}\left(y\right)e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,y\right)}\overset{{D}\left(v\,|\,x\right)}{\overbrace{\sum_{s^{\prime}\in\mathcal{X}^{n-1}}{D}\left(s^{\prime}\right){D}\left(v\,|\,\left(s^{\prime},x\right)\right)}}+\delta$
$\displaystyle=\underset{Y\sim
D}{\mathbb{E}}\left[e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,Y\right)}\right]{D}\left(v\,|\,x\right)+\delta.$

Similarly,

$\displaystyle{D}\left(v\right)$
$\displaystyle=\sum_{s^{\prime}\in\mathcal{X}^{n-1}}{D}\left(s^{\prime}\right)\sum_{y\in\mathcal{X}}{D}\left(y\right){D}\left(v\,|\,\left(s^{\prime},y\right)\right)$
$\displaystyle\geq\sum_{s^{\prime}\in\mathcal{X}^{n-1}}{D}\left(s^{\prime}\right)\sum_{y\in\mathcal{X}}{D}\left(y\right)e^{-{\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,y\right)}\left({D}\left(v\,|\,\left(s^{\prime},x\right)\right)-\delta\right)$
$\displaystyle\overset{\left(1\right)}{\geq}\frac{1}{\sum_{y\in\mathcal{X}}{D}\left(y\right)e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,y\right)}}\left(\overset{{D}\left(v\,|\,x\right)}{\overbrace{\sum_{s^{\prime}\in\mathcal{X}^{n-1}}{D}\left(s^{\prime}\right){D}\left(v\,|\,\left(s^{\prime},x\right)\right)}}-\delta\right)$
$\displaystyle=\frac{1}{\underset{Y\sim
D}{\mathbb{E}}\left[e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,Y\right)}\right]}\left({D}\left(v\,|\,x\right)-\delta\right)$
$\displaystyle\Rightarrow{D}\left(v\,|\,x\right)$
$\displaystyle\leq\underset{Y\sim
D}{\mathbb{E}}\left[e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,Y\right)}\right]{D}\left(v\right)+\delta,$

where (1) results from invoking Jensen’s inequality for the convex function
$\frac{1}{x}$.

Combining the two, we get

$\left|{D}\left(v\,|\,x\right)-{D}\left(v\right)\right|\leq\underset{Y\sim
D}{\mathbb{E}}\left[e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;x,Y\right)}-1\right]{D}\left(v\right)+\delta.$

Using this bound we get

$\displaystyle\left\lVert\underset{X\sim
D}{\text{Cov}}\left({q}\left(X\right),{K}\left(X,v\right)\right)\right\rVert$
$\displaystyle=\left\lVert\underset{X\sim
D}{\mathbb{E}}\left[\left({q}\left(X\right)-{q}\left(D\right)\right)\left({K}\left(X,v\right)-\overset{=1}{\overbrace{{K}\left(D,v\right)}}\right)\right]\right\rVert$
$\displaystyle=\left\lVert\underset{X\sim
D}{\mathbb{E}}\left[\left({q}\left(X\right)-{q}\left(D\right)\right)\left(\frac{{D}\left(v\,|\,X\right)}{{D}\left(v\right)}-\frac{{D}\left(v\right)}{{D}\left(v\right)}\right)\right]\right\rVert$
$\displaystyle=\left\lVert\underset{X\sim
D}{\mathbb{E}}\left[\left({q}\left(X\right)-{q}\left(D\right)\right)\frac{1}{{D}\left(v\right)}\left({D}\left(v\,|\,X\right)-{D}\left(v\right)\right)\right]\right\rVert$
$\displaystyle\leq\underset{X\sim
D}{\mathbb{E}}\left[\left\lVert{q}\left(X\right)-{q}\left(D\right)\right\rVert\cdot\frac{1}{{D}\left(v\right)}\left|{D}\left(v\,|\,X\right)-{D}\left(v\right)\right|\right]$
$\displaystyle\leq\underset{X,X\sim
D}{\mathbb{E}}\left[\left\lVert{q}\left(X\right)-{q}\left(D\right)\right\rVert\frac{1}{{D}\left(v\right)}\left(\left(e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;X,Y\right)}-1\right){D}\left(v\right)+\delta\right)\right]$
$\displaystyle=\underset{X,Y\sim
D}{\mathbb{E}}\left[\left\lVert{q}\left(X\right)-{q}\left(D\right)\right\rVert\left(e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;X,Y\right)}-1\right)\right]$
$\displaystyle~{}~{}~{}~{}+\frac{\delta}{{D}\left(v\right)}\underset{X\sim
D}{\mathbb{E}}\left[\left\lVert{q}\left(X\right)-{q}\left(D\right)\right\rVert\right]$
$\displaystyle\leq\underset{X,Y\sim
D}{\mathbb{E}}\left[\left\lVert{q}\left(X\right)-{q}\left(D\right)\right\rVert\left(e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v;X,Y\right)}-1\right)\right]+\frac{\sigma\delta}{{D}\left(v\right)}.$

######  Lemma D.1.

Given $0\leq\delta$, a function $h:\mathcal{R}\rightarrow\mathbb{R}$ and a
distribution $D$ over $\mathcal{R}$, if for any
$\mathbf{r}\subseteq\mathcal{R}$ we have
$\underset{r\in\mathbf{r}}{\sum}{D}\left(r\right){h}\left(r\right)\leq\delta$,
then for any $0<c$, $\underset{R\sim
D}{\text{Pr}}\left[{h}\left(R\right)>c\right]<\frac{\delta}{c}$.

###### Proof.

Denote $\mathbf{r}_{c}\coloneqq\left\\{r\,|\,{h}\left(r\right)>c\right\\}$,
then

$\underset{R\sim
D}{\text{Pr}}\left[{h}\left(R\right)>c\right]={D}\left(\mathbf{r}_{c}\right)\leq\sum_{r\in\mathbf{r}_{c}}{D}\left(r\right)\overset{>1}{\overbrace{{h}\left(r\right)\frac{1}{c}}}<\frac{\delta}{c}.$

∎

######  Lemma D.2 (Lemma 3.17.1 in [DR+14]).

Given $\epsilon,\delta\geq 0$ and two probability distributions $D_{0},D_{1}$
over some domain $\mathcal{R}$,
${\boldsymbol{D}_{\infty}^{\delta}}\left(D_{0}\lVert D_{1}\right)$ if and only
if there exists another distribution $D_{2}$ such that
${\boldsymbol{D}_{\Delta}}\left(D_{0}\lVert D_{2}\right)\leq\delta$ and
${\boldsymbol{D}_{\infty}}\left(D_{2}\lVert D_{1}\right)\leq\epsilon$.

######  Lemma D.3.

Given $\alpha,\beta\geq 0$ and two probability distributions $D_{0},D_{1}$
over the same domain $\mathcal{R}$, if
${\mathbf{D}_{\infty}}\left(D_{0}\|D_{1}\right)\leq\alpha+\beta$, then there
exists some distribution $D^{\prime}$ over $\mathcal{R}$, such that
${\mathbf{D}_{\infty}}\left(D_{0}\|D^{\prime}\right)\leq\alpha$ and
${\mathbf{D}_{\infty}}\left(D^{\prime}\|D_{1}\right)\leq\beta$.

###### Proof.

Denote
$D^{\prime}=\frac{e^{\beta}-1}{e^{\alpha+\beta}-1}D_{0}+\frac{e^{\alpha+\beta}-e^{\beta}}{e^{\alpha+\beta}-1}D_{1}$.

$\displaystyle{\mathbf{D}_{\infty}}\left(D_{0}\|D^{\prime}\right)$
$\displaystyle=\underset{x\in\mathcal{X}}{\sup}\left({\ln}\left(\frac{{D_{0}}\left(x\right)}{{D^{\prime}}\left(x\right)}\right)\right)$
$\displaystyle=\underset{x\in\mathcal{X}}{\sup}\left(-{\ln}\left(\frac{{D^{\prime}}\left(x\right)}{{D_{0}}\left(x\right)}\right)\right)$
$\displaystyle\overset{\left(1\right)}{=}-{\ln}\left(\underset{x\in\mathcal{X}}{\inf}\left(\frac{{D^{\prime}}\left(x\right)}{{D_{0}}\left(x\right)}\right)\right)$
$\displaystyle=-{\ln}\left(\underset{x\in\mathcal{X}}{\inf}\left(\frac{\frac{e^{\beta}-1}{e^{\alpha+\beta}-1}{D_{0}}\left(x\right)+\frac{e^{\alpha+\beta}-e^{\beta}}{e^{\alpha+\beta}-1}{D_{1}}\left(x\right)}{{D_{0}}\left(x\right)}\right)\right)$
$\displaystyle=-{\ln}\left(\frac{e^{\beta}-1}{e^{\alpha+\beta}-1}+\frac{e^{\alpha+\beta}-e^{\beta}}{e^{\alpha+\beta}-1}\underset{x\in\mathcal{X}}{\inf}\left(\frac{{D_{1}}\left(x\right)}{{D_{0}}\left(x\right)}\right)\right)$
$\displaystyle\overset{\left(2\right)}{\leq}-{\ln}\left(\frac{e^{\beta}-1}{e^{\alpha+\beta}-1}+\frac{e^{\alpha+\beta}-e^{\beta}}{e^{\alpha+\beta}-1}e^{-\left(\alpha+\beta\right)}\right)$
$\displaystyle=-{\ln}\left(\frac{e^{\beta}-e^{-\alpha}}{e^{\alpha+\beta}-1}\right)$
$\displaystyle=-{\ln}\left(e^{-\alpha}\frac{e^{\alpha+\beta}-1}{e^{\alpha+\beta}-1}\right)$
$\displaystyle=-{\ln}\left(e^{-\alpha}\right)$ $\displaystyle=\alpha,$

where (1) results from the fact that for any $Y\subseteq\mathbb{R}_{+}$,
$\underset{y\in
Y}{\sup}\left(-{\ln}\left(y\right)\right)=-{\ln}\left(\underset{y\in
Y}{\inf}y\right)$ and (2) because
$\frac{{D_{1}}\left(x\right)}{{D_{0}}\left(x\right)}\geq
e^{-\left(\alpha+\beta\right)}$ for all $x\in\mathcal{X}$.

$\displaystyle{\mathbf{D}_{\infty}}\left(D^{\prime}\|D_{1}\right)$
$\displaystyle=\underset{x\in\mathcal{X}}{\sup}\left({\ln}\left(\frac{{D^{\prime}}\left(x\right)}{{D_{1}}\left(x\right)}\right)\right)$
$\displaystyle={\ln}\left(\underset{x\in\mathcal{X}}{\sup}\left(\frac{{D^{\prime}}\left(x\right)}{{D_{1}}\left(x\right)}\right)\right)$
$\displaystyle={\ln}\left(\underset{x\in\mathcal{X}}{\sup}\left(\frac{\frac{e^{\beta}-1}{e^{\alpha+\beta}-1}{D_{0}}\left(x\right)+\frac{e^{\alpha+\beta}-e^{\beta}}{e^{\alpha+\beta}-1}{D_{1}}\left(x\right)}{{D_{1}}\left(x\right)}\right)\right)$
$\displaystyle={\ln}\left(\frac{e^{\beta}-1}{e^{\alpha+\beta}-1}\underset{x\in\mathcal{X}}{\sup}\left(\frac{{D_{0}}\left(x\right)}{{D_{1}}\left(x\right)}\right)+\frac{e^{\alpha+\beta}-e^{\beta}}{e^{\alpha+\beta}-1}\right)$
$\displaystyle\leq{\ln}\left(\frac{e^{\beta}-1}{e^{\alpha+\beta}-1}e^{\alpha+\beta}+\frac{e^{\alpha+\beta}-e^{\beta}}{e^{\alpha+\beta}-1}\right)$
$\displaystyle={\ln}\left(e^{\beta}\right)$ $\displaystyle=\beta.$

######  Lemma D.4 (Azuma inequality extension for dynamic bound - Exercise
3.11 in [vH14]).

Given a probability triplet $\left(\Omega,\mathcal{F},\text{Pr}\right)$ and an
increasing sequence of $\sigma$-algebras
$\emptyset=\mathcal{F}_{0}\subseteq\mathcal{F}_{1}\subseteq\ldots\subseteq\mathcal{F}_{k}=\mathcal{F}$
(also known as a filtration), for all $i\in\left[k\right]$ let
$X_{i},A_{i},B_{i}$ be a real-valued random variable such that $X_{i}$ is
$\mathcal{F}_{i}$-measurable, $A_{i},B_{i}$ are
$\mathcal{F}_{i-1}$-measurable,
$\underset{}{\mathbb{E}}\left[X_{i}|\mathcal{F}_{i-1}\right]=0$ and $A_{i}\leq
X_{i}\leq B_{i}$ almost surely, and define the martingale $Y_{0}\coloneqq 0$,
$\forall i>0:Y_{i}\coloneqq\sum_{j=1}^{i}X_{j}$. For any
$\epsilon_{1},\epsilon_{2}\geq 0$,

$\underset{X_{1},\ldots,X_{k}}{\text{Pr}}\left[Y_{k}\geq\epsilon_{1}~{}~{}~{}\text{and}~{}~{}~{}\sqrt{\sum_{i=1}^{k}\left(B_{i}-A_{i}\right)^{2}}\leq\epsilon_{2}\right]\leq
e^{-2\left(\frac{\epsilon_{1}}{\epsilon_{2}}\right)^{2}}.$

###### Proof.

We first prove that for any $\lambda\geq 0$ and $i\geq 0$,

$\underset{}{\mathbb{E}}\left[{\exp}\left(\lambda
Y_{i}-\frac{\lambda^{2}}{8}\sum_{j=1}^{i}\left(B_{j}-A_{j}\right)^{2}\right)\right]\leq
1.$

This is done by induction over the filtration. The base case of $i=0$ is
trivial; for the induction step we prove that for all $i>0$,

$\displaystyle\mathbb{E}$ $\displaystyle\left[{\exp}\left(\lambda
Y_{i}-\frac{\lambda^{2}}{8}\sum_{j=1}^{i}\left(B_{j}-A_{j}\right)^{2}\right)\,|\,\mathcal{F}_{i-1}\right]$
$\displaystyle={\exp}\left(\lambda
Y_{i-1}-\frac{\lambda^{2}}{8}\sum_{j=1}^{i}\left(B_{j}-A_{j}\right)^{2}\right)\underset{}{\mathbb{E}}\left[{\exp}\left(\lambda
X_{i}\right)\,|\,\mathcal{F}_{i-1}\right]$
$\displaystyle\overset{\left(1\right)}{\leq}{\exp}\left(\lambda
Y_{i-1}-\frac{\lambda^{2}}{8}\sum_{j=1}^{i}\left(B_{j}-A_{j}\right)^{2}\right)\cdot{\exp}\left(\frac{\lambda^{2}}{8}\left(B_{i}-A_{i}\right)^{2}\right)$
$\displaystyle={\exp}\left(\lambda
Y_{i-1}-\frac{\lambda^{2}}{8}\sum_{j=1}^{i-1}\left(B_{j}-A_{j}\right)^{2}\right)$
$\displaystyle=\underset{}{\mathbb{E}}\left[{\exp}\left(\lambda
Y_{i-1}-\frac{\lambda^{2}}{8}\sum_{j=1}^{i-1}\left(B_{j}-A_{j}\right)^{2}\right)\,|\,\mathcal{F}_{i-2}\right]$

where (1) results from Hoeffding’s lemma, which completes the proof.

$\displaystyle\underset{}{\text{Pr}}$
$\displaystyle\left[Y_{k}\geq\epsilon_{1}~{}~{}~{}\text{and}~{}~{}~{}\sqrt{\sum_{i=1}^{k}\left(B_{i}-A_{i}\right)^{2}}\leq\epsilon_{2}\right]$
$\displaystyle\leq\underset{}{\text{Pr}}\left[\lambda
Y_{k}-\frac{\lambda^{2}}{8}\sum_{i=1}^{k}\left(B_{i}-A_{i}\right)^{2}\geq\lambda\epsilon_{1}-\frac{\lambda^{2}\epsilon_{2}^{2}}{8}\right]$
$\displaystyle=\underset{}{\text{Pr}}\left[{\exp}\left(\lambda
Y_{k}-\frac{\lambda^{2}}{8}\sum_{i=1}^{k}\left(B_{i}-A_{i}\right)^{2}\right)\geq
e^{\lambda\epsilon_{1}-\frac{\lambda^{2}\epsilon_{2}^{2}}{8}}\right]$
$\displaystyle\overset{\left(1\right)}{\leq}e^{\frac{\lambda^{2}\epsilon_{2}^{2}}{8}-\lambda\epsilon_{1}}\cdot\underset{}{\mathbb{E}}\left[{\exp}\left(\lambda
Y_{k}-\frac{\lambda^{2}}{8}\sum_{i=1}^{k}\left(B_{i}-A_{i}\right)^{2}\right)\right]$
$\displaystyle\overset{\left(2\right)}{\leq}e^{\frac{\lambda^{2}\epsilon_{2}^{2}}{8}-\lambda\epsilon_{1}}$

where (1) results from Markov’s inequality and (2) from the previous claim.

Setting $\lambda=\frac{4\epsilon_{1}}{\epsilon_{2}^{2}}$ completes the proof.
∎

###### Missing Details From the Proof of Theorem 4.6.

Define the following random variables:

$\displaystyle{\tilde{L}_{i}}\left(v_{i}\right)\coloneqq$
$\displaystyle{\ln}\left(\frac{{D^{q_{i}}}\left(r_{i}\,|\,\left(s^{\prime},y\right)\right)}{{D^{q_{i}}}\left(r_{i}\,|\,\left(s^{\prime},x\right)\right)}\right)$
$\displaystyle{\tilde{L}^{1}_{i}}\left(v_{i}\right)\coloneqq$
$\displaystyle{\ln}\left(\frac{{D^{q_{i}}}\left(r_{i}\,|\,\left(s^{\prime},y\right)\right)}{{D^{\prime}_{i}}\left(r_{i}\right)}\right)$
$\displaystyle{\tilde{L}^{2}_{i}}\left(v_{i}\right)\coloneqq$
$\displaystyle{\ln}\left(\frac{{D^{\prime}_{i}}\left(r_{i}\right)}{{D^{q_{i}}}\left(r_{i}\,|\,\left(s^{\prime},x\right)\right)}\right)$
$\displaystyle{L_{i}}\left(v_{i}\right)\coloneqq$
$\displaystyle{\tilde{L}^{1}_{i}}\left(v_{i}\right)-\underset{R\sim{M}\left(\left(s^{\prime},x\right),q_{i}\right)}{\mathbb{E}}\left[{\tilde{L}^{1}_{i}}\left(\left(v_{i-1},R\right)\right)\right].$

Using this notation we get that

$\displaystyle{\ln}\left(\frac{{D}\left(v_{k}\,|\,\left(s^{\prime},y\right)\right)}{{D}\left(v_{k}\,|\,\left(s^{\prime},x\right)\right)}\right)$
$\displaystyle={\ln}\left(\prod_{i=1}^{k}\frac{{D}\left(v_{i}\,|\,\left(s^{\prime},y\right),v_{i-1}\right)}{{D}\left(v_{i}\,|\,\left(s^{\prime},x\right),v_{i-1}\right)}\right)$
$\displaystyle=\sum_{i=1}^{k}{\ln}\left(\frac{{D}\left(r_{i}\,|\,\left(s^{\prime},y\right),v_{i-1}\right)}{{D}\left(r_{i}\,|\,\left(s^{\prime},x\right),v_{i-1}\right)}\right)$
$\displaystyle\overset{\left(1\right)}{=}\sum_{i=1}^{k}{\ln}\left(\frac{{D^{q_{i}}}\left(r_{i}\,|\,\left(s^{\prime},y\right)\right)}{{D^{q_{i}}}\left(r_{i}\,|\,\left(s^{\prime},x\right)\right)}\right)$
$\displaystyle=\sum_{i=1}^{k}{\tilde{L}_{i}}\left(v_{i}\right)$
$\displaystyle=\sum_{i=1}^{k}\left({L_{i}}\left(v_{i}\right)+\overset{\frac{\gamma^{2}_{1}}{2}\left\lVert{q_{i}}\left(x\right)-{q_{i}}\left(y\right)\right\rVert^{2}}{\overbrace{\underset{v_{i}\sim{M}\left(\left(s^{\prime},x\right),A\right)}{\mathbb{E}}\left[{\tilde{L}^{1}_{i}}\left(v_{i}\right)\right]}}+\overset{\gamma_{2}\left\lVert{q_{i}}\left(x\right)-{q_{i}}\left(y\right)\right\rVert^{2}}{\overbrace{{\tilde{L}^{2}_{i}}\left(v_{i}\right)}}\right)$
$\displaystyle\overset{\left(2\right)}{\leq}\sum_{i=1}^{k}\left({L_{i}}\left(v_{i}\right)+\left(\frac{\gamma^{2}_{1}}{2}+\gamma_{2}\right)\left\lVert{q_{i}}\left(x\right)-{q_{i}}\left(y\right)\right\rVert^{2}\right)$
$\displaystyle=\sum_{i=1}^{k}{L_{i}}\left(v_{i}\right)+\left(\frac{\gamma^{2}_{1}}{2}+\gamma_{2}\right)\left\lVert{\bar{q}_{v}}\left(x\right)-{\bar{q}_{v}}\left(y\right)\right\rVert^{2}$

where (1) results from the fact that $q_{i}$ could already encode $v_{i-1}$
and (2) from the bound on
$\underset{R\sim{M}\left(\left(s^{\prime},x\right),q_{i}\right)}{\mathbb{E}}\left[{\tilde{L}^{1}_{i}}\left(\left(v_{i-1},R\right)\right)\right]$
and the definition of $D^{\prime}_{i}$. ∎

###### Proof of Theorem 4.3.

From Theorem 4.6, $M$ is
$\left(\tilde{\gamma}_{1},\tilde{\gamma}_{2},k\delta+\delta^{\prime}\right)$-LBI
with respect to $A$. From Lemma 4.5, this implies that for all
$v\in\mathcal{V}_{k}$ and $i\in\left[k\right]$

$\displaystyle\underset{i\in\left[k\right]}{\max}$
$\displaystyle\left\lVert{q_{i}}\left(D^{v_{i-1}}\right)-{q_{i}}\left(D\right)\right\rVert$
$\displaystyle=\underset{i\in\left[k\right]}{\max}\left\lVert\underset{X\sim
D}{\text{Cov}}\left({q_{i}}\left(X\right),{K}\left(X,v_{i-1}\right)\right)\right\rVert$
$\displaystyle\leq\underset{i\in\left[k\right]}{\max}\left(\underset{X,Y\sim
D}{\mathbb{E}}\left[\left\lVert{q_{i}}\left(X\right)-{q_{i}}\left(D\right)\right\rVert\left(e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v_{i-1};X,Y\right)}-1\right)\right]+\frac{\sigma\delta}{{D}\left(v_{i-1}\right)}\right)$
$\displaystyle\leq\underset{i\in\left[k\right]}{\max}\left(\underset{X,Y\sim
D}{\mathbb{E}}\left[\left\lVert{q_{i}}\left(X\right)-{q_{i}}\left(D\right)\right\rVert\left(e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v_{i-1};X,Y\right)}-1\right)\right]\right)+\frac{\sigma\delta}{{D}\left(v\right)}$

Invoking Lemma D.1 for the function

${h}\left(v\right)\coloneqq\underset{i\in\left[k\right]}{\max}\left(\left\lVert{q_{i}}\left(D^{v_{i-1}}\right)-{q_{i}}\left(D\right)\right\rVert-\underset{X,Y\sim
D}{\mathbb{E}}\left[\left\lVert{q_{i}}\left(X\right)-{q_{i}}\left(D\right)\right\rVert\left(e^{{\ell_{\gamma_{1},\gamma_{2}}}\left(v_{i-1};X,Y\right)}-1\right)\right]\right)$

completes the proof. ∎

###### Proof of Lemma 4.7.

For any $s^{\prime}\in\mathcal{X}^{n-1}$, $x,y\in\mathcal{X}$,
$r\in\mathcal{R}$,

$\displaystyle{D}\left(r\,|\,\left(s^{\prime},x\right)\right)$
$\displaystyle={D}\left(s^{\prime}\right)\frac{1}{2\eta}{\exp}\left(\frac{1}{\eta}\left\lVert{q}\left(\left(s^{\prime},x\right)\right)-r\right\rVert\right)$
$\displaystyle\overset{\left(1\right)}{\leq}\frac{1}{2\eta}{\exp}\left(\frac{1}{\eta}\left\lVert{q}\left(\left(s^{\prime},y\right)\right)-r\right\rVert+\frac{1}{n\eta}\left\lVert{q}\left(x\right)-{q}\left(y\right)\right\rVert\right)$
$\displaystyle={\exp}\left(\frac{1}{n\eta}\left\lVert{q}\left(x\right)-{q}\left(y\right)\right\rVert\right){D}\left(r\,|\,\left(s^{\prime},y\right)\right)$

where (1) results from the definition of linear query and the triangle
inequality.

The second part is a direct result of Theorem 4.6. ∎

###### Proof of Lemma 4.8.

The proof makes use of several claims proven by [BS16]. In their Lemma 17,
[BS16] prove that if $M$ is a Gaussian Mechanism with noise parameter $\eta$,
then for any $\alpha\geq 1$,
$s^{\prime}\in\mathcal{X}^{n-1},x,y\in\mathcal{X}$ and query $q$,

${\mathbf{D}_{\alpha}}\left({M}\left(\left(s^{\prime},x\right),q\right)\lVert{M}\left(\left(s^{\prime},y\right),q\right)\right)\leq\frac{\alpha}{2n^{2}\eta^{2}}\left\lVert{q}\left(x\right)-{q}\left(y\right)\right\rVert^{2},$

where $\mathbf{D}_{\alpha}$ is the
$\alpha$-$\text{R}\acute{\text{e}}\text{nyi}$ Divergence (Definition B.4).

In their Lemma 21, [BS16] prove that given $\rho>0$ and two distributions
$D_{0},D_{1}$, if for any $\alpha\geq 1$ and $i\in\left\\{0,1\right\\}$,
${\mathbf{D}_{\alpha}}\left(D_{i}\lVert D_{1-i}\right)\leq\rho\alpha$ then for
any $\delta>0$, $D_{0}$ and $D_{1}$ are
$\left(\rho+2\sqrt{\rho{\ln}\left(\frac{1}{\delta}\right)},\delta\right)$-Indistinguishable.
Combining these two claims completes the proof of the first part.

The second part is a direct result of Theorem 4.6. ∎

##  Appendix E Missing Parts From Section 5

###### Missing Parts From the Proof of Theorem 5.1.

From the definition of $\ell$, for any $i\in\left[k\right]$,

$\displaystyle\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}$
$\displaystyle\left(v_{i-1};x,y\right)$
$\displaystyle=\gamma_{1}\sqrt{2{\ln}\left(\frac{1}{\delta^{\prime}}\right)}\left\lVert{\bar{q}_{v_{i-1}}}\left(x\right)-{\bar{q}_{v_{i-1}}}\left(y\right)\right\rVert+\left(\overset{\leq\frac{\gamma_{1}^{2}}{2}}{\overbrace{\gamma_{2}}}+\frac{\gamma_{1}^{2}}{2}\right)\left\lVert{\bar{q}_{v_{i-1}}}\left(x\right)-{\bar{q}_{v_{i-1}}}\left(y\right)\right\rVert^{2}$
$\displaystyle\overset{\left(1\right)}{\leq}\gamma_{1}\left(\sqrt{2{\ln}\left(\frac{1}{\delta^{\prime}}\right)}+\gamma_{1}\overset{\leq\sqrt{k}\Delta}{\overbrace{\left\lVert{\bar{q}_{v_{i-1}}}\left(x\right)-{\bar{q}_{v_{i-1}}}\left(y\right)\right\rVert}}\right)\left\lVert{\bar{q}_{v_{i-1}}}\left(x\right)-{\bar{q}_{v_{i-1}}}\left(y\right)\right\rVert$
$\displaystyle\overset{\left(2\right)}{\leq}\gamma_{1}\left(\sqrt{2{\ln}\left(\frac{1}{\delta^{\prime}}\right)}+\gamma_{1}\sqrt{k}\Delta\right)\left\lVert{\bar{q}_{v_{i-1}}}\left(x\right)-{\bar{q}_{v_{i-1}}}\left(y\right)\right\rVert$
$\displaystyle\overset{\left(3\right)}{\leq}\gamma_{1}\left(\sqrt{2{\ln}\left(\frac{1}{\delta^{\prime}}\right)}+\frac{1}{2\sqrt{{\ln}\left(\frac{1}{\delta^{\prime}}\right)}}\right)\left\lVert{\bar{q}_{v_{i-1}}}\left(x\right)-{\bar{q}_{v_{i-1}}}\left(y\right)\right\rVert$
$\displaystyle\overset{\left(4\right)}{\leq}2\gamma_{1}\sqrt{{\ln}\left(\frac{1}{\delta^{\prime}}\right)}\left\lVert{\bar{q}_{v_{i-1}}}\left(x\right)-{\bar{q}_{v_{i-1}}}\left(y\right)\right\rVert$
$\displaystyle\overset{\left(1\right)}{\leq}2\gamma_{1}\sqrt{{\ln}\left(\frac{1}{\delta^{\prime}}\right)}\sqrt{k}\Delta$
$\displaystyle\overset{\left(3\right)}{\leq}1,$

where (1) results from the bound on $\gamma_{2}$, (2) from the bounded range
of the queries, (3) from the lower bound on $\delta^{\prime}$ and (4) from the
upper bound on $\delta^{\prime}$. ∎

######  Lemma E.1.

If $X$ is a centered sub-Gaussian random variable with parameter $\sigma>0$,
then

  * •

for any $\lambda>0$, $\underset{}{\text{Pr}}\left[X\geq\lambda\right]\leq
e^{-\frac{\lambda^{2}}{4\sigma^{2}}}$,

  * •

for any $n\geq 2$, $\underset{}{\mathbb{E}}\left[\left|X\right|^{n}\right]\leq
n\left(2\sigma^{2}n\right)^{\frac{n}{2}}$,

  * •

for any $0\leq\lambda\leq\frac{1}{\sqrt{5e}\sigma}$,
$\underset{X}{\mathbb{E}}\left[e^{\lambda^{2}X^{2}}\right]\leq\frac{1}{1-5e\lambda^{2}\sigma^{2}}$.

###### Proof.

For the first part notice that

$\underset{}{\text{Pr}}\left[X\geq\lambda\right]=\underset{}{\text{Pr}}\left[e^{\frac{\lambda}{2\sigma^{2}}X}\geq
e^{\frac{\lambda^{2}}{2\sigma^{2}}}\right]\overset{\left(1\right)}{\leq}e^{-\frac{\lambda^{2}}{2\sigma^{2}}}\underset{}{\mathbb{E}}\left[e^{\frac{\lambda}{2\sigma^{2}}X}\right]\overset{\left(2\right)}{\leq}e^{-\frac{\lambda^{2}}{2\sigma^{2}}}\cdot
e^{\frac{\lambda^{2}}{4\sigma^{4}}\sigma^{2}}=e^{-\frac{\lambda^{2}}{4\sigma^{2}}},$

where (1) is by Markov’s inequality and (2) results from the sub-Gaussian
definition.

For the second part we use this bound and get that for any $n\geq 2$,

$\displaystyle\underset{}{\mathbb{E}}\left[\left|X\right|^{n}\right]$
$\displaystyle=\int_{0}^{\infty}\underset{}{\text{Pr}}\left[\left|X\right|^{n}\geq
u\right]du$
$\displaystyle\overset{\left(t=u^{1/n}\right)}{=}\int_{0}^{\infty}\underset{}{\text{Pr}}\left[\left|X\right|\geq
t\right]nt^{n-1}dt$
$\displaystyle\overset{\left(1\right)}{\leq}n\int_{0}^{\infty}2e^{-\frac{t^{2}}{4\sigma^{2}}}t^{n-1}dt$
$\displaystyle\overset{\left(s=\frac{t^{2}}{4\sigma^{2}}\right)}{=}2n\int_{0}^{\infty}e^{-s}\left(2\sigma\sqrt{s}\right)^{n-1}\frac{\sigma}{\sqrt{s}}ds$
$\displaystyle=n\left(2\sigma\right)^{n}\int_{0}^{\infty}e^{-s}s^{\frac{n}{2}-1}ds$
$\displaystyle\overset{\left(2\right)}{=}n\left(2\sigma\right)^{n}{\Gamma}\left(\frac{n}{2}\right)$
$\displaystyle\overset{\left(3\right)}{\leq}n\left(2\sigma\right)^{n}\left(\frac{n}{2}\right)^{\frac{n}{2}}$
$\displaystyle=n\left(2\sigma^{2}n\right)^{\frac{n}{2}},$

where (1) is by the previous inequality, (2) is by the Gamma function
definition, and (3) results from the inequality ${\Gamma}\left(n\right)\leq
n^{n}$ for any $n\geq 1$ .

For the third part we observe that

$\displaystyle\underset{}{\mathbb{E}}\left[e^{\lambda^{2}X^{2}}\right]$
$\displaystyle=\underset{}{\mathbb{E}}\left[\sum_{n=0}^{\infty}\frac{\left(\lambda^{2}X^{2}\right)^{n}}{n!}\right]$
$\displaystyle=1+\sum_{n=1}^{\infty}\frac{\lambda^{2n}}{n!}\underset{}{\mathbb{E}}\left[X^{2n}\right]$
$\displaystyle\overset{\left(1\right)}{\leq}1+\sum_{n=1}^{\infty}\frac{\lambda^{2n}2n\left(4\sigma^{2}n\right)^{n}}{\sqrt{2\pi
n}\left(\frac{n}{e}\right)^{n}}$
$\displaystyle\overset{\left(2\right)}{\leq}1+\sum_{n=1}^{\infty}\left(4e\sqrt{e^{\frac{1}{e}}}\lambda^{2}\sigma^{2}\right)^{n}$
$\displaystyle\leq\sum_{n=0}^{\infty}\left(5e\lambda^{2}\sigma^{2}\right)^{n}$
$\displaystyle\overset{\left(3\right)}{\leq}\frac{1}{1-5e\lambda^{2}\sigma^{2}},$

where (1) results from the previous inequality and Stirling’s inequality, (2)
from the inequality $n\leq e^{\frac{n}{e}}$ and (3) is a converging geometric
series from the bound on $\lambda$. ∎

######  Lemma E.2.

Given $d\in\mathbb{N}$, $v\in\mathbb{R}^{d}$ and a series
$\bar{X}\coloneqq\left(X_{1},X_{2},\ldots,X_{d}\right)$ of $d$ sub-Gaussian
independent random variables with parameter $\sigma$, then $\langle
v,\bar{X}\rangle$ is also a sub-Gaussian random variable with parameter
$\left\lVert v\right\rVert\sigma$.

###### Proof.

For any $\lambda\in\mathbb{R}$,

$\underset{}{\mathbb{E}}\left[e^{\lambda
v^{T}\bar{X}}\right]=\underset{}{\mathbb{E}}\left[\prod_{i=1}^{d}e^{\lambda
v_{i}X_{i}}\right]\overset{\left(1\right)}{=}\prod_{i=1}^{d}\underset{}{\mathbb{E}}\left[e^{\lambda
v_{i}X_{i}}\right]\leq\prod_{i=1}^{d}e^{\lambda^{2}v^{2}_{i}\sigma^{2}}=e^{\lambda^{2}\left\lVert
v\right\rVert^{2}\sigma^{2}},$

where (1) is a result of the independence of the random variables. ∎

######  Lemma E.3.

Given $d\in\mathbb{N}$ and a sequence
$\bar{X}\coloneqq\left(X_{1},\ldots,X_{d}\right)$ of $d$ sub-Gaussian random
variables with parameter $\sigma$, then

  * •

for any $\lambda>0$,
$\underset{X}{\mathbb{E}}\left[e^{\lambda\left\lVert\bar{X}\right\rVert}\right]\leq
e^{2\lambda\sqrt{2d}\sigma+4\lambda^{2}d\sigma^{2}}$,

  * •

for any $0\leq\lambda\leq\frac{1}{\sqrt{5e\cdot d}\sigma},$
$\underset{X}{\mathbb{E}}\left[e^{\lambda^{2}\left\lVert\bar{X}\right\rVert^{2}}\right]\leq\frac{1}{1-5e\lambda^{2}d\sigma^{2}}$.

###### Proof.

$\underset{}{\mathbb{E}}\left[e^{\lambda\left\lVert\bar{X}\right\rVert}\right]=\underset{}{\mathbb{E}}\left[\sum_{n=0}^{\infty}\frac{\left(\lambda\left\lVert\bar{X}\right\rVert\right)^{n}}{n!}\right]=1+\lambda\underset{}{\mathbb{E}}\left[\sqrt{\sum_{i=1}^{d}X_{i}^{2}}\right]+\sum_{n=2}^{\infty}\frac{\lambda^{n}}{n!}\underset{}{\mathbb{E}}\left[\left(\sum_{i=1}^{d}X_{i}^{2}\right)^{\frac{n}{2}}\right].$

We will analyze the two parts separately.

$\underset{}{\mathbb{E}}\left[\sqrt{\sum_{i=1}^{d}X_{i}^{2}}\right]\overset{\left(1\right)}{\leq}\sqrt{\sum_{i=1}^{d}\underset{}{\mathbb{E}}\left[X_{i}^{2}\right]}\overset{\left(2\right)}{\leq}\sqrt{\sum_{i=1}^{d}8\sigma^{2}}=2\sqrt{2d}\sigma,$

where (1) results from Jensen’s inequality for the concave case and (2) from
the bound proved in Lemma E.1.

$\displaystyle\sum_{n=2}^{\infty}\frac{\lambda^{n}}{n!}\underset{}{\mathbb{E}}\left[\left(\sum_{i=1}^{d}X_{i}^{2}\right)^{\frac{n}{2}}\right]$
$\displaystyle=\sum_{n=2}^{\infty}\frac{\lambda^{n}}{n!}\underset{}{\mathbb{E}}\left[\left(\frac{1}{d}\sum_{i=1}^{d}dX_{i}^{2}\right)^{\frac{n}{2}}\right]$
$\displaystyle\overset{\left(1\right)}{\leq}\sum_{n=2}^{\infty}\frac{\lambda^{n}}{n!}\frac{1}{d}\sum_{i=1}^{d}\underset{}{\mathbb{E}}\left[\left(dX_{i}^{2}\right)^{\frac{n}{2}}\right]$
$\displaystyle=\frac{1}{d}\sum_{i=1}^{d}\left(\sum_{n=2}^{\infty}\frac{\lambda^{n}d^{\frac{n}{2}}}{n!}\underset{}{\mathbb{E}}\left[\left|X_{i}\right|^{n}\right]\right)$
$\displaystyle\overset{\left(2\right)}{=}\frac{1}{d}\sum_{i=1}^{d}\left(\sum_{m=1}^{\infty}\frac{\lambda^{2m}d^{m}}{\left(2m\right)!}\underset{}{\mathbb{E}}\left[X_{i}^{2m}\right]+\sum_{m=1}^{\infty}\frac{\lambda^{2m+1}d^{m+\frac{1}{2}}}{\left(2m+1\right)!}\underset{}{\mathbb{E}}\left[\left|X_{i}\right|^{2m+1}\right]\right)$
$\displaystyle\overset{\left(3\right)}{\leq}\sum_{m=1}^{\infty}\frac{\lambda^{2m}d^{m}}{\left(2m\right)!}2m\left(2\sigma\right)^{2m}{\Gamma}\left(m\right)$
$\displaystyle~{}~{}~{}~{}+\sum_{m=1}^{\infty}\frac{\lambda^{2m+1}d^{m+\frac{1}{2}}}{\left(2m+1\right)!}\left(2m+1\right)\left(2\sigma\right)^{2m+1}{\Gamma}\left(m+\frac{1}{2}\right)$
$\displaystyle=\sum_{m=1}^{\infty}\left(4\lambda^{2}d\sigma^{2}\right)^{m}\left(\frac{{\Gamma}\left(m\right)}{\left(2m-1\right)!}+2\lambda\sqrt{d}\sigma\frac{{\Gamma}\left(m+\frac{1}{2}\right)}{\left(2m\right)!}\right)$
$\displaystyle\overset{\left(4\right)}{\leq}\left(1+2\lambda\sqrt{d}\sigma\right)\sum_{m=1}^{\infty}\frac{\left(4\lambda^{2}d\sigma^{2}\right)^{m}}{\left(2m\right)!}2m{\Gamma}\left(m\right)$
$\displaystyle=\left(1+2\lambda\sqrt{d}\sigma\right)\sum_{m=1}^{\infty}\frac{2m!}{\left(2m\right)!}\left(4\lambda^{2}d\sigma^{2}\right)^{m}$
$\displaystyle\overset{\left(5\right)}{\leq}\left(1+2\lambda\sqrt{d}\sigma\right)\sum_{m=1}^{\infty}\frac{\left(4\lambda^{2}d\sigma^{2}\right)^{m}}{m!}$

where (1) results from Jensen’s inequality (treating the sum over $d$ as a
uniform distribution), (2) is simply splitting the sum to odds and evens, (3)
repeats the proof of Lemma E.1 with $\sqrt{d}\sigma$ replacing $\sigma$, (4)
from the inequality
$\frac{{\Gamma}\left(m\right)}{\left(2m-1\right)!}\geq\frac{{\Gamma}\left(m+\frac{1}{2}\right)}{\left(2m\right)!}$
for any $m\geq 1$ and (5) from the inequality
$2\left(n!\right)^{2}\leq\left(2n\right)!$.

Combining the two we get

$\displaystyle\underset{}{\mathbb{E}}\left[e^{\lambda\left\lVert\bar{X}\right\rVert}\right]$
$\displaystyle=1+\lambda\underset{}{\mathbb{E}}\left[\sqrt{\sum_{i=1}^{d}X_{i}^{2}}\right]+\sum_{n=2}^{\infty}\frac{\lambda^{n}}{n!}\underset{}{\mathbb{E}}\left[\left(\sum_{i=1}^{d}X_{i}^{2}\right)^{\frac{n}{2}}\right]$
$\displaystyle\leq
1+2\lambda\sqrt{2d}\sigma+\left(1+2\lambda\sqrt{d}\sigma\right)\sum_{n=1}^{\infty}\frac{\left(4\lambda^{2}d\sigma^{2}\right)^{n}}{n!}$
$\displaystyle\leq\left(1+2\lambda\sqrt{2d}\sigma\right)\sum_{n=0}^{\infty}\frac{\left(4\lambda^{2}d\sigma^{2}\right)^{n}}{n!}$
$\displaystyle\overset{\left(1\right)}{\leq}e^{2\lambda\sqrt{2d}\sigma+4\lambda^{2}d\sigma^{2}},$

where (1) results from the inequality $1+x\leq e^{x}$ for any $x\geq 0$.

The second part is proved in a similar way.

$\displaystyle\underset{}{\mathbb{E}}\left[e^{\lambda^{2}\left\lVert\bar{X}\right\rVert^{2}}\right]$
$\displaystyle=\underset{}{\mathbb{E}}\left[\sum_{n=0}^{\infty}\frac{\left(\lambda^{2}\left\lVert\bar{X}\right\rVert^{2}\right)^{n}}{n!}\right]$
$\displaystyle=1+\sum_{n=1}^{\infty}\frac{\lambda^{2n}}{n!}\underset{}{\mathbb{E}}\left[\left(\sum_{i=1}^{d}X_{i}^{2}\right)^{n}\right]$
$\displaystyle=1+\sum_{n=1}^{\infty}\frac{\lambda^{2n}}{n!}\underset{}{\mathbb{E}}\left[\left(\frac{1}{d}\sum_{i=1}^{d}dX_{i}^{2}\right)^{n}\right]$
$\displaystyle\overset{\left(1\right)}{\leq}1+\sum_{n=1}^{\infty}\frac{\lambda^{2n}}{n!}\frac{1}{d}\sum_{i=1}^{d}\underset{}{\mathbb{E}}\left[\left(dX_{i}^{2}\right)^{n}\right]$
$\displaystyle=\frac{1}{d}\sum_{i=1}^{d}\left(1+\sum_{n=1}^{\infty}\frac{\lambda^{2n}d^{n}}{n!}\underset{}{\mathbb{E}}\left[X_{i}^{2n}\right]\right)$
$\displaystyle\overset{\left(2\right)}{\leq}\frac{1}{1-5e\lambda^{2}d\sigma^{2}}$

where (1) results from Jensen’s inequality (treating the sum over $d$ as a
uniform distribution) and (2) repeats the proof of Lemma E.1 with
$\sqrt{d}\sigma$ replacing $\sigma$.

∎

###### Proof of Theorem 5.3.

Denote
$\tilde{\gamma}_{1}\coloneqq\gamma_{1}\sqrt{2{\ln}\left(\frac{1}{\delta^{\prime}}\right)}$,
$\tilde{\gamma}_{2}\coloneqq\gamma_{2}+\frac{\gamma^{2}_{1}}{2}$, and
$\lambda\coloneqq 4\tilde{\gamma}_{1}\sqrt{kd}\sigma$. From the lower bound on
$\delta^{\prime}$,
$156k\gamma_{1}^{2}\sigma^{2}{\ln}\left(\frac{1}{\delta^{\prime}}\right)=78k\tilde{\gamma}_{1}^{2}\sigma^{2}\leq
1$.

Using this notation we get

$\displaystyle\underset{X,Y\sim D}{\mathbb{E}}$
$\displaystyle\left[\left\lVert{q_{i}}\left(X\right)-{q_{i}}\left(D\right)\right\rVert\left({\exp}\left({\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)\right)-1\right)\right]$
$\displaystyle\overset{\left(1\right)}{=}\left(e^{\lambda}-1\right)\underset{X,Y\sim
D}{\mathbb{E}}\left[\left\lVert{q_{i}}\left(X\right)-{q_{i}}\left(D\right)\right\rVert{\exp}\left({\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)-\lambda\right)\right]$
$\displaystyle~{}~{}~{}~{}+\underset{X,Y\sim
D}{\mathbb{E}}\left[\left\lVert{q_{i}}\left(X\right)-{q_{i}}\left(D\right)\right\rVert\left({\exp}\left({\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)-\lambda\right)-1\right)\right]$
$\displaystyle\overset{\left(2\right)}{\leq}\left(e^{\lambda}-1\right)\sqrt{\underset{X\sim
D}{\mathbb{E}}\left[\left\lVert{q_{i}}\left(X\right)-{q_{i}}\left(D\right)\right\rVert^{2}\right]\cdot\underset{X,Y\sim
D}{\mathbb{E}}\left[{\exp}\left(2\left({\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)-\lambda\right)\right)\right]}$
$\displaystyle~{}~{}~{}~{}+\sqrt{\underset{X\sim
D}{\mathbb{E}}\left[\left\lVert{q_{i}}\left(X\right)-{q_{i}}\left(D\right)\right\rVert^{2}\right]\cdot\underset{X,Y\sim
D}{\mathbb{E}}\left[\left({\exp}\left({\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)-\lambda\right)-1\right)^{2}\right]}$
$\displaystyle\overset{\left(3\right)}{\leq}\sigma\left(e^{\lambda}-1\right)\sqrt{\underset{X,Y\sim
D}{\mathbb{E}}\left[{\exp}\left(2\left({\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)-\lambda\right)\right)\right]}$
$\displaystyle~{}~{}~{}~{}+\sigma\sqrt{\underset{X,Y\sim
D}{\mathbb{E}}\left[{\exp}\left(2\left({\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)-\lambda\right)\right)\right]-1},$

where (1) results from the identity
$e^{a}-1=\left(e^{b}-1\right)e^{a-b}+e^{a-b}-1$, (2) from the Cauchy-Schwarz
inequality and (3) from the fact that the variance of a sub-Gaussian random
variable is bounded by $\sigma^{2}$ and the fact that
$\left(e^{x}-1\right)^{2}\leq e^{2x}-1$ for any $x>0$.

For any $i\in\left[k\right]$, denote
$Z_{i}=\left\lVert{\bar{q}_{v_{i}}}\left(X\right)-{\bar{q}_{v_{i}}}\left(Y\right)\right\rVert$.

$\displaystyle\underset{X\sim
D}{\mathbb{E}}\left[{\exp}\left(2\left({\ell_{\tilde{\gamma}_{1},\tilde{\gamma}_{2}}}\left(v_{i-1};X,Y\right)-\lambda\right)\right)\right]$
$\displaystyle=\underset{X\sim
D}{\mathbb{E}}\left[{\exp}\left(2\tilde{\gamma}_{1}Z_{i}+2\tilde{\gamma}_{2}Z_{i}^{2}-2\lambda\right)\right]$
$\displaystyle\overset{\left(1\right)}{\leq}e^{-2\lambda}\sqrt{\underset{X\sim
D}{\mathbb{E}}\left[{\exp}\left(4\tilde{\gamma}_{1}Z_{i}\right)\right]\cdot\underset{X\sim
D}{\mathbb{E}}\left[{\exp}\left(4\tilde{\gamma}_{2}Z_{i}^{2}\right)\right]}$
$\displaystyle\overset{\left(2\right)}{\leq}e^{-2\lambda}\sqrt{e^{16\tilde{\gamma}_{1}\sqrt{kd}\sigma+128\tilde{\gamma}_{1}^{2}kd\sigma^{2}}\frac{1}{1-40e\tilde{\gamma}_{2}kd\sigma^{2}}}$
$\displaystyle\overset{\left(3\right)}{\leq}e^{64\tilde{\gamma}_{1}^{2}kd\sigma^{2}}\frac{1}{\sqrt{1-5e\tilde{\gamma}_{1}^{2}kd\sigma^{2}}}$
$\displaystyle\overset{\left(4\right)}{\leq}\left(1+128\tilde{\gamma}_{1}^{2}kd\sigma^{2}\right)\left(1+5e\tilde{\gamma}_{1}^{2}kd\sigma^{2}\right)$
$\displaystyle\overset{\left(5\right)}{\leq}1+\left(128+10e\right)\tilde{\gamma}_{1}^{2}kd\sigma^{2}$
$\displaystyle\overset{\left(6\right)}{\leq}1+156\gamma_{1}^{2}kd\sigma^{2}{\ln}\left(\frac{1}{\delta^{\prime}}\right),$

where (1) results from Cauchy-Schwarz inequality, (2) from Lemma E.3, (3) from
the definition of $\lambda$ and the bound on $\gamma_{2}$ and
$\delta^{\prime}$, (4) from the inequalities $e^{x}\leq 1+2x$ and
$\frac{1}{\sqrt{1-x}}\leq 1+x$ for $x<1$, (5) from the fact that
$\left(1+x\right)\left(1+y\right)\leq 1+x+2y$ for any $0\leq x,y\leq 1$ bound
on $\delta^{\prime}$ and (6) from the definition of $\tilde{\gamma}_{1}$.

∎

###### Proof of Theorem 5.4.

From Lemma 3.2, $M$ is ${\varphi}\left(\cdot\right)$-Sample Accurate for
${\varphi}\left(\alpha\right)=ke^{-\frac{\alpha}{\eta}}$ and
${\varphi^{\prime}}\left(\cdot\right)$-Posterior Accurate for
${\varphi^{\prime}}\left(\alpha\right)=ke^{1-\frac{\alpha}{\eta}}$. From Lemma
4.7, it is $\left(\frac{1}{n\eta},0,0\right)$-LBI. Invoking Theorem 5.1 and
plugging in these guarantees completes the proof of the first part, and using
Theorem 5.3 completes the second. ∎

###### Proof of Corollary 5.5.

Using the definition of $\eta$ and the bound on $n$ we get in the bounded case

$\epsilon=\frac{2\sigma^{2}}{n\eta}\sqrt{3k\cdot{\ln}\left(\frac{1}{\delta^{\prime}}\right)}\overset{\left(1\right)}{=}\frac{4\sigma^{2}}{n\alpha}\sqrt{3k}{\ln^{\frac{3}{2}}}\left(\frac{1}{\delta^{\prime}}\right)\overset{\left(2\right)}{\leq}\frac{\alpha}{4}$

and in the sub-Gaussian case,

$\epsilon=\frac{29\sigma^{2}}{n\eta}\sqrt{k\cdot{\ln}\left(\frac{1}{\delta^{\prime}}\right)}\overset{\left(1\right)}{=}\frac{38\sigma^{2}}{n\alpha}\sqrt{k}{\ln^{\frac{3}{2}}}\left(\frac{1}{\delta^{\prime}}\right)\overset{\left(2\right)}{\leq}\frac{\alpha}{4},$

where (1) results from the definition of $\eta$ and (2) from the bound on $n$.

Setting
$\delta^{\prime}=\frac{\min\left\\{\sigma,\alpha\right\\}\beta^{2}}{k\sigma}$
(we use $\delta^{\prime}$ to denote the parameter used in Theorem 5.4) and
$c=2\beta\min\left\\{\sigma,\alpha\right\\}$ we get

$\frac{\sigma\delta^{\prime}}{c}=\frac{\sigma\frac{\min\left\\{\sigma,\alpha\right\\}\beta^{2}}{k\sigma}}{2\beta\min\left\\{\sigma,\alpha\right\\}}=\frac{\beta}{2k}\leq\frac{\beta}{2}$

and

$\displaystyle-\frac{\alpha-\epsilon-c}{\eta}$
$\displaystyle=\frac{\epsilon+c-\alpha}{\eta}$
$\displaystyle\overset{\left(1\right)}{\leq}\frac{\frac{\alpha}{4}+2\beta\min\left\\{\sigma,\alpha\right\\}-\alpha}{\frac{\alpha}{2{\ln}\left(\frac{1}{\delta^{\prime}}\right)}}$
$\displaystyle\overset{\left(2\right)}{\leq}2{\ln}\left(\frac{1}{\delta^{\prime}}\right)\left(\frac{1}{4}+\frac{1}{4}-1\right)$
$\displaystyle={\ln}\left(\delta^{\prime}\right),$

where (1) results from the previous inequality and (2) from the bounds on
$\beta$. Therefore,

$ke^{1-\frac{\alpha-\epsilon-c}{\eta}}\overset{\left(1\right)}{\leq}ke\cdot{\exp}\left({\ln}\left(\delta^{\prime}\right)\right)=ke\delta^{\prime}=ke\frac{\min\left\\{\sigma,\alpha\right\\}\beta^{2}}{k\sigma}\overset{\left(2\right)}{\leq}\frac{\beta}{2},$

where (1) is the previous inequality and (2) results from the bound on
$\beta$.

Using the bound on $n$, we can bound $\delta^{\prime}$ from below and complete
the proof using Theorem 5.4 and the two bounds we proved. ∎

###### Proof of Theorem 5.6.

From Lemma 3.3, $M$ is ${\varphi}\left(\cdot\right)$-Sample Accurate for
${\varphi}\left(\alpha\right)=\frac{k}{2}{\text{erfc}}\left(\frac{\alpha}{\sqrt{2}\eta}\right)$
and ${\varphi^{\prime}}\left(\cdot\right)$-Posterior Accurate for
${\varphi^{\prime}}\left(\alpha\right)=\frac{k\alpha}{\sqrt{2\pi}\eta}e^{1-\frac{\alpha^{2}}{2\eta^{2}}}$.
From Lemma 4.8, it is
$\left(\frac{1}{n\eta}\sqrt{2{\ln}\left(\frac{1}{\delta}\right)},\frac{1}{2n^{2}\eta^{2}},\delta\right)$-LBI.
Invoking Theorem 5.1 and plugging in these guarantees completes the proof of
the first part, and using Theorem 5.3 completes the second. ∎

###### Proof of Corollary 5.7.

Using the definition of $\eta$ and the bound on $n$ we get in the bounded case

$\epsilon=\frac{2\sigma^{2}}{n\eta}\sqrt{6k\cdot{\ln}\left(\frac{1}{\delta^{\prime}}\right)}\overset{\left(1\right)}{=}\frac{12\sigma^{2}}{n\alpha}\sqrt{3k}{\ln^{\frac{3}{2}}}\left(\frac{1}{\delta^{\prime}}\right)\overset{\left(2\right)}{\leq}\frac{\alpha}{4}$

and in the sub-Gaussian case,

$\epsilon=\frac{29\sigma^{2}}{n\eta}\sqrt{2k\cdot{\ln}\left(\frac{1}{\delta^{\prime}}\right)}\overset{\left(1\right)}{=}\frac{114\sigma^{2}}{n\alpha}\sqrt{k}{\ln^{\frac{3}{2}}}\left(\frac{1}{\delta^{\prime}}\right)\overset{\left(2\right)}{\leq}\frac{\alpha}{4},$

where (1) results from the definition of $\eta$ and (2) from the bound on $n$.

Setting
$\delta=\delta^{\prime}=\frac{\min\left\\{\sigma,\alpha\right\\}\beta^{2}}{\left(k+1\right)\sigma}$
(we use $\delta^{\prime}$ to denote the parameter used in Theorem 5.4),
$c=2\beta\min\left\\{\sigma,\alpha\right\\}$ we get

$\frac{\sigma\left(k\delta+\delta^{\prime}\right)}{c}=\frac{\sigma\left(k+1\right)\frac{\min\left\\{\sigma,\alpha\right\\}\beta^{2}}{\left(k+1\right)\sigma}}{2\beta\min\left\\{\sigma,\alpha\right\\}}=\frac{\beta}{2}$

and

$\displaystyle\frac{\alpha-\epsilon-c}{\sqrt{2}\eta}-\frac{1}{2}$
$\displaystyle\overset{\left(1\right)}{\geq}\frac{\alpha-\frac{\alpha}{4}-2\beta\min\left\\{\sigma,\alpha\right\\}}{\sqrt{2}\frac{\alpha}{3\sqrt{2{\ln}\left(\frac{1}{\delta}\right)}}}-\frac{1}{2}$
$\displaystyle\geq
3\sqrt{{\ln}\left(\frac{1}{\delta}\right)}\left(1-\frac{1}{4}-2\beta\right)-\frac{1}{2}$
$\displaystyle\overset{\left(2\right)}{\geq}3\sqrt{{\ln}\left(\frac{1}{\delta}\right)}\left(1-\frac{1}{4}-\frac{1}{4}\right)-\frac{1}{2}$
$\displaystyle\overset{\left(3\right)}{\geq}\sqrt{{\ln}\left(\frac{1}{\delta}\right)},$

where (1) results from the definition of $\eta$ and $c$ and the bound on
$\epsilon$, (2) from the bounds on $n$ and $\beta$ and (3) from the fact that
$\delta\leq\frac{1}{e}$.

Therefore,

$\displaystyle\frac{k\left(\alpha-\epsilon-c\right)}{\sqrt{2\pi}\eta}{\exp}\left(-\frac{\left(\alpha-\epsilon-c\right)^{2}-2\eta^{2}}{2\eta^{2}}\right)$
$\displaystyle\overset{\left(1\right)}{\leq}\frac{e^{\frac{5}{4}}k}{\sqrt{\pi}}{\exp}\left(-\left(\frac{\alpha-\epsilon-c}{\sqrt{2}\eta}-\frac{1}{2}\right)^{2}\right)$
$\displaystyle\overset{\left(2\right)}{\leq}\frac{e^{\frac{5}{4}}k}{\sqrt{\pi}}\delta$
$\displaystyle=\frac{e^{\frac{5}{4}}k}{\sqrt{\pi}}\cdot\frac{\min\left\\{\sigma,\alpha\right\\}\beta^{2}}{\left(k+1\right)\sigma}$
$\displaystyle\overset{\left(3\right)}{\leq}\frac{\beta}{2}$

where (1) results from the inequality $xe^{-x^{2}}\leq
e^{-\left(x-\frac{1}{2}\right)^{2}+\frac{1}{4}}$, (2) is the previous
inequality and (3) results from the bound on $\beta$.

Using the bound on $n$, we can bound $\delta^{\prime}$ from below and complete
the proof using Theorem 5.6 and the two bounds we proved.∎

##  Appendix F Relationship to LSS [SL19]

In this section, we show how the main results of [SL19] can be rederived in
the present framework with improved constants.

Consider the quantity
$\left\lVert{q}\left(D^{v}\right)-{q}\left(D\right)\right\rVert$ bounded by
the Bayes stability definition (Definition 3.4). Given a $\Delta$-bounded
linear query $q$, then
$\left\lVert{q}\left(D^{v}\right)-{q}\left(D\right)\right\rVert\leq\Delta\cdot{\mathbf{D}_{\text{TV}}}\left(D\|D^{v}\right)$,
where $\mathbf{D}_{\text{TV}}$ is the Total Variation Distance (Definition
B.1). Equality is achieved by
${q_{v}}\left(x\right)\coloneqq\begin{cases}\Delta&{D}\left(v\,|\,x\right)>{D}\left(v\right)\\\
0&{D}\left(v\,|\,x\right)\leq{D}\left(v\right)\end{cases}$. This is captured
by the _Stability Loss_ measure of [SL19], reproduced below as Definition F.1.
Our Covariance Stability Lemma (Lemma 3.6) thus also provides an alternative
proof (Corollary F.4) of the generalization capabilities of _Local Statistical
Stability_ (Definition F.2), as we see below.

######  Definition F.1 (Stability loss [SL19]).

Given an analyst $A$ and a view $v$, the _stability loss_
${\ell}\left(v\right)$ is defined as the Total variation Distance between the
prior distribution over $\mathcal{X}$ and the posterior induced by $v$. That
is,
${\ell_{D_{\mathcal{X}^{n}}}^{q}}\left(r\right)\coloneqq{\mathbf{D}_{\text{TV}}}\left(D,D^{v}\right)$.
Similarly, we define the stability loss ${\ell}\left(\mathbf{v}\right)$ of a
set of views $\mathbf{v}\subseteq\mathcal{V}$ as
${\ell}\left(\mathbf{v}\right)\coloneqq\sum_{v\in\mathbf{v}}\frac{{D}\left(v\right)}{{D}\left(\mathbf{v}\right)}{\ell}\left(v\right)$.

######  Definition F.2 (Local Statistical Stability [SL19]).

Given $0\leq\epsilon,\delta\leq 1$ and an analyst $A$, a mechanism $M$ will be
called _$\left(\epsilon,\delta\right)$ -Local-Statistically Stable with
respect to $A$_ (or _LSS_ , for short) if for any
$\mathbf{v}\subseteq\mathcal{V}$,
${D}\left(\mathbf{v}\right)\cdot\left({\ell}\left(\mathbf{v}\right)-\epsilon\right)\leq\delta$.

######  Theorem F.3 (LSS Implies Bayes Stability).

Given $\epsilon,\delta,\sigma>0$ and an analyst $A$ issuing linear queries
with standard deviation bounded by $\sigma$, if a mechanism $M$ is
$\left(\epsilon,\delta\right)$-LSS with respect to $A$, then it is
$\left(\sigma\left(\epsilon+c\right),\frac{\delta}{c}\right)$-Bayes Stable for
any $c>0$.

###### Proof.

For any $v\in\mathcal{V}$, $q\in\mathcal{Q}$,

$\displaystyle\left\lVert\underset{X\sim
D}{\text{Cov}}\left({q}\left(X\right),{K}\left(X,v\right)\right)\right\rVert$
$\displaystyle=\left\lVert\underset{X\sim
D}{\mathbb{E}}\left[\left({q}\left(X\right)-{q}\left(D\right)\right)\left({K}\left(X,v\right)-1\right)\right]\right\rVert$
$\displaystyle=\left\lVert\sum_{x\sim