論文の概要: Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness
- arxiv url: http://arxiv.org/abs/2002.03239v2
- Date: Fri, 14 Aug 2020 05:02:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 22:28:46.336407
- Title: Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness
- Title（参考訳）: 証明ロバスト性に対するランダム化平滑化の寸法曲線
- Authors: Aounon Kumar, Alexander Levine, Tom Goldstein, Soheil Feizi
- Abstract要約: 我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
- 参考スコア（独自算出の注目度）: 151.67113334248464
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Randomized smoothing, using just a simple isotropic Gaussian distribution,
has been shown to produce good robustness guarantees against $\ell_2$-norm
bounded adversaries. In this work, we show that extending the smoothing
technique to defend against other attack models can be challenging, especially
in the high-dimensional regime. In particular, for a vast class of
i.i.d.~smoothing distributions, we prove that the largest $\ell_p$-radius that
can be certified decreases as $O(1/d^{\frac{1}{2} - \frac{1}{p}})$ with
dimension $d$ for $p > 2$. Notably, for $p \geq 2$, this dependence on $d$ is
no better than that of the $\ell_p$-radius that can be certified using
isotropic Gaussian smoothing, essentially putting a matching lower bound on the
robustness radius. When restricted to {\it generalized} Gaussian smoothing,
these two bounds can be shown to be within a constant factor of each other in
an asymptotic sense, establishing that Gaussian smoothing provides the best
possible results, up to a constant factor, when $p \geq 2$. We present
experimental results on CIFAR to validate our theory. For other smoothing
distributions, such as, a uniform distribution within an $\ell_1$ or an
$\ell_\infty$-norm ball, we show upper bounds of the form $O(1 / d)$ and $O(1 /
d^{1 - \frac{1}{p}})$ respectively, which have an even worse dependence on $d$.
- Abstract（参考訳）: 単純な等方的ガウス分布を用いたランダムな平滑化は、$$\ell_2$-normの有界対向に対して良好な堅牢性を保証することが示されている。
本研究では,特に高次元環境において,他の攻撃モデルから守るための平滑化手法を拡張することは困難であることを示す。
特に、不規則分布の広大なクラスに対して、証明可能な最大の$\ell_p$-radius が $O(1/d^{\frac{1}{2} - \frac{1}{p}})$ として減少し、次元が $d$ for $p > 2$ となることを証明している。
特に、$p \geq 2$ の場合、この$d$ への依存は、等方性ガウス平滑化を用いて証明できる$\ell_p$-radius のそれと変わらない。
一般化されたガウスの滑らか化に制限された場合、これらの2つの境界は漸近的な意味で互いに定数係数内にあることが示され、$p \geq 2$ のとき、ガウスの滑らか化が定数係数まで最高の結果をもたらすことが確かめられる。
我々は,CIFARを用いた理論の検証実験を行った。
他の平滑化分布、例えば、$\ell_1$ または $\ell_\infty$-norm 球内の一様分布に対して、それぞれ $o(1 / d)$ と $o(1 / d^{1 - \frac{1}{p}}) という形の上限を示し、これは $d$ に依存しない。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Sharper Utility Bounds for Differentially Private Models [20.246768861331276]
最初の$mathcalObig (fracsqrtpnepsilonbig)$ 高確率過剰集団リスクは、差分プライベートアルゴリズムに縛られる。
新しいアルゴリズムm-NGPは、実データセット上での差分プライベートモデルの性能を改善する。
論文 参考訳（メタデータ） (2022-04-22T07:03:13Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - From Smooth Wasserstein Distance to Dual Sobolev Norm: Empirical
Approximation and Statistical Applications [18.618590805279187]
我々は$mathsfW_p(sigma)$が$pth次スムーズな双対ソボレフ$mathsfd_p(sigma)$で制御されていることを示す。
我々は、すべての次元において$sqrtnmathsfd_p(sigma)(hatmu_n,mu)$の極限分布を導出する。
論文 参考訳（メタデータ） (2021-01-11T17:23:24Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Learning Mixtures of Spherical Gaussians via Fourier Analysis [0.5381004207943596]
標本と計算複雑性の有界性は、$omega(1) leq d leq O(log k)$のとき以前には分かっていなかった。
これらの著者はまた、半径$d$ in $d$ dimensions, if $d$ is $Theta(sqrtd)$ in $d$ dimensions, if $d$が少なくとも$poly(k, frac1delta)$であるとき、ガウスのランダム混合の複雑さのサンプルを示す。
論文 参考訳（メタデータ） (2020-04-13T08:06:29Z) - Randomized Smoothing of All Shapes and Sizes [29.40896576138737]
最適」ノルムの適切な概念に対して、任意の「ニッチ」ノルムに対する最適な滑らか化はノルムの *Wulff Crystal* によって与えられるレベル集合を持つことを示す。
ここでは、*バナッハ空間コタイプ*の理論を通して、現在のランダム化平滑化技術に基本的な限界を示す。
論文 参考訳（メタデータ） (2020-02-19T11:41:09Z) - Random Smoothing Might be Unable to Certify $\ell_\infty$ Robustness for
High-Dimensional Images [23.264535488112134]
乱数平滑化の難易度は, $ell_p$ の半径 $epsilon$ の攻撃に対して, $p>2$ のとき, 対逆ロバスト性が得られることを示す。
論文 参考訳（メタデータ） (2020-02-10T03:26:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。