arXiv:1511.02513v1 [cs.LG] 8 Nov 2015

Algorithmic Stability for Adaptive Data Analysis∗
Raef Bassily†

Kobbi Nissim‡

Adam Smith§

Thomas Steinke¶

Uri Stemmerk

Jonathan Ullman∗∗

Abstract
Adaptivity is an important feature of data analysis—the choice of questions to ask about
a dataset often depends on previous interactions with the same dataset. However, statistical
validity is typically studied in a nonadaptive model, where all questions are specified before
the dataset is drawn. Recent work by Dwork et al. (STOC, 2015) and Hardt and Ullman (FOCS,
2014) initiated the formal study of this problem, and gave the first upper and lower bounds on
the achievable generalization error for adaptive data analysis.
Specifically, suppose there is an unknown distribution P and a set of n independent samples
x is drawn from P. We seek an algorithm that, given x as input, accurately answers a sequence
of adaptively chosen “queries” about the unknown distribution P. How many samples n must
we draw from the distribution, as a function of the type of queries, the number of queries, and
the desired level of accuracy?
In this work we make two new contributions towards resolving this question:
1. We give upper bounds on the number of samples n that are needed to answer statistical
queries. The bounds improve and simplify the work of Dwork et al. (STOC, 2015), and
have been applied in subsequent work by those authors (Science, 2015; NIPS, 2015).
2. We prove the first upper bounds on the number of samples required to answer more
general families of queries. These include arbitrary low-sensitivity queries and an important
class of optimization queries (alternatively, risk minimization queries).
As in Dwork et al., our algorithms are based on a connection with algorithmic stability in
the form of differential privacy. We extend their work by giving a quantitatively optimal, more
general, and simpler proof of their main theorem that stable algorithms of the kind guaranteed
by differential privacy imply low generalization error. We also show that weaker stability
guarantees such as bounded KL divergence and total variation distance lead to correspondingly
weaker generalization guarantees.
∗ This work unifies and subsumes the two arXiv manuscripts [BSSU15, NS15].
† University of California San Diego, Center for Information Theory and Applications and Department of Computer

Science and Engineering. Part of this work was done while the author was at Pennsylvania State University, supported
by NSF award CDI-0941553. rbassily@ucsd.edu
‡ Ben-Gurion University of the Negev, Department of Computer Science and Center for Research on Computation
and Society (CRCS), Harvard University. Supported by a grant from the Sloan Foundation, a Simons Investigator grant
to Salil Vadhan, and NSF grant CNS-1237235. kobbi@cs.bgu.ac.il
§ Pennsylvania State University, Department of Computer Science and Engineering. Supported by NSF award
IIS-1447700, a Google Faculty Award and a Sloan Foundation research award. asmith@psu.edu
¶ Harvard University, John A. Paulson School of Engineering and Applied Sciences. Supported by NSF grants
CCF-1116616, CCF-1420938, and CNS-1237235. tsteinke@seas.harvard.edu
k Ben-Gurion University of the Negev, Depaprtment of Computer Science. Supported by the Ministry of Science and
Technology, Israel. stemmer@cs.bgu.ac.il
∗∗ Northeastern University, College of Computer and Information Science. Part of this work was done while the author
was at Columbia University, supported by a Junior Fellowship from the Simons Society of Fellows. jullman@ccs.neu.edu

Contents
1 Introduction
1.1 Overview of Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Overview of Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
2
3

2 Preliminaries
2.1 Queries . . . . . . . . . . . . . . . . . . . . . .
2.2 Mechanisms for Adaptive Queries . . . . . . .
2.3 Max-KL Stability (a.k.a. Differential Privacy)
2.3.1 Stability for Interactive Mechanisms .
2.3.2 Composition of Max-KL Stability . . .

5
5
7
7
8
9

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

3 From Max-KL Stability to Accuracy for Low-Sensitivity Queries
3.1 Warmup: A Single-Sample De-Correlated Expectation Lemma for SQs
3.2 Warmup: A Multi-Sample De-Correlated Expectation Lemma for SQs
3.3 A Multi-Sample De-Correlated Expectation Lemma . . . . . . . . . .
3.4 From Multi-Sample De-Correlated Expectation to Accuracy . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

9
. 9
. 10
. 11
. 14

.
.
.
.
.

16
16
17
17
18
19

4 Other Notions of Stability and Accuracy on Average
4.1 Other Notions of Algorithmic Stability . . . . . . . . . . . . . . .
4.2 From TV Stability to Accuracy on Average . . . . . . . . . . . . .
4.3 Accuracy on Average . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.1 A De-Correlated Expectation Lemma . . . . . . . . . . . .
4.3.2 From De-Correlated Expectation to Accuracy on Average

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

5 From Low-Sensitivity Queries to Optimization Queries

20

6 Applications
6.1 Low-Sensitivity and Statistical Queries . . . . .
6.2 Optimization Queries . . . . . . . . . . . . . . .
6.2.1 Minimization Over Arbitrary Finite Sets
6.2.2 Convex Minimization . . . . . . . . . . .

21
21
22
22
22

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

7 An Alternative Form of Generalization and Tightness of Our Results
24
7.1 Optimality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Acknowledgements

26

References

26

If you torture the data enough, nature will always confess.

1

– Ronald Coase

Introduction

Multiple hypothesis testing is a ubiquitous task in empirical research. A finite sample of data is
drawn from some unknown population, and several analyses are performed on that sample. The
outcome of an analysis is deemed significant if it is unlikely to have occurred by chance alone,
and a “false discovery” occurs if the analyst incorrectly declares an outcome to be significant.
False discovery has been identified as a substantial problem in the scientific community (see
e.g. [Ioa05, GL14]). This problem persists despite decades of research by statisticians on methods
for preventing false discovery, such as the widely used Bonferroni Correction [Bon36, Dun61] and
the Benjamini-Hochberg Procedure [BH95].
False discovery is often attributed to misuse of statistics. An alternative explanation is that the
prevalence of false discovery arises from the inherent adaptivity in the data analysis process—the
fact that the choice of analyses to perform depends on previous interactions with the data (see
e.g. [GL14]). Adaptivity is essentially unavoidable when a sequence of research groups publish
research papers based on overlapping data sets. Adaptivity also arises naturally in other settings,
for example: in multistage inference algorithms where data are preprocessed (say, to select features
or restrict to a principal subspace) before the main analysis is performed; in scoring data-based
competitions [BH15]; and in the re-use of holdout or test data [DFH+ 15c, DFH+ 15a].
The general problem of adaptive data analysis was formally modeled and studied in recent
papers by Dwork, Feldman, Hardt, Pitassi, Reingold, and Roth [DFH+ 15b] and by Hardt and
Ullman [HU14]. The striking results of Dwork et al. [DFH+ 15b] gave the first nontrivial algorithms
for provably ensuring statistical validity in adaptive data analysis, allowing for even an exponential
number of tests against the same sample. In contrast, [HU14, SU15b] showed inherent statistical
and computational barriers to preventing false discovery in adaptive settings.
The key ingredient in Dwork et al. is a notion of “algorithmic stability” that is suitable for
adaptive analysis. Informally, changing one input to a stable algorithm does not change it’s output
“too much.” Traditionally, stability was measured via the change in the generalization error of
an algorithm’s output, and algorithms stable according to such a criterion have long been known
to ensure statistical validity in nonadaptive analysis [DW79a, DW79b, KR99, BE02, SSSS10].
Following a connection first suggested by McSherry1 , Dwork et al. showed that a stronger stability
condition designed to ensure data privacy—called differential privacy (DP) [DMNS06, Dwo06]—
guarantees statistical validity in adaptive data analysis. This allowed them to repurpose known
DP algorithms to prevent false discovery. A crucial difference from traditional notions of stability
is that DP requires a change in one input lead to a small change in the probability distribution on
the outputs (in particular, differentially private algorithms must be randomized). In this paper,
we refer to differential privacy as max-KL-stability (Definition 2.3), to emphasize the relation to
the literature on algorithmic stability other notions of stability we study (KL- and TV-stability, in
particular).
In this work, we extend the results of Dwork et al. along two axes. First, we give an optimal
analysis of the statistical validity of max-KL stable algorithms. As a consequence, we immediately
obtain the best known bounds on the sample complexity (equivalently, the convergence rate) of
adaptive data analysis. Second, we generalize the connection between max-KL stability and
statistical validity to a much larger family of statistics. Our proofs are also significantly simpler
than those of Dwork et al., and clarify the role of different stability notions in the adaptive setting.
1 See, e.g., [McS14], although the observation itself dates back at least to 2008 (personal communication).

1

1.1

Overview of Results

Adaptivity and Statistical Queries. Following the previous work on this subject ([DFH+ 15b]),
we formalize the problem of adaptive data analysis as follows. There is a distribution P over some
finite universe X , and a mechanism M that does not know P, but is given a set x consisting of n
samples from P. Using its sample, the mechanism must answer queries on P. Here, a query q, coming from some family Q, maps a distribution P to a real-valued answer. The mechanism’s answer a
to a query q is α-accurate if |a − q(P)| ≤ α with high probability. Importantly, the mechanism’s goal
is to provide answers that “generalize” to the underlying distribution, rather than answers that are
specific to its sample.
We model adaptivity by allowing a data analyst to ask a sequence of queries q1 , q2 , . . . , qk ∈ Q
to the mechanism, which responds with answers a1 , a2 , . . . , ak . In the adaptive setting, the query
qj may depend on the previous queries and answers q1 , a1 , . . . , qj−1 , aj−1 arbitrarily. We say the
mechanism is α-accurate given n samples for k adaptively chosen queries if, with high probability,
when given a vector x of n samples from an arbitrary distribution P, the mechanism accurately
responds to any adaptive analyst that makes at most k queries.
Dwork et al. [DFH+ 15b] considered the family of statistical queries [Kea93]. A statistical query
q asks for the expected value of some function on random draws from the distribution. That is, the
query is specified by a function p : X → [0, 1] and its answer is q(P) = Ez←R P [p(z)].
The most natural way to answer a statistical query is to compute the empirical answer Ez←R x [p(z)],
which is just the average value of the function on the given sample x.2 It is simple to show that
when k queries are specified nonadaptively (i.e. independent of previous answers), then the empirical answer is within q(P) ± α (henceforth, “α-accurate”) with high probability so long as the
sample has size n & log(k)/α 2 . 3 However, when the queries can be chosen adaptively, the empirical
average performs much worse. In particular, there is an algorithm (based on [DN03]) that, after
seeing the empirical answer to k = O(α 2 n) random queries, can find a query such that the empirical
answer and the correct answer differ by α. Thus, the empirical average is only guaranteed to be
accurate when n & k/α 2 , and so exponentially more samples are required to guarantee accuracy
when the queries may be adaptive.
Answering Adaptive Statistical Queries. Surprisingly, Dwork et al. [DFH+ 15b], showed there
are mechanisms that are much more effective than naı̈vely outputting the empirical answer.
They show that “stable” mechanisms are accurate and, by applying a stable mechanism from
the √
literature on differential privacy, they obtain a mechanisms that are accurate given only
n & k/α 2.5 samples, which is a significant improvement over the naı̈ve mechanism when α is not
too small. (See Table 1 for more detailed statements of their results, including results that achieve
an exponential improvement in the sample complexity when |X | is bounded.)
Our first contribution is to give a simpler and quantitatively optimal analysis of the generalization properties of stable algorithms, which immediately
yields new accuracy bounds for adaptive
√
statistical queries. In particular, we show that n & k/α 2 samples suffice. Since 1/α 2 samples are
required to answer a single nonadaptive query, our dependence on α is optimal.
Beyond Statistical Queries. Although statistical queries are surprisingly general [Kea93], we
would like to be able to ask more general queries on the distribution P that capture a wider variety
2 For convenience, we will often use x as shorthand for the empirical distribution over x. We use z ← x to mean a
R

