論文の概要: Sample Complexity of Adversarially Robust Linear Classification on
Separated Data
- arxiv url: http://arxiv.org/abs/2012.10794v1
- Date: Sat, 19 Dec 2020 22:04:59 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-01 12:01:01.766780
- Title: Sample Complexity of Adversarially Robust Linear Classification on
Separated Data
- Title（参考訳）: 分離データに基づく逆ロバスト線形分類のサンプル複雑性
- Authors: Robi Bhattacharjee, Somesh Jha, Kamalika Chaudhuri
- Abstract要約: 対向的堅牢性を伴う学習の複雑さについて考察する。
非常に分離されたデータの場合、$o(frac1n)$の収束率は達成可能である。
- 参考スコア（独自算出の注目度）: 41.30425613353595
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the sample complexity of learning with adversarial robustness.
Most prior theoretical results for this problem have considered a setting where
different classes in the data are close together or overlapping. Motivated by
some real applications, we consider, in contrast, the well-separated case where
there exists a classifier with perfect accuracy and robustness, and show that
the sample complexity narrates an entirely different story. Specifically, for
linear classifiers, we show a large class of well-separated distributions where
the expected robust loss of any algorithm is at least $\Omega(\frac{d}{n})$,
whereas the max margin algorithm has expected standard loss $O(\frac{1}{n})$.
This shows a gap in the standard and robust losses that cannot be obtained via
prior techniques. Additionally, we present an algorithm that, given an instance
where the robustness radius is much smaller than the gap between the classes,
gives a solution with expected robust loss is $O(\frac{1}{n})$. This shows that
for very well-separated data, convergence rates of $O(\frac{1}{n})$ are
achievable, which is not the case otherwise. Our results apply to robustness
measured in any $\ell_p$ norm with $p > 1$ (including $p = \infty$).
- Abstract（参考訳）: 対向的堅牢性を伴う学習の複雑さについて考察する。
この問題の最も初期の理論的な結果は、データの異なるクラスが近接したり重なり合うような設定を考えることである。
現実の応用に動機づけられ、対照的に、完全な正確性と堅牢性を持った分類器が存在する、十分に分離されたケースを検討し、サンプル複雑性が全く異なるストーリーを成すことを示す。
具体的には、線形分類器に対して、任意のアルゴリズムの期待ロバストな損失が少なくとも$\omega(\frac{d}{n})$であるようなよく分離された分布のクラスを示し、一方max marginアルゴリズムは標準損失$o(\frac{1}{n})$を期待する。
これは、従来の技術では得られない標準と堅牢な損失のギャップを示している。
さらに,ロバスト性半径がクラス間のギャップよりはるかに小さい場合において,ロバスト損失が期待される解が$o(\frac{1}{n})$となるようなアルゴリズムを提案する。
これは、非常によく分離されたデータの場合、$o(\frac{1}{n})$の収束率は達成可能であることを示している。
我々の結果は、$p > 1$ ($p = \infty$を含む) の任意の$\ell_p$ノルムで測定されたロバスト性に適用できる。
関連論文リスト
- Testable Learning with Distribution Shift [9.036777309376697]
分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。
テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。
ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
論文 参考訳（メタデータ） (2023-11-25T23:57:45Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - When are Local Queries Useful for Robust Learning? [25.832511407411637]
本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。
我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。
我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
論文 参考訳（メタデータ） (2022-10-12T11:04:22Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Sample Complexity Bounds for Robustly Learning Decision Lists against
Evasion Attacks [25.832511407411637]
敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。
我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。
すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
論文 参考訳（メタデータ） (2022-05-12T14:40:18Z) - Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of
Them All? [17.514226416388475]
我々は、個々の公平性の観点からr$-nn問題を研究し、平等な機会を提供する。
クエリから$r$の距離内のすべてのポイントは、返されるのと同じ確率を持つ必要があります。
フェアNN問題の正確かつ近似的な変種に対して,複数の効率的なデータ構造を提案する。
論文 参考訳（メタデータ） (2021-01-26T16:13:07Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。