論文の概要: Revisiting Smoothed Online Learning

• arxiv url: http://arxiv.org/abs/2102.06933v1
• Date: Sat, 13 Feb 2021 14:15:55 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-16 15:58:05.402127
• Title: Revisiting Smoothed Online Learning
• Title（参考訳）: Smoothed Online Learningを再考
• Authors: Lijun Zhang, Wei Jiang, Shiyin Lu, Tianbao Yang
• Abstract要約: オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。 競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
• 参考スコア（独自算出の注目度）: 70.09792747315323
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we revisit the problem of smoothed online learning, in which the online learner suffers both a hitting cost and a switching cost, and target two performance metrics: competitive ratio and dynamic regret with switching cost. To bound the competitive ratio, we assume the hitting cost is known to the learner in each round, and investigate the greedy algorithm which simply minimizes the weighted sum of the hitting cost and the switching cost. Our theoretical analysis shows that the greedy algorithm, although straightforward, is $1+ \frac{2}{\alpha}$-competitive for $\alpha$-polyhedral functions, $1+O(\frac{1}{\lambda})$-competitive for $\lambda$-quadratic growth functions, and $1 + \frac{2}{\sqrt{\lambda}}$-competitive for convex and $\lambda$-quadratic growth functions. To bound the dynamic regret with switching cost, we follow the standard setting of online convex optimization, in which the hitting cost is convex but hidden from the learner before making predictions. We modify Ader, an existing algorithm designed for dynamic regret, slightly to take into account the switching cost when measuring the performance. The proposed algorithm, named as Smoothed Ader, attains an optimal $O(\sqrt{T(1+P_T)})$ bound for dynamic regret with switching cost, where $P_T$ is the path-length of the comparator sequence. Furthermore, if the hitting cost is accessible in the beginning of each round, we obtain a similar guarantee without the bounded gradient condition.
• Abstract（参考訳）: 本稿では,オンライン学習者がヒットコストと切り替えコストの両方に苦しむスムーズなオンライン学習の問題を再考し,競争率と切り替えコストに対する動的後悔という2つのパフォーマンス指標を目標とした。 競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。 我々の理論的解析によれば、グリーディアルゴリズムは単純ではあるが、$\alpha$-polyhedral関数の$+ \frac{2}{\alpha}$-competitive、$\lambda$-quadratic成長関数の$+O(\frac{1}{\lambda})$-competitive、$\lambda$-quadratic成長関数の$+ \frac{2}{\sqrt{\lambda}}$-competitive、$\lambda$-quadratic成長関数の$+ \frac{2}{\sqrt{\lambda}}$-competitiveである。 スイッチングコストに対する動的後悔を和らげるために、我々はオンライン凸最適化の標準設定に従い、ヒットコストは凸だが、予測を行う前に学習者から隠蔽される。 動的後悔のために設計された既存のアルゴリズムであるAderを修正し、パフォーマンスを測定する際のスイッチングコストをわずかに考慮します。 提案アルゴリズムはSmoothed Aderと名付けられ, 動的後悔に対して最適な$O(\sqrt{T(1+P_T)})を切替コストで有界とし, コンパレータ列のパス長を$P_T$とする。 さらに,各ラウンドの始めに打上げコストが利用可能であれば,境界勾配条件を使わずに同様の保証が得られる。

関連論文リスト

• Improved Dynamic Regret for Online Frank-Wolfe [52.709213334244495]
  オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。 FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより、OFWの動的後悔境界を改善した。
  論文  参考訳（メタデータ） (2023-02-11T07:19:51Z)
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion [56.92236659731376]
  本稿では,新しい解析手法を用いて,未知の非平滑な目的を最適化するアルゴリズムを提案する。 決定論的二階スムーズな目的のために、先進的な楽観的なオンライン学習技術を適用することで、新しい$O(delta0.5)All$が最適または最もよく知られた結果の回復を可能にする。
  論文  参考訳（メタデータ） (2023-02-07T22:09:20Z)
• Chasing Convex Bodies and Functions with Black-Box Advice [7.895232155155041]
  ブラックボックスアドバイスによる凸関数追跡の問題点を考察する。 オンラインの意思決定者は、$textitConsistency$.com($textitConsistency$.com)と呼ばれる、うまく機能するときにアドバイスに匹敵するコストを求める。 本稿では,この問題の凸性を利用して,この制限を回避できる2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-23T15:30:55Z)
• Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
  円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。 提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
  論文  参考訳（メタデータ） (2022-05-02T08:48:22Z)
• Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond [23.91519151164528]
  適切な学習設定で、Strongly Adaptiveアルゴリズムは、ほぼ最適な動的後悔を実現することができることを示す。 また, 適切なオンライン学習を行う場合, Exp-concaveの損失を伴って, 最適の動的後悔率を導出する。
  論文  参考訳（メタデータ） (2022-01-21T22:08:07Z)
• Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
  連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。 強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
  論文  参考訳（メタデータ） (2021-03-21T11:43:35Z)
• Lazy OCO: Online Convex Optimization on a Switching Budget [26.613126943532357]
  我々は、オンライン凸最適化の変形について研究し、プレイヤーは、T$ラウンドを通して、最大$S$で決定を切り替えることを許されている。 離散的な決定セットの事前の作業や、より最近の連続的な設定では、適応的な逆数でのみ、同様の問題が解決されている。
  論文  参考訳（メタデータ） (2021-02-07T14:47:19Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)
• Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learning [7.6146285961466]
  我々は、すべての$gamma 1$に対して一様に束縛されたサンプル複雑性を持つ新しいアルゴリズムのクラスを導入する。 最適化されたステップサイズシーケンスとQ-ラーニングアルゴリズムの共分散は、1/(1-ガンマ)$の二次関数であることを示す。
  論文  参考訳（メタデータ） (2020-02-24T15:12:41Z)

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

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