Generalization in the Face of Adaptivity: A Bayesian Perspective
Authors: Moshe Shenfeld
Katrina Ligett
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Differential Privacy
Adaptive Data Analysis
TL;DR: We provide generalization guarantees under adaptivity that scale with the variance, rather than the range

Abstract: Repeated use of a data sample via adaptively chosen queries can rapidly lead to overfitting, wherein the empirical evaluation of queries on the sample significantly deviates from their mean with respect to the underlying data distribution. It turns out that simple noise addition algorithms suffice to prevent this issue, and differential privacy-based analysis of these algorithms shows that they can handle an asymptotically optimal number of queries.  However, differential privacy's worst-case nature entails scaling such noise to the range of the queries even for highly-concentrated queries, or introducing more complex algorithms.

In this paper, we prove that straightforward noise-addition algorithms already provide variance-dependent guarantees that also extend to unbounded queries. This improvement stems from a novel characterization that illuminates the core problem of adaptive data analysis. We show that the harm of adaptivity results from the covariance between the new query and a Bayes factor-based measure of how much information about the data sample was encoded in the responses given to past queries. We then leverage this characterization to introduce a new data-dependent stability notion that can bound this covariance.

Generalization in the Face of Adaptivity: A Bayesian Perspective
Moshe Shenfeld
Katrina Ligett
Department of Computer Science
Department of Computer Science Federmann Center for the Study of Rationality
The Hebrew University of Jerusalem moshe.. wwwnfeldeneeeeeeeee huji aacjj.ac.... ac.il
The Hebrew University of Jerusalem katrina@ca huji ac.
Abstract
Repeated use of a data sample via adaptively chosen queries can rapidly lead overfitting, wherein the empirical evaluation of queries the sample significantly deviates from their mean with respect to the underlying data distribution. turns out that simple noise addition algorithms suffice prevent this issue, and differential privacy-based analysis of these algorithms shows that they can handle asymptotically optimal number of queries. However, differential privacy's s worst-case nature entails scaling such noise to the range the queries even for highly-concentrated queries, introducing more complex algorithms.
In this paper, we prove that straightforward noise-adding addition algorithms already provide variance-depene dependent guarantees that also extend to unbounded queries. This improvement stems from a novel characterization that illuminates the core problem of adaptive data analysis. We show that the harm of adaptivity results from the covariance between the new query and Bayes factor-based measure of how much information about the data sample queries. We then leverage this characterization to introduce new data-dependent stability notion that can bound this covariance.
encoded in the responses given to past
Introduction
Recent years have seen growing recognition of the role of adaptivity in causing overfitting and thereby reducing the accuracy of the conclusions drawn from data. Intuitively, allowing data analyst to adaptively choose the queries that she issues potentially leads to misleading conclusions, because the results of prior queries might encode information that is specific to the available data sample and not relevant to the underlying distribution from which it was drawn. As a result, future queries might then be chosen leverage these sample-specific properties, giving answers the sample that differ wildly from the values of those queries on the data distribution. Such adaptivity has been blamed, in part, for the current reproducibility crisis in the data-driven sciences [loannidis] 2005 Gelman and Loken 2014].
A series of works catalyzed by Dwork et al. 2015 recently established formal framework for understanding and analyzing adaptivity in data analysis, and introduced general toolkit for provably preventing the harms of choosing queries adaptively- that is, function of the results of previous queries. This line of work has established that enforcing that computations obey a constraint of differential privacy (Dwork et al. -wiich one can interpret requirement on computations provably limits the extent to which adaptivity can cause overfitting. Practically, for simple numerical computations, these results translate into adding level of noise to the query results that would be sufficient to ensure worst-case stability of the worst-case query on the worst-case dataset. In particular, when analyzed using differential privacy, simple noise-addition
robustness stability
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

mechanisms must add noise that scales with the worst-case change in query value that could be induced by changing a single input data element, in order to protect against adaptivity.
However, this can be overkill: for the purposes of statistical validity, we do not care about the worst case but the typical case. In the present work, we prove the following new and better generalization guarantees for simple Gaussian noise-addition algorithms:
Theorem 1.1 (Informal versions of main theorems). With probability > 1- 8, the error of the
responses produced by mechanism which only adds Gaussian noise to the empirical values of the queries it receives is bounded by c, even after responding to k adaptively chosen queries, if
the range of the queries is bounded by A, their variance is bounded by o², and the size of the dataset n. = S2 (max { (
vi- ( (Theorem 5.1 or
the queries are
and the size of the dataset Q (0"y In
Kd (Theo-
de
rem 5.3
In contrast, analyzing the same mechanism using differential privacy yields a sample size requirement
that scales with n Ω A A
in the first setting, and provides no guarantee in the latter.
We prove these theorems via a new notion, pairwise concentration (PC) (Definition captures the extent to which replacing one dataset by another would be "noticeable," given a particular query-response sequence. This is thus function of particular differing datasets (instead of worst-case over elements), and it also depends (Theorem 4.4) that allows us to track PC losses over multiple computations. The PC notion allows for more careful analysis of the information encoded by the query-responee sequence than differential privacy does.
which
the actual issued queries. We then build a composition toolkit
In order to leverage this more careful analysis of the information encoded in query-response sequences, we rely on a simple new characterization (Lemma 3.5) that shows explicitly that the harms of adaptivity come from the covariance between the behavior of the future queries and a Bayes factor- based measure of how much information about the data sample was encoded in the responses to the issued queries. Our characterization gives insight into how differential privacy protects against adaptivity, and then allows us to step away from this worst-case approach. What differential privacy accomplishes is that it bounds worst-case version of the Bayes factor; however, this new characterization makes clear, it is sufficient to bound the "typical" Bayes factor in order to avoid overfitting.
We measure the harm that past adaptivity causes to a future query by considering the query as evaluated posterior data distribution and comparing this with its value prior. The prior is the true data distribution, and the posterior is induced by observing the responses to past queries and updating the prior. If the new query behaves similarly on the prior distribution it does this posterior (a guarantee we call Bayes stability. Definition 3.3), adaptivity has not led us too far astray [ If furthermore, the the response given by the mechanism is close to the query result on the posterior, then by triangle inequality argument, that mechanism is distribution accurate. This type of triangle inequality first appeared an analysis technique in Jung al. 2020
The dependence of our PC notion on the actual adaptively chosen queries places it in the so-called fully-adaptive setting [Rogers al. 2016 Whitehouse et al. 2023), which requires a fairly subtle analysis involving set of tools and concepts that may be of independent interest. In particular, we establish a series of "dissimilarity" notions in Appendix B which generalize the notion of divergence, replacing the scalar bound with a function. Our main stability notion (Definition 4.2) can be viewed an rastance-tailored variant of zero-concentrated differential privacy (Bun and Steinke 2010), and we also make use of a similar extension of the classical max-divergence- differential privacy definition B.8
Related work Differential privacy [Dwork et al. 2006 is a privacy notion based on a bound on the max divergence between the output distributions induced by any two neighboring input
'This can be viewed as a generalization of the Hypothesis Stability notion of Bousquet and Elisseeff 2002
which was proven to guarantee on average generalization (Shalev-Shwartz et al. 2010 where the hypothesis is post-proccee processing of the responses past queries, and the future query is the loss function estimation.

---

datasets (datasets which differ in one element). One natural way to enforce differential privacy is by directly adding noise to the results of a numeric-valued query, where the noise is calibrated to the global sensitivity of the function to be computed the maximal change in its value between any two neighboring datasets. Dwork et al. 2015] and [Bassily et al. [02T]] showed that differential privacy
also useful as tool for ensuring generalization in settings where the queries are chosen adaptively.
Differential privacy essentially provides the optimal asymptotic generalization guarantees given adaptive queries [[ardt and Ullman 2014 Steinke and Ullman [015]] However, its optimality is for worst-case adaptive queries, and the guarantees that offers only beat the naive intervention of splitting a dataset so that each query gets fresh aata-when the imput dataset is quite huge [Jung et al., 2020]. A worst-case approach makes sense for privacy, but for statistical guarantees like generalization we only need statements that hold with high probability with respect to the sampled dataset, and only on the actual queries issued.
One cluster of works that steps away from this worst-case perspective focuses on giving privacy guarantees that are tailored the dataset hand (Nissim et al. 2007 Ghosh and Roth 2011 Ebadi et al., 2015 Wang 2019]. In Feldman and Zrnic [202] in particular, the authors elegantly manage to track the individual privacy loss of the elements in the dataset. However, their results do not enjoy a dependence on the standard deviation in place of the range of the queries. Several truncation-basl based specialized mechanisms have been proposed, both to provide differential privacy guarantees for Gaussian and aab-Guusiian queries even in the case of multivariate distribution with unknown covariance (Karwa and Vadhan 2018 Ashtiani and Liaw 2022 Duchi et al.) 2023] and,
remarkably, design specialized algorithms that achieve adaptive data analysis guarantees that scale like the standard deviation of the queries [Feldman and Steinke 2017]. Recently, [Blanc| (2023) proved that randomized rounding followed by sub-sampling provides accuracy guarantees that scale with the queries' variance. But none of these results apply to simple noise addition mechanisms.
Another line of work Gehrke et al. [2012). Bassily et al. [2013), Bhaskar et al. (20TT) proposes relaxed privacy definitions that leverage the natural noise introduced by dataset sampling achieve more average-cass notions of privacy. This builds on intuition that average-case privacy can be viewed from a Bayesian perspective, by restricting some distance measure between some prior distribution and some posterior distribution induced by the mechanism's 's behavior (Dwork et al. 2006 Kasiviswanathan and Smith 2014). This perspective was used [Shenfeld and Ligett| 2019 to propose a stability notion which is both necessary and sufficient for adaptive generalization under several assumptions. Unfortunately, these definitions have best extremely limited adaptive composition guarantees. [assily and Freund 2016) connect this Bayesian intuition to statistical validity via typical stability, an approach that discards "unlikely" databases that do not obey a differential privacy guarantee, but their results require sample size that grows linearly with the number of queries even for iid distributions. [riistcyn and Faltings [2020) propose the notion of Bayesian differential privacy which leverages the underlying distribution to improve generalization guarantees, but their results still scale with the range in the general case.
An alternative route for avoiding the dependence on worst case queries and datasets was achieved using expectation based stability notions such as mutual information and KL. stability Russo and Zou 2 Bassily et al. [202T]. [Steinke and Zakynthinou 2020]. Using these methods Feldman Feldman and Steinke (2018) presented natural noise addition mechanism, which adds noise that scales
with the empirical variance when responding to queries with known range and unknown variance.
Unfortunately, in the general case, the accuracy guarantees provided by these methods hold only for the expected error rather than with high probability.
detailed comparison to other lines of work can be found in Appendix
2 Preliminaries
2.1 Setting
We study datasets, each of fixed size E N, whose elements are drawn from some domain X.. We assume there exists some distribution Dxn defined over the datasets & E x 2 We consider a family
Throughout the paper, the notation D (-) describing a distribution over a domain, will either represent the probability mass function defined by discrete probability over countable sample space or the probability density function (the Radon -iikody derivative) in case of measure over measurable spaces.
3

---

of functions (queries) Q of the form x" - R S R. We refer to the functions' outputs as responses
We denote by q (Dxx)) == S~Dxy la (S)) the mean of with respect to the distribution Dx and
think of it as the true value of the query q. which we wish to estimate. As is the case in many machine learning or data-driven science settings, we do not have direct access to the distribution over datasets, but instead receive a dataset sampled from Dx=, which can be used to compute (s)-the the empirical value the query.
A mechanism M is (possibly non-deterministic) function M A x Q x θ - R which, given a dataset X²,, query q E Q, and some auxiliary parameters E R (we omit 0 when not in use). The most trivial mechanism would simply return we will consider mechanisms that return a noisy version of q (s). A mechanism induces distribution R| (-1s) indicating the probability that each response r will be the output of the mechanism, given 8, and 0 as input. Combining this with Dx induces the marginal distribution D% over the responses, and the conditional distribution xx (-Ir) over sample sets. Considering the uniform distribution over elements in the sample set induces similar distributions over the elements Dx and D = D (- (r)). This last distribution, D", is central our analysis, and it represents the posterior distribution over the sample elements given an observed response Bayesian update with respect prior of Dx All of the distributions discussed in this subsection are more formally defined in Appendix
O, provides some response
(s), but
over the responses D8.0
An analyst A is a (possibly non-deterministic) function A : R + (2, +) which, given a sequence of responses, provides a query and parameters be asked next. interaction between mechanism and an analyst- wherein repeatedly (and potentially adaptively) the analyst generates query, then the mechanism generates a response for the analyst to observe generates sequence of le queries and responses for some & E N, which together we refer to as a view = (2.,,2,.... 7k) omit when it is clear from context). In the case of non-deterministic analyst, we add its coin tosses as the first entry in the view, in order to ensure each (4s, 0:) is deterministic function of 44-1, as detailed in Definition A.. given a view u E V, we denote by Ze the sequence of queries that it induces. Slightly abusing notation, we denote v = M (s, A). The distributions D R| D
E V (we
x= R. and Dr naturally extend to versions where sequence of queries is generated by an analyst: x Dú, 2 y, and D D (-1v).
Notice that M holds s but has no access D. On the other hand, A might have access to D, but her only information regarding comes from M 's responses as represented by D". This intuitively turns some metric of distance between D and D into a measure of potential overfitting, an intuition that we formalize in Definition 3.3 and Lemma 5.5
2.2 Notation
Throughout the paper, calligraphic letters denote domains (c.g.. X'), lower case letters denote elements of domains (e.g.. x E X"), and capital letters denote random variables (e.g., X Dx))
We omit most superscripts and subscripts when clear from context (e.g., D (r] D (r () is the probability to receive r E R as response, conditioned on particular input dataset 8, given query g and parameters 0). Unless specified otherwise, we assume Dx n, k, and are fixed, and omit them from notations and definitions.
We use ||=|| to denote the Euclidean norm, so 11 (x)] V (gs (z))² will denote the norm of concatenated sequence of queries.
2.3 Definitions
We introduce terminology to describe the accuracy of responses that mechanism produces in response to queries.
Moost of the definitions and claims in this paper can be extended beyond R and the Euclidean norm. To do so, the divergence in Lemma 3.5 the yp function (Definition 4.2) must be chosen accordingly.

---

Definition 2.1 (Accuracy of mechanism). Given a dataset an analyst A, and view M (s, A). we define three types of output error for the mechanism: sample error errs (8, = max Ir 4 (s)1, distribution error erpp (s, v) = max ri 2i (D),, and posterior iE(k]
iE
error emp (8, v) max |r (D"),, where qi is the ith query and r; is the ith response in v.
iE|
These errors can be viewed random variables with distribution that is induced by the underlying distribution D and the internal randomness of and A. Given 6, 2 0 we call mechanism M (e, 8) sampleddistribution//nnn
accurate with respect to A if
Pr S~DDM,VVMMSA.
[(err (S,
c) s 6,
for err = errg/errp/er'p respectively.
Notice that if each possible value of e has a corresponding 6, then is essentially a function of e. Given such a function 5: IR+ 00, 1]. will say the mechanism is (e, 5 (e)) accurate, perspective which will be used in Lemma
We start by introducing a particular family of queries known as linear queries, which will be used to state the main results in this paper, but it should be noted that many of the claims extend to arbitrary queries as discussed Section G.2
Definition 2.2 (Linear queries). function g 2 + R is linear query if is defined by function
X + IR such that q (s) = + qi (s:). For simplicity, we denote qı as throughout.
The aforementioned error bounds implicitly assume some known scale of the queries, which is usually chosen to be their range, denoted by A, = sup 1g (x) (v)l (we refer to such query x.yÊX
A A-bounded). This poses issue for concentrated random variables, where the "typical" range can be arbitrarily smaller than the range, which might even be infinite. A natural alternative source of scale we consider in this paper is the query's variance of
E
[X) 9 (Dx))² or its
X-
variance proxy in the case of a sub-Gaussian query (Definition 5.2 for arbitrary queries are presented in Section C.2
The corresponding definitions
Our main tool for ensuring generalization is the Gaussian mechanism, which simply adds Gaussian noise to the empirical value of a query.
Definition 2.3 (Gaussian mechanism). Given 17 >> 0 and a query q, the Gaussian mechanism with noise parameter 1) returns its empirical mean q (s) after adding a random value, sampled from an unbiased Gaussian distribution with variance 7/² Formally, M (s, q) N (g(s)
Analyzing adaptivity-driven overfitting
In this section, we give a clean, new characterization of the harms of adaptivity. Our goal is bound the distribution error of a mechanism that responds to queries generated by an adaptive analyst. This bound will be achieved via triangle inequality, by bounding both the posterior accuracy and the Bayes stability (Definition 3.3 Missing proofs from this section appear in Appendix C
The simpler part of the argument is posterior accuracy. which prove can be inherited directly from the sample accuracy the advantage of being independent of the range of the queries.
mechanism. This lemma resembles Lemma in Jung et al. 2020) but has
Lemma 3.1 (Sample accuracy implies posterior accuracy). Given a function ò: R [0, and an analyst A, if mechanism M is (e, 8 (e)) (s))-sample accurate for all e O, then M is (e, 8' (e)))pooterria)
accurate for 8' (e) = inf (1 SC 5 (1) (1)
ÇE(O.c)
We this lemma provide accuracy guarantees for the Gaussian mechanism.
'In the case of an adaptive process, one can also consider the case where are adaptively chosen by the analyst and provided to the mechanism the auxiliary parameter O:.
5

---

Lemma 3.2 (Accuracy of Gaussian mechanism). Given 1) > O, the Gaussian mechanism with noise parameter that receives k queries is (e, -sample accurate for 6 (c) 2n² and
2
(c, 6 -costtrot accurate for 5 (c) = 4k 407
In order to complete the triangle inequality, we have define the stability of the mechanism. Bayes stability captures the concept that the results returned by mechanism and the queries selected by the adaptive adversary are such that the queries behave similarly on the true data distribution and on the posterior distribution induced by those results. This notion first appeared in Jung et al. (2020). under the name Posterior Sensitivity, as did the following theorem.
Definition 3.3 (Bayes stability). Given 6, 6 0 and analyst A, we say M is (e, BBaayes stable with respect to A, if
Pr Swp (S)
[10(D") Q > S.
Bayes stability and sample accuracy (implying posterior accuracy) combine via triangle inequality to give distribution accuracy.
Theorem 3.4 (Generalization). Given two functions 81 : R + [0, 82 R + [0, 1], and an analyst
A, if mechanism M is (c, 81 (c))-Bayes stable and (c, 82 (c)) Jsample accurate with respect to A, then
M is (e,8' (e))-distiibution accurate for 8' (c) <'E(0..)&E(0.Cc-)))
inf
61 (c) + - 52 (t) (t)dt) dt..
Since achieving posterior accuracy is relatively straightforward, guaranteeing Bayes stability is the main challenge in leveraging this theorem to achieve distribution accuracy with respect to adaptively chosen queries. The following lemma gives a useful and intuitive characterization of the quantity that the Bayes stability definition requires be bounded. Simply put, the Bayes factor K (.s-) (defined in the lemma below) represents the amount of information leaked about the dataset during the interaction with an analyst, by moving from the prior distribution over data elements to the posterior induced by some view The degree to which query q overfits the dataset is expressed by the correlation between the query and that Bayes factor. This simple lemma is at the heart of the progress that we make in this paper, both in intuitive understanding of adaptive data analysis, and in the concrete results we show in subsequent sections. Its corresponding version for arbitrary queries are presented in Section e
Lemma 3.5 (Covariance stability). Given view E V and linear query q.
a (D") q (Dx) Cov (a X~Dx (X)),((X,) ( (X,
Furthermore, given A, o >
sup Q A, <3
- (Dx) = Div(D"
and
(1())) - -0xx) D (De (D*)
sup T s.f. 53
where K uI
is the Bayes factor of x given v (and vice-versa). Drv is the total variation distance (Definition B. and Dya is the chi-square divergence (Definition B.2
D(u m) D(a)
D(e)
Proof. By definition, (D*)
= E
(x)] = E [K (X, XND
(X)),
X X~D"
(D*) = E X-D
E X
[ (X,
E
[g (X)
Coy (x), K (X)
X
X~D
The second part is direct result of the known variational representation of total variation distance and x2 divergence, which are both f-divergences (see Equations 7.88 and 7.91 in Polyanskiy and Wu 2022 for more details).

---

Using the first part of the lemma, we guarantee Bayes stability by bounding the correlation between specific q and K (-. u) as discussed in Section The second part of this Lemma implies that bounding the appropriate divergence is necessary and sufficient for bounding the Bayes stability of the worst query in the corresponding family, which how the main theorems of this paper are all achieved, using the next corollary.
Corollary 3.6. Given an analyst A, for any > O we have
Pr Swatn) (=.
[1Q(D") - (D) > σQ S
Pr 8-D(H) (8,((
DDx > E
The corresponding version of this corollary for bounded range queries provides an alternative proof to the generalization guarantees of the the LS stability notion (Shenfeld and Ligett 2019
4 Pairwise concentration
In order to leverage Lemma 3.5
we need a stability notion that implies Bayes stability of query responses in manner that depends the actual datasets and the actual queries (not just the worst case). In this section we propose such a notion and prove several key properties of it. Missing proof' from this section can be found Appendix D
We start by introducing a measure the stability loss of the mechanism.
Definition 4.1 (Stability loss). Given two sample sets 8, s' X", query q. and a response E R. we denote by by s';r) = In (we omit q from notation for simplicity) Notice that if R M (5, q). the stability loss defines random variable. Similarly, given two elements y E X, we denote & (ær, y: == In (D(rla) and (Drl
D*(r(=) the stability loss of between 8 and s' for De([(s
L (x: = In [D(l=)) This definition extends to views as well.
Next we introduce a notion of a bound on the stability loss, where the bound is allowed to depend on the pair of swapped inputs and the issued queries.
Definition 4.2 (Pairwise concentration). Given a non-negative function p: X x x R which is symmetric in its first two arguments, mechanism M will be called --Pairwise Concentrated (or PC, for short), if for any two datasets s, s' E X and E Q, for any a 2 o
E
exp (a (a p (s, (s, [exp ((a 1) e ss [))) S
(
Given non-negative function yp X x X x xV R which is symmetric in its first two arguments and an analyst A, mechanism M will be called y -aPaiiiss Concentrated with respect to A, if for any s, s E d and a 2 0,
op -op V(,((s
E
1
We refer to such a function yp a similarity function over responses views, respectively.
The similarity function serves as a measure of the local sensitivity of the issued queries with respect to the replacement of the two datasets, by quantifying the extent to which they differ from each other with respect to the query q. The case of noise addition mechanisms provides a natural intuitive interpretation, where the ip scales with the difference between q (s) and q (s'), which governs how much observing the response r distinguishes between the two datasets, as stated in the next lemma.
We note that the first part of this definition can be viewed as a refined version of zCDP (Definition B.18). where the bound on the Rényi divergence (Definition B.5 a function of the sample sets
'This quantity sometimes referred to as privacy loss the context of differential privacy, or information density in the context of information theory.
'The requirement for the range a might appear somewhat counter-intuitive. and results from the fact that jo provides simultaneously bound on the stability loss random variable's mean (the (a 1) coefficient) and variance proxy (the (a 1)² coefficient), discusses in Definitions B.17 B.18
7

---

and the query. As for the second part, since the bound depends on the queries, which themselves are random variables, it should be viewed as bound on the Rényi dissimilarity notion that we introduce in the appendix (Definition B.9 This kind of extension is not limited to Rényí divergence,
as discussed in Appendix B
Lemma 4.3 (Gaussian mechanism is PC). Given rj > and an analyst A, if M is Gaussian mechanism with noise parameter 7,, then it is q-PC for yp (8,8':9) (a())-a(d'))* and y-PP with 2n/"
respect to for (s, s/; =
2qp
To leverage this stability notion in an adaptive setting, must hold under adaptive composition, which we prove in the next theorem.
Theorem 4.4 (PC composition). Given k E N. similarity function over responses and an analyst A issuing k queries, if a mechanism M PpPPC, then it is G-PC with respect to A, where 4 (8, (8))) = E ip (s,5';4:)
Before we state the stability properties of PC mechanisms, we first transition to its element-wise version, which while less general than the original definition, is more suited for our use.
Lemma 4.5 wiss PC). Given similarity function and analyst A. if mechanism M that is PpPC with respect to receives an iid sample from X",, then for any two elements I, E X and 0 2 1 have
E V- 2)
(exp ((a app (2. v))) 1
and
E V~D(-12)
(exp ((a (f axp (z; V))i < 1,
where =p (z)
sup SEX
(p ((s,, 2) (s. v): :))) and 4 (x; = In E yun
(evla.ro1)).
Finally, we bound the Bayes stability of PC mechanisms.
Theorem 4.6 (PC stability). Given a similarity function over views ip and an analyst A, if mechanism M that is Pp-PC with respect A receives iid sample from X then for any e, 5 > V)), we have
(4p (X;V). X=D.S-((m) V~M((SAA)
E
Pr SNDDO (-M(S.A).G-AV))
1IQ - Q(Dx)) ooe
27 (2T
2
e
Pr B-D(U)
E
>1
+
0
XnD
V=M(t.A)
where yp (z; v) is as defined in Lemma
4.5
An exact version of the bound can be found in Theorem D.10
Proof outline. From Corollary 3.6
Pr
-1x))) > ooe <
Pr g-pio) V-M(8.A)
D (D* > e..
V.M(G.A).Q-AVV)
Denoting e (1;1) = (x; 4 (b) (40 (x; Φ), this can bounded by
E X [ -1) 1)²
22
(011x:)
2
D D
JE X
B=D())
swp()) V*-M(S.A)
V~A((B.A)
We then show via algebraic manipulation that this second term can be bounded using the inequality
(ceXx - {)²} <3 X
-1). -
XwD
8

---

and, recalling the definition of the chi square divergence between P and Q (Definition B x (PIIQ) = x-D;
- (oxx) -
-
the first term can be bounded using Markov's incquality followed by the Cauchy-Schwarz -chwwazz inequality by the term:
(D(VIXX)
D(V) - -1 ((()) ((X, V))
2
E
e² SwNt) V-M(S.A)
(DVVXX)
9 +1 11
I x2
E
( D(V)
Pr
[(X E (s))
X=DDsmD(n) Vini(S.A)
where B (e)
(a,, XX In
D(vl=)) D(v)
(x: v):
We then bound the quantity by O (e*), and we bound by O ) which completes the proof.
(o))
Combining this theorem with Theorem 3.4 we get that PC and sample accuracy together imply distribution accuracy.
Variance-based generalization guarantees for the Gaussian mechanism
In this section we leverage the theorems of the previous sections to prove variance-basel general- ization guarantees for the Gaussian mechanism under adaptive data analysis. All proofs from this section appear in Appendix
first provide generalization guarantees for bounded queries.
Theorem 5.1 (Generalization guarantees for bounded queries). Given k E N; A, 2;, e)
1, and an analyst A issuing A-bounded linear queries with variance bounded by 0², if M is
Gaussian mechanism with noise parameter = 0
that receives an iid dataset of size
n= mmxx
A o2 (
In
then M is (e, dedisttriibnnnnnnnn accurate.
An exact version of the bound be found in Theorem E.4
This theorem provides sigmificant improvement over similar results that were achieved using differen- tial privacy (see. e.g., Theorem 13 in Jung al. (020). which is defined for A 1), by managing to replace the A term with o². The remaining dependence on is inevitable. in the sense that such dependence is needed even for non-adan non-adaptive analysis. This improvement resembles the improvement provided by Bernstein's 's inequality over Hoeffding's inequality.
This generalization guarantee, which nearly avoids dependence on the range of the queries, begs the question whether is possible to extend these results to handle unbounded queries. Clearly such a result would not be true without some bound the tail distribution for single query, we focus in the next theorem on the case Gob-Gaussian queries. Formally, we will consider the case where q (X) q (D) is sub-Gaussian random variable, for all queries.
Definition 5.2 Sub-Gaussiian random variable). Given a > 0, random variable X E IR will be have E [e^X| < <
called oassub-Gaussion if for any
We can now state our result for unbounded queries.
Theorem 5.3 (Generalization guarantees for aab-Gaussian queries). Given k E N: o,e o, 0 8 < L and analyst A issuing & o² subbGaussian linear queries, if M is Gaussian mechanism
with noise parameter 1 θ VI
that receives an iid dataset of size n S ( Teln kg
then M is (e, distribbutio accurate.

---

An exact version of the bound can be found in Theorem E.10
These results extend to the case where the variance (or variance proxy) of each query qi is bounded by unique value of by simply passing this value to the mechanism auxiliary information and scaling the added noise T/ accordingly. Furthermore, using this approach we can quantify the extent to which incorrect bounds affect the accuracy guarantee. Overestimating the bound a query's variance would increase the error of the response to this query by a factor of square root of the ratio between the assumed and the correct variance, while the error of the other responses would only decrease. On the other hand, underestimating the bound on a query's s variance would only decrease the error of the response to this query, while increasing the error of each subsequent query by factor of the square root of the ratio between the assumed and the correct variance, divided by the number of subsequent queries. A formal version of this claim can be found in Section
Discussion
The contribution of this paper is two-fold. In Section we provide a tight measure of the level of overfitting of some query with respect to previous responses. In Sections g and 5 a toolkit to utilize this measure, and use it to prove new generalization properties of fundamental noise-addition mechanisms. The novelty of the PC definition stems replacing the fixed parameters that appear in the differential privacy definition with a function of the datasets and the query. The definition presented in this paper provides a generalization of zero-concentrated differential privacy, and future work could study similar generalizations of other privacy notions, as discussed in Section B4
we demonstrate
One small extension of the present work would be to consider queries with range R. would also be interesting extend our results to handle arbitrary normed spaces, using appropriate noise such as perhaps the Laplace mechanism. It might also be possible to relax our assumption that data elements are drawn iid to a weaker independence requirement. Furthermore, it would be interesting to explore an extension from linear queries to general sen-ieiitivviy queries.
We hope that the mathematical toolkit that we establish in Appendix B to analyze our stability notion may find additional applications, perhaps also in context of privacy accounting. Furthermore, the max divergence can be generalized analogously to the "dynamic" generalization of Rényi divergence proposed in this paper (B.9). perhaps suggesting that this approach may be useful in analyzing other mechanisms as well.
Our Covariance Lemma overfitting- bounding the Bayes factor term, which induces a bound on 14 (D") q (D) as we do in this work, or by bounding the correlation between q and K (-vv) This second option suggests interesting directions for future work. For example, to capture an analyst that is non-worst-coe the sense that she "forgets" some of the information that she has learned about the dataset, both the posterior accuracy and the Bayes stability could be redefined with respect to the internal state of the analyst instead of with respect the full view. This could allow for improved bounds in the style of Zrnc and Hardt [2019).
shows that there two possible ways avoid adaptivity-
in
Acknowledgments and Disclosure of Funding
We gratefully acknowledge productive discussions with Etam Benger, Vitaly Feldman, Yosef Rinott, Aaron Roth, and Tomer Shoham. This work was supported in part by a gift to the McCourt School of Public Policy and Georgetown University, Simons Foundation Collaboration 733792, Israel Science Foundation (ISF) grant 2861/20, and a grant from the Israeli Council for Higher Education. Shenfeld's work also partly supported by the Apple Scholars in AI/M PhD Fellowship. Part this work was completed while Ligett was visiting Princeton University's 's Center for Information Technology Policy.
References
Hassan Ashtiani and Christopher Liaw. Private and polynomial time algorithms for learning gaussians and beyond. In Conference on Learning Theory, pages 1075-1076. PMLR, 2022.
10

---

Raef Bassily and Yoav Freund. Typical stability. arXiv preprint arXiv:1604.0333 2016.
Raef Bassily, Adam Groce, Jonathan Katz, and Adam Smith. Coupled-worids privacy: Exploiting adversarial uncertainty statistical data privacy, In IEEE Symposium on Foundations of Computer Science, pages 439-448, 2013.
Racf Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. SIAM Journal on Computing, 2021.
Raghay Bhaskar, Abhishek Bhowmick, Vipul Goyal, Srivatsan Laxman, and Abhradeep Thakurta. Noiseless database privacy. In International Conference on the Theory and Application of Cryptol- ogy and Information Security, pages 215-232. Springer, 2011
Guy Blanc. Subsampling suffices for adaptive data analysis. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 999-1012, 2023.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
Mark Bun and Thomas Steinke. Concentrated differrnniial privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635-658. Springer, 2016.
Konstantinos Chatzikokolakis, Miguel E Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi. Broadening the scope of differential privacy using metrics. In Privacy Enhanc- ing Technologies: 13th International Symposium, PETS 2013, Bloomington, IN, USA, July 10-12. 12, 2013. Proceedings 13, pages 82-102. Springer, 2013.
Elbert Du and Cynthia Dwork. Improved generalization guarantees in restricted data models. In 3rd Symposium on Foundations of Responsible Computing, 2022.
John C. Duchi, Saminul Haque, and Rohith Kuditipudi. A fast algorithm for adaptive private mean estimation. ArXiv, abs/2301.07077 2023.
Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv:1603.01887, 2016.
arXiv preprint
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pages 265-284. Springer, 2006.
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In ACM Symposium Theory of Computing, pages 117-126, 2015.
Hamid Ebadi, David Sands. and Gerardo Schneider, Differential privacy: Now it's getting personal. Acm Sigplan Notices, 50(1)66-881, 2015.
Sam Elder. Challenges in bayesian adaptive data analysis. arXiv preprint arXiv: 2016.
Vitaly Feldman and Thomas Steinke. Generalization for adaptively-chosen estimators via stable median. In Conference Learning Theory, pages 728-757. PMLR, 2017.
Vitaly Feldman and Thomas Steinke. Calibrating noise variance in adaptive data analysis. In Conference On Learning Theory, pages 535-544. PMLR, 2018.
Vitaly Feldman and Tijana Zrnic. Individual privacy accounting via a Renyi filter. Advances in Neural Information Processing Systems, 34:28080-28091 2021.
Johannes Gehrke, Michael Hay, Edward Lui, and Rafael Pass. Crowd-blending privacy, In Annual Cryptology Conference, pages 479-496. Springer, 2012.
Andrew Gelman and Eric Loken. The statistical crisis in science. American Scientist, 102(6):460, 2014.
Arpita Ghosh and Aaron Roth. Selling privacy at auction. ACM Conference on Electronic Commerce, pages 199-208, 2011.

---

Moritz Hardt and Jonathan Ullman. Preventing false discovery in interactive data analysis is hard. In IEEE Symposium on Foundations of Computer Science, pages 4544463,75 2014.
Jacob Imola, Shiva Kasiviswanathan, Stephen White, Abhinav Aggarwal, and Nathanael Teissier. Bal- ancing utility and scalability in metric differential privacy. In Uncertainty in Artificial Intelligence, pages 885-894. PMLR, 2022.
John PA loannidis. Why most published research findings are false. PLoS medicine, 2(8):e 2005.
Christopher Jung, Katrina Ligett. Seth Neel, Aaron Roth, Saeed Sbarifi-Malvajerdi, and Moshe Shenfeld. A new analysis of differential privacy's generalization guarantees. In Innovations in Theoretical Computer Science (ITCS), 2020.
Vishesh Karwa and Salil Vadhan. Finite Sample Differentially Private Confidence Intervals. In Innovations in Theoretical Computer Science Conference, volume 94 of Leibniz International Proceedings in Informatics (LJPlcs), pages 44:1 14:99, 2018.
Shiva Kasiviswanathan and Adam Smith. On the 'semantics' of differential privacy: Bayesian formulation. Journal of Privacy and Confidentiality, 6(1), 2014.
Aryeh Kontorovich, Menachem Sadigurschi, and Uri Stemmer. Adaptive data analysis with correlated observations. In International Conference on Machine Learning, pages 11483-11498, PMLR, 2022.
Ninghui Li, Wahbeh Qardaji, Dong Su, Yi Wu, and Weining Yang. Membership privacy: A unifying framework for privacy definitions. In ACM SIGSAC Conference on Computer & Communications Security, pages 889-900, 2013.
Katrina Ligett, Seth Neel, Aaron Roth, Bo Waggoner, and Steven Z Wu. Accuracy first: Selecting a differential privacy level for accuracy constrained erm. Advances in Neural Information Processing Systems, 30, 2017.
Ashwin Machanavajhalla Johannes Gehrke, and Michaela Götz. Data publishing against realistic adversaries. Proceedings of the VLDB Endowment, 2(1):790-801, 2009.
Ilya Mironov. Rényi differential privacy. In IEEE Computer Security Foundations Symposium (CSF), pages 263-275, 2017.
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In ACM Symposium Theory of Computing, pages 75-84, 2007.
Yury Polyanskiy and Yihong Wu. Information Theory: From Coding Learning (book draft). Cambridge university press, 2022.
Ryan M. Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan. Privacy odometers and filters:
Pay-as-you-go composition. Advances in Neural Information Processing Systems, 29:1921-1929, 2016.
Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory. In Artificial Intelligence and Statistics, pages 1232-1240, 2016.
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 1 11:2635-2670, 2010.
Moshe Shenfeld and Katrina Ligett. A necessary and sufficient stability notion for adaptive general- ization. Advances in Neural Information Processing Systems, 32:1 11885-11494, 2019.
Thomas Steinke and Jonathan Ullman. Interactive fingerprinting codes and the hardness of preventing false discovery. In Conference on Learning Theory, pages 1588-166 1628. PMLR, 2015.
Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Conference on Learning Theory, pages 3437-3452. PMLR, 2020.
Aleksei Triastcyn and Boi Faltings. Bayesian differential privacy for machine learning. In Interna- tional Conference on Machine Learning, pages 9583-9592. PMLR, 2020.
12

---

Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence, 1EEE Transactions on Information Theory, 60(7):3777-320,, 2014.
Victor, Michael Klass, and Tze Leung Lai. Pseudo-maximization and self-normalized processes.
Probability Surveys, 4:172-192, 2007.
Yu-Xiang Wang. Per-instance differential privacy. Journal of Privacy and Confidentiality, 9(1. 2019.
Justin Whitehouse, Aaditya Ramdas, Ryan Rogers, and Steven Wu, Fully-adaptive composition in differential privacy. In International Conference on Machine Learning, pages 36990-37007.
PMLR. 2023.
Bin Yang, Issei Sato, and Hiroshi Nakagawa. Bayesian differential privacy on correlated data. In Proceedings of the 2015 ACM SIGMOD international conference on Management of Data, pages 747-762, 2015.
Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In International Conference on Artificial Intelligence and Statistics, pages 1782-4817. PMLR, 2022.
Tijana Zmnc and Moritz Hardt. Natural analysts in adaptive data analysis. International Conference Machine Learning, pages 7703-7711, PMLR, 2019.
13


Reviews:
[{"review_id": "RMmJ6Y3JzG", "reviewer": "Reviewer_GhwK", "summary": "In this paper, the authors generalize and improve the sample complexity that scales with variance compared to the sensitivity/range in the state-of-art DP result for adaptivity guarantee based on a novel definition of pairwise concentration (PC). The paper demonstrates such generalization in both bounded queries and sub-Gaussian queries.", "questions": "Can the author please provide any explanations and details on the concerns in the weakness part?", "limitations": "The paper does not have experiments compared to the DP baseline result. And due to the fact that the adaptivity parameter is arbitrary, I think the dataset size in the main theorem 5.1 can scale beyond the DP result when $\\alpha$ is large.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The analysis of the main results for both bounded and unbounded queries using the pairwise concentration (PC) stability is novel and has potential to analyze similar questions in the literature.\n\n2. The main results get rid of the range $\\Delta$ dataset size required for the adaptivity guarantee only depend on variance.", "weaknesses": "1. In theorem 5.1, the data size n can still be significantly larger than the baseline in DP due to max term and the fact that $\\alpha$ is arbitrary. Specifically, when $\\alpha$ increases, the dataset size n in Theorem 5.1 does not necessarily improve over the DP result, even if it does not depend on $\\Delta$.\n\n2. The paper does not provide any empirical evaluation to compare with the DP result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the useful feedback.\n\nRegarding the first point under ``weaknesses'': note that the case of $\\alpha \\ge \\frac{\\Delta}{2}$ is trivial, since it can trivially be achieved by $r = \\frac{1}{2} \\left(\\underset{x \\in \\mathcal{X}}{\\min} \\left(q(x) \\right) + \\underset{x \\in \\mathcal{X}}{\\max} \\left(q(x) \\right) \\right)$ (the mid point of the query's range), which is independent of the data. For any $\\alpha < \\frac{\\Delta}{2}$, we obtain $\\max \\left( \\frac{\\Delta}{\\alpha}, \\frac{\\sigma^{2}}{\\alpha^{2}} \\right) \\le \\frac{\\Delta^{2}}{2 \\alpha^{2}}$, and so the new bound provides improvement over the standard DP analysis for any non-trivial $\\alpha$.\n\nWe did not include empirical evaluation because it is straightforward to make such an empirical evaluation look arbitrarily good, by choosing a setting where the range is much larger than the standard deviation. One plot we could consider adding would have the range-to-standard deviation ratio as the x-axis, and plot the accuracy on the y-axis for both our analysis and the standard DP analysis. We somewhat prefer to use the space for additional intuition and other details, but are happy to defer to the reviewers on this matter."}, {"review_id": "p66tgAF8xE", "reviewer": "Reviewer_KJvw", "summary": "Overfitting can occur when a single dataset is used for several statistical tasks. It is known the application of additive noise techniques from differential privacy can prevent overfitting in a variety of statistical settings. The issue is that traditional mechanisms from differential privacy, which are inherently worst-case in nature, are overly pessimistic in adapting to the true variance of queries being issued. This work shows that additive noise mechanisms, such as the Gaussian mechanism, can provide guarantees that are inherently adaptive to the variance of queries issued by a data analyst. This departs from previous works, in which the guarantees are calibrated to worst-case (sensitivity-based) characterizations of the queries. To facilitate analysis, the authors introduce several novel analytic devices based on the realized Bayes factors of the queries.", "questions": "NA", "limitations": "-\tThe authors fairly discuss limitations as well as directions for future work in the final section of the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "-\tThe paper is very well written, and the related work section is good at framing the problem considered in this paper with respect to the general research landscape.\n-\tThis work, unlike most existing work, circumvents many aspects of worst-case analysis involved in differential privacy. Namely, through introducing several sophisticated analytical objects, the authors are able to present a more refined utility guarantee for the commonly used Gaussian mechanism.\n", "weaknesses": "-\tI think the results in the paper would appear stronger if the guarantees allowed the variance of queries to differ across rounds, as will likely be the case in practical data-analytic settings. From the current wording it appears that the query variance is fixed across rounds, but perhaps I am mistaken? Perhaps in practice many queries are of low variance, but only a few are of high variance.\n-\tAlong this line, I think experiments would be very important in demonstrating the impact in preventing overfitting. Even something along lines of a toy regression problem could make the message of the paper stronger.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the useful feedback.\n\nRegarding the first point under ``weaknesses'': Our results can handle queries of differing variances, as long as the mechanism has access to bounds on their variances. In such a case, the mechanism can scale the added noise at each iteration $\\eta_{i}$ to the corresponding bound on variance $\\sigma_{i}$, and the guarantees will still hold. One way to think of this is as simply rescaling all queries according to their variance bounds, adding a fixed level of noise, and then re-scaling the responses. We will clarify this  in the final version of the paper. (The case of entirely unknown variances is not covered in this work, but is an exciting direction for future work.)\n\nWe did not include empirical evaluation because it is straightforward to make such an empirical evaluation look arbitrarily good, by choosing a setting where the range is much larger than the standard deviation. One plot we could consider adding would have the range-to-standard deviation ratio as the x-axis, and plot the accuracy on the y-axis for both our analysis and the standard DP analysis. We somewhat prefer to use the space for additional intuition and other details, but are happy to defer to the reviewers on this matter."}, {"review_id": "FJO9OgnZXT", "reviewer": "Reviewer_wAxx", "summary": "This paper makes progress in adaptive data analysis by providing a better analysis of the Gaussian mechanism (for answering statistical/linear/counting queries), and showing that adding Gaussian noise ensures generalization error that scales with the **variance** of the queries.\n\nPreviously, the differential-privacy-based analysis achieved a similar conclusion. However, the generalization error might scale with the *range* of the queries. In practice, we might expect the queries to exhibit some \"nice\" behavior so that the worst-case analysis might be too pessimistic. In this sense, the contribution of this paper is valuable.\n\nThis paper is not the first one to study this question. Previously, [Feldman and Steinke, 2017] and [Feldman and Steinke 2018] considered the same question and got some results that were quantitatively weaker than the one presented in the current paper. The algorithm presented in this work is simpler than prior ones (i.e., simply adding Gaussian noises suffices), and the bound sharper.", "questions": "See weaknesses.", "limitations": "Limitations and future directions are discussed in the submission.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The algorithm is a natural and simple one. It's valuable that we can not understand the role of Gaussian noise in ADA better.\n* The bound is sharp.\n* The technical analysis seems novel (the so-called \"covariance between the new query and a Bayes factor-based measure\"), which might help advance the field further (though the reviewer did not have a chance to verify all the claims).", "weaknesses": "* The current algorithm only works for linear queries. i.e., queries of the form q(D) = 1/n \\sum_i q(x_i). The DP-based technique can offer bounds even for low-sensitivity queries.\n* I believe the \"covariance\" and \"Bayes factor\" notions are technically interesting. However, it seems that the current write-up does not fully convey an intuitive interpretation of these quantities. In particular, I feel like the claim \"how much information about the data sample was encoded in the responses given to past queries\" (quote from the abstract) could be made clearer.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the useful feedback.\n\nThe restriction to linear queries is indeed a limitation of the current work, and we hope to extend the results beyond linear queries in future work, as we briefly mention in the discussion.\n\nThanks for your comment about wanting more discussion/intuition for the Covariance Lemma and surrounding concepts! We agree and will add it in the final version. Here are some comments in that direction:\n\nThe Bayes factor $K(x, v)$ represents the likelihood ratio of seeing a particular view $v$ (a history of queries and responses) when conditioning on a particular datapoint $x$ being in the dataset, relative to when the dataset is entirely drawn at random. This captures the extent to which the presence of $x$ affects our probability of seeing $v$. \n\nThe first part of the Covariance Lemma (3.5) shows that the correlation that the view induces between a query $q$ and the Bayes factor $K(\\cdot, v)$ is an important quantity; it precisely controls the difference between the expectation of $q$ on the underlying data distribution versus its expectation on the posterior distribution (a distribution reflecting how a prior of the true data distribution would be updated after seeing $v$). When $q$ behaves very differently on this prior and this posterior, $q$ ``encodes'' information from the dataset, information that it received via $v$.\n\nFor arbitrary analysts with unlimited prior knowledge, the inequality in the Lemma is tight. This can be observed via the variational representation of the Chi-square divergence, which implies that $\\chi^{2}\\left(D_{\\mathcal{X}}^{v} \\Vert D_{\\mathcal{X}}\\right) = \\underset{q \\in \\mathcal{Q}}{\\sup} \\left(\\frac{\\left(q \\left(D_{\\mathcal{X}}^{v} \\right) - q \\left(D_{\\mathcal{X}} \\right) \\right)^{2}}{\\sigma_{q}^{2}} \\right)$. In this case, the only way to avoid overfitting is by bounding the Bayes factor term, so that the prior and posterior remain close in Chi-square divergence.\n\nThis Lemma offers the tantalizing suggestion that it may also be possible to obtain improved guarantees for adaptive generalization under stricter assumptions on the analyst. Such an improvement would not contradict known lower bounds, and might help us better understand the existence of algorithms whose generalization properties in practice seem to beat the known theoretical guarantees."}, {"review_id": "enDNCXh4dF", "reviewer": "Reviewer_WLLe", "summary": "This paper explores the problem of adaptive data analysis - when a single dataset is repeatedly used for adaptively chosen queries, overfitting can occur rapidly. To reduce this bias, a popular approach is to add noise to the output of each query. Intuitively, this prevents the analyst from learning too much about the sample and thus prevents them from choosing a query that overfits the sample.\n\nThe most common technique used to analyze this adaptive setting is differential privacy. However, the worst-case nature of DP requires scaling the noise to a worst-case dataset, rather than a typical dataset. The paper's contributions are:\n\n1) Prior work has shown that (roughly speaking), to ensure that the query responses are low bias, it suffices to show the responses have \"posterior accuracy.\" This paper shows that posterior accuracy can be thought of as the correlation between the query asked and a Bayes factor. \n\n2) They introduce a new notion of stability (pairwise concentration). Roughly speaking, stability measures (like DP) measure how much an algorithm's output depends on its input and have long been used to analyze mechanisms for adaptive data analysis. Pairwise concentration crucially depends on the dataset and query, to avoid the worst-case requirements of DP. Using this new notion of stability, they bounded the variance of the Bayes factor introduced in the previous point, which in particular bounds the correlation between it and the query asked. As a result, this new notion of stability can be used to prove generalization guarantees.\n\n3) Using pairwise concentration, they show that it suffices to add noise that scales with the standard deviation of each query.\n\nFor 3), a similar result was shown by [Feldman and Steinke 18]. However, [FS 18's] result is weaker than this paper in two ways. First, it only holds in expectation over the error, whereas this paper's guarantee holds with extremely high probability (the difference is equivalent to Markov's  vs Chernoff-style bounds). Second, this paper can handle subgaussian queries with unbounded ranges, whereas it's unclear if [FS 18] can handle unbounded ranges.", "questions": "I'm a bit confused about the regime where $\\alpha < 1$ in Definition 4.2 and Fact B.7. In Fact B.7, I believe the $\\leq$ should be converted to a $\\geq$ in this setting because the righthand side becomes decreasing with $\\phi$. For Definition 4.2, do you similarly want the direction to depend on whether $(\\alpha - 1)$ is positive? That would align with the intuition that $\\varphi$ is an upper bound on some notion of ``distance\" between $s$ and $s'$. The way it's written, we need $\\varphi$ to be an upper bound on this distance when $\\alpha > 1$ and a lower bound when $0 \\leq \\alpha < 1$.\n\nLine 731 typo \"ration\"-> \"ratio\"\n\nSee also the questions from the Weaknesses section.", "limitations": "Yes - all assumptions/theorem statements are clear, and the discussion includes some future directions that the present work does not address.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Within the field of adaptive data analysis, the authors give a refined answer to a simple question: What happens if we scale the noise of our answers to the standard deviation of the query? Prior work of [FS 18] suggested this approach can work, but were only able to prove that the error is bounded in expectation. This paper shows the error is bounded with high probability and also extends to unbounded but subgaussian queries.\n\nI'm also excited by the new notion of stability (pairwise concentration) introduced in this paper and hopeful that it can be applied in other settings (for instant, to analyze other mechanisms).\n\nAlong the way, the authors introduce a number of perspectives and new tools that may be more broadly applicable. For example, they introduce a number of \"dissimilarity\" measures, which provide more expressive ways to measure how dissimilar two distributions are than classical notions of divergence.", "weaknesses": "The definition of pairwise concentration and its application (in Theorem 4.5) are technically complex. One way for this work to be impactful is for pairwise concentration to be applied more broadly, and providing a simple interface to it would aid that. For example:\n1) In Theorem 4.5, I believe you only ever need to bound the pairwise concentration by datasets that differ in one point (via the function $\\psi(x,y;v)$ defined on line 291). If so, I would explicitly state that (ideally early) as this would make it easier for someone else to apply your framework.\n2) Also in Theorem 4.5, is there ever a reason (up to a small constant) to not set $\\xi = \\epsilon^2$?  It seems to me the probability bound is monotonically decreasing in both $\\xi$ and $\\epsilon$, in which case setting both $\\xi$ and $\\epsilon^2$ to the maximum of the two will only improve the error probability, and affect the deviation bounded by at most a factor of $\\sqrt{2}$. If so, my (personal) preference is that it's better to state a simpler version losing that $\\sqrt{2}$ and defer more detailed versions to the appendix.\n\nAnother minor point: This paper's mechanism assumes it knows the standard deviation of each query. The work of [FS 18] is able to estimate the standard deviation of each query and scale the noise on the fly. Can your analysis handle a similar approach?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the useful feedback.\n\nWe appreciate the suggestions on how to make the presentation of pairwise concentration more accessible. We felt a tension between simplicity versus presenting the more general notion, which may have broader consequences and applications beyond the usage in this paper (for example, group stability becomes a direct result of the definition, not requiring any proof). Given your comments, we will more prominently highlight that this paper uses only the $\\varphi(x, y;v)$ notion, where datasets differ in only one point. We'll also take your suggestion to set $\\xi = \\epsilon^2$ to simplify the statement of Theorem 4.5.\n\nThe case of unknown variance is not covered in this work, but we hope that the pairwise concentration stability notion will also offer new insights for this case, in future work.\n\nThe sign for the $0 \\le \\alpha \\le 1$ regime is not wrong, though it is somewhat counter-intuitive. It may help to note that $\\varphi$ serves two roles in this setting: (1) a bound on the stability loss random variable's mean (the $-\\alpha$ part), and (2) the variance proxy of the stability loss's distribution (the $\\alpha^{2}$ part). In the CDP representation [1], these two parts are denoted by $\\mu$ and $\\sigma^{2}$, respectively. Using this notation, we see that the bound is indeed monotonically tighter as $\\sigma^{2}$ decreases, as expected. \n\nThere was a typo in Fact B.7: it holds only for the range $\\alpha \\ge 1$ (we only need it for that range).\n\n~\n\n[1] Dwork, Cynthia, and Guy N. Rothblum. \"Concentrated differential privacy.\""}]

Author rebuttal:

Meta-review: This paper studies generalization in adaptive data analysis. It presents a novel analysis of Gaussian noise addition as a query answering mechanism. It shows that the noise can be scaled to the standard deviation of the queries, rather than their worst-case sensitivity, while achieving high-probability accuracy guarantees.

The main technical tool introduced is "pairwise concentration" which is a refined stability notion. Prior work has used either differential privacy or variants of mutual information.
Differential privacy gives high-probability guarantees, but the noise added must scale with the worst-case sensitivity.
Mutual information based approaches allow the noise to scale with the standard deviation of the queries, but they only yield in-expectation guarantees, rather than high-probability guarantees.
This paper provides the best of both worlds.

One limitation of the paper is that it assumes the queries' variance is known a priori. The prior works do not have this requirement. Thus there is room for further work.

Overall the reviewers are excited by this work and support acceptance at NeurIPS.
Decision: Accept (spotlight)