論文の概要: Beyond Bandit Feedback in Online Multiclass Classification
- arxiv url: http://arxiv.org/abs/2106.03596v1
- Date: Mon, 7 Jun 2021 13:22:30 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-08 17:48:43.059325
- Title: Beyond Bandit Feedback in Online Multiclass Classification
- Title（参考訳）: オンラインマルチクラス分類におけるバンディットフィードバックを超えて
- Authors: Dirk van der Hoeven and Federico Fusco and Nicol\`o Cesa-Bianchi
- Abstract要約: 学習者のフィードバックが任意の有向グラフによって決定されるような環境で,オンライン多クラス分類の問題について検討する。
任意のフィードバックグラフで動作する,初のオンラインマルチクラスアルゴリズムであるGappletronを紹介する。
- 参考スコア（独自算出の注目度）: 17.07011090727996
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of online multiclass classification in a setting where
the learner's feedback is determined by an arbitrary directed graph. While
including bandit feedback as a special case, feedback graphs allow a much
richer set of applications, including filtering and label efficient
classification. We introduce Gappletron, the first online multiclass algorithm
that works with arbitrary feedback graphs. For this new algorithm, we prove
surrogate regret bounds that hold, both in expectation and with high
probability, for a large class of surrogate losses. Our bounds are of order
$B\sqrt{\rho KT}$, where $B$ is the diameter of the prediction space, $K$ is
the number of classes, $T$ is the time horizon, and $\rho$ is the domination
number (a graph-theoretic parameter affecting the amount of exploration). In
the full information case, we show that Gappletron achieves a constant
surrogate regret of order $B^2K$. We also prove a general lower bound of order
$\max\big\{B^2K,\sqrt{T}\big\}$ showing that our upper bounds are not
significantly improvable. Experiments on synthetic data show that for various
feedback graphs, our algorithm is competitive against known baselines.
- Abstract（参考訳）: 学習者のフィードバックが任意の有向グラフによって決定される設定において,オンライン多クラス分類の問題点について検討する。
特別なケースとしてバンディットフィードバックを含める一方で、フィードバックグラフはフィルタリングやラベルの効率的な分類など、よりリッチなアプリケーションセットを可能にする。
任意のフィードバックグラフで動作する,初のオンラインマルチクラスアルゴリズムであるGappletronを紹介する。
この新しいアルゴリズムでは,大量のサロゲート損失に対して,期待と高い確率の両方で保持される後悔境界を仮定する。
私たちの境界は順に$B\sqrt{\rho KT}$で、$B$は予測空間の直径、$K$はクラスの数、$T$は時間地平線、$\rho$は支配数(探索の量に影響を与えるグラフ理論のパラメータ)である。
完全な情報の場合、gappletron は $b^2k$ の定期的な後悔を成す。
また、位数 $\max\big\{B^2K,\sqrt{T}\big\}$ の一般下界を証明し、上界があまり即効性がないことを示す。
合成データの実験により, 様々なフィードバックグラフに対して, アルゴリズムは既知のベースラインと競合することがわかった。
関連論文リスト
- The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
バンディットフィードバックを用いた複数クラス分類の古典的問題を再考する。
我々は, 後悔すべき$smashwidetildeO(|H|+sqrtT)$を保証する新しい帯域分類アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-16T12:11:09Z) - Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。
複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文 参考訳（メタデータ） (2023-06-05T15:35:00Z) - Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文 参考訳（メタデータ） (2023-05-15T05:37:32Z) - 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) - Multi-armed Bandit Learning on a Graph [0.0]
そこで,エージェントがグラフの上を移動して,異なるノードから収集した報酬を最大化するグラフバンドイットと呼ばれるMABの拡張について検討する。
我々は,楽観主義の原理を用いて長期探査・探索のバランスをとる学習アルゴリズムG-UCBを設計する。
提案アルゴリズムは,ノード数として$O(sqrt|S|Tlog(T)+D|S|log T)$学習後悔を実現する。
論文 参考訳（メタデータ） (2022-09-20T02:31:42Z) - A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with
Feedback Graphs [21.563733343861713]
フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。
本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-01T15:14:32Z) - Littlestone Classes are Privately Online Learnable [28.04975353867202]
プライバシー制約下でのオンライン分類の問題点を考察する。
この設定では、学習者はラベル付き例のストリームを$(x_t, y_t)$, for $1 leq t leq T$で順次観察し、各イテレーションで新しい例のラベルを予測するために使用される仮説$h_t$を返す。
学習者のパフォーマンスは、既知の仮説クラスである$mathcalH$に対する後悔によって測定される。
論文 参考訳（メタデータ） (2021-06-25T09:08:33Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳（メタデータ） (2020-12-10T15:40:07Z) - Exploiting the Surrogate Gap in Online Multiclass Classification [13.452510519858995]
Gaptronは、オンラインのマルチクラス分類のためのランダム化された一階述語アルゴリズムである。
その結果,ロジスティックな損失,ヒンジの損失,スムーズなヒンジの損失に対して,常に後悔する結果が得られた。
ゼロワン損失とサロゲート損失のギャップを利用した新しい証明手法を提案する。
論文 参考訳（メタデータ） (2020-07-24T16:19:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。