論文の概要: A closer look at temporal variability in dynamic online learning
- arxiv url: http://arxiv.org/abs/2102.07666v1
- Date: Mon, 15 Feb 2021 16:50:16 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-16 23:45:14.967956
- Title: A closer look at temporal variability in dynamic online learning
- Title(参考訳): 動的オンライン学習における時間変動について
- Authors: Nicol\`o Campolongo and Francesco Orabona
- Abstract要約: この作品は、完全な情報でオンライン学習の文脈でダイナミックな後悔の設定に焦点を当てています。
損失関数の列は時間とともに大きく変化しないと仮定することにより、既存の結果と比較して改善された後悔境界を導き出すことが可能であることを示す。
- 参考スコア(独自算出の注目度): 19.468067110814808
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This work focuses on the setting of dynamic regret in the context of online
learning with full information. In particular, we analyze regret bounds with
respect to the temporal variability of the loss functions. By assuming that the
sequence of loss functions does not vary much with time, we show that it is
possible to incur improved regret bounds compared to existing results. The key
to our approach is to use the loss function (and not its gradient) during the
optimization process. Building on recent advances in the analysis of Implicit
algorithms, we propose an adaptation of the Implicit version of Online Mirror
Descent to the dynamic setting. Our proposed algorithm is adaptive not only to
the temporal variability of the loss functions, but also to the path length of
the sequence of comparators when an upper bound is known. Furthermore, our
analysis reveals that our results are tight and cannot be improved without
further assumptions. Next, we show how our algorithm can be applied to the
setting of learning with expert advice or to settings with composite loss
functions. Finally, when an upper bound to the path-length is not fixed
beforehand we show how to combine a greedy strategy with existing
strongly-adaptive algorithms to compete optimally against different sequences
of comparators simultaneously.
- Abstract(参考訳): この作品は、完全な情報でオンライン学習の文脈でダイナミックな後悔の設定に焦点を当てています。
特に,損失関数の時間的変動に関して,後悔の限界を分析する。
損失関数の列は時間とともに大きく変化しないと仮定することにより、既存の結果と比較して改善された後悔境界を導き出すことが可能であることを示す。
我々のアプローチの鍵は、最適化プロセス中に損失関数(その勾配ではなく)を使用することです。
暗黙的アルゴリズム解析の最近の進歩を踏まえて,オンラインミラー降下の暗黙的バージョンを動的設定に適応する手法を提案する。
提案アルゴリズムは,損失関数の時間的変動だけでなく,上界が知られている場合のコンパレータ列の経路長にも適応する。
さらに,本分析の結果は厳密であり,さらなる仮定なしでは改善できないことが明らかとなった。
次に、専門家のアドバイスによる学習の設定や複合損失関数による設定にアルゴリズムをどのように適用できるかを示します。
最後に、経路長への上限が予め固定されていない場合、既存の強適応アルゴリズムとグリード戦略を組み合わせ、異なるコンパレータ列に対して最適に競合する方法を示す。
関連論文リスト
- Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for
Online Convex Optimization [93.71361250701075]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応するのは, 既往の結果よりも厳密であり, 最悪の場合, 同一の値が保証されるためである。
論文 参考訳(メタデータ) (2021-12-29T02:42:59Z) - Online estimation and control with optimal pathlength regret [52.28457815067461]
オンライン学習アルゴリズムを設計する際の自然なゴールは、入力シーケンスの時間的変動の観点から、アルゴリズムの後悔を束縛することである。
OCOや盗賊など、さまざまなオンライン学習問題に対して、データ依存の「病的」後悔境界が最近取得されている。
論文 参考訳(メタデータ) (2021-10-24T22:43:15Z) - Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for
Mixable/Exp-Concave Losses [0.0]
動的環境における対数的静的後悔を伴う混合損失関数のオンライン最適化について検討する。
文献では,スイッチ1回あたりのほぼ対数的後悔を1時間あたりのポリノミカルな複雑さで達成できることが確認できた。
論文 参考訳(メタデータ) (2021-09-28T15:06:31Z) - Optimal and Efficient Algorithms for General Mixable Losses against
Switching Oracles [0.0]
動的環境における混合損失関数のオンライン最適化について検討する。
我々の結果は、個々のシーケンス方式で強い決定論的意味を持つことが保証されている。
論文 参考訳(メタデータ) (2021-08-13T21:48:55Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳(メタデータ) (2021-07-21T17:10:14Z) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
論文 参考訳(メタデータ) (2021-06-29T09:48:46Z) - Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
非定常環境におけるオンライン凸最適化について検討する。
パフォーマンス指標として動的後悔を選択します。
本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
論文 参考訳(メタデータ) (2020-07-07T14:10:57Z) - Neural Non-Rigid Tracking [26.41847163649205]
我々は、新しい、エンドツーエンドの学習可能、差別化可能な非剛性トラッカーを導入する。
我々は畳み込みニューラルネットワークを用いて、密度の高い通信とその信頼性を予測する。
現状の手法と比較して,提案アルゴリズムは再構築性能の向上を示す。
論文 参考訳(メタデータ) (2020-06-23T18:00:39Z) - Temporal Variability in Implicit Online Learning [15.974402990630402]
最強の後悔分析は、オンラインミラー・ダイスンよりも限界的な改善しか示さない。
損失関数列の時間的変動に依存する新しい静的な後悔境界を証明した。
本稿では、時間的変動の事前知識を必要とせずに、この後悔を抑える適応アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-12T22:50:34Z) - Learning with Differentiable Perturbed Optimizers [54.351317101356614]
本稿では,操作を微分可能で局所的に一定ではない操作に変換する手法を提案する。
提案手法は摂動に依拠し,既存の解法とともに容易に利用することができる。
本稿では,この枠組みが,構造化予測において発達した損失の族とどのように結びつくかを示し,学習課題におけるそれらの使用に関する理論的保証を与える。
論文 参考訳(メタデータ) (2020-02-20T11:11:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。