論文の概要: Efficiently Learning Drifting Halfspaces with Massart Noise

• arxiv url: http://arxiv.org/abs/2606.11149v1
• Date: Tue, 09 Jun 2026 17:35:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-10 15:40:58.648335
• Title: Efficiently Learning Drifting Halfspaces with Massart Noise
• Title（参考訳）: マスアート雑音によるドリフト半空間の学習
• Authors: Mingchen Ma, Guyang Cao, Jelena Diakonikolas, Ilias Diakonikolas,
• Abstract要約: 本研究では,マッサートノイズの存在下での漂流概念の学習問題について検討する。 このフレームワークでは、オンライン学習者は独立したサンプルの履歴にアクセスすることができる。 目標は、各ラウンドで小さな予測誤差の仮説を出力することである。
• 参考スコア（独自算出の注目度）: 50.4331323695175
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of learning a drifting concept in the presence of Massart noise. In this framework, an online learner has access to a history of independent samples whose labels are noisy versions of a target concept that may change from round to round. The goal is to output, in each round, a hypothesis with small prediction error. We study the complexity of this learning problem for the fundamental class of margin-separable linear classifiers (halfspaces). On the positive side, we give a computationally efficient learner achieving error $η+ \tilde O(Δ^{1/3}/γ)$, where $η$ upper bounds the Massart noise rate, $Δ$ is the drift rate, and $γ$ is the margin. Interestingly, in the realizable setting, an adaptation of our techniques yields an efficient learner with an improved error rate over prior work. On the lower-bound side, we provide formal evidence of an information-computation tradeoff, strongly suggesting that our algorithm's performance is essentially optimal. Specifically, while the information-theoretically optimal error scales with $Δ^{1/2}$, we prove that $Δ^{1/3}$-scaling is unavoidable for low-degree polynomial tests, even in the special case of random classification noise.
• Abstract（参考訳）: 本研究では,マッサートノイズの存在下での漂流概念の学習問題について検討する。 このフレームワークでは、オンライン学習者は、ラウンドからラウンドへと変化する可能性のあるターゲット概念のノイズの多いバージョンであるラベルを持つ独立したサンプルの履歴にアクセスすることができる。 目標は、各ラウンドで小さな予測誤差の仮説を出力することである。 本研究では,辺分離線形分類器(半空間)の基本クラスに対するこの学習問題の複雑性について検討する。 正の面では,誤差$η+ \tilde O(Δ^{1/3}/γ)$,$η$上界がMassartノイズレート,$Δ$がドリフトレート,$γ$がマージンとなるような計算効率のよい学習者を与える。 興味深いことに、実現可能な環境では、我々の手法の適応により、事前の作業よりも優れたエラー率を持つ効率的な学習者が得られる。 低バウンド側では、情報計算トレードオフの正式な証拠を提供し、アルゴリズムの性能が本質的に最適であることを強く示唆する。 具体的には、情報理論上の最適誤差スケールが$Δ^{1/2}$であるのに対して、$Δ^{1/3}$-scalingがランダム分類ノイズの特殊な場合であっても、低次多項式テストでは避けられないことを証明している。

関連論文リスト

• Online Set Learning from Precision and Recall Feedback [60.00180898830079]
  オンライン設定でドメインの未知のサブセットである$N_texttarget$を学習する問題を考察する。 この単純なオンラインセット学習問題は、精度とリコール型のフィードバックで様々な学習シナリオを抽象化する。 この設定で仮説クラスが学習可能であることを示し、それが有限のヴァプニク・チェルヴォネンキス次元を持つ場合に限る。
  論文  参考訳（メタデータ） (2026-05-10T14:28:05Z)
• Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate [10.550885570889527]
  スパースハーフスペースの属性効率の学習は、機械学習理論における根本的な問題である。 本稿では,データ内に一定の量の悪意のあるノイズが存在することを考察し,基礎となる$s$スパースハーフスペースを学習することを目的とする。 このような条件下では、既存のヒンジ損失最小化プログラムの単純な変種により、属性効率が達成可能であることを示す。
  論文  参考訳（メタデータ） (2025-05-27T17:02:28Z)
• Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random [17.56894435702055]
  我々は、マスアートノイズを伴う$gamma$-marginハーフスペースのPAC学習問題について検討する。 本稿では,サンプル複雑性を$widetildeO((epsilongamma)-2)$とする単純な固有学習アルゴリズムPerspectronを提案する。
  論文  参考訳（メタデータ） (2025-01-16T21:46:53Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Boosting in the Presence of Massart Noise [49.72128048499074]
  マスアートノイズを伴う(分布に依存しない)PACモデルにおいて、弱い学習者の精度を高める問題について検討する。 我々の主な成果は、Massartノイズの存在下で最初の計算効率の良いブースティングアルゴリズムである。 正の結果の簡単な応用として、高次元矩形の和に対して、第一に効率的なMassart学習者を与える。
  論文  参考訳（メタデータ） (2021-06-14T22:21:25Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)
• Towards Deep Learning Models Resistant to Large Perturbations [0.0]
  敵対的堅牢性は、機械学習アルゴリズムの必須特性であることが証明されている。 とよばれるアルゴリズムは、大きくても合理的で摂動のマグニチュードが与えられたディープニューラルネットワークのトレーニングに失敗することを示した。
  論文  参考訳（メタデータ） (2020-03-30T12:03:09Z)

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

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