論文の概要: Tight Bounds for Answering Adaptively Chosen Concentrated Queries

• arxiv url: http://arxiv.org/abs/2507.13700v1
• Date: Fri, 18 Jul 2025 07:08:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-21 20:43:26.202825
• Title: Tight Bounds for Answering Adaptively Chosen Concentrated Queries
• Title（参考訳）: アダプティブ・チョーゼン濃縮クエリーに対するタイトバウンド
• Authors: Emma Rapoport, Edith Cohen, Uri Stemmer,
• Abstract要約: 本研究では、このユーティリティギャップが、集中クエリフレームワークの現在の定式化に固有のものであることを実証する。 我々は、最もよく知られたアルゴリズムの単純化版を提示する。
• 参考スコア（独自算出の注目度）: 24.243931410934323
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.
• Abstract（参考訳）: 適応データ分析に関するほとんどの研究は、データセットのサンプルが独立していると仮定している。 相関が許されると、いくつかの構造的制約が課せられない限り、非適応的な設定でさえ難解になる。 これに対処するため、Bassily氏とFreund氏は2016年に、集中クエリのエレガントなフレームワークを紹介した。 この仮定は、非適応的な設定では問題を簡単にするが、適応的な設定では、かなり難しいままである。 実際、このフレームワークのすべての既知のアルゴリズムは、独立したケースよりもはるかに少ないクエリをサポートしている: 独立の環境では、$O(n^2)$に対して、$n$のサンプルに対して、ほとんどの$O(n)$クエリは、独立の環境で$O(n^2)$である。 本研究では,このユーティリティギャップが,アルゴリズムの自然な条件を前提として,現在の集中クエリフレームワークの定式化に固有のものであることを証明した。 さらに、最もよく知られたアルゴリズムの単純化版を提示する。

関連論文リスト

• T$^2$: An Adaptive Test-Time Scaling Strategy for Contextual Question Answering [49.5489716597489]
  T$2$: Think-to-Thinkは質問の複雑さに基づいて推論深度を動的に適応する新しいフレームワークである。 T$2$は、質問を構造的要素に分解し、候補推論戦略と同じような例を生成し、これらの戦略を複数の基準に対して評価し、元の質問に最も適切な戦略を適用する、という4つの重要なステップで機能する。
  論文  参考訳（メタデータ） (2025-05-23T03:18:02Z)
• Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
  Retrieval-augmented Large Language Models (LLMs) は、質問回答(QA)のようなタスクにおける応答精度を高めるための有望なアプローチとして登場した。 本稿では,クエリの複雑さに基づいて,LLMの最適戦略を動的に選択できる適応型QAフレームワークを提案する。 オープンドメインのQAデータセットを用いて、複数のクエリの複雑さを網羅し、QAシステムの全体的な効率性と精度を高めることを示す。
  論文  参考訳（メタデータ） (2024-03-21T13:52:30Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity [16.331196225467707]
  強化学習におけるサンプル効率と適応性の関係を理論的に検討する。 私たちは、バッチ毎にフィードバックが処理され、クエリが更新されるように、クエリをK$のバッチで送信できる学習フレームワークを採用しています。
  論文  参考訳（メタデータ） (2023-10-02T20:14:01Z)
• Subsampling Suffices for Adaptive Data Analysis [8.231050911072755]
  ほとんどの古典的なテクニックは、データセットがアナリストのクエリとは独立していると仮定し、データセットが複数の適応的に選択されたクエリのために再利用される一般的な設定に分解する。 クエリが適応的に選択された場合でも、クエリが引き続き表現されるという、非常に単純な仮定のセットを特定します。 このサブサンプルベースのフレームワークの単純さにより、以前の作業でカバーされていないさまざまな現実世界のシナリオをモデル化することができる。
  論文  参考訳（メタデータ） (2023-02-17T02:47:54Z)
• How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
  機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。 本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。 さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
  論文  参考訳（メタデータ） (2021-10-05T20:15:35Z)
• Generalization in the Face of Adaptivity: A Bayesian Perspective [3.0202264016476623]
  適応的に選択されたクエリによるデータサンプルの繰り返し使用は、急速に過度な適合につながる可能性がある。 単純なノイズアンバウンド付加アルゴリズムは、この問題を防ぐのに十分であることがわかった。 提案手法では, 過去のクエリに対する応答にデータサンプルに関する情報がどの程度エンコードされたか, ベイズ因子と新しいクエリの共分散から適応性の害が生じることを示す。
  論文  参考訳（メタデータ） (2021-06-20T22:06:44Z)
• Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments [55.24895403089543]
  ドメインの一般化は、限られた数のトレーニング環境からのデータで、目に見えないテスト環境でうまく機能することを目的としています。 我々は,O(logd_s)$環境のみを見た後に一般化する予測器を高確率で生成することを保証する反復的特徴マッチングに基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-18T04:39:19Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Distributionally Robust Weighted $k$-Nearest Neighbors [21.537952410507483]
  少数のサンプルから堅牢な分類器を学ぶことは、マシンラーニングにおける重要な課題である。 本稿では, 重み付き$k$-アネレスト近傍のミニマックス分布に頑健な定式化について検討する。 我々は,この関数最適化問題を効率的に解くアルゴリズムである textttDr.k-NN を開発した。
  論文  参考訳（メタデータ） (2020-06-07T00:34:33Z)

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

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