論文の概要: Best-Case Lower Bounds in Online Learning

• arxiv url: http://arxiv.org/abs/2106.12688v1
• Date: Wed, 23 Jun 2021 23:24:38 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-25 15:03:36.770769
• Title: Best-Case Lower Bounds in Online Learning
• Title（参考訳）: オンライン学習におけるベストケースローワーバウンダリ
• Authors: Crist\'obal Guzm\'an and Nishant A. Mehta and Ali Mortazavi
• Abstract要約: オンライン学習における研究の多くは、後悔に対する下線上界の研究に焦点を当てている。 本研究では,オンライン凸最適化における最良ケース下界の研究を開始する。 我々はFTRLの線形化バージョンが負の線形後悔を達成できることを示した。
• 参考スコア（独自算出の注目度）: 9.01310450044549
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Much of the work in online learning focuses on the study of sublinear upper bounds on the regret. In this work, we initiate the study of best-case lower bounds in online convex optimization, wherein we bound the largest improvement an algorithm can obtain relative to the single best action in hindsight. This problem is motivated by the goal of better understanding the adaptivity of a learning algorithm. Another motivation comes from fairness: it is known that best-case lower bounds are instrumental in obtaining algorithms for decision-theoretic online learning (DTOL) that satisfy a notion of group fairness. Our contributions are a general method to provide best-case lower bounds in Follow The Regularized Leader (FTRL) algorithms with time-varying regularizers, which we use to show that best-case lower bounds are of the same order as existing upper regret bounds: this includes situations with a fixed learning rate, decreasing learning rates, timeless methods, and adaptive gradient methods. In stark contrast, we show that the linearized version of FTRL can attain negative linear regret. Finally, in DTOL with two experts and binary predictions, we fully characterize the best-case sequences, which provides a finer understanding of the best-case lower bounds.
• Abstract（参考訳）: オンライン学習における研究の多くは、後悔に対する下線上界の研究に焦点を当てている。 本研究は,オンライン凸最適化における最良ケース下界の研究を開始し,アルゴリズムが後から得られる最良動作に対する最大の改善点を定めている。 この問題は、学習アルゴリズムの適応性をよりよく理解することを目的としている。 もうひとつのモチベーションは、グループフェアネスの概念を満たす決定理論オンライン学習(DTOL)のアルゴリズムを得る上で、ベストケースの下位境界が有効であることが知られていることである。 我々のコントリビューションは、Follow The Regularized Leader (FTRL)アルゴリズムに時間変化レギュラーライザを付加する一般的な方法であり、このアルゴリズムは、最良のケースの下位境界が既存の上位の後悔境界と同じ順序であることを示すために使われる。 対照的に、FTRLの線形化バージョンは負の線形後悔を達成できることを示す。 最後に、2人の専門家とバイナリ予測を持つdtolでは、ベストケースシーケンスを完全に特徴付けし、ベストケース下限をより詳細に理解します。

関連論文リスト

• Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
  勾配変分オンライン学習は、オンライン関数の勾配の変化とともにスケールする後悔の保証を達成することを目的としている。 ニューラルネットワーク最適化における最近の取り組みは、一般化された滑らかさ条件を示唆し、滑らかさは勾配ノルムと相関する。 ゲームにおける高速収束と拡張逆最適化への応用について述べる。
  論文  参考訳（メタデータ） (2024-08-17T02:22:08Z)
• Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds [59.875550175217874]
  本稿では,オンラインとオフラインのRL設定において,モデルベース強化学習方式が強い後悔とサンプル境界を実現することを示す。 我々のアルゴリズムは単純で、かなり標準的であり、実際にRLの文献で広く研究されている。
  論文  参考訳（メタデータ） (2024-08-16T19:52:53Z)
• More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning [58.626683114119906]
  本研究では,分散強化学習(DistRL)がオンラインとオフラインのRLの2次境界を得ることができることを示す。 我々の結果は、低ランク MDP とオフライン RL に対する最初の2階境界である。
  論文  参考訳（メタデータ） (2024-02-11T13:25:53Z)
• Learning-Augmented Algorithms for Online Linear and Semidefinite Programming [9.849604820019394]
  Semidefinite Programming (SDP) は線形および二次的に制約されたプログラミングを一般化する統一フレームワークである。 SDPをカバーするための制約がオンラインに届くと、最適解を近似するためには、既知の不可能な結果が存在する。 予測器が正確であれば、これらの不可能な結果を効率よく回避し、最適解に対する定数係数近似を達成できることが示される。
  論文  参考訳（メタデータ） (2022-09-21T19:16:29Z)
• Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm [14.834625066344582]
  対数損失下での逐次的オンライン回帰(シーケンシャル確率代入)について検討する。 我々は、専門家のクラスで発生する過剰な損失として定義される連続したミニマックスの後悔に対して、厳密で、しばしば一致し、下限と上限を得ることに重点を置いている。
  論文  参考訳（メタデータ） (2022-05-07T22:03:00Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning [50.44564503645015]
  有限エピソードマルコフ決定過程における強化学習のための改良されたギャップ依存的後悔境界を提供する。 楽観的なアルゴリズムでは,より強い後悔境界を証明し,多数のMDPに対して新たな情報理論的下限を伴う。
  論文  参考訳（メタデータ） (2021-07-02T20:36:05Z)
• Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversaries [33.53470955144013]
  本論文では,テストタイムの逆数の存在下でのクロスエントロピー損失の最適下限と,それに対応する最適分類出力を決定する。 また、この下界を効率的に計算するベスポークアルゴリズムの正しさの証明を提案し、提案する。 我々は,現在のロバストなトレーニング手法の有効性を判定するための診断ツールとして下限を用い,より大きな予算での最適性とのギャップを見出した。
  論文  参考訳（メタデータ） (2021-04-16T21:41:28Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)

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

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