論文の概要: Optimal Multi-Distribution Learning
- arxiv url: http://arxiv.org/abs/2312.05134v2
- Date: Sat, 20 Jan 2024 17:04:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-23 19:51:46.040086
- Title: Optimal Multi-Distribution Learning
- Title(参考訳): 最適マルチディストリビューション学習
- Authors: Zihan Zhang, Wenhao Zhan, Yuxin Chen, Simon S. Du, Jason D. Lee
- Abstract要約: マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では,$(d+k)/varepsilon2$の順に,サンプルの複雑さを伴って,$varepsilon$-optimal randomized hypothesisを生成するアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 94.73322179348332
- 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 have been 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, unveiling a large
sample size barrier when only deterministic hypotheses are permitted. These
findings successfully resolve three open problems presented in COLT 2023 (i.e.,
Awasthi et al., (2023, Problem 1, 3 and 4)).
- Abstract(参考訳): 分散学習(mdl、multi-distribution learning)は、k$の異なるデータ分散間で最悪のリスクを最小限に抑える共有モデルを目指しているが、ロバスト性、公平性、マルチグループコラボレーションといった進化する需要に応えて、統一されたフレームワークとして登場した。
データ効率のよいMDLを実現するには、学習プロセス全体を通じて適応サンプリング(オンデマンドサンプリングとも呼ばれる)が必要である。
しかし, 最適標本の複雑性には, 最先端の上限と下限のギャップが存在する。
Vapnik-Chervonenkis (VC) 次元 $d$ の仮説クラスに焦点をあて、最もよく知られた下界と一致する$(d+k)/\varepsilon^2$ (modulo some logarithmic factor) の順にサンプル複雑性を持つ $varepsilon$-optimal randomized hypothesis を生成する新しいアルゴリズムを提案する。
我々のアルゴリズムのアイデアと理論はラデマッハクラスに対応するためにさらに拡張されている。
提案アルゴリズムはオラクル効率が良く、経験的リスク最小化オラクルを通してのみ仮説クラスにアクセスする。
さらにランダム化の必要性を確立し,決定論的仮説のみを許容した場合に,大きなサンプルサイズバリアを明らかにする。
これらの結果は、COLT 2023(Awasthi et al., 2023, Problem 1, 3 and 4)で示された3つのオープンな問題を解決した。
関連論文リスト
- Comparative Learning: A Sample Complexity Theory for Two Hypothesis
Classes [5.194264506657145]
比較学習は、PAC学習における実現可能な設定と不可知な設定の組み合わせとして導入する。
たとえ$S$と$B$が無限のVC次元を持つとしても、比較学習の複雑さは小さい。
比較学習のサンプルの複雑さは、相互VC次元$mathsfVC(S,B)$によって特徴づけられる。
論文 参考訳(メタデータ) (2022-11-16T18:38:24Z) - On-Demand Sampling: Learning Optimally from Multiple Distributions [87.09946206044332]
社会的・現実世界の考察は、協調的、集団的分布的堅牢性、公正な連合学習など、多分野の学習パラダイムを生み出している。
本稿では、これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
私たちのアルゴリズムの設計と分析は、プレイヤーの安価なワンオフサンプルやより高価な再利用可能なサンプルへのアクセスをトレードオフできるミラー・ダイスンの拡張によって実現されます。
論文 参考訳(メタデータ) (2022-10-22T19:07:26Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳(メタデータ) (2021-10-09T21:13:48Z) - 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) - Pareto Optimal Model Selection in Linear Bandits [15.85873315624132]
本研究では,学習者が最適仮説クラスの次元に適応しなければならない線形帯域設定におけるモデル選択問題について検討する。
本稿では,まず,固定アクション集合であっても,未知の内在次元$d_star$ への適応がコスト的に現れることを示す下限を定式化する。
論文 参考訳(メタデータ) (2021-02-12T16:02:06Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳(メタデータ) (2020-07-15T03:25: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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。