論文の概要: On-Demand Sampling: Learning Optimally from Multiple Distributions
- arxiv url: http://arxiv.org/abs/2210.12529v3
- Date: Tue, 2 Apr 2024 22:48:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-04 23:57:15.396344
- Title: On-Demand Sampling: Learning Optimally from Multiple Distributions
- Title(参考訳): オンデマンドサンプリング:複数分布から最適学習
- Authors: Nika Haghtalab, Michael I. Jordan, Eric Zhao,
- Abstract要約: 社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。
これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
- 参考スコア(独自算出の注目度): 63.20009081099896
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Social and real-world considerations such as robustness, fairness, social welfare and multi-agent tradeoffs have given rise to multi-distribution learning paradigms, such as collaborative learning, group distributionally robust optimization, and fair federated learning. In each of these settings, a learner seeks to uniformly minimize its expected loss over $n$ predefined data distributions, while using as few samples as possible. In this paper, we establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Importantly, our sample complexity bounds for multi-distribution learning exceed that of learning a single distribution by only an additive factor of $n \log(n) / \epsilon^2$. This improves upon the best known sample complexity bounds for fair federated learning by Mohri et al. and collaborative learning by Nguyen and Zakynthinou by multiplicative factors of $n$ and $\log(n)/\epsilon^3$, respectively. We also provide the first sample complexity bounds for the group DRO objective of Sagawa et al. To guarantee these optimal sample complexity bounds, our algorithms learn to sample from data distributions on demand. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving stochastic zero-sum games. In particular, we contribute stochastic variants of no-regret dynamics that can trade off between players' differing sampling costs.
- Abstract(参考訳): 堅牢性、公正性、社会福祉、マルチエージェントのトレードオフといった社会的および現実世界の考察は、協調学習、グループ分散的ロバストな最適化、公正なフェデレーション付き学習などの多分散学習パラダイムを生み出している。
これらの設定それぞれにおいて、学習者は、可能な限り少数のサンプルを使用しながら、予測される損失を$n$以上のデータ分散で均一に最小化する。
本稿では、これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
重要なことは、我々のサンプルの複雑さは、n \log(n) / \epsilon^2$の加法的因子だけで1つの分布を学習する限界を超えている。
これは、Mohriらによるフェアフェデレーション学習と、Nguyen と Zakynthinou による協調学習において、それぞれ$n$ と $\log(n)/\epsilon^3$ の乗算因子によって、最もよく知られたサンプル複雑性境界を改善している。
また、佐川らによるグループDRO目標に対する最初のサンプル複雑性境界も提供し、これらの最適なサンプル複雑性境界を保証するため、我々のアルゴリズムは要求に応じてデータ分布からサンプルを学習する。
我々のアルゴリズムの設計と解析は、確率ゼロサムゲームを解決するためのオンライン学習手法の拡張によって実現されている。
特に,プレイヤーの異なるサンプリングコストのトレードオフが可能な非回帰力学の確率的変種に寄与する。
関連論文リスト
- Optimal Multi-Distribution Learning [94.73322179348332]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では,$(d+k)/varepsilon2$の順に,サンプルの複雑さを伴って,$varepsilon$-optimal randomized hypothesisを生成するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-12-08T16:06:29Z) - The sample complexity of multi-distribution learning [17.45683822446751]
サンプル複雑性$widetildeO((d+k)epsilon-2) cdot (k/epsilon)o(1)$は、Awasthi, Haghtalab, Zhao の COLT 2023 開放問題を解く。
論文 参考訳(メタデータ) (2023-12-07T03:53:17Z) - 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 [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳(メタデータ) (2023-02-18T09:24:15Z) - A Moment-Matching Approach to Testable Learning and a New
Characterization of Rademacher Complexity [15.746613321517282]
我々は、モーメントマッチングやメートル法非依存のツールを用いて、テスト可能な学習アルゴリズムを開発するための強力な新しいアプローチを提案する。
意外なことに、テスト可能な学習における情報理論の複雑さは、概念クラスのRademacher複雑さによって強く特徴づけられている。
論文 参考訳(メタデータ) (2022-11-23T21:29:51Z) - Sample Complexity Bounds for Robustly Learning Decision Lists against
Evasion Attacks [25.832511407411637]
敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。
我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。
すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
論文 参考訳(メタデータ) (2022-05-12T14:40:18Z) - The Sample Complexity of Distribution-Free Parity Learning in the Robust
Shuffle Model [11.821892196198457]
我々は$d$-bitパリティ関数の学習のサンプル複雑さが$Omega (2d/2)$であることを示した。
また、単純なシャッフルモデルプロトコルをスケッチし、その結果が$poly(d)$ factorにきついことを示す。
論文 参考訳(メタデータ) (2021-03-29T15:26:02Z) - 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) - A Provably Efficient Sample Collection Strategy for Reinforcement
Learning [123.69175280309226]
オンライン強化学習(RL)における課題の1つは、エージェントがその振る舞いを最適化するために、環境の探索とサンプルの活用をトレードオフする必要があることである。
1) 生成モデル(環境のスパースシミュレータなど)にアクセス可能な状態のサンプル数を規定する「対象別」アルゴリズム,2) 所定のサンプルをできるだけ早く生成する「対象別」サンプル収集。
論文 参考訳(メタデータ) (2020-07-13T15:17:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。