論文の概要: Learning on the Edge: Online Learning with Stochastic Feedback Graphs
- arxiv url: http://arxiv.org/abs/2210.04229v1
- Date: Sun, 9 Oct 2022 11:21:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-11 19:32:58.114369
- Title: Learning on the Edge: Online Learning with Stochastic Feedback Graphs
- Title（参考訳）: エッジでの学習:確率的フィードバックグラフによるオンライン学習
- Authors: Emmanuel Esposito, Federico Fusco, Dirk van der Hoeven, Nicol\`o
Cesa-Bianchi
- Abstract要約: 有向フィードバックグラフが帯域幅を持つ拡張について検討する。
グラフの各ラウンドにおいて、グラフの各エッジは、それぞれのエッジに対して異なる確率で実現されるか、実現されないかのいずれかである。
我々は、独立性の重み付けされたバージョンと弱い支配数に依存する、より効率的なアルゴリズムを導出する。
- 参考スコア（独自算出の注目度）: 12.83118601099289
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The framework of feedback graphs is a generalization of sequential
decision-making with bandit or full information feedback. In this work, we
study an extension where the directed feedback graph is stochastic, following a
distribution similar to the classical Erd\H{o}s-R\'enyi model. Specifically, in
each round every edge in the graph is either realized or not with a distinct
probability for each edge. We prove nearly optimal regret bounds of order
$\min\bigl\{\min_{\varepsilon} \sqrt{(\alpha_\varepsilon/\varepsilon) T},\,
\min_{\varepsilon} (\delta_\varepsilon/\varepsilon)^{1/3} T^{2/3}\bigr\}$
(ignoring logarithmic factors), where $\alpha_{\varepsilon}$ and
$\delta_{\varepsilon}$ are graph-theoretic quantities measured on the support
of the stochastic feedback graph $\mathcal{G}$ with edge probabilities
thresholded at $\varepsilon$. Our result, which holds without any preliminary
knowledge about $\mathcal{G}$, requires the learner to observe only the
realized out-neighborhood of the chosen action. When the learner is allowed to
observe the realization of the entire graph (but only the losses in the
out-neighborhood of the chosen action), we derive a more efficient algorithm
featuring a dependence on weighted versions of the independence and weak
domination numbers that exhibits improved bounds for some special cases.
- Abstract（参考訳）: フィードバックグラフの枠組みは、バンディットや全情報フィードバックによる逐次意思決定の一般化である。
本研究では,古典的 Erd\H{o}s-R\enyi モデルに類似した分布に従って,有向フィードバックグラフが確率的となる拡張について検討する。
具体的には、グラフの各辺は、それぞれの辺に対して異なる確率で実現されるか、実現されないかのいずれかである。
位数 $\min\bigl\{\min_{\varepsilon} \sqrt{(\alpha_\varepsilon/\varepsilon) T},\, \min_{\varepsilon} (\delta_\varepsilon/\varepsilon)^{1/3} T^{2/3}\bigr\}$(対数因子を無視した)$$$\alpha_{\varepsilon}$と$\delta_{\varepsilon}$は確率的フィードバックグラフ $\mathcal{G}$の支持で測定されたグラフ理論量である。
我々の結果は、$\mathcal{G}$に関する予備的な知識を持たないもので、学習者は、選択されたアクションの実際の外部のみを観察する必要がある。
学習者がグラフ全体の実現(ただし、選択された行動の外部での損失のみ)を観察できる場合、より効率的なアルゴリズムが導出され、独立性の重み付けされたバージョンといくつかの特別なケースで改善された境界を示す弱い支配数に依存する。
関連論文リスト
- Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。
複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文 参考訳（メタデータ） (2023-06-05T15:35:00Z) - 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) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - 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) - A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with
Feedback Graphs [21.563733343861713]
フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。
本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-01T15:14:32Z) - Improved Reconstruction of Random Geometric Graphs [3.930410971186142]
ランダムな幾何グラフの古典的モデルを考えると、$n$の点が一様に領域$n$の正方形に散らばっている。
グラフ距離と近距離推定のハイブリッドを用いてユークリッド距離を推定する。
本手法は, グラフ距離と近辺点数に基づく短距離推定のハイブリッドを用いてユークリッド距離を推定する。
論文 参考訳（メタデータ） (2021-07-29T20:37:28Z) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳（メタデータ） (2020-12-10T15:40:07Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。