Typical Stability

arXiv:1604.03336v2 [cs.LG] 19 Sep 2016

Raef Bassily∗

Yoav Freund†

Abstract
In this paper, we introduce a notion of algorithmic stability called typical stability. When our
goal is to release real-valued queries (statistics) computed over a dataset, this notion does not
require the queries to be of bounded sensitivity – a condition that is generally assumed under
differential privacy [DMNS06, Dwo06] when used as a notion of algorithmic stability [DFH+ 15b,
DFH+ 15c, BNS+ 16] – nor does it require the samples in the dataset to be independent – a
condition that is usually assumed when generalization-error guarantees are sought. Instead,
typical stability requires the output of the query, when computed on a dataset drawn from
the underlying distribution, to be concentrated around its expected value with respect to that
distribution. Typical stability can also be motivated as an alternative definition for database
privacy. Like differential privacy, this notion enjoys several important properties including
robustness to post-processing and adaptive composition. However, privacy is guaranteed only
for a given family of distributions over the dataset.
We also discuss the implications of typical stability on the generalization error (i.e., the
difference between the value of the query computed on the dataset and the expected value of
the query with respect to the true data distribution). We show that typical stability can control
generalization error in adaptive data analysis even when the samples in the dataset are not
necessarily independent and when queries to be computed are not necessarily of boundedsensitivity as long as the results of the queries over the dataset (i.e., the computed statistics)
follow a distribution with a “light” tail. Examples of such queries include, but not limited to,
subgaussian and subexponential queries.
We discuss the composition guarantees of typical stability and prove composition theorems
that characterize the degradation of the parameters of typical stability under k-fold adaptive
composition. We also give simple noise-addition algorithms that achieve this notion. These
algorithms are similar to their differentially private counterparts, however, the added noise is
calibrated differently.

∗ University of California San Diego, Center for Information Theory and Applications and Department of Computer
Science and Engineering. rbassily@ucsd.edu
† University of California San Diego, Department of Computer Science and Engineering. yfreund@eng.ucsd.edu

1

Introduction

Differential privacy [DMNS06, Dwo06] is a strong notion of algorithmic stability that was originally
introduced to ensure data privacy. This notion has also been recently re-purposed to control
generalization error and ensure statistical validity in adaptive scenarios of data analysis [DFH+ 15b,
DFH+ 15a, DFH+ 15c, BNS+ 16]. Depsite of its power, the use of differential privacy to control
generalization error of real-valued queries (i.e., real-valued statistics) in the aforementioned works
entails two main assumptions. The first assumption is that such queries are of bounded sensitivity,
that is, the maximum change in the value of the query’s output due to a change in any single
data point in the dataset has to be bounded. The second assumption is that the samples in the
dataset are i.i.d., which is a more standard assumption in the literature when generalization error
guarantees are discussed.
Typical Stability. In this work, we introduce a notion of algorithmic stability called typical
stability that does not require the queries to be of bounded-sensitivity and does not assume that the
samples in the dataset are i.i.d., but instead requires that the output of each query when evaluated
on a dataset drawn from the underlying distribution (i.e., the value of the computed statistic)
to be “well concentrated” around its true mean with respect to that distribution. This notion
introduces a new algorithmic-stability approach to controlling generalization error in adaptive
data analysis especially in the settings where queries are not necessarily of bounded sensitivity and the
data set entries are not necessarily independent. Moreover, typical stability can also be motivated as
an alternative definition for privacy. Like differential privacy, this notion enjoys several important
properties including robustness to post-processing and adaptive composition. However, privacy is
guaranteed only for some given family of distributions over the dataset. Our attention in this paper
will be devoted to the properties of this notion, its implication on generalization error, and its
achievability via simple algorithms. However, we will not discuss any privacy-relared applications
of this notion in this paper.
As it is the case with differential privacy, there are two versions of the definition of typical
stability: pure and approximate typical stability. In general, typical stability is defined via three
parameters: η, τ, and ν. When τ = 0, we call it pure typical stability, otherwise, we call it
approximate typical stability. We will give here an intuitive description of this notion (Formal
definitions are given in Section 2.1). Consider a randomized algorithm A that takes as input a
dataset drawn from some arbitrary distribution P over the dataset domain X n . We say that A is
(η, τ, ν)-typically stable algorithm if there is a subset S ⊆ X n whose measure with respect to P is
at least 1 − ν such that for any pair of datasets x, y ∈ S, the distribution of A(x) is “close” to that
of A(y). Such closeness is determined by the two parameters η and τ that play similar roles to
that of ε and δ in differential privacy. So, intutively, S is a set of “typical” datasets, and roughly
speaking, we require the distributions of the output of A on any pair of typical datasets to be
“indistinguishable”. The intuition is that the output of A should “conceal” the identity of the
dataset inside the typicality set S, that is, the output should not reveal which of the typical datasets
is the true input of A. However, the output should still reveal information about S as a whole since
such information depends on the underlying distribution P rather than the sample. In this sense,
typical stability ensures that the whatever is revealed by the algorithm is essentially information
shared by all typical datasets.
Concentrated Queries. In this work, we consider releasing answers to real-valued queries under
typical stability. As mentioned earlier, we consider scenarios where the answers of such queries

are concentrated around their expectation with respect to the underlying distribution on the
input dataset. We say that a class Qγn (P) of real-valued queries on datasets from X n (i.e., datasets
of n elements from X ) is γn -concentrated with respect to distribution P over X n if there is a
non-negative, non-decreasing function γn : R+ → R+ (that possibly depends on n) such that for
every query q ∈ Qγn (P), with probability at least 1 − e−γn (α) over the choice of a dataset X ∼ P,
the generalization error for q is bounded by α, where generalization error refers to the quantity
q(X) − E [q(Y)] . For different settings of γn , we obtain, as special cases, query classes such as the
Y∼P

class of subgaussian queries and the class of sub-exponential queries which were studied in [RZ15],
and the more special class of jointly Gaussian queries that was studied in both [RZ15, WLF16].
Properties of Typical Stability. We show that typical stability is closed under post-processing.
We also show that typical stability is robust to both non-adaptive and adaptive composition (albeit
with different guarantees for each case). As the case of adaptive composition is more complicated
and requires delicate analysis, we devote Section 4 to our results for this case. In particular, we
prove a composition theorem that gives a characterization of the degradation of the parameters of
typical stability when a sequence of arbitrarily and adaptively chosen typically stable algorithms1
operating on the same dataset are composed together.
Typical Stability and Generalization. We also show that typical stability implies generalization
by first proving a “near-independence” lemma for typically stable algorithms. In particular, we
show that with high probability the generalization error for any γn -concentrated query is small as
long as the query is generated during an interaction with a typically stable algorithm. In other
words, any γn -concentrated query generated via a typically stable interaction with the dataset does
not overfit to the same dataset. As a consequence, typical stability is a rigorous approach to statistcal
validity that gives non-trivial guarantees in adaptive settings where queries are not of bounded sensitivity
and the data set entries are not independent.
Achieving Typical Stability via Noise-Adding Mechanisms. We give simple noise-addition
typically stable mechanisms for answering real-valued queries. Our mechanisms are based on
adding Laplace and Gaussian noise to the query output to achieve pure and approximate typical
stability, respectively. These mechanisms are similar to the differentially private Lalplace and
Gaussian mechanisms [DMNS06, DKM+ 06], however, the added noise is calibrated differently in our
case. In particular, the noise is added based on how “well” the query output is concentrated around
its expectation, that is, the noise is calibrated to the confidence interval of the query’s answer over
the given dataset. More formally, let P be an arbitratry distribution on X n . For a query q : X n → R,


if we have P q(X) − E [q(Y )] > α < ν, then, our mechanisms would add noise (Laplace for
X∼P

Y ∼P

pure, and Gaussian for approximate typical stability) whose standard deviation proportional to α.
Applications in Adaptive Data Analysis. Our results for this notion have immediate implications on statistical accuracy in adaptive data analysis especially in scenarios where the data samples
are not independent and the statistics to be computed are not necessarily of bounded sensitivity. In
particular, the established properties of typical stability (mainly its closure under post-processing
and adaptive composition, and its generalization guarantees (Sections 3 and 4)) together with the
1 That is, the choice of each typically stable algorithm possibly depends on all previous outputs and choices of the

