論文の概要: Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR

• arxiv url: http://arxiv.org/abs/2111.11550v1
• Date: Mon, 22 Nov 2021 21:52:47 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-24 14:13:56.624836
• Title: Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR
• Title（参考訳）: オンラインkrrの強適応法と最適性に対する動的後悔
• Authors: Dheeraj Baby, Hilaf Hasson, Yuyang Wang
• Abstract要約: 我々は、強い適応性(SA)アルゴリズムを、動的後悔を制御するための原則的な方法と見なせることを示した。 我々は,オンラインKernel Ridge Regression(KRR)の最小限の最適性を確立する,ある罰則による新たな下限を導出する。
• 参考スコア（独自算出の注目度）: 13.165557713537389
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the framework of non-stationary Online Convex Optimization where a learner seeks to control its dynamic regret against an arbitrary sequence of comparators. When the loss functions are strongly convex or exp-concave, we demonstrate that Strongly Adaptive (SA) algorithms can be viewed as a principled way of controlling dynamic regret in terms of path variation $V_T$ of the comparator sequence. Specifically, we show that SA algorithms enjoy $\tilde O(\sqrt{TV_T} \vee \log T)$ and $\tilde O(\sqrt{dTV_T} \vee d\log T)$ dynamic regret for strongly convex and exp-concave losses respectively without apriori knowledge of $V_T$. The versatility of the principled approach is further demonstrated by the novel results in the setting of learning against bounded linear predictors and online regression with Gaussian kernels. Under a related setting, the second component of the paper addresses an open question posed by Zhdanov and Kalnishkan (2010) that concerns online kernel regression with squared error losses. We derive a new lower bound on a certain penalized regret which establishes the near minimax optimality of online Kernel Ridge Regression (KRR). Our lower bound can be viewed as an RKHS extension to the lower bound derived in Vovk (2001) for online linear regression in finite dimensions.
• Abstract（参考訳）: 本研究では,学習者が任意のコンパレータ列に対して動的後悔を制御しようとする非定常オンライン凸最適化の枠組みを検討する。 損失関数が強い凸あるいはexp-凹である場合、コンパレータ列の経路変動$V_T$という観点から、強い適応性(SA)アルゴリズムを動的後悔を制御する原理的な方法と見なすことができる。 具体的には、SAアルゴリズムが$\tilde O(\sqrt{TV_T} \vee \log T)$および$\tilde O(\sqrt{dTV_T} \vee d\log T)$ 強い凸とexp-凹の損失に対する動的後悔を、それぞれ$V_T$の予備知識なしで楽しむことを示す。 原理的アプローチの汎用性は、有界線形予測子に対する学習とガウス核を用いたオンライン回帰の新たな結果によってさらに証明される。 関連する設定の下で、論文の第2のコンポーネントは、zhdanov と kalnishkan (2010) が提起した、二乗誤差損失を伴うオンラインカーネル回帰に関するオープン質問に対処している。 我々は、オンラインのKernel Ridge Regression(KRR)の最小限の最適性を確立する、ある罰則による新たな下限を導出する。 我々の下限は、有限次元のオンライン線形回帰に対してvovk (2001) から導かれる下限への rkhs 拡張と見なすことができる。

関連論文リスト

• LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
  敵は、学習者に未知の任意の数kの損失関数を破損させることで、外れ値を導入することができる。 我々は,任意の数kで損失関数を破損させることで,敵が外乱を発生させることができる,頑健なオンラインラウンド最適化フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-08-12T17:08:31Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
  円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。 提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
  論文  参考訳（メタデータ） (2022-05-02T08:48:22Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge [24.880035784304834]
  オンラインリッジ回帰とフォワードアルゴリズムに対して高い確率的後悔境界を導出する。 これにより、オンライン回帰アルゴリズムをより正確に比較し、有界な観測と予測の仮定を排除できる。
  論文  参考訳（メタデータ） (2021-11-02T13:57:53Z)
• Optimal Dynamic Regret in Exp-Concave Online Learning [28.62891856368132]
  我々は、オンライン学習におけるZinkevich(2003)スタイルの動的後悔最小化の問題を検討する。 不適切な学習が許されるたびに、Strongly Adaptive のオンライン学習者は $tilde O(d3.5n1/3C_n2/3 vee dlog n)$ の動的後悔を達成する。 経路の長さ) 学習者が事前に知ることができない任意のコンパレータのシーケンス。
  論文  参考訳（メタデータ） (2021-04-23T21:36:51Z)
• Online nonparametric regression with Sobolev kernels [99.12817345416846]
  我々は、ソボレフ空間のクラス上の後悔の上限を$W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$ とする。 上界は minimax regret analysis で支えられ、$beta> fracd2$ または $p=infty$ の場合、これらの値は(本質的に)最適である。
  論文  参考訳（メタデータ） (2021-02-06T15:05:14Z)
• Adaptive Online Estimation of Piecewise Polynomial Trends [23.91519151164528]
  我々は,2乗誤差損失と雑音勾配フィードバックを伴う非定常最適化の枠組みを考察する。 非パラメトリック回帰理論から動機づけられた新しい変分制約を導入する。 我々は、同じ方針が、他のいくつかの非パラメトリックな関心の族に最適であることを示す。
  論文  参考訳（メタデータ） (2020-09-30T19:30:28Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)

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

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