論文の概要: Online Learning of Halfspaces with Massart Noise

• arxiv url: http://arxiv.org/abs/2405.12958v1
• Date: Tue, 21 May 2024 17:31:10 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-22 12:30:44.656040
• Title: Online Learning of Halfspaces with Massart Noise
• Title（参考訳）: マスアートノイズを伴うハーフスペースのオンライン学習
• Authors: Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis,
• Abstract要約: 我々はMassartノイズの存在下でのオンライン学習の課題について検討する。 計算効率のよいアルゴリズムで, 誤り境界が$eta T + o(T)$であることを示す。 我々はMassartオンライン学習者を用いて、任意のラウンドでランダムなアクションを選択するよりも、少なくとも$(1-1/k) Delta T - o(T)$の報酬を得られる効率的なバンディットアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 47.71073318490341
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the task of online learning in the presence of Massart noise. Instead of assuming that the online adversary chooses an arbitrary sequence of labels, we assume that the context $\mathbf{x}$ is selected adversarially but the label $y$ presented to the learner disagrees with the ground-truth label of $\mathbf{x}$ with unknown probability at most $\eta$. We study the fundamental class of $\gamma$-margin linear classifiers and present a computationally efficient algorithm that achieves mistake bound $\eta T + o(T)$. Our mistake bound is qualitatively tight for efficient algorithms: it is known that even in the offline setting achieving classification error better than $\eta$ requires super-polynomial time in the SQ model. We extend our online learning model to a $k$-arm contextual bandit setting where the rewards -- instead of satisfying commonly used realizability assumptions -- are consistent (in expectation) with some linear ranking function with weight vector $\mathbf{w}^\ast$. Given a list of contexts $\mathbf{x}_1,\ldots \mathbf{x}_k$, if $\mathbf{w}^*\cdot \mathbf{x}_i > \mathbf{w}^* \cdot \mathbf{x}_j$, the expected reward of action $i$ must be larger than that of $j$ by at least $\Delta$. We use our Massart online learner to design an efficient bandit algorithm that obtains expected reward at least $(1-1/k)~ \Delta T - o(T)$ bigger than choosing a random action at every round.
• Abstract（参考訳）: 我々はMassartノイズの存在下でのオンライン学習の課題について検討する。 オンラインの敵対者が任意のラベル列を選択する代わりに、文脈 $\mathbf{x}$ が逆選択されると仮定するが、学習者に提示されるラベル $y$ は、大まかに$\eta$ の確率が未知の基底構造ラベル $\mathbf{x}$ と矛盾する。 我々は$\gamma$-margin線形分類器の基本クラスについて研究し、$\eta T + o(T)$の誤りを解く計算効率の良いアルゴリズムを提案する。 我々のミスバウンダリは、効率的なアルゴリズムに対して質的に厳密である。オフライン設定でも、$\eta$よりも優れた分類誤差を達成するには、SQモデルにおいて超多項式時間が必要であることが知られている。 オンライン学習モデルを$k$-armの文脈的ビジット設定に拡張し、一般的に使用される実現可能性の仮定を満たす代わりに、報酬は、重みベクトル $\mathbf{w}^\ast$ のある線形ランキング関数と一貫性(期待通り)を持つ。 文脈のリスト $\mathbf{x}_1,\ldots \mathbf{x}_k$, if $\mathbf{w}^*\cdot \mathbf{x}_i > \mathbf{w}^* \cdot \mathbf{x}_j$ が与えられた場合、期待されるアクションの報酬$i$は少なくとも$\Delta$によって$j$よりも大きくなければならない。 我々はMassartオンライン学習者を用いて,任意のラウンドでランダムなアクションを選択するよりも,少なくとも$(1-1/k)~ \Delta T - o(T)$の報酬を得られる効率的なバンディットアルゴリズムを設計する。

関連論文リスト

• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
  この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。 重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
  論文  参考訳（メタデータ） (2023-10-18T10:56:57Z)
• A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity [28.068960555415014]
  非定常環境下での線形包帯の固定予算ベストアーム識別問題について検討する。 アルゴリズムは、可能な限り高い確率で最適な腕 $x* := argmax_xinmathcalXxtopsum_t=1Ttheta_t$ を正しく識別することを目的としている。
  論文  参考訳（メタデータ） (2023-07-27T19:03:36Z)
• Online Low Rank Matrix Completion [28.316718791239303]
  我々は,textitonline Low-rank matrix completion with $mathsfM$ users, $mathsfN$ items and $mathsfT roundsについて検討した。 それぞれ、低線形ユーザ-イテム報酬行列からサンプリングされた(自明な)報酬を得る。 提案アルゴリズムは,ユーザをクラスタリングし,アイテムを協調的かつ反復的に除去する新しい手法を用いて,$mathsfT$で最小値に近い最適なレートを得ることができる。
  論文  参考訳（メタデータ） (2022-09-08T18:49:10Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。 我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-09T05:39:05Z)
• The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
  この問題に対して、より優れたブルートフォースアルゴリズムは存在しないことを示す。 また,予測誤差が測定された場合,より優れたブラトフォースアルゴリズムが不可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T14:19:43Z)
• 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)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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