要旨: 本稿では、敵対的ノイズによる学習に対して最適な誤りを実現するアルゴリズムを構成する。 本研究の中心的な主張は、
\textsl{randomized}（ランダム化された）仮説を用いることによって、決定論的仮説で達成可能な最良の誤り率を大幅に上回ることができる、という点である。
-
\etaeta率）の悪意ある（malicious）ノイズに対して、最適な誤りは \frac{1}{2} \cdot \eta/(1-\eta) であることを示し、決定論的仮説の最適な誤りを 1/2 倍だけ改善する。これは、Cesa-Bianchi ら（JACM 1999）が、ランダム性によって誤りが 6/7 倍改善し得ることを示していた未解決問題に答えるものである。
-
\eta\frac{3}{2} \cdot \eta、固定分布の学習者では最適な誤りが \eta であることを示す。いずれも、決定論的仮説の最適な誤り 2\eta を改善する。これは、Bshouty ら（Theoretical Computer Science 2002）が悪質ノイズを導入した際に最初に指摘したギャップを埋めるものであり、さらに最近の Klivans ら（NeurIPS 2025）および Blanc ら（SODA 2026）の研究でも再度述べられている。
-
\eta
\eta2\eta を改善する。
本稿で提案するすべての学習者は、サンプル複雑度が概念クラスの VC 次元に対して線形であり、過剰誤り（excess error）の逆数に対して多項式である。固定分布の悪質ノイズ学習者を除くすべてについて、経験的リスク最小化のためのオラクルへのアクセスがあれば、計算時間効率も良い。
最適誤りで堅牢に学習する
arXiv cs.LG / 2026/4/6
💬 オピニオンSignals & Early TrendsIdeas & Deep AnalysisModels & Research
要点
- 本論文は、敵対的ノイズ下での学習において、ランダム化した仮説（randomized hypotheses）を用いることで、決定論的仮説よりも最適誤り率を大幅に改善できることを示している。
- η-rateのmalicious noiseでは、最適誤り率を1/2·η/(1-η)まで下げ、決定論的仮説の最適誤りに対する改善率が1/2倍になるとしており、Cesa-Bianchiら（1999）の未解決問題を解決した。
- η-rateのnasty noiseでは、分布非依存（distribution-independent）学習で最適誤り率3/2·η、固定分布（fixed-distribution）でηを達成し、決定論的仮説の2ηから改善して、Bshoutyら（2002）が指摘したギャップを埋めた。
- η-rateのagnostic noiseや関連するnasty classification noiseでも最適誤り率ηを示し、決定論的仮説の2ηに対して改善しており、サンプル計数はVC次元に線形、過剰誤り（inverse excess error）に多項式で、（固定分布nasty noiseを除き）経験リスク最小化（ERM）オラクルへのアクセスを前提に時間効率も備える。
