論文の概要: Random Smoothing Might be Unable to Certify $\ell_\infty$ Robustness for
High-Dimensional Images
- arxiv url: http://arxiv.org/abs/2002.03517v3
- Date: Thu, 5 Mar 2020 17:16:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 08:19:31.846883
- Title: Random Smoothing Might be Unable to Certify $\ell_\infty$ Robustness for
High-Dimensional Images
- Title（参考訳）: 高次元画像におけるランダムな平滑化は$\ell_\infty$ロバスト性を証明できない
- Authors: Avrim Blum, Travis Dick, Naren Manoj, Hongyang Zhang
- Abstract要約: 乱数平滑化の難易度は, $ell_p$ の半径 $epsilon$ の攻撃に対して, $p>2$ のとき, 対逆ロバスト性が得られることを示す。
- 参考スコア（独自算出の注目度）: 23.264535488112134
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show a hardness result for random smoothing to achieve certified
adversarial robustness against attacks in the $\ell_p$ ball of radius
$\epsilon$ when $p>2$. Although random smoothing has been well understood for
the $\ell_2$ case using the Gaussian distribution, much remains unknown
concerning the existence of a noise distribution that works for the case of
$p>2$. This has been posed as an open problem by Cohen et al. (2019) and
includes many significant paradigms such as the $\ell_\infty$ threat model. In
this work, we show that any noise distribution $\mathcal{D}$ over
$\mathbb{R}^d$ that provides $\ell_p$ robustness for all base classifiers with
$p>2$ must satisfy
$\mathbb{E}\eta_i^2=\Omega(d^{1-2/p}\epsilon^2(1-\delta)/\delta^2)$ for 99% of
the features (pixels) of vector $\eta\sim\mathcal{D}$, where $\epsilon$ is the
robust radius and $\delta$ is the score gap between the highest-scored class
and the runner-up. Therefore, for high-dimensional images with pixel values
bounded in $[0,255]$, the required noise will eventually dominate the useful
information in the images, leading to trivial smoothed classifiers.
- Abstract（参考訳）: ランダムスムーシングの難易度は,$\ell_p$ 半径 $\epsilon$ の攻撃に対して,$p>2$ のときの正逆ロバスト性を達成できることを示す。
ガウス分布を用いた$\ell_2$ の場合、ランダムな平滑化はよく理解されているが、$p>2$ の場合に適したノイズ分布の存在については不明な点が多い。
これは Cohen ら (2019) によってオープンな問題として提起され、$\ell_\infty$ 脅威モデルのような多くの重要なパラダイムを含んでいる。
この研究で、任意のノイズ分布 $\mathcal{D}$ over $\mathbb{R}^d$ は、$p>2$ を持つ全ての基底分類器に対して $\ell_p$ のロバスト性を提供し、$\mathbb{E}\eta_i^2=\Omega(d^{1-2/p}\epsilon^2(1-\delta)/\delta^2)$ のベクター $\eta\sim\mathcal{D}$ の 99% の特徴(ピクセル)に対して $\epsilon$ はロバストな半径であり、$\delta$ は最高スコア付きクラスとランナーアップの間のスコアギャップであることを示す。
したがって、ピクセル値が$[0,255]$で有界な高次元画像の場合、要求されるノイズが最終的に画像の有用な情報を支配し、自明なスムーズな分類器となる。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - Fitting an ellipsoid to a quadratic number of random points [10.208117253395342]
問題 $(mathrmP)$ が $n$ の標準ガウス確率ベクトルを $mathbbRd$ で中心楕円体の境界に収まることを $n, d to infty$ とみなす。
任意の$varepsilon > 0$ に対して、$n leq (1 - varepsilon) d2 / 4$ ならば、$(mathrmP)$ は高い確率の解を持つ。
論文 参考訳（メタデータ） (2023-07-03T17:46:23Z) - Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture
Models [12.746888269949407]
2進隠れマルコフモデルに対する高次元平均推定問題を考える。
ほぼ最小限の誤差率(対数係数まで)を $|theta_*|,delta,d,n$ の関数として確立する。
論文 参考訳（メタデータ） (2022-06-06T09:34:04Z) - Unique Games hardness of Quantum Max-Cut, and a conjectured
vector-valued Borell's inequality [6.621324975749854]
関数 $f:mathbbRn の -1, 1$ への雑音安定性は $f(boldsymbolx) cdot f(boldsymboly)$ の期待値であることを示す。
我々は $langle f(boldsymbolx), f(boldsymboly)rangle$ の期待値は、関数 $f(x) = x_leq k / Vert x_leq k / によって最小化されると予想する。
論文 参考訳（メタデータ） (2021-11-01T20:45:42Z) - 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) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - 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) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。