Adaptive Data Analysis for Growing Data

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.

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)

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

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$?

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

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

We'd like to clarify a few points regarding $n_0$:

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

• 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).

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?

We 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).

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

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.

These 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$.

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

We observe that the error does decrease marginally with increasing $b$ which is consistent with Fig 6.

The $\Delta_t$ variables seem redundant, and can be fixed to some single $\Delta$ by resealing the queries

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

Posterior distribution from line 169 is not defined in the body of the paper

This is defined on line 172 as $\mathcal{Q}_{\Pi}^{t} = \mathcal{P}^t | \Pi$. Please let us know if this is unclear.

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

$\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$.

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

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

Lemma 4.2 holds regardless of the clipping, so I recommend removing it from the statement

You'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".

Thank you for the detailed response.

I found the responses to most questions satisfactory.

I am still somewhat concerned with the confusion resulting from fixing $n_0=n/3$ in the experiment of Figure 3 (indeed, I meant 3, not 1). Besides my concern that it leads to a somewhat unfair comparison to JLNRSS, it also leads to an unnatural separation between the $b=1$ and $b>1$ settings. My recommendation would be to slightly change the experiment by issuing the queries at $b$ points each one after $n/b$ elements. This way the $b=1$ naturally becomes the static case.

Minor questions and comments:

1. My $n_0$ question was a matter of presentation. Of course, choosing to issue queries with small sample size would result in poor accuracy, but it seems like the results can be simply expressed in terms of the choices of the analyst as with the scheduling of the rest of the queries.
2. My proposal to avoid the usage of $\Delta_{t}$ results from the insight that accuracy $\alpha_{t}$ is actually measured in $\Delta_{t}$ units. Consider a process where the mechanism is wrapped by a preprocess step that scaled the query such that its sensitivity is $\Delta$, and a post process step that scales back the response. In this case, all queries share the same sensitivity, and the accuracy guarantees $\alpha_t$ which apply to the rescaled queries must be rescaled as well. In any case, this is just a presentation simplification proposal, nothing that matters to the content of the work.
3. Regarding Lemma 3.3, I suspect it is possible to change the sum over $t$ as introduced in eq. 13 and its consequent usage to be over the indexes where queries were issued, changing the probability terms to represent the sampling of all elements sampled between rounds, but I might very well be missing something. In any case, this will probably not have a significant effect on the results.

I will maintain my score, given the various phenomena in the empirical results which are not explained by the theory (though, do not contradict it, so I do not consider them a problem).

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.

Round-dependent standard deviation in experiments

We 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:

1. It simplifies the interpretation of the results: we can report the number of queries that can be answered at a fixed confidence width.

2. If we considered round-dependent confidence width $\alpha_t’$, we would need to make assumptions about the dependence that an analyst would find tolerable.

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?

The 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)$.

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

Checking what’s plotted in Fig 3, and suggestion to evaluate on an actual growing dataset and analyst.

You'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:

• Simulation results would be highly dependent on specific choices, potentially limiting their generalizability.
• Our theoretical analysis is necessary to understand the fundamental limits for any real setting.

Why not consider a round-dependent $\epsilon$?

While 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$:

$$\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)}$$

would no longer simplify nicely. This is why we opted for a round-dependent $\delta$ instead.

Appendix doesn’t detail how to do fully adaptive composition with time-varying delta, e.g. using Feldman and Zrnic (2021).

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

Budget only depends on time, but personalized DP supports budget that depends on the data from record themselves. Would individual accounting yield extra savings?

We'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).

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.

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?

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

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

We 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$.

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

We appreciate your suggestion and are happy to incorporate this discussion into the paper to clarify the distinctions between our work and previous approaches.

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?

In fact, our experiments do include the scenario you describe as an optimistic baseline. Specifically:

• The case where the analyst waits for the entire dataset corresponds to $b = 1$ in our experiments (see line 313 in the paper).

• In this case ($b = 1$), our bound and the tighter JLNRSS bound coincide, as shown in the last panel of Figure 3.

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

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

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.

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?

Theorem 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’$.

Our 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:

1. It simplifies the interpretation of the results: we can report the number of queries that can be answered at a fixed confidence width.

2. If we considered round-dependent confidence width $\alpha_t’$, we would need to make assumptions about the dependence that an analyst would find tolerable.