論文の概要: Second Order Path Variationals in Non-Stationary Online Learning
- arxiv url: http://arxiv.org/abs/2205.01921v1
- Date: Wed, 4 May 2022 07:14:39 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-05 14:03:36.095182
- Title: Second Order Path Variationals in Non-Stationary Online Learning
- Title（参考訳）: 非定常オンライン学習における2次経路変動
- Authors: Dheeraj Baby and Yu-Xiang Wang
- Abstract要約: 設計したStrongly Adaptiveアルゴリズムは$tilde O(d2 n1/5 C_n2/5 vee d2)$の動的後悔を実現する。
上記の動的後悔率は、最適モジュラー次元依存およびn$の多対数因子であることが示されている。
- 参考スコア（独自算出の注目度）: 23.91519151164528
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We consider the problem of universal dynamic regret minimization under
exp-concave and smooth losses. We show that appropriately designed Strongly
Adaptive algorithms achieve a dynamic regret of $\tilde O(d^2 n^{1/5} C_n^{2/5}
\vee d^2)$, where $n$ is the time horizon and $C_n$ a path variational based on
second order differences of the comparator sequence. Such a path variational
naturally encodes comparator sequences that are piecewise linear -- a powerful
family that tracks a variety of non-stationarity patterns in practice (Kim et
al, 2009). The aforementioned dynamic regret rate is shown to be optimal modulo
dimension dependencies and poly-logarithmic factors of $n$. Our proof
techniques rely on analysing the KKT conditions of the offline oracle and
requires several non-trivial generalizations of the ideas in Baby and Wang,
2021, where the latter work only leads to a slower dynamic regret rate of
$\tilde O(d^{2.5}n^{1/3}C_n^{2/3} \vee d^{2.5})$ for the current problem.
- Abstract（参考訳）: 我々は,exp-concave と smooth loss の下での普遍的動的後悔の最小化の問題を考える。
そこで,n$は時間軸であり,c_n$はコンパレータ列の2次差に基づく経路変動である,$\tilde o(d^2 n^{1/5} c_n^{2/5} \vee d^2)$の動的後悔を適切に設計した強適応アルゴリズムが達成することを示す。
このような経路変分法は、区分線形であるコンパレータ列を自然にエンコードする -- 様々な非定常パターンを追跡する強力なファミリー -- (kim et al, 2009)。
上記の動的後悔率は、最適モジュラー次元依存およびn$の多対数因子であることが示されている。
我々の証明手法はオフラインオラクルのkkt条件の解析に依存しており、2021年のbaby and wangにおけるアイデアのいくつかの非自明な一般化を必要としており、後者の仕事は現在の問題に対して$\tilde o(d^{2.5}n^{1/3}c_n^{2/3} \vee d^{2.5})$の動的後悔率をもたらすだけである。
関連論文リスト
- ELRA: Exponential learning rate adaption gradient descent optimization
method [83.88591755871734]
我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。
本手法の主な考え方は,状況認識による$alphaの適応である。
これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
論文 参考訳（メタデータ） (2023-09-12T14:36:13Z) - 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) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - Optimal Dynamic Regret in Proper Online Learning with Strongly Convex
Losses and Beyond [23.91519151164528]
適切な学習設定で、Strongly Adaptiveアルゴリズムは、ほぼ最適な動的後悔を実現することができることを示す。
また, 適切なオンライン学習を行う場合, Exp-concaveの損失を伴って, 最適の動的後悔率を導出する。
論文 参考訳（メタデータ） (2022-01-21T22:08:07Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - 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) - Adaptive Online Estimation of Piecewise Polynomial Trends [23.91519151164528]
我々は,2乗誤差損失と雑音勾配フィードバックを伴う非定常最適化の枠組みを考察する。
非パラメトリック回帰理論から動機づけられた新しい変分制約を導入する。
我々は、同じ方針が、他のいくつかの非パラメトリックな関心の族に最適であることを示す。
論文 参考訳（メタデータ） (2020-09-30T19:30:28Z) - Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
非定常環境におけるオンライン凸最適化について検討する。
パフォーマンス指標として動的後悔を選択します。
本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
論文 参考訳（メタデータ） (2020-07-07T14:10:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。