論文の概要: Isotuning With Applications To Scale-Free Online Learning

• arxiv url: http://arxiv.org/abs/2112.14586v1
• Date: Wed, 29 Dec 2021 14:58:56 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-30 14:45:39.446003
• Title: Isotuning With Applications To Scale-Free Online Learning
• Title（参考訳）: スケールフリーオンラインラーニングへの応用による等質化
• Authors: Laurent Orseau, Marcus Hutter
• Abstract要約: 高速で適応的で、いつでも、スケールフリーなオンライン学習アルゴリズムを設計するためのツールを開発しています。 最初の、そして主要なツールであるisotuningは、後悔のトレードオフのバランスをとるという考え方の一般化です。 第2のツールはオンラインの修正であり、多くのアルゴリズムで中心となる境界を求めることができる。 最後のツールはnullアップデートであり、アルゴリズムが過度に大規模な更新を行うのを防ぐ。
• 参考スコア（独自算出の注目度）: 32.79776733870005
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We extend and combine several tools of the literature to design fast, adaptive, anytime and scale-free online learning algorithms. Scale-free regret bounds must scale linearly with the maximum loss, both toward large losses and toward very small losses. Adaptive regret bounds demonstrate that an algorithm can take advantage of easy data and potentially have constant regret. We seek to develop fast algorithms that depend on as few parameters as possible, in particular they should be anytime and thus not depend on the time horizon. Our first and main tool, isotuning, is a generalization of the idea of balancing the trade-off of the regret. We develop a set of tools to design and analyze such learning rates easily and show that they adapts automatically to the rate of the regret (whether constant, $O(\log T)$, $O(\sqrt{T})$, etc.) within a factor 2 of the optimal learning rate in hindsight for the same observed quantities. The second tool is an online correction, which allows us to obtain centered bounds for many algorithms, to prevent the regret bounds from being vacuous when the domain is overly large or only partially constrained. The last tool, null updates, prevents the algorithm from performing overly large updates, which could result in unbounded regret, or even invalid updates. We develop a general theory using these tools and apply it to several standard algorithms. In particular, we (almost entirely) restore the adaptivity to small losses of FTRL for unbounded domains, design and prove scale-free adaptive guarantees for a variant of Mirror Descent (at least when the Bregman divergence is convex in its second argument), extend Adapt-ML-Prod to scale-free guarantees, and provide several other minor contributions about Prod, AdaHedge, BOA and Soft-Bayes.
• Abstract（参考訳）: 我々は、高速で適応的で、いつでも、スケールフリーなオンライン学習アルゴリズムを設計するために、文学のいくつかのツールを拡張し、組み合わせます。 スケールフリーの後悔境界は、大きな損失と非常に小さな損失の両方に対して、最大損失とともに直線的にスケールしなければならない。 適応的後悔境界(Adaptive regret bounds)は、アルゴリズムが簡単なデータを利用して、繰り返し後悔する可能性があることを示す。 我々は、できるだけ少数のパラメータに依存する高速なアルゴリズム、特にそれらはいつでも存在すべきであり、したがって時間軸に依存しないアルゴリズムの開発を目指している。 私たちの最初の主要なツールは、後悔のトレードオフのバランスをとるという考え方の一般化です。 このような学習率の設計と分析を容易にするツールセットを開発し,後悔率(定数,$o(\log t)$,$o(\sqrt{t})$など)に自動的に適応することを示す。 ) 同一の観測量に対する後視における最適学習率の2因子以内であった。 2つめのツールはオンライン修正で、多くのアルゴリズムで中心境界を得ることができ、ドメインが大きすぎるか、一部しか制約されていない場合に、後悔境界が空白になることを防ぐ。 最後のツールであるnull updateは、アルゴリズムが過度に大規模な更新を実行できないようにする。 我々はこれらのツールを用いて一般的な理論を開発し、いくつかの標準アルゴリズムに適用する。 特に、(ほぼ完全に)非有界領域に対するFTRLの小さな損失に対する適応性を復元し、ミラー・ディクセントの変種に対するスケールフリー適応保証(少なくとも第2引数においてブレグマン偏差が凸である場合)を設計し、証明し、Adapt-ML-Prodをスケールフリー保証に拡張し、Prod、AdaHedge、BOA、Soft-Bayesに関するいくつかの小さな貢献を提供する。