previous algorithms.

simple mechanisms achieving it and their accuracy guarantees (Section 5) provide a systematic
approach to answering any sequence of adaptively chosen “concentrated queries” over a given
dataset while ensuring statistical accuracy of all the released answers (with high probability). We
note that in scenarios where the samples in the dataset are not independent, a simple approach
such as sample splitting2 may not always give statistically accurate answers when the queries are
adaptive. Our approach gives rigorous guarantees on generalization error and statistical accuracy
in this type of scenarios as long as the computed statistics are reasonably concentrated around
their expected value. Examples of such scenarios include those that arise in structured prediction
where the dataset entries can be correlated (e.g., nodes of a graph), yet the computed statistics can
be well concentrated around their expected values (for example, see [LHTG13]).
Other Related Work Typical stability is a generalization of the notion of perfect generalization
that was introduced very recently and independently by Cummings et al. [CLN+ 26] where it was
also studied in the context of generalization in PAC-learning models. Perfect generalization is
a special case of typical stability when the dataset is i.i.d. . Hence, our positive results for the
notion of typical stability apply directly to perfect generalization as well. In particular, our positive
results on the adaptive composition of typically stable algorithms in Section 4 imply the same for
perfectly generalizing algorithms.
Our notion also appears to be similar to the notion of distributional privacy that was introduced and
briefly studied in [BLR08] as a privacy concept. However, it is imortant to note that typical stability
is different from the notion of distributional privacy. In particular, in distributional privacy,
the samples in the dataset are assumed to be drawn without replacement from the underlying
population whereas typical stability does not impose this requirement.
Notation. We will use the symbol X to denote a generic data domain. We will consider data
sets of n ∈ N samples from X . We will often use the symbol P to denote an arbitrary distribution
over X n . That is, P will in general denote the joint distribution of the samples in the data set. We
will use upper-case bold symbols such as X to denote the dataset, that is, X denotes the random
sequence (X1 , . . . , Xn ) drawn from P. Unless stated otherwise, we will use upper-case letters to
denote random variables and lower-case letters to denote realizations of random variables. In
general, a data analysis algorithm A : X n → Z is an algorithm that takes as input a dataset from
X n , performs a certain task based on the input dataset, e.g., statistical estimation or learning, and
returns some output from the set Z (e.g., a parameter estimate, or a classifier). We allow any such
algorithm to be randomized, i.e., to have access to its own set random coins, and thus, the output
of such algorithm, denoted generically as Z, will be a random variable whose randomness depends
on both the distribution P of the input dataset and the random coins of the algorithm.

2

Definitions

Before we formally define typical stability, we first state a standard definition for the notion
(η, τ)-indistinguishability between distributions of random variables.
Definition 2.1 ((η, τ)-indstinguishability). Random variables X, Y with the same range are said to
have (η, τ)-indistinguishable distributions, denoted as X ≈η,τ Y , if for all measurable subsets O of
their range, we have
P [X ∈ O] ≤ eη P [Y ∈ O] + τ

and

P [Y ∈ O] ≤ eη P [X ∈ O] + τ.

2 I.e., splitting the dataset randomly into multiple disjoint parts, and using each part to answer a single query.

2.1

Typical Stability

Definition 2.2 (Typical Stability). Let A : X n → Z be a randomized algorithm. We say that A is
(η, τ, ν)-typically stable with respect to a family P of distributions over X n if for any distribution
P ∈ P there exists an oracle W that takes P as input and outputs an element in Z, such that with
probability at least 1 − ν over the choice X ∼ P, we have A(X) ≈η,τ W (P).
When τ = 0, the notion will usually be referred to as (η, ν)-pure typical stability with respect to
P (as opposed to approximate typical stability when τ > 0.)
We note that the definition above is almost the same as perfect generalization [CLN+ 26] except
that it does not require the samples in the dataset to be i.i.d. .
Another slightly weaker version of the above definition can be phrased as follows.
Definition 2.3. Let A : X n → Z be a randomized algorithm. We say that A is (η, τ, ν)-typically
stable with respect to a family P of distributions over X n if for any distribution P ∈ P , for any two
independent X, Y ∼ P, with probability at least 1 − ν over the choice of X, Y we have A(X) ≈η,τ A(Y).
It is not hard to see that (η, τ, ν)-typical stability according to Definition 2.2 implies (2η, 3τ, 2ν)typical stability according to Definition 2.3.

2.2

Queries

We define the main class of queries (statistics on the dataset) that will be considered in this paper.
We show that several standard classes of statistics are special cases of this class.
Definition 2.4 (γn -Concentrated Queries). For any fixed dataset size n ∈ N, let γn : R+ → R+ be a
non-negative, non-decreasing function (possibly depends on n). We define Qγn (P) as the class of all
real-valued queries defined on X n that when computed on a dataset drawn from the distribution P
yields an output that is within distance α from its expected value with respect to P with probability
at least 1 − e−γn (α) , for every α > 0. Formally,




n
−γn (α)
Qγn (P) , q : X → R s.t. P q(X) − E [q(Y)] > α < e
for all α > 0 .
X∼P

Y∼P

The following are some special cases of γn -concentrated queries:
• ∆-Sensitive Queries: We let Q∆ denote the class of ∆-sensitive queries on X n . That is,

Q∆ = q : X n → R s.t. ∀x, x0 ∈ X n with dH (x, x0 ) ≤ 1, |q(x) − q(x0 )| ≤ ∆ ,
where dH (·, ·) is the Hamming distance.
2

2α
For all functions γn satisfying γn (α) ≤ n∆
2 , α > 0, from McDiarmid’s inequality, it follows
T
that Q∆ ⊆
Qγn (P) where P π is the class of all product distributions over X n . When ∆ is
P∈P π

small, e.g., ∆ = 1/n, this class is usually referred to as low-sensitivity queries (or, Lipschitz
statistics).
• σ -subgaussian Queries: A query q : X n → R is said to be σ -subgaussian with respect to a
distribution P over X n if we have


1 2 2
E et (q(X)−µq ) ≤ e 2 t σ , t ∈ R,
X∼P

where µq = E [q(Y)]. We denote the class of σ -subgaussian queries with respect to P by
Y∼P

QσG (P).

For all functions γn satisfying γn (α) ≤
2σ
any P ∈ P π , Q∆ ⊂ QσG (P) for ∆ ≤ √
.
n

α2
,α
2σ 2

> 0, we have QσG (P) ⊆ Qγn (P). Note also that for

• (σ , b)-subexponential Queries: A query q : X n → R is said to be (σ , b)-subexponential with
respect to a distribution P over X n if we have


1 2 2
t (q(X)−µq )
E e
≤ e 2 t σ , |t| ≤ 1/b,
X∼P

where µq = E [q(Y)]. We denote the class of (σ , b)-subexponential queries with respect to P
Exp

Y∼P

by Qσ ,b (P).
For all functions γn satisfying γn (α) ≤ min



α2 σ 2
,
2σ 2 2b2



Exp

, α > 0, we have Qσ ,b (P) ⊆ Qγn (P).

