論文の概要: Adversarially Robust PAC Learning with Optimal VC Rates

• arxiv url: http://arxiv.org/abs/2609.24260v1
• Date: Mon, 21 Sep 2026 08:23:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-22 20:29:01.209751
• Title: Adversarially Robust PAC Learning with Optimal VC Rates
• Title（参考訳）: 最適VCレートを用いた逆ロバストPAC学習
• Abstract要約: 本研究では,PAC学習の課題について検討する。 このフレームワークでは、学習者は従来のPAC学習のように、$mathcalX times 0,1$以上の未知の分布から独立したサンプルを観察する。 逆方向のロバスト性は,すべての摂動マップに対して,分布自由な統計コストを増大させることを示した。
• 参考スコア（独自算出の注目度）: 30.993334156637186
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of \emph{adversarially robust} PAC learning. In this framework, the learner observes independent samples from an unknown distribution over $\mathcal{X} \times \{0,1\}$, as in classical PAC learning. However, given a perturbation map $\mathcal{U} : \mathcal{X} \to 2^{\mathcal{X}}$ known to the learner, the goal is to output, with high probability, a predictor that correctly classifies \emph{every} perturbation $z \in \mathcal{U}(x)$ of most future examples $(x,y)$ drawn from the same underlying distribution. We determine the \emph{optimal} $\mathcal{U}$-independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class $\mathcal{H}$ of $\operatorname{VC}$ dimension $d$, we prove upper bounds of $\mathcal{O} \big( d/ε+ \log(1/δ)/ε\big)$ in the realizable setting and $\mathcal{O} \big( d/ε^2 + \log(1/δ)/ε^2 \big)$ in the agnostic setting, together with an optimal first-order refinement of the latter. These bounds match the corresponding lower bounds for classical PAC learning. Consequently, and perhaps surprisingly, adversarial robustness incurs \emph{no additional} distribution-free statistical cost, uniformly over all perturbation maps. Our bounds improve exponentially on those of [Montasser, Hanneke, and Srebro; COLT '19]. On the technical side, we present short and elementary proofs based on a new algorithmic principle that we call \emph{binomial-bagging}. We believe that binomial-bagging and its analysis may be of independent interest.
• Abstract（参考訳）: PAC学習におけるemph{adversarially robust}の問題について検討する。 このフレームワークでは、学習者は、古典的なPAC学習のように、$\mathcal{X} \times \{0,1\}$という未知の分布から独立したサンプルを観測する。 しかし、学習者に知られている摂動写像 $\mathcal{U} : \mathcal{X} \to 2mathcal{X}}$ が与えられた場合、その目標は、高い確率で出力することであり、予測器は \emph{every} 摂動を正しく分類する。 我々は、この問題の非依存的なサンプルの複雑さを、実現可能な設定と不可知な設定の両方で決定する。 具体的には、すべての概念クラス $\mathcal{H}$ of $\operatorname{VC}$ dimension $d$ に対して、既約集合において $\mathcal{O} \big(d/ε+ \log(1/δ)/ε\big)$ と既約集合において $\mathcal{O} \big(d/ε^2 + \log(1/δ)/ε^2 \big)$ の上限を証明し、後者を最適に一階改良する。 これらの境界は古典的なPAC学習の対応する下位境界と一致する。 その結果、また驚くべきことに、対向ロバスト性は、すべての摂動写像に対して分布のない統計コストをもたらす。 我々の境界は[Montasser, Hanneke, Srebro; COLT '19] の値よりも指数的に改善する。 技術的な面から、我々は「emph{binomial-bagging}」と呼ばれる新しいアルゴリズム原理に基づいて、短い証明と初等証明を提示する。 我々は、二項バッグとその分析が独立した関心事であると信じている。

関連論文リスト

• An Optimal Agnostic PAC Algorithm [15.361702135159845]
  2進リスクに対して$L$と$L*=min_hin HL(h)$を書き、統計的に最適なリスク境界を達成する学習者を構築する。 これにより、PACが任意の固定された$L*$で普遍定数まで学習する際の無知なサンプル複雑性が解決される。
  論文  参考訳（メタデータ） (2026-08-06T17:57:25Z)
• On Agnostic PAC Learning in the Small Error Regime [4.422219522591412]
  経験的リスク最小化学習者は、実現可能なケースでは最適だが、不可知なケースでは最適である。 Hanneke、Larsen、Zhivotovskiyの作業は、エラー項のパラメータとして$tau$を含めることで、この欠点に対処する。 我々の学習者は、一定の$c leq 2.1$に対して、誤りの少ない$tau + Omega left(sqrtfractau))m + fracd + log (1 / delta)m right)の厳密性を達成することを示す。
  論文  参考訳（メタデータ） (2025-02-13T17:03:03Z)
• Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise [38.551072383777594]
  本研究では, 対向分布シフトの存在下でのL2$損失に対して, 単一ニューロンを学習する問題について検討した。 ベクトルベクトル二乗損失を$chi2$divergenceから$mathcalp_0$に近似するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-11-11T03:43:52Z)
• Revisiting Agnostic PAC Learning [30.67561230812141]
  PAC学習は、Valiant'84とVapnik and Chervonenkis'64,'74にさかのぼる、教師あり学習を研究するための古典的なモデルである。 経験的リスク最小化(英: Empirical Risk Minimization、ERM)は、訓練データに最も少ない誤りを犯すために$mathcalH$から仮説を出力する自然学習アルゴリズムである。 私たちはPAC学習を再考し、最良仮説の性能を$tau:=Pr_mathcalD[hstar_mathと表すと、ERMが実際は準最適であることを示す。
  論文  参考訳（メタデータ） (2024-07-29T08:20:49Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  論文  参考訳（メタデータ） (2023-02-27T16:34:21Z)
• On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
  本研究は,学習者によって達成可能な最小のエラー$epsilon=epsilon(eta)$を,そのような敵の存在下で特徴付けることを目的とする。 注目すべきは,上界が決定論的学習者によって達成できることである。
  論文  参考訳（メタデータ） (2022-10-06T06:49:48Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)

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

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