論文の概要: Optimal Multi-Distribution Learning

• arxiv url: http://arxiv.org/abs/2312.05134v4
• Date: Thu, 23 May 2024 16:28:21 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-26 19:54:19.238282
• Title: Optimal Multi-Distribution Learning
• Title（参考訳）: 最適マルチディストリビューション学習
• Authors: Zihan Zhang, Wenhao Zhan, Yuxin Chen, Simon S. Du, Jason D. Lee,
• Abstract要約: マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 88.3008613028333
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-distribution learning (MDL), which seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions, has emerged as a unified framework in response to the evolving demand for robustness, fairness, multi-group collaboration, etc. Achieving data-efficient MDL necessitates adaptive sampling, also called on-demand sampling, throughout the learning process. However, there exist substantial gaps between the state-of-the-art upper and lower bounds on the optimal sample complexity. Focusing on a hypothesis class of Vapnik-Chervonenkis (VC) dimension d, we propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon^2 (modulo some logarithmic factor), matching the best-known lower bound. Our algorithmic ideas and theory are further extended to accommodate Rademacher classes. The proposed algorithms are oracle-efficient, which access the hypothesis class solely through an empirical risk minimization oracle. Additionally, we establish the necessity of randomization, revealing a large sample size barrier when only deterministic hypotheses are permitted. These findings resolve three open problems presented in COLT 2023 (i.e., citet[Problems 1, 3 and 4]{awasthi2023sample}).
• Abstract（参考訳）: MDL(Multi-distriion Learning)は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目的として、ロバストネス、フェアネス、マルチグループコラボレーションなどに対する需要の高まりに対応する統一されたフレームワークとして登場した。 データ効率のよいMDLを実現するには、学習プロセス全体を通じて適応サンプリング(オンデマンドサンプリングとも呼ばれる)が必要である。 しかし、最適なサンプルの複雑さについて、最先端の上境界と下限の間にはかなりのギャップがある。 Vapnik-Chervonenkis (VC) 次元 d の仮説クラスに焦点をあて、(d+k)/varepsilon^2 (modulo some logarithmic factor) の順にサンプル複雑性を持つヴァレプシロン最適ランダム化仮説を導出し、最もよく知られた下界と一致する新しいアルゴリズムを提案する。 我々のアルゴリズムの考えと理論はさらに拡張され、ラデマッハ類に適合する。 提案したアルゴリズムはオラクル効率が良く、経験的リスク最小化オラクルを通してのみ仮説クラスにアクセスする。 さらに、ランダム化の必要性を確立し、決定論的仮説のみを許す場合、大きなサンプルサイズ障壁を明らかにする。 これらの結果は、COLT 2023で提示された3つのオープンな問題を解決している(citet[Problems 1, 3 and 4]{awasthi2023sample})。

関連論文リスト

• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。 データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-16T04:32:22Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Optimal PAC Bounds Without Uniform Convergence [11.125968799758436]
  我々は、一様収束論の極限を超えるフレームワークを通して、最適な高確率リスク境界を提供する。 我々のフレームワークは、置換不変予測器の残余誤差を高い確率リスク境界に変換する。 具体的には, 1-inclusion graph アルゴリズムの特定のアグリゲーションが最適であることを示す。
  論文  参考訳（メタデータ） (2023-04-18T17:57:31Z)
• Supervised Multivariate Learning with Simultaneous Feature Auto-grouping and Dimension Reduction [7.093830786026851]
  本稿では,クラスタ化低ランク学習フレームワークを提案する。 2つの合同行列正則化を課し、予測因子を構成する特徴を自動的にグループ化する。 低ランクなモデリングよりも解釈可能であり、変数選択における厳密な空間性仮定を緩和する。
  論文  参考訳（メタデータ） (2021-12-17T20:11:20Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。 局所探索のための政策勾配は、しばしばランダムな摂動から得られる。 目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-06-22T16:07:02Z)
• Improved Algorithms for Agnostic Pool-based Active Classification [20.12178157010804]
  プールに依存しない環境でのバイナリ分類のためのアクティブラーニングを検討する。 我々のアルゴリズムは、画像分類データセットにおけるアートアクティブな学習アルゴリズムの状況よりも優れている。
  論文  参考訳（メタデータ） (2021-05-13T18:24:30Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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