random element chosen from the uniform distribution over the elements of x.
3 This guarantee follows from bounding the error of each query using a Chernoff bound and then taking a union
bound over all queries. The log k term corresponds to the Bonferroni correction in classical statistics.

2

of machine learning and data mining tasks. To this end, we give the first bounds on the sample
complexity required to answer large numbers of adaptively chosen low-sensitivity queries and
optimization queries, which we now describe.
Low-sensitivity queries are a generalization of statistical queries. A query is specified by an
arbitrary function p : X n → R satisfying |p(x) − p(x0 )| ≤ 1/n for every x, x0 ∈ X n differing on exactly
one element. The query applied to the population is defined to be q(P) = Ex←R Pn [p(x)]. Examples
include distance queries (e.g. “How far is the sample from being well-clustered?”) and maxima of
statistical queries (e.g. “What is the classification error of the best k-node decision tree?”)
Optimization queries are a broad generalization of low-sensitivity queries to arbitrary output
domains. The query is specified by a loss function L : X n × Θ → R that is low-sensitivity in its first
parameter, and the goal is to output θ ∈ Θ that is “best” in the sense that it minimizes the average
loss. Specifically, q(P) = arg minθ∈Θ Ez←R Pn [L(z; θ)]. An important special case is when Θ ⊆ Rd
is convex and L is convex in θ, which captures many fundamental regression and classification
problems.
Our sample complexity bounds are summarized in Table 1.
Query Type
Statistical (k  n2 )
Statistical (k  n2 )
Low Sensitivity (k  n2 )
Low Sensitivity (k  n2 )
Convex Min. (k  n2 )
Convex Min. (k  n2 )

