論文の概要: Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor

• arxiv url: http://arxiv.org/abs/2205.00741v1
• Date: Mon, 2 May 2022 08:48:22 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-03 16:37:49.676645
• Title: Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor
• Title（参考訳）: discounted normal-predictorに基づく平滑化オンライン凸最適化
• Authors: Lijun Zhang, Wei Jiang, Jinfeng Yi, Tianbao Yang
• Abstract要約: 円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。 提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
• 参考スコア（独自算出の注目度）: 68.17855675511602
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we investigate an online prediction strategy named as Discounted-Normal-Predictor (Kapralov and Panigrahy, 2010) for smoothed online convex optimization (SOCO), in which the learner needs to minimize not only the hitting cost but also the switching cost. In the setting of learning with expert advice, Daniely and Mansour (2019) demonstrate that Discounted-Normal-Predictor can be utilized to yield nearly optimal regret bounds over any interval, even in the presence of switching costs. Inspired by their results, we develop a simple algorithm for SOCO: Combining online gradient descent (OGD) with different step sizes sequentially by Discounted-Normal-Predictor. Despite its simplicity, we prove that it is able to minimize the adaptive regret with switching cost, i.e., attaining nearly optimal regret with switching cost on every interval. By exploiting the theoretical guarantee of OGD for dynamic regret, we further show that the proposed algorithm can minimize the dynamic regret with switching cost in every interval.
• Abstract（参考訳）: 本稿では,学習者が打球コストだけでなく,切替コストも最小にする必要がある平滑化オンライン凸最適化(soco)のための,ディスカウント正規予測 (kapralov and panigrahy, 2010) と呼ばれるオンライン予測戦略について検討する。 Daniely and Mansour (2019) は、専門家の助言による学習の設定において、切り換えコストがある場合でも、任意の間隔でほぼ最適な後悔境界が得られることを証明した。 これらの結果に触発されて、オンライン勾配降下(OGD)と異なるステップサイズを順次組み合わせたSOCOの簡単なアルゴリズムを開発した。 その単純さにもかかわらず、スイッチングコストで適応的な後悔を最小化できること、すなわち、間隔ごとにスイッチングコストでほぼ最適の後悔を達成できることを実証する。 さらに,ogdの理論的保証を動的後悔に活用することにより,提案手法が各区間の切り替えコストで動的後悔を最小化できることを示す。

関連論文リスト

• 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)
• Optimal Parameter-free Online Learning with Switching Cost [47.415099037249085]
  オンライン学習における自由とは、後ろ向きの最適決定に対するアルゴリズムの適応性を指す。 本稿では,パラメータフリーで要求される楽観的な更新を,スイッチングコストを前提として,そのようなアルゴリズムを設計する。 本稿では,オンライン線形最適化 (OLO) のための簡易かつ強力なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-13T18:44:27Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR [13.165557713537389]
  我々は、強い適応性(SA)アルゴリズムを、動的後悔を制御するための原則的な方法と見なせることを示した。 我々は,オンラインKernel Ridge Regression(KRR)の最小限の最適性を確立する,ある罰則による新たな下限を導出する。
  論文  参考訳（メタデータ） (2021-11-22T21:52:47Z)
• Revisiting Smoothed Online Learning [70.09792747315323]
  オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。 競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
  論文  参考訳（メタデータ） (2021-02-13T14:15:55Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)
• Minimizing Dynamic Regret and Adaptive Regret Simultaneously [60.17824125301273]
  動的後悔と適応的後悔を同時に最小化できる新しいオンラインアルゴリズムを提案する。 我々の理論的保証は、あるアルゴリズムが任意の間隔で動的後悔を最小化できるという意味でさらに強い。
  論文  参考訳（メタデータ） (2020-02-06T03:32:37Z)

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

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