論文の概要: Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity

• arxiv url: http://arxiv.org/abs/2410.00690v1
• Date: Tue, 1 Oct 2024 13:45:55 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-05 04:25:20.085997
• Title: Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity
• Title（参考訳）: 分散ロバスト最適化におけるミニマックス速度の超越
• Authors: Quan Nguyen, Nishant A. Mehta, Cristóbal Guzmán,
• Abstract要約: 私たちは、$(lambda, beta)$-sparsityをダブした、空白という新しい概念を示します。 また、最適な$(lambda, beta)$-sparsity条件に適応する適応アルゴリズムを示す。
• 参考スコア（独自算出の注目度）: 14.396304498754688
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The minimax sample complexity of group distributionally robust optimization (GDRO) has been determined up to a $\log(K)$ factor, for $K$ the number of groups. In this work, we venture beyond the minimax perspective via a novel notion of sparsity that we dub $(\lambda, \beta)$-sparsity. In short, this condition means that at any parameter $\theta$, there is a set of at most $\beta$ groups whose risks at $\theta$ all are at least $\lambda$ larger than the risks of the other groups. To find an $\epsilon$-optimal $\theta$, we show via a novel algorithm and analysis that the $\epsilon$-dependent term in the sample complexity can swap a linear dependence on $K$ for a linear dependence on the potentially much smaller $\beta$. This improvement leverages recent progress in sleeping bandits, showing a fundamental connection between the two-player zero-sum game optimization framework for GDRO and per-action regret bounds in sleeping bandits. The aforementioned result assumes having a particular $\lambda$ as input. Perhaps surprisingly, we next show an adaptive algorithm which, up to log factors, gets sample complexity that adapts to the best $(\lambda, \beta)$-sparsity condition that holds. Finally, for a particular input $\lambda$, we also show how to get a dimension-free sample complexity result.
• Abstract（参考訳）: 群分布的ロバスト最適化 (GDRO) のミニマックス標本複雑性は、群数$Kに対して$\log(K)$因子に決定されている。 この研究において、我々は、$(\lambda, \beta)$-sparsity をダブした空間という新しい概念を通じて、minimaxの観点を超えて試みる。 つまり、この条件は任意のパラメータ $\theta$ において、少なくとも $\beta$ のリスクが他のグループのリスクよりも少なくとも $\lambda$ 大きいグループが存在することを意味する。 $\epsilon$-optimal $\theta$ を見つけるために、サンプル複雑性における $\epsilon$-dependent 項が、潜在的に小さい$\beta$ に対する線形依存に対して$K$ の線形依存と交換可能であることを示す新しいアルゴリズムと解析を通して示される。 この改良は睡眠帯域の最近の進歩を生かし、GDROのための2プレーヤゼロサムゲーム最適化フレームワークと睡眠帯域における動作毎の後悔境界との基本的な関係を示す。 上記の結果は、特定の$\lambda$を入力として持つと仮定する。 おそらく、私たちは次に、ログファクタまで、最高の$(\lambda, \beta)$-sparsity条件に適合するサンプルの複雑さを得る適応アルゴリズムを示します。 最後に、特定の入力$\lambda$に対して、次元のないサンプルの複雑さの結果を得る方法を示す。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Optimal Sample Complexity for Average Reward Markov Decision Processes [1.0445957451908694]
  平均報酬 MDP の最適ポリシを$widetilde O(|S||A|t_textmix2 epsilon-2)$で推定する。 これは文学の下位境界に到達した最初のアルゴリズムと分析である。
  論文  参考訳（メタデータ） (2023-10-13T03:08:59Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
  論文  参考訳（メタデータ） (2023-06-03T04:00:47Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners [17.224805430291177]
  線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。 そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-13T05:00:01Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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