論文の概要: Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates
- arxiv url: http://arxiv.org/abs/2502.07141v1
- Date: Tue, 11 Feb 2025 00:12:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-12 14:07:05.415936
- Title: Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates
- Title(参考訳): スモールステップはもうない: 任意の学習率に対する確率勾配帯域のグローバル収束
- Authors: Jincheng Mei, Bo Dai, Alekh Agarwal, Sharan Vaswani, Anant Raj, Csaba Szepesvari, Dale Schuurmans,
- Abstract要約: 勾配帯域幅アルゴリズムは, 経験的定値学習率を用いて, ほぼ確実にグローバルな最適ポリシーに収束することを示す。
この結果は、標準の滑らかさと騒音制御の仮定が崩壊するシナリオにおいても、勾配アルゴリズムが適切な探索と利用のバランスを保ち続けていることを証明している。
- 参考スコア(独自算出の注目度): 61.091122503406304
- License:
- Abstract: We provide a new understanding of the stochastic gradient bandit algorithm by showing that it converges to a globally optimal policy almost surely using \emph{any} constant learning rate. This result demonstrates that the stochastic gradient algorithm continues to balance exploration and exploitation appropriately even in scenarios where standard smoothness and noise control assumptions break down. The proofs are based on novel findings about action sampling rates and the relationship between cumulative progress and noise, and extend the current understanding of how simple stochastic gradient methods behave in bandit settings.
- Abstract(参考訳): 本稿では, 確率勾配帯域幅アルゴリズムの新しい理解法として, ほぼ確実に 'emph{any} 定常学習率を用いて, グローバルな最適政策に収束することを示す。
この結果は、標準的な滑らかさと騒音制御の仮定が崩壊するシナリオにおいても、確率勾配アルゴリズムが探索と利用のバランスを適切に保ち続けていることを証明している。
これらの証明は、行動サンプリング率と累積進行と雑音の関係に関する新たな知見に基づいており、単純な確率勾配法がバンディット設定でどのように振る舞うかについての現在の理解を拡張している。
関連論文リスト
- Learning Optimal Deterministic Policies with Stochastic Policy Gradients [62.81324245896716]
政策勾配法(PG法)は連続強化学習(RL法)問題に対処する手法として成功している。
一般的には、収束(ハイパー)政治は、決定論的バージョンをデプロイするためにのみ学習される。
本稿では,サンプルの複雑性とデプロイされた決定論的ポリシのパフォーマンスのトレードオフを最適化するために,学習に使用する探索レベルの調整方法を示す。
論文 参考訳(メタデータ) (2024-05-03T16:45:15Z) - Stochastic Gradient Succeeds for Bandits [64.17904367852563]
エンフィスト確率勾配帯域幅アルゴリズムは,O (1/t)$レートで,エンフィグロブな最適ポリシに収束することを示す。
興味深いことに、勾配帯域アルゴリズムのグローバル収束は以前に確立されていない。
論文 参考訳(メタデータ) (2024-02-27T06:05:01Z) - The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise [17.493808856903303]
近似アルゴリズムを解析する根本的な課題は、その安定性を確立することである。
我々は、マルティンゲール差分雑音設定からマルコフ雑音設定へ有界な安定性に対するボルカール・メインの定理を拡張した。
論文 参考訳(メタデータ) (2024-01-15T17:20:17Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳(メタデータ) (2021-10-20T02:25:25Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳(メタデータ) (2021-07-21T17:10:14Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳(メタデータ) (2021-06-30T17:51:36Z) - Sample Efficient Reinforcement Learning with REINFORCE [10.884278019498588]
本稿では,古典的政策勾配法と広く用いられているREINFORCE推定手法について考察する。
悪い」エピソードの数を制御することによって、常にサブリニアな高い後悔の束縛を確立し、平均的後悔のグローバル収束を、アナルなサブリニアレートでほぼ確実に確立する。
これらのアルゴリズムは、よく知られたREINFORCEアルゴリズムに対して、グローバル収束とサンプル効率の最初のセットを提供し、実際にの性能をよりよく理解するのに貢献する。
論文 参考訳(メタデータ) (2020-10-22T01:02:55Z) - Variance Regularization for Accelerating Stochastic Optimization [14.545770519120898]
ミニバッチ勾配に隠れた統計情報を利用してランダムな誤りの蓄積を低減する普遍原理を提案する。
これは、ミニバッチのばらつきに応じて学習率を正規化することで達成される。
論文 参考訳(メタデータ) (2020-08-13T15:34:01Z) - Incremental Without Replacement Sampling in Nonconvex Optimization [0.0]
経験的リスクに対する最小限の分解法は、一般に近似設定で分析される。
一方、このような手法の現代的な実装は漸進的であり、それらは置換せずにサンプリングに依存しており、利用可能な分析は極めて少ない。
我々は、多変数な漸進勾配スキームを解析することにより、後者の変分に対する収束保証を提供する。
論文 参考訳(メタデータ) (2020-07-15T09:17:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。