Sample Complexity
+ 15b]
[DFH√
This √
Work
!
!
k
k
Õ 2.5
Õ 2
α
α
p



p
 log |X | · log3/2 k 
 log |X | · log k 





Õ 
Õ 


α 3.5
α3
√ !
k
—
Õ 2
α
!
log |X | · log k
Õ
—
3
√α !
dk
Õ
—
α2 p

 √
 ( d + log k) · log |X | 


—
Õ 

α3

Time per Query
poly(n, log |X |)
poly(n, |X |)
poly(n, log |X |)
poly(|X |n )
poly(n, d, log |X |)
poly(n, d, |X |)

Table 1: Summary of Results. Here k = number of queries, n = number of samples, α = desired
accuracy, X = universe of possible samples, d = dimension of parameter space Θ.

Subsequent Work. Our bounds were applied in subsequent work of Dwork et al. [DFH+ 15c,
DFH+ 15a] in the analysis of their “reusable holdout” construction.

1.2

Overview of Techniques

Our main result is a new proof, with optimal parameters, that a stable algorithm that provides
answers to adaptive queries that are close to the empirical value on the sample gives answers that
generalize to the underlying distribution. In particular, we prove:
Theorem 1.1 (Main “Transfer Theorem”). Let M be a mechanism that takes a sample x ∈ X n and
answers k adaptively-chosen low-sensitivity queries. Suppose that M satisfies the following:

3

4
1. For
h every sample x, M’sianswers are (α, αβ)-accurate with respect to the sample x. That is,
P maxj∈k qj (x) − aj ≤ α ≥ 1 − αβ, where q1 , · · · , qk : X n → R are the low-sensitivity queries that

are asked and a1 , · · · , ak ∈ R are the answers given. The probability is taken only over M’s random
coins.
2. M satisfies (α, αβ)-max-KL stability (Definition 2.3, identical to (α, αβ)-differential privacy).
Then, if x consists of n samples from an
h arbitrary distribution P over
i X , M’s answers are (O(α), O(β))accurate with respect to P. That is, P maxj∈k qj (P) − aj ≤ O(α) ≥ 1 − O(β), where the probability is
taken only over the choice of x ←R Pn and M’s random coins.
Our actual result is somewhat more general than Theorem 1.1. We show that the populationlevel error of a stable algorithm is close to its error on the sample, whether or not that error is low.
Put glibly: stable algorithms cannot be wrong without realizing it.
Compared to the results of [DFH+ 15b], Theorem 1.1 requires a quantitatively weaker stability
guarantee—(α, αβ)-stability, instead of (α, (β/k)1/α )-stability. It also applies to arbitrary lowsensitivity queries as opposed to the special case of statistical queries.
Our analysis differs from that of Dwork et al. in two key ways. First, we give a better bound on
the probability with which a single low-sensitivity query output by a max-KL stable algorithm has
good generalization error. Second, we show a reduction from the case of many queries to the case
of a single query that has no loss in parameters (in contrast, previous work took a union bound
over queries, leading to a dependence on k, the number of queries).
Both steps rely on a thought experiment in which several “real” executions of a stable algorithm
are simulated inside another algorithm, called a monitor, which outputs a function of the “real”
transcripts. Because stability is closed under post-processing, the monitor is itself stable. Because
it exists only as a thought experiment, the monitor can be given knowledge of the true distribution
from which the data are drawn, and can use this knowledge to process the outputs of the simulated
“real” runs. The monitor technique allows us to start from a basic guarantee, which states that a
single query has good generalization error with constant probability, and amplify the guarantee
so that (a) the generalization error holds with very high probability, and (b) the guarantee holds
simultaneously over all queries in a sequence. The proof of the basic guarantee follows the lines of
existing proofs using algorithmic stability (e.g., [DW79a]), while the monitor technique and the
resulting amplification statements are new.
The amplification of success probability is the more technically sophisticated of the two key
steps. The idea is to run many (about 1/β, using the notation of Theorem 1.1) copies of a stable
mechanism on independently selected data sets. Each of these interactions results in a sequence
of queries and answers. The monitor then selects the the query and answer pair from amongst
all of the sequences that has the largest error. It then outputs this query as well as the index of
the interaction that produced it. Our main technical lemma shows that the monitor will find a
“bad” query/dataset pair (one where the true and empirical values of the query differ) with at most
constant probability. This implies that the each of the real executions outputs a bad query with
probability O(β). Relative to previous work, the resulting argument yields better bounds, applies
to more general classes of queries, and even generalizes to other notions of stability.
Optimality. In general, we cannot prove that our bounds are optimal. Even for nonadaptive
statistical queries, n & log(k)/α 2 samples are necessary, and [HU14, SU15b] showed that n &
4 Accuracy is formally defined in Section 2.2. Informally, a mechanism is (α, β)-accurate if every answer it produces
to an adversarial adaptive sequence of queries is α-accurate with probability at least 1 − β.

4

√ p
min{ k, log |X |}/α samples are necessary to answer adaptively chosen statistical queries. However,
the gap between the upper and lower bounds is still significant.
However, we can show that our connection between max-KL stability and generalization is
optimal (see Section 7 for details). Moreover, for every family of queries we consider, no max-KL
stable algorithm can achieve better sample complexity [BUV14, BST14]. Thus, any significant
improvement to our bounds must come from using a weaker notion of stability or some entirely
different approach.
Computational Complexity. Throughout, we will assume that the analyst only issues queries
q such that the empirical answer q(x) can be evaluated in time poly(n, log |X |). When k  n2 our
algorithms have similar running time. However, when answering k  n2 queries, our algorithms
suffer running time at least poly(n, |X |). Since the mechanism’s input is of size n · log |X |, these
algorithms cannot be considered computationally efficient. For example, if X = {0, 1}d for some
dimension d, then in the non adaptive setting poly(n, d) running time would suffice, whereas
our algorithms require poly(n, 2d ) running time. Unfortunately, this running time is known to
be optimal, as [HU14, SU15b] (building on hardness results in privacy [Ull13]) showed that,
assuming exponentially hard one-way functions exist, any poly(n, 2o(d) ) time mechanism that
answers k = ω(n2 ) statistical queries is not even 1/3-accurate.
Stable / Differentially Private Mechanisms. Each of our results requires instantiating the mechanism with a suitable stable / differentially private algorithm. For statistical queries, the optimal
mechanisms are the well known Gaussian and Laplace Mechanisms (slightly refined by [SU15a])
when k is small and the Private Multiplicative Weights Mechanism [HR10] when k is large. For
arbitrary low-sensitivity queries, the Gaussian or Laplace Mechanism is again optimal when k is
small, and for large k we can use the Median Mechanism [RR10].
When considering arbitrary search queries over an arbitrary finite range, the optimal algorithm
is the Exponential Mechanism [MT07]. For the special case of convex minimization queries over
an infinite domain, we use the optimal algorithm of [BST14] when k is small, and when k is large,
we use an algorithm of [Ull15] that accurately answers exponentially many such queries.
Other Notions of Stability Our techniques applies to notions of distributional stability other
than max-KL/differential privacy. In particular, defining stability in terms of total variation (TV)
or KL divergence (KL) leads to bounds on the generalization error that have polynomially, rather
than exponentially, decreasing tails. See Section 4 for details.

2
2.1

Preliminaries
Queries

Given a distribution P over X or a sample x = (x1 , · · · , xn ) ∈ X n , we would like to answer queries
about P or x from some family Q. We will often want to bound the “sensitivity” of the queries with
respect to changing one element of the sample. To this end, we use x ∼ x0 to denote that x, x0 ∈ X n
differ on at most one entry. We will consider several different families of queries:
• Statistical Queries: These queries are specified by a function q : X → [0, 1], and (abusing

5

notation) are defined as
q(P) = E [q(z)]

and

z←R P

q(x) =

1X
q(xi ).
n
i∈[n]

The error of an answer a to a statistical query q with respect to P or x is defined to be
errx (q, a) = a − q(x)

and

errP (q, a) = a − q(P).

• ∆-Sensitive Queries: For ∆ ∈ [0, 1], n ∈ N, these queries are specified by a function q : X n → R
satisfying |q(x) − q(x0 )| ≤ ∆ for every pair x, x0 ∈ X n differing in only one entry. Abusing notation,
let
q(P) = E n [q(z)] .
z←R P

The error of an answer a to a ∆-sensitive query q with respect to P or x is defined to be
errx (q, a) = a − q(x)

and

errP (q, a) =

E [errz (q, a)] = a − q(P).

z←R Pn

We denote the set of all ∆-sensitive queries by Q∆ . If ∆ = O(1/n) we say the query is low sensitivity.
Note that 1/n-sensitive queries are a strict generalization of statistical queries.
• Minimization Queries: These queries are specified by a loss function L : X n × Θ → R. We
require that L has sensitivity ∆ with respect to its first parameter, that is,
|L(x; θ) − L(x0 ; θ)| ≤ ∆ .

sup
θ∈Θ, x,x0 ∈X n , x∼x0

Here Θ is an arbitrary set of items (sometimes called “parameter values”) among which we aim
to chose the item (“parameter”) with minimal loss, either with respect to a particular input data
set x, or with respect to expectation over a distribution P.
The error of an answer θ ∈ Θ to a minimization query L : X n × Θ → R with respect to x is defined
to be
errx (L, θ) = L(x, θ) − min
L(x, θ ∗ )
∗
θ ∈Θ

and, with respect to P, is
errP (L, θ) =
Note that minθ ∗ ∈Θ


E n [errz (L, θ)] =

z←R P

E [L(z, θ ∗ )] ≥

z←R Pn

E n [L(z, θ)] − E

z←R P


∗
min
L(z,
θ
)
.
∗

z←R Pn θ ∈Θ

E [minθ ∗ ∈Θ L(z, θ ∗ )], whence

z←R Pn

E [L(z, θ)] − min
E n [L(z, θ ∗ )] ≤ errP (L, θ) .
∗

z←R Pn

θ ∈Θ z←R P

Note that minimization queries (with Θ = R) generalize low-sensitivity queries: Given a ∆sensitive q : X n → R, we can define L(x; θ) = |θ − q(x)| to obtain a minimization query with the
same answer.
We denote the set of minimization queries by Qmin . We highlight two special cases:
– Minimization for Finite Sets: We denote by Qmin,D the set of minimization queries where Θ
is finite with size at most D.
– Convex Minimization Queries: If Θ ⊂ Rd is closed and convex and L(x; ·) is convex on Θ for
every data set x, then the query can be answered nonprivately up to any desired error α, in
time polynomial in d and α. We denote the set of all convex minimization queries by QCM .
6

2.2

Mechanisms for Adaptive Queries

Our goal is to design a mechanism M that answers queries on P using only independent samples
x1 , . . . , xn ←R P. Our focus is the case where the queries are chosen adaptively and adversarially.
Specifically, M is a stateful algorithm that holds a collection of samples x1 , . . . , xn ∈ X , takes a
query q from some family Q as input, and returns an answer a. We require that when x1 , . . . , xn are
independent samples from P, the answer a is “close” to q(P) in a sense that is appropriate for the
family of queries. Moreover we require that this condition holds for every query in an adaptively
chosen sequence q1 , . . . , qk . Formally, we define an accuracy game between a mechanism M and a
stateful data analyst A in Figure 1.
A chooses a distribution P over X .
Sample x1 , . . . , xn ←R P, let x = (x1 , . . . , xn ). (Note that A does not know x.)
For j = 1, . . . , k
A outputs a query qj ∈ Q.
M(x, qj ) outputs aj .
(As A and M are stateful, qj and aj may depend on the history q1 , a1 , . . . , qj−1 , aj−1 .)
Figure 1: The Accuracy Game Accn,k,Q [M, A]
Definition 2.1 (Accuracy). A mechanism M is (α, β)-accurate with respect to the population for k
adaptively chosen queries from Q given n samples in X if for every adversary A,
"
#


P
P
max err qj , aj ≤ α ≥ 1 − β.
Accn,k,Q [M,A] j∈[k]

We will also use a definition of accuracy relative to the sample given to the mechanism,
described in Figure 2.
A chooses x = (x1 , . . . , xn ) ∈ X n .
For j = 1, . . . , k
A outputs a query qj ∈ Q.
M(x, qj ) outputs aj .
(qj and aj may depend on the history q1 , a1 , . . . , qj−1 , aj−1 and on x.)
Figure 2: The Sample Accuracy Game SampAccn,k,Q [M, A]
Definition 2.2 (Sample Accuracy). A mechanism M is (α, β)-accurate with respect to samples of size
n from X for k adaptively chosen queries from Q if for every adversary A,
"
#


P
max errx qj , aj ≤ α ≥ 1 − β.
SampAccn,k,Q [M,A] j∈[k]

2.3

Max-KL Stability (a.k.a. Differential Privacy)

Informally, an algorithm is “stable” if changing one of its inputs does not change its output “too
much.” For our results, we will consider randomized algorithms, and require that changing one
7

input does not change the distribution of the algorithm’s outputs too much. With this in mind,
we will define here one notion of algorithmic stability that is related to the well-known notion
of KL-divergence between distributions. In Section 4.1, we will give other related notions of
algorithmic stability based on different notions of closeness between distributions.
Definition 2.3 (Max-KL Stability). Let W : X n → R be a randomized algorithm. We say that W is
(ε, δ)-max-KL stable if for every pair of samples x, x0 that differ on exactly one element, and every
R ⊆ R,


P [W (x) ∈ R] ≤ eε · P W (x0 ) ∈ R + δ.
This notion of (ε, δ)-max-KL stability is also commonly known as (ε, δ)-differential privacy [DMNS06],
however in this context we choose the term max-KL stability to emphasize the conceptual relationship between this notion and other notions of algorithmic stability that have been studied
in machine learning. We also emphasise that our work has a very different motivation to the
motivation of differential privacy — stable algorithms are desirable even when privacy is not a
concern, such as when the data does not concern humans.
In our analysis, we will make crucial use of the fact that max-KL-stability (as well as the other
notions of stability discussed in Section 4.1)is closed under post-processing.
Lemma 2.4 (Post-Processing). Let W : X n → R and f : R → R0 be a pair of randomized algorithms. If
W is (ε, δ)-max-KL-stable then the algorithm f (W (x)) is (ε, δ)-max-KL-stable.
2.3.1

Stability for Interactive Mechanisms

The definition we gave above does not immediately apply to algorithms that interact with a data
analyst to answer adaptively chosen queries. Such a mechanism does not simply take a sample x
as input and produce an output. Instead, in the interactive setting, there is a mechanism M that
holds a sample x and interacts with some algorithm A. We can view this entire interaction between
M and A as a single noninteractive meta algorithm that outputs the transcript of the interaction
and define stability with respect to that meta algorithm. Specifically, we define the algorithm
W [M, A](x) that simulates the interaction between M(x) and A and outputs the messages sent
between them. The simulation is also parameterized by n, k, Q, although we will frequently omit
these parameters when they are clear from context.

x ∈ Xn

Wn,k,Q [M, A] : X n → (Q × R)k .

Input: A sample
For j = 1, . . . , k
Feed aj−1 to A and get a query qj ∈ Q.
Feed qj to M(x) and get an answer aj ∈ R.
Output ((q1 , a1 ), . . . , (qk , ak )).

Note that W [M, A] is a noninteractive mechanism, and its output is just the query-answer pairs
of M and A in the sample accuracy game, subject to the mechanism being given the sample x.
Now we can define the stability of an interactive mechanism M using W .
Definition 2.5. [Stability of for Interactive Mechanism] We say an interactive mechanism M is
(ε, δ)-max-KL stable for k queries from Q if for every adversary A, the algorithm Wn,k,Q [M, A](x) :
X n → (Q × R)k is (ε, δ)-max-KL stable.
8

2.3.2

Composition of Max-KL Stability

The definition above allows for adaptive composition. This follows directly from composition results
of (ε,
√δ)-differentially private algorithms. A mechanism that is (ε, δ)-max-KL stable for 1 query is
(≈ ε k, ≈ δk)-stable for k adaptively chosen queries [DMNS06, DRV10]. More precisely, for every
0 ≤ ε ≤ 1 and δ, δ0 > 0, if a mechanism that
p is (ε, δ)-max-KL stable for 1 query is used to answer k
adaptively chosen queries, it remains (ε k log(1/δ0 ) + 2ε2 k, δ0 + kδ)-max-KL stable [DRV10].

3

From Max-KL Stability to Accuracy for Low-Sensitivity Queries

In this section we prove our main result that any mechanism that is both accurate with respect to
the sample and satisfies max-KL stability (with suitable parameters) is also accurate with respect
to the population. The proof proceeds in two mains steps. First, we prove a lemma that says that
there is no max-KL stable mechanism that takes several independent sets of samples from the
distribution and finds a query and a set of samples such that the answer to that query on that set
of samples is very different from the answer to that query on the population. In Section 3.2 we
prove this lemma for the simpler case of statistical queries and then in 3.3 we extend the proof to
the more general case of low-sensitivity queries.
The second step is to introduce a monitoring algorithm. This monitoring algorithm will simulate
the interaction between the mechanism and the adversary on multiple independent sets of samples.
It will then output the least accurate query across all the different interactions. We show that if
the mechanism is stable then the monitoring algorithm is also stable. By choosing the number
of sets of samples appropriately, we ensure that if the mechanism has even a small probability
of being inaccurate in a given interaction, then the monitor will have a constant probability of
finding an inaccurate query in one of the interactions. By the lemma proven in the first step, no
such monitoring algorithm can satisfy max-KL stability, therefore every stable mechanism must be
accurate with high probability.

3.1

Warmup: A Single-Sample De-Correlated Expectation Lemma for SQs

As a warmup, in this section we give a simpler version of our main lemma for the case of statistical
queries and a single sample. Although these results follow from the results of Section 3.3 on
general low-sensitivity queries, we include the simpler version to introduce the main ideas in the
cleanest possible setting.
Lemma 3.1. Let W : (X n )T → Q be (ε, δ)-max-KL stable where Q is the class statistical queries
q : X → [0, 1]. Let P be a distribution on X and let x ←R Pn . Then5
E [q(P) | q = W (x)] − E [q(x) | q = W (x)] ≤ eε − 1 + δ.

x,W

X,W

Proof of Lemma 3.1. Before giving the proof, we set up some notation. Let x = (x1 , . . . , xn ). For a
single element x0 ∈ X , and an index i ∈ [n], we use xi→x0 to denote the new sample where the i-th
element of x has been replaced by the element x0 . Let x0 ←R P be independent from x.
5 The notation E [q(P) | q = W (x)] should be read as “the expectation of q(P), where q denotes the output of W (x).”
x,W

That is, the “event” being conditioned on is simply a definition of the random variable q.

9

We can now calculate
E [q(x) | q = W (x)]

x,W

n

1X
E [ q(xi ) | q = W (x)]
=
n
x,W
i=1
n Z
1X 1
=
P [ q(xi ) > z| q = W (x)] dz
n
0 x,W
i=1

Now we can apply max-KL stability:
n

≤

=

1X
n

1

Z

i=1

0

n
1X

ε

n

1
=
n

i=1
n
X

eε P [ q(xi ) > z| q = W (xi→x0 )] + δdz

(by (ε, δ)-max-KL stability)

x,W

!
e · 0 E [ q(xi ) | q = W (xi→x0 )] + δ
x ,x,W

e · 0E

x ,x,W

i=1

= eε · 0 E

h

ε

x ,x,W

h

!
i
q(x ) q = W (x) + δ (the pairs (xi , xi→x0 ) and (x0 , x) are identially distributed)
0

i
q(x0 ) q = W (x) + δ

ε

= e · E [ q(P) | q = W (x)] + δ
x,W

An identical argument shows that
!
E [q(x) | q = W (x)] ≥ e

−ε

x,W

· E [ q(P) | q = W (x)] − δ .
x,W

Therefore, using the fact that |q(P)| ≤ 1 for any statistical query q and distribution P, we have
E [q(P) | q = W (x)] − E [q(x) | q = W (x)] ≤ eε − 1 + δ,

x,W

x,W

as desired.

3.2

Warmup: A Multi-Sample De-Correlated Expectation Lemma for SQs

As a second warmup, in this section we give a simpler version of our main lemma for the case
of statistical queries and multiple samples. That is, we consider a setting where there are many
subsamples available to the algorithm. The multi-sample de-correlated expectation lemma says
that a max-KL stable algorithm cannot take a collection of samples x1 , . . . , xT and output a pair
(q, t) such that q(P) and q(xt ) differ significantly in expectation.
Lemma 3.2. Let W : (X n )T → Q × [T ] be (ε, δ)-max-KL stable where Q is the class statistical queries
q : X → [0, 1]. Let P be a distribution on X and let X = (x1 , . . . , xT ) ←R (Pn )T . Then
E [q(P) | (q, t) = W (X)] − E [q(xt ) | (q, t) = W (X)] ≤ eε − 1 + T δ.

X,W

X,W

10

Proof of Lemma 3.2. Before giving the proof, we set up some notation. Let X = (x1 , . . . , xT ) be a set of
T samples where each sample xt = (xt,1 , . . . , xt,n ). For a single element x0 ∈ X , and a pair of indices
(m, i) ∈ [T ] × [n], we use X(m,i)→x0 to denote the new set of T samples where the i-th element of the
m-th sample of X has been replaced by the element x0 .
We can now calculate
E [q(xt ) | (q, t) = W (X)]

X,W

=

T
X

h
i
E 1{t=m} · q(xm ) (q, t) = W (X)

X,W
m=1
n X
T
X

=

1
n

=

1
n

i
h
E 1{t=m} · q(xm,i ) (q, t) = W (X)

X,W
i=1 m=1
n X
T Z 1
X
i=1 m=1

h
i
P 1{t=m} · q(xm,i ) ≥ z (q, t) = W (X) dz

0 X,W

Now we can apply (ε, δ)-max-KL stability.
n

T

1 XX
≤
n

i=1 m=1

Z

1

0

!
i
e P 1{t=m} · q(xm,i ) ≥ z (q, t) = W (X(m,i)→x0 ) + δ dz
h

ε

X,W

(by (ε, δ)-max-KL stability)
!
n T
i
h
1 XX ε
0
=
e · 0 E 1{t=m} · q(xm,i ) (q, t) = W (X(m,i)→x ) + δ
n
x ,X,W
i=1 m=1
!
n T
h
i
1 XX ε
0
e · 0 E 1{t=m} · q(x ) (q, t) = W (X) + δ
=
n
x ,X,W
i=1 m=1

= eε · 0 E

x ,X,W

h

(the pairs (xm,i , X(m,i)→x0 ) and (x0 , X) are identially distributed)
i
q(x0 ) (q, t) = W (X) + T δ

ε

= e · E [ q(P) | (q, t) = W (X)] + T δ
X,W

≤ E [ q(P) | (q, t) = W (X)] + eε − 1 + T δ
X,W

(since q(P) ∈ [0, 1])

An identical argument shows that
E [q(xt ) | (q, t) = W (X)] ≥ E [ q(P) | (q, t) = W (X)] + (e−ε − 1) − T δ.

X,W

3.3

X,W

A Multi-Sample De-Correlated Expectation Lemma

Here, we give the most general de-correlated expectation lemma that considers multiple samples
and applies to the more general class of low-sensitivity queries.
Lemma 3.3 (Main Technical Lemma). Let W : (X n )T → Q∆ × [T ] be (ε, δ)-max-KL stable where Q∆ is
the class of ∆-sensitive queries q : X n → R. Let P be a distribution on X and let X = (x1 , . . . , xT ) ←R (Pn )T .
Then
E [q(P) | (q, t) = W (X)] − E [q(xt ) | (q, t) = W (X)] ≤ 2(eε − 1 + T δ)∆n.
X,W

X,W

11

We remark that if we use the weaker assumption that W is (eε − 1 + δ)-TV stable, (defined in
Section 4.1), then we would obtain the same conclusion but with the weaker bound of 2T (eε − 1 +
δ)∆n. The advantage of using the stronger definition of max-KL stability is that we only have to
decrease δ with T and not ε. This advantage is crucial because algorithms satisfying (ε, δ)-max-KL
stability necessarily have a linear dependence on 1/ε but only a polylogarithmic dependence on
1/δ .
Proof of Lemma 3.3. Let X0 = (x01 , . . . , x0T ) ←R (Pn )T be independent of X. Recall that each element xt
of X is itself a vector (xt,1 , . . . , xt,n ), and the same is true for each element x0t of X0 . We will sometimes
refer to the vectors x1 , . . . , xT as the subsamples of X.
We define a sequence of intermediate samples that allow us to interpolate between X and X0
using a series of neighbouring samples. Formally, for ` ∈ {0, 1, . . . , n} and m ∈ {0, 1, . . . , T }, define
`,m
n T
X`,m = (x`,m
1 , . . . , xT ) ∈ (X ) by
(
xt,i (t > m) or (t = m and i > `)
`,m
xt,i =
0
xt,i
(t < m) or (t = m and i ≤ `)
By construction we have X0,1 = Xn,0 = X and Xn,T = X0 . Also X0,m = Xn,m−1 for m ∈ [T ]. Moreover,
pairs (X`,t , X`−1,t ) are neighboring in the sense that there is a single subsample, xt such that x`,t
t
0 , t, x`,t = x`−1,t .
and x`−1,T
are
neighbors
and
for
every
t
0
0
t
t
t
For ` ∈ [n] and m ∈ [T ], define a randomized function B`,m : (X n )T × (X n )T → R by
(
q(zt ) − q(zt,−` ) + ∆ t = m
`,m
B (X, Z) =
where (q, t) = W (X),
0
t,m
where zt,−` is the t-th subsample of Z with its `-th element replaced by some arbitrary fixed
element of X .
We can now expand E [q(P) − q(xt ) | (q, t) = W (X)] in terms of these intermediate samples
X,W

and the functions B`,m :
E [q(P) − q(xt ) | (q, t) = W (X)]

X,W

=
=

E0

X,X ,W

 0

q(xt ) − q(xt ) | (q, t) = W (X)

X X
`∈[n] m∈[T ]

≤


`−1,m
q(x`,m
)
−
q(x
)
(q,
t)
=
W
(X)
t
t




`−1,m
q(x`,m
)
−
q(x
)
(q,
t)
=
W
(X)
t
t

X,X ,W

X X
E0

`∈[n] m∈[T ]

=


E0

X,X ,W

X X
E0

`∈[n] m∈[T ]

X,X ,W



  `−1,m

`,m
`−1,m
q(x`,m
)
−
q(x
)
+
∆
−
q(x
)
−
q(x
)
+
∆
(q,
t)
=
W
(X)
t
t
t,−`
t,−`
`−1,m
(By construction, x`,m
t,−` = xt,−` )

=

X X
E0

`∈[n] m∈[T ]

X,X ,W

h
i
B`,m (X, X`,m ) − B`,m (X, X`−1,m )

12

(Definition of B`,m .)

Thus, it suffices to show that

h
i
`,m (X, X`,m ) − B`,m (X, X`−1,m ) ≤ 2(eε − 1 + T δ)∆ for all
E
B
m∈[T ]

P

` ∈ [n]. To this end, we make a few observations.
1. Since q is ∆-sensitive, for every `, m, X, Z, we have 0 ≤ B`,m (X, Z) ≤ 2∆.h Moreover,i since
P
B`,m (X, Z) = 0 whenever W (X) outputs (q, t) with t , m, we have m∈[T ] E B`,m (x, x`,m ) ≤ 2∆.
2. By construction, B`,m (X, Z) is (ε, δ)-max-KL stable as a function of its first parameter X.
Stability follows by the post-processing lemma (Lemma 2.4) since B`,m is a post-processing of
the output of W (X), which is assumed to be (ε, δ)-max-KL stable.
3. Lastly, observe that the random variables X`,m are identically distributed (although they are
not independent). Namely, each one consists of nT independent samples from P. Moreover,
for every ` and m, the pair (X`,m , X) has the same distribution as (X, X`,m ). Specifically, the
first component is nT independent samples from P and the second component is equal to the
first component with a subset of the entries replaced by fresh independent samples from P.
Consider the random variables B`,m (X, X`,m ) and B`,m (X, X`−1,m ) for some ` ∈ [n] and m ∈ [T ].
Using observations 2 and 3, we have
B`,m (X, X`,m ) ∼ B`,m (X`,m , X) ∼(ε,δ) B`,m (X`−1,m , X) ∼ B`,m (X, X`−1,m ),
where ∼ denotes having the same distribution and ∼(ε,δ) denotes having (ε, δ)-max-KL close
distributions.6 Thus B`,m (X, X`−1,m ) and B`,m (X, X`,m ) are (ε, δ)-max-KL close.
Now we can calculate
h
i Z 2∆
h
i
`,m
`−1,m
E0
B (X, X
) =
P0
B`,m (X, X`−1,m ) ≥ z dz
X,X ,W
0 X,X ,W
!
Z 2∆
h
i
ε
`,m
`,m
≤
e · P0
B (X, X ) ≥ z + δ dz
X,X ,W

0

Z

2∆

h
i
B`,m (X, X`,m ) ≥ z dz + 2δ∆
0 X,X ,W
h
i
= eε · E0
B`,m (X, X`,m ) + 2δ∆.

= eε ·

P0

X,X ,W

Thus we have


X

h
i
h
i



E0
B`,m (X, X`−1,m ) ≤ eε · 
E B`,m (X, X`,m )  + 2T δ∆


