論文の概要: A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs

• arxiv url: http://arxiv.org/abs/2206.00557v1
• Date: Wed, 1 Jun 2022 15:14:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-02 12:43:52.695978
• Title: A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs
• Title（参考訳）: フィードバックグラフを用いたオンライン学習のための最適最良両世界のアルゴリズム
• Authors: Chlo\'e Rouyer, Dirk van der Hoeven, Nicol\`o Cesa-Bianchi and Yevgeny Seldin
• Abstract要約: フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。 本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 21.563733343861713
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider online learning with feedback graphs, a sequential decision-making framework where the learner's feedback is determined by a directed graph over the action set. We present a computationally efficient algorithm for learning in this framework that simultaneously achieves near-optimal regret bounds in both stochastic and adversarial environments. The bound against oblivious adversaries is $\tilde{O} (\sqrt{\alpha T})$, where $T$ is the time horizon and $\alpha$ is the independence number of the feedback graph. The bound against stochastic environments is $O\big( (\ln T)^2 \max_{S\in \mathcal I(G)} \sum_{i \in S} \Delta_i^{-1}\big)$ where $\mathcal I(G)$ is the family of all independent sets in a suitably defined undirected version of the graph and $\Delta_i$ are the suboptimality gaps. The algorithm combines ideas from the EXP3++ algorithm for stochastic and adversarial bandits and the EXP3.G algorithm for feedback graphs with a novel exploration scheme. The scheme, which exploits the structure of the graph to reduce exploration, is key to obtain best-of-both-worlds guarantees with feedback graphs. We also extend our algorithm and results to a setting where the feedback graphs are allowed to change over time.
• Abstract（参考訳）: 学習者のフィードバックを行動セット上の有向グラフによって決定するシーケンシャルな意思決定フレームワークであるフィードバックグラフを用いたオンライン学習を考える。 本稿では,確率環境と逆環境の両方において,最適に近い後悔領域を同時に達成する,計算効率の高い学習アルゴリズムを提案する。 悪意のある敵に対する境界は$\tilde{o} (\sqrt{\alpha t})$であり、ここで$t$は時間軸、$\alpha$はフィードバックグラフの独立数である。 確率環境に対するバウンドは$O\big( (\ln T)^2 \max_{S\in \mathcal I(G)} \sum_{i \in S} \Delta_i^{-1}\big)$である。 このアルゴリズムは、確率的および逆の帯域幅に対するEXP3++アルゴリズムと、フィードバックグラフのためのEXP3.Gアルゴリズムと、新しい探索スキームを組み合わせたものである。 探索を減らすためにグラフの構造を利用するこのスキームは、フィードバックグラフで最高の世界を保証するための鍵となる。 また、アルゴリズムと結果を、フィードバックグラフが時間とともに変更できるような設定に拡張します。

関連論文リスト

• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。 提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
  論文  参考訳（メタデータ） (2024-08-03T20:08:02Z)
• Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
  ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。 複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
  論文  参考訳（メタデータ） (2023-06-05T15:35:00Z)
• Learning on the Edge: Online Learning with Stochastic Feedback Graphs [12.83118601099289]
  有向フィードバックグラフが帯域幅を持つ拡張について検討する。 グラフの各ラウンドにおいて、グラフの各エッジは、それぞれのエッジに対して異なる確率で実現されるか、実現されないかのいずれかである。 我々は、独立性の重み付けされたバージョンと弱い支配数に依存する、より効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2022-10-09T11:21:08Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。 提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。 また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T04:36:15Z)
• Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedback [15.429356827868514]
  一般フィードバックグラフの探索と活用のための新たなトレードオフ機構を導入する。 提案アルゴリズムは,対数設定において,$mathrmpoly-designed log T$ regretを同時に達成する。 これは、一般のフィードバックグラフに対する世界で初めての最良の結果である。
  論文  参考訳（メタデータ） (2022-06-16T04:21:27Z)
• Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs [34.37963000493442]
  本研究では,汎用的なフィードバックグラフを用いたオンライン学習について考察する。 両世界のベスト・オブ・ワールドズ・アルゴリズムは、敵の環境に対してほぼ厳密な後悔の限界を達成できる。
  論文  参考訳（メタデータ） (2022-06-02T05:01:40Z)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。 我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-09T05:39:05Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。 既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。 そこで本研究では,学習可能なグラフマッチング手法を提案する。
  論文  参考訳（メタデータ） (2021-03-30T08:58:45Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。 我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。 これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
  論文  参考訳（メタデータ） (2021-01-28T02:39:27Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)

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

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