論文の概要: Efficient Methods for Non-stationary Online Learning

• arxiv url: http://arxiv.org/abs/2309.08911v2
• Date: Thu, 30 Jan 2025 09:02:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-31 15:13:08.504687
• Title: Efficient Methods for Non-stationary Online Learning
• Title（参考訳）: 非定常オンライン学習のための効率的な方法
• Authors: Peng Zhao, Yan-Feng Xie, Lijun Zhang, Zhi-Hua Zhou,
• Abstract要約: 本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 また、さらに強化された測度、すなわち「インターバル・ダイナミック・リピート」を研究し、ラウンド当たりの射影数を$mathcalO(log2 T)$から$$$$に減らした。
• 参考スコア（独自算出の注目度）: 61.63338724659592
• License:
• 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 first 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$. The 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. Furthermore, we study an even strengthened measure, namely the ``interval dynamic regret'', and reduce the number of projections per round from $\mathcal{O}(\log^2 T)$ to $1$ to minimize it. Our reduction demonstrates great generalizability and can be applied to two important applications: online stochastic control and online principal component analysis, resulting in methods that are both efficient and optimal. Finally, empirical studies verify our theoretical findings.
• Abstract（参考訳）: 近年,非定常オンライン学習が注目されている。 特に、動的後悔と適応的後悔は、非定常環境におけるオンライン凸最適化のための2つの原則的性能指標として提案される。 これらを最適化するために、通常、2層オンラインアンサンブルは、ベースラーナーのグループを維持し、メタアルゴリズムを用いて、最高のアンサンブルの追跡を行う非定常性の固有の不確実性のために展開される。 しかし、この2層構造は計算複雑性に関する懸念を提起するものであり、これらの手法は通常、$T$ラウンドのオンラインゲームに対して$\mathcal{O}(\log T)$base-learnerを同時に維持する。 本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を最初に提示し, ラウンド当たりの投影回数を$\mathcal{O}(\log T)$から$1$に削減した。 得られたアルゴリズムは、各ラウンドで1つの勾配クエリと1つの関数評価しか必要としない。 本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。 さらに、 'interval dynamic regret'' というさらに強化された測度について検討し、ラウンド当たりの射影数を$\mathcal{O}(\log^2 T)$から$ $1$ に減らして最小化する。 我々の削減は、非常に一般化可能性を示し、オンライン確率制御とオンライン主成分分析の2つの重要な応用に適用できる。 最後に,我々の理論的知見を実証的に検証した。

関連論文リスト

• 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)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。