論文の概要: Tight Robustness Certification through the Convex Hull of $\ell_0$ Attacks

• arxiv url: http://arxiv.org/abs/2511.10576v1
• Date: Fri, 14 Nov 2025 01:58:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-14 22:53:22.939998
• Title: Tight Robustness Certification through the Convex Hull of $\ell_0$ Attacks
• Title（参考訳）: $$\ell_0$アタックの凸ハルによる厳密なロバスト性証明
• Authors: Yuval Shapira, Dana Drachsler-Cohen,
• Abstract要約: 画像のいくつかのピクセルを変更することで、ロバスト性検証器を誤認する画素は少ない。 凸船体上の境界を正確に計算する線形境界伝播を示す。 この有界伝播は、最も挑戦的なベンチマークで最先端の検証器を1.24x-7.07xスケールし、幾何学平均は3.16である。
• 参考スコア（独自算出の注目度）: 0.22774471443318753
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Few-pixel attacks mislead a classifier by modifying a few pixels of an image. Their perturbation space is an $\ell_0$-ball, which is not convex, unlike $\ell_p$-balls for $p\geq1$. However, existing local robustness verifiers typically scale by relying on linear bound propagation, which captures convex perturbation spaces. We show that the convex hull of an $\ell_0$-ball is the intersection of its bounding box and an asymmetrically scaled $\ell_1$-like polytope. The volumes of the convex hull and this polytope are nearly equal as the input dimension increases. We then show a linear bound propagation that precisely computes bounds over the convex hull and is significantly tighter than bound propagations over the bounding box or our $\ell_1$-like polytope. This bound propagation scales the state-of-the-art $\ell_0$ verifier on its most challenging robustness benchmarks by 1.24x-7.07x, with a geometric mean of 3.16.
• Abstract（参考訳）: 画像のいくつかのピクセルを変更することで分類器を誤認する画素はほとんどない。 摂動空間は$\ell_0$-ballであり、$\ell_p$-balls for $p\geq1$と異なり凸ではない。 しかし、既存の局所ロバスト性検証器は通常、凸摂動空間をキャプチャする線形境界伝播に依存する。 我々は、$\ell_0$-ball の凸包は、その有界箱と非対称スケールの $\ell_1$-like polytope の交叉であることを示す。 凸殻とこのポリトープの体積は入力次元が増加するにつれてほぼ等しい。 次に、凸船体上の有界分布を正確に計算し、有界箱上の有界伝播または我々の$\ell_1$-like polytopeよりもかなり厳密な線形有界伝播を示す。 この有界伝播は、最も困難な堅牢性ベンチマークにおいて、最先端の$\ell_0$検証器を1.24x-7.07xでスケールし、幾何学平均は3.16である。

関連論文リスト

• Intrinsic Heisenberg Lower Bounds on Schwarzschild and Weyl-Class Spacelike Slices [0.0]
  我々は、静的、球対称、平らな(AF)ブラックホールの水平正方形空間のようなスライス上に、半径$r_g$の測地球に厳密に局在した量子状態に対する座標型ハイゼンベルク型下界を確立する。 Schwarzschild Painlev'e-Gullstrand (PG) スライスでは、誘発される3つの幾何学はユークリッドであり、全ての許容スライスの中で最適なユークリッドスケール $sigma_p r_g ge pihbar$ を復元する。
  論文  参考訳（メタデータ） (2025-09-23T14:47:53Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。 効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。 また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
  論文  参考訳（メタデータ） (2025-02-25T19:08:26Z)
• Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees [56.80920351680438]
  本研究では,重音の存在下でのオンライン学習における高確率収束について検討する。 ノイズモーメントを仮定することなく、幅広い種類の非線形性を保証する。
  論文  参考訳（メタデータ） (2024-10-17T18:25:28Z)
• Higher-dimensional performance of port-based teleportation [4.656345386543646]
  ポートベーステレポーテーション(ポートベーステレポーテーション、Port-based teleportation、PBT)は、通常の量子テレポーテーションの一種で、最終的なユニタリ補正なしに動作する。 我々は,PBTの高次元的性能を,表現のオーバーヘッドが無視できるような「精密な測定」のために計算する。
  論文  参考訳（メタデータ） (2022-07-11T02:51:44Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• An effective solution to convex $1$-body $N$-representability [0.0]
  固定スペクトル $mathbfw$ のアンサンブル状態に対する1ドルボディ$N$表現可能性問題の一般化について検討する。 我々は、対称ポリトープ、スイープポリトープ、ガレオーダーなどのツールを適応し、さらに開発する。
  論文  参考訳（メタデータ） (2021-05-13T17:56:14Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。