論文の概要: Sample Complexity of Robust Learning against Evasion Attacks
- arxiv url: http://arxiv.org/abs/2308.12054v1
- Date: Wed, 23 Aug 2023 10:51:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-24 14:25:20.256845
- Title: Sample Complexity of Robust Learning against Evasion Attacks
- Title（参考訳）: 回避攻撃に対するロバスト学習のサンプル複雑性
- Authors: Pascale Gourdeau
- Abstract要約: 本研究では, 学習理論の観点から, サンプルの複雑さを考慮し, 逆向きの頑健な学習の実現可能性について検討する。
均一分布下では, 連接関係をしっかり学習する相手の予算への指数的依存は避けられないままである。
問合せ半径が敵の予算に等しければ、分布自由な環境で堅牢な経験的リスクアルゴリズムを開発できることを示す。
- 参考スコア（独自算出の注目度）: 3.8888996044605855
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: It is becoming increasingly important to understand the vulnerability of
machine learning models to adversarial attacks. One of the fundamental problems
in adversarial machine learning is to quantify how much training data is needed
in the presence of evasion attacks, where data is corrupted at test time. In
this thesis, we work with the exact-in-the-ball notion of robustness and study
the feasibility of adversarially robust learning from the perspective of
learning theory, considering sample complexity.
We first explore the setting where the learner has access to random examples
only, and show that distributional assumptions are essential. We then focus on
learning problems with distributions on the input data that satisfy a Lipschitz
condition and show that robustly learning monotone conjunctions has sample
complexity at least exponential in the adversary's budget (the maximum number
of bits it can perturb on each input). However, if the adversary is restricted
to perturbing $O(\log n)$ bits, then one can robustly learn conjunctions and
decision lists w.r.t. log-Lipschitz distributions.
We then study learning models where the learner is given more power. We first
consider local membership queries, where the learner can query the label of
points near the training sample. We show that, under the uniform distribution,
the exponential dependence on the adversary's budget to robustly learn
conjunctions remains inevitable. We then introduce a local equivalence query
oracle, which returns whether the hypothesis and target concept agree in a
given region around a point in the training sample, and a counterexample if it
exists. We show that if the query radius is equal to the adversary's budget, we
can develop robust empirical risk minimization algorithms in the
distribution-free setting. We give general query complexity upper and lower
bounds, as well as for concrete concept classes.
- Abstract（参考訳）: 敵攻撃に対する機械学習モデルの脆弱性を理解することがますます重要になっている。
敵機械学習の基本的な問題のひとつは、テスト時にデータが破損する回避攻撃の存在下で、どれだけのトレーニングデータが必要とされるかを定量化することである。
本論文では,頑健性という厳密な概念に取り組み,サンプル複雑性を考慮した学習理論の観点から,対向的に頑健な学習の実現可能性について検討する。
まず,学習者がランダムな例のみにアクセス可能な環境について検討し,分布仮定が重要であることを示す。
次に,リプシッツ条件を満たす入力データに分布を持つ学習問題に焦点を当て,ロバストに学習する単調結合は,少なくとも敵の予算(各入力に摂動できる最大ビット数)において指数関数的にサンプル複雑性を有することを示す。
しかし、敵が$O(\log n)$ bitsの摂動に制限されている場合、対数-Lipschitz分布の接続と決定リストをしっかりと学習することができる。
そして、学習者がより多くの力を与えられる学習モデルを研究する。
まず,学習者が学習サンプルの近傍の点のラベルをクエリできる局所的会員クエリについて検討する。
均一分布下では, 連接関係をしっかり学習する相手の予算への指数的依存は避けられないままである。
次に,局所同値クエリoracleを導入し,仮説と対象概念がトレーニングサンプルの点付近の所定の領域で一致しているかどうかと,それが存在する場合の反例を返す。
クエリ半径が敵の予算に等しければ、分散フリー設定においてロバストな経験的リスク最小化アルゴリズムを開発できることを示す。
一般的なクエリの複雑さを上と下の境界に加え、具体的な概念クラスにも与えます。
関連論文リスト
- 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) - Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。
本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
論文 参考訳（メタデータ） (2022-10-26T03:19:24Z) - On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。
これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文 参考訳（メタデータ） (2022-10-22T19:07:26Z) - When are Local Queries Useful for Robust Learning? [25.832511407411637]
本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。
我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。
我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
論文 参考訳（メタデータ） (2022-10-12T11:04:22Z) - Sample Complexity Bounds for Robustly Learning Decision Lists against
Evasion Attacks [25.832511407411637]
敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。
我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。
すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
論文 参考訳（メタデータ） (2022-05-12T14:40:18Z) - Examining and Combating Spurious Features under Distribution Shift [94.31956965507085]
我々は、最小限の統計量という情報理論の概念を用いて、ロバストで刺激的な表現を定義し、分析する。
入力分布のバイアスしか持たない場合でも、モデルはトレーニングデータから急激な特徴を拾い上げることができることを証明しています。
分析から着想を得た結果,グループDROは,グループ同士の相関関係を直接考慮しない場合に失敗する可能性が示唆された。
論文 参考訳（メタデータ） (2021-06-14T05:39:09Z) - Learning and Certification under Instance-targeted Poisoning [49.55596073963654]
インスタンスターゲット中毒攻撃におけるPAC学習性と認証について検討する。
敵の予算がサンプルの複雑さに比例してスケールすると、PACの学習性と認定が達成可能であることを示す。
実データセット上でのK近傍, ロジスティック回帰, 多層パーセプトロン, 畳み込みニューラルネットワークの堅牢性を実証的に検討する。
論文 参考訳（メタデータ） (2021-05-18T17:48:15Z) - Defensive Few-shot Learning [77.82113573388133]
本稿では,防御的数発学習という新たな課題について検討する。
敵の攻撃に対して頑丈な数発のモデルを学習することを目的としている。
提案したフレームワークは、既存の数発のモデルを敵攻撃に対して効果的に堅牢にすることができる。
論文 参考訳（メタデータ） (2019-11-16T05:57:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。