論文の概要: Delaytron: Efficient Learning of Multiclass Classifiers with Delayed Bandit Feedbacks

• arxiv url: http://arxiv.org/abs/2205.08234v1
• Date: Tue, 17 May 2022 11:12:20 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-18 20:16:59.497664
• Title: Delaytron: Efficient Learning of Multiclass Classifiers with Delayed Bandit Feedbacks
• Title（参考訳）: Delaytron: 遅延帯域フィードバックを持つマルチクラス分類器の効率的な学習
• Authors: Naresh Manwani, Mudit Agarwal
• Abstract要約: Adaptive Delaytronは、$mathcalOleft(sqrtfrac2 Kgammaleft[fracT2+left(2+fracL2R2Vert WVert_F2right)sum_t=1Td_tright)の後悔の限界を達成する。 我々は、Adaptive Delaytronが$mathcalOleft(sqrtfrac2 Kgammaleft[fracT2]の後悔の限界を達成することを示す。
• 参考スコア（独自算出の注目度）: 6.624726878647541
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we present online algorithm called {\it Delaytron} for learning multi class classifiers using delayed bandit feedbacks. The sequence of feedback delays $\{d_t\}_{t=1}^T$ is unknown to the algorithm. At the $t$-th round, the algorithm observes an example $\mathbf{x}_t$ and predicts a label $\tilde{y}_t$ and receives the bandit feedback $\mathbb{I}[\tilde{y}_t=y_t]$ only $d_t$ rounds later. When $t+d_t>T$, we consider that the feedback for the $t$-th round is missing. We show that the proposed algorithm achieves regret of $\mathcal{O}\left(\sqrt{\frac{2 K}{\gamma}\left[\frac{T}{2}+\left(2+\frac{L^2}{R^2\Vert \W\Vert_F^2}\right)\sum_{t=1}^Td_t\right]}\right)$ when the loss for each missing sample is upper bounded by $L$. In the case when the loss for missing samples is not upper bounded, the regret achieved by Delaytron is $\mathcal{O}\left(\sqrt{\frac{2 K}{\gamma}\left[\frac{T}{2}+2\sum_{t=1}^Td_t+\vert \mathcal{M}\vert T\right]}\right)$ where $\mathcal{M}$ is the set of missing samples in $T$ rounds. These bounds were achieved with a constant step size which requires the knowledge of $T$ and $\sum_{t=1}^Td_t$. For the case when $T$ and $\sum_{t=1}^Td_t$ are unknown, we use a doubling trick for online learning and proposed Adaptive Delaytron. We show that Adaptive Delaytron achieves a regret bound of $\mathcal{O}\left(\sqrt{T+\sum_{t=1}^Td_t}\right)$. We show the effectiveness of our approach by experimenting on various datasets and comparing with state-of-the-art approaches.
• Abstract（参考訳）: 本稿では,遅延バンディットフィードバックを用いたマルチクラス分類学習のためのオンラインアルゴリズム「it delaytron」を提案する。 フィードバック遅延の列 $\{d_t\}_{t=1}^t$ はアルゴリズムに未知である。 このアルゴリズムは、$t$-th ラウンドで、例 $\mathbf{x}_t$ を観察し、ラベル $\tilde{y}_t$ を予測し、後でバンドイットフィードバック $\mathbb{I}[\tilde{y}_t=y_t]$ のみ$d_t$ ラウンドを受信する。 $t+d_t>T$の場合、$t$-thラウンドのフィードバックが欠落していると考えています。 提案アルゴリズムは,各欠落サンプルの損失が$L$の上限値である場合に,$\mathcal{O}\left(\sqrt {\frac{2K}{\gamma}\left[\frac{T}{2}+\left(2+\frac{L^2}{R^2\Vert \W\Vert_F^2}\right)\sum_{t=1}^Td_t\right]}\right)を後悔することを示す。 欠失サンプルの損失が上限値になっていない場合、delaytronが達成した後悔は$\mathcal{o}\left(\sqrt{\frac{2 k}{\gamma}\left[\frac{t}{2}+2\sum_{t=1}^td_t+\vert \mathcal{m}\vert t\right]}\right)$である。 これらの境界は一定のステップサイズで達成され、これは$T$と$\sum_{t=1}^Td_t$の知識を必要とする。 T$と$\sum_{t=1}^Td_t$が未知の場合、オンライン学習に2倍のトリックを使用し、Adaptive Delaytronを提案する。 Adaptive Delaytron は $\mathcal{O}\left(\sqrt{T+\sum_{t=1}^Td_t}\right)$ の残差を持つことを示す。 各種データセットを実験し,最先端のアプローチと比較することにより,提案手法の有効性を示す。

関連論文リスト

• Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
  未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。 我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。 このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
  論文  参考訳（メタデータ） (2024-02-22T02:20:24Z)
• Matrix Completion in Almost-Verification Time [37.61139884826181]
  99%の行と列で$mathbfM$を完了するアルゴリズムを提供する。 本稿では,この部分完備保証を完全行列補完アルゴリズムに拡張する方法を示す。
  論文  参考訳（メタデータ） (2023-08-07T15:24:49Z)
• 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)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• 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)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。 Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
  論文  参考訳（メタデータ） (2020-05-22T16:55:01Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)
• Adaptive Online Learning with Varying Norms [45.11667443216861]
  オンライン凸最適化アルゴリズムは、あるドメインで$w_t$を出力する。 この結果を用いて新しい「完全行列」型後悔境界を得る。
  論文  参考訳（メタデータ） (2020-02-10T17:22:08Z)

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

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