論文の概要: Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs
- arxiv url: http://arxiv.org/abs/2107.09572v1
- Date: Tue, 20 Jul 2021 15:39:42 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-21 14:55:00.300595
- Title: Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs
- Title（参考訳）: フィードバックグラフを用いたオンライン学習のための世界ベストバウンド
- Authors: Liad Erez, Tomer Koren
- Abstract要約: Mannor and Shamir (2011) が導入したフィードバックグラフフレームワークを用いてオンライン学習について検討し、オンライン学習者からのフィードバックを利用可能なアクションに対してグラフ$G$で指定する。
逆損失を持つ$smashmathcalO(sqrttheta(G) T)$、逆損失を持つ$mathcalO(theta(G)operatornamepolylogT)$、逆損失を持つ$mathcalO(theta)。
- 参考スコア（独自算出の注目度）: 26.613126943532357
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the online learning with feedback graphs framework introduced by
Mannor and Shamir (2011), in which the feedback received by the online learner
is specified by a graph $G$ over the available actions. We develop an algorithm
that simultaneously achieves regret bounds of the form:
$\smash{\mathcal{O}(\sqrt{\theta(G) T})}$ with adversarial losses;
$\mathcal{O}(\theta(G)\operatorname{polylog}{T})$ with stochastic losses; and
$\mathcal{O}(\theta(G)\operatorname{polylog}{T} + \smash{\sqrt{\theta(G) C})}$
with stochastic losses subject to $C$ adversarial corruptions. Here,
$\theta(G)$ is the clique covering number of the graph $G$. Our algorithm is an
instantiation of Follow-the-Regularized-Leader with a novel regularization that
can be seen as a product of a Tsallis entropy component (inspired by Zimmert
and Seldin (2019)) and a Shannon entropy component (analyzed in the corrupted
stochastic case by Amir et al. (2020)), thus subtly interpolating between the
two forms of entropies. One of our key technical contributions is in
establishing the convexity of this regularizer and controlling its inverse
Hessian, despite its complex product structure.
- Abstract（参考訳）: Mannor and Shamir (2011) が導入したフィードバックグラフフレームワークを用いてオンライン学習について検討し、オンライン学習者からのフィードバックを利用可能なアクションに対してグラフ$G$で指定する。
逆数損失を持つ$$\mathcal{O}(\theta(G)\operatorname{polylog}{T})$、確率的損失を持つ$\mathcal{O}(\theta(G)\operatorname{polylog}{T})$、確率的損失を持つ$\mathcal{O}(\theta(G)\operatorname{polylog}{T} + \smash{\sqrt{\theta(G)C})}$。
ここで、$\theta(G)$ はグラフ $G$ のclique被覆数である。
このアルゴリズムは, Tsallis エントロピー成分 (Zimmert and Seldin (2019) に触発された) と Shannon エントロピー成分 (Amir et al の劣化確率論的ケースで解析された) の積として見ることのできる, 新規な正規化によるFollow-the-Regularized-Leader のインスタンス化である。
(2020) は2つのエントロピーの形式の間を微妙に補間する。
我々の重要な技術的貢献の1つは、複雑な積構造にもかかわらず、この正則化器の凸性を確立し、その逆 Hessian を制御することである。
関連論文リスト
- Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - 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) - Best-of-Both-Worlds Algorithms for Partial Monitoring [34.37963000493442]
非退化したグローバル可観測ゲームでは、レジームの後悔は$O(k3 m2 log(k_Pi T) / Delta_min2)$で制限される。
我々のアルゴリズムは、フィードバックグラフを用いたオンライン学習の分野におけるアルゴリズムにインスパイアされた、フォロー・ザ・レギュラライズド・リーダー・フレームワークに基づいている。
論文 参考訳（メタデータ） (2022-07-29T08:40:05Z) - A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with
Feedback Graphs [21.563733343861713]
フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。
本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-01T15:14:32Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳（メタデータ） (2020-12-10T15:40:07Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - Optimal Contextual Pricing and Extensions [32.152826900874075]
このアルゴリズムは$Omega(d log T)$ lower bound up to the $d log d$ additive factor。
これらのアルゴリズムは、凸領域のスタイナー固有値を様々なスケールで有界化する新しい手法に基づいている。
論文 参考訳（メタデータ） (2020-03-03T18:46:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。