論文の概要: Group Distributionally Robust Optimization with Flexible Sample Queries
- arxiv url: http://arxiv.org/abs/2505.15212v1
- Date: Wed, 21 May 2025 07:41:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-22 15:42:59.119898
- Title: Group Distributionally Robust Optimization with Flexible Sample Queries
- Title（参考訳）: フレキシブルサンプルクエリを用いた群分散ロバスト最適化
- Authors: Haomin Bai, Dingzhi Yu, Shuai Li, Haipeng Luo, Lijun Zhang,
- Abstract要約: グループ分散ロバスト最適化(GDRO)は、$m$の分散を同時に行うモデルを開発することを目的としている。
既存のGDROアルゴリズムは、イテレーション毎に1または$m$の固定数のサンプルしか処理できない。
我々はGDROアルゴリズムを開発し、1ラウンドあたりの任意のサンプルサイズを可変し、高い確率最適化誤差を$Oleft(frac1tsqrtsum_j=1t fracmr_jlog mright)$とする。
- 参考スコア（独自算出の注目度）: 41.4457693520265
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Group distributionally robust optimization (GDRO) aims to develop models that perform well across $m$ distributions simultaneously. Existing GDRO algorithms can only process a fixed number of samples per iteration, either 1 or $m$, and therefore can not support scenarios where the sample size varies dynamically. To address this limitation, we investigate GDRO with flexible sample queries and cast it as a two-player game: one player solves an online convex optimization problem, while the other tackles a prediction with limited advice (PLA) problem. Within such a game, we propose a novel PLA algorithm, constructing appropriate loss estimators for cases where the sample size is either 1 or not, and updating the decision using follow-the-regularized-leader. Then, we establish the first high-probability regret bound for non-oblivious PLA. Building upon the above approach, we develop a GDRO algorithm that allows an arbitrary and varying sample size per round, achieving a high-probability optimization error bound of $O\left(\frac{1}{t}\sqrt{\sum_{j=1}^t \frac{m}{r_j}\log m}\right)$, where $r_t$ denotes the sample size at round $t$. This result demonstrates that the optimization error decreases as the number of samples increases and implies a consistent sample complexity of $O(m\log (m)/\epsilon^2)$ for any fixed sample size $r\in[m]$, aligning with existing bounds for cases of $r=1$ or $m$. We validate our approach on synthetic binary and real-world multi-class datasets.
- Abstract（参考訳）: グループ分散ロバスト最適化(GDRO)は、$m$の分散を同時に行うモデルを開発することを目的としている。
既存のGDROアルゴリズムは、1回につき1または$m$の固定数のサンプルしか処理できないため、サンプルサイズが動的に変化するシナリオをサポートできない。
この制限に対処するため、GDROをフレキシブルなサンプルクエリを用いて調査し、2プレイヤーゲームとしてキャストする。一方のプレイヤーはオンライン凸最適化問題を解き、他方のプレイヤーは限定的なアドバイス(PLA)問題で予測に対処する。
このようなゲーム内では,サンプルサイズが1か2の場合に適切な損失推定器を構築し,従順化リーダを用いて決定を更新する,新しいPLAアルゴリズムを提案する。
そこで我々は,非公開PLAに対する最初の高い確率的後悔を確立する。
上記のアプローチに基づいて、GDROアルゴリズムは、任意の1ラウンドあたりのサンプルサイズを許容し、高い確率最適化誤差を$O\left(\frac{1}{t}\sqrt{\sum_{j=1}^t \frac{m}{r_j}\log m}\right)$で達成する。
この結果は、サンプルの数が増えるにつれて最適化エラーが減少し、固定されたサンプルサイズ$r\in[m]$に対して$O(m\log (m)/\epsilon^2)$が一貫したサンプル複雑性を示し、$r=1$または$m$の場合に既存の境界と整合することを示している。
合成バイナリと実世界のマルチクラスデータセットに対するアプローチを検証する。
関連論文リスト
- Efficiently Solving Discounted MDPs with Predictions on Transition Matrices [6.199300239433395]
生成モデルに基づくDMDP(Discounted Markov Decision Processs)について検討した。
DMDPの解法において,遷移行列上での予測がサンプル効率をいかに向上させるかを検討するための新しい枠組みを提案する。
論文 参考訳（メタデータ） (2025-02-21T09:59:46Z) - On the query complexity of sampling from non-log-concave distributions [2.4253233571593547]
密度$p(x)propto e-f(x)$を持つ$d$次元分布からサンプリングする問題を、必ずしも良好な等尺条件を満たすとは限らない。
広い範囲のパラメータに対して、サンプリングは$d$の超指数係数による最適化よりも厳密に容易であることを示す。
論文 参考訳（メタデータ） (2025-02-10T06:54:16Z) - Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity [14.396304498754688]
私たちは、$(lambda, beta)$-sparsityをダブした、空白という新しい概念を示します。
つまり、少なくとも$theta$のリスクが他のグループのリスクよりも少なくとも$lambda$であるような、少なくとも$beta$グループのセットがあります。
計算効率のよい手法により,次元自由な半適応サンプルの複雑性を得る方法を示す。
論文 参考訳（メタデータ） (2024-10-01T13:45:55Z) - 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) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。