論文の概要: When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification

• arxiv url: http://arxiv.org/abs/2608.20480v1
• Date: Thu, 20 Aug 2026 18:10:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-24 14:49:32.150444
• Title: When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification
• Title（参考訳）: クリーンなデータ処理 - バイナリ分類を超えたモノトン破壊による学習
• Authors: Julian Asilis, Shaddin Dughmi, Chirag Pabbaraju,
• Abstract要約: 多クラス分類や部分二分概念クラスにおいて,単調な逆数の方が驚くほど強力であることを示す。 古典的なマルチクラスエラーレートである$O(d_mathrmDS / n)$が、適応的な敵に対して達成可能であることを示す。
• 参考スコア（独自算出の注目度）: 9.871543582439903
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Optimal learners are tailored to exploit the i.i.d.\ data assumption underlying the classic PAC model. What if an i.i.d.\ training sample were corrupted with correctly labeled examples drawn from an otherwise unrelated, even adversarial source? This model of learning with monotone adversarial corruptions was recently introduced by Larsen et al. (2026), who demonstrated that all known optimal binary learners suffer increased error rates in this setting, from $O(d / n)$ in the PAC model to $Ω(d \log(n / d) / n)$ under monotone corruption. Mehrotra (2026) proved this logarithmic factor to be necessary for binary classification, but left open the consequences of corruption for more general learning settings, such as multiclass classification and partial binary concept classes. As our primary result, we demonstrate that monotone adversaries are frighteningly more powerful in each of these settings. We exhibit a learnable multiclass problem, of DS dimension only 2, that becomes altogether unlearnable under a monotone adversary, and show an analogous result for partial binary concept classes. These results are achieved by an adaptive adversary permitted to view the original i.i.d.\ training set $S$ and to insert $b < \infty$ corrupted datapoints into $S$. In the multiclass example, the adversary need only insert a linear number $b = |S| = n$ of datapoints. We complement these impossibility results by proving that every class remains learnable when the number of adaptive additions is $o(n)$, which our previous multiclass lower bound proves to be tight. We further observe that the classic multiclass error rate of $O(d_{\mathrm{DS}} / n)$ remains achievable against adaptive adversaries restricted to a known constant budget $b = O(1)$, against semi-adaptive adversaries viewing only a $p$-fraction of $S$ for $p \in (0, 1)$, and against oblivious adversaries that cannot view $S$.
• Abstract（参考訳）: 学習者は、古典的なPACモデルに基づくi.d.\データ仮定を利用するように調整される。 もし、i.i.d.\トレーニングサンプルが、そうでなければ無関係で、敵対的な情報源から引き出された正しくラベル付けされたサンプルで破損した場合はどうでしょう? この学習モデルが最近Larsen et al (2026) によって導入され、PACモデルでは$O(d / n)$から$Ω(d \log(n / d) / n)$まで、全ての既知の二進学習者がこの設定でエラー率を増大させることを示した。 Mehrotra (2026) は、この対数係数が二項分類に必要であることを証明したが、多クラス分類や部分二項概念クラスのようなより一般的な学習環境において、汚職の結果を開放した。 主な結果として,それぞれの設定においてモノトーンの敵が驚くほど強力であることを示す。 DS次元がたった2の学習可能な多クラス問題を示し、これは単調な逆数の下で完全に学習不可能となり、部分二項概念クラスに対して類似した結果を示す。 これらの結果は、元の i.i.d.\ トレーニングセット $S$ と $b < \infty$ の破損したデータポイントを $S$ に挿入することを許す適応的敵によって達成される。 マルチクラスの例では、逆元はデータポイントの線型数 $b = |S| = n$ を挿入するだけでよい。 適応的な加算の数が $o(n)$ であるとき、すべてのクラスが学習可能であることを証明して、これらの不可能性の結果を補完する。 さらに、古典的なマルチクラスエラーレートである$O(d_{\mathrm{DS}} / n)$は、既知の一定の予算に制限された適応的敵に対して、$b = O(1)$、半適応的敵に対して$p$-fraction of $S$ for $p \in (0, 1)$、そして$S$を見ることができない不愉快な敵に対して、引き続き達成可能であることを観察する。

