論文の概要: Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making

• arxiv url: http://arxiv.org/abs/2302.05430v2
• Date: Tue, 19 Mar 2024 15:22:18 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-21 01:40:47.415383
• Title: Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making
• Title（参考訳）: Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making
• Authors: Adam Block, Alexander Rakhlin, Max Simchowitz,
• Abstract要約: この研究は、複雑性という新しい概念、一般化ブラケット数を導入し、空間の大きさに対する敵の制約を結婚させる。 次に、オンライン予測や断片的連続関数の計画など、関心のあるいくつかの問題で境界をインスタンス化する。
• 参考スコア（独自算出の注目度）: 73.48977854003697
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Smoothed online learning has emerged as a popular framework to mitigate the substantial loss in statistical and computational complexity that arises when one moves from classical to adversarial learning. Unfortunately, for some spaces, it has been shown that efficient algorithms suffer an exponentially worse regret than that which is minimax optimal, even when the learner has access to an optimization oracle over the space. To mitigate that exponential dependence, this work introduces a new notion of complexity, the generalized bracketing numbers, which marries constraints on the adversary to the size of the space, and shows that an instantiation of Follow-the-Perturbed-Leader can attain low regret with the number of calls to the optimization oracle scaling optimally with respect to average regret. We then instantiate our bounds in several problems of interest, including online prediction and planning of piecewise continuous functions, which has many applications in fields as diverse as econometrics and robotics.
• Abstract（参考訳）: スムースなオンライン学習は、古典的な学習から逆の学習へと移行するときに生じる統計的および計算的複雑さのかなりの損失を軽減するために人気のあるフレームワークとして現れてきた。 残念なことに、いくつかの空間では、学習者が空間上の最適化オラクルにアクセスできたとしても、効率の良いアルゴリズムが極端に最適であるアルゴリズムよりも指数関数的に悪い後悔を被っていることが示されている。 この指数的依存を緩和するために、この研究は複雑性という新しい概念を導入し、一般ブラケット数(英語版)を導入し、これは空間の大きさに対する敵の制約をマージし、Follow-the-Perturbed-Leaderのインスタンス化が、平均的後悔に対して最適にスケールする最適化オラクルへの呼び出しの数に対して、あまり後悔しないことを示す。 そして、オンラインの予測や断片的連続関数の計画など、関心のあるいくつかの問題で境界をインスタンス化し、計量学やロボット工学のような分野に多くの応用がある。

関連論文リスト

• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• Smoothed Online Learning for Prediction in Piecewise Affine Systems [43.64498536409903]
  本稿では,最近開発されたスムーズなオンライン学習フレームワークに基づく。 これは、断片的なアフィン系における予測とシミュレーションのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-01-26T15:54:14Z)
• Adaptive Oracle-Efficient Online Learning [23.185655992407742]
  オラクル効率のアルゴリズムは指数関数的に大きい決定空間を探索し、どのデータセットでも最善を尽くしたかを選択する。 我々は、オラクル効率が良く、小さな環境に順応する、後続のリーダーアルゴリズムを設計するための新しいフレームワークを提供する。 我々は、オンラインオークションや、近似可能性を保持するトランスダクティブオンライン分類を含む、現実世界の一連の設定を識別する。
  論文  参考訳（メタデータ） (2022-10-17T19:32:30Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。 特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。 以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
  論文  参考訳（メタデータ） (2022-02-08T16:39:57Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for Mixable/Exp-Concave Losses [0.0]
  動的環境における対数的静的後悔を伴う混合損失関数のオンライン最適化について検討する。 文献では,スイッチ1回あたりのほぼ対数的後悔を1時間あたりのポリノミカルな複雑さで達成できることが確認できた。
  論文  参考訳（メタデータ） (2021-09-28T15:06:31Z)
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games [114.90723492840499]
  大規模な2人プレイのゼロサム情報ゲームでは、反事実後悔最小化(cfr)の現代的な拡張がnash均衡を計算するための実用的な技術である。 私たちは、戦略空間がエージェントに知られていないオンライン学習設定を形式化します。 エージェントが逆の環境に直面しても、その設定に高い確率で$O(T3/4)$後悔を達成する効率的なアルゴリズムを提供します。
  論文  参考訳（メタデータ） (2021-03-08T04:03:24Z)
• Learning fine-grained search space pruning and heuristics for combinatorial optimization [5.72274610208488]
  本稿では,機械学習技術を利用して正確な最適化アルゴリズムをスケールアップするフレームワークを提案する。 我々のフレームワークは、問題インスタンスのサイズを減らすために、要素を刈り取るという比較的単純なタスクを学習します。 我々のフレームワークは入力グラフのかなりの部分を取り除き、なおも最大傾きのほとんどを検出可能であることを示す。
  論文  参考訳（メタデータ） (2020-01-05T13:10:39Z)

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

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