X,X ,W
X,X,W
m∈[T ]
m∈[T ]
X
h
i
≤
E0
B`,m (X, X`,m ) + 2(eε − 1)∆ + 2∆T δ.
X

m∈[T ]

X,X ,W

Thus we have the desired upper bound on the expectation of

P

m∈[T ] E

h
i
B`,m (X, X`,m ) − B`,m (X, X`−1,m ) .

The corresponding lower bound follows from an analogous argument. This completes the
proof.
6 In the spirit of (ε, δ)-max-KL stability, we say that distributions A and B over R are (ε, δ)-max-KL close if for every
R ⊆ R, P [A ∈ R] ≤ eε · P [B ∈ R] + δ and vice versa.

13

3.4

From Multi-Sample De-Correlated Expectation to Accuracy

Now that we have Lemma 3.3, we can prove the following result that max-KL stable mechanisms
that are also accurate with respect to their sample are also accurate with respect to the population
from which that sample was drawn.
Theorem 3.4 (Main Transfer Theorem). Let Q be a family of ∆-sensitive queries on X . Assume that,
for some α, β ∈ (0, .1), M is
1. (ε = α/64∆n, δ = αβ/32∆n)-max-KL stable for k adaptively chosen queries from Q and
2. (α 0 = α/8, β 0 = αβ/16∆n)-accurate with respect to its sample for n samples from X for k adaptively
chosen queries from Q.
Then M is (α, β)-accurate with respect to the population for k adaptively chosen queries from Q given n
samples from X .
The key step in the proof is to define a monitoring algorithm that takes T separate samples
X = (x1 , . . . , xT ) and for each sample xt , simulates an independent interaction between M(xt ) and
A. This monitoring algorithm then outputs the query with the largest error across all of the
queries and interactions (kT queries in total). Since changing one input to X only affects one of
the simulations, the monitoring algorithm will be stable so long as M is stable, without any loss
in the stability parameter. On the other hand, if M has even a small chance β of answering a
query with large error, then if we simulate T ≈ 1/β independent interactions, there is a constant
probability that at least one of the simulations results in a query with large error. Thus, the
monitor will be a stable algorithm that outputs a query with large error in expectation. By the
multi-sample de-correlated expectation lemma, such a monitor is impossible, which implies that
M has probability ≤ β of answering any query with large error.
Proof of Theorem 3.4. Let M be an interactive mechanism. Let A be an analyst and let P be the
distribution chosen by A. We define the following monitoring algorithm.
W (X) = WP [M, A](X) :
Input: X = (x1 , . . . , xT ) ∈ (X n )T
For t = 1, . . . , T :
Simulate M(xt ) and A interacting, let qt,1 , . . . , qt,k ∈ Q be the queries of A and let
at,1 , . . . , at,k ∈ R be the corresponding answers of M.
Let


