論文の概要: Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond

• arxiv url: http://arxiv.org/abs/2302.09267v5
• Date: Wed, 20 Nov 2024 05:58:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-21 16:10:26.836210
• Title: Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond
• Title（参考訳）: 群分布ロバスト最適化のための確率近似的アプローチ
• Authors: Lijun Zhang, Haomin Bai, Peng Zhao, Tianbao Yang, Zhi-Hua Zhou,
• Abstract要約: 本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
• 参考スコア（独自算出の注目度）: 89.72693227960274
• License:
• Abstract: This paper investigates group distributionally robust optimization (GDRO) with the goal of learning a model that performs well over $m$ different distributions. First, we formulate GDRO as a stochastic convex-concave saddle-point problem, which is then solved by stochastic mirror descent (SMD) with $m$ samples in each iteration, and attain a nearly optimal sample complexity. To reduce the number of samples required in each round from $m$ to 1, we cast GDRO as a two-player game, where one player conducts SMD and the other executes an online algorithm for non-oblivious multi-armed bandits, maintaining the same sample complexity. Next, we extend GDRO to address scenarios involving imbalanced data and heterogeneous distributions. In the first scenario, we introduce a weighted variant of GDRO, enabling distribution-dependent convergence rates that rely on the number of samples from each distribution. We design two strategies to meet the sample budget: one integrates non-uniform sampling into SMD, and the other employs the stochastic mirror-prox algorithm with mini-batches, both of which deliver faster rates for distributions with more samples. In the second scenario, we propose to optimize the average top-$k$ risk instead of the maximum risk, thereby mitigating the impact of outlier distributions. Similar to the case of vanilla GDRO, we develop two stochastic approaches: one uses $m$ samples per iteration via SMD, and the other consumes $k$ samples per iteration through an online algorithm for non-oblivious combinatorial semi-bandits.
• Abstract（参考訳）: 本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 まず、GDROを確率的凸凹サドル点問題として定式化し、各イテレーションで$m$のサンプルを持つ確率的ミラー降下(SMD)により解き、ほぼ最適なサンプル複雑性を得る。 各ラウンドで必要となるサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーがSMDを行い、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行し、同じサンプル複雑性を維持した。 次に、不均衡なデータと不均一な分布を含むシナリオに対処するためにGDROを拡張します。 第1のシナリオでは、GDROの重み付き変種を導入し、各分布からのサンプル数に依存する分布依存収束率を実現する。 サンプル予算を満たすための2つの戦略を設計する。一方は非一様サンプリングをSMDに統合し、他方は確率的ミラープロキシアルゴリズムとミニバッチを用いて、より多くのサンプルで分布速度を高速化する。 第2のシナリオでは、リスクの最大化ではなく、平均的最上位k$リスクを最適化し、アウトリーチ分布の影響を軽減することを提案する。 バニラGDROの場合と同様に、我々は2つの確率的アプローチを開発する。一方はSMDを介して1イテレーションあたり$m$サンプルを使用し、もう一方は、非公開の組合せ半帯域に対するオンラインアルゴリズムを通じて、1イテレーション当たり$k$サンプルを消費する。

関連論文リスト

• Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel [10.840582511203024]
  我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでのみ実行できるように並列化可能であることを示す。 また、我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでしか実行できないことを示す。
  論文  参考訳（メタデータ） (2024-06-03T01:34:34Z)
• Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
  非log-concave分布からのサンプリングのための近位サンプリング器 (SPS) について検討した。 対象分布への収束性は,アルゴリズムの軌道が有界である限り保証可能であることを示す。 我々は、Langevin dynamics(SGLD)とLangevin-MALAの2つの実装可能な変種を提供し、SPS-SGLDとSPS-MALAを生み出した。
  論文  参考訳（メタデータ） (2024-05-27T00:53:18Z)
• Efficient Algorithms for Empirical Group Distributional Robust Optimization and Beyond [15.664414751701718]
  経験的GDROを$textittwo-level$ finite-sum convex-concave minimax Optimization問題として定式化する。 我々は、スナップショットとミラースナップショットポイントを1インデックスシフトした重み付き平均で計算し、単純エルゴディック平均と区別する。 注目すべきは、我々の手法が最先端の手法よりも$sqrtm$で優れていることだ。
  論文  参考訳（メタデータ） (2024-03-06T09:14:24Z)
• Perfect Sampling from Pairwise Comparisons [26.396901523831534]
  分散分布$mathcalD$の与えられたアクセスから最適なサンプルを効率よく取得する方法を,サポート対象の要素のペア比較に限定して検討する。 固定分布が$mathcalD$と一致するマルコフ連鎖を設計し、過去からの結合技術を用いて正確なサンプルを得るアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-11-23T11:20:30Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。 我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-13T17:37:21Z)
• 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)
• 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)

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

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