論文の概要: Sample-Adaptivity Tradeoff in On-Demand Sampling

• arxiv url: http://arxiv.org/abs/2511.15507v1
• Date: Wed, 19 Nov 2025 14:59:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-20 15:51:28.857795
• Title: Sample-Adaptivity Tradeoff in On-Demand Sampling
• Title（参考訳）: オンデマンドサンプリングにおけるサンプル適応性トレードオフ
• Authors: Nika Haghtalab, Omar Montasser, Mingda Qiao,
• Abstract要約: オンデマンドサンプリングにおけるサンプル複雑性とラウンド複雑性のトレードオフについて検討し、学習アルゴリズムは限られたラウンド数で$k$分布から適応的にサンプルをサンプリングする。 我々は,$widetilde O((d + k) / 2)$を$widetilde O(sqrtk)$ラウンド内で,ほぼ最適なサンプル複雑性を実現するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 27.212536031930643
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the tradeoff between sample complexity and round complexity in on-demand sampling, where the learning algorithm adaptively samples from $k$ distributions over a limited number of rounds. In the realizable setting of Multi-Distribution Learning (MDL), we show that the optimal sample complexity of an $r$-round algorithm scales approximately as $dk^{Θ(1/r)} / ε$. For the general agnostic case, we present an algorithm that achieves near-optimal sample complexity of $\widetilde O((d + k) / ε^2)$ within $\widetilde O(\sqrt{k})$ rounds. Of independent interest, we introduce a new framework, Optimization via On-Demand Sampling (OODS), which abstracts the sample-adaptivity tradeoff and captures most existing MDL algorithms. We establish nearly tight bounds on the round complexity in the OODS setting. The upper bounds directly yield the $\widetilde O(\sqrt{k})$-round algorithm for agnostic MDL, while the lower bounds imply that achieving sub-polynomial round complexity would require fundamentally new techniques that bypass the inherent hardness of OODS.
• Abstract（参考訳）: オンデマンドサンプリングにおけるサンプル複雑性とラウンド複雑性のトレードオフについて検討し、学習アルゴリズムは限られたラウンド数で$k$分布から適応的にサンプルをサンプリングする。 MDL(Multi-Distribution Learning)では、$r$ラウンドアルゴリズムの最適なサンプル複雑性が、約$dk^{*(1/r)} / ε$とスケールできることが示されている。 一般の非依存の場合には、$\widetilde O((d + k) / ε^2)$を$\widetilde O(\sqrt{k})$ラウンド内で、ほぼ最適サンプル複雑性を達成するアルゴリズムを提案する。 そこで我々は,サンプル適応性トレードオフを抽象化し,既存のMDLアルゴリズムの多くをキャプチャする,On-Demand Smpling (OODS) による最適化という新しいフレームワークを導入する。 OODSの設定において、ラウンドの複雑さにほぼ厳密な境界を定めています。 上界は、非依存的MDLに対して$\widetilde O(\sqrt{k})$-roundアルゴリズムを直接生成するが、下界は、サブポリノミカルなラウンド複雑性を達成するためには、OODSの本質的な硬さをバイパスする根本的な新しい技術が必要であることを暗示している。

関連論文リスト

• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。 我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
  論文  参考訳（メタデータ） (2023-06-28T16:33:39Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。 我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
  論文  参考訳（メタデータ） (2022-06-07T16:49:54Z)
• Rejection sampling from shape-constrained distributions in sublinear time [14.18847457501901]
  離散分布の様々なクラスを対象としたミニマックスフレームワークにおいて,リジェクションサンプリングのクエリ複雑性について検討した。 本研究は,アルファベットサイズに比例して複雑度が増大するサンプリングのための新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-29T01:00:42Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning [123.69175280309226]
  オンライン強化学習(RL)における課題の1つは、エージェントがその振る舞いを最適化するために、環境の探索とサンプルの活用をトレードオフする必要があることである。 1) 生成モデル(環境のスパースシミュレータなど)にアクセス可能な状態のサンプル数を規定する「対象別」アルゴリズム,2) 所定のサンプルをできるだけ早く生成する「対象別」サンプル収集。
  論文  参考訳（メタデータ） (2020-07-13T15:17:35Z)

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

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