证明了相关数据下自适应查询的上限天然受限，无法突破线性数量级。
Tight Bounds for Answering Adaptively Chosen Concentrated Queries
- 在集中查询框架下，限制查询集中在期望值附近
- 证明了自适应查询最多只能支持O(n)个，远低于独立数据时的O(n²)
- 提出简化版算法，与理论极限一致，适合关注数据相关性的研究者
大多数自适应数据分析工作假设数据样本相互独立。当允许样本间存在相关性时，即使非自适应设置也可能变得不可行，除非施加某些结构约束。Bassily和Freund（2016）提出了集中的查询框架，要求分析者仅使用围绕其期望值集中的查询。该假设使非自适应场景变得平凡，但在自适应场景中仍极具挑战性。事实上，目前所有已知算法在此框架下支持的查询数量远低于独立情况：对于大小为n的样本，最多支持O(n)个查询，而独立情况下可达O(n²)。本文证明，在当前集中查询框架下，这一效用差距是固有的，前提是算法满足某些自然条件。此外，我们给出了一个简化版的最佳已知算法，其性能与不可能性结果完全匹配。
原文摘要 · Abstract (English)
Most work on adaptive data analysis assumes that samples in the dataset are independent. When correlations are allowed, even the non-adaptive setting can become intractable, unless some structural constraints are imposed. To address this, Bassily and Freund [2016] introduced the elegant framework of concentrated queries, which requires the analyst to restrict itself to queries that are concentrated around their expected value. While this assumption makes the problem trivial in the non-adaptive setting, in the adaptive setting it remains quite challenging. In fact, all known algorithms in this framework support significantly fewer queries than in the independent case: At most $O(n)$ queries for a sample of size $n$, compared to $O(n^2)$ in the independent setting. In this work, we prove that this utility gap is inherent under the current formulation of the concentrated queries framework, assuming some natural conditions on the algorithm. Additionally, we present a simplified version of the best-known algorithms that match our impossibility result.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。