論文の概要: Optimal Dynamic Regret in Proper Online Learning with Strongly Convex
Losses and Beyond
- arxiv url: http://arxiv.org/abs/2201.08905v1
- Date: Fri, 21 Jan 2022 22:08:07 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-25 15:29:02.604224
- Title: Optimal Dynamic Regret in Proper Online Learning with Strongly Convex
Losses and Beyond
- Title（参考訳）: 強凸損失を含む適切なオンライン学習における最適動的後悔
- Authors: Dheeraj Baby and Yu-Xiang Wang
- Abstract要約: 適切な学習設定で、Strongly Adaptiveアルゴリズムは、ほぼ最適な動的後悔を実現することができることを示す。
また, 適切なオンライン学習を行う場合, Exp-concaveの損失を伴って, 最適の動的後悔率を導出する。
- 参考スコア（独自算出の注目度）: 23.91519151164528
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We study the framework of universal dynamic regret minimization with strongly
convex losses. We answer an open problem in Baby and Wang 2021 by showing that
in a proper learning setup, Strongly Adaptive algorithms can achieve the near
optimal dynamic regret of $\tilde O(d^{1/3} n^{1/3}\text{TV}[u_{1:n}]^{2/3}
\vee d)$ against any comparator sequence $u_1,\ldots,u_n$ simultaneously, where
$n$ is the time horizon and $\text{TV}[u_{1:n}]$ is the Total Variation of
comparator. These results are facilitated by exploiting a number of new
structures imposed by the KKT conditions that were not considered in Baby and
Wang 2021 which also lead to other improvements over their results such as: (a)
handling non-smooth losses and (b) improving the dimension dependence on
regret. Further, we also derive near optimal dynamic regret rates for the
special case of proper online learning with exp-concave losses and an
$L_\infty$ constrained decision set.
- Abstract（参考訳）: 強い凸損失を伴う普遍的動的後悔最小化の枠組みについて検討する。
我々は、Baby と Wang 2021 のオープンな問題に、適切な学習設定で、強い適応アルゴリズムは、$\tilde O(d^{1/3} n^{1/3}\text{TV}[u_{1:n}]^{2/3} \vee d)$ を任意のコンパレータ列 $u_1,\ldots,u_n$ に対して、同時に、$n$ は時間地平線、$\text{TV}[u_{1:n}]$ はコンパレータのトータル変分を、ほぼ最適に再現できることを示した。
これらの結果は、Baby や Wang 2021 では考慮されなかった KKT の条件によって課せられる多くの新しい構造を活用して促進される。
(a)非滑らかな損失の処理
(b)後悔の次元依存性を改善すること。
さらに, 適切なオンライン学習を行う場合, exp-concave損失と$L_\infty$制約付き決定セットで, 最適の動的後悔率を導出する。
関連論文リスト
- 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) - Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。
本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
論文 参考訳（メタデータ） (2023-02-11T07:19:51Z) - Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。
我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。
先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
論文 参考訳（メタデータ） (2022-06-17T12:58:58Z) - Second Order Path Variationals in Non-Stationary Online Learning [23.91519151164528]
設計したStrongly Adaptiveアルゴリズムは$tilde O(d2 n1/5 C_n2/5 vee d2)$の動的後悔を実現する。
上記の動的後悔率は、最適モジュラー次元依存およびn$の多対数因子であることが示されている。
論文 参考訳（メタデータ） (2022-05-04T07:14:39Z) - 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) - Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary
Dueling Bandits [27.279654173896372]
我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。
これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
論文 参考訳（メタデータ） (2021-11-06T16:46:55Z) - Optimal Dynamic Regret in Exp-Concave Online Learning [28.62891856368132]
我々は、オンライン学習におけるZinkevich(2003)スタイルの動的後悔最小化の問題を検討する。
不適切な学習が許されるたびに、Strongly Adaptive のオンライン学習者は $tilde O(d3.5n1/3C_n2/3 vee dlog n)$ の動的後悔を達成する。
経路の長さ) 学習者が事前に知ることができない任意のコンパレータのシーケンス。
論文 参考訳（メタデータ） (2021-04-23T21:36:51Z) - Revisiting Smoothed Online Learning [70.09792747315323]
オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。
競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
論文 参考訳（メタデータ） (2021-02-13T14:15:55Z) - Projection-free Online Learning over Strongly Convex Sets [24.517908972536432]
我々は,強い凸集合に対するオンライン学習の特別な事例について検討し,OWが一般凸集合の損失に対して$O(T2/3)$よりも良い後悔の限界を享受できることを最初に証明した。
一般凸集合に対する$O(sqrtT)$の後悔境界と強凸集合に対する$O(sqrtT)$の後悔境界を達成することを示す。
論文 参考訳（メタデータ） (2020-10-16T05:42:50Z) - Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
非定常環境におけるオンライン凸最適化について検討する。
パフォーマンス指標として動的後悔を選択します。
本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
論文 参考訳（メタデータ） (2020-07-07T14:10:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。