論文の概要: Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback
- arxiv url: http://arxiv.org/abs/2310.14085v4
- Date: Thu, 28 Mar 2024 19:37:02 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-01 20:26:59.935761
- Title: Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback
- Title（参考訳）: ゆるやかなフィードバックを持つ強いモノトーンゲームとExp-Concaveゲームにおける適応的2倍最適非線形学習
- Authors: Michael I. Jordan, Tianyi Lin, Zhengyuan Zhou,
- Abstract要約: オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。
本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
- 参考スコア（独自算出の注目度）: 75.29048190099523
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Online gradient descent (OGD) is well known to be doubly optimal under strong convexity or monotonicity assumptions: (1) in the single-agent setting, it achieves an optimal regret of $\Theta(\log T)$ for strongly convex cost functions; and (2) in the multi-agent setting of strongly monotone games, with each agent employing OGD, we obtain last-iterate convergence of the joint action to a unique Nash equilibrium at an optimal rate of $\Theta(\frac{1}{T})$. While these finite-time guarantees highlight its merits, OGD has the drawback that it requires knowing the strong convexity/monotonicity parameters. In this paper, we design a fully adaptive OGD algorithm, \textsf{AdaOGD}, that does not require a priori knowledge of these parameters. In the single-agent setting, our algorithm achieves $O(\log^2(T))$ regret under strong convexity, which is optimal up to a log factor. Further, if each agent employs \textsf{AdaOGD} in strongly monotone games, the joint action converges in a last-iterate sense to a unique Nash equilibrium at a rate of $O(\frac{\log^3 T}{T})$, again optimal up to log factors. We illustrate our algorithms in a learning version of the classical newsvendor problem, where due to lost sales, only (noisy) gradient feedback can be observed. Our results immediately yield the first feasible and near-optimal algorithm for both the single-retailer and multi-retailer settings. We also extend our results to the more general setting of exp-concave cost functions and games, using the online Newton step (ONS) algorithm.
- Abstract（参考訳）: オンライン勾配降下(OGD)は、強凸性や単調性仮定の下では2倍に最適であることがよく知られており、(1)強凸コスト関数に対する$\Theta(\log T)$の最適後悔、(2)強凸コスト関数に対する強い単調ゲームのマルチエージェント設定において、OGDを用いる各エージェントは、それぞれ$\Theta(\frac{1}{T})$の最適な速度で、一意のナッシュ平衡に対する結合作用の最終的な収束を得る。
これらの有限時間保証はその利点を強調するが、OGDは強い凸性/単調性パラメータを知る必要があるという欠点がある。
本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズムである \textsf{AdaOGD} を設計する。
単一エージェント設定では、このアルゴリズムは強い凸性の下で$O(\log^2(T))$ regretを達成し、ログ係数まで最適である。
さらに、強単調ゲームにおいて各エージェントが \textsf{AdaOGD} を用いる場合、結合作用は最後の定位感覚で$O(\frac{\log^3 T}{T})$で一意なナッシュ平衡に収束する。
従来のニュースベンダ問題の学習バージョンでは,販売が遅れたため,(ノイズの多い)勾配フィードバックのみを観測できる。
この結果から, 単小売店と複数小売店の双方で実現可能な, ほぼ最適アルゴリズムが得られた。
また、オンラインニュートンステップ(ONS)アルゴリズムを用いて、exp-concaveコスト関数とゲームをより一般的な設定に拡張する。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises:
High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation [22.758674468435302]
重尾雑音系では、勾配と真の速度の差は有限の$p-thモーメントを持つと仮定される。
本稿では,重み付き雑音を用いた非平滑凸最適化の包括的解析を行う。
論文 参考訳（メタデータ） (2023-03-22T03:05:28Z) - Accelerated Single-Call Methods for Constrained Min-Max Optimization [5.266784779001398]
既存の方法は、各イテレーションで2つのグラデーションコールか2つのプロジェクションを必要とする。
本稿では,RGOG(Optimistic Gradient)の変種が,非可換な min-max 収束率問題に富むことを示した。
私たちの収束率は、自然や自然のような標準の尺度に当てはまる。
論文 参考訳（メタデータ） (2022-10-06T17:50:42Z) - Restricted Strong Convexity of Deep Learning Models with Smooth
Activations [31.003601717265006]
本研究では,スムーズなアクティベーション機能を持つディープラーニングモデルの最適化問題について検討する。
Restricted Strong Convexity (RSC) に基づく最適化の新しい解析手法を提案する。
深層学習モデルのためのRCCに基づくGDの幾何収束性を確立するための最初の結果である。
論文 参考訳（メタデータ） (2022-09-29T21:24:26Z) - The Power of Regularization in Solving Extensive-Form Games [22.557806157585834]
本稿では,ゲームにおける支払関数の正規化に基づく新しいアルゴリズムを提案する。
特に、拡張された楽観的ミラー降下(DOMD)が高速な$tilde O(T)$ last-iterate convergenceを達成できることを示す。
また、Reg-CFRは、楽観的ミラー降下アルゴリズムの変形を最小化して、$O(T1/4)$ベストイテレート、$O(T3/4)$平均イテレート収束率を達成できることを示した。
論文 参考訳（メタデータ） (2022-06-19T22:10:38Z) - Provably Efficient Convergence of Primal-Dual Actor-Critic with
Nonlinear Function Approximation [15.319335698574932]
The first efficient convergence result with primal-dual actor-critic with a convergence of $mathcalOleft ascent(Nright)Nright)$ under Polyian sample。
Open GymAI連続制御タスクの結果。
論文 参考訳（メタデータ） (2022-02-28T15:16:23Z) - Near-Optimal No-Regret Learning for Correlated Equilibria in
Multi-Player General-Sum Games [104.74734408204749]
マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。
外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
論文 参考訳（メタデータ） (2021-11-11T01:19:53Z) - Linear Last-iterate Convergence in Constrained Saddle-point Optimization [48.44657553192801]
我々は、OGDA(Optimistic Gradient Descent Ascent)とOMWU(Optimistic Multiplicative Weights Update)に対する最終段階の独特さの理解を著しく拡大する。
平衡が一意である場合、線形終端収束は、値が普遍定数に設定された学習速度で達成されることを示す。
任意のポリトープ上の双線型ゲームがこの条件を満たすことを示し、OGDAは一意の平衡仮定なしで指数関数的に高速に収束することを示した。
論文 参考訳（メタデータ） (2020-06-16T20:53:04Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。