論文の概要: Simplifying Adversarially Robust PAC Learning with Tolerance

• arxiv url: http://arxiv.org/abs/2502.07232v1
• Date: Tue, 11 Feb 2025 03:48:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-12 14:07:02.229230
• Title: Simplifying Adversarially Robust PAC Learning with Tolerance
• Title（参考訳）: 耐久性を考慮した逆ロバストPAC学習の簡易化
• Authors: Hassan Ashtiani, Vinayak Pathak, Ruth Urner,
• Abstract要約: 本稿では,Hの仮定を必要とせずに,VC次元の線形なサンプル複雑性を実現する,より単純な学習者の存在を示す。 学習者が不適切なとしても、H の仮説と「類似」な仮説を出力するという意味では「最も適切」である。 また,アルゴリズムのアイデアを用いて,トレラントな環境下で半教師付き学習者を構築する。
• 参考スコア（独自算出の注目度）: 9.973499768462888
• License:
• Abstract: Adversarially robust PAC learning has proved to be challenging, with the currently best known learners [Montasser et al., 2021a] relying on improper methods based on intricate compression schemes, resulting in sample complexity exponential in the VC-dimension. A series of follow up work considered a slightly relaxed version of the problem called adversarially robust learning with tolerance [Ashtiani et al., 2023, Bhattacharjee et al., 2023, Raman et al., 2024] and achieved better sample complexity in terms of the VC-dimension. However, those algorithms were either improper and complex, or required additional assumptions on the hypothesis class H. We prove, for the first time, the existence of a simpler learner that achieves a sample complexity linear in the VC-dimension without requiring additional assumptions on H. Even though our learner is improper, it is "almost proper" in the sense that it outputs a hypothesis that is "similar" to a hypothesis in H. We also use the ideas from our algorithm to construct a semi-supervised learner in the tolerant setting. This simple algorithm achieves comparable bounds to the previous (non-tolerant) semi-supervised algorithm of Attias et al. [2022a], but avoids the use of intricate subroutines from previous works, and is "almost proper."
• Abstract（参考訳）: 現在知られている学習者(Montasser et al , 2021a)は複雑な圧縮スキームに基づく不適切な手法に頼っているため、VC次元ではサンプル複雑性が指数関数的に増大する。 Ashtiani et al , 2023, Bhattacharjee et al , 2023, Raman et al , 2024] とよばれる問題を少し緩和し、VC次元の観点からより優れたサンプル複雑性を実現した。 しかし、これらのアルゴリズムは不適切で複雑であったり、仮説クラスHに追加の仮定が必要であったりした。我々は、初めて、VC次元で線形なサンプル複雑性を実現する単純な学習者の存在を証明した。 この単純なアルゴリズムは、Attias et al [2022a] の以前の(耐性のない)半教師付きアルゴリズムに匹敵する限界を達成するが、以前の研究から複雑なサブルーチンの使用を回避し、「最も適切な」ものである。

関連論文リスト

• Regularized Robustly Reliable Learners and Instance Targeted Attacks [11.435833538081557]
  Balcan et al (2022) は、堅牢で信頼性の高い学習者の概念を定義することによって、この問題に対処するアプローチを提案した。 少なくともある興味深いケースでは、トレーニング時間内にサブリニアで出力を生成できるアルゴリズムを設計できることが示されています。
  論文  参考訳（メタデータ） (2024-10-14T14:49:32Z)
• Is Transductive Learning Equivalent to PAC Learning? [0.9012198585960443]
  PACモデルとトランスダクティブモデルは、本質的には非依存のバイナリ分類に等価であることを示す。 我々は,2番目の結果が2進分類を超えて拡張可能かどうかという興味深い疑問を残して,トランスダクティブモデルとPACモデルがより広範に等価であることを示す。
  論文  参考訳（メタデータ） (2024-05-08T16:26:49Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Uniform-PAC Guarantees for Model-Based RL with Bounded Eluder Dimension [86.3584476711976]
  一般関数クラスと有界エリューダを用いた非線形帯域幅とモデルベースエピソードRLのアルゴリズムを提案する。 達成された一様PACサンプルの複雑性は、最先端の後悔境界や、線形ケースに還元された場合のサンプルの複雑さを保証するという意味で厳密である。
  論文  参考訳（メタデータ） (2023-05-15T05:07:45Z)
• Learnability, Sample Complexity, and Hypothesis Class Complexity for Regression Models [10.66048003460524]
  この研究はPACの基礎に触発され、既存の回帰学習問題に動機付けられている。 提案手法はEpsilon-Confidence Aough Correct (epsilon CoAC)で示され、Kullback Leibler divergence(相対エントロピー)を利用する。 これにより、学習者は異なる複雑性順序の仮説クラスを比較でき、それらの中から最小のエプシロンを最適に選択できる。
  論文  参考訳（メタデータ） (2023-03-28T15:59:12Z)
• Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient [51.37720227675476]
  我々は、決定推定係数の新たな変種を導入し、それを用いて、3つの面における事前の作業を改善する新しい下界を導出する。 我々は同じ量でスケールした後悔について上界を与え、フォスター等における上界と下界の間のギャップの1つを除いて全てを閉じる。 この結果は、後悔のフレームワークとPACフレームワークの両方に適用され、我々が期待するいくつかの新しい分析とアルゴリズム設計技術を利用して、より広範な利用が期待できる。
  論文  参考訳（メタデータ） (2023-01-19T18:24:08Z)
• A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity [15.746613321517282]
  我々は、モーメントマッチングやメートル法非依存のツールを用いて、テスト可能な学習アルゴリズムを開発するための強力な新しいアプローチを提案する。 意外なことに、テスト可能な学習における情報理論の複雑さは、概念クラスのRademacher複雑さによって強く特徴づけられている。
  論文  参考訳（メタデータ） (2022-11-23T21:29:51Z)
• A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
  本研究では、半教師付きPACモデルにおいて、時間攻撃をテストするために、逆向きに頑健な予測器を学習する問題について検討する。 最悪の分布自由モデルにおいても,半教師付き頑健な学習には大きなメリットがあることが示されている。
  論文  参考訳（メタデータ） (2022-02-11T03:01:45Z)
• Agnostic Proper Learning of Halfspaces under Gaussian Marginals [56.01192577666607]
  ガウスの下の半空間を不可知的に学習する問題を考察する。 我々の主な成果は、この問題に対するエム第一固有学習アルゴリズムである。
  論文  参考訳（メタデータ） (2021-02-10T18:40:44Z)
• Sample-efficient proper PAC learning with approximate differential privacy [51.09425023771246]
  近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。 この結果は Bun et al の質問に答えます。 (FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
  論文  参考訳（メタデータ） (2020-12-07T18:17:46Z)

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

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