(j ∗ , t ∗ ) = arg max errP qt,j , at,j .
j∈[k], t∈[T ]

If at ∗ ,j ∗ − qt ∗ ,j ∗ (P) ≥ 0, let q∗ = qt ∗ ,j ∗ , otherwise let q∗ = −qt ∗ ,j ∗ . (Q∆ is closed under negation.)
Output: (q∗ , t ∗ ).

If M is stable then so is W , and this fact follows easily from the post-processing lemma
(Lemma 2.4):
Claim 3.5. For every ε, δ ≥ 0, if the mechanism M is (ε, δ)-max-KL stable for k adaptively chosen queries
from Q, then for every P and A, the monitor WP,k,Q [M, A] is (ε, δ)-max-KL stable.
14

Proof. If M is (ε, δ)-max-KL stable for k adaptively chosen queries from Q then for every analyst
A who asks k queries from Q, and every t the algorithm W 0 (xt ) that simulates the interaction
between M(xt ) and A and outputs the resulting query-answer pairs is (ε, δ)-max-KL stable. From
this, it follows that the algorithm W 0 (X) that simulates the interactions between M(xt ) and A for
every t = 1, . . . , T and outputs the resulting query-answer pairs is (ε, δ)-max-KL stable. To see this,
observe that if X, X0 differ only on one subsample xt , then for every t 0 , t, xt 0 = x0t 0 and thus the
query-answer pairs corresponding to subsample t 0 are identically distributed regardless of whether
we use X or X0 as input to W .
Observe that the algorithm W defined above is simply a post-processing of these kT queryanswer pairs. That is, (q∗ , t ∗ ) depends only on {(qt,j , at,j }t∈[T ],j∈[k] and P, and not on X. Thus, by
Lemma 2.4, W is (ε, δ)-max-KL stable.


We will use the W with T = 1/β . In light of Claim 3.5 and our assumption that M is (ε, δ)max-KL stable, we can apply Lemma 3.3 to obtain
∗

∗

∗



∗

E [q (P) − q (xt ∗ ) | (q , t ) = W (X)] ≤ 2 e

α/64∆n

X,W

αβ
−1+T
32∆n



∆n ≤ α/8.

(1)

To complete the proof, we show that if M is not (α, β)-accurate with respect to the population
P, then (1) cannot hold. To do so, we need the following natural claim about the output of the
monitor.
h
i
Claim 3.6. P q∗ (P) − aq∗ > α > 1−(1−β)T , and q∗ (P)−aq∗ ≥ 0, where aq∗ is the answer to q∗ produced
X,W

during the simulation.
Proof. Since M fails to be (α, β)-accurate, for every t ∈ [T ],
"
#
P max qt,j (P) − at,j > α > β.
xt ,M j∈[k]

(2)

We obtain the claim from (2) by using the fact that the T sets of query-answer pairs corresponding to
different subsamples x1 , . . . , xT are independent. That is, the random variables maxj∈[k] qt,j (P) − at,j
indexed by t ∈ [T ] are independent. Since q∗ (P) − aq∗ is simply the maximum of these independent
random variables, the first part of the claim follows. Also, by construction, W ensures that
q∗ (P) − aq∗ ≥ 0.

Claim 3.7. If M is (α 0 , β 0 )-accurate for the sample but not (α, β)-accurate for the population, then
E [q∗ (P) − q∗ (xt ∗ ) | (q∗ , t ∗ ) = W (X)] ≥ α/4.

X,W

15

(3)

Proof. Now we can calculate
E [q∗ (P) − q∗ (xt ∗ ) | (q∗ , t ∗ ) = W (X)]

X,W

h
i
h
i
= E q∗ (P) − aq∗ | (q∗ , t ∗ ) = W (X) + E aq∗ − q∗ (xt ∗ ) | (q∗ , t ∗ ) = W (X)
X,W

X,W

h
i
h
i
≥ E q∗ (P) − aq∗ | (q∗ , t ∗ ) = W (x) − E aq∗ − q∗ (xt ∗ ) | q∗ = W (x)
X,W

X,W

h
i
≥ α(1 − (1 − β)T ) − E aq∗ − q∗ (xt ∗ ) | (q∗ , t ∗ ) = W (X)
X,W


 
αβ
≥ α(1 − (1 − β)T ) − α/8 + 2T
∆n
16∆n
≥ α/2 − (α/8 + α/8) = α/4

(Claim 3.6)
(4)
(T = b1/βc.)

Line (4) follows from two observations. First, since M is assumed to be (α/8, αβ/16∆n)-accurate
for one sample, by a union bound, it is simultaneously (α/8, T (αβ/16∆n))-accurate for all of the
T samples. Thus, we have aq∗ − q∗ (xt ∗ ) ≤ α 0 except with probability at most T (αβ/16∆n). Second,
since q∗ is a ∆-sensitive query, we always have aq∗ − q∗ (xt ∗ ) ≤ 2∆n.7
Thus, if M is not (α, β)-accurate for the population, we will obtain a contradiction to (1). This
completes the proof.

4

Other Notions of Stability and Accuracy on Average

Definition 4.2 gives one notion of stability, namely max-KL stability. However, this is by no means
the only way to formalise stability for our purposes. In this section we consider other notions of
stability and the advantages they have.

4.1

Other Notions of Algorithmic Stability

We will define here other notions of algorithmic stability, and in Section 4.2, we will show that such
notions can provide expected guarantees for generalization error which can be used to achieve
accuracy on average.
Definition 4.1 (TV-Stability). Let W : X n → R be a randomized algorithm. We say that W is ε-TV
stable if for every pair of samples that differ on exactly one element,


dTV (W (x), W (x0 )) = sup P [W (x) ∈ R] − P W (x0 ) ∈ R ≤ ε.
R⊆R

Definition 4.2 (KL-Stability). Let W : X n → R be a randomized algorithm. We say that W is
ε-KL-stable if for every pair of samples x, x0 that differ on exactly one element,

 
  P [W (x) = r] 

 ≤ 2ε2
E log 

0
P
(x
)
=
r]
[W
r←R W (x)
7 Without loss of generality, the answers of M can be truncated to an interval of width 2∆n that contains the correct
answer q∗ (xt ∗ ). Doing so will ensure |aq∗ − q∗ (xt ∗ )| ≤ 2∆n.

16

The post-processing property of Max-KL stability (Lemma 2.4 in Section 2.3) also applies to
the two stability notions above.
Lemma 4.3 (Stability Notions Preserved under Post-Processing). Let W : X n → R and f : R → R0 be
a pair of randomized algorithms. If W is {ε-TV, ε-KL, (ε, δ)-max-KL}-stable then the algorithm f (W (x))
is {ε-TV, ε-KL, (ε, δ)-max-KL}-stable.
Relationships Between Stability Notions ε-KL stability implies ε-TV stability by Pinsker’s
inequality. The relationship between max-KL stability defined in Section 2.3 and the above notions
is more subtle. When ε ≤ 1, (ε, 0)-max-KL stability implies ε-KL stability and thus also ε-TV
stability. When ε ≤ 1 and δ > 0, (ε, δ)-max-KL stability implies (2ε + δ)-TV stability. It also implies
that M is “close” to satisfying 2ε-KL stability (cf. [DRV10] for more discussion of these notions).
As in Section 2.3.1, we define TV-stability and KL-stability of an interactive mechanism M
through a noninteractive mechanism that simulates the interaction between M and an adversary
A. The definition for these notions of stability is precisely analogous to Definition 2.5 for max-KL
stability.
As with max-KL stability, both notions above allow for adaptive composition. In fact, ε-TV
stability composes linearly—a mechanism that is ε-TV stable for 1 query is εk-stable for k queries.
The advantage of the stronger notions of KL and max-KL stability
is that they have a stronger
√
composition. A mechanism that is ε-KL stable for 1 query is (ε k)-stable for k queries.

4.2

From TV Stability to Accuracy on Average

In this section we show that TV stable algorithms guarantee a weaker notion of accuracy on average
for adaptively chosen queries.

4.3

Accuracy on Average

In Section 2.2 we defined accurate mechanisms to be those that answer accurately (either with
respect to the population or the sample) with probability close to 1. In this section we define a
relaxed notion of accuracy that only requires low error in expectation over the coins of M and A.
Definition 4.4 (Average Accuracy). A mechanism M is α-accurate on average with respect to the
population for k adaptively chosen queries from Q given n samples in X if for every adversary A,
"
#


P
E
max err qj , aj ≤ α.
Accn,k,Q [M,A] j∈[k]

We will also use a definition of accuracy relative to the sample given to the mechanism:
Definition 4.5 (Sample Accuracy on Average). A mechanism M is α-accurate on average with respect
to samples of size n from X for k adaptively chosen queries from Q if for every adversary A,
"
#


E
max errx qj , aj ≤ α.
SampAccn,k,Q [M,A] j∈[k]

17

4.3.1

A De-Correlated Expectation Lemma

Towards our goal of proving that TV stability implies accuracy on average in the adaptive setting,
we first prove a lemma saying that TV stable algorithms cannot output a low-sensitivity query such
that the sample has large error for that query. In the next section we will show how this lemma
implies accuracy on average in the adaptive setting.
Lemma 4.6. Let W : X n → Q∆ be an ε-TV stable randomized algorithm. Recall Q∆ is the family of
∆-sensitive queries q : X n → R. Let P be a distribution on X and let x ←R Pn . Then
E [q(P) | q = W (x)] − E [q(x) | q = W (x)] ≤ 2ε∆n.

x,W

x,W

Proof. The proof proceeds via a sequence of intermediate samples. Let x0 ←R Pn be independent of
x. For ` ∈ {0, 1, . . . , n}, we define x` = (x1` , . . . , xn` ) ∈ X n by
(
xi i > `
`
xi =
xi0 i ≤ `
By construction, x0 = x and xn = x0 , and intermediate samples x` interpolate between x and x0 .
Moreover, x` and x`+1 differ in at most one entry, so that we can use the stability condition to relate
W (x` ) and W (x`+1 ).
For every ` ∈ [n], we define B` : X n × X n → R by
B` (x, z) = q(z) − q(z−` ) + ∆, where q = W (x).
Here, z−` is z with the `-th element replaced by some arbitrary fixed element of X .
Now we can write
E [q(P) − q(x) | q = W (x)]

x,W

=
=
≤

E0

x,x ,W
n
X
`=1
n
X
`=1

=

X
`∈[n]

=

 0

q(x ) − q(x) | q = W (x)
E0

h
i
q(x` ) − q(x`−1 ) | q = W (x)

E0

h
i
q(x` ) − q(x`−1 ) | q = W (x)

x,x ,W

x,x ,W



 

`
`
`−1
`−1
E0
q(x ) − q(x−` ) + ∆ − q(x ) − q(x−` ) + ∆ q = W (x)

x,x ,W

X
E0

`∈[n]

x,x ,W

h
i
B` (x, x` ) − B` (x, x`−1 ) .

