論文の概要: Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds

• arxiv url: http://arxiv.org/abs/2602.20111v1
• Date: Mon, 23 Feb 2026 18:30:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-24 17:42:02.945628
• Title: Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds
• Title（参考訳）: 逆行性注入による信頼性の低下--下肢と新上肢について
• Authors: Ezra Edelman, Surbhi Goel,
• Abstract要約: 我々は, [Goel et al. 2017] が導入した対戦型インジェクションモデルを用いてオンライン学習を研究する。 一致する$(sqrtT)$ down bound for VC dimension $1$を証明し、2つの情報体制の鮮明な分離を確立します。 敵の汚染に対する耐性が保たれていることを予測するためのラベル付きサンプルの小さなサブセットである、インプロバストな目撃者によって駆動される潜在的基盤フレームワークを導入する。
• 参考スコア（独自算出の注目度）: 16.636823007179082
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study online learning in the adversarial injection model introduced by [Goel et al. 2017], where a stream of labeled examples is predominantly drawn i.i.d.\ from an unknown distribution $\mathcal{D}$, but may be interspersed with adversarially chosen instances without the learner knowing which rounds are adversarial. Crucially, labels are always consistent with a fixed target concept (the clean-label setting). The learner is additionally allowed to abstain from predicting, and the total error counts the mistakes whenever the learner decides to predict and incorrect abstentions when it abstains on i.i.d.\ rounds. Perhaps surprisingly, prior work shows that oracle access to the underlying distribution yields $O(d^2 \log T)$ combined error for VC dimension $d$, while distribution-agnostic algorithms achieve only $\tilde{O}(\sqrt{T})$ for restricted classes, leaving open whether this gap is fundamental. We resolve this question by proving a matching $Ω(\sqrt{T})$ lower bound for VC dimension $1$, establishing a sharp separation between the two information regimes. On the algorithmic side, we introduce a potential-based framework driven by \emph{robust witnesses}, small subsets of labeled examples that certify predictions while remaining resilient to adversarial contamination. We instantiate this framework using two combinatorial dimensions: (1) \emph{inference dimension}, yielding combined error $\tilde{O}(T^{1-1/k})$ for classes of inference dimension $k$, and (2) \emph{certificate dimension}, a new relaxation we introduce. As an application, we show that halfspaces in $\mathbb{R}^2$ have certificate dimension $3$, obtaining the first distribution-agnostic bound of $\tilde{O}(T^{2/3})$ for this class. This is notable since [Blum et al. 2021] showed halfspaces are not robustly learnable under clean-label attacks without abstention.
• Abstract（参考訳）: 我々は, [Goel et al 2017] が導入した, 未知の分布$\mathcal{D}$から, ラベル付きサンプルのストリームを優先的に描画するオンライン学習について検討する。 重要なことに、ラベルは常に固定されたターゲット概念(クリーンラベル設定)と一致している。 さらに、学習者は予測を棄却することを許可され、総誤差は、学習者がi.d.\ラウンドで棄権した場合に、不正確な棄権を予測すると判断した場合に、誤りをカウントする。 おそらく、以前の研究は、基礎となる分布へのオラクルアクセスがVC次元の$d$に対して$O(d^2 \log T)$コンビネーションエラーをもたらすことを示しているが、分布に依存しないアルゴリズムは制限クラスに対して$\tilde{O}(\sqrt{T})$のみを達成する。 この問題は、VC次元が1ドルと一致する$Ω(\sqrt{T})$ローバウンドを証明し、2つの情報体制間の鋭い分離を確立することで解決する。 アルゴリズム面では, 敵の汚染に対する耐性を維持しつつ, 予測を認証するラベル付きサンプルの小さなサブセットである 'emph{robust witnesses} によって駆動されるポテンシャルベースのフレームワークを導入する。 1) \emph{inference dimension}, yielding combination error $\tilde{O}(T^{1-1/k})$ for inference dimension $k$, (2) \emph{certificate dimension}, a new relaxation。 応用として、$\mathbb{R}^2$ の半空間は証明書次元が 3$ であることを示し、このクラスに対して $\tilde{O}(T^{2/3})$ の分布非依存境界を得る。 このことは[Blum et al 2021] がハーフスペースを断念せずにクリーンラベル攻撃で頑健に学習できないことを示していたことから注目に値する。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds [9.036777309376697]
  Klivans、Stavropoulos、Vasilyanは、分散シフトを伴うテスト可能な学習の研究を始めた。 それらのモデルは、$mathcalD'$に仮定されないという点で、以前のすべての作業から逸脱している。
  論文  参考訳（メタデータ） (2024-04-02T23:34:39Z)
• Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
  2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。 グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
  論文  参考訳（メタデータ） (2024-01-16T03:14:24Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• Adversarially Robust Learning with Tolerance [8.658596218544774]
  本稿では,距離摂動集合に対する寛容逆PAC学習の問題点について考察する。 自然摂動・平滑アルゴリズムの変種であるPACは、$gamma$-tolerant adversarial setにおいて、VC次元が$v$の任意の仮説クラス$mathcalH$を学習する。 また,2次元に線形依存したサンプル境界を求める学習手法を提案する。
  論文  参考訳（メタデータ） (2022-03-02T03:50:16Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Provable Robustness of Adversarial Training for Learning Halfspaces with Noise [95.84614821570283]
  ラベル雑音の存在下での敵対的ロバストなハーフスペースの特性を分析する。 我々の知る限りでは、これは敵の訓練がノイズの分類子を与えることを示す最初の研究である。
  論文  参考訳（メタデータ） (2021-04-19T16:35:38Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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