論文の概要: Sample Complexity Bounds for Robustly Learning Decision Lists against
Evasion Attacks
- arxiv url: http://arxiv.org/abs/2205.06127v1
- Date: Thu, 12 May 2022 14:40:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-13 17:50:16.731353
- Title: Sample Complexity Bounds for Robustly Learning Decision Lists against
Evasion Attacks
- Title（参考訳）: 侵入攻撃に対するロバスト学習決定リストのためのサンプル複雑度境界
- Authors: Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska and James Worrell
- Abstract要約: 敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。
我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。
すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
- 参考スコア（独自算出の注目度）: 25.832511407411637
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A fundamental problem in adversarial machine learning is to quantify how much
training data is needed in the presence of evasion attacks. In this paper we
address this issue within the framework of PAC learning, focusing on the class
of decision lists. Given that distributional assumptions are essential in the
adversarial setting, we work with probability distributions on the input data
that satisfy a Lipschitz condition: nearby points have similar probability. Our
key results illustrate that the adversary's budget (that is, the number of bits
it can perturb on each input) is a fundamental quantity in determining the
sample complexity of robust learning. Our first main result is a
sample-complexity lower bound: the class of monotone conjunctions (essentially
the simplest non-trivial hypothesis class on the Boolean hypercube) and any
superclass has sample complexity at least exponential in the adversary's
budget. Our second main result is a corresponding upper bound: for every fixed
$k$ the class of $k$-decision lists has polynomial sample complexity against a
$\log(n)$-bounded adversary. This sheds further light on the question of
whether an efficient PAC learning algorithm can always be used as an efficient
$\log(n)$-robust learning algorithm under the uniform distribution.
- Abstract（参考訳）: 敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。
本稿では,PAC学習の枠組みの中で,意思決定リストのクラスに着目し,この問題に対処する。
リプシッツ条件を満たす入力データ上の確率分布について, 分布の仮定が相反する設定において必須であることを考慮すると, 近傍点が類似する確率を持つ。
私たちの重要な結果は、敵の予算(つまり各入力で摂動できるビット数)が、ロバストな学習のサンプル複雑性を決定する基本的な量であることを示している。
モノトン結合の類(本質的にはブール超キューブ上の最も単純な非自明な仮説クラス)であり、任意の超クラスは少なくとも敵の予算において指数関数的にサンプル複雑性を持つ。
固定された$k$ に対して、$k$-決定リストのクラスは$\log(n)$-bounded adversaryに対して多項式のサンプル複雑性を持つ。
これにより、効率的なpac学習アルゴリズムが常に一様分布下で効率的な$\log(n)$-robust学習アルゴリズムとして使用できるかどうかという疑問が浮き彫りになる。
関連論文リスト
- Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
細長い分布は、少数の少数派が限られた数のサンプルを含む実世界のデータにしばしば現れる。
近年の研究では、教師付きコントラスト学習がデータ不均衡を緩和する有望な可能性を示していることが明らかになっている。
本稿では,特徴空間の各クラスからのサンプルデータ分布を推定する確率論的コントラスト学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-11T13:44:49Z) - Sample Complexity of Robust Learning against Evasion Attacks [3.8888996044605855]
本研究では, 学習理論の観点から, サンプルの複雑さを考慮し, 逆向きの頑健な学習の実現可能性について検討する。
均一分布下では, 連接関係をしっかり学習する相手の予算への指数的依存は避けられないままである。
問合せ半径が敵の予算に等しければ、分布自由な環境で堅牢な経験的リスクアルゴリズムを開発できることを示す。
論文 参考訳（メタデータ） (2023-08-23T10:51:33Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - 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) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - Robust learning under clean-label attack [26.323812778809913]
クリーンラベルデータ汚染攻撃におけるロバスト学習の問題点について検討する。
学習目標は、最適なPAC学習よりも難しい攻撃可能な速度を最小限にすることです。
論文 参考訳（メタデータ） (2021-03-01T00:21:15Z) - Sample Complexity of Adversarially Robust Linear Classification on
Separated Data [41.30425613353595]
対向的堅牢性を伴う学習の複雑さについて考察する。
非常に分離されたデータの場合、$o(frac1n)$の収束率は達成可能である。
論文 参考訳（メタデータ） (2020-12-19T22:04:59Z) - The Complexity of Adversarially Robust Proper Learning of Halfspaces
with Agnostic Noise [67.27523616312428]
分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。
この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
論文 参考訳（メタデータ） (2020-07-30T04:18:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。