Tight Bounds for Answering Adaptively Chosen Concentrated Queries
Authors: Emma Rapoport
Edith Cohen
Uri Stemmer
Venue: NeurIPS 2025 poster ()
Keywords: Adaptive data analysis
Differential privacy
Concentrated Queries
Correlations
Primary area: theory

Abstract: Most work on adaptive data analysis assumes that samples in the dataset are independent. When correlations are allowed, even the non-adaptive setting can become intractable, unless some structural constraints are imposed. To address this, Bassily and Freund [2016] introduced the elegant framework of *concentrated queries*, which requires the analyst to restrict itself to queries that are concentrated around their expected value. While this assumption makes the problem trivial in the non-adaptive setting, in the adaptive setting it remains quite challenging. In fact, all known algorithms in this framework support significantly fewer queries than in the independent case: At most $O(n)$ queries for a sample of size $n$, compared to $O(n^2)$ in the independent setting.

In this work, we prove that this utility gap is inherent under the current formulation of the concentrated queries framework, assuming some natural conditions on the algorithm. Additionally, we present a simplified version of the best-known algorithms that match our impossibility result.

Tight Bounds for Answering Adaptively Chosen Concentrated Queries
Emma Rapoport Tel Aviv University
Edith Cohen Google Research and Tel Aviv University edi addthhoohenwangccom com
Uri Stemmer Tel Aviv University and Google Research u@uri co. iil
enmarapoport@@maill com
Abstract
Most work on adaptive data analysis assumes that samples in the dataset are independent. When correlations are allowed, even the non-adaptive setting can become intractable, unless some structural constraints are imposed. To address this, [Bussily and Freund (2016) introduced the elegant framework of concentrated queries, which requires the analyst restrict itself to queries that concentrated around their expected value. While this assumption makes the problem trivial in the non-ada -dn-adtptvve setting, in the adaptive setting it remains quite challenging. In fact, known algorithms in this framework support significantly fewer queries than the independent case: At most (n) queries for sample of size n, compared to (n²) in the independent setting.
In this work, we prove that this utility gap inherent under the current formulation the concentrated queries framework, assuming some natural conditions on the algorithm. Additionally, present simplified version of the best-known algorithms that match our impossibility result.
1 Introduction
Adaptive interaction with data is a central feature of modern analysis pipelines, from scientific exploration to model selection and parameter luning. However, adaptivity introduces fundamental statistical difficulties, it creates dependencies between the data and the analysis procedures applied to it, which could quickly lead to overfitting and false discoveries. Motivated by this, following the seminal work of Dwork et al. [2015b, substantial body of work has established rigorous frameworks for addressing this problem. These works demonstrated that various notions of algorithmic stability, and particular differential privacy (DP) [Dwork et al, 2006]. allow for methods which maintain statistical validity under the adaptive setting. Most of the current work, however, focuses the case where the underlying data distribution a product distribution, i.c., the samples the dataset are independent of each other. Much less is understood about the feasibility of accurate adaptive analysis when the data exhibits correlations. In this work, we examine the extent to which accurate adaptive analysis remains possible under minimal structural conditions on the data distribution.
Before presenting our new results, we describe our setting more precisely. Let 2' he a data domain. We consider the following game between data analyst A and mechanism M.
The analyst chooses a distribution over tuples in 2" (under some restrictions).
2. The mechanism M obtains a sample +- D. % We denote [S]
3. For & rounds 1,
(a) The analyst chooses query 9j : X |0, 1), possibly as a function of all previous answers given by M (under some restrictions).
-
(b) The mechanism M obtains 9j and responds with an answer aj C IR, which is given to A.
39th Conference Neural Information Processing Systems (NeurIPS 2025).

---

Note that the analyst A is adaptive in the sense that it chooses the queries q; based on previous outputs of M, which in turn depend on the sample S. So the queries 4 themselves depend on S. If instead the analyst A were to fix all & queries before the game begins, then these queries would be independent of the datasct S. We refer to this variant of the game (where all queries are fixed ahead of time) as the non-adaptive setting.
The goal of M in this game is to produce accurate answers w.r.t the expectation of the queries over the underlying distribution D. Formally, we say that .M is (a,, -)-statistically accurate if for every analyst A, with probability at least B. for every E [k] it holds that |a, - q (D) S a, where
2 (D) := BT [T EmeT (2(2) As way of dealing with worst-case analysts, the analyst A is assumed to adversarial in that tries to cause the mechanism to fail. We therefore sometimes think of A as an attacker.
The main question here is:
What is the maximal number queries one can accurately answer, k. as a function of the sample size n, the desired utility parameters a. B, and the type of restrictions we place the choice of DD and the queries 93 (in Steps [ and 3a above)?
Question 1.1.
The vast majority of the work on adaptive data analysis (ADA) focuses on the case where D is restricted be a product distribution over n elements (without restricting the choice of the queries 4)), After a decade of research, this setting is relatively well-understood: For constant a, 3, there exist computationally efficient mechanisms that can answer O(n²) adaptive queries, and efficient mechanism can answer more than that !
The siluation is far less well-understooll when correlations in the data are possible. Let us consider the following toy example as warmup. Suppose that the attacker randomly picks one of the following two distributions:
Do = The distribution that with probability 1/2 returns the sample (1. .......... returns the sample (0, .,....)). 0).
} and w.p. 1/2
D,=The The distribution that with probability 1/2 returns the sample (1) 2.... ......))) 2) and w.p. 1/2
returns the sample (1. 1).
Note that in this scenario, mechanism holding the sample (1, 1 :....: #)) cannot accurately answer the query (2x = x, as the true answer could be either 1/4 or 3/4. The takeaway from this toy example is that when correlations in the data are possible, then we must impose additional restrictions on our setting in order to make it feasible. There are two main approaches for this in the literature:
Explicitly limit dependencies within the sample [Kontorovich et al., 2022|: Intuitively, if we restrict the attacker A to choose only distributions 2 that adhere to certain "limited dependencies" assumptions, then the problem becomes feasible. A downside of this approach is that it is typically tied to a specific measure for limiting dependencies, and it is not clear why one should prefer one measure over another.
2. Limit the attacker to concentrated queries [Bassily and Freund, 2016]:
Notice that the toy example above cannot be solved even in the non-adaptive setting, because the description of the hard query q(x) = x does not depend on the sample S. So in a sense, it is "unfair" to attempt solving it in the adaptive setting. In other words, if something cannot be solved in the non-adaptive setting, how can we hope to solve it in the adaptive setting? Motivated by this, Bassily and Freund [2016) restricted the attacker AA to queries that in the non-adaptive setting are sharply concentrated around their true mean. Specifically, the attacker is restricted choose queries 9; such that if we were to sample a fresh dataset T from the underlying distribution 'D (where T is independent of the description of qj), then with high probability it holds that the empirical average of q; on T close to the true mean of q, over D. Notice that under this restriction, the problem becomes trivial in the non-adaptive setting, as we could simply answer each query using its exact empirical average. In the adaptive setting, however, the problem is quite challenging.
'See. e.g., Hardt and Ullman [] Dwork et al. [ Steinke and Ullman [0015] Bassily et al. 22016]
Cummings et al. [2016] Rogers et al. [206)] Felldmn and Steinke| [2017] Nissim et al.
2018 81, Feldman and 2020
Steinke [2018] Shenfeld and Ligett| 2019), Steinke and Zakynthinou (2020] Jung et al.
Shenfeld and
Ligett 20233
Blanc 2023 NNsssm al. 2023

---