関連論文リスト

• Computing Optimal Regularizers for Online Linear Optimization [38.72709491927979]
  FTRL(Follow-the-Regularized-Leader)アルゴリズムはオンライン線形最適化(OLO)のための一般的な学習アルゴリズムである。 本稿では,最良学習アルゴリズムの一定要素内における後悔を実現するFTRLのインスタンス化が存在することを示す。
  論文  参考訳（メタデータ） (2024-10-22T18:10:50Z)
• Meta-Learning Adversarial Bandit Algorithms [55.72892209124227]
  我々は,バンディットフィードバックを用いたオンラインメタラーニングについて研究する。 我々は自己協和障壁正規化器を用いてオンラインミラー降下一般化(OMD)をチューニングすることを学ぶ。
  論文  参考訳（メタデータ） (2023-07-05T13:52:10Z)
• Riemannian Projection-free Online Learning [5.918057694291832]
  プロジェクション操作は、オンライン勾配降下(OGD)のような最適化アルゴリズムにおける重要な要素である。 これは高次元の設定における計算上の制限や、不条件の制約セットを扱う際に悩まされる。 本稿では,曲面空間上でのオンライン測地線凸最適化において,線形後悔の保証を得る手法を提案する。
  論文  参考訳（メタデータ） (2023-05-30T18:22:09Z)
• Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Arms [41.06668954462585]
  本研究では,適応型マルチアームバンディットアルゴリズムを設計する際の課題について検討する。 FTRLには多種多様な正規化要因と新たな学習率スケジュールが不要であることを示す。
  論文  参考訳（メタデータ） (2023-02-27T06:09:10Z)
• Improved Online Conformal Prediction via Strongly Adaptive Online Learning [86.4346936885507]
  我々は、強い適応的後悔を最小限に抑える新しいオンライン共形予測手法を開発した。 提案手法は,すべての区間において,ほぼ最適に適応的な後悔を同時に達成できることを実証する。 実験により,本手法は実世界のタスクにおける既存の手法よりも,より優れたカバレッジと予測セットが得られることがわかった。
  論文  参考訳（メタデータ） (2023-02-15T18:59:30Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Online estimation and control with optimal pathlength regret [52.28457815067461]
  オンライン学習アルゴリズムを設計する際の自然なゴールは、入力シーケンスの時間的変動の観点から、アルゴリズムの後悔を束縛することである。 OCOや盗賊など、さまざまなオンライン学習問題に対して、データ依存の「病的」後悔境界が最近取得されている。
  論文  参考訳（メタデータ） (2021-10-24T22:43:15Z)
• Universal Online Convex Optimization Meets Second-order Bounds [74.0120666722487]
  ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。 主要なアイデアは、オリジナルのオンライン機能を処理するための専門家のセットを構築し、線形化された損失に対してメタアルゴリズムをデプロイすることである。 このようにして、私たちはブラックボックスの専門家として、既成のオンライン問題解決者をプラグインして、問題依存の後悔の限界を提供することができます。
  論文  参考訳（メタデータ） (2021-05-08T11:43:49Z)
• Optimistic and Adaptive Lagrangian Hedging [11.698607733213226]
  オンライン学習では、アルゴリズムは各ラウンドの敵によって選択される可能性のある損失のある環境と対戦する。 私たちは、後悔マッチングとヘッジを含むオンラインアルゴリズムのクラスであるLagrangian hedgingに楽観と適応的なステップを導入します。
  論文  参考訳（メタデータ） (2021-01-23T23:32:40Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)

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

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