論文の概要: On-Demand Sampling: Learning Optimally from Multiple Distributions

• arxiv url: http://arxiv.org/abs/2210.12529v1
• Date: Sat, 22 Oct 2022 19:07:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-25 21:37:16.411210
• Title: On-Demand Sampling: Learning Optimally from Multiple Distributions
• Title（参考訳）: オンデマンドサンプリング:複数分布から最適学習
• Authors: Nika Haghtalab and Michael I. Jordan and Eric Zhao
• Abstract要約: 社会的・現実世界の考察は、協調的、集団的分布的堅牢性、公正な連合学習など、多分野の学習パラダイムを生み出している。 本稿では、これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 私たちのアルゴリズムの設計と分析は、プレイヤーの安価なワンオフサンプルやより高価な再利用可能なサンプルへのアクセスをトレードオフできるミラー・ダイスンの拡張によって実現されます。
• 参考スコア（独自算出の注目度）: 87.09946206044332
• 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, group distributionally robust, and fair federated learning. In each of these settings, a learner seeks to minimize its worst-case loss over a set of $n$ predefined 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 exceed that of the sample complexity of learning a single distribution only by an additive factor of $n \log(n) / \epsilon^2$. These improve upon the best known sample complexity of agnostic federated learning by Mohri et al. by a multiplicative factor of $n$, the sample complexity of collaborative learning by Nguyen and Zakynthinou by a multiplicative factor $\log n / \epsilon^3$, and give the first sample complexity bounds for the group DRO objective of Sagawa et al. To achieve optimal sample complexity, our algorithms learn to sample and learn from distributions on demand. Our algorithm design and analysis is enabled by our extensions of stochastic optimization techniques for solving stochastic zero-sum games. In particular, we contribute variants of Stochastic Mirror Descent that can trade off between players' access to cheap one-off samples or more expensive reusable ones.
• Abstract（参考訳）: 堅牢性、公平性、社会福祉、マルチエージェントトレードオフといった社会的および現実世界の考慮は、協調的、集団的分散的、そして公正な連合学習のような多分散学習パラダイムを生み出している。 それぞれの設定において、学習者は、可能な限り少数のサンプルを使用しながら、$n$の事前定義されたディストリビューションのセットよりも最悪のケース損失を最小限にしようとします。 本稿では,これらの学習パラダイムの最適なサンプル複雑性を確立し,このサンプル複雑性を満たすアルゴリズムを与える。 重要なことに、サンプルの複雑性境界は、1つの分布を学習するサンプルの複雑さのそれを超えるのは、加法係数が$n \log(n) / \epsilon^2$である。 これはmohriらによる無知連合学習の最もよく知られたサンプル複雑性を、n$の乗算係数、nguyen と zakynthinou による協調学習のサンプル複雑性を $\log n / \epsilon^3$ の乗算係数によって改善し、sagawa らのグループdro目標に対する最初のサンプル複雑性境界を与える。 最適なサンプル複雑性を実現するために,我々のアルゴリズムは需要分布からサンプルを学習する。 アルゴリズム設計と解析は確率的ゼロサムゲームを解くための確率的最適化手法の拡張によって実現される。 特にStochastic Mirror Descentの変種は、プレーヤーの安価なワンオフサンプルや、より高価な再利用可能なサンプルへのアクセスをトレードオフできる。

関連論文リスト

• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。 データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-16T04:32:22Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• 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)
• 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)

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

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