Tight Bounds for Answering Adaptively Chosen Concentrated Queries

Thank you for your thoughtful review. We will correct the typo you identified and expand on the motivation for considering adaptive queries in the next revision of our work.

> What would be the canonical distributions (beyond i.i.d.) that satisfy the concentration property? e.g. maybe finite-state Markov chains with a concentrated stationary distribution, or some martingales?

Any canonical distribution that is known to satisfy a concentration bound analogous to Hoeffding’s inequality for i.i.d. samples (e.g., Azuma’s inequality for martingales with bounded differences) would indeed satisfy the concentration property. Exploring such distributions, particularly those that naturally arise in real-world sampling scenarios, is a promising direction for future work. Many of these distributional structures provide stronger concentration guarantees than the general assumption used in this paper, while still relaxing the very strict i.i.d. assumption.

Thank you for your detailed and helpful review. We greatly appreciate the comprehensive suggestions and corrections regarding clarity, readability, and typos, and we will address them carefully in the revision.

> I fail to see the motivation to restrict the setting to noise addition mechanism. Maybe the authors would like to give some more background on this aspect? Was this a popular or most promising method to study before this work?

Noise-addition is a very popular approach, used both on its own and as a fundamental building block in many ADA algorithms. Our lower bound also applies to mechanisms that answer queries by evaluating them on random subsamples (this could be viewed as a form of a mean-zero noise addition mechanism; we will clarify this in the next revision). Thus, our lower bound shows that all known (efficient) techniques for answering a super-linear number of queries in the i.i.d. setting provably fail when correlations are present in the data. As we mentioned at the end of Section 1.1.1, our work steers future work to either impose additional structural assumptions on the problem or introduce fundamentally new algorithmic techniques.

> I am surprised to see the $O(n)$ v.s. $O(n^2)$ gap persists even if the queries are tightly concentrated as Hoeffding bound. Is there an intuitive explanation to why Hoeffiding bound is insufficient to support more queries in correlation setting? What other properties of i.i.d. setting are exploited to obtain the query result?

This is indeed a surprising result and one of the compelling insights of our paper. To gain intuition for this gap, consider first the simpler i.i.d. setting. A typical query in the i.i.d. scenario has a standard deviation on the order of $O(1/\sqrt(n))$. Thus, naively, to "hide" deviations in even a single query, one might expect to add noise of this magnitude. By leveraging advanced composition arguments from the literature of differential privacy, answering $k$ adaptive queries would therefore (naively) require noise on the order of $O(\sqrt(k)/\sqrt(n))$, limiting the number of queries $k$ to be linear in $n$. The key strength of differential privacy in the i.i.d. setting is that the magnitude of noise needed per query only needs to "hide" every single sample point, which translates to significantly less noise than the standard deviation. This is what enables answering a super-linear number of adaptive queries in the i.i.d. setting. However, our result shows that once correlations are introduced—even with queries that satisfy strong concentration properties— this advantage disappears. In other words, when correlations are present in the data, our results show that (in general) one must add noise of the order of the standard deviation, and that "hiding" every single sample point is insufficient.

Thank you for your constructive review and helpful suggestions.

> The fact that the lower bound only holds for a certain special case of mechanisms could be considered a weakness.

Our lower bound is indeed limited to noise-addition mechanisms. At the same time, noise-addition mechanisms remain a broad and important class, used both on their own and also as key building blocks in many ADA mechanisms. Our lower bound also applies to mechanisms that answer queries by evaluating them on random subsamples (this could be viewed as a form of a mean-zero noise addition mechanism; we will clarify this in the next revision). Thus, our lower bound shows that all known (efficient) techniques for answering a super-linear number of queries in the i.i.d. setting provably fail when correlations are present in the data. As we mentioned at the end of Section 1.1.1, our work steers future work to either impose additional structural assumptions on the problem or introduce fundamentally new algorithmic techniques.

> It feels like the presentation could be improved a bit by providing a natural example and explaining what the different objects represent in the example.

Thank you for this suggestion; we will try to make the introduction of the general setting more accessible and will also correct the typos you noted in the next revision of our work.

> Instead of limiting the types of queries made by the analyst, what if one relaxes the independence assumption a bit? Are there known bounds for this problem quantified in terms of "how independent" the samples are guaranteed to be?

This is indeed a promising direction for future work. One recent work (Kontorovich et al., 2022) addresses this setting, where the bound depends on a measure of the distance between the underlying distribution and a product distribution. To the best of our knowledge, no other results directly address these questions. Further investigation of this problem, particularly for distributional structures that naturally arise in sampling scenarios and have practical applications, would be a valuable direction for future research.

Thank you for your helpful suggestions and for pointing out the typo; we will address these in the next revision of our work.

> What is known about algorithms which do not fall into the class of "noise-additive" algorithms?

Currently there are two known techniques for (efficiently) answering adaptive queries when correlations are present in the data:

(1) Noise addition. With correlations, all existing noise-addition mechanisms support at most $O(n)$ queries. We show that this is a barrier one cannot cross, despite the fact that, in the i.i.d. setting, noise addition supports up to $O(n^2)$ queries.

(2) Transcript compression. Another technique for efficiently answering $O(n)$ queries when correlations are present is based on "transcript compression" (a.k.a. "Bounded description length"). But this technique only answers $O(n)$ queries even in the i.i.d. setting, and so one should not expect it to support a super-linear number of queries in the correlated case.

Our lower bound also applies to mechanisms that answer queries by evaluating them on random subsamples (this could be viewed as a form of a mean-zero noise addition mechanism; we will clarify this in the next revision). Together, our lower bound shows that all known (efficient) techniques for answering a super-linear number of queries in the iid setting provably fail when correlations are present in the data.

> Are there natural weaker or incomparable restrictions of the allowable queries which may allow stronger positive results?

One natural direction for future work is to consider queries satisfying stronger concentration constraints, such as sub-gaussian queries. Another promising direction—potentially more applicable to natural scenarios—would be to impose stronger structural constraints on the underlying data distribution, while still relaxing the strict i.i.d. assumption.

Thank you very much for your thorough review. We appreciate your thoughtful comments and will try to address your concerns in turn.

> The lower bound applies only for mechanisms that operate by adding independent noise to a sample average -- there is no specific reason why a mechanism needs to operate this way, so it would be much more interesting to see a more general lower bound.

Our lower bound is indeed limited to noise-addition mechanisms. At the same time, noise-addition mechanisms remain a broad and important class, used both on their own and also as key building blocks in many ADA mechanisms. Our lower bound also applies to mechanisms that answer queries by evaluating them on random subsamples (this could be viewed as a form of a mean-zero noise addition mechanism; we will clarify this in the next revision). Thus, our lower bound shows that all known (efficient) techniques for answering a super-linear number of queries in the i.i.d. setting provably fail when correlations are present in the data. As we mentioned at the end of Section 1.1.1, our work steers future work to either impose additional structural assumptions on the problem or introduce fundamentally new algorithmic techniques. Together with our simplified (and improved) positive results, we view this as telling a compelling story.

> This lower bound is not as surprising, since the concentrated queries assumption is extremely weak... When the dataset is given by i.i.d. samples, the random variable $q(D)$ is $1/\sqrt{n}$ subgaussian. Would a strengthening of the conditions to one of this form be enough to obtain an improved upper bound?

The weakness of the concentration assumptions is indeed a limitation of the framework (as our results highlight through the lower bound). We agree that it would be interesting to strengthen these assumptions or to focus on specific distribution structures that arise in practice. We hope our work provides a starting point for future work along these lines. Your suggestion about requiring concentration for every value of $\varepsilon$ is particularly interesting. While we do not answer this question, our attack and analysis offer some initial insight: due to the tradeoff between $\varepsilon$ and $\gamma_{\rm \scriptsize{Hoeffding}}$​ one can take $\varepsilon^{\*}=O(1/\sqrt(n))$ and proceed with the same construction and information-gathering rounds (since in that regime for any smaller values of $\varepsilon$, $\gamma_{\rm \scriptsize{Hoeffding}} >1$, thus our information gathering queries remain concentrated for any value of $\varepsilon$). This implies that data leakage—and therefore membership inference and even full reconstruction of the true sample —remains possible at the rate $\tilde{O}(1/{\varepsilon^{\*}}^2)$. What changes under the stricter requirement is that the final query that "overfits" the dataset would no longer be allowed, as it is not concentrated relative to every value of $\varepsilon$. We hope that such observations could provide useful intuition for future work along the lines of the stronger setting you suggest.

> The mechanism only slightly improves parameters over the original Bassily and Fruend algorithm.

It is true that, quantitatively, our upper bound only slightly improves the previous upper bound. But the analysis is substantially simpler, which we view as an important contribution of our work. We stress that while our analysis is simpler, it does not follow from a direct application of the generalization properties of DP to our setting, as is done in the i.i.d. case, and requires our use of the thought experiment of the "three worlds" described in Section 1.1.4.

> One striking gap is that throughout the paper, it seems that it is never formally stated what is supposed to mean that the lower bound rules out any mechanism that operated by adding "any noise"... it is assumed that the outputs are clipped...

The definition of "noise addition mechanisms" is stated in lines 99-101. We meant mechanisms that answer each query using the exact empirical average, after adding to it random mean-zero noise (independent of the previous noises). We will clarify this further in the body of the paper.

Since queries are bounded in [0,1], any response outside the range of [-1,2] would already violate the accuracy requirement. In other words, if an answer falls outside of the interval [-1,2] then the mechanism fails and we (the attacker) win. Thus, in the proof of the lower bound we allowed ourselves to assume that the answers are always in the range [-1,2]. We agree that the terminology we used about this can be made more precise, and we will restate this in the next revision of our paper.