論文の概要: Efficient Methods for Non-stationary Online Learning
- arxiv url: http://arxiv.org/abs/2309.08911v1
- Date: Sat, 16 Sep 2023 07:30:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-19 18:44:40.988981
- Title: Efficient Methods for Non-stationary Online Learning
- Title（参考訳）: 非定常オンライン学習の効率的な方法
- Authors: Peng Zhao and Yan-Feng Xie and Lijun Zhang and Zhi-Hua Zhou
- Abstract要約: 本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
- 参考スコア（独自算出の注目度）: 67.3300478545554
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Non-stationary online learning has drawn much attention in recent years. In
particular, dynamic regret and adaptive regret are proposed as two principled
performance measures for online convex optimization in non-stationary
environments. To optimize them, a two-layer online ensemble is usually deployed
due to the inherent uncertainty of the non-stationarity, in which a group of
base-learners are maintained and a meta-algorithm is employed to track the best
one on the fly. However, the two-layer structure raises the concern about the
computational complexity -- those methods typically maintain $\mathcal{O}(\log
T)$ base-learners simultaneously for a $T$-round online game and thus perform
multiple projections onto the feasible domain per round, which becomes the
computational bottleneck when the domain is complicated. In this paper, we
present efficient methods for optimizing dynamic regret and adaptive regret,
which reduce the number of projections per round from $\mathcal{O}(\log T)$ to
$1$. Moreover, our obtained algorithms require only one gradient query and one
function evaluation at each round. Our technique hinges on the reduction
mechanism developed in parameter-free online learning and requires non-trivial
twists on non-stationary online methods. Empirical studies verify our
theoretical findings.
- Abstract（参考訳）: 非定常オンライン学習は近年注目を集めている。
特に,非定常環境におけるオンライン凸最適化のための2つの原理的性能指標として動的後悔と適応後悔が提案されている。
これらを最適化するために、通常、2層オンラインアンサンブルは、ベースラーナーのグループを維持し、メタアルゴリズムを用いて、最高のアンサンブルを追跡する非定常性の固有の不確実性のために展開される。
しかし、2層構造は計算の複雑さに関する懸念を提起する - これらの手法は通常、$t$-roundオンラインゲームのために$\mathcal{o}(\log t)$ base-learnerを同時に保持し、従ってラウンド当たりの実行可能な領域に複数の射影を実行する。
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$\mathcal{O}(\log T)$から$1$に削減する。
さらに,得られたアルゴリズムでは,各ラウンドの勾配クエリと1つの関数評価のみを要求できる。
本手法は,パラメータフリーオンライン学習で開発されたリダクション機構に依存しており,非定常オンライン手法では非自明なツイストを必要とする。
実証研究は我々の理論的な結果を検証する。
関連論文リスト
- Variance Reduced Online Gradient Descent for Kernelized Pairwise
Learning with Limited Memory [19.822215548822882]
オンラインのペアワイズ学習を扱うために、オンライン勾配降下アルゴリズム(OGD)が提案されている。
OGDアルゴリズムの最近の進歩は、オンライン勾配の計算の複雑さを減らし、O(T)$未満の複雑さを達成し、たとえ$O(1)$であるとしても達成することを目的としている。
本研究では,カーネルのオンラインペアワイズ学習に拡張し,サブ線形後悔を改善したメモリOGDアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-10T09:50:54Z) - Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。
インスタンス最適性の追求に動機づけられ,我々は新しいアルゴリズムを提案する。
これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
論文 参考訳（メタデータ） (2023-09-27T21:54:52Z) - 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 Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳（メタデータ） (2022-10-02T05:03:38Z) - Proximal Point Imitation Learning [48.50107891696562]
我々は、無限地平線模倣学習のための厳密な効率保証を備えた新しいアルゴリズムを開発した。
我々は、最適化、特に近点法(PPM)と双対平滑化から古典的ツールを活用する。
線形関数とニューラルネットワーク関数の近似の双方に対して、説得力のある経験的性能を実現する。
論文 参考訳（メタデータ） (2022-09-22T12:40:21Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Adaptive Approximate Policy Iteration [22.915651391812187]
均一なエルゴディックMDPの学習を継続する学習方法として,$tildeO(T2/3)$ regret bound for undiscounted, continuing learning in uniformly ergodic MDPを提案する。
これは、関数近似を持つ平均逆ケースに対する$tildeO(T3/4)$の最良の既存の境界よりも改善されている。
論文 参考訳（メタデータ） (2020-02-08T02:27:03Z) - Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
自己指向型オンライン学習最適化は、ディープニューラルネットワーク(DNN)と有限要素法(FEM)計算を統合している。
本アルゴリズムは, コンプライアンスの最小化, 流体構造最適化, 伝熱促進, トラス最適化の4種類の問題によって検証された。
その結果, 直接使用法と比較して計算時間を2～5桁削減し, 実験で検証した全ての最先端アルゴリズムより優れていた。
論文 参考訳（メタデータ） (2020-02-04T20:00:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。