論文の概要: Is Randomness Necessary for Adaptive Data Analysis?

• arxiv url: http://arxiv.org/abs/2607.07085v1
• Date: Wed, 08 Jul 2026 07:17:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-09 22:50:30.313114
• Title: Is Randomness Necessary for Adaptive Data Analysis?
• Title（参考訳）: 適応データ分析にはランダム性が必要か?
• Authors: Edith Cohen, Haim Kaplan, Yishay Mansour, Shay Sapir, Uri Stemmer,
• Abstract要約: 非自明な数の適応クエリに答えるためには、ランダム性が厳密に必要であることを示す。 ADAに関する10年にわたる作業にもかかわらず、この問題は未解決のままである。
• 参考スコア（独自算出の注目度）: 54.49386214602422
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Adaptive Data Analysis (ADA) problem formalizes the challenge of preventing false discovery and overfitting when a dataset is repeatedly reused. Formally, our input is a dataset containing $n$ i.i.d. samples from an unknown distribution $\mathcal{P}$ over a domain $\mathcal{X}$, and our goal is to answer a sequence of $k$ adaptively chosen statistical queries with respect to $\mathcal{P}$. The main question is how many queries we can support (i.e., how large $k$ can be), primarily as a function of the number of samples $n$. This question has been intensively studied and is relatively well-understood for randomized mechanisms: there are computationally efficient mechanisms that support $k \approx n^2$ queries, and no computationally efficient mechanism can answer $k \gg n^2$ queries. In this paper, we address a fundamental question: is randomness necessary for ADA? Despite a decade of work on ADA, this question remains open. A folklore observation dating back to the initial works on ADA is that randomness is not necessary when the analyst is computationally bounded. Yet, the necessity of randomness against computationally unbounded analysts has remained elusive. Our main contribution resolves this gap in the information-theoretic Random Oracle model. Perhaps surprisingly, we show that randomness is strictly necessary to answer a non-trivial number of adaptive queries: when the analyst is unbounded, any deterministic mechanism can be forced to fail after just $k = \tilde{O} (n)$ queries.
• Abstract（参考訳）: Adaptive Data Analysis (ADA) 問題では,データセットの再利用を繰り返し実施する場合の誤検出や過度な適合を防止するという課題が定式化されている。 正式には、我々の入力は未知の分布である$\mathcal{P}$から$n$、すなわち$\mathcal{P}$のサンプルを含むデータセットであり、我々のゴールは、$\mathcal{P}$に関する$k$適応的に選択された統計的クエリのシーケンスに答えることである。 主な質問は、どれだけのクエリをサポートすることができるか(例えば、$k$がどれだけ大きいか)、主にサンプル数$n$の関数としてである。 この問題は集中的に研究され、ランダム化メカニズムに対して比較的よく理解されている:$k \approx n^2$クエリをサポートする計算効率の良いメカニズムがあり、$k \gg n^2$クエリに答える計算効率の良いメカニズムは存在しない。 本稿では、ADAにランダム性が必要なのかという根本的な疑問に対処する。 ADAに関する10年にわたる作業にもかかわらず、この問題は未解決のままである。 ADAに関する初期の研究にさかのぼる民俗学的観察は、アナリストが計算的に境界づけられている場合、ランダム性は必要ないということである。 しかし、計算的に非有界なアナリストに対するランダム性の必要性は、いまだ解明されていない。 私たちの主な貢献は、情報理論のRandom Oracleモデルにおけるこのギャップを解決することです。 アナリストが非有界な場合、任意の決定論的メカニズムは、単に$k = \tilde{O} (n)$クエリの後に失敗する可能性がある。

関連論文リスト

• Statistical and computational challenges in ranking [53.03724383992195]
  質問に対する回答の正しさに基づいて,専門家の能力に応じて$n$をランク付けする問題を考察する。 ここでは,この問題に対する統計的に最適かつ計算学的に効率的な手順の存在について検討する。
  論文  参考訳（メタデータ） (2025-12-24T11:18:06Z)
• Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph [45.975805184376036]
  局所的な差分プライバシーを満足するアルゴリズムを記述し、個人に対して$tildeO(k3/2)$非適応クエリを実行する。 また、Scheff'eグラフをダブする新しいオブジェクトを導入し、$Q$の分散間の差の構造をキャプチャする。
  論文  参考訳（メタデータ） (2025-09-19T17:41:15Z)
• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  我々は、2層完全連結ニューラルネットワーク上での符号勾配降下(SGD)による$k$スパースパリティ問題を解く。 このアプローチは、$d$次元ハイパーキューブ上での$k$スパースパリティ問題を効率的に解くことができることを示す。 次に、符号SGDを持つトレーニングニューラルネットワークが、この優れたネットワークを効果的に近似し、小さな統計的誤差で$k$-parity問題を解く方法を示す。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• Adaptive Data Analysis in a Balanced Adversarial Model [26.58630744414181]
  適応データ解析において、メカニズムは未知の分布から$n$、すなわち$D$のサンプルを取得し、正確な推定を行う必要がある。 我々は、それぞれが2つの分離されたアルゴリズムから構成されるアンフバランスドと呼ばれる、より制限された敵を考える。 これらの強い硬さの仮定は、計算的に有界なアンフバランス逆元が公開鍵暗号の存在を示唆するという意味では避けられないことを示す。
  論文  参考訳（メタデータ） (2023-05-24T15:08:05Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• An Algorithm for Learning Smaller Representations of Models With Scarce Data [0.0]
  本稿では,データセットが問題を完全に表現していない場合のバイナリ分類問題の解法を提案する。 我々のアルゴリズムは、基礎となる分布の支持にある多様体をホモロジーに再構成することで機能する。
  論文  参考訳（メタデータ） (2020-10-15T19:17:51Z)
• Conditional Uncorrelation and Efficient Non-approximate Subset Selection in Sparse Regression [72.84177488527398]
  相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。 提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
  論文  参考訳（メタデータ） (2020-09-08T20:32:26Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。