論文の概要: The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination

• arxiv url: http://arxiv.org/abs/2505.20177v1
• Date: Mon, 26 May 2025 16:17:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 19:27:26.933352
• Title: The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination
• Title（参考訳）: 重質汚染による教師付き学習における反復フィルタリングの力
• Authors: Adam R. Klivans, Konstantinos Stavropoulos, Kevin Tian, Arsen Vasilyan,
• Abstract要約: 低次数で近似できる任意の関数クラスは、有界汚染下で効率的に学習できることを示す。 固定対数対数分布に対するハーフ空間の関数に対する耐久性試験可能学習のための最初の効率的なアルゴリズムを得る。
• 参考スコア（独自算出の注目度）: 13.980910832909906
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Inspired by recent work on learning with distribution shift, we give a general outlier removal algorithm called iterative polynomial filtering and show a number of striking applications for supervised learning with contamination: (1) We show that any function class that can be approximated by low-degree polynomials with respect to a hypercontractive distribution can be efficiently learned under bounded contamination (also known as nasty noise). This is a surprising resolution to a longstanding gap between the complexity of agnostic learning and learning with contamination, as it was widely believed that low-degree approximators only implied tolerance to label noise. (2) For any function class that admits the (stronger) notion of sandwiching approximators, we obtain near-optimal learning guarantees even with respect to heavy additive contamination, where far more than $1/2$ of the training set may be added adversarially. Prior related work held only for regression and in a list-decodable setting. (3) We obtain the first efficient algorithms for tolerant testable learning of functions of halfspaces with respect to any fixed log-concave distribution. Even the non-tolerant case for a single halfspace in this setting had remained open. These results significantly advance our understanding of efficient supervised learning under contamination, a setting that has been much less studied than its unsupervised counterpart.
• Abstract（参考訳）: 分布シフトを伴う学習の最近の研究に触発されて、反復多項式フィルタリングと呼ばれる一般的な外乱除去アルゴリズムが提供され、(1)超収縮分布に対して低次多項式で近似できる任意の関数クラスが、有界汚染(ナスティノイズとも呼ばれる)の下で効率的に学習できることが示される。 これは、無知学習の複雑さと汚染による学習との長年のギャップに対する驚くべき解決であり、低次近似器はラベルノイズに対する耐性のみを示唆していると広く信じられていた。 2) サンドイッチ近似の(強烈な)概念を許容する任意の関数クラスに対して, 重添加性汚染に関しても, 準最適学習保証を得る。 以前の関連する作業は、回帰とリストデコダブルな設定でのみ行われていました。 (3) 固定対数空間分布に対するハーフ空間の関数に対する耐久性試験可能学習のための最初の効率的なアルゴリズムを得る。 この設定での1つのハーフスペースに対する耐性のないケースでさえ、オープンのままであった。 これらの結果から, 汚染下での効率的な教師なし学習の理解が著しく向上した。

関連論文リスト

• Efficient Discrepancy Testing for Learning with Distribution Shift [17.472049019016524]
  局所的な一致距離をテストするための証明可能なアルゴリズムの最初のセットを提供する。 結果は、最近導入されたTestable Learning with Distribution Shiftモデルにおいて、新しい効率的な学習アルゴリズムの幅広いセットを示唆している。
  論文  参考訳（メタデータ） (2024-06-13T17:51:10Z)
• Tolerant Algorithms for Learning with Arbitrary Covariate Shift [18.37181965815327]
  学習者は,ある分布からラベル付き集合を学習するが,異なる,潜在的に逆向きに生成されたテスト分布で評価する。 我々は,PQ学習 (Goldwasser, A. Kalai, Y. Kalai, Montasser NeurIPS 2020) とTDS学習 (Klivans, Stavropoulos, Vasilyan COLT 2024) の2つのフレームワークに注目した。
  論文  参考訳（メタデータ） (2024-06-04T19:50:05Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  細長い分布は、少数の少数派が限られた数のサンプルを含む実世界のデータにしばしば現れる。 近年の研究では、教師付きコントラスト学習がデータ不均衡を緩和する有望な可能性を示していることが明らかになっている。 本稿では,特徴空間の各クラスからのサンプルデータ分布を推定する確率論的コントラスト学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-11T13:44:49Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。 データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-16T04:32:22Z)
• Shrinking Class Space for Enhanced Certainty in Semi-Supervised Learning [59.44422468242455]
  そこで我々はShrinkMatchと呼ばれる新しい手法を提案し、不確実なサンプルを学習する。 それぞれの不確実なサンプルに対して、元の Top-1 クラスを単に含むスランク類空間を適応的に求める。 次に、スランク空間における強と弱に強化された2つのサンプル間の整合正則化を課し、識別的表現を試みます。
  論文  参考訳（メタデータ） (2023-08-13T14:05:24Z)
• Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise [9.76321513479048]
  我々は,契約演算子の下で近似(SA)によって生成される反復体に対して最大濃度境界を確立する。 本稿では,有界乗法雑音を持つ SA と準ガウス加法雑音を持つ SA の2つの条件について考察する。
  論文  参考訳（メタデータ） (2023-03-28T05:32:30Z)
• Hierarchical Semi-Supervised Contrastive Learning for Contamination-Resistant Anomaly Detection [81.07346419422605]
  異常検出は、通常のデータ分布から逸脱したサンプルを特定することを目的としている。 コントラスト学習は、異常の効果的な識別を可能にする表現のサンプル化に成功している。 汚染耐性異常検出のための新しい階層型半教師付きコントラスト学習フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-07-24T18:49:26Z)
• Chaos is a Ladder: A New Theoretical Understanding of Contrastive Learning via Augmentation Overlap [64.60460828425502]
  コントラスト学習の下流性能に関する新たな保証を提案する。 我々の新しい理論は、攻撃的なデータ強化の下で、異なるクラス内サンプルのサポートがより重なり合うという知見に基づいている。 本稿では、下流の精度とよく一致した教師なしモデル選択距離ARCを提案する。
  論文  参考訳（メタデータ） (2022-03-25T05:36:26Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。 このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-08-22T16:00:45Z)

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

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