論文の概要: Robust Learning with Optimal Error
- arxiv url: http://arxiv.org/abs/2604.02555v1
- Date: Thu, 02 Apr 2026 22:10:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-06 17:20:24.230295
- Title: Robust Learning with Optimal Error
- Title（参考訳）: 最適誤差を用いたロバスト学習
- Authors: Guy Blanc,
- Abstract要約: 逆雑音を学習するアルゴリズムを最適誤差で構築する。
この研究の全体的テーマは、テキストスラランド化仮説の使用は決定論的仮説で達成可能な最高の誤り率で著しく改善できるということである。
- 参考スコア（独自算出の注目度）: 4.3386461601155295
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We construct algorithms with optimal error for learning with adversarial noise. The overarching theme of this work is that the use of \textsl{randomized} hypotheses can substantially improve upon the best error rates achievable with deterministic hypotheses. - For $η$-rate malicious noise, we show the optimal error is $\frac{1}{2} \cdot η/(1-η)$, improving on the optimal error of deterministic hypotheses by a factor of $1/2$. This answers an open question of Cesa-Bianchi et al. (JACM 1999) who showed randomness can improve error by a factor of $6/7$. - For $η$-rate nasty noise, we show the optimal error is $\frac{3}{2} \cdot η$ for distribution-independent learners and $η$ for fixed-distribution learners, both improving upon the optimal $2 η$ error of deterministic hypotheses. This closes a gap first noted by Bshouty et al. (Theoretical Computer Science 2002) when they introduced nasty noise and reiterated in the recent works of Klivans et al. (NeurIPS 2025) and Blanc et al. (SODA 2026). - For $η$-rate agnostic noise and the closely related nasty classification noise model, we show the optimal error is $η$, improving upon the optimal $2η$ error of deterministic hypotheses. All of our learners have sample complexity linear in the VC-dimension of the concept class and polynomial in the inverse excess error. All except for the fixed-distribution nasty noise learner are time efficient given access to an oracle for empirical risk minimization.
- Abstract（参考訳）: 逆雑音を学習するアルゴリズムを最適誤差で構築する。
この研究の包括的なテーマは、決定論的仮説によって達成できる最良のエラー率において、 \textsl{randomized}仮説の使用が大幅に改善できるということである。
-$η$-rate悪騒音の場合、最適誤差は$\frac{1}{2} \cdot η/(1-η)$で、決定論的仮説の最適誤差を1/2$で改善する。
このことはCesa-Bianchi et al (JACM 1999) のオープンな疑問に答え、ランダム性は6/7$の係数で誤りを改善することができることを示した。
-$η$-rateナスティノイズの場合,分布に依存しない学習者に対して$\frac{3}{2} \cdot η$,固定分布学習者に対して$η$が最適であることを示す。
Bshouty et al (Theoretical Computer Science 2002) が最近発表した Klivans et al (NeurIPS 2025) と Blanc et al (SODA 2026) で繰り返し言及した。
-$η$-rate agnostic noise およびそれと密接に関連する鼻音分類ノイズモデルに対して、最適誤差は$η$であり、決定論的仮説の最適2η$エラーにより改善されることを示す。
全ての学習者は、概念クラスと多項式のVC次元に線形なサンプル複雑性を持つ。
固定分布ノイズ学習者を除いては、経験的リスク最小化のためのオラクルへのアクセスを前提として、時間効率がよい。
関連論文リスト
- Entangled Mean Estimation in High-Dimensions [36.97113089188035]
信号のサブセットモデルにおける高次元エンタングルド平均推定の課題について検討する。
最適誤差(polylogarithmic factor)は$f(alpha,N) + sqrtD/(alpha N)$であり、$f(alpha,N)$は1次元問題の誤差であり、第二項は準ガウス誤差率である。
論文 参考訳（メタデータ） (2025-01-09T18:31:35Z) - Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。
1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。
我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。
我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
論文 参考訳（メタデータ） (2024-11-20T02:46:15Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Optimal Learning [0.0]
本稿では、与えられたデータから未知の関数を$f$で学習する問題を考察する。
学習問題は、データから$f$の値を予測する近似$hat f$ to $f$を与えることである。
論文 参考訳（メタデータ） (2022-03-30T02:05:27Z) - Learning stochastic decision trees [19.304587350775385]
対向雑音に対して最適に耐性のある決定木を学習するための準ポリノミカル時間アルゴリズムを提案する。
私たちのアルゴリズムはさらに適切で、それ自体が決定木である仮説を返します。
論文 参考訳（メタデータ） (2021-05-08T04:54:12Z) - 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) - Approximation Algorithms for D-optimal Design [4.889013411494113]
実験設計は古典的な統計問題であり、その目的は線形測定から未知の$m$次元ベクトル$beta$を推定することである。
実験的な設計問題に対しては、与えられた$n$実験から$k$を選び、未知のパラメータの最も正確な推定を行うことが目的である。
誤差推定の最も堅牢な尺度の1つとして、推定誤差に対する信頼楕円体の体積を最小化する$D$-optimality criterionについて検討する。
論文 参考訳（メタデータ） (2018-02-23T02:48:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。