Adaptive Data Analysis for Growing Data
Authors: Neil G Marchant
Benjamin I. P. Rubinstein
Venue: NeurIPS 2025 poster ()
Keywords: adaptive data analysis
generalization
differential privacy
false discovery
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We obtain the first generalization guarnatees for adaptive data analysis in a setting where data grows over time.

Abstract: Reuse of data in adaptive workflows poses challenges regarding overfitting and the statistical validity of results. Previous work has demonstrated that interacting with data via differentially private algorithms can mitigate overfitting, achieving worst-case generalization guarantees with asymptotically optimal data requirements. However, such past work assumes data is _static_ and cannot accommodate situations where data _grows_ over time. In this paper we address this gap, presenting the first generalization bounds for adaptive analysis on dynamic data. We allow the analyst to adaptively _schedule_ their queries conditioned on the current size of the data, in addition to previous queries and responses. We also incorporate time-varying empirical accuracy bounds and mechanisms, allowing for tighter guarantees as data accumulates. In a batched query setting, the asymptotic data requirements of our bound grows with the square-root of the number of adaptive queries, matching prior works' improvement over data splitting for the static setting. We instantiate our bound for statistical queries with the clipped Gaussian mechanism, where it empirically outperforms baselines composed from static bounds.

Adaptive Data Analysis for Growing Data
Neil G. Marchant
Benjamin I. P. Rubinstein School of Computing Information Systems University of Melbourne, Australia brubinstein Ceneetteeieuiiiinnmm Coulmmmmb.. edu. au
School Computing & Information Systems University of Melbourne, Australia nmarchant ierraanttummmmllm edu.au
Abstract
Reuse of data in adaptive workflows poses challenges regarding overfitting and the statistical validity of results. Previous work has demonstrated that interacting with data via differentially private algorithms mitigate overfitting, achieving worst- case generalization guarantees with asymptotically optimal data requirements. However, such past work assumes data static and cannot accommodate situations where data grows over time. In this paper we address this gap, presenting the first generalization bounds for adaptive analysis on dynamic data. We allow the analyst to adaptively schedule their queries conditioned on the current size of the data, in addition to previous queries and responses. We also incorporate time-varying empirical accuracy bounds and mechanisms, allowing for tighter guarantees as data accumulates. In a batched query setting, the asymptotic data requirements of our bound grows with the square-root of the number of adaptive queries, matching prior works' improvement over data splitting for the static setting. We instantiate our bound for statistical queries with the clipped Gaussian mechanism, where it empirically outperforms baselines composed from static bounds.
Introduction
The ubiquity of adaptive workflows in modern data science has raised concerns about the risk of overfitting and the validity of findings [1, 2]. In such adaptive workflows, data is reused over multiple steps, where the procedure analysis at any given step may depend on results of previous steps. Common examples include hyperparameter tuning or model selection on hold-out set [3-5], blending of exploratory and confirmatory data analysis [6, 7], and the reuse benchmark/public datasets within a research community [8]. While adaptivity can enable more exploratory analysis, it not covered by conventional guarantees of generalization and statistical validity, which assume the analysis is selected independently of the data [9].
simple approach for enabling adaptive data analysis with generalization guarantees is collect fresh dataset whenever step in the analysis depends on existing data. This can also be achieved by randomly splitting dataset and using separate split for each step. However, the data requirements of this approach may be prohibitive, scaling linearly in the number of adaptive steps. A line of work based on algorithmic stability [9-18] offers a significant improvement over data splitting, with data requirements that grow asymptotically with the square- root of the number of adaptive steps. The core result of this line of work transfer theorem, which guarantees that the outputs of adaptive analysis are close to the expected outputs on the data distribution if (i) the analysis is stable under small changes to the dataset and (ii) the outputs are close to the empirical average on the dataset. Differential privacy [19] is commonly adopted as notion of stability in this work, achieving the rouare-root dependence mentioned above, which is asymptotically optimal in the worst case [20, 21].
Most prior work on adaptive data analysis via algorithmic stability assumes a common setting, where the data is sampled i.i.d. from an unknown distribution and used by mechanism to estimate an analyst's adaptive queries [9, 10, 15]. Generalization bounds are then obtained for a worst-case data
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

distribution and worst-case analyst, who is actively trying to overfit. More recently, variations of this setting have been studied in an attempt better reflect how data used in practice [14, 18. 22, 23]. This includes replacing the assumption of i.i.d. data with weakly correlated data [23], or replacing a worst-case analyst by a dynamic model [22]. Concurrent work has also made progress on the former, providing generalization guarantees for correlated data by constraining the analyst to class of "concentrated" queries [24].
A limitation of all prior work is the assumption that data is collected before the analysis begins, and remains static thereafter. However, it common in practice for data to grow over time, and it may be undesirable to wait for all data to arrive or to ignore data that arrives after an analysis has begun. This growing data setting has been studied in the differential privacy literature, both for adaptive queries [25, 26] and for updating fixed query whenever a dataset changes [27-30]. In this paper, we bridge the gap, obtaining the first generalization guarantees for adaptive data analysis (ADA) in the growing setting. We consider a fully adaptive analyst, who can determine not only the content of their queries, but also the timing and frequency of their submissions on-the on-the-fly. conditioned on the current size of the data, well as all past queries and responses.
fly. This schedule can be
To tackle the growing data setting, we introduce definitions and techniques that extend beyond existing ADA frameworks. A key innovation is our approach to bounding query error, which, following Jung et al. [15], incorporates a term comparing the query results evaluated on a posterior data distribution and the true data distribution. Our insight is that for the growing data setting, the posterior distribution must be marginalized over unseen future data the time query is submitted a crucial departure from the static setting where the full dataset is known in advance. This yields a transfer theorem that depends on a corresponding variant of posterior stability. This dynamic nature of the posterior, whose support grows in a way that depends on the analyst's adaptive schedule, requires significant new analytical ideas to prove the conversion from differential privacy to posterior stability, which are instrumental in obtaining DP-based transfer theorems. This results in additional factor in the error bound (compared to the static case for linear queries) proportional to the percentage increase in the dataset size.
We propose a non-unn non-uniffrm generalization of (e, diffecrential privacy where the parameter varies for each data point/time step. inspired by personalized privacy [31]. This permits us to obtain tighter generalization guarantees- the error bound increases as a function of the average 5 over all time steps, rather than the maximum 5 under the standard DP definition. These theoretical advances culminate in new bounds for various query types, including statistical queries, sen-iensitivity queries, and low-sensitivity minimization queries using non-uniform differential privacy as stability measure.
As concrete application of our guarantees we consider using the clipped Gaussian mechanism to answer adaptive statistical queries. To ensure tight privacy accounting when the number of queries at each time step is chosen adaptively, we leverage a privacy filter [32] which supports fully adaptive composition. Our bound empirically outperforms baselines composed from bounds for static data. In a batched query setting, the asymptotic data requirements of our bound grow with the square-root of the number of adaptive queries for a fixed accuracy goal (assuming the ratio of final to initial data size is held constant). This improvement matches the improvement of bounds for static data [15] over the data splitting baseline.
2 Preliminaries
We introduce notation used throughout the paper. The sequence of integers from ny to n22 inclusive is denoted by [n], or [na] when n1 = 1. Given a sequence ar, we refer to the t-th element as a, and the length as |ax]- We use [x] to denote the subsequence of x containing elements from index t to 12 inclusive, or Øfe2 when & 1. We use capital letters for random variables and lower case letters for realizations of a random variable. The uniform distribution over set S is denoted (S) and the normal distribution with mean ju and standard deviation a is denoted A (H,,²)) The product distribution of i.i.d. random variables drawn from D is denoted D""
2.1 Formulating Adaptive Data Analysis (ADA) for Growing Data
We propose a new formulation of adaptive data analysis for growing data that builds on prior work for static data [9, 10, 15].

---

