論文の概要: Optimal Dynamic Regret in Exp-Concave Online Learning

• arxiv url: http://arxiv.org/abs/2104.11824v1
• Date: Fri, 23 Apr 2021 21:36:51 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-27 14:52:02.381464
• Title: Optimal Dynamic Regret in Exp-Concave Online Learning
• Title（参考訳）: Exp-Concaveオンライン学習における最適動的レグレット
• Authors: Dheeraj Baby and Yu-Xiang Wang
• Abstract要約: 我々は、オンライン学習におけるZinkevich(2003)スタイルの動的後悔最小化の問題を検討する。 不適切な学習が許されるたびに、Strongly Adaptive のオンライン学習者は $tilde O(d3.5n1/3C_n2/3 vee dlog n)$ の動的後悔を達成する。 経路の長さ) 学習者が事前に知ることができない任意のコンパレータのシーケンス。
• 参考スコア（独自算出の注目度）: 28.62891856368132
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We consider the problem of the Zinkevich (2003)-style dynamic regret minimization in online learning with exp-concave losses. We show that whenever improper learning is allowed, a Strongly Adaptive online learner achieves the dynamic regret of $\tilde O(d^{3.5}n^{1/3}C_n^{2/3} \vee d\log n)$ where $C_n$ is the total variation (a.k.a. path length) of the an arbitrary sequence of comparators that may not be known to the learner ahead of time. Achieving this rate was highly nontrivial even for squared losses in 1D where the best known upper bound was $O(\sqrt{nC_n} \vee \log n)$ (Yuan and Lamperski, 2019). Our new proof techniques make elegant use of the intricate structures of the primal and dual variables imposed by the KKT conditions and could be of independent interest. Finally, we apply our results to the classical statistical problem of locally adaptive non-parametric regression (Mammen, 1991; Donoho and Johnstone, 1998) and obtain a stronger and more flexible algorithm that do not require any statistical assumptions or any hyperparameter tuning.
• Abstract（参考訳）: 我々は,exp-concave損失を伴うオンライン学習におけるzinkevich(2003)スタイルの動的後悔最小化の問題を考える。 不適切な学習が許されるたびに、Strongly Adaptiveオンライン学習者は、$\tilde O(d^{3.5}n^{1/3}C_n^{2/3} \vee d\log n)$の動的後悔(a.k.a.a.)を達成する。 経路の長さ) 学習者が事前に知ることができない任意のコンパレータのシーケンス。 1Dでは最もよく知られている上限が$O(\sqrt{nC_n} \vee \log n)$ (Yuan and Lamperski, 2019)であった。 我々の新しい証明手法はkkt条件によって課される原始変数と双対変数の複雑な構造をエレガントに利用し、独立した興味を持つことができる。 最後に,局所適応非パラメトリック回帰(mammen, 1991, donoho and johnstone, 1998)の古典的統計問題に適用し,統計的仮定やハイパーパラメータチューニングを必要としない,より強固で柔軟なアルゴリズムを得る。

関連論文リスト

• Highly Adaptive Ridge [84.38107748875144]
  直交可積分な部分微分を持つ右連続函数のクラスにおいて,$n-2/3$自由次元L2収束率を達成する回帰法を提案する。 Harは、飽和ゼロオーダーテンソル積スプライン基底展開に基づいて、特定のデータ適応型カーネルで正確にカーネルリッジレグレッションを行う。 我々は、特に小さなデータセットに対する最先端アルゴリズムよりも経験的性能が優れていることを示す。
  論文  参考訳（メタデータ） (2024-10-03T17:06:06Z)
• 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 Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
  線形関数近似による強化学習と,コスト関数の逆変化について検討した。 本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T17:26:39Z)
• Optimal Dynamic Regret in LQR Control [23.91519151164528]
  我々は、LQR制御という2次的損失の連続を伴う非確率的制御の問題を考察する。 我々は、$tildeO(textmaxn1/3 MathcalTV(M_1:n)2/3, 1)$の最適動的(政治的)後悔を実現するオンラインアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-06-18T18:00:21Z)
• Second Order Path Variationals in Non-Stationary Online Learning [23.91519151164528]
  設計したStrongly Adaptiveアルゴリズムは$tilde O(d2 n1/5 C_n2/5 vee d2)$の動的後悔を実現する。 上記の動的後悔率は、最適モジュラー次元依存およびn$の多対数因子であることが示されている。
  論文  参考訳（メタデータ） (2022-05-04T07:14:39Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
  論文  参考訳（メタデータ） (2022-03-30T11:39:00Z)
• Scale-free Unconstrained Online Learning for Curved Losses [1.5147172044848798]
  コンパレータのノルム$U$と勾配の最大ノルム$G$に同時に適応する可能性を検討する。 意外なことに、最近の研究では1ドル=Lipschitz損失の特定のケースにおいて、適応性に対するそのような価格が不要であることが示されている。
  論文  参考訳（メタデータ） (2022-02-11T14:10:35Z)
• Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond [23.91519151164528]
  適切な学習設定で、Strongly Adaptiveアルゴリズムは、ほぼ最適な動的後悔を実現することができることを示す。 また, 適切なオンライン学習を行う場合, Exp-concaveの損失を伴って, 最適の動的後悔率を導出する。
  論文  参考訳（メタデータ） (2022-01-21T22:08:07Z)
• Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR [13.165557713537389]
  我々は、強い適応性(SA)アルゴリズムを、動的後悔を制御するための原則的な方法と見なせることを示した。 我々は,オンラインKernel Ridge Regression(KRR)の最小限の最適性を確立する,ある罰則による新たな下限を導出する。
  論文  参考訳（メタデータ） (2021-11-22T21:52:47Z)
• Strongly Adaptive OCO with Memory [49.319621885036035]
  本稿では,メモリを用いたオンライン学習のための適応型アルゴリズムを提案する。 このアルゴリズムは,線形時間変化システムの制御に強い適応性を持つリセットバウンドをもたらす。
  論文  参考訳（メタデータ） (2021-02-02T17:26:08Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)

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

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