In this work we continue the study of this question for concentrated queries. We aim to characterize can accurately answer (without
the largest number of adaptively-chosen concentrated--quries assuming independence in the data). Formally.
Definition 1.2 (Concentrated queries). Let X be a domain, let D be distribution over tuples in X', and let E E [0, 1] be parameters. A query q X - [0, 1] is (e, concentratee w.t.t. D if
SWD (5) - {(D) 2 5 s
Pr
where ((S) T&T ExEs is the empirical average of q S and qDD) EE [T(T)] is the expected value of 9 over sampling a fresh dataset from D.
For example, if D' a product distribution over datasets of size n, then, by the Hoeffding bound, every query 9 : X -> [0, 1] is (e, conceettneet for every example motivates the following question:
In2 2n
with y 22=- This
V
Question 1.3. How many adaptive queries could we efficiently answer when correlations in the data are allowed, but the analyst is restricted (s, -coneetecnee queries for E, 7 that are comparable to what is guaranteed without correlations, say E Vn
and y = n n-0?
Bassily and Freund (0166 introduced this question and presented noise addition mechanisms that
can efficiently answer ((n)) adaptive queries under the conditions of Question 1.3 By noise addition
mechanism we mean mechanism that given a sample answers every query q with q()) + 7) where 1) is drawn independently from a fixed noise distribution. Note the stark contrast from the i.i.d. case, where it is known that Onn²) queries can be supported rather than only Onn). To achieve their results. Bassill and Freund (2016) introduced a stability notion called rypical stability and showed that (1) noise addition mechanisms with appropriate noise are typically stable; and (2) typical stability guarantees statistical validity in the adaptive setting, even in the face of correlations in the data. More generally, the algorithm of Bassily and Freund (016]] can support roughly Ô queries provided that y is mildly small (polynomially small in K).
Following that, Kontorovich et al. [2022] showed that a qualitatively similar result could be obtained via compression arguments (instead of typical stability). However, their (computationally efficient) algorithms require y to be exponentially small in and thus do not apply to the parameters y stated in Question 1.3 They do support other ranges for (s, 7). but at any case their efficient algorithms can- not answer more than O(n) queries when the parameters (c, 7) adhere the behavior of Hoeffding's s inequality for i.i.d. samples. For example, for 0(1) and (n) adaptive queries within constant accuracy (even when there are correlations in the data).
2- -0() their algorithm supports
To summarize, currently there are two existing techniques for answering adaptively chosen concen- trated queries: Either via typical stability in the small regime or via compression arguments in the tiny y regime. At any case, all known results do not break the Onn) queries barrier, even when the concentration parameters reflect the behavior guaranteed in the i.i.d. setting. In contrast, without correlations in the data, answering ((z²)) queries is possible.
1.1
Our results
1.1.1
An impossibility result for answering concentrated queries
We establish a new negative result providing strong evidence that the linear barrier discussed above is inherent. Our result applies to mechanisms that perturb the empirical mean of query either by adding independent noise or by evaluating it on randomly selected subsample of the dataset, which together constitute all known efficient, polynomial number of queries in the i.i.d. setting. For brevity, we refer to these as Noise and Subsampling (NS) mechanisms. Specifically, we show that NS mechanisms cannol answer more than ((n) adaptively chosen concentrated queries, even if the query concentration matches the behavior of Hoeffding's inequality for i.i.d. samples. This constitutes the first negative result for answering adaptively chosen concentrated queries, and stands in sharp contrast to the O(n?) achievable in the i.id. setting. Specifically,
techniques for answering a super-linear
Theorem 1.4 (informal). Let > O and 7 E (0, 1). Then there exists a domain X and a distribution D over X such that the following holds. For any NS mechanism M there exists an adaptive analyst
3

---

issuing (s, comccentrat queries I...... Us where k- Q (min {1. ( ςa In (2) such that with probability at least 0.9 there is a query qs for which the answer provided by M deviates from its true mean (D) by at least 0.9.
To interpret this result, note for example that when O(1) and yy 2 then bound At gives & = (n). We show that the same is true for all values (E, that match the behavior of the Hoeffding bound in the i.i.d setting.
This negative result emphasizes a fundamental limitation. In order break the linear barrier the number of supported queries, future work must either impose additional structural assumptions on the problem or introduce new algorithmic techniques beyond noisc addition and subsampling mechanisms.
1.1.2 A simplified positive result
As we mentioned, Bassily and Freund (0166) introduced the notion of typical stability and leveraged it to design algorithms supporting adaptive concentrated queries. However, their definitions and techniques are quite complex. In particular, bounding the number of supported queries k function of the concentration parameters and ry is not easily extractable from their theorems.
We present a significantly simpler analysis for their algorithm that does not use lypical stability at all. Instead, it relies techniques from differential privacy (worrk et al. (2006). In addition to being privacyDDork
simpler, our analysis allows us to save logarithmic factors in the resulting bounds on k. Formally, we show the following theorem.
Theorem 1.5 (informal). Fix parameters 7- There exists noise addition mechanism M that guarantees 100 Tox) sttatistical accuracy against any analyst A issuing at most i queries which are (s.7)) concentntttte provided that = (min { [mm[[//))3 }).
In retrospect, leveraging differential privacy (DP) to answer concentrated queries (as we do in this work) is natural approach it is simpler than prior work this topic and aligns with other works on other variants of the ADA problem.
sense, the reason for the additional complexity in the work of Bassily and Freund (2016) steams from their alternative stability notion (typical stability). To the best of our knowledge, our work the first derive meaningful positive results for answering adaptively chosen concentrated queries via differential privacy when correlations are present in the data.
1.1.3 Technical overview of our negative result (informal)
The key insight underlying our negative result that query concentration alone does not prevent an attacker from extracting substantial information about correlated data. We consider a domain X' partitioned into & subsets, and define distribution D over X in which each sample consists of 1 distinct elements, each drawn from a different subset and repeated en times.
This structure simultaneously maximizes the information each query can reveal while ensuring that every query remains tightly concentrated. The attacker designs each query to assign nonzero values only within single targeted subset, keeping the empirical mean within [0, e] and satisfying (e, 7) m)-connentration by construction. Yet, the responses still leak significant information about the data.
Building on the adaptive attack of Nissim al. 2018 for the i.i.d. setting, attacker progressively identifies the repeated elements: each query randomly assigns binary values within the targeted subset and updates an accumulated score to isolate the correct element. We present a simple analysis adapted our setting, showing that the sample can be recovered with high probability. This breaks the accuracy guarantee of any NS mechanism once the number of queries exceeds our derived lower bound.
Our construction highlights that when correlations present, concentration alone cannot prevent information leakage. Thus, accurately answering more than linear number of adaptive, concentrated queries requires stronger structural assumptions on the distribution.

---

1.1.4 Technical overview of our positive result (informal)
We prove Theeore[[135] by showing that the mechanism that answers queries with their noisy empirical average guarantees statistical accuracy (for appropriately calibrated noise distribution). To show this, we introduce a thought experiment involving three mechanisms, initialized with the same sample S ~ D, all interacting with the same analyst A:
Answers each query using the empirical mean plus independent noise. This is the mechanism whose accuracy we want to analyze.
Real-world mechanism:
Answers each query using its true mean under the target distribution D, plus independent noise. Note that this mechanism "knows" the target distribution D. This is not real mechanism; it only exists as part of our proof. The noise magnitude will be small enough such that this mechanism remain accurate.
Oracle mechanism:
Hybrid mechanism: Initially behaves like the real-world mechanism, but switches permanently to behave like the oracle mechanism if some point the empirical mean on any query deviates significantly from its true mean. This is also not real mechanism; it exists only as part of our proof.
Our analysis proceeds in two steps. First, we leverage techniques from differential privacy to demonstrate that the oulput distributions of the the oracle and hybrid mechanisms are close. This allows us invoke commmced-oopssitooniiiii. theorems from differential privacy, ensuring that the outcome distributions of these two mechanisms remain close even after lc adaptive queries.
Second, we identify a class of good interactions. In these scenarios, the hybrid mechanism never switches to oracle responses, making its behavior identical to the real-world mechanism. We show that these good interactions occur with high probability under the oracle mechanism, and by extension, under the hybrid mechanism. We thus get that the real-world mechanism is also likely to produce these good interactions.
By combining these insights, we conclude that, under suitable concentration assumptions on the queries, the real-world mechanism's 's outputs closely track those of the oracle mechanism, which is statistically accurate by definition, thus ensuring statistical accuracy even in adaptive settings.
2 Preliminaries
We now formally define the two classes of mechanisms for which our negative result holds, which we refer to collectively as Noise and Subsampling (NS) mechanisms.
Definition 2.1 (Noise-Addition Mechanism). mechanism M a noise-addition mechanism if, given a dataset S and a statistical query it returns a = ={S) +1 where 1) is random variable drawn independently from a fixed, zero-mean noise distribution that does not depend on S q.
Definition 2.2 (Subsampling Mechanism). A mechanism M is subsampling mechanism if. given a dataset S size n, it answers each query q as follows. For each round independently, the mechanism samples a subsample S' of size m by drawing m elements from independently and uniformly at random with replacement, and returns = q(S")
Lves q(2), the empirical mean of on the subsample. The subsample S' is freshly resampled for every query, independently of previous rounds.
Differential privacy. Consider an algorithm that operates on a dataset. Differential privacy is a stability notion requiring the (outcome distribution of the) algorithm to be insensitive changing one example in the dataset. Formally,
Definition 2.3 (Dwork al. (2006)). Let M be a randomized algorithm whose input is a dataset. Algorithm M is (e, dddffferrentilll private (DP) if for any two datasets S.S' that differ in one point (such datasets are called neighboring) and for any event E it holds that Pr(M(S) E E e Pr'M(S') E Fi] + 6.
The most basic constructions of differentially private algorithms are via the Laplace mechanism as follows.
Definition 2.4 (The Laplace Distribution). A random variable has probability distribution Lap(b) if probability density function f(x) z exp
where x IR 4

---

Theorem 2.5 Dwork et al. 2006 ). Let f be a function that maps datasets to the reals with sensitivity (i.e., for any neighboring S, S' we have [(S)) f(SS) S E). The mechanism M that on input S adds noise with distribution Lap(E) ( the output of f(S) preserves (s, (e,0) -)-ffffrrntt privacy.
Finite precision and bounded outputs Real-world computing devices can only produce finitely many bits of precision. Accordingly, we assume outputs are rounded or truncated, ensuring a discrete output space. In our negative result, we additionally assume that outputs lic within fixed bounded range. This holds automatically for subsampling mechanisms, since the empirical mean of values in [0, always lies in [0, 1]. For noise-addition mechanisms, we assume oulputs lie in the interval [-,, Since queries are bounded in [0, 1] and the accuracy parameter is also in [0, 1/, any response outside this range would already violate the accuracy guarantee, meaning the mechanism has failed and the attack has succeeded.
3 An impossibility result for answering concentrated queries
We begin by noting that the bound of 1 1/y queries unavoidable. To see this, consider a distribution D that is uniform over 1/ry disjoint samples ,I,...,,1,/ of size n each. Now consider the analyst that queries (one by onc) all 1/7 queries of the form (x()) 1 if x E S; and q: (z) = 0 otherwisc. The "true mean" of each of these queries over D is exactly 7, and each of them, the probability of deviating from this truc mean by more than y (over sampling S D) is at most y. So for y < & and a < 1 y these queries are all concentrated, and one of them causes the mechanism to lose accuracy. See Appendix for the formal details.
The main result of this section gives a stronger impossibility bound. We construct a distribution and domain such that any NS mechanism can be forced to fail with probability 1 - 3 by an attacker issuing only (s, 7) concentaaet queries after
( (E.)))
rounds.
We then consider the setting where y is function and a that corresponds to the concentration of bounded queries in an i.i.d regime. Specifically, if <(,.)) = 2 expp-22=*i as given by the double-sided Hoeffding inequality, then the combined bounds imply that no NS mechanism can answer more than (n)) such queries.
Domain and distribution. We now formalize the domain and sample construction described above. 1
Let E (0, 1] and define r = 1/e. Let X' finite domain of size N .max c> Assume for simplicity that r is an integer and that it divides both N and n. Partition X' into disjoint subsets X1,- -i,..., Xr, each of size e.N. Label the elements in each subset arbitrarily: X; {x] 27 x; for all / .T.
The distribution D over x is defined as follows. First, sample an index j ~ Unif 2, ..... eNJ. ,....., That is, a single index j
Then, output the sample S = (xq....,.)
ST
En
determines one point ai from each subset X; and the sample consists of each of these points repeated exactly 1/r an times. Although D is defined X", its support contains only N/r =N distinct samples, and each is determined by the shared index j.
The attack procedure (Algorithm() []] operates over k rounds of information gathering followed by a single final query. During the information gathering rounds, each query ge is constructed using i..dd Bernoulli random variables: each element ø in the targeted subset Xi independently takes the value with probability Pt Unif(0, 1). while other elements in the domain receive value 0. Throughout the interaction, we track an accumulated score Z, for each
Attack Overview:
element wf. defined that the score increment 2 has positive expectation if 2 matches the unique element appearing in the true sample, and zero expectation otherwise. After all & rounds, we identify the element with the highest cumulative score. By standard concentration arguments, this element is likely to be the one present in the actual sample, as it uniquely accumulates positive expected score. We issue a final query that evaluates to 1 for the elements in the sample we identified and O for all other elements, thus pinpointing the true sample. Throughout the analysis, we assume

---

a <-11 deviation exceeds a.
Supp(DDj ensuring that if the final query successfully identifies the true sample, the resulting
Algorithm 1 Attack Procedure
Initialization: Let M be NS mechanism initialized with sample S ~ D. For each element of E &, initialize an accumulated score Z, 0.
Information gathering rounds: For each round e [k:]:
1. Sample pr Unif(o, 1].
2. Define the query X' - {0, 1) as:
(x) = [~ Bernoulli(pe)
i E X,, otherwise.
3. Submit @: the mechanism and receive the response dt-
For each of E X1, define of = (at - pt/r) (q=(x²) - pt), and update Z3 4- 23 + 2/. Final query: After l rounds, compute j = arg max, Zz. Submit final query 9" X + {0, 13 by setting
if x = x! for i E [r].
('())
otherwise.
Analysis of the attack. We now prove that the attack descrihed above succeeds using only 7)) concentrated queries. This analysis establishes three components: (1) all & information informatiiongaathrring gathering queries are (e, conceenntt,,, (2) the final attack query 9* is also (s, (0-c7c)enntttted,, and (3) with high probability, the attack correctly identifies the underlying sample. The proofs for the concentration of the queries deferred Appendix(A.2
Theorem 3.1. For the attack identify the true sample with probability least 1 -3, it suffices 1 + In (1))
that = 22 ( max In (2) In
Proof Sketch. Consider the variables of (as E (qi(z)) Pt). It can be shown (Appendix A.3.1 that these satisfy E[z]] 8r if corresponds to the true sample, and otherwise. Summing these variables, define Z, Σイ= z/. Each Z, thus accumulates positive expectation only for the true index js: and zero otherwise. Using standard concentration inequalities, one obtains that the index maximizing Z, coincides with the true sample with probability at lcast 1- 8, provided satisfies the stated bound. The detailed argument is deferred to Appendix A.3
Combining Theorem and the attack in Appendix A.
we get:
Theorem 3.2. Let Y E (0, 1), and (0, 1). Then there exists domain X and distribution
'D over X such that for any NS mechanism M, and any E (0, Supp(D]] there exists
( )) such
analyst issuing adaptive (e, concentraat queries with k = Q min that Pr [Bi [k] such that |M (q:) (D)
> a) 2 1- B.
Comparison to the i..d setting We now compare our query bound to the classical i.i.d. setting, where differentially private mechanisms can answer up to O(n²) adaptive statistical queries with bounded error. In sharp contrast, our results imply a strong negative statement: even if the query con- centration matches the behavior of Hoeffding's inequality for i.i.d. samples, the number of accurately answerable queries by NS mechanisms is tightly bounded by On)). To make this comparison precise, we assume a fixed failure probability (c.g. 8 = 0.01), and let the concentration rate 7(n, E) follow the double-sided Hoeffding bound: 7(n,E)
2 cxp( 2n Under this assumption, the bound from thcorem 3.2 simplifies = O(n) for any s E (0, 1). The full derivation is a straightforward asymptotic calculation, deferred to Appendix A.4

---

4 A simplified positive result
4.1 Setup and definitions
We introduce a thought experiment involving three mechanisms, all initialized with the same sample S ~ D, all interacting with the same adaptive analyst A over & rounds.
A sample S ~ D is drawn once and remains hidden from the analyst. The analyst A issues sequence of l statistical queries ?t ........ Qi X + [0, I), where each query may depend adaptively on previous queries and responses: AA is assumed to be deterministic without loss of generality, as randomized analysts can be treated by taking expectation over distribution of deterministic strategies.
The mechanism's 's responses are based on one of three strategies: the real-world mechanism adds Laplace noise to the empirical mean Ms(gg) = qi(S) + 1)i, where d/s ~ Laplace(O. 6); the oracle mechanism adds Laplace noise the true mean (o) q, (D) + 1//. where 7// ~ Laplace b);; and the hybrid mechanism responds as the real-world mechanism while all past queries are E- concentrated relative to S, but switches to the oracle mechanism once any empirical mean deviates (S) + тι, if max (D) + 1//- otherwise.
(D) S s,
by more than & from the true mean: MH(④g))
To describe the interaction between the analyst and the mechanism, define the transcript t (4), 01,.... qs ag), which records the sequence of queries and their corresponding responses. Each answer is given by either Ms(gg). Mo(g,) or (s(g;), depending on the mechanism being used in the interaction.
Definition 4.1 (Transcript). Let be an analyst interacting with a mechanism over k rounds. The random transcript TT' is the sequence of queries and responses generated in the interaction. A particular outcome denoted by (q1, .......9h. az).
Transeript Probability Notation. Let be a transcript arising from an interaction between an analyst A and mechanism M. We denote the probability of t arising under mechanism .M as PT t). where PrMs (T t), Pr.o (T t), and Pr (T t) refer to the probabilities under the real-world oracle, and hybrid mechanisms, respectively.
analyze the outcome of the interaction, we define two categories of " "good" events: (I) Statistical accuracy: This event contains all transcripts i such that all answers in f are close to the true means of their respective queries. (2) Sample concentration: This event contains all pairs of transcripts t and samples S such that the empirical mean on S of each query in f is close to its true mean on D. Note that statistical accuracy is property of the mechanism's 's outputs and their deviation from the true means, independent of the sample; sample concentration, by contrast, depends on both transcript and sample as il reflects how well the empirical means align with the true expectations.
Definition 4.2 (a-accurate transcript). A transcript response a; is within a of the true mean (D)) that is: (a, (D)) S. a for all i [k).
(1.,a ..........s. qe, 0g) is a-accurate if every
Definition 4.3 (E-good pair (S, t)). Let S E Supp(D) be sample and let = (q1,a1,.... qes ax) be transcript of k queries and responses. The pair (S,t) is called E-good if. for every query qi in t, the empirical mean of qs on S is close to its true mean: [9:(S) (D( I
Our strategy involves demonstrating that the probability of sample concentration events occurring is similar across the real-world, oracle, and hybrid mechanisms. By establishing this, we can infer that events satisfying both statistical accuracy and sample concentration- -hich wwich occur with high probability under the oracle mcchanism-aa also occur with high probability under the real-world mechanism. Thus ensuring that the real-world mechanism maintains statistical accuracy despite the adaptivity of the analyst.
4.2 Relating the distribution events under the oracle and hybrid mechanisms
The first component of our analysis shows that the output distributions of the oracle and hybrid mechanisms are closely aligned, similarly to the guarantees provided by (e. -dffffrrrett privacy for neighboring datasets. This is formalized in Lemma 4.4 with the proof deferred to Appendix B.

---

Lemma 4,4, Let S E Supp(D) be sample, and let be any query. Then for every measurable set in the output space & S y:: Pr[MH(1) E] I eñ Pr[Mo(a) E E] and Pr Pr[Mo(g) E E] - et (4) E E].
Extending advanced composition to setting. The preceding lemma allows extend the advanced composition analysis of Dwork et al. (2010b] (see also Dwork and Roth (2014[) to our framework. One of their results shows that if (s, 0)-dilferentially private mechanism interacts with an analyst over k rounds, then for any 8' O. the overall interaction (E* -')-differentially private, where z Vkg. Although this theorem framed in terms of differential privacy and neighboring datasets, the proof relies solely on the following: in each round, the conditional distributions of the outputs in two parallel experiments Y and Z given identical histories up the previous round satisfy that for any E C Supp(Y".. holds that In PrYEE Pr|ZEE
S E, and similarly for the reverse ratio.
our setting, Lemma 4.4 limlics that this condition holds for any interaction of a fixed analyst with the oracle and hybrid mechanisms once you condition on identical histories. now formalize the corresponding composition theorem in our framework and, for completeness, supply full proof in appendix [.2 that mimics the proof of (Dwork al. 2010b Theorem III.1] demonstrate that it applics under our conditions.
Theorem 4.5. Let S E Supp(D) be a sample, and let be a fixed analyst. Consider two k-round interactions with A: one with the hybrid mechanism MH, and one with the oracle mechanism Mo.
For any p > 0, define Ex = 1/2 2%
=
& k (e5/h - 1). Then
In PRMM (T =t) (T > 6" Sp. and
PEMO (T = t) te te-oo PRми (T > 6 Sp
Pr M
Pr
In
From this, we conclude the following corollary (the proof is deferred to Appendix B.3
Corollary 4.6. Let A be a fixed analyst, S Supp(D) a sample, and let be any event that can arise in the interaction with the analyst. For any p > 0, define s² as in Theorem 4.5 Then e= (Pr [8] p) S [T] I ee" Pr + p.
4.3 Hlighprobbbbi accuracy of the Laplace mechanism
The next lemma shows that the real-world and hybrid mechanisms assign equal probability any event consisting entirely of E-good mechanisms operate with the same randomness, so as long as all queries remain s-good, their responses are identical. Full details are provided in Appendix B.4
pairs. This follows from the fact that both
Lemma 4.7. Fix an analyst A, and let G be the set of s-good tample-transcrip pairs. Then, for every measurable subset & S G. Pr,; Pr,,, [E].
The following lemma provides a bigh-probability guarantee for E-good and a-accurate transcripts under the oracle mechanism. Since the output is independent of the sample, a union bound over queries and noise yields this result, with the full argument deferred to Appendix B.5
Lemma 4.8. Let S ~ D and consider a k-round interaction between an analyst A and the oracle mechanism, producing the transcript t. Define the failure probability of any of the Laplace noises exceeding a as
Pr[[ná S a)*; for n/ Laplace(O, b). Then,
[(S. t) is e-good and t is a-accurate] Pr SnD, PPMMo
2 1--k--
We have established that: (1) the transcript distribution under the hybrid mechanism closely ap- proximates that of the oracle mechanism, (2) the probability of any event consisting of s-good sample-transeee pairs identical under both the real-world and hybrid mechanisms, and (3) under the oracle mechanism, the joint event of s-good pairs and a-accuracy occurs with high probabil- ity. Combining these facts implies that the real-world mechanism is statistically accurate with high probability. This is formalized in the following theorem, the proof of which is deferred to Appendix B.6

---

Theorem 4.9. Let A be an analyst, and My the real-world Laplace mechanism interacting with A k rounds. For and p 0, define as theorem 4.5 and let be as in lemma 4.8 Then, the probability that the real-world mechanism produces an a-accurate transcript satisfies
Pr t (g,,a,,...,,.. TR, : Vi aa q.(P) sa] 2 e (1- Mg
Theorem 4.10. Let A be any analyst issuing & adaptive (E,7) conncenttrt queries, and fix an accuracy parameter a > and failure probability /3 > Then the Laplace mechanism can achieve
(a,, B)aaccuyy over all queries provided O min 8 [m(1/e]] (n11/7) (lm1//)) }):
o² g²
Proef. Run the Laplace mechanism with noise scale b 2 ( Theorem 4.9 implies that for any fixed a > 0 and number of queries k, the real-world mechanism satisfies (a, 3) accuracy provided e==" (1- k- (-P) 2 1 1- B. Requiring each term in the failure probability p. Ç. k and E* to & 3/4, yields the desired result. See Appendix B.7 for the details of this derivation.
Simplified bound for constant accuracy and failure (example). If we assume constant parameters for failure probability and accuracy with & < (c.g., a = 3 0.01), Theorem 4.10 implies the existence of a noise addition mechanism M that guarantees (0.01, 0.01 -sattsslaai accuracy against any analyst A issuing up adaptive, ( queries, provided
h = 0 ( min {
{(Im(1/0)3² })
1
Acknowledgments and Disclosure of Funding
Emma Rapoport is partially supported by the Israel Science Foundation (grant 1419/24), the Blavatnik Family Foundation and the Deutsch Foundation. Edith Cohen is partially supported by Israel Science Foundation, (grant 1156/23). Uri Stemmer is partially supported by the Israel Science Foundation (grant 1419/24) and the Blavatnik Family Foundation.
References
Kazuoki Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Seriex, 19(3):357-367, 1967.
Raef Bassily and Yoav Freund. Typicality-based stability and privacy. CoRR, abs/ abs/1664.03336 2016.
Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan R. Ullman. Algorithmic stability for adaptive data analysis. In STOC, 2016.
Guy Blanc. Subsampling suffices for adaptive data analysis. In STOC, 2023.
Rachel Cummings, Katrina Ligett, Kobbi Nissim, Aaron Roth, and Zhiwei Steven Wu. Adaptive Icarning with robust generalization guarantees. In COLT, 2016.
Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Now Publishers, 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise sensitivity in private data analysis. TCC, 2006.
Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 51st annual symposium foundations of computer science, pages 51-60. IEEE, 2010a.
Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In FOCS. 2010b.
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. Generalization in adaptive data analysis and holdout reuse. In NIPS, 2015a.
10

---

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In STOC, 2015b.
Vitaly Feldman and Thomas Steinke. Generalization for adaptively-chosen estimators via stable median. COLT, 2017.
Vitaly Feldman and Thomas Steinke. Calibrating noise to variance in adaptive data analysis. COLT, 2018.
Moritz Hardt and Jonathan Ullman. Preventing false discovery in interactive data analysis is hard. FOCS, 2014.
Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajeer and Moshe Shenfeld. A new analysis of differential privacy's generalization guarantees. In ITCS, 2020.
Aryeh Kontorovich, Menachem Sadigurschi, and Uri Stemmer. Adaptive data analysis with correlated observations. ICML, 2022.
Solomon Kullback and Richard A Leibler. On information and sufficiency. The annals of mathemati- cal statistics, 22(1))79-86, 1951.
Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan R. Ullman. The limits of post-selection generalization. In NewrlPS, 2018.
Kobbi Nissim, Uri Stemmer, and Eliad Tsfadia. Adaptive data analysis in balanced adversarial model. NeurlPS, 2023.
Ryan Rogers, Aaron Roth, Adam Smith, and Om Thakkar. Max-information differential privacy, and post-selection hypothesis lesting. FOCS, 2016.
Moshe Shenfeld and Katrina Ligett. necessary and sufficient stability notion for adaptive general- ization. NewrIPS, 2019.
Moshe Shenfeld and Katrina Ligett. Generalization in the face adaptivity: bayesian perspective. NeurlPS, 2023.
Thomas Steinke and Jonathan Ullman. Interactive fingerprinting codes and the hardness of preventing false discovery. COLT, 2015.
Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information, In COLT, 2020.

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction provide accurate summaries of the major claims made in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations of the results are captured in the formal theorem statements, and emphasize the differences between our setting other settings studied in prior work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specificatiin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach only tested on few datasets or with few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken low lighting. Or a speech-to-text system might not used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, the authors should discuss possible limitations of their approach address problems of privacy and fairess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerming limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set assumptions and a complete (and correct) proof?
12

---

Answer: [Yes]
Justification:
We fully prove all of our theorems.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. novel architecture, describing the architecture fully
For example, if the contribution might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access hosted model (e.g., in the case a large language model), relcasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code. the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with open-source dataset instructions for how construct the datasct).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
13

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
cubbic/guides////
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceplable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the command and environment needed reproduce the results. See the NeurIPS code and data submission guidelines (https:
moips.cc/public. hanlllcc/giieee guwdgs/ddieeeee wwweeeSuumsssioooooo
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc. The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information as possible in supplemental material (appended to the paper) is recommended,, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should explained (closed form formula, call to library function, bootstrap, etc.)
14

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK report 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding ligures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full rescarch project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
The paper and its underlying research conform to the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is not expected to have any immediate societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (c.g., deployment of technologics that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
15

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there direct path any negative applications, the authors should point it out. For example, it is legitimate point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
the other hand, it is not needed to point out
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does paper describe safeguards that have been put place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper does existing assels.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode. com/ datassts has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both original license and the license of the derived asset (if it has changed) should be provided.
16

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Are new assets introduced the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: The paper does release assets.
Guidelines:
The answer NA means that paper does not release new assels.
Researchers should communicate the details of the detaset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu-
tion the paper involves human subjects, then much detail as possible should included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country which research conducted, IRB approval (or equivalent) may he required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
17

---

Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the methods in this research? Note that if the L.IM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer LLM policy http:///eaaurpppoooooooooeereee/ for what should or should not be described.
18

---

Appendices
A Additional proofs for negative result
A.I simple negative result using 1/7 queries
We present a simple construction showing that for any values 0 < < S & S and any a S - there exists domain, distribution, and adversary strategy such that after most k = 1//7 queries, all which are (e, coonenttttt, the mechanism is forced return a response that is not statistically- accurate.
Claim A.1. Fix parameters < S E S and a S 11-7 There exists a distribution D over X and a set of k = queries, each (e, conceettent,, such that an attacker submitting these queries to any mechanism will receive response that differs from its true expectation by more than a on at least one query.
Proof. Let 1/h,, assumed be integer for simplicity. Let the domain be X' -1,,2....,nI) partitioned disjoint subsets Si,..., S, X, each of size n.
Let D the uniform distribution over these subsets: that is, S means S; with probability 1/r = for any i (I....,r}.
Define queries ........ qs, X + {0.1} by
i S., otherwise.
gs, (2)
0
Each query has true mean gs, (D) = 1/r = 7.. For any sample S,, we have qs, (5) = 1, while for all j * i, qs, (S) =0. O.
To verify concentration, note that for any o Sü The empirical mean qs, (S) so the deviation from the true mean is exactly S For the sample = S., qs, (S) = 1, and the deviation is
1-7 2
Thus, submitting the k 1/r queries guarantees that one query must yield an error greater than o, violating (a, -tstttiitti accuracy.
A.2 queries in the attack described algorithm Dare (e, concentrated
Lemma A.2. Each query qe in the first & rounds in the attack described in algorithm is (6, 7)- concentrated.
Proef. Fix round and any S' E Supp(D). The sample consists of copies of of of some element of E An and (n-En) elements from X' X'), Nr Since q. (x) 0 for z & X, have (S") equ (zf). where qe (xf) Bernoullipp). Therefore the empirical mean of any sample in Supp(D)is in {0, E). and q: (D)the true mean is Ept E [0, s), so the absolute deviation is at most E.
Lemma A.3. The final query q" in the attack described in algorithm is (c, conceeetaed under D.
Proof. Let T ~ D. The query g" evaluates to if T is the sample generated by choosing the j' element in each subset X. and otherwise. Thus, the true mean q" (D) eN If q" (T) 0, the the deviation exceeds but this event occurs with probability =
ly
deviation ; q² (T)
Since N max + कक j. have * I and r I 7, the deviation exceeds with probability at most 7, meaning 4* is (e, concentatr...
A.3 Proof of theorem
We begin by proving supporting lemma:
19

---

A.3.1 Lemma A.4
Lemma A.A. Let ja denote the index of the elements that appear in the true sample that is used by the mechanism. Define
z) = (a1
Pt
(x(x²) - -P.)
r Then for each E {l,.... EV and E {l,...,
.....,,,, k}.
if = j.. otherwise.
E0
0
Proof. Let S (2) ...... x.. ..... . .... x/)) be the true sample that is used by the mechanism.
Case 1: j is- Here a (zf) is independent of as, and E[q (x()) Pt.
B|=/] [ P (a(()) p+)l 0.
Case 2: j= ==- The analysis in this case depends on the type of mechanism used.
II M is noise addition mechanism: Substitute de (x(=²)) + into "/-". Since is zero-mean and independent,
E|a (x() p.)
Because go (2f")) Bernoulli(p.) and ps Unif(O, 1]. this gives:
Bia
Elp, p.)] p 6r
If M is a subsampling mechanism:The output a, is the empirical mean of the query evaluated on subsample SM of size which is constructed by drawing elements i.i.d. and uniformly from the original sample S. We can express the output as:
at = qr (Sm)
(Y2),
where each Y₁ is drawn uniformly from S. By construction, the original sample S (of size n) contains exactly n/r copies of x/" Therefore, the probability that any given draw Y, is equal to x/ is:
n/r
Pr(Ye =
Furthermore, (Y)) = 0 whenever Y; 전 oं. Let C' be the number of times of is drawn into SM, C ~ Bin(m, 1/r). The output can then be simplified to:
m (x(t)
all other points sampled into Sy contribute the sum. We first compute the expectation conditioned on Pt and
C
((f)))) 2t) (gn(2))) - -pt) pr.
E (ot 2t (aa(((")))
pr) Pe, C
E
((ff)) pi) [p]
E Pt. (q.(x))) - -Pt) pt
pt
m
pe(1 pt).
Next, laking expectation over the binomial randorn variable C yields the expectation conditioned only on py:
Pc
(1 p.)
7 p. -P).
m
Thus, in the subsampling case as well, the final expectation is:
+ r
Elp.(1 pe)] 6r
20

---

Theorem 3.1 For the attack to identify the true sample with probability at least 1 - 3, it suffices that
h = 98 max In ( In
- {
+ +
(1))
Proof of theorem Let ja denote the index of the true sample fed to the mechanism. Define for each index the cumulative variable Zj >t=1 z where
a1 Pt
(x(()))) pt)
According to lemma A.4
E[2/] = 6r if = jo:
1
0 otherwise.
For each * Je. define the difference W 2 z and let W Σx W Zj, -Zy. Note that for fixed j. the variables =/ ...... 2x are i.i.d., and so are the variables W!...., W By assumption, mechanism outputs are bounded fixed interval. Since Pt, ((()) E [0, 1]. each term [Wy'] bounded. Also, E[W?] 6r
Applying Hoeflding's inequality to W we get:
k Cr2
Pr(w3 < 0] exp
for some constant C.
We compare each alternative index j * j. to the true by checking whether Z₁ 2 Zj, which occurs exactly when W < O. By union bound over the N/r 1 such indices:
N
Pr + j. 2, 2,.1
exp
Ct22
ensure that the attack identifies the true sample with probability least B, suffices that
2 Cr2.11 .In
exp
Cr2 Cr2
r3
1 Substituting = 1/e and using the definition of max
we oblain
= Ery
N
= In(=N) + In (1]
In
max
In
In
+ In
r8
Thus,
1
max
In
c
A.4 Comparison to the i.i.d. setting
Fixed failure probability. For simplicity, we assume failure probability a constant (e.g. 8 = 0.01). Under this simplification, the final bound from Section 3 means that noise-addition mechanism can maintain (a, (a,,9)-sttissiii -tstttiiti accuracy for:
mimin min { o max
In
Comparison under Hoeffding-style concentration double-sided Hoeffding bound: (n, 2exp(-2200 2ne?). This yields
To mirror the i.i.d. setting, let ((n,)) e) be the
min { exp((ne"), o max In
(- ne? })}
21

---

Parametrizing the concentration rate To understand how i scales with n, we write E(n) f(n)//n, where (n) E (0, vnj. This gives:
ms= = f(n),, In = In In fnn).
2
Substituting, get:
Vu f(n)
((,,s) exp(2f(n))), max In
ne =
f(n)²
max
s(n)²
We divide the analysis into three regimes based on the value of f(n)² relative to In n: Case 1: f(n)² > Inn. In this case, the maximum in the second term is attained by f(z)2. so:
k: k= o -
T2
5(m)² = O(n).
Case 2: [(n)² E 12 Inn]
k: k= 0
Inn) O(n).
Inn
Case 3: f(n)² < hnn
exp(2f(n) S exp(Inn) O(n). (n,
Conclusion For any choice of & E (0, 1]. whether constant or varying with (c.g., s(n) = ). if (n,, <) matches the behavior of the Hoeffding concentration bound, the resulting bound is k = O()).
B Additional proofs for positive result
B.I Proof of lemma 4.4
Lemma 4.4 Let S Supp(D) be sample, and let q be any query. Then for every measurable in the output space & y.:: Pr[Mn(1) e E] I ę Pr[Molg) E E] and Pr Pr[Mo(g) E E] s
et Pr (r)Ma(1) E E]..
Proof of lemma 7.. If (ir(g) = Mo(g), the prohabilities are equal. Otherwise, since Mar(g) Ms(() and ((S) (DD) e, have Mz) ~ Laplace(g(S).)) and Mo(g) Laplaco(g(D).)) b). The two distributions differ only in location by at most Therefore, their (M)
density ratio bounded: (M) S exp(E//) for all y E R, and similarly for the reverse ratio. Assuming the mechanism oulputs are discretized to finite set ) C R by rounding to fixed precision, each output value y corresponds to an interval I, R. Integrating over these intervals preserves the density ratio bound, yielding the stated probability bounds.
B.2 Proof of Theorem
Before presenting the full proof theorem 4.5 we first introduce additional preliminaries, notation, and a supporting lemma that are used throughout the argument.
B.2.1 Additional preliminaries
Definition B.1 (KL, divergence or relative entropy Kullback and Leibler 1951[). For two dis- tributions Y and Z. the same domain, the KI. divergence (or relative entropy) of Y from Z
is
D(Y Ey-y Pr PTZ-
In
22

---

We now recall several definitions and results from Doork et al. (0106) that are instrumental in the proof of advanced composition in differential privacy, and which we will use directly in our analysis. Definition B.2 (Max divergence, e.g., [Dwork al. 2010a Let Y and Z be distributions on the same domain. Their max divergence is
Dx (2) = max In Pr(YES)
PT(ZeS]
SCSupp(Y)
(010b)). I and Z satisfy Dx (Y(12 S and Lemma B.3 (Lemma II1.2 in Dwork al.
Dx Y) S E. then D( 2) S E E(e
Lemma B.4 (Avuma-Hoeffddin inequality (Azuma, 1967 ). Let Ci...., C2 be real-valued random
variables with [C,] S a almost surely. Suppose also that E(C; C1 = Cl...., C2-1 G-11 S B for
every partial sequence (0....,,4-1)) E Supp(C1,..... ..... 1). Then, for any 2 > 0,
Pr
Ec>kB+
s c 1/
B.2.2 Definitions and notations
We recall the definition of a transcript:
Definition (rransrrpp)), Let A be an analyst interacting with a mechanism over k. rounds. The random transcript T is the sequence of queries and responses generated in the interaction. A particular realization denoted by t (q), (11 "tl dz)).
Extended notation. We extend the transcript notation introduced above by letting Qi and A; denote the random variables corresponding to the query issued and response returned at round i, respectively. The full transcript is then the random tuple is written = (41, a1.... qc ax). The values of A, depend on the mechanism: in the roal-world mechanism, A; = Ms(a); in the oracle mechanism, A, Mo (g:); and in the hybrid mechanism,
(Q1, A1,.- ... Qk, A&), and specifie realization
A, MB (9:).
Definition B.5 (Transcript prefix). For each round E [k),, the prefix of the transcript up round is the random variable T--1 = (Q1, A .... 1 For a particular realization t (q1. 01..... qs, (&), write the corresponding prefix t;-1 (q1, ai.......... :6-1, Q;-1)-
Definition B.6 (Support of transcripts). Let be the data distribution over X", and let ' be the random transcript produced by an interaction (with any of the mechanisms) with an analyst A. We define: TA {t: Pr([T-
0}.
Remark B.7. The support Ta depends only on the analyst A, not the mechanism. This is true because all mechanisms respond by adding independent Laplace noise to either (SS) or q: (D), and, by assumption, the output space y is finite. Therefore, for any fixed query every output 0g E Y occurs with positive probability under all mechanisms. As result, the transcript (q) (i,..., De, ag) has nonzero probability under each mechanism if and only if it is possible under the analyst's 's query selection behavior.
B.2.3 Supporting Lemma
Lemma B.8. Let S E Supp(D) be a fixed sample, and let q be any query. Then the Kullback-Leibler divergence between the outputs of the hybrid and oracle mechanisms satisfies
D(Mx(1) Mo(a))
(E - 1),
D(Mo(g) (M+(g)) s 8 (et/b 1).
Proof. By Lemma 4.4 for every measurable event
S V, we have Pr[Mo(g) E Pr[Mu(g) E F. < exp((E/)..
Pr (r[M+(() E E]
I exp(E/b).
(r[Mo(g) E E]
Taking the supremum over all E = gives
(M Mo(a)) S E
(I s
Applying Lemma B.3 yields the stated inequalities:
D(Mx(q) Mo(a)) S (6th-
D(Mo(g) Mx(2)) S (6 -1).
23

---

B.2.4 Proof of theorem 4.5
(h.0 Let S E Supp(D) be a sample, and let A be a fixed analyst. Consider two k-round interactions with A: one with the hybrid mechanism MH, and one with the oracle mechanism Mo.
For any p > 0, define s¹ = -V 22 In
+ k (e5/0 1). Then
PTMB (T = t) Prum (T t)
PrMo (T'= =1) PRM (T =t)
Pr
In
E² s., and
Pr L-Mo
In
>5" sp
(+MB
Proof of theorem 4.5
Fix an analyst. A and a sample S. To show that
Pr In PIMa (T = t) Prmo (T = t)
Sp
M-
We begin by decomposing the log-likelihodd ratio over the k rounds:
h PEмæ T. = & T t-1il In PR [ = = In Pr.m [ & T 4-11 Pr.o [T = t]
Since the analyst is assumed to be deterministic, the query in the i-th round is fully determined by the history up to that round. Therefore for any mechanism M and for any = (q1, a1..... 9h: ab:aa) Ta. it holds that:
PT[T. = t, T Pr(Q: q: T = t:-1] Pr(M(q)) a;) Pr(M(a)) a;)
M
Next, define the random variable, for any (g1, 01 ................................ 9k. 4x) E TA:
Ca(t,) = =In PIM2 T = t. T = 4-1 In
Pr(MH(q:) = 04) Prmo 77 t T [-1 Pr(Mo((i) =a.)
Then
PFMB (T = f)
PIMO (T = t) Ci(4).
We want apply Azuma-Hoeffding inequality B.4 to the sequence Ci,..., Ck. show that for
any p > 0
h
Pr l~
Σ
C((t))
/ 2k In 1
(1(
e 5 +
f
-1)
sp
b
which implies that
In Prma (T = t)
Pr MM
5" Sp
Proo (T = t)
To apply Sauma-Hoeffding 's incquality (Lemma B.4 to the sequence Cr,..., Ck. it suffices to verify the following conditions for all i E (1...., k/:
Pri~M (IC:(t+) () f) =1
2. For any C1....,G-1 Supp(CC.....,...
E[C, C1 Ba...,,,,,, c--1l b (6/16 1),
We now verify each item in turn. Fix any transcript = (g), ai,..., Ie, ax) E TA
Verification T From Lemma 4.4 for every round i, we have
(t,,,) In Pr[M+(g)) a.)
Se/b. -C,(t)) In Pr[Mo(a: a.] Pr[M a.) E//b
Pr[Mo(g) a.]
Thus for any t E TA:
(C,(t)) b'
24

---

Verification of We begin by bounding the conditional expectation of C2 given any fixed transcript prefix 4 TA Since the analyst is deferministie, fixing 4--1 determines the query yis and the randomness in round lies only in the mechanism's 's response.
E (C((T))
T-11= 4-1]
E ET
Pr Mi
[T. T- C.(())
PRми = T =
E
Pr [ = ti-1]
In
My
Prmo = 11
METa
a] In Pr(Mer(dd) = a) Pr[Mo(1.) a)
Pr(Mp(()) =
aEY
= D((M((a) [o(a)) S & -1),
where the third equality uses the fact that f-- = f4-1, since tz PIMMl [ = t--1). and the final inequality follows from Lemma B.8
Note that CI...., Cs are deterministic functions of the transcript, meaning that the transcript prefix 4-1 fully determines the values C1, c1,-..; G-11- Hence by showing the above bound holds for any transcript prefix in the support TA, it implies the desired conditional expectation also holds for any C1 G--1 E Supp(C1,.... C5-1). Therefore:
E b (65/b 1). E C = cI...., C.-
Conclusion.
Since both items
and hhlld, Azuma Hooma--oef inequality implies that for any
> O,
Ci(tt) > 2h In (
) E + k h
f -1] spp
Pr b
claimed.
A symmetric argument applies the reversed log- lelelkkli ratio, by repeating the analysis with the roles of Mi and Mo swapped. Hence, for any t E Ta, we obtain
In Prmm (T t) PrMo (T'= (t) et sp. and
In PIMo (T= ==
Pr B=
Pr M=
PrM = > sp
B.3 Proof of corollary 4.6
Corollary 4.66 Let A be a fixed analyst, S E Supp(D) a sample, and let be any event that can arise in the interaction with the analyst. For any p > 0, define s* as in Theorem 4.5 Then
e==" (PEMo [ - p) I Pr I ee" PR []] +
Proof. Let B E TA In PrMg (T-t)
Pimo (T=)) E*) be the "bad" event where the likelihood-ratio
bound fails. By Theorem 4.5
PTMæ (8) is al most p. Hence
[r] Pr
E
B) + Pr Pr(En S
Pr(EN p e Pr
[E].
Ma
My
Mo
Mo
Exchanging roles of Mi and Mo yields the lower bound Pr [8] 2 65" (PrMolE) 1 - p).
B.4 Proof of lemma 4.7
Lemma 4.7 Fix an analyst A, a noise scale b, and be the set of e-ood traple-t pairs. Then, for every measurable subset & S G. Pr = Pr [E].
25

---

Proof of lemma 4.7 Run both mechanisms by first drawing the sample S ~ D and then drawing k independent Laplace noises "/1.....> - T/
Laplace((,, b). These draws fix all randomness in the
interaction. On any transcript t in the event &, every query satisfies (g:(S) q:(D) I so by definition, the hybrid mechanism never switches to the oracle mode. Hence for every draw
(S, m... mm........ . M]))) that yields t, both Ms and Mr produce the same Since the joint distribution over (S, ............ Thk ) is identical in both mechanisms, the probability of observing any t & is the same.
B.5 Proof of lemma 4.8
Let and consider k-round interaction between an analyst A and the oracle mechanism, producing the transcript t. Define the failure probability of any of the Laplace noises exceeding a as = Pr[In/| S al*; for 7/1 Laplace(O,, b). Then,
Lemma 4.8
Pr I-D.moPMMo
[(S,t) is e-good and o-accurate] 2 1-k7-6
Proof of lemma 4.8 Since the oracle mechanism operates independently the sample, the queries are chosen independently of the sample. By the definition of (c, concentttti and applying a union bound over all & queries, the probability that the cample-transcript pair E-good is at least - k- Additionally the probability that for all k rounds the oracle's 's response is within a of the true mean is 1 Ç. where represents the failure probability due to the added Laplace noises. Combining these bounds with a union bound yields the desired result.
B.6 Proof of theorem
Let A be an analyst, and My the real-world Laplace mechanism interacting with A over k rounds. For the probability that real-world mechanism produces an a-accurate transcript satisfies
Theorem 4.9
and > 0, define E" as in theorem 4.3 and let be as in lemma Then,
Pr [ = Ms
Tk, 0x) Vi |a: - q: (D)) S a] 2 e -
Proof of theorem 4.9 Lett & denote the event that a sample-transeript pair (S.t) is both e-good
and a-accurate. By Lemma 4.8 we have Pr. [E] 2 by Ç. Applying Lemma 4.6 the probability of & under the hybrid mechanism is Pr [8] 2 e- (PrM. [8] p). By Lemma 4.7 we know the probabilities for E-good pairs are identical for the real-world and hybrid mechanisms, so Pr.ss [8] Pr,m, [E). Since & is subevent of the event that the transcript is a-accurate, we conclude that the probability an a-accurate transcript is at least e e="" (1 - ky - < (-P).
B.7 Detailed derivation of the query bound
Let A be any analyst issuing l adaptive (E, (e.7))-oo cooceetttrt queries, and fix an accuracy parameter 0 and failure probability > Then the Laplace mechanism achieve
Theorem 4.10
(o,, 3) acccurcyy over all ls queries provided = m00mm -
2 Do(1fe)) (111))) }).
a²
Full derivation of the bounds in theorem 4.10
Theorem 4.9 implies that for any fixed a > 0 and
number of queries the real-world mechanism satisfies (a: 3) -ccuurcyy provided
Pr [vi: (S:(S) + 7/s (D) < a] Z (1 k2 < 2 1-B.
As in the proof of Theorem 4.10 set .. The overall failure probability depends four terms: p. k.,, Ç. and e", each of which is bounded by 8/4. Under these conditions, the total success probability is approximated by
-= kn -- p) = -//4 6- - 1 B,
Concretely:
26

---

ii Concentration failure.
by S B
=
k S
47
iii Noise-exceddance failure.
Recall Ç <= 111 - (1 - E a/byk - ke a/b, aa/b Requiring
ke keaah B
k s B c/ 0(3=
(iii) Likelihood-ratio failure. The term E" ln
p) + k
" f ( - 1) must satisfy e* S
b
B/4. With p 3/4 and using the bound e=/b - -1 15 25/b for
E (0, 1). obtain
2 In(4/3)
2k
5
8
6
4
Substitute 2lm[1/3} 50 2e In(1/e)
This yields
(1)7)
Conclusion. Taking the minimum over the three derived bounds on completes the proof of Theorem
27


Reviews:
[{"review_id": "R19504lpxY", "reviewer": "Reviewer_GwEQ", "summary": "The paper considers adaptive data analysis, in the case where the dataset observed by the mechanism _does not_ consist of independent samples - indeed arbitrary correlations are permitted, and relatively weak assumptions on the pair of the query/dataset distribution are inputed.\n\nConcretely, as commonly studied in the area of differential privacy, a fruitful line of work starting with Dwork et al paper, shows that a mechanism given access to $n$ independent samples from a distribution $\\mathcal{P}$ over $\\mathcal{X}$, can provide an $0.1$ accurate answer to a sequence of $O(n^2)$ statistical queries; where a statistical query is specified my \"analyst\", as a function $q_i : \\mathcal{X} \\to [0,1]$, and the mechanism aims to provide answers $a_i$ s.t. $|\\E_{x \\sim \\mathcal{P}} q_i(x) - a_i| < 0.1$. (Naive approach would use $O(1)$ fresh samples for each query, being able to answer only $O(n)$ adaptive queries of this form.)\n\nIn the long line of research on the adaptive data analysis, the assumption that the dataset is given by sampling $n$ independent samples from some distribution is prevalent. This paper, after Bassily and Freund investigates a dramatic weakening of this assupton.\n\nSpecifically, a query $q$ (for a distribution $\\mathcal{D}$ over $m$ tuples in $\\mathcal{X}$) is said to be $(\\varepsilon, \\gamma)$-concentrated, if $\\Pr_{D \\sim \\mathcal{D}}(|q(D) - q(\\mathcal{D})| > \\varepsilon) < \\gamma,$ where $q(D) := \\frac{1}{m} \\sum_{x \\in D} q(x)$ and $q(\\mathcal{D}) := \\mathbb{E}_{D \\sim \\mathcal{D}} q(D)$. If a distribution $\\mathcal{D}$ is a product distribution, any bounded query is $(O(\\log n/\\sqrt{n}), n^{10})$-concentrated, or more generally, it's $(\\varepsilon, \\exp(-\\Omega(\\varepsilon^2 n)))$-concentrated for every $\\varepsilon$.\n\nBassily and Freud showed that there is a mechanism which could answer around $\\tilde{O}(1/\\varepsilon^2)$ adaptive queries as long as they are all $(\\varepsilon, poly(\\varepsilon))$-concentrated; specializing this to a setting where the database is formed by independent samples, this only recovers a simple $O(n)$ query budget (by using fresh samples for each query), as opposed to the improved $O(n^2)$ query budget from differential privacy.\n\nIn this paper, the authors provide a new, simpler analysis qualitatively matching (and slightly improving in lower order terms) the result of Bassily and Freud, as well as provide a new lower bound: for a large class of mechanisms that operates by adding independent noise to a sample average of each query, one cannot hope to answer significantly more than $O(1/\\varepsilon^2)$ queries.", "questions": "The paper is generally quite well written. One striking gap is that throughout the paper, it seems that it is never formally stated what is supposed to mean that the lower bound rules out any mechanism that operated by adding \"any noise\". Looking at the proof in the appendix, we see that the assumptions used in the lower bound proof together are quite unrealistic (they do not capture any of the existing mechanisms), although it seems that this is only for the convenience in the proof, not any intrinsic issues, and the same ideas should provide a lower bound under more realistic noise model.\n\nSpecifically, as I understand it, the mechanism is assumed to provide answers of the form $a_t = q_t(D) + \\eta_t$, s.t. $\\eta_t$ are i.i.d. random variables from some distributions, with $\\mathbb{E} \\eta_t = 0$ (line 816). But in the paragraph on line 218 it is assumed that the outputs are clipped to an interval $[0,1]$ or \"slightly extended\" (some bound on the range is used later in the appendix, in line 826). Discussion about a noise having non-neglible chance exceeding \"any reasonable range\" seems quite imprecise.", "limitations": "The lower bound applies only to a specific type of mechanisms, addition of independent mean-zero noise to each query. This lower bound is not as surprising, since the $(\\varepsilon, \\gamma)$-correlated queries assumption on the data/query distribution is extremely weak (compared to, say independent samples - but also much weaker than many other models of correlated samples). The weak assumptions for the data distribution is a pro for the upper bound, but the mechanism only slightly improves parameters over the original Bassily and Fruend algorithm.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper clarifies completely the situation of adaptive data analysis under the very weak assumptions of Bassily and Freund -- provides a short and intuitive proof of correctness, leveraging ideas from differential privacy (which is standard now in the area - and as simpler and more intuitive, than the previous _ad hoc_ analysis), while simultanously proving a tight lower bound - under this specific weakning of the assumptions, any mechanism that just adds independent mean-zero noise cannot achieve any better trade-offs than proposed here.\n\nThe main two weaknesses are that the lower bound applies only for mechanisms that operate by adding independent noise to a sample average -- there is no specific reason why a mechanism needs to operate this way, so it would be much more interesting to see a more general lower bound (which seems likely, since the conditions are very weak).\n\nAlso, potentially some more explorations whether the $(\\varepsilon, \\gamma)$-concentration condition can be weakened would be interesting. As it is right now, this condition concerns a single point in the tail distribution of a random variable $q(D)$ for $D \\sim \\mathcal{D}$ -- the probability of it's deviation from mean exceeding $\\varepsilon$ should be at most $\\gamma$. When the dataset is given by i.i.d. samples, the random variable $q(D)$ is $1/\\sqrt{n}$ subgaussian, i.e. it is $(\\varepsilon, \\exp(-\\varepsilon^2 n))$-concentrated _for every_ $\\varepsilon$. Would a strenghtening of the conditions to one of this form be enough to obtain an improved upper bound? Or can the lower bound be modified to rule out existance of noise-adding algorithm under this more stringent requirement?", "was_revised": true, "final_justification": "I seem to be a bit less enthusiastic than other reviewers regarding the significance of this specific result; but in the end they do provide a neat, clean and short proof of a upper bound, together with a matching lower bound for a specific class of mechanism. I agree that the general direction of adaptive data analysis is significant, and the goal of understanding how the independence assumption can be relaxed is worth pursuing.", "rebuttal": "Thank you very much for your thorough review. We appreciate your thoughtful comments and will try to address your concerns in turn.\n\n**> The lower bound applies only for mechanisms that operate by adding independent noise to a sample average -- there is no specific reason why a mechanism needs to operate this way, so it would be much more interesting to see a more general lower bound.**\n\nOur lower bound is indeed limited to noise-addition mechanisms. At the same time, noise-addition mechanisms remain a broad and important class, used both on their own and also as key building blocks in many ADA mechanisms. Our lower bound also applies to mechanisms that answer queries by evaluating them on random subsamples (this could be viewed as a form of a mean-zero noise addition mechanism; we will clarify this in the next revision). Thus, our lower bound shows that all known (efficient) techniques for answering a super-linear number of queries in the i.i.d. setting provably fail when correlations are present in the data. As we mentioned at the end of Section 1.1.1, our work steers future work to either impose additional structural assumptions on the problem or introduce fundamentally new algorithmic techniques. Together with our simplified (and improved) positive results, we view this as telling a compelling story.\n\n\n**> This lower bound is not as surprising, since the concentrated queries assumption is extremely weak... When the dataset is given by i.i.d. samples, the random variable $q(D)$ is $1/\\sqrt{n}$ subgaussian. Would a strengthening of the conditions to one of this form be enough to obtain an improved upper bound?**\n\nThe weakness of the concentration assumptions is indeed a limitation of the framework (as our results highlight through the lower bound). We agree that it would be interesting to strengthen these assumptions or to focus on specific distribution structures that arise in practice. We hope our work provides a starting point for future work along these lines.\nYour suggestion about requiring concentration for every value of $\\varepsilon$ is particularly interesting. While we do not answer this question, our attack and analysis offer some initial insight: due to the tradeoff between $\\varepsilon$ and $\\gamma_{\\rm \\scriptsize{Hoeffding}}$​ one can take $\\varepsilon^{\\*}=O(1/\\sqrt(n))$ and proceed with the same construction and information-gathering rounds (since in that regime for any smaller values of $\\varepsilon$, $\\gamma_{\\rm \\scriptsize{Hoeffding}} >1$, thus our information gathering queries remain concentrated for any value of $\\varepsilon$). This implies that data leakage—and therefore membership inference and even full reconstruction of the true sample —remains possible at the rate $\\tilde{O}(1/{\\varepsilon^{\\*}}^2)$. What changes under the stricter requirement is that the final query that \"overfits\" the dataset would no longer be allowed, as it is not concentrated relative to every value of $\\varepsilon$. We hope that such observations could provide useful intuition for future work along the lines of the stronger setting you suggest.\n\n**> The mechanism only slightly improves parameters over the original Bassily and Fruend algorithm.**\n\nIt is true that, quantitatively, our upper bound only slightly improves the previous upper bound. But the analysis is substantially simpler, which we view as an important contribution of our work. We stress that while our analysis is simpler, it does *not* follow from a direct application of the generalization properties of DP to our setting, as is done in the i.i.d. case, and requires our use of the thought experiment of the \"three worlds\" described in Section 1.1.4.\n\n**> One striking gap is that throughout the paper, it seems that it is never formally stated what is supposed to mean that the lower bound rules out any mechanism that operated by adding \"any noise\"... it is assumed that the outputs are clipped...**\n\nThe definition of \"noise addition mechanisms\" is stated in lines 99-101. We meant mechanisms that answer each query using the exact empirical average, after adding to it random mean-zero noise (independent of the previous noises). We will clarify this further in the body of the paper.\n\nSince queries are bounded in [0,1], any response outside the range of [-1,2] would already violate the accuracy requirement. In other words, if an answer falls outside of the interval [-1,2] then the mechanism fails and we (the attacker) win. Thus, in the proof of the lower bound we allowed ourselves to assume that the answers are always in the range [-1,2]. We agree that the terminology we used about this can be made more precise, and we will restate this in the next revision of our paper."}, {"review_id": "GTIQgGGCwC", "reviewer": "Reviewer_MjLV", "summary": "This paper studies the problem of answering adaptive queries under the restriction that the queries are $(\\varepsilon, \\gamma)$-concentrated around its means. This concentration assumption is needed to enable adaptive analysis on dataset with correlations (beyond the typical i.i.d setting). They provide query bounds that are tight up to logarithmic factors when the query answer provider is restricted to noise addition mechanisms.\n\nTheir impossibility result is new and implies an inherent gap between i.i.d. setting and setting with correlations (when restricted to noise addition mechanisms). While the newly provided noise addition mechanism is only a logarithmic improvement over the prior work, the analysis, combining ideas from differential privacy, is simplified compared to previous works.", "questions": "Suggestion and typos:\n1. I am surprised to see the $O(n)$ v.s. $O(n^2)$ gap persists even if the queries are tightly concentrated as Hoeffding bound. Is there a intuitive explanation to why Hoeffiding bound is insufficient to support more queries in correlation setting. What other properties of i.i.d. setting are exploited to obtain the $O(n^2)$ query result.\n2. Maybe give one simple example to show why adaptive queries are hard to answer, in the spirit of the example given in 56-62? What can the adaptive adversaries do to make the query answering hard?\n3. On my first read-through, I was confused by the expectation on Line 44 as it is a bit uncommon to treat a tuple or an entire dataset as \"a fresh sample\": $T \\leftarrow D$. Perhaps it would read better if you repeat here that $T$ is a tuple or an entire dataset.\n4. On Line 90, should $q(T)$ be the average of the tuple like what you wrote on Line 44 or on the same line? It doesn't make sense to me otherwise.\n5. In the standard upper and lower bounds kind of language, Theorem 1.4 and Theorem 1.5, is quite the opposite -- the hard instance (typically called lower bound) has larger values than what is reflected in the algorithm (typically called upper bound). Perhaps, it would be easier for folks like me to read if you add a note somewhere nearby explaining that query bounds are indeed the opposite of the time complexity bounds?\n   On that note, maybe it’s worth drawing a 2D-graph depicting the feasible regimes and infeasible regimes here to kind of map out this $\\min(1/\\gamma, \\ln(1/(\\eps \\gamma))/\\eps^2)$ v.s. $\\min(1/\\gamma, 1/(\\eps^2 (\\ln(1/\\eps))^2))$ query bounds?\n6. On Line 133, there is a typo, $\\delta$ should be $\\gamma$.\n7. On Line 139, it reads \"A simplified positive result\". On first read-through, I thought this was a simplified result compared to a more involved and general result in your work. Maybe change this to “alternative” or “A positive result based on techniques from differential privacy” or \"A simplified positive result compared to *Bassily and Freund [2016]\"*?\n8. I guess idea of Algorithm 1 is based on the idea from Line 226-232 -- identify the one query that can fail the mechanism? Probably it will the reading easier if the authors add the connection to this simpler starting example on Line 251 (attack overview).\n9. On Line 253: why focus on $\\mathcal{X}_1$, can we also make the same argument on $\\mathcal{X}_2$?\n10. From the presentation of the Algorithm 1 (or the description from Line 251-263), it is can be unclear that the Bernoulli chosen is fixed for the same $x$, i.e., it can be confused with the case where each query is simply randomly picking a fresh Bernoulli sample with parameter $p_t$. While it is clear once you take a look at the proof in the Appendix, I would suggest the authors to rewrite this part to make it clear that $q_t(x)$ is determinisic once you fix the random seeds of this Bernoulli (or make $q_t$ take the random seeds as one of the inputs).\n11. On Line 337, there is a typo double comma: \", ,\".", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n1. This paper is well written and clear in its presentation. I appreciate the example given in the introduction in addition to the informal proof techniques, which are also very helpful for understanding the proofs.\n2. While I did not fully check proofs in the Appendix, the proofs and proof sketch on the main body seem solid.\n3. Their result settles the problem (up to logarithmic facotrs) when the mechanism is restricted to adding noise.\n\nWeaknesses:\n   While the question considered is indeed quite interesting, I fail to see the motivation to restrict the setting to noise addition mechanism. Maybe the authors would like to give some more background on this aspect? Was this a popular or most promising method to study before this work?", "was_revised": true, "final_justification": "I maintain my ratings after the discussion.", "rebuttal": "Thank you for your detailed and helpful review. We greatly appreciate the comprehensive suggestions and corrections regarding clarity, readability, and typos, and we will address them carefully in the revision.\n\n**> I fail to see the motivation to restrict the setting to noise addition mechanism. Maybe the authors would like to give some more background on this aspect? Was this a popular or most promising method to study before this work?**\n\nNoise-addition is a very popular approach, used both on its own and as a fundamental building block in many ADA algorithms. Our lower bound also applies to mechanisms that answer queries by evaluating them on random subsamples (this could be viewed as a form of a mean-zero noise addition mechanism; we will clarify this in the next revision). Thus, our lower bound shows that all known (efficient) techniques for answering a super-linear number of queries in the i.i.d. setting provably fail when correlations are present in the data. As we mentioned at the end of Section 1.1.1, our work steers future work to either impose additional structural assumptions on the problem or introduce fundamentally new algorithmic techniques. \n\n**> I am surprised to see the $O(n)$ v.s. $O(n^2)$ gap persists even if the queries are tightly concentrated as Hoeffding bound. Is there an intuitive explanation to why Hoeffiding bound is insufficient to support more queries in correlation setting? What other properties of i.i.d. setting are exploited to obtain the query result?**\n\nThis is indeed a surprising result and one of the compelling insights of our paper. To gain intuition for this gap, consider first the simpler i.i.d. setting. A typical query in the i.i.d. scenario has a standard deviation on the order of $O(1/\\sqrt(n))$. Thus, naively, to \"hide\" deviations in even a single query, one might expect to add noise of this magnitude. By leveraging advanced composition arguments from the literature of differential privacy, answering $k$ adaptive queries would therefore (naively) require noise on the order of $O(\\sqrt(k)/\\sqrt(n))$, limiting the number of queries $k$ to be linear in $n$. The key strength of differential privacy in the i.i.d. setting is that the magnitude of noise needed per query only needs to \"hide\" every single sample point, which translates to significantly less noise than the standard deviation. This is what enables answering a super-linear number of adaptive queries in the i.i.d. setting. However, our result shows that once correlations are introduced—even with queries that satisfy strong concentration properties— this advantage disappears. In other words, when correlations are present in the data, our results show that (in general) one must add noise of the order of the standard deviation, and that \"hiding\" every single sample point is insufficient."}, {"review_id": "YoQm0OC7X8", "reviewer": "Reviewer_Whdi", "summary": "This paper studies adaptive data analysis beyond the iid setting. Given a dataset drawn (perhaps non-iid) from a distribution $\\cal{D}$ over datasets, the goal is to answer as many adaptively chosen statistical queries as possible, up to some error tolerance (relative to the expectation over $\\cal{D}$) and failure probability.\n\nIn general, in the non-iid setting, there is no hope that this is possible, even if the queries are non-adaptive. This paper studies the restricted setting where the queries are enforced to be those which exhibit concentration in the non-adaptive setting. A query is $(\\epsilon, \\gamma)$-concentrated if the probability that the query deviates from its expectation by more $\\epsilon$ is at most $\\gamma$. In the non-adaptive setting, $1/\\gamma$ of these queries could be answered all up to error $\\epsilon$ with probability $3/4$ by a standard union bound. The main question addressed in this paper is what is the cost of adaptivity in the concentrated query setting?\n\nPrior work of Bassily and Freund gave an algorithm allowing for $\\tilde{O}(1/\\epsilon^2)$ queries for $(\\epsilon, n^{-10})$-concentrated queries. This allows for $\\tilde{O}(n)$ queries which exhibit standard $1/\\sqrt{n}$ error bounds, which is significantly less than results for adaptive queries in the iid setting which allow for quadratically many queries. The authors show that this is inherent to noise-additive mechanism for this problem (which include Bassily and Freund's result). Such mechanisms cannot accurately answer more than $\\tilde{\\Omega}(1/\\epsilon^2)$ queries. On the upper bounds side, the authors give a simplified upper bound achieving this rate (up to log factors) via differential privacy.", "questions": "What is known about algorithms which do not fall into the class of \"noise-additive\" algorithms?\n\nAre there natural weaker or incomparable restrictions of the allowable queries which may allow stronger positive results?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper forms a nice picture about how the restriction of correlated queries can be used to adaptively answer statistical queries. The picture is essentially complete under the restriction of noise-additive algorithms, with new lower bounds showing that the concentrated queries setting does not allow for the same performance as in the i.i.d. case.\n\nThis result can help to guide research towards other relaxations of the i.i.d. assumption that may allow for stronger adaptivity results.\n\n## Minor Comments\n\nLine 116: of -> or\n\nIn Theorem 1.4 and 3.1, I would use big-O rather than big-$\\Omega$ for $k$ as the result is giving an upper bound on the smallest $k$ required to break the mechanism. (Though I understand the usage of these two notations is often somewhat subjective.)", "was_revised": true, "final_justification": "I maintain my positive score for the reasons given in the review.", "rebuttal": "Thank you for your helpful suggestions and for pointing out the typo; we will address these in the next revision of our work.\n\n**> What is known about algorithms which do not fall into the class of \"noise-additive\" algorithms?**\n\nCurrently there are two known techniques for (efficiently) answering adaptive queries when correlations are present in the data: \n\n**(1) Noise addition.** With correlations, all existing noise-addition mechanisms support at most $O(n)$ queries. We show that this is a barrier one cannot cross, despite the fact that, in the i.i.d. setting, noise addition supports up to $O(n^2)$ queries.\n\n**(2) Transcript compression.** Another technique for efficiently answering $O(n)$ queries when correlations are present is based on \"transcript compression\" (a.k.a. \"Bounded description length\"). But this technique only answers $O(n)$ queries even in the i.i.d. setting, and so one should not expect it to support a super-linear number of queries in the correlated case.\n\nOur lower bound also applies to mechanisms that answer queries by evaluating them on random subsamples (this could be viewed as a form of a mean-zero noise addition mechanism; we will clarify this in the next revision). Together, our lower bound shows that all known (efficient) techniques for answering a super-linear number of queries in the iid setting provably fail when correlations are present in the data. \n\n**> Are there natural weaker or incomparable restrictions of the allowable queries which may allow stronger positive results?**\n\nOne natural direction for future work is to consider queries satisfying stronger concentration constraints, such as sub-gaussian queries. Another promising direction—potentially more applicable to natural scenarios—would be to impose stronger structural constraints on the underlying data distribution, while still relaxing the strict i.i.d. assumption."}, {"review_id": "HzupwanRML", "reviewer": "Reviewer_LHqT", "summary": "This work considers an adaptive data analysis (ADA) game between an adversarial analyst $A$ and a mechanism $M$. In particular, $M$ is provided with a set $S$ of $n$ samples from a domain $X$ drawn from a distribution $D$. Then over $k$ rounds, $A$ submits queries $q_j  \\colon X \\to [0,1]$, and $M$ must return an answer $a_j \\in \\mathbb{R}$. The mechanism’s goal is to produce answers ($a_j$’s) that are close to the average value of the query over the true distribution, but the catch is that $M$’s only knowledge of the distribution is through the sample $S$ it holds. The question is, how many queries can $M$ answer accurately? (Defined by an error parameter $\\alpha$ and a confidence parameter $\\beta$.) As the number of samples, $n$, increases, $M$ is able to answer more queries. \n\nThis problem is well-studied under the assumption that the $n$ samples are obtained independently, and here it is known that $\\Theta(n^2)$ queries can be answered. If this independence assumption is removed without changing anything else about the problem, then this problem suddenly becomes impossible, as the authors point out with a simple example. One way forward is to then restrict the types of queries that the analyst is allowed to make. This work continues in the footsteps of Bassily-Freund 2016, who considered this question when the analyst is only allowed to make queries that are well-concentrated around their mean.\n\nIt was known due to prior work that $O(n)$ queries can be answered in this setting, quadratically fewer than when samples are independent. This work shows that this quadratic gap is necessary for all noise addition mechanisms, which are a natural special class. On the other hand, they provide a simpler analysis of the mechanism due to Bassily-Freund using techniques from differential privacy.", "questions": "Suggestions / questions:\n\nIt took me a bit of time to parse and understand the definition of the analyst-mechanism game on page 1, although I was able to do so after some thought. However, it feels like the presentation could be improved a bit by providing a natural example and explaining what the different objects ($A,M,D$ queries, etc.) represent in the example.\n\nInstead of limiting the types of queries made by the analyst, what if one relaxes the independence assumption a bit? Are there known bounds for this problem quantified in terms of “how independent” the samples are guaranteed to be? \n\nMinor typos and comments:\n\nLine 44: Should $q_j$ be just $q$ in this expression?\n\nLine 49: “of sample” should be “of the sample”?\n\nParagraph labeled “1” on page 2 contains a few typos: “chose” -> “choose”, “to to” -> “to.\n\nLine 112: “adhere the” -> “adhere to the”?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: This paper is nicely written in my opinion. I also appreciate the theme of the paper which is to remove a rather strict assumption (sample independence) from a natural statistical algorithmic problem. The paper makes nice contributions in this direction by proving a lower bound for a natural class of mechanisms and simplifying existing upper bounds by tying in established techniques, which I believe is valuable. \n\nWeaknesses: The fact that the lower bound only holds for a certain special case of mechanisms could be considered a weakness. \n\nOverall, I think the paper merits acceptance.", "was_revised": true, "final_justification": "I believe this is a well-written paper with nice results which is above the bar for NeurIPS. I am keeping my score a 5.", "rebuttal": "Thank you for your constructive review and helpful suggestions. \n\n**> The fact that the lower bound only holds for a certain special case of mechanisms could be considered a weakness.**\n\nOur lower bound is indeed limited to noise-addition mechanisms. At the same time, noise-addition mechanisms remain a broad and important class, used both on their own and also as key building blocks in many ADA mechanisms. Our lower bound also applies to mechanisms that answer queries by evaluating them on random subsamples (this could be viewed as a form of a mean-zero noise addition mechanism; we will clarify this in the next revision). Thus, our lower bound shows that all known (efficient) techniques for answering a super-linear number of queries in the i.i.d. setting provably fail when correlations are present in the data. As we mentioned at the end of Section 1.1.1, our work steers future work to either impose additional structural assumptions on the problem or introduce fundamentally new algorithmic techniques.\n\n**> It feels like the presentation could be improved a bit by providing a natural example and explaining what the different objects represent in the example.**\n\nThank you for this suggestion; we will try to make the introduction of the general setting more accessible and will also correct the typos you noted in the next revision of our work.\n\n**> Instead of limiting the types of queries made by the analyst, what if one relaxes the independence assumption a bit? Are there known bounds for this problem quantified in terms of \"how independent\" the samples are guaranteed to be?**\n\nThis is indeed a promising direction for future work. One recent work (Kontorovich et al., 2022) addresses this setting, where the bound depends on a measure of the distance between the underlying distribution and a product distribution. To the best of our knowledge, no other results directly address these questions. Further investigation of this problem, particularly for distributional structures that naturally arise in sampling scenarios and have practical applications, would be a valuable direction for future research."}, {"review_id": "yqd4MjaUNb", "reviewer": "Reviewer_oH1p", "summary": "The authors study the limitation of adaptively answering $(\\alpha,\\beta)$-statistically accurate queries. Their main (negative) result shows, given the underlying distribution is $(\\epsilon,\\gamma)$-concentrate, no mechanism can adaptively answer more than $1/\\gamma \\wedge 1/\\epsilon^2\\log(1/\\epsilon\\gamma)$ queries. The authors also provide a positive result that roughly matches the above bound up to polylog factors with respect to $\\epsilon$ and $\\gamma$.", "questions": "1. What would be the canonical distributions (beyond i.i.d.) that satisfy the concentration property? e.g. maybe finite-state Markov chains with a concentrated stationary distribution, or some martingales?\n\n2. page 2, line 44, $\\sum_{x\\in T} q(x) \\rightarrow \\sum_{x\\in T} q_j(x)$?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n> The results appear to be quite significant. It is potentially fundamental, given the natural formulation of the problem. Although I am not an expert in differential privacy, the authors’ findings still look very interesting to me. Thus it is likely to attract interest well beyond the privacy community.\n\n> The paper is enjoyable to read. Despite not having a background in privacy, I found the problem setup very clear, the significance of the results compelling, and the proof techniques both accessible and well-explained. The proof (based on what I read) is also well-structured and clear. \n\n> The lower bound proof is very clever. The simplified ($1/\\gamma$) version is quite simple but already interesting. The general version is pretty neat. \n\nWeaknesses:\n\nI do not see any significant weaknesses from my perspective. However, I believe the paper could be more impactful if the authors elaborated further on the potential applications of these adaptive queries, as there may be many relevant use cases.", "was_revised": true, "final_justification": "The authors have answered my questions. I'll keep my (already high) score.", "rebuttal": "Thank you for your thoughtful review. We will correct the typo you identified and expand on the motivation for considering adaptive queries in the next revision of our work.\n\n**> What would be the canonical distributions (beyond i.i.d.) that satisfy the concentration property?  e.g. maybe finite-state Markov chains with a concentrated stationary distribution, or some martingales?**\n\nAny canonical distribution that is known to satisfy a concentration bound analogous to Hoeffding’s inequality for i.i.d. samples (e.g., Azuma’s inequality for martingales with bounded differences) would indeed satisfy the concentration property. Exploring such distributions, particularly those that naturally arise in real-world sampling scenarios, is a promising direction for future work. Many of these distributional structures provide stronger concentration guarantees than the general assumption used in this paper, while still relaxing the very strict i.i.d. assumption."}]

Author rebuttal:

Meta-review: This paper studies the problem of answering adaptive queries under the restriction that the queries concentrated around their means. The paper uses differential privacy to provide a simplified upper bound matching previous results by Bassily and Freund, as well as nearly tight query bounds for noise-additive mechanisms. Although all reviewers agree that the lower bound essentially closes the gap quantitatively, all reviewers also initially expressed concerns about the richness of noise-additive mechanisms. However, these concerns were addressed during the author-reviewer discussion phase. 

I would encourage the authors to address reviewer concerns and to include expanded versions of the author response regarding noise-additive mechanisms, e.g., subsampling, to strengthen the potential impact of the work.
Decision: Accept (poster)