高密度分布における効率的適応データ分析

arXiv:2602.07732v1 Announce Type: new 要約: 現代のデータワークフローは本質的に適応的で、同じデータセットを繰り返しクエリすることで sequential 決定を-refine-および validation します。しかし、この適応性には過学習と無効な統計的推論をもたらす可能性があります。適応データ分析 (ADA) メカニズムはこの課題に対処しますが、計算効率とサンプル複雑性の間には根本的な緊張関係が存在します。$T$ 回の適応分析において、計算効率的なアルゴリズムは通常、最適ではない $O(\sqrt{T})$ のサンプル複雑性を受け入れますが、統計的に最適である $O(\log T)$ のアルゴリズムは、通常の暗号学的仮定の下では計算的に困難です。本研究では、このトレードオフの一端を明らかにし、計算効率性と最適サンプル複雑性の両方が実現可能なデータ分布の自然なクラスを特定しました。私たちが提案する計算効率的な ADA メカニズムは、既知の先验に対してデータ分布が密集している場合、最適である $O(\log T)$ のサンプル複雑性を達成します。この設定は、特に分布特異な学習に生じる特徴量 - ラベルデータ分布を含みます。結果として、私たちのメカニズムは、分布特異な設定におけるサンプル効率性（すなわち、$O(\log T)$ サンプル）を持つ統計クエリオーレルを也生み出します。さらに、私たちのアルゴリズムは微分プライバシーを基盤としておらず、代わりに既知の概念である述語単出 (PSO) 安全性（Cohen と Nissim, 2020）という緩和されたプライバシー概念を満たします。私たちの結果は、適応データ分析と、微分プライバシーを超えるプライバシーとの間に内在する接続を明らかにしています。

arXiv:2602.07732v1 Announce Type: new Abstract: Modern data workflows are inherently adaptive, repeatedly querying the same dataset to refine and validate sequential decisions, but such adaptivity can lead to overfitting and invalid statistical inference. Adaptive Data Analysis (ADA) mechanisms address this challenge; however, there is a fundamental tension between computational efficiency and sample complexity. For $T$ rounds of adaptive analysis, computationally efficient algorithms typically incur suboptimal $O(\sqrt{T})$ sample complexity, whereas statistically optimal $O(\log T)$ algorithms are computationally intractable under standard cryptographic assumptions. In this work, we shed light on this trade-off by identifying a natural class of data distributions under which both computational efficiency and optimal sample complexity are achievable. We propose a computationally efficient ADA mechanism that attains optimal $O(\log T)$ sample complexity when the data distribution is dense with respect to a known prior. This setting includes, in particular, feature--label data distributions arising in distribution-specific learning. As a consequence, our mechanism also yields a sample-efficient (i.e., $O(\log T)$ samples) statistical query oracle in the distribution-specific setting. Moreover, although our algorithm is not based on differential privacy, it satisfies a relaxed privacy notion known as Predicate Singling Out (PSO) security (Cohen and Nissim, 2020). Our results thus reveal an inherent connection between adaptive data analysis and privacy beyond differential privacy.