Summary
This paper explores the problem of adaptive data analysis - when a single dataset is repeatedly used for adaptively chosen queries, overfitting can occur rapidly. To reduce this bias, a popular approach is to add noise to the output of each query. Intuitively, this prevents the analyst from learning too much about the sample and thus prevents them from choosing a query that overfits the sample.
The most common technique used to analyze this adaptive setting is differential privacy. However, the worst-case nature of DP requires scaling the noise to a worst-case dataset, rather than a typical dataset. The paper's contributions are:
1) Prior work has shown that (roughly speaking), to ensure that the query responses are low bias, it suffices to show the responses have "posterior accuracy." This paper shows that posterior accuracy can be thought of as the correlation between the query asked and a Bayes factor.
2) They introduce a new notion of stability (pairwise concentration). Roughly speaking, stability measures (like DP) measure how much an algorithm's output depends on its input and have long been used to analyze mechanisms for adaptive data analysis. Pairwise concentration crucially depends on the dataset and query, to avoid the worst-case requirements of DP. Using this new notion of stability, they bounded the variance of the Bayes factor introduced in the previous point, which in particular bounds the correlation between it and the query asked. As a result, this new notion of stability can be used to prove generalization guarantees.
3) Using pairwise concentration, they show that it suffices to add noise that scales with the standard deviation of each query.
For 3), a similar result was shown by [Feldman and Steinke 18]. However, [FS 18's] result is weaker than this paper in two ways. First, it only holds in expectation over the error, whereas this paper's guarantee holds with extremely high probability (the difference is equivalent to Markov's vs Chernoff-style bounds). Second, this paper can handle subgaussian queries with unbounded ranges, whereas it's unclear if [FS 18] can handle unbounded ranges.
Strengths
Within the field of adaptive data analysis, the authors give a refined answer to a simple question: What happens if we scale the noise of our answers to the standard deviation of the query? Prior work of [FS 18] suggested this approach can work, but were only able to prove that the error is bounded in expectation. This paper shows the error is bounded with high probability and also extends to unbounded but subgaussian queries.
I'm also excited by the new notion of stability (pairwise concentration) introduced in this paper and hopeful that it can be applied in other settings (for instant, to analyze other mechanisms).
Along the way, the authors introduce a number of perspectives and new tools that may be more broadly applicable. For example, they introduce a number of "dissimilarity" measures, which provide more expressive ways to measure how dissimilar two distributions are than classical notions of divergence.
Weaknesses
The definition of pairwise concentration and its application (in Theorem 4.5) are technically complex. One way for this work to be impactful is for pairwise concentration to be applied more broadly, and providing a simple interface to it would aid that. For example:
1) In Theorem 4.5, I believe you only ever need to bound the pairwise concentration by datasets that differ in one point (via the function $\psi(x,y;v)$ defined on line 291). If so, I would explicitly state that (ideally early) as this would make it easier for someone else to apply your framework.
2) Also in Theorem 4.5, is there ever a reason (up to a small constant) to not set $\xi = \epsilon^2$? It seems to me the probability bound is monotonically decreasing in both $\xi$ and $\epsilon$, in which case setting both $\xi$ and $\epsilon^2$ to the maximum of the two will only improve the error probability, and affect the deviation bounded by at most a factor of $\sqrt{2}$. If so, my (personal) preference is that it's better to state a simpler version losing that $\sqrt{2}$ and defer more detailed versions to the appendix.
Another minor point: This paper's mechanism assumes it knows the standard deviation of each query. The work of [FS 18] is able to estimate the standard deviation of each query and scale the noise on the fly. Can your analysis handle a similar approach?
Questions
I'm a bit confused about the regime where $\alpha < 1$ in Definition 4.2 and Fact B.7. In Fact B.7, I believe the $\leq$ should be converted to a $\geq$ in this setting because the righthand side becomes decreasing with $\phi$. For Definition 4.2, do you similarly want the direction to depend on whether $(\alpha - 1)$ is positive? That would align with the intuition that $\varphi$ is an upper bound on some notion of ``distance" between $s$ and $s'$. The way it's written, we need $\varphi$ to be an upper bound on this distance when $\alpha > 1$ and a lower bound when $0 \leq \alpha < 1$.
Line 731 typo "ration"-> "ratio"
See also the questions from the Weaknesses section.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
Yes - all assumptions/theorem statements are clear, and the discussion includes some future directions that the present work does not address.