関連論文リスト

• 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)
• Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds [16.636823007179082]
  我々は, [Goel et al. 2017] が導入した対戦型インジェクションモデルを用いてオンライン学習を研究する。 一致する$(sqrtT)$ down bound for VC dimension $1$を証明し、2つの情報体制の鮮明な分離を確立します。 敵の汚染に対する耐性が保たれていることを予測するためのラベル付きサンプルの小さなサブセットである、インプロバストな目撃者によって駆動される潜在的基盤フレームワークを導入する。
  論文  参考訳（メタデータ） (2026-02-23T18:30:48Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Self-Directed Linear Classification [50.659479930171585]
  オンライン分類では、学習者は、誤りの総数を最小限に抑えるために、オンラインでラベルを予測することを目的としている。 そこで本研究では,予測順序の選択能力について検討し,最低次学習とランダム次学習の分離を初めて確立する。
  論文  参考訳（メタデータ） (2023-08-06T15:38:44Z)
• Supervised Contrastive Prototype Learning: Augmentation Free Robust Neural Network [17.10753224600936]
  ディープニューラルネットワーク(DNN)の入力空間における変換は、特徴空間の意図しない変化をもたらす。 我々は、SCPL (textbfd Contrastive Prototype Learning$) というトレーニングフレームワークを提案する。 同じクラスと反対クラスのプロトタイプでNペアの対照的な損失を使用し、分類ヘッドを$textbfPrototype Classification Head(PCH)で置き換える。 私たちのアプローチは、$textitsample efficient$、$textitsample mining$、既存のどのDNNでも変更せずに実装できます。
  論文  参考訳（メタデータ） (2022-11-26T01:17:15Z)
• Online Selective Classification with Limited Feedback [82.68009460301585]
  オンライン学習モデルにおいて、予測者がインスタンスの分類を控える可能性のある選択的分類について検討する。 私たちが考慮している設定の健全な2つの側面は、データが不可避である可能性があるため、データは不可避である可能性があるということです。 smash$tildeO(T1-mu)$ over abstention against Adaptive adversaries. smash$tildeO(T1-mu)$ incurring smash$tildeO(T1-mu)$ over abstention。
  論文  参考訳（メタデータ） (2021-10-27T08:00:53Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
  論文  参考訳（メタデータ） (2021-10-25T02:53:24Z)
• Corruption-Robust Offline Reinforcement Learning [19.300465320692066]
  オフライン強化学習における対向的堅牢性について検討する。 最悪な$Omega(デプシロン)最適性ギャップは避けられないことを示す。 本稿では,Last-Square Value Iteration (LSVI)アルゴリズムのロバストな変種を提案する。
  論文  参考訳（メタデータ） (2021-06-11T22:41:53Z)
• Towards Defending Multiple $\ell_p$-norm Bounded Adversarial Perturbations via Gated Batch Normalization [120.99395850108422]
  既存の敵防衛は、個々の摂動に対するモデル堅牢性を改善するのが一般的である。 最近の手法では、複数の$ell_p$球における敵攻撃に対するモデルロバスト性を改善するが、各摂動型に対するそれらの性能は、まだ十分ではない。 我々は,複数の$ell_pの有界摂動を守るために,摂動不変予測器を逆向きに訓練するGated Batch Normalization (GBN)を提案する。
  論文  参考訳（メタデータ） (2020-12-03T02:26:01Z)
• Improving Robustness and Generality of NLP Models Using Disentangled Representations [62.08794500431367]
  スーパービジョンニューラルネットワークはまず入力$x$を単一の表現$z$にマップし、次に出力ラベル$y$にマッピングする。 本研究では,非交叉表現学習の観点から,NLPモデルの堅牢性と汎用性を改善する手法を提案する。 提案した基準でトレーニングしたモデルは、広範囲の教師付き学習タスクにおいて、より堅牢性とドメイン適応性を向上することを示す。
  論文  参考訳（メタデータ） (2020-09-21T02:48:46Z)

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

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