論文の概要: Is nasty noise actually harder than malicious noise?

• arxiv url: http://arxiv.org/abs/2511.09763v1
• Date: Fri, 14 Nov 2025 01:08:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-14 22:53:22.467299
• Title: Is nasty noise actually harder than malicious noise?
• Title（参考訳）: 悪質な騒音は悪質な騒音よりも難しいのか?
• Authors: Guy Blanc, Yizhi Huang, Tal Malkin, Rocco A. Servedio,
• Abstract要約: 本稿では,雑音の存在下での学習において,計算効率の高いアルゴリズムの相対的能力と限界について考察する。 分布非依存学習では、2つのノイズモデルの間に強い等価性を示す。 これらのアルゴリズムでは、悪質なノイズと悪質なノイズは、ノイズ率の最大2倍に等しいことを示す。
• 参考スコア（独自算出の注目度）: 5.887031992513966
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We consider the relative abilities and limitations of computationally efficient algorithms for learning in the presence of noise, under two well-studied and challenging adversarial noise models for learning Boolean functions: malicious noise, in which an adversary can arbitrarily corrupt a random subset of examples given to the learner; and nasty noise, in which an adversary can arbitrarily corrupt an adversarially chosen subset of examples given to the learner. We consider both the distribution-independent and fixed-distribution settings. Our main results highlight a dramatic difference between these two settings: For distribution-independent learning, we prove a strong equivalence between the two noise models: If a class ${\cal C}$ of functions is efficiently learnable in the presence of $η$-rate malicious noise, then it is also efficiently learnable in the presence of $η$-rate nasty noise. In sharp contrast, for the fixed-distribution setting we show an arbitrarily large separation: Under a standard cryptographic assumption, for any arbitrarily large value $r$ there exists a concept class for which there is a ratio of $r$ between the rate $η_{malicious}$ of malicious noise that polynomial-time learning algorithms can tolerate, versus the rate $η_{nasty}$ of nasty noise that such learning algorithms can tolerate. To offset the negative result for the fixed-distribution setting, we define a broad and natural class of algorithms, namely those that ignore contradictory examples (ICE). We show that for these algorithms, malicious noise and nasty noise are equivalent up to a factor of two in the noise rate: Any efficient ICE learner that succeeds with $η$-rate malicious noise can be converted to an efficient learner that succeeds with $η/2$-rate nasty noise. We further show that the above factor of two is necessary, again under a standard cryptographic assumption.
• Abstract（参考訳）: 本稿では,学習者に対して与えられたサンプルのランダムなサブセットを敵が任意に破壊できる悪質ノイズと,学習者に対して与えられたサンプルの逆選択されたサブセットを敵が任意に破壊できる悪質ノイズの2つのよく研究され,挑戦的な雑音モデルに基づく,雑音の存在下での計算効率の高いアルゴリズムの相対的能力と限界について考察する。 分布非依存設定と固定分布設定の両方について検討する。 分布に依存しない学習では、クラス${\cal C}$の関数が$η$の悪質ノイズの存在下で効率的に学習可能である場合、$$$の悪質ノイズの存在下でも効率的に学習可能である。 標準的な暗号的仮定では、任意の大きな値$r$に対して、多項式時間学習アルゴリズムが許容できる悪質なノイズに対して$η_{malicious}$$$$r$の比率を持つ概念クラスが存在し、そのような学習アルゴリズムが許容できる悪質なノイズがある。 固定分布設定の負の結果を相殺するために、我々は広範かつ自然なアルゴリズムのクラス、すなわち矛盾する例(ICE)を無視したアルゴリズムを定義する。 これらのアルゴリズムでは、悪質なノイズと悪質なノイズはノイズレートの2倍に等しいことが示される:$η$rateの悪質なノイズで成功する効率的なICE学習者は、$η/2$-rateの悪質なノイズで成功する効率的な学習者に変換できる。 さらに、上記の2つの要素は、再び標準的な暗号的仮定の下で必要であることを示す。

関連論文リスト

• Enhance Vision-Language Alignment with Noise [59.2608298578913]
  本研究では,凍結モデルがカスタマイズノイズによって微調整可能であるか検討する。 ビジュアルエンコーダとテキストエンコーダの両方にノイズを注入することでCLIPを微調整できる正インセンティブノイズ(PiNI)を提案する。
  論文  参考訳（メタデータ） (2024-12-14T12:58:15Z)
• Learning Constant-Depth Circuits in Malicious Noise Models [9.036777309376697]
  我々は、定数深度回路を学習するためのLinial, Mansour, Nisanの準ポリノミカル時間アルゴリズムを証明した。 ノイズ率に最も依存しうることを達成し、最も厳しいノイズモデルの実現に成功した。
  論文  参考訳（メタデータ） (2024-11-06T00:19:58Z)
• Multiclass Learning from Noisy Labels for Non-decomposable Performance Measures [15.358504449550013]
  非分解性性能尺度の2つのクラスに対して雑音ラベルから学習するアルゴリズムを設計する。 どちらの場合も、広範に研究されているクラス条件雑音モデルの下で、アルゴリズムのノイズ補正バージョンを開発する。 実験では,ラベルノイズ処理におけるアルゴリズムの有効性を実証した。
  論文  参考訳（メタデータ） (2024-02-01T23:03:53Z)
• Certified Adversarial Robustness Within Multiple Perturbation Bounds [38.3813286696956]
  ランダムスムーシング(Randomized smoothing、RS)は、敵の攻撃に対するよく知られた防御である。 本研究では,複数の摂動境界に対して同時に認証された対向ロバスト性を改善することを目的としている。
  論文  参考訳（メタデータ） (2023-04-20T16:42:44Z)
• Identifying Hard Noise in Long-Tailed Sample Distribution [71.8462682319137]
  NLT(Noisy Long-Tailed Classification)を紹介する。 ほとんどのノイズ除去法は、ハードノイズを特定するのに失敗する。 我々はH2E(Hard-to-Easy)と呼ばれる反復的な雑音学習フレームワークを設計する。
  論文  参考訳（メタデータ） (2022-07-27T09:03:03Z)
• The Optimal Noise in Noise-Contrastive Learning Is Not What You Think [80.07065346699005]
  この仮定から逸脱すると、実際により良い統計的推定結果が得られることが示される。 特に、最適な雑音分布は、データと異なり、また、別の家族からさえも異なる。
  論文  参考訳（メタデータ） (2022-03-02T13:59:20Z)
• Learning with Group Noise [106.56780716961732]
  グループノイズを用いた学習のための新しいマックスマッチング手法を提案する。 いくつかの学習パラダイムの領域における実世界のデータセットのレンジのパフォーマンスは、Max-Matchingの有効性を示している。
  論文  参考訳（メタデータ） (2021-03-17T06:57:10Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)

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

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