論文の概要: Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization

• arxiv url: http://arxiv.org/abs/2112.14368v3
• Date: Sun, 7 Apr 2024 06:50:01 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-10 06:04:02.964839
• Title: Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization
• Title（参考訳）: 適応性と非定常性:オンライン凸最適化のための問題依存動的レグレット
• Authors: Peng Zhao, Yu-Jie Zhang, Lijun Zhang, Zhi-Hua Zhou,
• Abstract要約: 本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
• 参考スコア（独自算出の注目度）: 70.4342220499858
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate online convex optimization in non-stationary environments and choose dynamic regret as the performance measure, defined as the difference between cumulative loss incurred by the online algorithm and that of any feasible comparator sequence. Let $T$ be the time horizon and $P_T$ be the path length that essentially reflects the non-stationarity of environments, the state-of-the-art dynamic regret is $\mathcal{O}(\sqrt{T(1+P_T)})$. Although this bound is proved to be minimax optimal for convex functions, in this paper, we demonstrate that it is possible to further enhance the guarantee for some easy problem instances, particularly when online functions are smooth. Specifically, we introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities: the variation in gradients of loss functions, the cumulative loss of the comparator sequence, and the minimum of these two terms. These quantities are at most $\mathcal{O}(T)$ while could be much smaller in benign environments. Therefore, our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and meanwhile safeguard the same rate in the worst case. Notably, our proposed algorithms can achieve favorable dynamic regret with only one gradient per iteration, sharing the same gradient query complexity as the static regret minimization methods. To accomplish this, we introduce the collaborative online ensemble framework. The proposed framework employs a two-layer online ensemble to handle non-stationarity, and uses optimistic online learning and further introduces crucial correction terms to enable effective collaboration within the meta-base two layers, thereby attaining adaptivity. We believe the framework can be useful for broader problems.
• Abstract（参考訳）: 非定常環境におけるオンライン凸最適化について検討し、オンラインアルゴリズムが生み出す累積損失と実行可能なコンパレータシーケンスとの差として定義した性能指標として動的後悔を選択する。 T$を時間軸とし、$P_T$を環境の非定常性を本質的に反映するパス長とし、最先端の動的後悔は$\mathcal{O}(\sqrt{T(1+P_T)})$とする。 この境界は凸関数に最適であることが証明されているが、本論文では、特にオンライン関数が滑らかな場合に、いくつかの簡単な問題インスタンスの保証をさらに強化できることを実証する。 具体的には,損失関数の勾配の変動,コンパレータ列の累積損失,およびこれら2項の最小化など,スムーズさを生かし,動的後悔のT$への依存を問題依存量に置き換える新しいオンラインアルゴリズムを提案する。 これらの量は少なくとも$\mathcal{O}(T)$であるが、良質な環境ではずっと小さい。 したがって,本研究の結果は,既存の問題よりも厳密であり,かつ最悪の場合においても,同じ割合を保護できるため,本問題の本質的な難易度に適応する。 特に,提案アルゴリズムは1イテレーションに1つの勾配しか持たず,静的な後悔最小化法と同じ勾配クエリの複雑さを共有できる。 これを実現するために,協調的なオンラインアンサンブルフレームワークを導入する。 提案フレームワークは、非定常性を扱うために2層オンラインアンサンブルを使用し、楽観的なオンライン学習を用い、メタベース2層内で効果的な協調を可能にするために重要な修正項を導入し、適応性を得る。 このフレームワークは幅広い問題に有効であると考えています。

関連論文リスト

• An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
  線形損失に対して、動的後悔最小化は、拡張決定空間における静的後悔最小化と等価であることを示す。 R_T(u_1,dots,u_T)le tildeという形式の動的後悔を保証するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-06-03T17:54:58Z)
• Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
  リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。 インスタンス最適性の追求に動機づけられ,我々は新しいアルゴリズムを提案する。 これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
  論文  参考訳（メタデータ） (2023-09-27T21:54:52Z)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• 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)
• Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
  円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。 提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
  論文  参考訳（メタデータ） (2022-05-02T08:48:22Z)
• Universal Online Convex Optimization Meets Second-order Bounds [74.0120666722487]
  ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。 主要なアイデアは、オリジナルのオンライン機能を処理するための専門家のセットを構築し、線形化された損失に対してメタアルゴリズムをデプロイすることである。 このようにして、私たちはブラックボックスの専門家として、既成のオンライン問題解決者をプラグインして、問題依存の後悔の限界を提供することができます。
  論文  参考訳（メタデータ） (2021-05-08T11:43:49Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)

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

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