論文の概要: Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness
- arxiv url: http://arxiv.org/abs/2506.03075v1
- Date: Tue, 03 Jun 2025 16:53:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-05 01:42:09.447665
- Title: Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness
- Title（参考訳）: ターゲットポジショニングによるアグノスティックラーニング--最適レートとランダムネスの役割
- Authors: Bogdan Chornomaz, Yonatan Koren, Shay Moran, Tom Waknine,
- Abstract要約: 以前の研究は、このようなインスタンス標的の毒殺攻撃による最適エラーが$Theta(deta)$とスケールすることを確立した。
最適余剰誤差が $tildeTheta(sqrtdeta)$ であることを示し、Hannekeらによって残された主要な開問題の一つに答える。
- 参考スコア（独自算出の注目度）: 13.802167452101909
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of learning in the presence of an adversary that can corrupt an $\eta$ fraction of the training examples with the goal of causing failure on a specific test point. In the realizable setting, prior work established that the optimal error under such instance-targeted poisoning attacks scales as $\Theta(d\eta)$, where $d$ is the VC dimension of the hypothesis class arXiv:2210.02713. In this work, we resolve the corresponding question in the agnostic setting. We show that the optimal excess error is $\tilde{\Theta}(\sqrt{d\eta})$, answering one of the main open problems left by Hanneke et al. To achieve this rate, it is necessary to use randomized learners: Hanneke et al. showed that deterministic learners can be forced to suffer error close to 1, even under small amounts of poisoning. Perhaps surprisingly, our upper bound remains valid even when the learner's random bits are fully visible to the adversary . In the other direction, our lower bound is stronger than standard PAC-style bounds: instead of tailoring a hard distribution separately for each sample size, we exhibit a single fixed distribution under which the adversary can enforce an excess error of $\Omega(\sqrt{d\eta})$ infinitely often.
- Abstract（参考訳）: 特定のテストポイントに障害を引き起こすことを目標として,トレーニング例の$\eta$分の1を破損させるような敵の存在下での学習の問題について検討する。
実現可能な設定では、そのようなインスタンス標的の毒殺攻撃による最適誤差は$\Theta(d\eta)$とスケールし、$d$は仮説クラスarXiv:2210.02713のVC次元である。
そこで本研究では,非依存的条件下での対応問題について検討する。
最適余剰誤差は$\tilde{\Theta}(\sqrt{d\eta})$で、Hannekeらによって残された主要なオープンな問題の1つに答えるには、ランダムな学習者を使う必要がある。
おそらく、学習者のランダムビットが敵に完全に見えても、上界は有効である。
一方、我々の下界は標準のPAC型境界よりも強い:各サンプルサイズごとにハード分布を個別に調整する代わりに、敵が過大な誤差を$\Omega(\sqrt{d\eta})$無限に強制できるような単一の固定分布を示す。
関連論文リスト
- Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Better-than-KL PAC-Bayes Bounds [23.87003743389573]
我々は,新しいKLの分岐と密接な結びつきを達成できることを実証した。
我々の結果は、既存のPAC-Bayes境界と非KL分岐は、KLよりも厳密に優れていることが分かっていないという点において、第一種である。
論文 参考訳（メタデータ） (2024-02-14T14:33:39Z) - Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs [32.29254118429081]
我々は,帯域幅フィードバックの下での最適誤りが,全情報ケースの最適誤りよりも少なくとも$O(k)$倍高いことを示す。
また、ランダム化学習者と決定論的学習者の間のギャップに対して、$tildeTheta(k)$のほぼ最適な境界を示す。
論文 参考訳（メタデータ） (2024-02-12T07:20:05Z) - Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。
我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。
V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-19T01:09:24Z) - Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。
学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
論文 参考訳（メタデータ） (2021-06-18T15:01:01Z) - Locality defeats the curse of dimensionality in convolutional
teacher-student scenarios [69.2027612631023]
学習曲線指数$beta$を決定する上で,局所性が重要であることを示す。
我々は、自然の仮定を用いて、トレーニングセットのサイズに応じて減少するリッジでカーネルレグレッションを実行すると、リッジレスの場合と同じような学習曲線指数が得られることを証明して結論付けた。
論文 参考訳（メタデータ） (2021-06-16T08:27:31Z) - Robust learning under clean-label attack [26.323812778809913]
クリーンラベルデータ汚染攻撃におけるロバスト学習の問題点について検討する。
学習目標は、最適なPAC学習よりも難しい攻撃可能な速度を最小限にすることです。
論文 参考訳（メタデータ） (2021-03-01T00:21:15Z) - Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm
for Stochastic Bandits with Corruptions [91.8283876874947]
我々は,T段の固定予算設定において,敵対的腐敗を伴う連続的包帯に対する最適な腕識別(BAI)問題を考察した。
我々は, 汚職の量に依存しない新しいランダム化アルゴリズム, Probabilistic Shrinking($u$) (PSS($u$)) を設計する。
CPS が十分に大きいとき、BAI 確率を$Trightarrow infty$ として達成できるアルゴリズムは存在しない。
論文 参考訳（メタデータ） (2020-10-15T17:34:26Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。