(Since x`−` = x`−1
−` )
(Definition of B)

Thus, to prove the lemma, it suffices to show that for every ` ∈ [n],
E0

x,x ,W

h
i
B` (x, x` ) − B` (x, x`−1 ) ≤ 2∆ε

To complete the proof, we will need a few observations. First, since q is ∆-sensitive, for every
`, x, z, we have 0 ≤ B` (x, z) ≤ 2∆.
18

Second, observe that since W is assumed to be ε-TV stable, by the post-processing lemma
(Lemma 2.4) B` (x, z) is ε-TV stable with respect to its first parameter x.
Finally, observe that the random variables x0 , . . . , xn are identically distributed (although not
independent). That is, every x` consists of n independent draws from P. Moreover, for every `, the
pairs (x, x` ) and (x` , x) are identically distributed. Specifically, the first component is n independent
samples from P and the second component is equal to the first component with a subset of the
entries replaced by new independent samples from P.
Combining, the second and third observation with the triangle inequality, we have


dTV B` (x, x` ), B` (x, x`−1 )






≤ dTV B` (x, x` ), B` (x` , x) + dTV B` (x` , x), B` (x`−1 , x) + dTV B` (x`−1 , x), B` (x, x`−1 )
≤ 0 + ε + 0 = ε.
Using the observations above, for every ` ∈ [n] we have
h
i


E0
B` (x, x` ) − B` (x, x`−1 ) ≤ 2∆ · dTV B` (x, x` ), B` (x, x`−1 ) ≤ 2∆ε.
x,x ,W

Thus we have the desired upper bound on the expectation of B` (x, x` ) − B` (x, x`−1 ). The corresponding lower bound follows from an analogous argument. This completes the proof.
4.3.2

From De-Correlated Expectation to Accuracy on Average

Theorem 4.7. Let Q∆ be the family of ∆-sensitive queries on X . Assume that M is
1. (ε = α/4∆n)-TV stable for k adaptively chosen queries from Q = Q∆ and
2. (α 0 = α/2)-accurate on average with respect to its sample for n samples from X for k adaptively
chosen queries from Q.
Then M is α-accurate on average with respect to the population for k adaptively chosen queries from Q
given n samples from X .
The high level approach of the proof is to apply the Lemma 4.6 to a “monitoring algorithm”
that watches the interaction between the mechanism M(x) and the analyst A and then outputs
the least accurate query. Since M(x) is stable, the de-correlated expectation lemma says that the
query output by the monitor will satisfy q(P) ≈ q(x) in expectation, this implies that even for the
least accurate query in the interaction between M(x) and A, q(P) ≈ q(x) in expectation Thus, if M
is accurate with respect to the sample x, it is also accurate with respect to P.
Proof of Theorem 4.7. Let M be an interactive mechanism and A be an analyst that chooses the
distribution P. We define the following monitoring algorithm. If M is stable then so is W , and this
fact follows easily from the post-processing lemma (Lemma 2.4).
Claim 4.8. For every ε ≥ 0, if the mechanism M is ε-TV stable for k adaptively chosen queries from Q,
then for every P and A, the monitor WP [M, A] is ε-TV stable.
Proof of Claim 4.8. The assumption that M is ε-TV stable for k adaptively chosen queries from Q
means that for every analyst A who asks k queries from Q, the algorithm W 0 (x) that simulates
the interaction between M(x) and A and outputs the resulting query-answer pairs is ε-TV stable.
Observe that the algorithm W defined above is simply a post-processing of these query-answer
pairs. That is, q∗ depends only on q1 , a1 , . . . , qk , ak and P, and not on x. Thus, by Lemma 2.4, for
every P and A, the monitor WP [M, A] is ε-TV stable.
19

W (x) = WP [M, A](x) :
Input: x ∈ X n
Simulate M(x) and A interacting, let q1 , . . . , qk ∈ Q be the queries of A and let
a1 , . . . , ak ∈ R be the corresponding answers of M.


Let j = arg maxj=1,...,k errP qj , aj .
If aj − qj (P) ≥ 0, let q∗ = qj , otherwise let q∗ = −qj . (Q∆ is closed under negation.)
Output: q∗ .

In light of Claim 4.8 and our assumption that M is (α/4∆n)-TV stable, we can apply Lemma 4.6
to obtain


α
E [q∗ (P) − q∗ (x) | q∗ = W (x)] ≤ 2
∆n ≤ α/2.
(5)
4∆n
x,W
To complete the proof, we show that if M is not α-accurate on average with respect to the population
P, then (5) cannot hold.
Claim 4.9. If M is (α/2)-accurate for the sample but not α-accurate for the population, then
E [q∗ (P) − q∗ (x) | q∗ = W (x)] ≥ α/2.

x,W

Proof of Claim 4.9. Using our assumptions, we can calculate as follows.
E [q∗ (P) − q∗ (x) | q∗ = W (x)]

x,W

h
i
h
i
= E q∗ (P) − aq∗ | q∗ = W (x) + E aq∗ − q∗ (x) | q∗ = W (x)
x,W

x,W

h
i
h
i
≥ E q∗ (P) − aq∗ | q∗ = W (x) − E aq∗ − q∗ (x) | q∗ = W (x)
x,W

x,W

h
i
> α − E aq∗ − q∗ (x) | q∗ = W (x)

(6)

≥ α − α/2

(7)

x,W

= α/2.
Line (6) follows from two observations. First, by construction of W , we always have q∗ (P) − aq∗ ≤ 0.
Second, since M is assumed not to be α-accurate on average for the population, the expected value
of |q∗ (P) − aq∗ | > α. Since W ensures that aq∗ − q∗ (P) ≥ 0, we also have that the absolute value of
the expectation of q∗ (P) − aq∗ is greater than α. Line (7) follows from the assumption that M is
(α/2)-accurate on average for the sample.
Thus, if M is not α-accurate on average for the population, we will obtain a contradiction to (5).
This completes the proof.

5

From Low-Sensitivity Queries to Optimization Queries

In this section, we extend our results for low-sensitivity queries to the more general family of
minimization queries. To do so, we design a suitable monitoring algorithm for minimization
20

queries. As in our analysis of low-sensitivity queries, we will have the monitoring algorithm take as
input many independent samples and simulate the interaction between M and A on each of those
samples. Thus, if M has even a small probability of being inaccurate, then with constant probability
the monitor will find a minimization query that M has answered inaccurately. Previously, we had
monitor simply output this query and applied Lemma 3.3 to arrive at a contradiction. However,
since Lemma 3.3 only applies to algorithms that output a low-sensitivity query, we can’t apply it
to the monitor that outputs a minimization query. We address this by having the monitor output
the error function associated with the loss function and answer it selects, which is a low-sensitivity
query. If we assume that the mechanism is accurate for its sample but not for the population, then
the monitor will find a loss function and an answer with low error on the sample but large error on
the population. Thus the error function will be a low-sensitivity query with very different answers
on the sample and the population, which is a contradiction. To summarize, we have the following
theorem.
Theorem 5.1 (Transfer Theorem for Minimization Queries). Let Q = Qmin be the family of ∆-sensitive
minimization queries on X . Assume that, for some α, β ≥ 0, M is
1. (ε = α/128∆n, δ = αβ/64∆n)-max-KL stable for k adaptively chosen queries from Q and
2. (α 0 = α/8, β 0 = αβ/32∆n)-accurate with respect to its sample for n samples from X for k adaptively
chosen queries from Q.
Then M is (α, β)-accurate with respect to the population for k adaptively chosen queries from Q given n
samples from X .
The formal proof is nearly identical to that of Theorem 3.4, so we omit the full proof. Instead,
we will simply describe the modified monitoring algorithm.
W (X) = WP [M, A](X) :
Input: X = (x1 , . . . , xT ) ∈ (X n )T
For t = 1, . . . , T :
Simulate M(xt ) and A interacting, let Lt,1 , . . . , Lt,k ∈ Q be the queries of A and let
θt,1 , . . . , θt,k ∈ R be the corresponding answers of M.
Let (t ∗ , j ∗ ) be


(t ∗ , j ∗ ) = arg max errP Lt,j , θt,j .
j∈[k], t∈[T ]

Let q∗ (x) = errx (Lt ∗ ,j ∗ , θt ∗ ,j ∗ ) (note, by construction, q∗ ∈ Q2∆ , i.e. q∗ is 2∆-sensitive)
Output: (q∗ , t ∗ ).

6
6.1

Applications
Low-Sensitivity and Statistical Queries

We now plug known stable mechanisms (designed in the context of differential privacy) in to
Theorem 3.4 to obtain mechanisms that provide strong error guarantees with high probability for
both low-sensitivity and statistical queries.
21

Corollary 6.1 (Theorem 3.4 and [DMNS06, SU15a]). There is a mechanism M that is (α, β)-accurate
with respect to the population for k adaptively chosen queries from Q∆ where ∆ = O(1/n) given n samples
from X for
p

3/2
 k · log log k · log (1/αβ) 
n ≥ O 

α2
The mechanism runs in time poly(n, log |X |, log(1/β)) per query.
Corollary 6.2 (Theorem 3.4 and [RR10]). There is a mechanism M that is (α, β)-accurate with respect
to the population for k adaptively chosen queries from Q∆ where ∆ = O(1/n) given n samples from X for
log |X | · log k · log3/2 (1/αβ)
n=O
α3

!

The mechanism runs in time poly(|X |n ) per query. The case where ∆ is not O(1/n) can be handled by
rescaling the output of the query.
Corollary 6.3 (Theorem 3.4 and [HR10]). There is a mechanism M that is α-accurate on average with
respect to the population for k adaptively chosen queries from QSQ given n samples from X for

p
 log |X | · log k · log3/2 (1/αβ) 

n = O 

α3
The mechanism runs in time poly(n, |X |) per query.

6.2

Optimization Queries

The results of the Section 5 can be combined with existing differentially private algorithms for
minimizing “empirical risk” (that is, loss with respect to the sample x) to obtain algorithms for
answering adaptive sequences of minimization queries. We provide a few specific instantiations
here, based on known differentially private mechanisms.
6.2.1

Minimization Over Arbitrary Finite Sets

Corollary 6.4 (Theorem 5.1 and [MT07]). Let Θ be a finite set of size at most D. Let Q ⊂ Qmin be the
set of sensitivity-1/n loss functions bounded between 0 and C. Then there is a mechanism M that is
(α, β)-accurate with respect to the population for k adaptively chosen queries from Qmin given


√
 log(DC/α) · k · log3/2 (1/αβ) 


n ≥ O

α2
samples from X . The running time of the mechanism is dominated by O((k + log(1/β)) · D) evaluations
of the loss function.
6.2.2

Convex Minimization

We state bounds for convex minimization queries for some of the most common parameter regimes
in applications. In the first two corollaries, we consider 1-Lipschitz8 loss functions over a bounded
domain.
8 A loss function L : X × Rd → R is 1-Lipschitz if for every θ, θ 0 ∈ Rd , x ∈ X , |L(θ, x) − L(θ 0 , x)| ≤ kθ − θ 0 k .
2

22

Corollary 6.5 (Theorem 5.1 and [BST14]). Let Θ be a closed, convex subset of Rd set such that
maxθ∈Θ kθk2 ≤ 1. Let Q ⊂ Qmin be the set of convex 1-Lipschitz loss functions that are 1/n-sensitive.
Then there is a mechanism M that is (α, β)-accurate with respect to the population for k adaptively
chosen queries from Q given
√

 dk · log2 (1/αβ) 


n = Õ

α2
samples from Q. The running time of the mechanism is dominated by k · n2 evaluations of the gradient
∇L.
Corollary 6.6 (Theorem 5.1 and [Ull15]). Let Θ be a closed, convex subset of Rd set such that
maxθ∈Θ kθk2 ≤ 1. Let Q ⊂ Qmin be the set of convex 1-Lipschitz loss functions that are 1/n-sensitive.
Then there is a mechanism M that is (α, β)-accurate with respect to the population for k adaptively
chosen queries from Q given
√
p

 log |X | · ( d + log k) · log3/2 (1/αβ) 


n = Õ

α3
samples from X . The running time of the mechanism is dominated by poly(n, |X |) and k · n2 evaluations
of the gradient ∇L.
In the next two corollaries, we consider 1-strongly convex9 , Lipschitz loss functions over a
bounded domain.
Corollary 6.7 (Theorem 5.1 and [BST14]). Let Θ be a closed, convex subset of Rd set such that
maxθ∈Θ kθk2 ≤ 1. Let Q ⊂ Qmin be the set of 1-strongly convex, 1-Lipschitz loss functions that are
1/n-sensitive. Then there is a mechanism M that is (α, β)-accurate with respect to the population for k
adaptively chosen queries from Q given

√
 dk · log3/2 (1/αβ) 


n = Õ

α 3/2
samples from X . The running time of the mechanism is dominated by k · n2 evaluations of the gradient
∇L.
Corollary 6.8 (Theorem 5.1 and [Ull15]). Let Θ be a closed, convex subset of Rd set such that
maxθ∈Θ kθk2 ≤ 1. Let Q ⊂ Qmin be the set of 1-strongly convex 1-Lipschitz loss functions that are
1/n-sensitive. Then there is a mechanism M that is (α, β)-accurate with respect to the population for k
adaptively chosen queries from Q given
√
!
!
p
d log k
3/2
n = Õ log |X | · 5/2 + 3 · log (1/αβ)
α
α
samples from X . The running time of the mechanism is dominated by poly(n, |X |) and k · n2 evaluations
of the gradient ∇L.
9 A loss function L : X × Rd → R is 1-strongly convex if for every θ, θ 0 ∈ Rd , x ∈ X ,

L(θ 0 , x) ≥ L(θ, x) + h∇L(θ, x), θ 0 − θi + (1/2) · kθ − θ 0 k22 ,
where the (sub)gradient ∇L(θ, x) is taken with respect to θ.

23

7

An Alternative Form of Generalization and Tightness of Our Results

We now provide an alternative form of our generalization bounds. The following Theorem is
more general than Theorem 3.4 because it says that no max-KL stable procedure that outputs a
low-sensitivity can output a query that distinguishes the sample from the population (not just
max-KL stable procedures that are accurate for the sample).
First we prove the following technical lemma.
Lemma 7.1. Let F be a finite set, f : F → R a function, and η > 0. Define a random variable X on F by
P [X = x] =

eηf (x)
,
C

where

C=

X

eηf (x) .

x∈F

Then
E [f (X)] ≥ max f (x) −
x∈F

1
log |F|.
η

Proof. We have


1
f (x) =
log C + log P [X = x] .
η
Thus
E [f (X)] =

X

P [X = x] f (x)

x∈F

=

X
x∈F

P [X = x]



1
log C + log P [X = x]
η

1
= (log C − H(X)) ,
η
where H(X) is the Shannon entropy of the distribution of X (measured in nats, rather than bits). In
particular,
H(X) ≤ log |support(X)| = log |F|,
as the uniform distribution maximizes entropy. Moreover, C ≥ maxx∈F eηf (x) , whence
maxx∈F f (x). The result now follows from these two inequalities.

1
η

log C ≥

n
Theorem 7.2. Let ε ∈ (0, 1/3), δ ∈ (0, ε/4), and n ≥ ε12 log( 4ε
δ ). Let M : X → Q∆ be (ε, δ)-max-KL
stable where Q∆ is the class of ∆-sensitive queries q : X n → R. Let P be a distribution on X , let x ←R Pn ,
and let q ←R M(x). Then
δ
P [|q(P) − q(x)| ≥ 18ε∆n] < .
ε
x,M

Intuitively, Theorem 7.2 says that “stability prevents overfitting.” It says that no stable algorithm can output a low-sensitivity function that distinghishes its input from the population the
input was drawn from (i.e. “overfits” its sample).
In particular, Theorem 7.2 implies that, if a mechanism M is stable and outputs q that “fits” its
data, then q also “fits” the population. This gives a learning theory perspective on our results.
Proof. Consider the following monitor algorithm W .
We will use the monitor W with T = b/δc. Observe that W only access its input through M
(which is (ε, δ)-max-KL-stable) and the exponential mechanism (which is (ε, 0)-max-KL-stable).
24

W (X) = WP [M](X) :
Input: X = (x1 , . . . , xT ) ∈ (X n )T
Set F = ∅.
For t = 1, . . . , T :
Let qt ← M(xt ), and set F = F ∪ {(qt , t), (−qt , t)}.


Sample (q∗ , t ∗ ) from F with probability proportional to exp ∆ε (q∗ (xt ∗ ) − q∗ (P)) .
Output: (q∗ , t ∗ ).

Thus, by composition and postprocessing, W is (2ε, δ)-max-KL stable. We can hence apply
Lemma 3.3 to obtain


E [q∗ (xt ∗ ) − q∗ (P) | (q∗ , t ∗ ) = W (X)] ≤ 2 e2ε − 1 + T δ ∆n < 8ε∆n.
(8)
X,W

Now we can apply Lemma 7.1 with f (q, t) = q(xt ) − q(P) and η =
E [f (q∗ , t ∗ )] ≥ max f (q, t) −

q∗ ,t ∗

(q,t)∈F

ε
∆

to get

∆
∆
log |F| = max |qt (xt ) − qt (P)| − log(2T ).
ε
ε
t∈[T ]

Combining (8) and (9) gives
"
#
∆
E max |qt (xt ) − qt (P)| − log(2T ) ≤ E [q∗ (xt ∗ ) − q∗ (P) | (q∗ , t ∗ ) = W (X)] < 8ε∆n.
ε
X,W
X,W t∈[T ]

(9)

(10)

To complete the proof, we assume, for the sake of contradition, that M has a high enough
probability of outputting a query q such that |q(P) − q(x)| is large. To obtain a contradiction from
this assumption, we need the following natural claim (analogous to Claim 3.6) about the output of
the monitor.
Claim 7.3. If
δ
P [|q(P) − q(x)| ≥ 18ε∆n] ≥ ,
ε
x,M
then

#


δ T 1
P max |qt (xt ) − qt (P)| ≥ 18ε∆n ≥ 1 − 1 −
≥ .
ε
2
X,W t∈[T ]
"

Thus

"

#

E max |qt (xt ) − qt (P)| ≥ 9ε∆n.

X,W t∈[T ]

Combining (10) and (11) gives
9ε∆n −

∆
log(2T ) ≤ 8ε∆n,
ε

which simiplies to
log(2ε/δ) ≥ log(2T ) ≥ ε2 n.
This contradicts the assumption that n ≥

1
ε2

log( 4ε
δ ) and hence completes the proof.

25

(11)

7.1

Optimality

We now show that our connection between max-KL stability and generalization (Theorem 7.2 and
Theorem 3.4) is optimal.
Lemma 7.4. Let α > δ > 0, let n ≥ α1 , and let ∆ ∈ [0, 1]. Let U be the uniform distribution over [0, 1].
There exists a (0, δ)-max-KL stable algorithm A : [0, 1]n → Q∆ such that if X ←R U n and if q ←R A(X)
then
δ
.
Pr[q(X) − q(U ) ≥ α∆n] ≥
2α
Proof. Consider the following simple algorithm, denoted as B. On input a database x, output x
with probability δ, and otherwise output the empty database. Clearly, B is (0, δ)-max-KL stable.
Now construct the following algorithm A.
Input: A database X ∈ [0, 1]n . We think of X as

1
α

databases of size αn each: X = (x1 , . . . , x1/α ).

For 1 ≤ i ≤ 1/α let x̂i = B(xi ).
Let p : [0, 1] → {0, 1} where p(x) = 1 iff ∃i s.t. x ∈ x̂i .
P
Define qp : [0, 1]n → R where qp (x) = ∆ x∈x p(x) (note that qp is a ∆-sensitive query, and
that it is a statistical query if ∆ = 1/n).
Output: qp .

As B is (0, δ)-max-KL stable, and as A only applies B on disjoint databases, we get that A is
also (0, δ)-max-KL stable.
Suppose X = (x1 , . . . , x1/α ) contains i.i.d. samples from U , and consider the execution of A on X.
Observe that the predicate p evaluates to 1 only on a finite number of points from [0, 1], and hence,
we have that qp (U ) = 0. Next note that qp (X) = α∆n · |{i : x̂i = xi }|. Therefore, if there exists an i s.t.
x̂i = xi then qp (X) − qp (U ) ≥ α∆n. The probability that this is not the case is at most
(1 − δ)1/α ≤ e−δ/α ≤ 1 −
ans thus, with probability at least
α∆n.

δ
,
2α

δ
2α , algorithm A outputs a ∆-sensitive query qp

s.t. qp (X)−qp (U ) ≥

In particular, using Lemma 7.4 with α = ε shows that the parameters in Theorem 7.2 are tight.
Acknowledgements
We thank Mark Bun, Moritz Hardt, Aaron Roth, and Salil Vadhan for many helpful discussions.

References
[BE02]

Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine
Learning Research, 2:499–526, 2002.

[BH95]

Yoav Benjamini and Yosef Hochberg. Controlling the false discovery rate: a practical
and powerful approach to multiple testing. Journal of the Royal Statistical Society. Series
B (Methodological), 57(1):289–300, 1995.
26

[BH15]

Avrim Blum and Moritz Hardt. The ladder: A reliable leaderboard for machine
learning competitions. CoRR, abs/1502.04585, 2015.

[Bon36]

Carlo Emilio Bonferroni. Teoria statistica delle classi e calcolo delle probabilita. Pubbl.
d. R. Ist. Super. di Sci. Econom. e Commerciali di Firenze., 8, 1936.

[BSSU15]

Raef Bassily, Adam Smith, Thomas Steinke, and Jonathan Ullman. More general
queries and less generalization error in adaptive data analysis. CoRR, abs/1503.04843,
2015.

[BST14]

Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In FOCS, pages 464–473. IEEE,
October 18–21 2014.

[BUV14]

Mark Bun, Jonathan Ullman, and Salil P. Vadhan. Fingerprinting codes and the price
of approximate differential privacy. In STOC, pages 1–10. ACM, May 31 – June 3 2014.

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

Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In
PODS, pages 202–210. ACM, June 9-12 2003.

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

[Dun61]

Olive Jean Dunn. Multiple comparisons among means. Journal of the American
Statistical Association, 56:52–64, 1961.

[DW79a]

Luc Devroye and Terry J. Wagner. Distribution-free inequalities for the deleted and
holdout error estimates. IEEE Transactions on Information Theory, 25(2):202–207, 1979.

[DW79b]

Luc Devroye and Terry J. Wagner. Distribution-free performance bounds for potential
function rules. IEEE Transactions on Information Theory, 25(5):601–604, 1979.

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

27

[GL14]

Andrew Gelman and Eric Loken. The statistical crisis in science. American Scientist,
102(6):460, 2014.

[HR10]

Moritz Hardt and Guy Rothblum. A multiplicative weights mechanism for privacypreserving data analysis. In Proc. 51st Foundations of Computer Science (FOCS), pages
61–70. IEEE, 2010.

[HU14]

Moritz Hardt and Jonathan Ullman. Preventing false discovery in interactive data
analysis is hard. In FOCS. IEEE, October 19-21 2014.

[Ioa05]

John P. A. Ioannidis. Why most published research findings are false. PLoS Medicine,
2(8):124, August 2005.

[Kea93]

Michael J. Kearns. Efficient noise-tolerant learning from statistical queries. In STOC,
pages 392–401. ACM, May 16-18 1993.

[KR99]

Michael J. Kearns and Dana Ron. Algorithmic stability and sanity-check bounds for
leave-one-out cross-validation. Neural Computation, 11(6):1427–1453, 1999.

[McS14]

Frank McSherry.
Differential privacy for measure concentration.
Blog
post on “Windows on Theory”. http://windowsontheory.org/2014/02/04/
differential-privacy-for-measure-concentration/, 2014.

[MT07]

Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In
FOCS, pages 94–103. IEEE, Oct 20–23 2007.

[NS15]

Kobbi Nissim and Uri Stemmer. On the generalization properties of differential
privacy. CoRR, abs/1504.05800, 2015.

[RR10]

Aaron Roth and Tim Roughgarden. Interactive privacy via the median mechanism. In
STOC, pages 765–774. ACM, June 5–8 2010.

[SSSS10]

Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research,
11:2635–2670, 2010.

[SU15a]

Thomas Steinke and Jonathan Ullman. Between pure and approximate differential
privacy. CoRR, abs/1501.06095, 2015.

[SU15b]

Thomas Steinke and Jonathan Ullman. Interactive fingerprinting codes and the
hardness of preventing false discovery. In Proceedings of The 28th Conference on
Learning Theory (COLT’15), pages 1588–1628, 2015.

[Ull13]

Jonathan Ullman. Answering n2+o(1) counting queries with differential privacy is hard.
In STOC, pages 361–370. ACM, June 1-4 2013.

[Ull15]

Jonathan Ullman. Private multiplicative weights beyond linear queries. In PODS.
ACM, May 31–June 4 2015.

28

