論文の概要: Optimal Learning Under Tsybakov Noise

• arxiv url: http://arxiv.org/abs/2608.08416v1
• Date: Sun, 09 Aug 2026 02:20:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-11 19:16:36.816459
• Title: Optimal Learning Under Tsybakov Noise
• Title（参考訳）: ツィバコフ雑音下での最適学習
• Authors: Steve Hanneke, Hongao Wang, Mingyue Xu,
• Abstract要約: 高い確率で$h*$と競合する低い誤差の仮説を出力する学習アルゴリズムを設計する。 本手法は,非実現可能学習における近年の進歩と共通する概念基盤である。
• 参考スコア（独自算出の注目度）: 31.74405851825694
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Probably Approximately Correct (PAC) learning [Val84] is a fundamental learning model that has been extensively investigated. In this model, $\mathcal{H} \subseteq \{0,1\}^{\mathcal{X}}$ is a concept class, and $h^*\in\mathcal{H}$ is the target concept to be learned. Having access to i.i.d. labeled examples from a distribution $\mathcal{D}$ over $\mathcal{X}\times\{0,1\}$, which admits $h^*$ as the best concept in $\mathcal{H}$, the goal is to design a learning algorithm that outputs a hypothesis having low error competitive to $h^{*}$ with high probability. This model was initially studied under the realizable setting, which assumes that $h^*$ has no error. A natural relaxation is to allow label noise, that is, the true label can be flipped with probability $η\in(0,1/2)$. In reality, certain labels might be extremely noisy, especially for those points near the decision boundary. Hence, it is natural to allow very noisy points, though only rarely. This is quantified by a noise model introduced by [MT99] and [Tsy04], now known as Tsybakov noise. For learning general concept classes, [MN06] gave the general upper and lower bounds for error guarantees under Tsybakov noise. However, their upper and lower bounds differ by a logarithmic factor. Resolving this gap has remained a well-known open question for the past twenty years. In this work, we resolve this open question by improving the upper bound to match the best known lower bound, thus establishing the optimal error guarantee for learning under Tsybakov noise. Our learning algorithm operates by adaptively partitioning the instance space into regions, roughly corresponding to different noise levels, and returning a hypothesis in the concept class satisfying a specific error constraint for each region. Our technique shares a conceptual foundation with several recent advances in non-realizable learning, such as [HLZ24] and [Han25].
• Abstract（参考訳）: おそらくPAC学習 [Val84] は, 広く研究されている基礎学習モデルである。 このモデルでは、$\mathcal{H} \subseteq \{0,1\}^{\mathcal{X}}$ は概念クラスであり、$h^*\in\mathcal{H}$ は学習対象の概念である。 a distribution $\mathcal{D}$ over $\mathcal{X}\times\{0,1\}$, which is $h^*$ as the best concept in $\mathcal{H}$, the goal to design a learning algorithm which outputs low error competitive with $h^{*}$。 このモデルは最初、$h^*$に誤りがないと仮定して、実現可能な設定の下で研究された。 自然な緩和とは、ラベルノイズ、すなわち真のラベルを確率$η\in(0,1/2)$で反転させることである。 実のところ、特定のラベルは、特に決定境界付近の点では、非常にうるさいかもしれない。 したがって、非常にノイズの多い点を許すのは自然なことであるが、まれにのみである。 これは[MT99]と[Tsy04]によって導入されたノイズモデルによって定量化され、現在はTsybakovノイズとして知られている。 一般的な概念クラスを学ぶために [MN06] は、ツィバコフノイズの下でエラー保証の一般上と下の境界を与えた。 しかし、上と下の境界は対数係数によって異なる。 このギャップを解決することは、過去20年間、よく知られたオープンな問題である。 本研究では,この開放的問題を,最もよく知られた下界に適合する上限を改良し,ツィバコフ雑音下での学習における最適誤差保証を確立することで解決する。 学習アルゴリズムは、各領域の特定の誤差制約を満たす概念クラスに仮説を返すことにより、各領域に適応的にインスタンス空間を分割する。 本手法は, [HLZ24] や [Han25] などの非実現可能学習における近年の進歩と, 概念的基盤を共有している。

関連論文リスト

• Optimal Rates for Learning with Monotone Adversaries [7.053805156684374]
  モノトン対向は、i.i.d.ラベル付きサンプルを観察し、その選択の有限個の例を付加する。 すべてのサンプルは正しくラベル付けされているが、挿入はクリーンサンプルに依存するため、組み合わせたサンプルは交換できない。 このモデルを導入したLarsen、Pabbaraju、およびShettyは、VC次元$d$のクラスに対して、経験的リスク最小化が予測誤差$O((d/n)log(n/d))$に達することを示した。
  論文  参考訳（メタデータ） (2026-08-06T17:45:32Z)
• Efficiently Learning Drifting Halfspaces with Massart Noise [50.4331323695175]
  本研究では,マッサートノイズの存在下での漂流概念の学習問題について検討する。 このフレームワークでは、オンライン学習者は独立したサンプルの履歴にアクセスすることができる。 目標は、各ラウンドで小さな予測誤差の仮説を出力することである。
  論文  参考訳（メタデータ） (2026-06-09T17:35:18Z)
• Revisiting Agnostic PAC Learning [30.67561230812141]
  PAC学習は、Valiant'84とVapnik and Chervonenkis'64,'74にさかのぼる、教師あり学習を研究するための古典的なモデルである。 経験的リスク最小化(英: Empirical Risk Minimization、ERM)は、訓練データに最も少ない誤りを犯すために$mathcalH$から仮説を出力する自然学習アルゴリズムである。 私たちはPAC学習を再考し、最良仮説の性能を$tau:=Pr_mathcalD[hstar_mathと表すと、ERMが実際は準最適であることを示す。
  論文  参考訳（メタデータ） (2024-07-29T08:20:49Z)
• Online Learning of Halfspaces with Massart Noise [47.71073318490341]
  我々はMassartノイズの存在下でのオンライン学習の課題について検討する。 計算効率のよいアルゴリズムで, 誤り境界が$eta T + o(T)$であることを示す。 我々はMassartオンライン学習者を用いて、任意のラウンドでランダムなアクションを選択するよりも、少なくとも$(1-1/k) Delta T - o(T)$の報酬を得られる効率的なバンディットアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-05-21T17:31:10Z)
• The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
  バンディットフィードバックを用いた複数クラス分類の古典的問題を再考する。 我々は, 後悔すべき$smashwidetildeO(|H|+sqrtT)$を保証する新しい帯域分類アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-16T12:11:09Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• 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)

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

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