論文の概要: Online Learning with Imperfect Hints

• arxiv url: http://arxiv.org/abs/2002.04726v2
• Date: Fri, 2 Oct 2020 17:28:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-02 02:04:51.667982
• Title: Online Learning with Imperfect Hints
• Title（参考訳）: 不完全なヒントによるオンライン学習
• Authors: Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar and Manish Purohit
• Abstract要約: オンライン学習において,不完全な方向ヒントを用いたアルゴリズムを開発し,ほぼ一致している。 我々のアルゴリズムはヒントの品質を損なうものであり、後悔の限界は常に相関するヒントの場合と隠れない場合とを補間する。
• 参考スコア（独自算出の注目度）: 72.4277628722419
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a variant of the classical online linear optimization problem in which at every step, the online player receives a "hint" vector before choosing the action for that round. Rather surprisingly, it was shown that if the hint vector is guaranteed to have a positive correlation with the cost vector, then the online player can achieve a regret of $O(\log T)$, thus significantly improving over the $O(\sqrt{T})$ regret in the general setting. However, the result and analysis require the correlation property at \emph{all} time steps, thus raising the natural question: can we design online learning algorithms that are resilient to bad hints? In this paper we develop algorithms and nearly matching lower bounds for online learning with imperfect directional hints. Our algorithms are oblivious to the quality of the hints, and the regret bounds interpolate between the always-correlated hints case and the no-hints case. Our results also generalize, simplify, and improve upon previous results on optimistic regret bounds, which can be viewed as an additive version of hints.
• Abstract（参考訳）: 従来のオンライン線形最適化問題(英語版)では、各ステップにおいて、オンラインプレイヤーがそのラウンドのアクションを選択する前に「ヒント」ベクターを受け取る。 むしろ驚くべきことに、ヒントベクトルがコストベクトルと正の相関を持つことが保証された場合、オンラインプレイヤーは$O(\log T)$の後悔を達成でき、一般的な設定では$O(\sqrt{T})$の後悔よりも大幅に改善される。 しかし、結果と分析は、emph{all}の時間ステップで相関性を必要とするため、自然な疑問を提起する: 悪いヒントに耐性のあるオンライン学習アルゴリズムを設計できるだろうか? 本稿では,不完全方向ヒントを用いたオンライン学習のためのアルゴリズムと,ほぼ一致する下限を開発した。 私たちのアルゴリズムはヒントの品質に従わず、常に相関するヒントケースと非ヒットケースの間の後悔の境界を補間します。 この結果はまた、前回の結果を楽観的後悔境界上で一般化し、単純化し、改善し、ヒントの加法バージョンと見なすことができる。

関連論文リスト

• Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees [36.746745619968024]
  本研究では,非定常プロジェクションフリーオンライン学習について検討し,動的後悔と適応的後悔を選択して評価を行った。 我々の結果は、プロジェクションフリーオンライン学習における最初の一般的な動的後悔境界であり、既存の$mathcalO(T3/4)$static regretを復元することができる。 本稿では,$tildemathcalO(tau3/4)$ アダプティブリフレッシュバウンドを長さ$tauの任意の間隔で達成するためのプロジェクションフリーな手法を提案する。
  論文  参考訳（メタデータ） (2023-05-19T15:02:10Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games [36.969021834291745]
  本稿では,仮説クラスの逐次的脂肪散乱次元の観点から,ほぼ最適誤差を導出する固有学習アルゴリズムを提案する。 この結果は、適切な学習者が準最適誤り境界を達成できるかどうかという疑問に答える。 実数値(回帰)設定では、最適誤り境界は不適切な学習者にさえ知られていなかった。
  論文  参考訳（メタデータ） (2021-11-17T05:24:21Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Revisiting Smoothed Online Learning [70.09792747315323]
  オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。 競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
  論文  参考訳（メタデータ） (2021-02-13T14:15:55Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• Optimistic and Adaptive Lagrangian Hedging [11.698607733213226]
  オンライン学習では、アルゴリズムは各ラウンドの敵によって選択される可能性のある損失のある環境と対戦する。 私たちは、後悔マッチングとヘッジを含むオンラインアルゴリズムのクラスであるLagrangian hedgingに楽観と適応的なステップを導入します。
  論文  参考訳（メタデータ） (2021-01-23T23:32:40Z)
• Online Linear Optimization with Many Hints [72.4277628722419]
  本研究では,学習者が決定に先立って各ラウンドでK$"hint"ベクトルにアクセス可能なオンライン線形最適化(OLO)問題について検討する。 この設定では、コストベクトルと正の相関を持つ$K$ヒントの凸結合が存在する場合、対数後悔を求めるアルゴリズムを考案する。
  論文  参考訳（メタデータ） (2020-10-06T23:25:05Z)

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

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