Round
Daraset
Mc Mechanism
F
TC: Transcript
Analyst
Figure 1: Schematic of our setting for adaptive data analysis growing data. The dataset is of size no when the analysis begins, and grows by one data point in each round. The analyst asks queries adaptively in each round based past responses, and receives response from the mechanism before selecting the next query. The framework reduces to the static data setting when n = no-
Dataset. Let P be unknown data distribution
finite domain X' We consider growing dataset X = (X1, XK,,......) where each data point X, is drawn i..dd from P, and the data points are indexed in order of arrival. We define the snapshot of X at index be the portion of the data realized by index 4, namely X X1q-
We study datasets over fixed horizon n so that X n.
Analyst and mechanism. We consider an analyst A who would like to estimate queries about the data distribution P online using the growing dataset X. The analyst asks queries from fixed query class Q. such the class of statistical queries (see Section 2.2). The analyst is prohibited from accessing X directly, but can instead submit queries to an online mechanism M that returns estimates using the current snapshot of X. We assume M produces feasible estimates, meaning estimates guaranteed to fall within the range of the query. This can be achieved by design [33] or by modifying M project infeasible estimates onto the range of the query.
Interaction. Algorithm specifies how the an- alyst interacts with the mechanism. To begin, the analyst selects an initial dataset size no S n and waits for the mechanism receive no data points (lines and 4). The analyst then submits queries to the mechanism over multiple rounds,
Algorithm Interaction between A and M
1: Wait for M to receive data X X
2: Initialize empty transcript II
3: for Round E [[vo, do
Wait for M to receive next data point Xx while Analyst not finished do
5:
where each round is marked by the receipt of data point (lines 3-10). The rounds are
6:
Generate query: Q ~ A(II)
7:
Estimate query response: R ~ M(Q: xgg
indexed starting at no so that index coincides
8: Append (Q, R) to II, in-place
with the size of the growing dataset. The num-
end while
ber of queries asked mined adaptively by the analyst (line 5). Since the analyst adaptively controls when each round terminates, they can force the mechanism to use stale snapshot of the dataset X1q even if newer data points (with indices > t) have arrived and are waiting to be ingested by the mechanism.
given round / is deter-
10:
end for
11: return Transcript 11
The interaction yields transcript II of the queries submitted in each round and the estimates produced by the mechanism (lines and 8). The transcript structured as a sequence of sequences II (II, Il, ... II,)) where II, ((Qu,1, RR,1,, (Q1,s, R,,,)) records the query- estimate pairs from round t in the order they were submitted. We denote the space of possible transcripts by T UkeS(n,A) IT
Transcript.
Riki, where is the query class, R is the range of the
queries and (mn, k) = [ E [|']" (Vt < nk) = 0) A Σn he = k} is the set of possible allocations queries across n rounds.!
Looking ahead, we will be interested in the stability of the transcript under perturbations to the dataset. is therefore convenient to interpret the interaction in Algorithm as a random map I( (X; A, M) that takes growing dataset X E 2 as input and returns a transcript II E T output. We view A and M as parameters of I, and drop the dependence on them where it is clear from context.
In the definition of S(n, k). the first statement in the predicate accounts for the fact that the analyst does not begin submitting queries until round nio.
3

---

2.2 Query Classes
Following prior work [10, 15], we consider three query classes. We use ((<(a)) to denote the result of a query q E Q evaluated a snapshot 311] and g(D) to denote the result evaluated on data distribution 'D.
Low-sensitivity queries are defined by A A-sessitive function X [0, 1] that maps data snapshot to a scalar on the unit interval. We say q is A --sessitive given A = (Ai...., An) E RR. for all E [n] we have (2(()1)) (( I A, for any pair of neighboring snapshots æ Z[ X² that differ one data point. The result of the query when evaluated on data distribution D is (D) = ExExxxlle (x))]
Statistical queries are a subset of A A-sensitive queries where each query is of the form ((*(g)) =
Σ ((z))/t for some function q X - [0, 1]. Since each query is fully specified by q. we refer to q as q when there is no ambiguity. The sensitivity satisfies A, S 1/1 for all E [re]]-
Minimization queries are solutions to parameter optimization problems defined by data-dependent loss function. Due to space constraints, we discuss them in Appendix A.
2.3 Generalization and Stability
Algorithm/ 1 may fail to generalize if the mechanism leaks detailed information about the dataset that is exploited by the analyst when selecting queries. The degree of leakage is related to the stability of the interaction under perturbations to the dataset. Roughly speaking, a more stable interaction lcaks less information and is more likely to generalize. In Section 3, we will derive generalization guarantees that depend on the stability of the interaction. In preparation, we now define how generalization and stability will be measured. For clarity of exposition, we focus on low-sensitivity and statistical queries here, and extend to minimization queries in Appendix A.
Consider the mechanism's response R to query Q in round 6, for which the "true" answer to the query is the expected value on the data distribution, denoted Q(P"). We measure generalization of R terms of the absolute difference R - Q(P'),, which we refer to as the distributional error. Our generalization guarantee for the analysis as a whole, takes the form of a high probability bound on the worst-case distributional error that holds jointly over all rounds, as defined below. Note that we consider bounds the error a that vary function of the round index t, which permits the bound to improve as the dataset grows.
for all 1 [mo,n] and distributionally accurate if with probability 1 1 8 over the randomness in the dataset X ~ pn and transcript 11 1(X; A, M). the largest distributional error in the t-th round satisfies maxx(Qmmenll R Q(P*)) I at,, and this holds jointly for all t E [no, n.]. for any analyst A and any data distribution P.
Definition 2.1. Let 0z
0. A mechanism M is (fa,), ())
When deriving distributional accuracy bounds in the next section, we make use of a related accuracy bound that compares the mechanism's responses raw empirical estimates evaluated on the current data snapshot. Consider again the mechanism's 's response / to query Q in round t, where the raw estimate using snapshot X14 is denoted ((1).)) We define the snapshot error of to be the absolute difference |R - (+))))). By analogy with Definition 2.1, we then define the following accuracy bound using snapshot error.
Definition 2.2. Let 0g 2 0 for all / E [ro, n| and 3 2 0. A mechanism M is (far), (atee)))))sm) -nssshoto accurate if with probability 1 over the randomness in the dataset X ~ pp and transcript IT ~ I(;; A, M), the largest snapshot error in the 1-th round satisfies max(Q_.R)I.L R Q(X (1)) $ oz. and this holds for all t E [no, m1. for any analyst A and any data distribution P.
As previously mentioned, our generalization guarantees depend on the stability of the interaction. We adapt the notion of posterior stability introduced by Jung et al. [15] to the growing data setting. For a query Q in round t, it measures stability in terms of the absolute difference between the "true" answer
2 H. and (xx (1) do generally coincide, since the mechanism may inject noise in its estimates. $ *Cummings et al. [25] adopt similar definition of accuracy for a DP mechanism operating on a growing dataset. However their definition assumes a non adappiveive analyst and holds for worst-case dataset, whereas ours holds for worst-case adaptive analyst assuming the growing dataset is drawn from p

---

Delinition 2.2
Stutistical queries
Lemma
Delinition 2.4 Differcatial privacy
Snapshot accuracy
DP transfer theorem
DP to PS conversion
Bounded queries
Lemma Posterior uccuracy
Theorem 3.2 PS transfer thevrem
Theorem 3.6 DP transfer theorem
Lemmna DP to PS conversion
A-scusitive queries
Lemma
Definition Postetior stability
Theurem A.3 DP transfer theorem
Resampling Lemma
queries
Figure Outline results in Section 3. Arrows indicate key dependencies, and dashed boxes indicate results that hold for a particular class of queries.
evaluated on the data distribution Pt, and the answer evaluated on the posterior data distribution Of := pt II. As in the static setting, the posterior data distribution is conditioned on the full transcript II at the end of the interaction, however unlike the static setting, the distribution is only taken over the data available up to round t.
Definition 2.3 ([15)). Let ê 2 0. An interaction I(- .. M) is (e, -ooottrii stable, or (e, 8)-P for short, if with probability II ~ ((X; A, M), we have m R)).. any analyst A and any data distribution P.
over the randomness in the dataset ~ p and transcript
/tr.e,./(.PP)) IQ(Pt) Q (())) I e for all t [no.n]. nI. and this holds for
We will show that posterior stability follows from differential privacy [19]. We consider variation of the standard definition of differential privacy, where the level of privacylstability varies non-uni non-uniformly over data points. Similar definitions have been used in dynamic data settings [34, 35] to facilitate tighter privacy accounting. We have the same motivation here-by bounding the ó parameter for each data point separately, we can obtain tighter generalization bounds.
Definition 2.4. Let e 2 and 8: [n-] + [0, 1]. An interaction I(-: M) is (e, 8) diiffeerentiall private, or (e, -DP for short, if for all analysts A, all rounds t E [[]]] all pairs of neighboring growing datasets (ar, x') E N2 differing on the t-th data point, and all measurable events E CT:
P(I(x:A,M) e E) S e (I(²)A,,M) E) + 8(t).
We consider bounded neighboring relation, meaning that Mr contains pairs of datasets (xr, æ²) where a can be obtained from x' by replacing the (-th data point. We note that this non-uniform privacy definition includes the standard (uniform) definition a special case: in particular, (c, 6DD implies (c, max, -Dt) We refer the reader to Appendix D for discussion and results on non- non-uniform DP.
As a stability measure for adaptive data analysis, DP has several advantages. First, DP can be interpreted as a privacy guarantee, not merely a bound on stability. Second, DP has been widely studied in statistics and machine learning for almost two decades, so there are established private mechanisms for common data analysis and learning tasks. Third, DP supports composition which simplifies privacy accounting of the interaction. For example, one could instantiate privacy filter [32, 36) for a differentially private query-ans anery-nnseering mechanism with target privacy parameters and This then allows for adaptive selection of the analyst's 's queries, the mechanism's algorithm, and the privacy parameters for individual queries, noting that the interaction may be forced to terminate early to ensure it satisfies (e, DD. The pest-processing property of DP is essential for this accounting to work, as the analyst's is selection of the next query is viewed as post-process post-processing on the mechanism's private estimates previous queries. As result, the analyst does not accrue additional cost to privacy/stability, even the worst case.
3 Generalization Guarantees for ADA on Growing Data
In this section, we present generalization guarantees for ADA in the growing data setting. Figure provides outline of our key results, where the generalization guarantees (a.k.a. transfer theorems) are shaded in blue. Due to space constraints, we present selected results here and defer proofs and technical results Appendix B.
Recall that our aim is to obtain generalization guarantees in the form of high probability bounds on worst-case distributional accuracy. Our proof technique is based on Jung et al. [15], whose bounds
5

---

for static data outperform prior work [9, 10]. The core idea of the proof involves decomposing the distributional error into two terms using the triangle inequality:
| - xPp) S |r -(2% ll(la((()))) - -((")))))))(
(1)
Rather than comparing the response r' to query 9 with the true value g(P)) directly, we instead compare r and q(Pf) with an intermediate value a( (2),, which is the expectation of the query on the posterior distribution of the snapshot at round conditioned on the final transcript и. This intermediate
value is chosen to align with the definitions of snapshot accuracy and posterior stability, which we have adapted for the growing data setting.
We obtain worst-case probabilistic bounds on each term in (I) separately: a bound on the first term follows indirectly from snapshot accuracy and bound on the second term follows directly from posterior stability. The bound we obtain for the first term is stated below.
Lemma 3.1. Suppose M is (fae), -nnapshoo accurate for [0, 1| bl-boudded queries. Then for any <> >> O, with probability 1 - _ with respect to the randomness in the datasel X ~ p and transcript II ~ ((;; M)), we have for all i E [ma, n] that max(Q.
Q(2n1) S ar +.
The proof relies on an elementary observation stated in Lemma B. of Appendix B: that the joint distribution on datasets and transcripts does not change when the entire dataset is resampled from the posterior distribution 2i in the final round n. At first glance, this observation may not seem useful, as the expectation of the query in (1) is taken with respect to the posterior distribution of the data available at round when the query was submitted 2 not the posterior distribution of the entire dataset On However it turns out this is not a problem: Since the event of interest does not depend on data points received after the round t* when the worst-case deviation from the posterior expectation occurs, we can apply Lemma B. and marginalize over the remaining data points.
Combining Lemma 3.1 with posterior stability yields our first generalization guarantee.
Theorem 3.2 (PS transfer theorem). Suppose M is an (far). -nasssht accurate mechanism for [0, 1]-bounded queries and I(- M) is an (c, -ooosterirr stable interaction. Then for every M is ( diiri distribbutui accurate for af = at + c + e and B' = + 8
When the error bounds } are constant, we recover the same bound as Jung et al. [15, Theorem 4), albeit for the more general growing data setting.
We now turn to deriving generalization guarantees using differential privacy as a measure of stability, These guarantees are derived by first converting differential privacy (DP) to posterior stability (PS) in way that exploits the structure of the query class, and then invoking Theorem 3.2. These steps are visualized in Figure 2, where the DP PS conversion results in Lemmas 3.3 and 3.5 lead to generalization guarantees in Theorems 3.4 and 3.6.
We begin with conversion result for statistical queries.
Lemma 3.3. An OD interaction I(-; M)) for statistical queries is (E,8')-PS for e' = 1 2e Σi= 8(1)/no, 8' = 1/c and any e>>
If e and c are both constant, then the scaling of the lower bound é' as a function of the final dataset size n depends on the functional form of Σi= 8()). the worst case where 8(1) is uniform, we see that e' grows linearly in In the static setting, where and we recover the result of Jung et al. [15, Lemma 7]. Combining this lemma with Theorem 3.2 yields generalization guarantee for statistical queries.
no and d()) = 6. this factor disappears
Theorem 3.4. Suppose M is an (faz), 9) snasshooo accurate mechanism and 1(:: :, M) is an (c, 8)- DP interaction for statistical queries. Then for any constants c, d 0, M is (") "distributionnllly accurate for of a + - 1 2c Et= 8(t)/no + d and 3' = 3/d 1/c.
Next we consider low-sensitivity queries, where we obtain the following DP to PS conversion result.
Lemma 3.5. An O)-D) interaction I(:; " for A A-sesiitive queries is (e', "1,58'''osteriio stable fore' = max,, E[monn] TI A - min T2 +4c (E 8(1)) max max,, Arg. 8' = =1/c and any 0.
We see that the lower bound on the posterior stability depends on the extreme values of the sensitivity and the sensitivity weighted by dataset size. It is interesting to apply this lemma to statistical queries,

---

which are subset of A -sensitivv queries with A, I 1/t. We find é' = - - 4e Ei= -1=1 8(t)/no. which is looser than Lemma 3.3 by factor of the last term. We again point out that the bound reduces to Jung et al. [15, Lemma 15] in the static case, where n. = no and 5(1) = 6. By combining this lemma with Theorem 3.2 we obtain generalization guarantee for low-sensitvvity queries.
Theorem 3.6. Suppose M is ( 3)-snapshot accurate mechanism and 1( ; MM) is an (e, 8)-DP interaction for A-sensitive queries. Then for any constants C, > 0, M is (La)), (8)) "ddistributinnally accurate for of Ot e² maxx, [[mon]] A m T2 T2am 4e (E== o(t) mäx+zE[na.n] Arg + d and B' 3/d+ 1/c.
Finally, we provide a generalization guarantee for minimization queries in Theorem A.3 of Ap- pendix A.
4
Application: Gaussian Mechanism
In this section, we instantiate our generalization guarantees for statistical queries using the Gaussian mechanism. We focus on the Gaussian mechanism since it simple to describe, is easily adapted for growing data, and it is known to be optimal for answering a small number of queries k < on a static dataset of size v [10].* 4 For ease of exposition, we assume the number of queries asked in each round is fixed before the analysis begins, while the queries themselves are adaptively chosen. This simplifies the privacy accounting and makes for more direct comparison with prior work the static setting [15]. In Appendix C.2, we remove this assumption, presenting a guarantee for the more general setting where the analyst adaptively decides how many queries to ask in each round. This guarantee relies on fully adaptive composition via privacy filter [32]. All proofs for this section can be found in Appendix C.
4.1 Generalization Guarantee
We begin by defining the Gaussian mechanism for growing data. We also include clipped variant that produces feasible estimates to [0, 1J-bounded queries (see Section 2.1).
Definition 4.1.
The Gaussian mechanism perturbs estimate query q based snapshot a by adding Gaussian noise with round-dependent standard deviation o, > 0. Specifically, we have M(g; xx) = g(x;) z with z (0, of). The clipped Gaussian mechanism composes the Gaussian mechanism with the function cl = max (), min(x, 1)) as post-processing step.
We now analyze privacy for the clipped Gaussian mechanism. The result below is obtained using zero-concentrated differential privacy (zCDP, see Definition D.3), as it provides sharp composition bounds for the Gaussian mechanism [37]. After proving that the interaction satisfies p-zCDP, we convert (e, -DP using Corollary D.9, which generalizes a result of Canonne, Kamath, and Steinke [38, Corollary 13] to non-uniform privacy parameters.
I(:i,, M) where M is the ordinary or clipped Gaussian mech- anism. Suppose the analyst decides to submit k., statistical queries in round t E [no, n]] before 1(33,, M) executed. Then M(--,,M satisfies (e, 8DD for any > 0 and d(1) < "/1"",p(( e). where p(t) = Σr=no lig 1 1002= v((,,,E) = e(7-1)(1p-e) (1 (1-73 (1-- /(r - 1) and 7* = arg min.e(1..o)) (7,, max e)t),e).
Lemma 4.2. Consider an interaction
Next we analyze snapshot accuracy. The bound depends on the inverse CDF of the Gaussian distribution, which related the inverse complementary error function erfc
Lemma 4.3. For any 3 (0, 1). the clipped Gaussian mechanism with or a is (1ar), 10)-83spsssss accurate for k queries with
Ot V2a.
erfe
2-2
) erfc -1
(3) k
2
Combining Lemmas 4.2 and 4.3 with Theorem 3.4 yields the following generalization guarantee.
'In the regime where &o > n² variant of the private multiplicative weights mechanism for growing data be used instead [25].
7

---

batches
batches
Query batches
15000
40000
Number of queriess
19000
10000
10000
7500
30000
Bound
7500
5000
Solt
2500
10000
LMRSS
LMRSS
0
0.5 1.0
0.5
1.0
1.5
1.5
1e6
Ic5
166
1e6
Final dataset size,
Figure 3: Comparison of the number of adaptive statistical queries that can be answered with error tolerance 0.1 and uniform coverage probability 1 3 0.95 using a growing dataset with growth ratio n e/ng- = 3 in batched query setting. The number of queries (vertical axis) is plotted as function of the final dataset size (horizontal axis), bound (curve style) and the number of query batches (horizontal panel). The right-most panel (b = 1), represents the static baseline setting where the analyst forgoes intermediate responses and submits all queries only after the entire dataset of size n has arrived.
Theorem 4.4. Suppose the conditions of Lemma 4.2 hold and assume o; = - > O. Then the clipped Gaussian mechanism is (a', (3')3"))di disribbutinlllll accurate for k statistical queries for any 3r (0, and = ming,B,cE6 M(o, 3, where
(
2 8(T)
2
23 Σ" 8(T)
erfe- X(o,B,e) = V20erfe-1
+e² -1+
+
+
k
33'
no
3
n1
+ ((a,8,c)
0,0 8 < 1, 2 0) and 5() is defined in Lemma 4.2.
4.2 Empirical Comparison with Alternative Guarantees
We empirically compare our generalization bounds for growing data with baselines composed from bounds for static data. When instantiating the bounds, we must specify how many queries h are submitted in each round t.5 For simplicity, we assume is queries are evenly split into b batches, with batch being submitted every T = (n n2)) /b rounds. 6 Concretely, for b > we assume k; k/b for E {no, no + T, no 2T, ... n and k = 0 otherwise. This setting represents middle ground between two extremes: where all & queries are submitted in the initial round or final round. To provide a strong baseline from prior work, we treat the b = case specially: it represents the static data setting, where the analyst waits for all data points to arrive before submitting all k queries in single batch at the final round t n.
We consider the following generalization bounds:
Ours-N. Theorem 4.4 with non-uniform privacy.
Ours-U. Theorem 4.4 with uniform privacy (expression 5(t) is replaced by max,e 5(T) in our bounds).
JLNRSS. Proposition C.4 in Appendix C.3. Composes the static bound of Jung et al. [15, Theorem 13] over query batches using fresh static dataset for each query batch, thereby yielding a worst-case guarantee over all queries. The static bound depends on parameters that are optimized under the constraints 3 8 and e d.
JLNRSS+ A tighter variant of JLNRSS that differs in two aspects: (1) the parameters are optimized without imposing the simplifying constraints mentioned above, and (2) the conversion from zCDP to (e, 6D- is based on the tighter result that we use (Corollary D.9).
Split. An analogue of the sampling splitting baseline from prior work [10, 15] adapted for growing data. It splits incoming data points into samples of size [n/k] and answers each query using fresh sample. Unlike the other methods, this method may respond with a delay if a query arrives before a fresh sample is ready. Since there no data reuse, a generalization bound follows directly from Hoeffding's s bound and the union bound (see Appendix C.4).
$ SSince bounds are worst case with respect to the analyst and data distribution, no simulation is necessary.
When division by yields remainder r, distributed evenly across the first batches/rounds.
8

---

Figure 3 plots the number of adaptive queries k that can be answered as function of the final dataset size n while guaranteeing a confidence interval around estimates of a' 0.1 with uniform coverage probability 1 - 8 = 0.95, following the empirical settings of Jung et al. [15]. When varying n. we set the initial dataset size ni = n1/3 to maintain a constant growth ratio. This choice models a practical scenario where a substantial dataset is available before adaptive analysis begins, which is necessary to obtain non- vacuous guarantees in a fully adaptive setting. To present the tightest possible guarantees for each method, we follow the approach of Jung et al. [15] and numerically optimize over the free parameters of the bounds (e.g., o, B. e for Ours-N and Ours-U) for each point plotted. Our primary goal is to compare generalization guarantees under data reuse, so the resulting privacy parameters may vary slightly between points. We note, however, that the optimal values were found to be stable in practice, varying only beyond the first significant figure (e.g.. o 0.008, 3 x 10 00-5,
0.04).
We observe quadratic growth in n for Ours-U and Ours-N, linear growth in n for Split and slower quadratic growth in for JLNRSS and JNLRSS+ In this regime, Ours-N generally outperforms the other bounds, which is not surprising as JLLRSS in particular is not optimized for growing data b >> I. We provide additional results in Appendix E examining the enror for fixed number of queries; the effect of b; and a setting where no is fixed and the growth ratio varies.
5 Related Work
Various methods have been proposed in the statisties community for adaptive analysis of static data. For instance, a-investing and related methods can be used to control false discovery rates for sequential hypothesis testing [39, 40]. Another line of work aims to ensure statistical validity when model selection and significance testing are performed on the same dataset [41-43]. However, these methods are specialized and place restrictions on the analyst [9].
Our paper builds on a body of work exploiting a connection between stable algorithms and gen- eralization for adaptive data analysis [5, 9-18]. Dwork et al. [9] were first to establish transfer theorem showing that differentially private algorithms are sufficient to guarantee high-probability bounds on the worst-case error of an adaptive analysis. In subsequent work [10, 15], simpler proofs of the transfer theorem were given that achieve sharper bounds, while covering a broader range of queries. Recent work has obtained bounds that improve data/queries [11, 14, 18] or constraining the analyst [22]. In a similar spirit, concurrent work also constrains the analyst's queries, which in turn allows them to provide guarantees for certain classes of correlated, non-i.i.d. data [24]. Lower bounds have also been studied exploiting connections to cryptography [20, 21, 44]. However, all of this prior work is limited to static data.
the worst case, by conditioning on
While there is no prior work on adaptive analysis of dynamic data, this setting has been studied in differential privacy. One line of work is known as differential privacy under continual observation [27, 28), where the goal is to repeatedly estimate a fixed function of a dataset whenever new data arrives. An elementary task in this setting is estimating the number of ones in a binary stream, which can be solved using the binary mechanism [27. 28]. More recently, alternative mechanisms have been proposed that achieve tighter error bounds [29, 30] while also maintaining computational efficiency [45]. These counting mechanisms have been used as a primitive to tackle other tasks including frequency estimation [46, 47], learning [29, 48] and graph spectrum analysis [49]. A second line of work studies differential privacy for more general kinds of adaptive queries on dynamic data [25, 26). Cummings et al. [25] design mechanisms for growing data that call black- mechanisms for static data on a schedule. Qiu and Yi [26] go beyond growing data, designing mechanisms that estimate adaptive linear queries on datasets where items may be inserted or deleted over time. Our paper provides generalization guarantees for many of these mechanisms.
Several works have obtained generalization bounds for adaptive data analysis that do not rely on differential privacy. While differential privacy yields accuracy bounds that hold with high probability, one can also study weaker bounds that hold on average via connections to information theory [10, 50, 51]. Concepts from computational learning theory, such as Rademacher complexity, have also been used to obtain data-depended dependent generalization bounds for adaptive testing [52]. However, estimating detendepend bounds on Rademacher complexity may be computationally challenging.
Connections have been made between adaptive data analysis and seemingly disparate areas. Steinke, Nasr, and Jagielski [53] develop a method for privacy auditing that runs the algorithm under audit once on single dataset rather than many times adjacent datasets. The analysis of their method

---

relies on generalization bounds for adaptive data analysis tailored for uniformly distributed binary data. Liu et [54] use static and dynamic analysis estimate the adaptivity of a program assist in bounding its generalization error.
6 Conclusion
This paper extends the current understanding of generalization in adaptive data analysis to dynamic scenarios where data arrives incrementally over time, setting increasingly relevant in many data- driven fields. Our approach builds on and extends the tightest known worst-case generalization guarantees for static data [15] by incorporating time-varying accuracy bounds and addressing the additional complexity introduced by data growth. Compared with bounds for static data, our bounds incorporate additional factor proportional to the data growth, associated with the stability of the analysis as measured by differential privacy. We instantiate our bounds for three query classes and demonstrate empirical improvement baselines for adaptive statistical queries answered with the clipped Gaussian mechanism.
There are various opportunities to extend our work. While it is conventional to assume i.i.d data when studying generalization, as we have done here, it would be interesting to consider non-i.i.d. growing data where the data distribution evolves over time. This may require bounds that depend on the rate of evolution, akin to bounds that depend on the correlation for non-i.i.d. data the static setting [23]. Another practical direction is to tighten (mostly) worst-case bounds by conditioning on the actual queries and data realized the analysis. This could be informed by similar work for the static setting [11, 14, 18). Finally, we believe there are opportunities design new differentially private mechanisms for different kinds of adaptive queries on dynamic data, as there has been limited work in this area to date [25, 26).
Acknowledgments and Disclosure of F Funding
We acknowledge support from the Australian Research Council Discovery Project DP220102269.
References
[1] John P. A. Ioannidis. "Why Most Published Research Findings Are False", In: PLOS Medicine
2.8 (2005). DOT: 10. 1371/journal. pmed. 0020124.
[2] Andrew Gelman and Eric Loken. "The Statistical Crisis in Science". In: American Scientist
102.6 (2014), pp. 460-465.
[3] Juha Reunanen. "Overfitting in making comparisons between variable selection methods". In:
J. Mach. Learn. Res. 3 (2003), pp. 1371-1382.
[4] R. Bharat Rao, Glenn Fung, and Romer Rosales. "On the Dangers of Volss-vali An Experimental Evaluation", In: Proceedings of the 2008 SIAM International Conference on Data Mining (SDM). 2008, pp. 588-596. DOI: 10. 1137 /1 97811119787877 .54.
[5] Cynthia Dwork et al. "Generalization in Adaptive Data Analysis and Holdout Reuse". In: Advances in Neural Information Processing Systems. Vol. 28. 2015.
[6] Zheguang Zhao et al. "Controlling False Discoveries During Interactive Data Exploration". In: Proceedings of the 2017 ACM International Conference Management of Data. 2017,
pp. 527-540. DOI: 10. 1145/ 1145/3035918 30359130011111 3064019.
[7] Dustin A Fife and Joseph Lee Rodgers. "Understanding the exploratory/coniimmtory data analysis continuum: Moving beyond the "replication "risis"" The American Psychologist
77 (3 2021), pp. 453-466. DOT: 10. 1037 h37/amp0000088.
[8] Bernard Koch et al. "Reduced, Reused and Recycled: The Life of Dataset in Machine Learning Research". In: Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks. Vol. 2021.
[9] Cynthia Dwork al. "Preserving Statistical Validity in Adaptive Data Analysis". In: Proceed- ings of the Forty-Seventh Anmual ACM Symposium on Theory of Computing. 2015, pp. 117_ 126. DOI: 10. 1145/ 2746529 2746580.
10

---

[10] Raef Bassily et al. "Algorithmic stability for adaptive data analysis". In: Proceedings of the Forty-Eighttl Annual ACM Symposium Theory of Computing. 2016, pp. 1046-1059, DOI:
10. 1145/2897518 2897566.
[11] Vitaly Feldman and Thomas Steinke. "Calibrating Noise Variance in Adaptive Data Anal- ysis". In: Proceedings of the 31st Conference On Learning Theory. Vol. 75. 2018, pp. 535- 544.
[12] Moshe Shenfeld and Katrina Ligett. "A Necessary and Sufficient Stability Notion for Adaptive Generalization", In: Advances in Neural Information Processing Systems. Vol. 32. 2019.
[13] Benjamin Fish, Lev Reyzin, and Benjamin I. P. Rubinstein. "Sampling Without Compromising Accuracy in Adaptive Data Analysis", In: Proceedings of the 31st International Conference on Algorithmic Learning Theory. Vol. 117. 2020, pp. 297-318.
[14] Ryan Rogers al. "Guaranteed Validity for Empirical Approaches to Adaptive Data Analysis". In: Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics. Vol. 108. 2020, pp. 2830-2840.
[15] Christopher Jung et al. "A New Analysis of Differential Privacy's Generalization Guarantees". In: / 11th Innovations T Theoretical Computer Science Conference (ITCS 2020). Vol. 151. 2020, 31:1-31:17. DOI: 10. 02.4220/112 C110//IIIcs... ITCS. 2020.00203 .3..
[16]
Itai Dinur et al. "On Differential Privacy and Adaptive Data Analysis with Bounded Space". In: Advances in Cryptology EUROCRYPT 2023. 2023, pp. 35-65. DOT: 1007 /9707799783--
031-30620-4_2.
[17] Guy Blanc. "'Subsampiing Suffices for Adaptive Data Analysis". In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 2023, pp. 999-1012, DO1: 10. 1145/ 3564246 3585226..
[18] Moshe Shenfeld and Katrina Ligett. "Generalization in the Face of Adaptivity: A Bayesian Per- spective". In: Advances in Neural Information Processing Systems. Vol. 36. 2023, pp. 52153- 52165.
[19] Cynthia Dwork al. "Calibrating Noise to Sensitivity in Private Data Analysis", " In: Theory of Cryptography. 2006, pp. 265-284.
[20]
Moritz Hardt and Jonathan Ullman. "Preventing False Discovery in Interactive Data Analysis Is Hard". In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. 2014,
pp. 454-463. DO1: 10. 101111909FFCC 2014.55.
[21] Thomas Steinke and Jonathan Ullman. "Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery". In: Proceedings of The 28th Conference on Learning Theory.
Vol. 40. 2015, pp. 1588-1628.
[22] Tijana Zinic and Moritz. Hardt. "Natural Analysts Adaptive Data Analysis". In: Proceedings of the 36th International Conference on Machine Learning. Vol. 97. 2019, pp. 7703-7711.
[23] Aryeh Kontorovich, Menachem Sadigurschi, and Uri Stemmer. "Adaptive Data Analysis with Correlated Observations" In: Proceedings of the 39th International Conference on Machine Learning. Vol. 162. 2022, pp. 11483-1 1498.
[24] Emma Rapoport, Edith Cohen, and Uri Stemmer. Tight Bounds for Answering Adaptively Chosen Concentrated Queries. 2025. arXiv: 2507. 13700 [cs. DS].
[25] Rachel Cummings et al. "Differential Privacy for Growing Databases". In: Advances in Neural Information Processing Systems. Vol. 31. 2018
[26] Yuan Qiu and Ke Yi. Differential Privacy on Dynamic Data. arXiv:2209.0139 [cs.CR]. 2022. arXiv: 2209. 01387 [Rs.
[27] Cynthia Dwork al. "Differential Privacy under Continual Observation". In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing. 2010, pp. 715-724. DOI:
10. 1145/1806689.... 1806787.
[28] T.-H. Hubert Chan, Elaine Shi, and Dawn Song. "Private and Continual Release of Statistics". In: ACM Trans. Inf. Syst. Secur: 14.3 (2011). DOI: 10. 1 /145/2443621 2043626. [29] Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. "Almost Tight Error Bounds on Differentially Private Continual Counting". In: Proceedings of the 2023 Annual ACM-SIAM Symposium Discrete Algorithmss 2023, pp. 5003-5039. DOI: 10. 1137/1 9781611977554 ch183.

---

[30] Hendrik Fichtenberger. Monika Henzinger, and Jalaj Upadhyay. "Constant Matters: Fine- grained Error Bound on Differentially Private Continual Observation". In: Proceedings of the 40th International Conference on Machine Learning. Vol. 202. 2023, pp. 10072-10092.
[31] Zach Jorgensen, Ting Yu, and Graham Cormode. "Conservative or liberal? Personalized differential privacy". privaccy In: 2015 IEEE s1 International Conference on Data Engineering- 2015,
Pp. 1023-1034 DOI: 10. 1109/ICDE 2015. 7113353.
[32] Justin Whitchouse et al. "Fully-Adattive Composition in Differential Privacy". In: Proceedings of the 40th International Conference on Machine Learning. Vol. 202. 2023, pp. 36990-37007.
[33] Shengyuan Hu et al. Privacy Amplification for the Gaussian Mechanism via Bounded Support. 2024, arvi:: 2403. 05598 [cs.
[34] Hamid Ebadi, David Sands, and Gerardo Schneider. "Differential Privacy: Now it's Getting Per- sonal". In: Proceedings of the 42nd Annual ACM SIGPLAN-SIGAG Symposium on Principles of Programming Languages. 2015, pp. 69-81. DOI: 10. 01114////76766.. 2677005.
[35] Uri Stemmer. Private Trela-Everlasting Robust-Prediction. 2024. arXiv: 2401 04311
[cs. LG].
[36] Vitaly Feldman and Tijana Zmic. "Individual Privacy Accounting via a Rényi Filter". In: Advances in Neural Information Processing Systems. Vol. 34. 2021, pp. 28090-28091.
[37] Mark Bun and Thomas Steinke. "Concentrated Differential Privacy: Simplifications, Exten- sions, and Lower Bounds". . In: Theory of Cryptography. 2016, pp. 635-658.
[38] Clément I. Canonne, Gautam Kamath, and Thomas Steinke. "The Discrete Gaussian for Differential Privacy". In: Advances in Neural Information Processing Systems. Vol. 33. 2020, pp. 15676-15688.
[39] Dean P. Foster and Robert A. Stine. "a-IIvveting: Procedure for Sequential Control of Expected False Discoveries". In: Journal of the Royal Statistical Society Series B: Statistical Methodology 70.2 (2008), pp. 429-444. DOI: 10. 1111/j 1467-9868 20000000003.....
[40] Adel Javanmard and Andrea Montanari. "Online Rules for Control of False Discovery Rate and False Discovery Exceedance". In: The Annals of Statistics 46.2 (2018), pp. 526-554.
[41] Yoav Benjamini. "Simultancous and selective inference: Current successes and future chal- lenges". In: Biometrical Journal 52.6 (2010), pp. 708-721, DOT: 10. 1002/bimj 200900299. [42] Jonathan Taylor and Robert J. Tibshirani. "Statistical learning and selective inference". In: Proceedings of the National Academy of Sciences 12225 (2015), pp. 7629-7634. DOE: 10. 1073/pnas. 1507583112.
[43] William Fithian, Dennis Sun, and Jonathan Taylor. Optimal Inference After Model Selection. 2017. arXiv: 1410. 2597 [math.ST]
[44] Kobbi Nissim, Uri Stemmer, and Eliad Tsfadia. "Adaptive Data Analysis in a Balanced Adversarial Model", In: Advances in Neural Information Processing Systems. Vol. 36. 2023, pp. 25748-25760.
[45] Joel Daniel Andersson and Rasmus Pagh. "A Smooth Binary Mechanism for Efficient Private Continual Observation". In: Advances in Neural Information Processing Systems. Vol. 36. 2023, pp. 49133-49145.
[46] Adrian Rivera Cardoso and Ryan Rogers. "Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknown".. In: Proceedings of The 25th Interna- tional Conference Artificial Intelligence and Statisties. Vol. 151. 2022, pp. 2397-2419.
[47] Jalaj Upadhyay. "Sublinear Space Private Algorithms Under the Sliding Window Model". In: Proceedings of the 36th International Conference Machine Learning. Vol. 97. 2019, pp. 6363 6372.
[48] Sergey Denisov et al. "Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams". In: Advances in Neural Information Processing Systems. Vol. 35. 2022, pp. 5910-5924.
[49] Jalaj Upadhyay, Sarvagya Upadhyay, and Raman Arora. "Differentially Private Analysis on Graph Streams". In: Proceedings of The 24th International Conference on Artificial Intelligence and Statistics. Vol. 130. 2021, pp. 1171-
[50] Daniel Russo and James Zou. "Controlling Bias in Adaptive Data Analysis Using Information Theory". In: Proceedings of the 19th International Conference on Artificial Intelligence and Statistics. Vol. 51. 2016, pp. 1232-1240.
12

---

[51] Thomas Steinke and Lydia Zakynthinou. "Reasoning About Generalization via Conditional Mutual Information". In: Proceedings of 33rd Conference on Learning Theory. Vol. 125. 2020, pp. 3437-3452.
[52] Lorenzo De Stefani and Eli Upfal. "A Rademacher Complexity Based Method for Controlling Power and Confidence Level in Adaptive Statistical Analysis". In: 2019 IEEE International Conference on Data Science and Advanced Analytics. 2019, pp. 71-80. DOI: 10. 1119//DAAA.
2019. 00021..
[53] Thomas Steinke, Milad Nasr, and Matthew Jagielski. "Privacy Auditing with One (1) Training Run". In: Advances in Neural Information Processing Systems. Vol. 36. 2023, pp. 49268- 49280.
[54] Jiawen Liu al. "Program Analysis for Adaptive Data Analysis". In: Proc. ACM Program. Lang. 8,PLDI (2024). DOr: 10. 1145/3656411
[55] Thomas Steinke. Composition of Differential Privacy & Privucy Amplification by Subsampling.
2022. arXiv: 2210. 00597 CC..
[56] Cynthia Dwork and Aaron Roth. "The Algorithmic Foundations of Differential Privacy". In:
Found. Trends Theor. Comput. Sci. 9.3-4 (2014), pp. 211-407. DOr: 10. 10.16//00000000442
A Results for Minimization Queries
In this appendix, provide generalization guarantee for the class of low-sensitivity minimization queries. Queries in this class are parameterized by a loss function L: X' x è -> [0. 1]. where the first argument is data snapshot and the second argument is set of parameters from parameter space O. We require that L is A Assesiitvee in its first argument, meaning for all E [n|]] and all E θ have [[(=14 0) [. 0)] I A, for any pair of neighboring snapshots =[t]] oteej E X When evaluated on a snapshot, the result of the query is q( E arg mingge Laz14 0). When evaluated on a data distribution D, the result (D) E arg mingee ExxdIL(X,0))
The definitions of distributional and snapshot accuracy that appear in Section 2.3 must be adapted for minimization queries. Minimization queries require different treatment because the output of the query is not scalar-valuee valued in general, but rather a set of parameters 0 E O. We use the loss function L associated with the query to measure the distributional and snapshot accuracy defined below.
Definition A.1. Let at 0 for all rounds t [mo, n] and 3 2 0. A mechanism M is (fa,), B)- distributionally accurate if for all analysts A and data distributions P
-min E [L(X, 2 oa)) S 3. dee X~pp
P
E [XXX X
X- X-P" X.MM
1= (I,9)em,
Definition A.2. Let a 2 for all rounds t E [mn, n] and 3 2 0. mechanism M is (far), B)- snapshot accurate if for all analysts A and data distributions P
Ü
(1(X10.0) min L L(X 0) dEe
2 201 ca)) S
P X-PMII-I(XAM.
U
(tngg (L,0)TTT
Following prior work [10, 15), we obtain generalization guarantee for A-sensitive minimization queries by applying Theorem 3.6 to a related set of 2 -sensitive scalar-valued queries.
Theorem A.3. Suppose M is an (Hax),8)-snaye -3)-saashoo accurate mechanism and 1(,;,,M) M) is
(c. DDP interaction for --sessitive minimization queries. Then any constants c, d > 0, M is
(fa4), (8") J-distributionally accurate for a, a: +e++22 2e max,, [[na.]] Ar - min A Arg + and 3' = B/d 1/c.
8c Σm 8(1) maxx3e[no.n]
Proof. We begin by defining a mapping f 2min θ + Qis x [0, 1] that takes a A-sensitive minimization query-estimate pair (I, W) E Qmin x θ and returns a 24 -A-sensitive scalar-valued query-estimate pair (q.r) E Qs x [0, 1]:
f(L, W) (q,r) with q(x) L(x, W)
min L(x, W) and r r= 0. w'ee
13

---

Since f does not depend on the dataset, we can apply it to all pairs in the minimization query transcript II to yield a transformed transcript II' that also satisfies (c. 6DD by the post-processing guarantee (Theorem D.6). It is straightforward to see that the transformed transcript IT' is ((or): (()x)),))ssapppp snapshot accurate iff the original transcript is.
Next, observe that the probability of interest can be upper-bounder using Jensen's 'sseen' incquality to swap the order of the minimization and expectation operations:
(Ü
U
{
X'mpp [L(X',
W)] - min E
[LXX W')] > of
X X- (eming (L,W)EIl,
wh x'rpi
n U
L(X', w7) > oz
$ P CwPPIIMM( (mmg (L,W)EII,
L(X'
min W'EB
X'ape
U
n UUS
U
E X'
lx(x')
> of }
X~PP (xx((
(=no (q-7)En;
In the last line above, we have rewritten the event in terms of the transformed transcript II'. Applying Theorem 3.6 upper bounds this probability by B", completing the proof.
B Proofs for Section 3
Lemma B.1 (Resampling Lemma [15]). Lef C X x T be any event. Then P
(IX,II= E E) X~P", IMP" ((X' E).
Proof. The result follows by writing the probabilities as expectations, invoking the definition of Qn. and using the fact that x and x' can be swapped without changing the expectation:
IP X X~pp 1x) (XX', II) E)
Σ P(X x,
II π.)
P (X' X'm2r
x' a²)1 ((x)
x) x' II= π
1 ((rt,
n,
Σ P(X = x, II [(.T))
2,,
X~PxX (X)I))E))
Lemma 3.1. Suppose M is ((ov), -n-snshsoot accurate for [0, bJ-bounded queries. Then for any 0. with probability 1 - with respect the randommess in the dataset X p and transcript 11 A(X;A,M) M), we have for all t E [no, n] that max, |R Q( S 0: +
Proof. Given a transcript π E T, let round--uery-esstmaate tuple that achieves the largest or adjuustd posterior error be denoted
".9" E
arg max Ir q( ( at. (QT)))
where we have omitted the dependence on æ. We use this definition to write the probability of interest in terms of single event, which we then express as union of two independent (since or-- + c >> 0) events corresponding to the branches of the absolute value function:
Ü
P XxI(I
U
(rr --ggg((ftt) > as +c}
(=no (g.r)ETT.
[r" 1r"-9"(O(") - ar. > c)
P xxIxx,I<(())
(r' (-"99(0f) > >c) +
Xupa xxxmx1n(xx) P (0'(2 -r" -ar (er>))..2 .22
P
14

---

Observe that the first term in (2) can be bounded as follows:
P
(1"
9"
Cx. >c)
X~P",,In
P
E
r" q- (X(x..) -ace) -0
(3)
X~pm,Il-(X*
$
P
E
maxfr* 9¹ (x((( ar ar. 03] >c
X-Px.II~((X)
1
maxfr* 9¹ (X(1)) -op,, ap, 07]
$
E
E
(4)
(X-PH,TTI(X
X
1
gx* (1-1) ox > 00]
<
E
P
(5)
XImR1I
1
(r' -x -ox- 0)
P
P c CX-PXIIIXX)
(r' (X at. >0)
(6)
where line (3) follows from the definition of ut (i:); line (4) follows from Markov's inequality; line (5) follows from the fact that r g [q) a I 1 for a [0, 1]-bounded query and mechanism;
and line (6) follows from Lemma B.1. By symmetry, a similar bound holds for the second term in (2).
Substituting these bounds in (2) gives
P x--(x,I~1(()
Ü
U
(|r ((2)) or +c
(1 (g.r)elI,
1
P c X Nx IIvl(X)
(Ir* - (' - ar. 00)
(7)
Ü U {r - q(X11)) > at)
P
(8)
c xxpp Sapp IIwI(()
(tn (a.)eel,
8
e'
where line (7) follows from the independence of the events in the two terms; line (8) follows since the starred round-query-estimatt tuple may not achieve the largest addausste snapshot error; and line (9) follows from the definition of
accuracy.
Theorem 3.2 (PS transfer theorem), Suppose M is an (far). -nsspshhhot accurate mechanism for [o, bl-bounded queries and I(:; M) is (c, -pposterior stable interaction. Then for every M is (La(), ('od)))""'disiibbuuue "distributionnlll accurate for of 04 + and B' e 8.
Proof. Given transcript T, let round-query estimate quetr-estmatee tuple that achieves the largest ar adjasstee distributional error be denoted
t", " E arg max
|r- -P-)(' Citz
where we have omitted the dependence on æ. Using this definition, we express the probability of interest in terms of single event, and then obtain upper bound using the triangle inequality and
15

---

the union bound:
U
12
(or fr- q(P') > ar +ctee)
X~pm,Ilw(x)
(1=ng (q.7)Ell.
P
- ("(p())) ) ar. cc+c
[1-
X~Pm XxP(,IIm((() [Ill(()
(r* -7--(i(1i)1 ar + +100 - (p" -P
X~Pm X~~p..I~-(()
(I"' (r*=0(( ar >c)
Xapa [I)
K.PPIIII- (10((
- n² (p (P()))>()
(10)
We can upper bound the two probabilities in (10) by maximizing the L.HS of the inequalities with
respect to 1", "'"""" E Un=no ((, (q.r) IT,) Then Lemma 3.1 upper bounds the first
probability by & and Definition 2.3 bounds the second probability by giving the required result. C
Lemma 3.3. An () interaction I(-; M) for statistical queries is (' for e'
+ 2c Di= 8(1)/no. 8' = a/d and any c >
Proof. Given a transcript π E T, let the round-query-estimate tuple that achieves the largest absolute difference be denoted
c" 0,
arg max 1 (o..).).....))..
le(2%) ((P)))
where we have omitted the dependence on n.
Define for any > 0, E X, / E [m], = E [0, 1/mo):
II))) TTT:: (2 1²t (Pt') > >>)>
(*) TEX:
P
(X, 2 P (X =m]
Xap
B (*(a)= U (x* (m)),
(El((a)
IT ( E T x) E B+)))
II (a,
n E II (a,x) :f t5 15 1,,1
Fix any a > 0 and let J = Σt= 5(t). Suppose Px- (2ft) - 1" (pp)))
2. which implies either Px~p= _~((() (1"(2))) x' (pC') a)
or
Px~P=.n-x(X) (a" (P'") 9" (2fi) > a) 2. Without loss of generality assume
P X-P-IIIXXX
(1 - q" (P) > a) = P I(a))) >
1
(11)
2c
From the definition of [a),, we have
P E ((a)) <
Σ
-
9¹ (P'i)}
rEll(a)
Σ
E X'
(x
x 35 la (X
*EI((a)
Σ
{
E Xxwon tullte
l0" (x(())))
E 10 (X)1)
(12)
x
rell(a)
16

---

where we have used linearity of statistical queries in the last line. Expanding out the difference of expectations, we have
E
(x()
X-p l
E
X M
1'
Σ
(x))
P(X: = x -I= P(X =x)
ZEN
t=1
1
p( z == P(X 2)
(13)
aEX (T)
P(X x) Pill= T)
P(II = X = x) PIII= x)
(14)
ZEN (T)
where (13) follows by dropping negative terms from the sum and using the boundedness of statistical queries, and (14) follows from Bayes' theorem. Putting (14) in (12) and swapping the order of the sums gives a P(T (o))
Σ Σ TEll(a) xEX (T)
P(X = r)
P(T = x x x) - PP = =m) m
1
P(X = x)
Σ
perr (P[[I]= = X x) P(T = m)}
DEA
TEll (a,a)
P(X x)
Σ
1 [| dz | [PIII= = ग. X x) - -(1 m)
1=1 TEN
(a.x)
P(X = x)
(P(LI II (a, X =x) - P(I e II 2,,)), de
T
/ n0
P(X- = x²
1Ie'- II
II (a, 2,,,,,2,)) 2, 2)) 8(t) dz
(15)
1=1 TEN
Σ SEX
P(X 1)) { (65- II (a, x)) x)) + no
5
(e: 11) I(a)) +
no
2cd
<
e 1+
P(I E (()))
(16)
no
where (15) follows from Lemma B.2, and (16) follows from (11). This is contradiction for e 1 205/ /no-
stable Lemma 3.5. An (DP interaction i M) for A sensitive queries is (e,88)-posterion stable fore' = max; A -min T2 +4c Ac (E 8(1)) max Any 8' 1/c
and any > 0.
Proof. Given a transcript π E T, let a round-query-result tuple that achieves the largest absolute difference be denoted
lq(E() - q(P')),
arg max me]mo.n).(grr)en.
where the dependence is omitted.
17

---

Let # denote the concatenation operator, such that for any pair of sequences and of length and m respectively, we have z y (f1,...,,Fx y1, ................................ .. Let A maxig[no.n] A, and = Σi= 0(t). For any 2 0. J. E [n]. X" and 2 E 22,), define ", =
X pm [x(
E
[I) =
9² (P") > >>
[[, 2, x14) = [ IIaa)) lege (u(q", tt, x11n)) v(q" t", -1j- + A..) > =}.
Using the definition of differential privacy, observe that
Σ
F(UI = x= = =xxx 1pse (u(g", 1", x1u v(q": ,t, xqi-11) + A,:)
TE))(O)
Σ P(I x X x) / 24
1 (1
dz
(EIT())
P(I E (1,,2 | X = x) dz
24
(e [(, mng) X rep(2,, 2,))) 5(1) de
Σ (Ell(a)
=(I= X (ep(,,,, ( (v(a" 1", mpee - v(q"; , (((-111)) + A..)
+
(17)
where rep(ær, 1, x') denotes the dataset obtained from æ by replacing the 1-th data point with x' E X. Taking the expectation of inequality (17) with respect to p and X' ~ P, and summing over t [n]] we have
Σ
P(II = K X)1 (u(q", x11) ulq", ,t", X + Ar.))
X
[TEl((a)
E X Pu Xap
P(II= = π X)
nEll(a)
[[see (v(g* , rep((x, u6q" (00, 2(, + Ao.) 24+8
(18)
n
Σ
P(I= K x) +0)
(19)
(E)
Se
max 1 n]]
A, P(I E ((a)) + 2
(20)
where (18) follows since (X,X') and (rep(X, X'), Xx)) have the same distribution, and (19)
follows since X' is independent of II and Ex~p [x(g" t", rep(X. x))] = v(g", , X X (
Subtracting ExeN(()) t² from both sides of inequality (20), we have
E X Xmp
Σ (ell(a)
P(I1= n X)1 (v(g", "o(a""t",,0 ((1) - v(g", tt, X(e-))))
1=1
<( c max
A,
min A P(II E I(()) (())) [E[ng.n]
+ 2
IE [ng.n]
Now fix a = e "mxx tA minre[mo.nt t'Ar + 4cn maxe"e Arr.
Suppose
P((g'(OHi (Of 9" (p""' a) > 1. Then it must be that either PPg' (Ofi) g" (pt') > >a)
1 or
ze
18

---

- -""pp""")-"(ffff") > a) 20.
1.
Without loss of generality, assume
P(q"(2)) 9- (pr)) > a) = P(LL II)))) >
2c
But this leads to contradiction since
P E Iaa))
Σ P(I = π) -
xell(a)
Σ (E))(a))
P(IT= = x) gg )
=
Σ (EII(a)
P(II= क X) (u(g", 1", X14) - v(a", 1", X(c-11))
[=1
$ E max
min eEE
de P(Ll II(a)) + 2
(e"
s P(I E I[))
min [E[no.]] d'Enn.n]
max th
t + 4c1
Lemma B.2 (Lemma 21, [15]). If((:; any index E [n]] and value x E X:
M) is (e, -)differrettially private, for any event E E T,
P X~pP I>I[repXX... xt,)))
[II E] S e
P
11 E] 6(t)
X-PP III
where rep(X, t, 2) is the dataset obtained from X by replacing the t-th data point with æ.
Proof. This follows from expanding the definitions
P X~PP J.PP*.InlleepX..... (.)))
[1 E = Σ
P X
x=
11 E)
[=I((ep(ae,t..1))
X
x
e-
P
I E + 5(t)
(21)
X~pm
II~1(x))
=e
P (()
IT E F.] 5())
where (21) follows from the definition of differential privacy.
C Proofs for Section
C.1 Generalization Guarantees Assuming Fixed Privacy Parameters
Lemma 4.2. Consider an interaction I(::.M) where M is the ordinary or clipped Gaussian mech- anism. Suppose the analyst decides to submit k statistical queries in round T [ng, n] before
(c;..)) is executed. Then I(::,,M M) satisfies (c, DDD for any >> 0 and ö(t) < "61",, ,(t), c),
where p(t) = Ex= h / 1p(1.p.C) e(7-1)(1p-e) (1 -1) /r 1) and
7* aarg min,e(1,00) (5(7, maxre]n] e))
Proof. We begin by bounding the privacy of the interaction using zero-concentrated differential privacy (zCDP), defined in Definition D.3. When releasing an estimate single statistical query in round the Gaussian mechanism satisfies p-zCDP with p(t) = Aiss:/2o? where we have used 1/72 as upper bound the sensitivity of the query [37, Proposition 1.6]. By procpsoccssing (see Theorem D.5), clipping the output of the Gaussian mechanism does not acerue an additional privacy loss, nor does the analyst's choice of the next query conditioned the previous
19

---

releases. Now by advanced composition (see Theorem D.4), the interaction satisfies p-zCDP with p(t) = = k=] We note that in order to apply this theorem, we have relied on the fact that the privacy parameters are non-adaptive, which is true when the ky 's are fixed in advance. Finally we convert from p-xCDP to (c, 6)- using Corollary D.9.
priva
Lemma 4.3. For any B (0, 1). the clipped Gaussian mechanism with or ar is (far), ((aa))B)-ssaaee -S-napshot accurate for k queries with
0t 22,
erfe -1
2 2 1 3 ) < erfe -1
(1
Proof. Let Kt denote the number of queries asked in round t. Let j E {l.... .......k. ke} index the queries asked in round f and Zz,; iid Normal(O, oz) denote the Gaussian noise added by the mechanism to the j-th query in round t. We begin with the observation that
P max max (-Zr, - ar) 2 20) = - P max max (-Zis as) < 0)
ne je[k]
Me[no.n] je[k]
II t=mp
II
P(Zz.j 2 -0r)
II
1
erfc
0t
2
V201
t= J=1
))²
Otz
=
erfe
v20+1
(22)
where the last equality follows from the fact that c is constant with respect to t. By symmetry, this equality also holds under the replacement Zr,j Zt.j-
Conditioning on the number of queries k asked each round t, we have with respect the joint distribution on the dataset X and transcript IT that
{la(X1q)) -| ar) n (1T kz))
P
(g.r)EmT
{19.5( (X (1)) (9.5 + Ze,)] - -a13 0)
P
max
max
jE[(,]
P
max
max
{|Zr,| - a,) 2 20)
[E[no.n] jE[k,
P
max
max (-Ze.- - a+ 2 20 +
max max [Zr,j - -ar 2 20)
ME me
jE[{,]
(rE[o.n jE[k,]
1 11-
1 erfe
at
2
(23)
V20
where the last line follows from (22). Note that the bound only depends on the total number of queries k. not the number of queries asked at each time step ke. thus it serves as a bound on the probability
conditioned on the event) Ei [II, = k. The result follows by setting (23) equal to and solving for az/ /2,
Theorem 4.4. Suppose the conditions of Lemma 4.2 hold and assume at - > O. Then the clipped Gaussian mechanism (a', (8') distriibbuti accurate for k statistical queries for any 3 (0,1) 1)
and a' = ming,B,ese N(o, 3, E), where
( B
B 2
2 3
23
T== 8(T))
erfe- -1 Xa, B,c V2o -rfeerf-
-
+e- -1
K
3
ng
θ = ((0,8,e E 3 :0> 0,0 8 < 1, 0} and 8(-) is defined in Lemma 4.2.
20

---

Proof. Combining Lemmas 4.2 and 4.3 and Theorem 3,4 implies the clipped Gaussian mechanism is (a', diittributionnaly ( accurate for 3' =3/d 1/c and
- -1 2c -=== 8(T)
a' = 2a erfe
no
for any d > 0 and 0 < 3 < 1. We select the free parameters to minimize a'. Eliminating e using
the constraint 3 8/d + 1/c and minimizing with respect d analytically gives:
a' 2a erfe -1 (3) k
(
2 2 8(T) + - -1+
3 8
28
G 8(T)
+
nop3"
8
Minimizing this expression with respect the remaining free parameters gives the required result.
C.2 Generalization Guarantees Assuming Adaptive Privacy Parameters
In this appendix, we instantiate generalization guarantees for the clipped Gaussian mechanism where allow the analyst adaptively select how many queries to ask in each round. This is in contrast with the results of Section 4.1, where we assume the numher of queries asked in each round fixed before interacting with the data. To support fully adaptive analyst, we rely which provides differential privacy guarantees when both the mechanisms and privacy parameters are selected adaptively. Generally speaking, privacy filter is an algorithm that continually monitors the privacy parameters of mechanisms as they are composed. At any point, can force the composition terminate to ensure it satisfies pre-specified level of privacy.
privacy filter,
We use a privacy filter proposed by Whitehouse et al. [32] for approximate cero-concentrated differential privacy (zCDP). It achieves the rates advanced composition [37] assuming the privacy level is specified upfront. The filter does not support non-uniform privacy accounting- -hhne the privacy loss is estimated separately for each data point /individual. We therefore resort to uniform accounting, which results in looser generalization bounds. We expect the filter could be adapted to support non-uniform privacy accounting, in similar way to the Rényi filter proposed by Feldman and Zmic [36].
To incorporate Whitehouse et al. 's privacy filter for adaptive analysis using the clipped Gaussian mechanism, we require additional monitoring as shown Algorithm 2. Lines and 4 track the running privacy level f using the same additive rule advanced composition for zCDP. If releasing response to a query would not exceed the target privacy level (line 5), then a response to the query is released (line 7) and the analysis continues, otherwise the mechanism is terminated (line 9).
Algorithm 2 Composition of Clipped Gaussian Mechanisms with zCDP Privacy Filter Input: target privacy level p
1: # ++0
2: for Round t [no, rl] do
3: while Analyst has another query g do
4:
/ p+ 20702²
5:
i S p then
6:
Sample noise: ~ N00
7:
Return response to query: r +- (0(()))((( + +2)
8:
else
9:
TERMINATE
10:
end
11: end while
12:
end for
Lemma C.1. Consider interaction 1(;-,M) M) where M is composition of clipped Gaussian mechanisms tracked by a privacy filter that satisfies p-zCDP, as described in Algorithm 2. Then the interaction satisfies p-zCDP, with the possibility that it may terminate early, It also satisfies (e. 6DP for any 2 0 with 8 < inf -1--)---- -1-
)) ( 11
1).
21

---

Proof. We recall that the Gaussian mechanism satisfies ( for a statistical query with sensitivity Á S 1/t [37, Proposition 1.6]. By post- prot-psocsssing for zCDP, clipping the result of the Gaussian mechanism and selecting query as a function of the result (and past results) does not acerue an additional cost to privacy. Hence, by fully adaptive composition for the zCDP privacy filter [32, Theorem 1I, the interaction satisfies p-zCDP. Finally, we convert from p-ZCDP to (c, 6)-DP to obtain the final result [38, Corollary 13].
Combining Lemma C.I with Lemma 4.3 and Theorem 3.4 yields the following generalization guarantee. We note that this essentially matches the guarantee for the more constrained setting where the number of queries in each round is fixed upfront (Theorem 4.4).
Theorem C.2. Consider an interaction Mi: M) where M is composition of clipped Gaussian mechanisms tracked by a zCDP privacy filter that satisfies (e, 8--D. Suppose M answers statistical queries without terminating and assume o = 0. Then M is "od..""ddsstiibtiionn accurate for k statistical queries with
22 @rferfe" (a.8.0)E0
min
(B
+
11
2nd no
3
2
23nd
31
no
where @ defined in Theorem 4.4 and 8 is defined in Lemma C.I.
Proof.
The proof is similar to the proof of Theorem 4.4.
C,3 Generalization Guarantees using the Static Bound of Jung al. [15]
In this appendix, we derive a generalization guarantee for the setting considered in Section 4.2 by composing a bound for static data due to Jung et al. [15]. In doing so, we will obtain the bound that is labeled JLNRSS in the empirical results of Section 4.2. For completeness, we begin by restating Jung al.'s result below, with some minor changes in notation. In particular, we make the dependence of the bound on the dataset size n and number of queries & explicit, since we will apply the bound to multiple batches, each with a different value of n and k.
Theorem C.3. Consider ADA on static dataset of size n-iee, an instantiation of Algorithm with Nu = - 1. The clipped Gaussian mechanism can be used to answer k statistical queries while satisfying (a(n, k B), B) distribution accuracy for any (0, 1) with
knn,k, min
V20 erfe
-1
(())
+ exp
k
+
2k log n²o²
V VZnoō )
1 + 6 8 3
0,820
2n
We note that improved bound can be obtained by (1) not constraining 3' = and d in the proof and (2) using a tighter conversion from zCDP to approximate DP based on Canonne, Kamath, and Steinke [38] in place of Bun and Steinke [37]. This improved bound is used in the approach labeled JLNRSS+ in Section 4.2.
We now turn to the batched setting described in Section 4.2. Recall that the data arrives in b batches, which we index by E [b]. We let n, denote the size the f-th data batch, and ki denote the number of queries asked by the analyst after the batch arrives. Since the b-th data batch is static while the analyst asks the k queries, we can bound the worst-case distributional accuracy for the entire analysis by applying static bound on each batch, and taking the union bound.
Proposition C.4. Consider ADA growing data in the batched setting. The clipped Gaussian mech- anism can be used to answer statistical queries while satisfying (a', ddistribbutii accuracy for any 8 E (0, 1) with a' maxtepo] (x(r ke, B² /b), where a(-,..-) is as defined in Theorem C.3.
Proof. Let X ~ P and II ~ I(X;A, A, It is convenient to refer to the queries and responses in the transcript using two indices: the batch E [b] when the query was asked and the number j E [ky] of the query within batch f. Adopting these indices, we say that the clipped Gaussian mechanism (a', (8') distribbbuui accurate if with probability
3' over the randomness in X and IT, we have that max max [Re,j (P a' for any data distribution P and analyst A.
22

---

Now we obtain an upper bound on the probability of interest by replacing the error a' with lower bound for each batch e, and finally applying the union bound:
max max [ JEle]
Qe,((P"s)
max ang dap
e'El
P X~/P",IIMlp [[v(())
max [E[D]
max Re. QP JE[Rel
max Onerr Kep E'El
20
P
max RE[M]
max Rr.j Qt.(PnM)) anee.te 20 jE[Rel
X~>P,,I~1((7)
Re, Qe,((Tm)) anecee })
P XIx(x
max jElke
S ((B.
C.4
Generalization Guarantees for Data Splitting
Data splitting is simple method for mitigating the risk of overfitting when conducting an adaptive analysis. It involves randomly splitting i.i.d. dataset into disjoint chunks, and using a fresh chunk whenever a step the analysis depends on existing data. Data splitting has been used as a baseline in prior work for static data [10, 14, 15] and can be adapted for growing data by splitting the data into chunks as data points arrive. There a limitation in the growing setting: may be necessary to delay step in the analysis if sufficient data has not yet arrived to create fresh chunk of the desired size. This is not a limitation of our approach (Algorithm 1) which can respond to queries without delay at any time. For completeness, we provide high probability worst-case generalization bound for data splitting below.
Proposition C.5. Data splitting is (a, -yddistributionnalyy accurate when used to answer k adaptive statistical queries for any a, B 2 such that Σ₁ 22bp02 é, where n, the (predetermined) size of the split used to answer the j-th query. In particular, if dataset of size split evenly across the k queries so that n2- = n/kk E N then n = 20 log 2h
B
Proof. We write (gjrry) to refer to the j-th query-estimate pair in the flattened transcript. We also define m, E3= Ny to be the number of data points used by the mechanism prior to answering the j-th query. By the union bound and Hoeffding' bound have
A (URlr-- - 20]
P X~pr XII(x)) I1,((X)
(P)))201)
4-l
m, +n,
Σ (X()))
E 1x]1 20)
=
P XIPxxIIN((X)
Tly l=m;
xmp
1 my
(xi(X))
F [ 20
X Pn X>Px,Inw(())
nJ r=my
/=1
2e 22
Ø=1
D Results for Non-uniform Privacy Parameters
In this appendix, we prove key results for differential privacy with non-uniform privacy parameters. Although many of the results are identical to the uniform case, we were unable to find proofs in
23

---

the literature. We begin by extending the definitions of approximate differential privacy (approx. DP) and ceno-concettrated differential privacy (zCDP) to the non-uniform setting. Then we prove composition and post-processing for these definitions in Appendix D.1, and a conversion theorem from zCDP to approx. DP in Appendix D.2.
Informally, differential privacy (DP) is bound on how distinguishable the outputs of a randomized algorithm will be when run on two neighboring datasets. Ordinarily, the bound on distinguishability holds uniformly over all neighboring datasets, which means the level of privacy is the same for all records in the dataset. However, in some scenarios it may be tolerable for the privacy guarantee to vary non-uniformly over records e.g. where individuals have different privacy preferences, or where privacy is permitted to decay as records age. Non-uniform privacy definitions have been studied using pure DP as foundation, which is known as personalized DP [31, 34], Below, we extend this idea to approximate DP, by upgrading the parameter from constant to function (-) that varies for each record index.
Definition D.1 (Approximate DP). Let 2 0 and 6: [n] - [0, 1]. A randomized mechanism M: X -> Y satisfies (c, dddifferrent privacy or (c, 6)-DP for short, if for all indices E [n]. all pairs of neighboring datasets (æ,, x²) E EM differing on the i-th entry, and all measurable events E _ y:
P(M(z) E) S e P(M(2)) E E) + 5(1).
Note that this definition depends on N₁. the set of neighboring datasets that differ on the i-th record. One could consider unbounded neighboring datasets, in which case N₁ would consist of pairs of datasets (ar, x²) such that x' can be obtained from xr by adding or removing the i-th record. Alternatively, one could consider bounded neighboring datasets, where the pairs of datasets (ær, x') in N₁ are such that x' can be obtained from x by changing the i-th record.
Next, we define non-uniform variant of zero-concentrated differential privacy (zCDP). However, we must first define the privacy loss distribution, since is used to measure indistinguishabiliy for zCDP.
Definition D.2 (Privacy loss distribution). Let P and Q be probability distributions on y Define spIQ: y RR such that (v) = (Pg) (w))) The privacy loss random variable is given by Z = fril (Y) for Y <- P. The distribution of Z is denoted by PP)I).
The standard definition of zCDP bounds the moment generating function of the privacy loss random variable 2 PrivLoss (=>))](((²)) uniformly over pairs of neighboring datasets, in terms of scalar, [37]. We upgrade the scalar to a function p(-) that varies for each record index.
Definition D.3 (Zero-concentrated DP). Let p: [n] - [0, oo). A randomized mechanism M: X -
y satisfies p-zero- ezzeeecconcettrated differential privacy or p-zCDP for short, if for all indices i E [[]] and all pairs of neighboring datasets (x, xx) E N₁ that differ on the i-th entry, the privacy loss distribution PrivLoss ((z) M(z') )) well-defined and
VT 2 0, Z (M)
E
(exp(rZ)) S exp(r(r+
D.1 Composition and post- post-processing
We need a composition theorem for p-zCDP analyze the privacy of successive applications of the clipped Gaussian mechanism in Lemma 4.2. We show that p-zCDP composes in the obvious way: by adding the P privacy parameters pointwise.
Theorem D.4 (Composition for p-zCDP). Let randomized mechanism Mj : X + V1 satisfy
PDPP Let M2 : X x Vi- + 3)2 be such that, for all E )1, the restriction M2(x.)= Xx + ye2
satisfies P2-tCDP. Define M X + V1 x V22 such that Yı + (z))). Y2 Yı & M2(x, Yi) and
M(x) = (Y1, Y2). Then M satisfies PDPCDP with p(1) = (i) + (i( for all i E [[].
Proof. We adapt the proof of Steinke [55]. Fix [r]]]] and neighboring datasets x') M; that differ on the i-th entry. Fix T 2 O. Let Z t PrivLoss(MEC (M(x) M(()))(())) where we conceal the dependence on We must prove E ((ex((TZ) = exp(T(T + 1) (i) + (2))))
For simplicity assume y' is discrete, that don't have worry about measure theory.
24

---

The privacy loss distribution for M can be decomposed as f
fM)=)))M(=:)()) = log P(M(()) ()) (y1,92))
P(M(x') = (9L,82))
log P(M (x) 91) P(M2 y1) = 122
P(M (a') y11) IP(M2 (x', y1) - y2)
PMM (a) -91) + log P(M2(2' (x' 122 = 122
P (M y1) = 1/2)
log P(M1 (x') = 1/1)
(M) (V1) (Ma (l2 (M))m))))) (V2).
Hence
2+ MMPiiVoossMMe))MMM... (exp(TZ))
Ys ( (2))
exp(T (xp( Y2- (M
(exp(T (exp(T//Mac)))Mace>) (Xa)))
=
(x)
<
exp(TfM (Xi)
sup
E
(exp(TfMn(=))) (12)))
(x))
31 Y2 (2
E PriPPivLossMM (x) (xm) (exp(TZ())
E we 22 (Mn (exp(r r 22))
sup
< exp(TTT + (0) exp(T(T++ 1)p2(1))
exx(((( (1) P2)
as required.
We require post-processing of p-zCDP to perform privacy accounting of the entire interaction between the analyst and mechanism in 4.2. In essence, we model the adversary as a post-processing operation applied to previous responses from the clipped Gaussian mechanism, which selects the next query. We demonstrate below that post-processing holds in the non-uniform setting-
Theorem D.5 satisfies p-PCDP and let f: X" - be an arbitrary randomized mapping. Define the post-poi procepre mechanism M: X - Z such that M(x) = f (Mo(x)). Then M also satisfies p-zCDP.
for p-zCDP). Let Mo: X + y be a randomized mechanism that
Proof. Fix i [m] and neighboring datasets (xx, E N that differ on the i-th entry. Fix 5 2 Applying Lemma 20 of Steinke [55], we have
E 2- (M (exp(r2)) S
Zot (a-PPriLoss(MM((t)]MMM... (exp(rZo)).
Now the right-hand side S exp(T(r + 1)p(i)) since Mo is p-zCDP, as required.
We also show that post-processing holds for non-uniform approximate DP. This result is used to prove generalization guarantees for minimization queries Theorem A.3, which can regarded as post-processed low sensitivity queries.
Theorem D.6 (Post- processro for (e, D)-D). Let My: X y be a randomized mechanism that satisfies (c, DDP and let f: X" + Z be an arbitrary randomized mapping. Define the post-processed mechanism M: x >> such that M(x:) f(Mo(x)). Then M also satisfies (e. DD..
Proof. We adapt the proof of Dwork and Roth [56]. First consider deterministic mapping f. Fix d [n]] and neighboring datasets (x, æ') E N, that differ on the i-th entry. Fix any event E S O and let G fo O f(o) E). We then have
P(M(x) E E) = P(Mo(x)) E G)
I e (P(Mo(x') G) + 5(i)
= e' P(M(xx) E E) + 5(),
We again assume that is discrete for simplicity, however the result holds generally.
25

---

which completes the proof for a deterministic mapping. To extend the result to random mapping. we can write f as a mixture of deterministic mappings. The result then follows, since a mixture of (e, 6D-DP mechanisms is also ()-PP.
D.2 Converting zero-concentrated DP to approximate DP
is convenient to analyze the privacy of the interaction ((X; A, M) for the clipped Gaussian mecha- nism using p-zCDP, since it provides tighter accounting than (e, 6D-DP. However, we ultimately need to convert (e, DDD in order to obtain a generalization guarantee using Theorem 3.4. Canonne. Kamath, and Steinke [38] provide conversion result from p-zCDP to (e, 3D- when the privacy parameters are uniform. Here we generalize their result to non-uniform privacy parameters.
We begin by generalizing Lemma 9 of Canonne, Kamath, and Steinke [38]. This is technical result that lower bounds (i) in terms of expectation involving the privacy loss random variable.
Lemma D.7. Let 2 0 and 8: [m=]]] + (0). A randomized mechanism M: X - y satisfies (e, DD if and only if
( 2
Z, Pro (max {0, - e(-=)()
for all indices i E [m]] and neighboring datasets (xx, x') E Ni.
Proof. Fix E [n]] and neighboring datasets (æ, x') E N,. Let Z; Pri)) M(x²)) and Z + PMivLoss(M(e')) [[M())). Our goal is to prove that
sup P(M(z) E) e P(M(2') E) E(max(0, e 21)) ECy
For any E C.V. we have
P(M((') E E) B(1 ((1 = B(IMaa)Ez))
Thus for all F C V. we have
P(M(x)) E E) (M((2)) E E) ((1 - E 2.)
= =B(1MMte)EE - ())
The worst event is E E v: - 0} Thus
sup P(M(x) E E) P(M(2') E E) = (1p---- (1- e 2i) BQ
= E[maxx()) (0, -
as required.
We can then use this lemma to generalize Proposition 12 of Canonne, Kamath, and Steinke [38], which converts Rényi DP to approximate DP. This is a step towards our final goal of converting zCDP to approximate DP, since zCDP is equivalent to enforcing Rényi DP over range of privacy parameters.
Proposition D.8. Let M: X + +y y be a randomized mechanism. Let E (1, and 2 Suppose D. (M(x) M((')) S for all indices i and neighboring datasets (x, x²) E N₁, where (a(P is the Rényi divergence of order a of distribution P from distribution Q. Then M (c. 8) -iffferrenlllll private for
8(1) ela-1)(p(i-o)
(1-1) a2
a
Proof. Fix index E [n]. neighboring datasets (x, x²) E No and let Zi PrivIoss((())))(2))) By assumption we have
E ((((a-1)z,) = -e(a-IDD.(Mc)]|Mee - 1)p())
26

---

By Lemma D.7, we seek an upper bound on E(max(0,1- z),, which we can set to 8(1). Following Canonne, Kamath, and Steinke, we pick e > such that max(0, 1 - - e s c ela for all 2 E R. Then
[mmax (0, - ef s e/a))))) S c. e! ()p(()
Canonne, Kamath, and Steinke show that the smallest value of e that satisfies this condition is
-((3mo) (1- 2)² )1 Thus
ela-1)(p(1)-c) 1 (1-2) _) e(a-1))(1) E (max((,, (0, - ee) s a-1 a
e=(1-a)
(1 1
=(i).
a-1
By exploiting the connection between Rényi DP and zCDP, we obtain conversion result from zCDP to approximate DP. This is generalization of Corollary 13 of Canonne, Kamath, and Steinke [38].
Corollary D.9. Let M: X + y be a randomized mechanism that satisfies p-zCDP. Then M is (D, for any 2 0 and ô [m] [0, 00) such that
( e( 1)(a" (())-)
1
a+-1
with a* arg min) (a- s)(ass,, p(t)-c)
(1 2)
Proof. Fix i E [n]] and (x. x') E Mr. Since M satisfies p-zCDP, we have D (M(z)) < ap(i) for all a E (1, oo). Proposition D.8 (with p(i) + ap(i)) provides conversion result to (e, DD for any choice of a. We choose minimize the worst case di). given by:
sup 5(1) = (aa-1)( (as p(i)-c)
(1- - = expg(a))
-
with g(a) = (a - sup, ((i) e) a log(1 1/a) - log((- a 1). A unique minimizer a* exists
since g(a) is smooth convex function.
We note that the optimizer a" can be found efficiently using binary search as described by Canonne, Kamath, and Steinke [38].
E Additional Empirical Results
In this appendix, we provide additional empirical results to complement those presented in Section 4.2. In Figure 3 of the main paper, we plotted a lower bound on the number of adaptive statistical queries k that be answered as function of the final dataset size There varied the initial size of the dataset no to ensure a fixed growth ratio n n//no = 3. In Figure 4, we produce a similar plot where we fix R4 500 000 and vary the growth ratio n/ng instead. Here again, observe that bounds (Ours-U and Ours-N) outperform the others in the non-asymptotic regime plotted, with the performance gap becoming more pronounced for larger values of b.
Figure covers the same setting as Figure in the main paper, except that it plots the confidence width on the vertical axis for fixed number of queries k = 000. A smaller confidence width better, and we see that the relative rankings of the bounds is the same as in Figure 3. Notably, the behavior of our bounds (Ours-U and Ours-N) is stable for all values of 1, whereas the confidence width degrades for the static-based bounds (JLNRSS and JLNRSS+) as b increases.
Figure 6 examines the impact of query batching for a fixed final dataset size 1 500 000 and fixed initial dataset size no 500 000. shows that both of our bounds (Ours-U and Ours-N) improve as the number of batches b increases, reaching a saturation point at around b = 40. This suggests it is better from a generalization perspective ask queries more frequently smaller batches when using our bounds. In contrast, the btatic-based bounds (JLNRSS and JLNRSS+) degrade as the number of batches increases.
27

---

Ouery batches 50
Query batches 10
Query Snerybaatee batches
Query batches
Number of queries, k
12500
10000
10000
Bound
12000
7300
5003
5000
2303
1.50
166
Final datas size,
Figure 4: Comparison of the number of adaptive statistical queries that can be answered with error tolerance a = 0.1 and uniform coverage probability 1 1 3 0.95 using growing dataset with fixed initial size no 500 000 in batched query setting. The number of queries (vertical axis) is plotted as function of the final dataset size n (horizontal axis), bound (curve style) and the number of query batches 6 (horizontal pancl). The right-most panel with 6 1 corresponds to the static data setting.
Query batches 50
Query batches - 10
Query batches -
Query batches -1
Confidence width,
0.4
0.30
0.3
0.20
0.25
020
0.2
Splt
DunNN
Our-UU
0.2
0.15
0.15
JUMRSS
JUNSS
61
0.10
0.10
1.0
1.5
0.5
1.0
155
0.5
1.5
Final datas
Figure 5: Comparison of the error tolerance (vertical axis) for 10 000 adaptive statistical
queries with uniform coverage probability 1 - 3 = 0.95 using different ADA bounds (curve style). The queries are answered using a growing dataset with final size (horizontal axis) and growth ratio 12/ng- = 3, and are grouped into 6 batches (horizontal panel). The right-most panel with 6 = corresponds to the static data setting.
15000
Number of queries, k
12500
Bound
10000
Ours-U
Ours N
7500
Split
JLNRSS
5000
2500
0
100
Number of queries batches,
Figure 6: Comparison of the number of adaptive statistical queries that can be answered with error 0.95 using a growing dataset with
tolerance = 0.1 and uniform coverage probability initial size no = 500 000 and final size n = 1 500 000 in a batched query setting. The number of queries (vertical axis) is plotted as function of the number of query batches (horizontal axis) and bound (curve style).
28

---

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 claims in the abstract and introduction summarize the paper's is key contribu- tions. These contributions are mostly theoretical results with all proofs offered in the paper's body or appendices. Empirical observations/claims are based on experimental evaluation presented in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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.
is fine include aspirational goals as motivation as long 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: Yes, limitations of the paper are discussed in Section 6: namely that (like most of the literature on adaptive data analysis) we assume i.i.d. data and worst-case analyst. While these are conventional assumptions. we highlight these assumptions clearly throughout the paper and again in Section 6 as limitations. We cite relevant work in the literature that has relaxed these assumptions in the static scenario, previously.
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 encouraged to create separate "I "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, 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 the scope of the claims made, e.g., if the approach only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect 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 in low lighting. Or speech-to-text system might not be 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.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
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 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 concerning limitations.
29

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We present key theoretical results in Sections 3 and 4 with narrative text and schematic (Figure 2) explaining how the derivation proceeds. Proofs for these key results are provided in Appendices B and C. Some of these proofs rely on properties of non-uniform differential privacy, which are stated and proved in Appendix D.
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 the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or 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 information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We produce plots based on evaluating mathematical expressions Figure 3). All parameter settings are specified in Section 4 and in the caption below each plot.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not 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. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the of a large language model), releasing 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
30

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: Our empirical results are obtained by evaluating mathematical expressions, so there is no data or code to release.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
public/gue wtwgggiidc/ceSsuueee
sondesuubisssonooliit cassonnnlccyy cy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /wt////oobssssiiioooooooo www.himmmissooooooocccc... for more details.
/nips. wwt.ccccppccccccecc httpppiilgguuteee/oeuuutttiiiiii
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 new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: We do not train or test models. When instantiating our bounds in Figures 3, and 6, we specify parameter settings in the captions.
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 to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as 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:
We plot quantities derived from exact bounds, so there is no statistical error to
consider.
Guidelines:
31

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emror 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 be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
We do not conduct experiments that require significant compute resources.
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, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn'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 https: attps://neurips: wctp:clic/ccctccicccccccccccccee wew.iiiieeeeeeeeeeeeeeeeeeeeieee
Answer: [Yes]
Justification:
We have read the Code of Ethics and confirm that our work complies.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction)
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
32

---

Justification: We motivate our work by highlighting the potential negative consequences of the replication crisis/p-hace haans///daa dredging in the introduction. Adaptive data analysis sheds light on generalization in this important and practical adaptive setting. We do not anticipate specific negative societal impact of the work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used 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 unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition 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
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We not releasing assets, so there such risks to consider.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 that 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
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
We do use assets created by others.
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.
33

---

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 a 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/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [NA]
Justification: Our work is theoretical, so there are no assets of this nature to release. Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/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 an anonymized URL or include an 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 as details about compensation (if any)?
Answer: [NA]
Justification: Our work theoretical and does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information
supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (TRB) approvals or equivalent for research with human subjects
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: Since our work does not involve human subjects, there no need to obtain IRB approval.
Guidelines:
34

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be 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 expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We did use LLMs conduct this research.
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 to our LLM policy (https:/ fattps://neurd:: wwt.c//eeeeennce//222222222 for what should or should not be described.
35


Reviews:
[{"review_id": "FzWLlMjmfo", "reviewer": "Reviewer_Cyhf", "summary": "The paper considers application of a differential privacy to address the problem of adaptive data analysis in for a growing dataset. \n\nSpecifically, authors consider a sequence of elements $X_1, \\ldots X_n$ sampled i.i.d. from a probability distribution $P$ over a universe $\\mathcal{X}$. At each timestep $n_0 \\leq t \\leq n$, the algorithm, having access only to elements $X_1, \\ldots X_t$, is supposed to provide an answer to a low-sensitivity query $q$, provided by analyst. (For simplicity, a special case of a low-sensitivity query, is a statistical query, which is specified by a function $q : \\mathcal{X} \\to [0,1]$. The intended answer to the statistical query is an approximation of $\\mathbb{E}_{X \\sim \\mathcal{P}} q(X)$.) The subsequent queries specified for the mechanism can potentially depend on the answers to the previous queries, and the algorithm aims at answering all those queries approximately correctly, even against an adversarial analyst. \n\nIn a static dataset setting, where $X_1, \\ldots X_n$ are known to the mechanism as it starts answering the queries, this is extremely well-studied topic. Naively, to achieve simultanous error $\\varepsilon$, on all $m$ (adaptively chosen) queries, one would used around $n=O(m/\\varepsilon^2)$ samples - $1/\\varepsilon^2$ samples for each query. The celebrated line of research stemming from an observation that methods from Differential Privacy could be used to improve the error/sample complexity trade-off: using those methods one can achieve error $\\varepsilon$ on $m$ queries using number of samples that grows only as $O(\\sqrt{m}/\\varepsilon^2)$.\n\nSimultanously, in recent years, a growing body of research addresses providing privacy guarantees using differential privacy under the streaming setting: when the data is not necessairly known to the algorithm at the beginning of the computation, but instead is provided to algorithm one by one.\nIn this paper authors combine those two prolific lines, providing an answer to a natural, and important question: can differential privacy be used to adaptively answer statistical (or low-sensitivity) queries for a sequence of independent samples from a given distribution, in a streaming scenario.\n\nAs in the case of adaptive data analysis in a static data set, they introduce an intermediate notion of \"posterior stability\", and show that on one hand that any mechanism satisfying differential privacy with particular parameters, also satisfies the posterior stability; then they proceed to showing that the posterior stability in fact implies the accuracy guarantee for an adaptive algorithm operating on a growing data set - i.e. analog of the \"transfer theorems\" known in the static dataset setting.\n\nFinally, they instantiate this for a specific case of the Gaussian Mechanism, satisfying concrete Differential Privacy guarantees, which by the transfer theorems imply concrete generalization guarantees for the distributional setting. In the appendix they additionally provide a generalization of the framework to \"minimization queries\", which could be used as a building block of more involved learning algorithms.", "questions": "Is there any more interpretable asymptotic guarantee that could be deduced from Theorem 4.4 (or from the framework in general), giving a sense of how the error profile $\\alpha_t$ depends on $t$, and the number of queries asked in the batch at time step $t$? Is there a way to interpret formula in the Theorem 4.4?", "limitations": "See above.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The paper posits and answers a natural question, combining in a natural way two very prolific lines of research within the differential privacy. It is extremely well written, and provides a rather general theorem translating concrete DP guarantees (that can be achieved thanks to large body of DP primitives, and convenient composability theorems for DP) into statistical generalization guarantees that are desirable as an end goal. The paper is also extremely well written, and provides plots comparing the generalization guarantees of the new mechanism, with attempting to achieve the same by using either trivial methods, or previous DP-based mechanism for static data.\n\nThe main weakness of the paper is that even the most concrete instantiation of the framework (Theorem 4.4) still does not provide much intuition about asymptotic behavior of the proposed solution. The formula for error parameter $\\alpha'$ surprisingly does not depend on $t$, and is relatively involved, and difficult to interpret. It would be great to see a (potentially worse) asymptotic bound that can be deduced from concrete instantiation of this framework with a specific mechanism, that is more interpretable.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and positive feedback on our paper. We appreciate your recognition of the paper's contribution in combining two lines of research within differential privacy. Below we provide clarification and context for your comments about Theorem 4.4. If you are satisfied, we’d be grateful if you might consider increasing your score. \n\n> Is there any more interpretable asymptotic guarantee that could be deduced from Theorem 4.4 (or from the framework in general), giving a sense of how the error profile $\\alpha_t$ depends on $t$, and the number of queries asked in the batch at time step $t$? Is there a way to interpret formula in the Theorem 4.4? \n\nTheorem 4.4 is stated for the Gaussian mechanism with a constant noise scale $\\sigma_t = \\sigma$. In this case, the confidence width/error profile $\\alpha_t’ = \\alpha’$ is indeed constant with respect to $t$ (see proof in Appendix C.1). In words, Theorem 4.4 guarantees that the worst-case absolute error across _all_ rounds/queries is bounded by $\\alpha’$ with probability $1 - \\beta’$. \n\nOur bound can be easily extended to round-dependent $\\sigma_t$ (and hence round-dependent $\\alpha_t'$) by simply replacing $\\sigma$ with $\\sigma_t$ in the statement, assuming $\\sigma_t \\propto \\alpha_t$. However, we chose to use a constant $\\alpha'$ in our main results for two reasons: \n\n1. It simplifies the interpretation of the results: we can report the number of queries that can be answered at a fixed confidence width. \n\n2. If we considered round-dependent confidence width $\\alpha_t’$, we would need to make assumptions about the dependence that an analyst would find tolerable."}, {"review_id": "iHpKex1rk8", "reviewer": "Reviewer_ow1s", "summary": "Differential privacy can be used to provide generalization guarantees for data workflows where queries are issued adaptively. However, all prior work assumed that the dataset is static. This paper studies adaptive data analysis when data grows over time. That is, an analyst interactively submits queries from a fixed class to a differentially private mechanism. At time $t \\in [n_0, n]$, the mechanism runs only on the first t records of a \"final\" dataset containing n records. \n\nThe authors consider three query classes: statistical queries (standard definition), \"low-sensitivity queries\" (a larger class of scalar queries, where the sensitivity is a vector indexed by the dataset size) and minimization queries (solutions to certain optimization problems). \n\nIn this setting, the paper proves generalization guarantees similar to what exists in the static case. The transfer theorem says that if we have a mechanism that answers accurately based on the data available for each query (snapshot accuracy) and an interaction that satisfies DP, then the answers for each query are actually close to the the expected value of the query over the true distribution. \n\nFinally, the bounds are instantiated by answering statistical queries with the Gaussian mechanism. The new framework outperforms a baseline that uses static ADA on disjoint data subsets for each batch of queries, and a baseline that just runs each query on a disjoint subset.", "questions": "How did you set the round-dependent standard deviation in the experiments, and what are the epsilon, delta (or delta(t) for Ours-N?) guarantees in Fig 3?", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The paper fills a natural gap, by studying a valuable problem (adaptive data analysis) in a relevant setting (growing data). I agree with the authors that growing data is still a sorely understudied setting, even though practical DP applications are actually quite likely to operate under this setting. \n\nThe results are significant, since the bounds outperform what could be obtained by composing existing bounds over disjoint static datasets. The proof techniques seem to broadly follow previous work from Jung et al, with some novel time-dependent budget and accuracy variants.\n\nA few things were unclear to me in the evaluation:\n- I didn't understand how the round-dependent standard deviation was set in the experiments. Intuitively, I might want to spend more budget on the first queries, so I would expect something like sigma_t proportional to t. Indeed, it should become easier and easier to get good accuracy as data accumulates, at least for statistical queries, where alpha is the absolute counting error normalized by t. \n- On a related note, what is the exact time-dependent delta for \"Ours-N\"? And more generally, what are epsilon and delta in Fig 3, and how can we compare the utility for Ours-N and Ours-U on the same graph when they operate under different privacy guarantees?\n- Finally, if I understand correctly, Fig 3 takes a collection of theorems and plots the values under various configurations. But it could be interesting to see an evaluation over a workload of statistical queries over an actual growing dataset. Instead of showing the theoretical number of queries within the error target, could we look at the empirical error distribution for each batch, e.g. with box plots?\n\nAlso, regarding the time-dependent guarantees:\n- The paper uses a time-dependent delta, but not a time-dependent epsilon. Internally, rho depends on t, but it seems that the zCDP to approximate DP conversion stashes all the time-dependencies into delta. I wonder why and what would be the implications of a time-dependent epsilon.\n- The semantics of time-varying delta under fully adaptive composition are left unspecified. The appendix mentions that individual filters could be used, such as the one from Feldman and Zrnic, but does not detail how.\n- In the paper, budget only depends on time, but personalized DP supports budget that depends on the data from record themselves. Would individual accounting a la Feldman and Zrnic yield extra savings, e.g. for certain data distributions and queries where most records have low individual sensitivity?\n\nOverall, I found the paper extremely clear and well-written. The results were crisp and motivated. Fig 2 was useful, and the background related work sections were particularly pleasant to follow. As a non-expert, this was a great opportunity to learn about the field -- thank you!", "was_revised": true, "final_justification": "The authors answered my questions, and I maintain my high score.", "rebuttal": "We thank you for your thorough review and positive feedback. We're pleased that you recognize the significance of our work in addressing the understudied setting of growing data for adaptive data analysis. We address your questions and comments below. We welcome further feedback, including a potential reconsideration of your score if you feel it's warranted. \n\n> Round-dependent standard deviation in experiments \n\n \n\nWe used a constant noise scale $\\sigma_t = \\sigma$ for all rounds, which results in a constant confidence width $\\alpha_t’ = \\alpha’$. We chose this approach since: \n\n1. It simplifies the interpretation of the results: we can report the number of queries that can be answered at a fixed confidence width. \n\n2. If we considered round-dependent confidence width $\\alpha_t’$, we would need to make assumptions about the dependence that an analyst would find tolerable. \n\n> What is the exact time-dependent delta for \"Ours-N\"? And more generally, what are epsilon and delta in Fig 3, and how can we compare the utility for Ours-N and Ours-U on the same graph when they operate under different privacy guarantees? \n\nThe time-dependent $\\delta(t)$ for \"Ours-N\" is defined in Lemma 4.2. The computation involves three steps: (1) the privacy accounting is done using non-uniform zCDP; (2) given $\\mathbf{\\rho}(t)$ and $\\epsilon$, we compute the optimal order of the Renyi divergence $\\gamma^\\star$; (3) finally, we plug $\\mathbf{\\rho}(t)$, $\\epsilon$ and $\\gamma^\\star$ into $\\psi$ to obtain $\\mathbf{\\delta}(t)$.  \n\nIn Figure 3, we follow the approach of Jung et al. (2020) by optimizing over free parameters to obtain tighter bounds. Specifically, we optimize over $\\epsilon$, $\\sigma$, and $\\beta$, with $\\delta$ determined by Lemma 4.2. As a result, the privacy guarantee can vary slightly between points, which is acceptable in our context, as our focus is on generalization under adaptation (data reuse) rather than privacy per se. We will clarify this point in Section 4.2 of the paper. It's worth noting that we found the optimal values $\\sigma = 0.008$, $\\beta = 10^{-5}$, $\\epsilon = 0.04$ to be quite stable, varying only beyond the first significant figure. \n\n> Checking what’s plotted in Fig 3, and suggestion to evaluate on an actual growing dataset and analyst. \n\nYou're correct that Fig 3 plots theoretical bounds, representing worst-case scenarios for both the data distribution and analyst's strategy. While we agree that case studies with real adaptive analysts could be valuable future work, it’s important to note that: \n\n- Simulation results would be highly dependent on specific choices, potentially limiting their generalizability. \n- Our theoretical analysis is necessary to understand the fundamental limits for any real setting. \n\n > Why not consider a round-dependent $\\epsilon$? \n\nWhile it's certainly possible to define privacy using an $\\epsilon$ that depends on $t$, this approach isn't useful for obtaining generalization bounds, at least with our current proof technique. For example, if we used a time-dependent $\\epsilon$, we would encounter issues following equation (15) in our proof of Lemma 3.3, as the sum over $t$: \n\n$$ \n\\sum_{t = 1}^{n} (e^{\\epsilon(t)} - 1) \\sum_{\\pi \\in \\Pi^+(\\alpha, x)} \\mathbb{P}(\\Pi = \\pi) \\frac{1_{t \\leq t^\\star(\\pi)}}{t^\\star(\\pi)} \n$$ \n\nwould no longer simplify nicely. This is why we opted for a round-dependent $\\delta$ instead. \n\n> Appendix doesn’t detail how to do fully adaptive composition with time-varying delta, e.g. using Feldman and Zrnic (2021). \n\nWe did not explain how to use Feldman and Zrnic’s filter, as it uses Renyi DP for accounting, not zCDP, which we used for accounting in Section 4. We would be happy to include it if the reviewer feels this would be helpful. In essence we would integrate Feldman and Zrnic’s Algorithm 3 into our Algorithm 2, with the main change being that $\\bar{\\rho}$ and $\\rho$ become $t$-dependent, and upon termination, the interaction would satisfy $(\\alpha, \\vec{\\rho})$-RDP rather than $\\rho$-zCDP. \n\n> Budget only depends on time, but personalized DP supports budget that depends on the data from record themselves. Would individual accounting yield extra savings? \n\nWe'd like to clarify that in our paper, the budget actually depends on the _record_ received at round $t$, which is similar to personalized DP. You're correct that individual accounting can yield savings, especially for the “sparse” setting considered by Feldman and Zrnic (2021)."}, {"review_id": "0vgh98cgEX", "reviewer": "Reviewer_KtCZ", "summary": "This paper studies adaptive data analysis in the context of a growing dataset. In this line of work there is a dataset consisting of i.i.d. draws from a distribution $P$ and an analyst is interrogating it by asking an adaptively chosen sequence of queries. Our goal is to design mechanisms for responding to those queries such that, despite the data reuse, we can bound the absolute error in all query responses simultaneously with high probability. The key new aspect considered in this work is to allow the underlying dataset to grow over time as the analyst issues the queries. The specific protocol works as follows: the analyst waits for the first $n_0$ to appear and then after each successive data point arrives, the analyst can ask a sequence of queries with that snapshot of the data.\n\nThe analysis in the paper roughly follows that of Jung et al. [15]. At a high level, they argue that when a mechanism is snapshot-accurate (in the sense that every query response is close to its empirical value on the data snapshot) and the induced interaction between the analyst and mechanism is posterior-stable (in the sense that the expected query values on the posterior distribution conditioned on the transcript are not far from from the expected query distributions on the original data distribution), then it will be distributionally accurate as well (meaning that query responses are accurate for all queries). In the specific case when the Gaussian mechanism is used to answer queries, we obtain snapshot accuracy because the mechanism adds a small amount of noise to the empirical values, and the authors argue that for several query classes, differentially private mechanisms induce posterior-stable interactions. Putting this together gives generalization guarantees that hold for all the queries simultaneously.\n\nThe paper also compares empirically the number of queries that can be answered as a function of the total dataset size when the queries arrive in batches that must be answered when they were issued. For prior work that does not handle growing data, they collect a different batch of data for each batch of queries and use that static data with the prior work's method. They also consider a splitting baseline that answers each query with disjoint subset of the data. In these experiments, their proposed method is able to answer the most queries as a function of the given data size.", "questions": "See questions under strengths and weaknesses.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "## Strengths\n1. The paper is well written and relatively easy to follow.\n1. The extension of adaptive data analysis generalization guarantees to the case where the dataset grows over time seems natural and useful in practice.\n1. The proposed method performs better than natural baselines in the empirical comparison.\n\n## Weaknesses\n1. This is relatively minor, but I think the paper would be strengthened by identifying places where the analysis and arguments deviate significantly from Jung et al. [15]. After the modified definitions have been introduced, it is somewhat unclear if any of the arguments need significant new ideas, or if they more or less go through unmodified. In the introduction the authors (on line 54) write that a key insight is \"in the growing data setting, [...] the posterior distribution should be marginalized over unseen future data at the time the query was submitted, while conditioning on the full history of the analysis.\" Is this a major change to the argument?\n1. The experiments mostly focus on the setting where queries must be answered quickly and we cannot wait until the full dataset has arrived to start answering them. As an optimistic baseline, it would be interesting to include the number of queries that can be answered by prior work adaptively if we wait for the entire dataset of size n to arrive. Is it true that this number of queries should be higher than the proposed method, or do we actually gain some additional generalization due to the fact that some of the queries are answered on a subset of the data?", "was_revised": true, "final_justification": "The authors addressed my comments adequately and after reading the other reviews I do not have major concerns, so I will keep my positive score.", "rebuttal": "We appreciate your thoughtful review and your overall positive reception of our paper. We'd like to address your comments and provide some additional context to highlight the significance of our contributions. If you find them satisfactory, we would be grateful if you would consider updating your score. \n\n> This is relatively minor, but I think the paper would be strengthened by identifying places where the analysis and arguments deviate significantly from Jung et al. [15]. After the modified definitions have been introduced, it is somewhat unclear if any of the arguments need significant new ideas, or if they more or less go through unmodified. In the introduction the authors (on line 54) write that a key insight is \"in the growing data setting, [...] the posterior distribution should be marginalized over unseen future data at the time the query was submitted, while conditioning on the full history of the analysis.\" Is this a major change to the argument?  \n\nOur approach follows a similar high-level structure to Jung et al.: upper bounding the tail probability of the distributional error using two other tail probabilities bounded by snapshot accuracy and posterior stability. However, adapting this to the growing data setting introduced challenges and novel elements. \n\nIn Jung et al.'s work, the tail probabilities depend on a \"reference point\" for each query $q$, evaluated on the posterior distribution $\\mathcal{Q}_\\Pi$. For our growing data setting, we had to reconsider this reference point, choosing to marginalize over unseen future data at the time of the query. This wasn't an obvious choice and only came to us after exploration of alternatives. \n\nWe then adapted the definition of posterior stability based on this new reference point. The most challenging aspect was proving the conversion lemmas from differential privacy to our new definition of posterior stability. This required careful adaptation as the support of the posterior grows with $t$. Since $\\mathcal{Q}_{\\Pi}^{t}$ only covers data observed up to round $t$, and the analyst controls when the mechanism ingests the next data point, the size of data used for a query depends on the transcript $\\Pi$.  \n\nThis dependency complicated our proofs significantly. For instance, in Lemma 3.3, we could no longer interchange sums (three steps before equation 15), requiring more complex manipulations to tightly invoke differential privacy. Similar challenges arose in Lemma 3.5. \n\nWe appreciate your suggestion and are happy to incorporate this discussion into the paper to clarify the distinctions between our work and previous approaches. \n\n> The experiments mostly focus on the setting where queries must be answered quickly and we cannot wait until the full dataset has arrived to start answering them. As an optimistic baseline, it would be interesting to include the number of queries that can be answered by prior work adaptively if we wait for the entire dataset of size n to arrive. Is it true that this number of queries should be higher than the proposed method, or do we actually gain some additional generalization due to the fact that some of the queries are answered on a subset of the data? \n\nIn fact, our experiments do include the scenario you describe as an optimistic baseline. Specifically: \n\n- The case where the analyst waits for the entire dataset corresponds to $b = 1$ in our experiments (see line 313 in the paper). \n\n- In this case ($b = 1$), our bound and the tighter JLNRSS bound coincide, as shown in the last panel of Figure 3. \n\n- Comparing the first three panels in Figure 3 (where $b > 1$) with the last panel ($b = 1$), we can see that waiting for the full dataset allows answering roughly 3–4 times more queries, regardless of which bound is used. \n\nThis comparison illustrates a key trade-off: being forced to use smaller snapshots early on does indeed harm the worst-case error over all queries. However, our method provides a way to handle scenarios where immediate query responses are necessary, while still maintaining strong generalization guarantees."}, {"review_id": "aRLQ0g7yLE", "reviewer": "Reviewer_BVSk", "summary": "As suggested by its title, this paper considers adaptive data analysis (ADA) - an interaction between a data curator and an analyst(s) issuing adaptive queries based on previous responses, where data is accumulated throughout the interaction. Previous work proved that ADA may lead to statistically invalid results by letting the analyst \"overfit\" the queries to the dataset, even without direct access to that data, just by observing responses to past queries. This risk can be mitigated by ensuring some stability properties of the response producing mechanism, such as the ones guaranteed by differential privacy (DP), which guarantee statistical validity for $O(n^2)$ queries where $n$ is the sample size.\nPrevious work considered only a fixed dataset setting, but in some cases it might be useful to gradually increase the dataset (e.g., as a price for the queries [1]). A natural baseline option can be fixing some $n_0$, using the first $n_0$ data elements to reply to some $O(n_{0}^{2})$ queries, then tossing those points and using the next $n_{0}$ data elements to reply to the next$O(n_{0}^{2})$ queries, and so on.\nThis work considers a more sophisticated technique, extending the analysis of [2] to the dynamic sample size setting, significantly increasing the number of queries that can be estimated.\n\n[1] Woodworth Blake E. et al. \"The everlasting database: Statistical validity at a fair price\" (NeurIPS 2018)\n\n[2] Christopher Jung et al. “A New Analysis of Differential Privacy’s Generalization Guarantees” (ITCS 2020)", "questions": "What is the purpose of the $n_0$ variable in algorithm 1?\nSince the choice when to issue the queries is governed by the analyst, why can't the mechanism simply reply from $n_0=1$?\n\nWhy was $n_0$ fixed for all experiments to be $n/3$?\nIt seems like a fair comparison to JLNRSS would be setting $n_0 = n/b$. I assume it won't induce a huge change (equivalent to $\\approx 2/3$ increase in sample size), but nevertheless it seems like the natural choice, which keeps the sample size constant throughout the rounds.\n\nHow is it possible that the empirical results in Figure 1 show the maximal number of queries that can be answered by your method for a given sample size (say $1.5 \\cdot 10^6$) *decreases* with $b$ from 1 to 5 then *increase* from 5 to 10 to 50?\nThe existing formal guarantees are too convoluted for me to analyze asymptotically, but I would expect it to decrease with $b$ as does the baseline method of JLNRSS. This result is emphasized in Figure 6 but without explanation. Do you expect the saturation to remain even when $b \\rightarrow k$? this sounds unreasonable to me.\nFigure 5 presents a different surprising result. It seems like your method is barely affected by $b$. That is, the $\\alpha(n)$ profile for fixed $k$ and $\\beta$ barely changes as we vary $b$, which I have a hard time understanding.\n\n\n**Minor comments**\n* The $\\Delta_t$ variables seem redundant, and can be fixed to some single $\\Delta$ by resealing the queries and the $\\alpha_t$ accuracy requirements accordingly, this will also simplify notations in Lemma 3.5\n* The posterior distribution mentioned first in line 169 is not define in the body of the paper, and might be hard to understand for the unfamiliar reader\n* It seems like the $\\mathcal{N}_{t}$ notation in Definition 2.4 was not defined, and I suspect it is a mistake and should've been $\\mathcal{X}^{t}$\n* I think the result in Lemma 3.3 can be improved by restricting $\\sum \\delta(t)$ to the sum over the indexes where queries were issued (or, alternatively, we can define $\\delta(t)=0$ for the rest of the rounds)\n* Lemma 4.2 holds regardless of the clipping, so I recommend removing it from the statement", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\nThe main contribution of this work is the generalization of existing results in adaptive data analysis from the constant dataset size to the growing data setting. While the asymptotic (in sample size and accuracy parameters) guarantees it provides are identical to the ones provided by the natural baseline, the improvement is nevertheless significant for many finite sample sizes, and so can be proven very useful. The proof techniques, though not very different from the original work, encounter various subtle issues and iseseveral novel techniques.\n\n**Weaknesses**\n\nMost of the mathematical analysis is a direct generalization of the work by [1]. While it requires careful care and some novel technical steps, it does not provide additional conceptual insights.\n\nThe paper is lacking comparisons to direct application of the results for DP [2, 3], which might be relevant (though, some are computationally inefficient, so I am not certain there is a clear comparison)\n\nI find the empirical data results somewhat concerning (see questions section). I am open to change my score if this question will be settled.\n\n[1] Christopher Jung et al. “A New Analysis of Differential Privacy’s Generalization Guarantees” (ITCS 2020)\n\n[2] Rachel Cummings et al. “Differential Privacy for Growing Databases” (NeurIPS 2018)\n\n[3] Yuan Qiu and Ke Yi. \"Differential Privacy on Dynamic Data\" (ArXiv 2022)", "was_revised": true, "final_justification": "The authors provided sufficient clarification to most of my questions, though there are some empirical results which I still find less intuitive and cannot be corroborated by the theory.", "rebuttal": "Thank you for your detailed review and for recognizing the significance of our work in generalizing existing results in adaptive data analysis to the growing data setting. Now that we have addressed your concerns, in particular your core question about empirical data results, we hope that you will update your score as offered. If you have any follow-up questions, we'd be happy to address them.  \n\n> The paper is lacking comparisons to direct application of the results for DP [2, 3], which might be relevant (though, some are computationally inefficient, so I am not certain there is a clear comparison) \n\nThank you for this suggestion. The papers you mention study DP mechanisms for growing data, providing asymptotic bounds for snapshot accuracy (a.k.a. sample accuracy). However, they don't address generalization, which is the focus of our work. While it's possible to plug in their results for snapshot accuracy and privacy into our framework, we didn't pursue this because the papers don't provide the necessary constants for a meaningful comparison.  \n\n> What is the purpose of the variable $n_0$ in algorithm 1? Since the choice when to issue the queries is governed by the analyst, why can't the mechanism simply reply from $n_0 = 1$? \n\nThe variable $n_0$ represents the initial sample size before the analysis begins. While our bounds can theoretically be instantiated with $n_0 = 1$, this would lead to vacuous results due to low posterior stability/privacy. This is expected behavior – it is difficult to achieve reasonable privacy on a dataset containing one record without adding a large amount of noise. \n\n> Why was $n_0$ fixed for all experiments to be $n/3$? It seems like a fair comparison to JLNRSS would be setting $n_0 = n / b$.  \n\nWe'd like to clarify a few points regarding $n_0$: \n\n- We don't fix $n_0 = n/3$ in all experiments. In Figs 4 and 6, we vary $n$ independently of $n_0$, allowing us to explore a range of scenarios. \n\n- The choice of $n_0 = n/3$ reflects scenarios where a substantial initial dataset is available before adaptive querying begins. This choice balances immediate utility (answering queries early) with overall performance (maintaining low error across all queries). \n\n> How is it possible that the empirical results in Figure 1 show the maximal number of queries that can be answered by your method for a given sample size (say $1.5 \\cdot 10^6$) decreases with $b$  from 1 to 5 then increase from 5 to 10 to 50? \n\nWe believe you're referring to Fig 3 rather than Fig 1. The behavior you've observed is due to the special case definition for $b = 1$. When $b = 1$ and $n > n_0$, we stipulate that all queries are asked in a single batch at round $n$, which is equivalent to the static setting from prior work. (Note: if we didn’t define this special behavior for $b = 1$, all queries would be asked at round $n_0$, ignoring the remaining $n - n_0$ data points, which isn’t an interesting case to consider).  \n\nThis explains the discontinuous behavior between $b = 1$ and $b > 1$. We can see how this is not clear from the figure’s presentation, and are considering replacing the “$b = 1$” label with “Static” instead, but we welcome your advice on how best to present this distinction.  \n\n> The existing formal guarantees are too convoluted for me to analyze asymptotically, but I would expect it to decrease with $b$ as does the baseline method of JLNRSS. This result is emphasized in Figure 6 but without explanation. Do you expect the saturation to remain even when $b \\to k$? this sounds unreasonable to me. Figure 5 presents a different surprising result. It seems like your method is barely affected by $b$. That is, the $\\alpha(n)$ profile for fixed $k$ and $\\beta$ barely changes as we vary $b$, which I have a hard time understanding. \n\nThese are interesting questions. We don’t have a strong intuition for why the asymptotic behavior would disagree with our empirical results – namely that the number of queries $k$ increases with $b$ for fixed $\\alpha’$, and the confidence width $\\alpha’$ decreases with $b$ for fixed $k$. \n\nAs you rightly point out, the bound is difficult to analyze asymptotically (in the limit $b \\to n - n_0$), as it is defined as the solution to an optimization problem over the free parameters, which may depend implicitly on $b$. As requested here is a table for Fig 5.  \n\n| Bound | Batches (b) | Final size (n) | Confidence width (ɑ) | \n|--------|--:|--:|------:| \n| Ours-U | 1 | 500000 | 0.119229 | \n| | | 700000 | 0.100801 | \n| | | 900000 | 0.0889361 | \n| | | 1100000 | 0.0804802 | \n| | | 1300000 | 0.0740615 | \n| | | 1500000 | 0.0689744 | \n| | 5 | 500000 | 0.174153 | \n| | | 700000 | 0.147117 | \n| | | 900000 | 0.129732 | \n| | | 1100000 | 0.117354 | \n| | | 1300000 | 0.107964 | \n| | | 1500000 | 0.100526 | \n| | 10 | 500000 | 0.170241 | \n| | | 700000 | 0.14382 | \n| | | 900000 | 0.126829 | \n| | | 1100000 | 0.114731 | \n| | | 1300000 | 0.105553 | \n| | | 1500000 | 0.0982822 | \n| | 50 | 500000 | 0.167663 | \n| | | 700000 | 0.141648 | \n| | | 900000 | 0.124917 | \n| | | 1100000 | 0.113003 | \n| | | 1300000 | 0.103964 | \n| | | 1500000 | 0.096804 | \n| Ours-N | 1 | 500000 | 0.119229 | \n| | | 700000 | 0.100801 | \n| | | 900000 | 0.0889361 | \n| | | 1100000 | 0.0804802 | \n| | | 1300000 | 0.0740615 | \n| | | 1500000 | 0.0689744 | \n| | 5 | 500000 | 0.167389 | \n| | | 700000 | 0.141418 | \n| | | 900000 | 0.124715 | \n| | | 1100000 | 0.112821 | \n| | | 1300000 | 0.103797 | \n| | | 1500000 | 0.0966487 | \n| | 10 | 500000 | 0.161115 | \n| | | 700000 | 0.136131 | \n| | | 900000 | 0.120059 | \n| | | 1100000 | 0.108614 | \n| | | 1300000 | 0.0999301 | \n| | | 1500000 | 0.0930505 | \n| | 50 | 500000 | 0.156637 | \n| | | 700000 | 0.132356 | \n| | | 900000 | 0.116736 | \n| | | 1100000 | 0.105611 | \n| | | 1300000 | 0.0971692 | \n| | | 1500000 | 0.0904813 | \n\nWe observe that the error does decrease marginally with increasing $b$ which is consistent with Fig 6. \n\n> The $\\Delta_t$ variables seem redundant, and can be fixed to some single $\\Delta$ by resealing the queries  \n\nPerhaps we’re missing something, but we can’t see how this would work. If we were to abandon the round-dependent sensitivity $\\Delta_t$, we would sacrifice some tightness in the bounds. In Lemma 3.5, the posterior stability depends on $\\min_t t \\Delta_t$, $\\max_t t \\Delta_t$, and $\\max_t \\Delta_t$. These three factors cannot be described using a single sensitivity without sacrificing tightness. \n\n> Posterior distribution from line 169 is not defined in the body of the paper \n\nThis is defined on line 172 as $\\mathcal{Q}_{\\Pi}^{t} = \\mathcal{P}^t | \\Pi$. Please let us know if this is unclear. \n\n> It seems like the $\\mathcal{N}_t$ notation in Definition 2.4 was not defined, and I suspect it is a mistake and should've been $\\mathcal{X}^t$.  \n\n$\\mathcal{N}_t$ is defined in words on lines 187-188. It denotes the set of neighboring datasets that differ on the $t$-th record. It is not equal to $\\mathcal{X}^t$. \n\n> I think the result in Lemma 3.3 can be improved by restricting $\\sum \\delta(t)$ to the sum over the indexes where queries were issued \n\nWe don’t see how this would work. In Lemma 3.3, we don’t assume knowledge of the rounds in which queries are issued. Rather, we consider a worst-case analyst. The proof is centered around the round, query and response that result in the largest error (the starred quantities in the proof). After invoking DP on a carefully constructed event (eq. 15), the sum over $\\delta(t)$ appears without any connection to the transcript $\\pi$ (which specifies the rounds in which queries were issued). We therefore don’t see how the sum could be restricted to only those rounds for which queries were issued. \n\n> Lemma 4.2 holds regardless of the clipping, so I recommend removing it from the statement \n\nYou're correct that Lemma 4.2 holds for both the clipped and ordinary Gaussian mechanisms. We initially presented it for the clipped Gaussian mechanism as our work assumes [0, 1]-bounded queries. However, for generality, we'll revise the statement in Lemma 4.2 to read: \"where $M$ is the ordinary or clipped Gaussian mechanism\"."}]

Author rebuttal:

Meta-review: The reviewers all agreed that this paper was a strong submission. The strengths identified included: it combined two lines of work in the DP literature to fill a natural gap in the literature, it is well-written, it provides a strong set of theoretical results and verified these results empirically. There was a question of novelty with respect to Jung et al., but the authors engagement in the discussion phase helped clarify these, and the authors promised to make this more clear in the final version.

The reviewers were largely positive before the rebuttal phase, and feel that the authors satisfactorily addressed any remaining concerns through their rebuttals, particularly through a lengthy discussion with Reviewer BVSk, which clarified details of the problem setting.
Decision: Accept (poster)