Note: We note that there are γn -concentrated queries with respect to distributions that are not
product distributions (as in structured prediction where, for example, the dataset can be a graph
with correlated nodes, nevertheless, for some types of statistics and under certain assumptions,
one can still show that the computed statistics are concentrated in the sense of Definition 2.4 (e.g.,
see [LHTG13, Section 4, Theorem 1] and the references therein).
We also note that there are σ -subgaussian (or, (σ , b)-subexponential) queries that are not necessarily ∆-sensitive (not even for arbitrary large ∆), for example, the class of queries that correspond
to sums of independent Gaussian random variables, or more generally, independent random
variables with bounded moments (but not necessarily bounded support) where concentration
inequalities such as Bernstein’s can be applied. On the other√hand, as indicated above ∆-sensitive
queries is a subclass of σ -subgaussian queries for ∆ ≤ 2σ / n. Hence, the class of subgaussian
queries (and more generally the class of γn -concentrated queries) is strictly larger than the class of
low-sensitivity queries.

3

Basic Properties of Typical Stability

In this section, we discuss some useful properties of typical stability. Together with our results
in the following section (Section 4) on the adaptive composition guarantees of typically stable
algorithms, these properties play essential role in establishing the guarantees of typical stability
on the generalization error in adaptive data analysis.

3.1

Closure under post-processing and non-adaptive composition

First, we discuss some useful properties of typically stable algorithms. In particular, we show
that this notion is closed under post-processing and under non-adaptive composition where the
stability parameters degrade linearly with the number of algorithms to be composed. We defer the
discussion of the adaptive composition of typically stable algorithms to Section 4.
Lemma 3.1 (Postprocessing). Let A : X n → Z be an (η, τ, ν)-typically stable algorithm with respect
to a family of distributions P over X n . Let B : Z n → U be a randomized algorithm. Let C : X n → U be
defined as C(x) = B(A(x)). Then, C is (η, τ, ν)-typically stable algorithm with respect to P .

Proof. The proof follows from a straightforward manipulation where the probability of any measurable subset O of the outcomes of C is expressed as a convex combination of probabilities of a
collection of sets over the outcomes of A.
The next theorem characterizes the degradation in privacy parameters under non-adaptive
composition of typically stable algorithms.
Lemma 3.2 (Non-Adaptive Composition). Let Ai : X n → Zi , i ∈ [k] be any collection of (η, τ, ν)typically stable algorithms with respect to a common family P of distributions over X n where all Ai , i ∈ [k]
have independent random coins. Define C : X n → Z1 ×. . .×Zk as C(x) = (A1 (x), . . . , Ak (x)) , x ∈ X n . Then,
C is (kη, kτ, kν)-typically stable.
Proof. The proof follows from combining the union bound with a standard technique for bounding
the joint probability of the output of C similar to that used in proving basic composition theorem
for (ε, δ)-differentially private algorithms [DKM+ 06, DR14].

3.2

Typical stability and the Near-Independence property

The following lemma describes an important implication of typical stability. It shows the impact
of typical stability on the joint distribution of the input and output of a typically stable algorithm.
Let P be a family of distributions over X n . Let P be a distribution in P and X ∼ P. Let A : X n → Z
be an (η, τ, ν)-typically stable algorithm with respect to P . Lemma 3.3 below states that the joint
probability measure of (X, A(X)) is “close” to the product measure of X and A(X) (i.e., the measure
induced by the product of the marginal distributions of X and A(X)). A statement of the same spirit
is known for ε-differentially private algorithms via a connection to the notion of max-information
[DFH+ 15a] (and more recently for (ε, δ)-differentially private algorithms when their inputs are
drawn from a product distribution [RRST16]).
Lemma 3.3 (Near-Independence Lemma of Typically Stable Algorithms). Let P be a family of
distributions over X n , and A : X n → Z be an (η, τ, ν)-typically stable algorithm with respect to P . Let
P ∈ P , and X, Y ∼ P be two independent random variables. Let S ⊆ X n be a set that satisfies the condition
of typical stability in Definition 2.3, that is, P [X, Y ∈ S] ≥ 1 − ν and for every x, y ∈ S, we have
X,Y∼P

A(x) ≈η,τ A(y). Then, for every measurable O ⊆ X n × Z, we have
h
i
h
i
P (X, A(X)) ∈ O X ∈ S ≤ eη P (X, A(Y)) ∈ O X, Y ∈ S + τ

(1)

Moreover, if η < 1 and ν < 1/10, then (1) implies
P [(X, A(X)) ∈ O] ≤ eη P [(X, A(Y)) ∈ O] + τ + 5ν

(2)

Proof. Fix O ⊆ X n × Z n . For every x ∈ X n , let Ux = {z ∈ Z n : (x, z) ∈ O}. Now, observe3
h
i X h
i h
i
P (X, A(X)) ∈ O X ∈ S =
P A(x) ∈ Ux X = x, X ∈ S P X = x X ∈ S
x∈X n

≤

X

h
i
eη P [A(y) ∈ Ux ] P X = x X ∈ S + τ

x∈X n
3 For continuous measures, we will regard the probabilities below as density functions and sums are replaced with

Lebesgue integrals with respect to the appropriate probability measures.

for every y ∈ S. The last inequality follows from the typical stability of A. Now, by taking the
expectation
of the
h
i two sides of the above inequality with respect to the conditional measure
P Y = · Y ∈ S , we get (1).
·←y

Now, from (1) and by straightforward manipulation, we have
h
i
P [(X, A(X)) ∈ O] ≤ eη P (X, A(Y)) ∈ O Y ∈ S + τ + ν
≤ eη

P [(X, A(Y)) ∈ O]
P [Y ∈ S]

+τ +ν

≤ eη P [(X, A(Y)) ∈ O] + τ + 5ν
where the last inequality follows from the fact that P [Y ∈ S] ≥ 1 − ν, and that η < 1, ν < 1/10.

3.3

Generalization via Typical Stability

We discuss here an important implication of Lemma 3.3. Let P be a distribution over X n . The next
theorem states that if a query in Qγn (P) is generated as a result of an (η, τ, ν = e−γn (α) )-typically
stable algorithm with input dataset X ∼ P, then the generlaization error for that query on the
dataset will be bounded by α with high probability.
Theorem 3.4 (Generalization via Typical Stability). Let P be any distribution on X n . Let A : X n → Qγn (P)
be an (η, τ, ν)-typically stable algorithm with respect to P that outputs a γn -concentrated query in Qγn (P).
n
o
Let qX denote the output of A(X). Let α = inf r ∈ R+ : e−γn (α) ≤ ν . Then, we have


P qX (X) − E [qX (T)] > α ≤ (eη + 5) ν + τ
T∼P

In particular, if η = O(1), then


P qX (X) − E [qX (T)] > α ≤ O (max (ν, τ))
T∼P

Proof. The proof follows from Lemma 3.3. In particular, if we define the event O in Lemma 3.3 as


O = (x, qx ) : qx (x) − E [qx (T)] > α ,
T∼P

then by (2) in Lemma 3.3, the definition of α, and the fact that the output of A is γn -concentrated
query with respect to P, we get the desired result.

4

Adaptive Composition of Typically Stable Algorithms

In this section, we discuss an important property of typical stability. We give a characterization
of how fast typical stability degrades as a result of adaptively composing (η, τ, ν)-typically stable
algorithms.
Before we state our composition results, we first describe the adaptive composition model.
Let P be a family of distribrutions over X n . We consider an arbitrary sequence of k adaptively
chosen algorithms Ai : X n × Z1 × . . . × Zi−1 → Zi , i ∈ [k] such that for every i ∈ [k] and every
zi−1 , (z1 , . . . , zi−1 ) ∈ Z1 × . . . × Zi−1 , the algorithm Ai (·, zi−1 ) is (η, τ, ν)-typically stable with respect
to P . We consider the k-fold adaptive composition mechanism Mk outlined in Algorithm 1.

Algorithm 1 Mk : X n → Z1 ×. . .×Zk : A k-fold adaptive composition mechanism for typically stable
algorithms
Require: A dataset x ∈ X n and a composition adversary Adv.
1: Initialize z0 = ⊥, i.e., empty string.
2: for i = 1, . . . , k do
3:
Adv chooses an (η, τ, ν)-typically stable algorithm (w.r.t. P ) Ai : X n × Z1 × . . . × Zi−1 → Zi .
4:
Adv receives zi = Ai (x, zi−1 ).
5: end for
6: return zk = (z1 , . . . , zk ).
Definition 4.1. We say that the class of (η, τ, ν)-typically stable mechanisms w.r.t. a family of
distributions P satisfies (η 0 , τ 0 , ν 0 )-typical stability w.r.t. P under k-fold adaptive composition if
mechanism Mk (Algorithm 1) is (η 0 , τ 0 , ν 0 )-typically stable w.r.t. P .

4.1

Composition of pure typically stable algorithms

In this section, we state and prove our composition theorem for pure typically stable algorithms,
i.e., when τ = 0. Whenever we refer to the composition mechanism Mk in this section, it will be
assumed that Mk runs with τ = 0.
Theorem 4.2 (Adaptive Composition of Pure Typically Private Algorithms). Let k ≥ 2. For all
η > 0, 0 ≤ ν < 1, and 0 < τ 0 < 1, the class of (η, 0, ν)-typically stable algorithms w.r.t. P satisfies
(η ∗ , τ ∗ , ν ∗ )-typical stability w.r.t. P under k-fold adaptive composition where η ∗ , τ ∗ , and ν ∗ are given by
p
η ∗ = 3 2k log(1/τ 0 )η + 3kη (eη − 1) ,
1/2

k−1
X


eηt ν/η 
τ ∗ = ν ∗ = 5 kτ 0 /η + ν/η +
t=1

q
In particular, for η = O

log(1/τ 0 )
k

!
, the k-fold adaptive composition is

√  
√  
p
p
 √ 
p
p
Õ kη
Õ kη
, O kτ 0 /η + kν/ηe
− typically stable
Õ kη , O kτ 0 /η + kν/ηe

p
where the hidden logarithmic factor in the Õ(·) expressions is ≈ log(1/τ 0 ).
We note here that ν ∗ does not scale linearly with k as one would expect if a simple application
of the union bound would have been used. A straightforward application of the union bound
would not be appropriate in an adaptive setting since, at each step of the k-fold composition,
conditioning on the previous outputs effectively changes the data distribution.
The high-level idea of the proof is as follows. Suppose X ∼ P. Let Zi = (Z1 , . . . , Zi ) denote
the output of Mi (X) and Z̃i = (Z̃1 , . . . , Z̃i ) denote the output of W i (P) = (W1 (P), . . . , Wi (P)) where
Wi (P) is the oracle corresponding to Ai (·, Zi−1 ) as described in Definition 2.2. At each step i
of the composition, we prune the bad set of pairs (X, Zi−1 ) for which the distribution of the
output of Ai (X, Zi−1 ) is not η-indistinguishable from that of Wi (P) (the oracle corresponding to
Ai (·, Zi−1 )). By doing so at each step i = 1, . . . , j, then at step j, we are left with a good set for
which this indistinguishability condition holds for all i ∈ [j]. We then use a standard concentration
inequality (Azuma’s inequality; see Theorem 4.4) to argue that by removing another tiny portion



(of small measure) from that good set, we can ensure that the joint distribution of X, Mj (X) is


ηj -indistinguishable from the joint distribution of X, W j (P) for some ηj that will be determined
shortly (ηj is given by (3) below). We then apply a useful lemma from [KS14] (see Lemma 4.6) to
argue typical stability of Mj . In our proof, in order to bound the measure of the bad set as we go
from one step of the composition to the next, we use induction. Lemma 4.7 serves as the induction
step where we bound the additional “bad” measure we need to prune as we go from step j to step
j + 1. Similar idea of pruning “bad” sets and applying the conditioning lemma of [KS14] appeared in
[RRST16, Proof of Theorem 3.1], albeit in a different context and without involving an induction
argument.
4.1.1

Proof of Theorem 4.2

Fix some P ∈ P . Let X ∼ P. For any integer j ≥ 1, we use Zj = (Z1 , . . . , Zj ) to denote the output
of Mj (X). We will also use Z̃j to denote the output of W j (P). In the sequel, we will assume that
Z0 = Z̃0 = ⊥ with probability 1.
Let
p
ηj = 2j log(1/τ 0 )η + jη (eη − 1) ,
(3)
1/2

j−1


X

 0
(4)
eηt ν/η 
τj = νj = jτ /η + ν/η +


t=1

For any integer i ≥ 1, and any (x, zi ) ∈ X n × Z1 × . . . × Zi , we define

i
 h 
 P Ai x, zi−1 = zi 


fi (x, zi ) = ln 

 P [Wi (P) = zi ] 

(5)

We then define
j

Fj (x, z ) =

j
X

fi (x, zi )

(6)

i=1

and


fˆi (x, zi−1 ) = max fi x, (zi−1 , z)
z∈Zi

where (zi−1 , z) ∈ Z1 × . . . × Zi−1 × Zi . We define the sequence of sets
n
o
Ci = (x, zi−1 ) : fˆi (x, zi−1 ) ≤ η ,

(7)

(8)

and
n
o
Ĉi = (x, zi−1 ) : ∀` ∈ [i] (x, z`−1 ) ∈ C`

(9)

Fix τ 0 > 0. Let ηj be as defined in (3). Now, we define the set of “good inputs and outputs” as
n
o
Gj = (x, zj ) : Fj (x, zj ) ≤ ηj

(10)

h
i
Lemma 4.3. Let j ≥ 1. Suppose there is µ∗ ≥ jν such that P (X, Zj−1 ) ∈ Ĉj ≥ 1 − µ∗ . Then,
h
i
P (X, Zj ) < Gj and (X, Zj−1 ) ∈ Ĉj ≤ τ 0 ,
and hence,

h
i
P (X, Zj ) ∈ Gj ≥ 1 − µ∗ − τ 0 .

Proof. Consider the random variables fi (X, Zi ), i ∈ [j]. Fix i ∈ [j]. Given (x, zi−1 ) ∈ Ĉi , then with
probability 1, we have
max fi (x, zi−1 , ζ) ≤ η,
ζ∈Zi

(11)

h
i
Now, given (x, zi−1 ) ∈ Ĉi , we analyze the conditional expectation E fi (X, Zi ) | x, zi−1 where we
h
i
h
i
use the notation E fi (X, Zi ) | x, zi−1 as a shorthand for E fi (X, Zi ) | X = x, Zi−1 = zi−1 . We note
that this is the conditional KL-divergence between the distributions of the outputs of Ai and Wi
conditioned on (x, zi−1 ). Using a standard bound on this KL-divergence (see [DRV10]4 ) together
with (11), we have
h
i
E fi (X, Zi ) | x, zi−1 ≤ η(eη − 1)
(12)
Now, define
(
i

gi (x, z ) =

fi (x, zi ) for (x, zi−1 ) ∈ Ĉi ;
0
otherwise.

Observe that using (11), we have gi (X, Zi ) ≤ η with probability 1. Moreover, using (12), for all
(x, zi−1 ) ∈ X × Z1 × . . . × Zi−1 , we have
h
i
E gi (X, Zi ) | x, zi−1 ≤ η(eη − 1).
Now, we use the following classical concentration inequality.
Theorem 4.4 (Azuma’s Inequality). Let T1 , . . . , Tj be a sequence of random variables such that for every
i ∈ [j] we have
P [|Ti | ≤ b] = 1
and for every prefix Ti−1 = ti−1 we have
h
i
E Ti | ti−1 ≤ c
then for all u ≥ 0, we have


j
X

p
2


P 
Ti ≥ jc + u jb ≤ e−u /2


i=1

4 [DR16] gives a tighter bound by a factor of 1/2.

Now, let ηj be as defined in (3). Observe that


j
X

h
i


P (X, Zj ) < Gj and (X, Zj−1 ) ∈ Ĉj = P 
fi (X, Zj ) > ηj and (X, Zj−1 ) ∈ Ĉj 


i=1


j
X



= P 
gi (X, Zj ) > ηj  ≤ τ 0


i=1

where the last inequality follows from Theorem 4.4. This together with the premise in the lemma
concludes the proof.
Lemma 4.5. Let j ≥ 1. Suppose the premise q
of Lemmaq4.3 is true, that is, there is µ∗ ≥ jν such that
h
i
µ∗ +τ 0
µ∗ +τ 0
P (X, Zj−1 ) ∈ Ĉj ≥ 1 − µ∗ . Then Mj is (3ηj , 5
η , 5
η )-typically stable.
Proof. Recall the definition of Gj in (10). Observe that for any (x, zj ) ∈ Gj
h
i
P Mj (x) = zj
h
i ≤ e ηj
j
j
P W (P) = z

(13)



where W j (P) = W1 (P), . . . , Wj (P) . Let Z̃j denote the output of W j (P). Define
n
o
G̃j = (x, zj ) : − Fj (x, zj ) ≤ ηj
where Fj (x, zj ) is as defined in (6). Now, for any (x, zj ) ∈ G̃j , we also have
h
i
P W j (P) = zj
h
i ≤ e ηj
P Mj (x) = zj

(14)

Moreover, by the independence of X and Z̃j−1 , using the union bound we get
i
h
P (X, Z̃j−1 ) ∈ Ĉj ≥ 1 − jν
where Ĉj is as defined in (9).
Thus, by swaping the roles of Mj (X) and W j (P) in Lemma 4.3, it follows that
h
i
P (X, Z̃j ) ∈ G̃j ≥ 1 − jν − τ 0 ≥ 1 − µ∗ − τ 0

(15)

Hence, by Lemma 4.3, and using (13)-(15) above, we have




X, Mj (X) ≈ηj , µ∗ +τ 0 X, W j (P)
Now, we use the following useful lemma from [KS14].
Lemma 4.6 (Conditioning Lemma [KS14]). Suppose that (U , V ) ≈,δ (U 0 , V 0 ). Then, for every δ̂ > 0,
the following holds
h
i
2δ
2δ
P U |V =t ≈3,δ̂ U 0 |V 0 =t ≥ 1 −
−
1
−
e−
t∼p(V )
δ̂
where p(V ) denotes the distribution of V .





Now, by replacing the pairs (U , V ) and (U 0 , V 0 ) in Lemma 4.6 with Mj (X), X and W j (P), X ,
respectively, and also replacing , δ with ηj , µ∗ + τ 0 , respectively, we get


2(µ∗ + τ 0 ) 2(µ∗ + τ 0 )
P Mj (X) ≈3ηj , δ̂ W j (P) ≥ 1 −
−
X∼P
1 − e−ηj
δ̂
p
for every δ̂ > 0. We conclude the proof by setting δ̂ = 2 (µ∗ + τ 0 ) η/5 and noting that 1 − e−ηj ≥
1 − e−η ≥ 25 min(η, 1).
The following lemma serves as the induction step in our proof.
Lemma
4.7. Leti j ≥ 1. Suppose the premise of Lemma 4.3 is true, i.e., there exists µ∗ ≥ jν such that
h
P (X, Zj−1 ) ∈ Ĉj ≥ 1 − µ∗ . Then, we have
h
i
P (X, Zj ) ∈ Ĉj+1 ≥ 1 − µ∗ − eηj ν − τ 0
Proof. From the definitions of the sequence of sets Ci , Ĉi , and Gi in (8), (9), and (10), respecitvely,
observe that
h
i
h
i
h
i
P (X, Zj ) < Ĉj+1 =P (X, Zj ) < Cj+1 and (X, Zj−1 ) ∈ Ĉj + P (X, Zj−1 ) < Ĉj
h
i
=P (X, Zj ) < Cj+1 and (X, Zj−1 ) ∈ Ĉj and (X, Zj ) ∈ Gj
h
i
h
i
+ P (X, Zj ) < Cj+1 and (X, Zj−1 ) ∈ Ĉj and (X, Zj ) < Gj + P (X, Zj−1 ) < Ĉj
h
i
h
i
h
i
≤P (X, Zj ) < Cj+1 and (X, Zj ) ∈ Gj + P (X, Zj−1 ) ∈ Ĉj and (X, Zj ) < Gj + P (X, Zj−1 ) < Ĉj
h
i
≤P (X, Zj ) < Cj+1 and (X, Zj ) ∈ Gj + τ 0 + µ∗
where the last inequality follows from Lemma 4.3 and the fact that the premise of Lemma 4.3 is
c
true. Now, consider the remaining term. Let Cj+1
denote the complement of the set Cj+1 , and let Z̃j
denote the output of W j (P). Observe that
h
i
P (X, Zj ) < Cj+1 and (X, Zj ) ∈ Gj =

X

h
i
P X = x, Zj = zj

c
(x,zj )∈Cj+1
∩Gj

X

=

h
i
P Zj = zj | X = x P [X = x]

c
(x,zj )∈Cj+1
∩Gj

X

=

h
i
P Mj (x) = zj P [X = x]

c
(x,zj )∈Cj+1
∩Gj

≤ e ηj

X

h
i
P W j (P) = zj P [X = x]

c
(x,zj )∈Cj+1
∩Gj

h
i
≤ eηj P (X, Z˜j ) < Cj+1
where the fourth inquality follows from the definition of Gj .
Notice that X and Z̃j are independent. By the (η, 0, ν)-typical stability of Aj+1 , for any fixed
prefix zj we have
h
i
P Aj+1 (X, zj ) ≈η Wj+1 (P) ≥ 1 − ν

Thus, by the independence of X and Z̃j , we have
h
i
P Aj+1 (X, Z˜j ) ≈η Wj+1 (P) ≥ 1 − ν,
i.e.,

h
i
P (X, Z˜j ) < Cj+1 ≤ ν.

This concludes the proof.
The proof of Theorem
4.2 follows
three lemmas and by induction on the basis
h
i
hfrom the above
i
0
of j = 1. Note that P (X, Z ) ∈ Ĉ1 = P (X, ⊥) ∈ Ĉ1 ≥ 1 − ν by the typical stability of A1 , and hence
the premise in Lemma 4.3 is true for j = 1 (the base case of the induction).

4.2

Composition of approximate typically stable algorithms

Our composition theorem for approximate typically stable algorithms, i.e. when τ > 0, is given by
Theorem 4.8 below. The proof of this theorem follows the general paradigm of the proof of the
pure case in Section 4.1.1. However, the proof requires few non-trivial modifications to account
for another sequence of “bad” sets that arises from the fact that τ > 0. We defer the details of this
proof to the appendix.
Theorem 4.8 (Adaptive Composition of Approximate Typically Stable Algorithms). Let k ≥ 2. For
all η ∈ (0, 3/2], τ ∈ (0, η/50], ν ∈ (0, 1), and τ 0 ∈ (0, 1), the class of (η, τ, ν)-typically stable algorithms
w.r.t. a family of distributions P satisfies (η ∗ , τ ∗ , ν ∗ )-typical stability w.r.t. P under k-fold adaptive
composition where η ∗ , τ ∗ , and ν ∗ are given by
!
!
p
e2η
∗
0
− 1 + ψ(τ) ,
η = 6 2k log(1/τ )η + 3k 2η
1 − τ̂

1/2
k−1
X
 τ̂ + τ 0

ν
ν
τ ∗ = ν ∗ = 5 k
+
+
eηt 
2η
2η
2η
t=1

where
2τ
= O (τ/η) ,
1 − e−η
!




2η
η
−η
−2η
4e + 4e − 3 − 2e + e
= O τ + τ 2 /η 2 .
2

τ̂ ,
ψ(τ) , τ (2eη + 1) + τ 2 1 +

In particular, for τ

= O(η 2 ),

2e2η
(eη − 1)

q
and η = O

log(1/τ 0 )
k

!
, the k-fold adaptive composition is

√  
√  
 √ 
q
q
p
p
Õ kη
Õ kη
2
0
2
0
Õ kη , O k (τ/η + τ /η) + kν/ηe
, O k (τ/η + τ /η) + kν/ηe
−typically stable

p
where the hidden logarithmic factor in the Õ(·) expressions is ≈ log(1/τ 0 ).

5

Typically Stable Algorithms for Answering Concentrated Queries

We describe here two simple noise-adding mechanims for answering real-valued γn -concentrated
queries while achieving typical stability. The algorithms are based on adding Laplace or Gaussian
noise to the output of the query, and hence these algorithms are very similar to their differntially
private counterparts, however, the added noise is calibrated differently from the case of differential
privacy.
Rather than calibrating the noise based on the global sensitivity [DMNS06] (or smoothed local
sensitivity [NRS07]) of the query, the noise added here is proportional to the width of the confidence
interval of the query’s answer w.r.t. the given dataset, that is, based on how well the value of
the statistic computed over the dataset is concentrated around its true mean with respect to the
underlying distribution on the data. In particular, for
of γn -concentrated queries, to
 the class

−γ
(α)
n
achieve typical stability with parameters η and ν = O e
, the noise added is proportional to
α, namely, the magnitude (standard deviation) of the noise is chosen to be ≈ α/η.
The intution here is that the added noise aims to hide the identity of the specific sample given
to the algorithm (i.e., the input dataset) so that it “blends” with the other typical datasets that occur
with probability greater than 1 − ν. At the same time, the noisy output would still reveal only the
relevant information that is shared by all typical datasets. Such information depends more on the
distribution rather than the sample.
Let P be any distribution over X n . Algorithm 2 describes a (η, 0, ν)-typically stable algorithm
for answering γn -concentrated queries with respect to P, i.e., for answering any query in Qγn (P).
Algorithm 2 A Pure Typically Stable Laplace Mechanism for answering queries in Qγn (P)
Require: A dataset x ∈ X n , parameters η, ν, and a γn -concentrated query q ∈ Qγn (P) (the function
γn is also given as input to the algorithm).
1: Choose α such that γn (α) ≥ ln (1/ν) .
 
2: Let N ∼ Lap α
η .
3: return w = q(x) + N .
Theorem 5.1 (Typical Stability of the Algorithm 2). For any distribution P over X n , Algorithm 2 for
answering queries in Qγn (P) is (η, 0, ν)-typically stable with respect to P.


Proof. Let S q , x ∈ X n : q(x) − E [q(T)] ≤ α where q is the input query from Qγn (P). Let W be
T∼P
 
the oracle that takes the distribution P as input, computes E [q(T)], then adds Lap αη noise to it
T∼P

and outputs the result. By definition of Qγn , we have P [X ∈ S q ] ≥ 1 − e−γn (α) ≥ 1 − ν.
X∼P

Let x ∈ S q . Let w be the output of Algorithm 2 for input dataset x, and O ⊆ R be any measurable
set. Observe
"
!
#
Z
η
η
α
P [w ∈ O] = P q(x) + Lap
∈O =
e− α |w−q(x)| dw
η
2α O
Z
η
η
η
E [q(T)]
− w− E [q(T)]
α q(x)−T∼P
≤e
·
e α T∼P
dw
2α O
"
!
#
α
≤ eη P E [q(T)] + Lap
∈O
T∼P
η

where the last inequality follows from the fact that q(x) − E [q(T)] ≤ α since x ∈ S q .
T∼P

The following theorem follows directly from the tail properties of Laplace distribution.
Theorem 5.2 (Empirical Error of Algorithm 2). With probability at least 1 − β with respect to the
α ln(1/β)
random coins of Algorithm 2, the output w satisfies |w − q(x)| <
.
η
Next, we describe and analyze a mechanism for answering γn -concentrated queries while
satisfying approximate typical stability.
Let P be any distribution over X n . Algorithm 3 describes a (η, τ, ν)-typically stable algorithm
for answering γn -concentrated queries with respect to P.
Algorithm 3 An Approximate Typically Stable Gaussian Mechanism for answering queries in
Qγn (P)
Require: A dataset x ∈ X n , parameters η, τ, ν, and a γn -concentrated query q ∈ Qγn (P) (the function
γn is also given as input to the algorithm).
1: Choose α such that γn (α) ≥ ln (1/ν) .
√


α 2 ln(1.5/τ)
2
2: Let N ∼ N 0, σ where σ =
.
η
3: return w = q(x) + N .
Theorem 5.3 (Typical Stability of Algorithm 3). For any distribution P over X n , Algorithm 3 for
answering queries in Qγn (P) is (η, τ, ν)-typically stable with respect to P.


q
n
Proof. As in the proof of Theorem 5.1, let S , x ∈ X : q(x) − E [q(T)] ≤ α where q is the input
T∼P

query from Qγn (P). Let W be the oracle that takes the distribution P as input, computes E [q(T)],
T∼P


then adds N 0, σ 2 noise to it and outputs the result, where σ is as given in Step 2 of Algorithm 3.
By definition of Qγn , we have P [X ∈ S q ] ≥ 1 − e−γn (α) ≥ 1 − ν.
X∼P

Let x ∈ S q . To reach the desired

 result, we then bound the ratio of the densities of q(x) + N and
2
E [q(T)] + N where N ∼ N 0, σ . This is done by following the same approach in the analysis of

T∼P

the standard Gaussian mechanism in the literature of differential privacy [DKM+ 06, DR14, NTZ13]
and using the fact that q(x) − E [q(T)] ≤ α.
T∼P

The following theorem follows directly from the tail properties of the Gaussian distribution.
Theorem 5.4 (Empirical Error of Algorithm 3). With probability
√ at least 1 − β with respect to the
2α ln(1.5/τ) ln(1/β)
random coins of Algorithm 3, the output w satisfies |w − q(x)| <
.
η

6

Applications in Adaptive Data Analysis

In this section, we discuss a direct implication of our results in previous sections on the statistical
accuracy resulting from using a typically stable algorithm to answer any sequence of k adaptively
chosen γn -concentrated queries.

In particular, we give a theorem (Theorem 6.1 below) that describes an upper bound on the
worst true error in the answers of Algorithm 2 (of Section 5) to any sequence of k adaptively
chosen γn -concentrated queries from the class Qγn (P). Similar guarantees can be also obtained for
Algorithm 3.
First, we describe the adaptive model that we consider here. Figure 1 describes an adaptive
interaction between an analyst and Algorithm 2. Let P be a distribution over X n . The procedure
consists of k iterations where in each iteration j ∈ [k], the analyst chooses a query qj adaptively
from Qγn (P) (based on all the previously submitted queries q1 , . . . , qj−1 and answers w1 , . . . , wj−1
received from the algorithm), the analyst submits qj to Algorithm 2, then the algorithm returns an
answer wj .
Let P be a distribution over X n .
The analyst is given access to the class of γn -concentrated queries Qγn (P).
Algorithm 2 (described in Section 5) is given a dataset X ∼ P and stability parameters η, ν as
inputs.
FOR j = 1, . . . , k:.
Analyst chooses a query qj ∈ Qγn (P) and submits it to Algorithm 2.
(qj can be chosen adaptively based on the sequence q1 , w1 , . . . , qj−1 , wj−1 )
Algorithm 2 returns an answer wj to the analyst.
Figure 1: Adaptive interaction between an analyst and Algorithm 2
The worst true error is defined as the maximum statistcal error in all the answers of the
algorithm.
h Given
i the adaptive procedure in Figure 1, the worst true error is formally defined as
max E qj (Y) − wj .
j∈[k] Y∼P

The following theorem characterizes an upper bound on such an error. This theorem is a
direct consequence of the generalization guarantees in Section 3.3 (Theorem 3.4), the adaptive
composition guarantees of typical stability in Section 4 (Theorem 4.2), and the guarantees of
Algorithm 2 in Section 5 (Theorems 5.1 and 5.2).
Theorem 6.1. Let P be a distribution over X n . Let α > 0, 0 < β < 1. Let k ∈ N. Consider the adaptive
procedure for answering k adaptively chosen queries from Qγn (P) as described in Figure 1. Suppose
!
 √


−γn α/ k ln3/2 (k/β)
1
Algorithm 2 is run with input parameters η = O √
and ν = O e
. Then, we
k ln(k/β)

have
"
#
  √



h
i
−Ω γn α/ k ln3/2 (k/β)
3/4 1/4
P max E qj (Y) − wj ≥ α = O k ln (k/β)e
+β
j∈[k] Y∼P

where the probability is over the randomness in the choice of q1 , . . . , qk (i.e., the possible randomness in
the choice of the analyst) and over the randomness in w1 , . . . , wk (i.e., randomness in Algorithm 2 and in
the choice of its input X ∼ P).

Acknowledgement
We would like to thank Adam Smith and James Zhou for the insightful discussions. We also thank
Adam Smith for pointing out the conditioning lemma of [KS14] which we used in our proof for
the adaptive composition guarantees of typical stability.

References
[BLR08]

Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to noninteractive database privacy. In STOC, May 2008.

[BNS+ 16]

Raef Bassily, Kobbi Nissim, Adam Smith, Uri Stemmer, Thomas Steinke, and Jonathan
Ullman. Algorithmic stability for adaptive data analysis. STOC, 2016.

[CLN+ 26]

Rachel Cummings, Katrina Ligett, Kobbi Nissim, Aaron Roth, and Zhiwei Steven
Wu. Adaptive learning with robust generalization guarantees. In 29th Annual
Conference on Learning Theory (COLT), pages 772–814, June 2016 (also available
at arXiv:1602.07726).

[DFH+ 15a] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and
Aaron Roth. Generalization in adaptive data analysis and holdout reuse. In Advances
in Neural Information Processing Systems (NIPS), Montreal, December 2015.
[DFH+ 15b] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold,
and Aaron Roth. Preserving statistical validity in adaptive data analysis. In ACM
Symposium on the Theory of Computing (STOC). ACM, June 2015.
[DFH+ 15c] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and
Aaron Roth. The reusable holdout: Preserving validity in adaptive data analysis.
Science, 349(6248):636–638, June 2015.
[DKM+ 06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni
Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT,
2006.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to
sensitivity in private data analysis. In TCC, pages 265–284. Springer, March 4-7 2006.
[DR14]

Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy.
Foundations and Trends in Theoretical Computer Science, 9(3-4):211–407, 2014.

[DR16]

Cynthia Dwork and Guy Rothblum. Concentrated differential privacy. In CoRR
abs/1603.01887, March 2016.

[DRV10]

Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential
privacy. In IEEE Symposium on Foundations of Computer Science (FOCS ’10), pages
51–60. IEEE, 23–26 October 2010.

[Dwo06]

Cynthia Dwork. Differential privacy. In Automata, Languages and Programming, 33rd
International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part
II, pages 1–12, 2006.

[KS14]

Shiva P. Kasiviswanathan and Adam Smith. On the ‘semantics’ of differential privacy:
A bayesian formulation. Journal of Privacy and Confidentiality, 6(1), 2014.

[LHTG13] Ben London, Bert Huang, Ben Taskar, and Lise Getoor. Collective stability in structured prediction: Collective stability in structured prediction: Generalization from
one example. In ICML, JMLR W&CP, volume 28(3), 2013.

[NRS07]

Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In STOC, June 2007.

[NTZ13]

Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of di erential privacy:
The sparse and approximate cases. In STOC, June 2013.

[RRST16]

Ryan Rogers, Aaron Roth, Adam Smith, and Om Thakkar. Max-information, differential privacy, and post-selection hypothesis testing. In FOCS. Also available at
arXiv:1604.03924, 2016.

[RZ15]

Daniel Russo and James Zhou. Controlling bias in adaptive data analysis using
information theory. arXiv:1511.05219v1, Novemver 2015.

[WLF16]

Yu-Xiang Wang, Jing Lei, and Stephen E. Fienberg. A minimax theory for adaptive
data analysis. arXiv:1602.04287v1, Feb. 2016.

Appendix A

Proof of Theorem 4.8

Fix η ∈ (0, 3/2], τ ∈ (0, η/50], ν ∈ (0, 1), and τ 0 ∈ (0, 1). For any j ≥ 1, let
!
!
p
e2η
0
− 1 + ψ(τ) ,
ηj = 2 2j log(1/τ )η + j 2η
1 − τ̂
1/2

j−1
 τ̂ + τ 0
ν X ηt ν 

+
+
e
τj = νj = j
 .
 2η
2η
2η 

(16)

(17)

t=1

where
2τ
= O (τ/η) ,
1 − e−η
!




2η
η
−η
−2η
2 2
4e
+
4e
−
3
−
2e
+
e
=
O
τ
+
τ
/η
.
2

τ̂ ,
ψ(τ) , τ (2eη + 1) + τ 2 1 +

2e2η
(eη − 1)

(18)
(19)

Fix some P ∈ P . Let X ∼ P. As before, for any integer j ≥ 1, we let Zj = (Z1 , . . . , Zj ) denote the
output of Mj (X), and let Z̃j to denote the output of W j (P). We assume that Z0 = Z̃0 = ⊥ with
probability 1.
Analogous to the definitions in the case of pure typical stability, for any integer i ≥ 1, and any
(x, zi ) ∈ X n × Z1 × . . . × Zi , we define

i
 h 
 P Ai x, zi−1 = zi 



fi (x, zi ) = ln 
(20)
 P [Wi (P) = zi ] 
and
j

Fj (x, z ) =

j
X
i=1

fi (x, zi )

(21)

Unlike the case of pure typical stability, here we define different sequence of sets Ci :
n
o
Ci = (x, zi−1 ) : Ai (x, zi−1 ) ≈η,τ Wi (P) ,

(22)

We also define the sequence of sets of input/output pairs for which |fi (x, zi )| is bounded:
n
o
Ei = (x, zi ) : |fi (x, zi )| ≤ 2η

(23)

bi as follows:
Now, we define the sequences Hi and H
n
o
Hi = (x, zi ) : ∀` ∈ [i] (x, z`−1 ) ∈ C` and (x, z` ) ∈ E`
n
o
bi = (x, zi−1 ) : ∀` ∈ [i] (x, z`−1 ) ∈ C` and (x, z`−1 ) ∈ E`−1
H

(24)
(25)

where E0 , X n × {⊥}.
Let ηj be as defined in (16), and define the set of “good inputs and outputs” as
n
o
Gj = (x, zj ) : Fj (x, zj ) ≤ ηj

(26)

We start by a lemma that will play a similar role to that of Lemma 4.3 in the proof of Theorem 4.2. However, we note that both the statement and the proof of this lemma are different from
those of Lemma 4.3.
Lemma
A.1. Leti j ≥ 1 and τ̂ be as defined in (18). Suppose there exists a µ∗ ≥ j(ν + τ̂) such that
h
bj ≥ 1 − µ∗ . Then,
P (X, Zj−1 ) ∈ H
h
i
bj ≤ τ 0 + τ̂,
P (X, Zj ) < Gj and (X, Zj−1 ) ∈ H
and

h
i
P (X, Zj ) ∈ Gj ≥ 1 − µ∗ − τ 0 − τ̂.

The proof of the above lemma relies mainly on the following claims. The proof of these claim
follow ideas similar to those in [RRST16, Claim 3.5 and Lemma 3.7].
bi . We have
Claim A.2. Let η ∈ (0, 3/2] and τ ∈ (0, η/50]. Let (x, zi−1 ) ∈ H
h
i
E fi (x, zi ) X = x, Zi−1 = zi−1 , (X, Zi ) ∈ Hi ≤ 2η

!
e2η
− 1 + ψ(τ)
1 − τ̂

where τ̂ and ψ(τ) are as defined in (18) and (19), respectively.
bi and τ̂ be as defined in (18). Then, we have
Claim A.3. Let (x, zi−1 ) ∈ H
h
i
P (X, Zi ) < Hi X = x, Zi−1 = zi−1 < τ̂
Proof of Lemma A.1
Define
(
i

gi (x, z ) =

fi (x, zi ) for (x, zi ) ∈ Hi ;
0
otherwise.

First, by definition, we have
i
h
P gi (x, zi ) ≤ 2η = 1

(27)

Next, we claim that for all (x, zi−1 ) ∈ X n × Z1 × . . . × Zi−1
h
i
E gi (x, zi ) X = x, Zi−1 = zi−1 ≤ 2η

!
e2η
− 1 + ψ(τ)
1 − τ̂

bi , we have
To see this, first, observe that for any (x, zi−1 ) ∈ H
h
i
E gi (x, zi ) X = x, Zi−1 = zi−1 , (X, Zi ) < Hi = 0.

(28)

(29)

bi , by using Claim A.2, we get
Moreover, for any (x, zi−1 ) ∈ H
i
i
h
h
E gi (x, zi ) X = x, Zi−1 = zi−1 , (X, Zi ) ∈ Hi = E fi (x, zi ) X = x, Zi−1 = zi−1 , (X, Zi ) ∈ Hi
!
e2η
≤ 2η
− 1 + ψ(τ)
(30)
1 − τ̂
bi , we have (X, Zi ) < Hi with probability 1, and hence
For any (x, zi−1 ) < H
i
h
E gi (x, zi ) X = x, Zi−1 = zi−1 = 0

(31)

Thus, from (29), (30), and (31), we have shown that (28) is true for all (x, zi−1 ) ∈ X n × Z1 × . . . × Zi−1 .
Now, given (27) and (28), we can apply Azuma’s inequality (Theorem 4.4) to the sequence of
random variables gi (x, zi ), i ∈ [j]. Let ηj be as defined in (16). Observe that


j
X

h
i


P (X, Zj ) < Gj and (X, Zj ) ∈ Hj = P 
fi (X, Zj ) > ηj and (X, Zj ) ∈ Hj 


i=1


j
X



= P 
gi (X, Zj ) > ηj  ≤ τ 0
(32)


i=1

where the last inequality follows from Azuma’s inequality (Theorem 4.4) and the definition of ηj
in (16). Now, we have
h
i
bj
P (X, Zj ) < Gj and (X, Zj−1 ) ∈ H
h
i
h
i
bj and (X, Zj ) ∈ Hj + P (X, Zj ) < Gj and (X, Zj−1 ) ∈ H
bj and (X, Zj ) < Hj
= P (X, Zj ) < Gj and (X, Zj−1 ) ∈ H
h
i
h
i
bj and (X, Zj ) < Hj
≤ P (X, Zj ) < Gj and (X, Zj ) ∈ Hj + P (X, Zj−1 ) ∈ H
h
i
h
i
bj
≤ P (X, Zj ) < Gj and (X, Zj ) ∈ Hj + P (X, Zj ) < Hj (X, Zj−1 ) ∈ H
≤ τ 0 + τ̂
where
the last inequality
follows from (32) and Claim A.3. This together with the fact that
h
i
bj ≥ 1 − µ∗ (the premise of Lemma A.1) gives
P (X, Zj−1 ) ∈ H
h
i
P (X, Zj ) ∈ Gj ≥ 1 − µ∗ − τ 0 − τ̂.
Hence, the proof of Lemma A.1 is complete.
Next, we state and prove an analog of Lemma 4.5.

Lemma A.4. Let j ≥ 1. Suppose the premise of Lemma
is q
true, that is, there is µ∗ ≥ j(ν + τ̂) such
q ∗ A.1
h
i
0
∗
0
bj ≥ 1 − µ∗ . Then Mj is (3ηj , 5 µ +τ +τ̂ , 5 µ +τ +τ̂ )-typically stable.
that P (X, Zj−1 ) ∈ H
η
η
Proof. Recall the definition of Gj in (26). Observe that for any (x, zj ) ∈ Gj
h
i
P Mj (x) = zj
h
i ≤ e ηj
P W j (P) = zj

(33)



where W j (P) = W1 (P), . . . , Wj (P) . Let Z̃j denote the output of W j (P). Define
n
o
G̃j = (x, zj ) : − Fj (x, zj ) ≤ ηj
where Fj (x, zj ) is as defined in (21). Now, for any (x, zj ) ∈ G̃j , we also have
h
i
P W j (P) = zj
h
i ≤ e ηj
j
j
P M (x) = z

(34)

Moreover, by the independence of X and Z̃j , using Claim A.3 and the union bound, we get
h
i
bj ≥ 1 − j(ν + τ̂) ≥ 1 − µ∗
P (X, Z̃j−1 ) ∈ H
bj is as defined in (25).
where H
Thus, by swaping the roles of Mj (X) and W j (P) in Lemma A.1, it follows that
i
h
P (X, Z̃j ) ∈ G̃j ≥ 1 − µ∗ − τ 0 − τ̂

(35)

Hence, by Lemma A.1, and using (33)-(35) above, we have




X, Mj (X) ≈ηj , µ∗ +τ 0 +τ̂ X, W j (P)
The rest of the proof follows by applying Lemma 4.6 in the same way as in the proof of
Lemma 4.5.
The final component of the proof is the following lemma that is analogous to Lemma 4.7 and
serves as our induction step.
∗
Lemma
h A.5. Let j ≥ i1. Suppose the premise of Lemma A.1 is true, i.e., there exists µ ≥ j(ν + τ̂) such
bj ≥ 1 − µ∗ . Then, we have
that P (X, Zj−1 ) ∈ H

h
i
bj+1 ≥ 1 − µ∗ − eηj ν − τ 0 − τ̂
P (X, Zj ) ∈ H

bj , Cj , and Ej in (25), (22), and (23), respecitvely,
Proof. From the definitions of the sequence of sets H
observe that
h
i
bj+1
P (X, Zj ) < H
h
i
h
i
bj+1 and (X, Zj−1 ) ∈ H
bj + P (X, Zj−1 ) < H
bj
=P (X, Zj ) < H
h
i
h
i
h
i
bj + P (X, Zj−1 ) < H
bj
=P (X, Zj ) < Cj+1 and (X, Zj ) ∈ Hj + P (X, Zj ) < Ej and (X, Zj−1 ) ∈ H
h
i
h
i
h
i
bj + P (X, Zj−1 ) < H
bj
=P (X, Zj ) < Cj+1 and (X, Zj ) ∈ Hj + P (X, Zj ) < Hj and (X, Zj−1 ) ∈ H
h
i
h
i
h
i
bj + P (X, Zj−1 ) < H
bj
≤P (X, Zj ) < Cj+1 and (X, Zj ) ∈ Hj + P (X, Zj ) < Hj (X, Zj−1 ) ∈ H
h
i
≤P (X, Zj ) < Cj+1 and (X, Zj ) ∈ Hj + τ̂ + µ∗
(36)
where the last inequality follows from Claim A.3 and from the premise in the lemma.
Now, let’s consider the first term on the right-hand side of the last inequality. Observe that
h
i
P (X, Zj ) < Cj+1 and (X, Zj ) ∈ Hj
h
i
h
i
=P (X, Zj ) < Cj+1 and (X, Zj ) ∈ Hj and (X, Zj ) ∈ Gj + P (X, Zj ) < Cj+1 and (X, Zj ) ∈ Hj and (X, Zj ) < Gj
h
i
h
i
≤P (X, Zj ) < Cj+1 and (X, Zj ) ∈ Gj + P (X, Zj ) ∈ Hj and (X, Zj ) < Gj
h
i
≤P (X, Zj ) < Cj+1 and (X, Zj ) ∈ Gj + τ 0
(37)
c
where the last inequality follows from (32). Now, consider the remaining term. Let Cj+1
denote the

complement of the set Cj+1 , and let Z̃j denote the output of W j (P). Observe that
X
h
i
h
i
P (X, Zj ) < Cj+1 and (X, Zj ) ∈ Gj =
P X = x, Zj = zj
c
(x,zj )∈Cj+1
∩Gj

X

=

h
i
P Zj = zj | X = x P [X = x]

c
(x,zj )∈Cj+1
∩Gj

X

=

h
i
P Mj (x) = zj P [X = x]

c
(x,zj )∈Cj+1
∩Gj

≤ e ηj

X

h
i
P W j (P) = zj P [X = x]

c
(x,zj )∈Cj+1
∩Gj

h
i
≤ eηj P (X, Z˜j ) < Cj+1
where the fourth inquality follows from the definition of Gj .
Notice that X and Z̃j are independent. By the (η, τ, ν)-typical stability of Aj+1 , for any fixed
prefix zj we have
h
i
P Aj+1 (X, zj ) ≈η,τ Wj+1 (P) ≥ 1 − ν
Thus, by the independence of X and Z̃j , we have
h
i
P (X, Z˜j ) < Cj+1 ≤ ν.
Putting (36), (37), and (38) together concludes the proof.

(38)

The proof of Theorem 4.8 nowh follows from
i the Lemmas A.1, A.4, and A.5, and via induction
0
b
on the basis of j = 1. Note that P (X, Z ) ∈ H1 = P [(X, ⊥) ∈ C1 ] ≥ 1 − ν by the typical stability of
A1 , and hence the premise in Lemma A.1 is true for j = 1 (the base case of the induction).

