論文の概要: The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
- arxiv url: http://arxiv.org/abs/2507.16345v1
- Date: Tue, 22 Jul 2025 08:25:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-23 21:34:14.031553
- Title: The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
- Title（参考訳）: 圧縮のコスト:$$$\ell_2$ Normの推定のためのケッチの四角いブラックボックス攻撃
- Authors: Sara Ahmadian, Edith Cohen, Uri Stemmer,
- Abstract要約: 線形スケッチによる次元の低減は強力で広く使われている手法であるが、敵の入力に弱いことが知られている。
Rk X n$ の固定されたスケッチ行列 A は、高次元ベクトル v $in Rn$ を、低次元スケッチ A v in $Rk$ に写像する。
我々は、tilde(O)($k2$)クエリを使用して、ノルム推定の失敗を引き起こすか、クエリ分布の最適推定器が失敗する逆入力を構築する、普遍的で非適応的な攻撃を示す。
- 参考スコア（独自算出の注目度）: 27.82218389495089
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Dimensionality reduction via linear sketching is a powerful and widely used technique, but it is known to be vulnerable to adversarial inputs. We study the black-box adversarial setting, where a fixed, hidden sketching matrix A in $R^{k X n}$ maps high-dimensional vectors v $\in R^n$ to lower-dimensional sketches A v in $R^k$, and an adversary can query the system to obtain approximate ell2-norm estimates that are computed from the sketch. We present a universal, nonadaptive attack that, using tilde(O)($k^2$) queries, either causes a failure in norm estimation or constructs an adversarial input on which the optimal estimator for the query distribution (used by the attack) fails. The attack is completely agnostic to the sketching matrix and to the estimator: It applies to any linear sketch and any query responder, including those that are randomized, adaptive, or tailored to the query distribution. Our lower bound construction tightly matches the known upper bounds of tilde(Omega)($k^2$), achieved by specialized estimators for Johnson Lindenstrauss transforms and AMS sketches. Beyond sketching, our results uncover structural parallels to adversarial attacks in image classification, highlighting fundamental vulnerabilities of compressed representations.
- Abstract（参考訳）: 線形スケッチによる次元の低減は強力で広く使われている手法であるが、敵の入力に弱いことが知られている。
我々はブラックボックスの逆数設定について検討し、そこでは固定されたスケッチ行列 A in $R^{k X n}$ が高次元ベクトル v $\in R^n$ から低次元スケッチ A v in $R^k$ に写像し、敵は、スケッチから計算された近似EL2-ノルム推定を求めることができる。
我々は、tilde(O)($k^2$)クエリを使用して、ノルム推定の失敗を引き起こすか、あるいは(攻撃によって使用される)クエリ分布の最適推定器が失敗する逆入力を構築する、普遍的で非適応的な攻撃を提案する。
この攻撃は、スケッチ行列と推定器に完全に依存しない: 線形スケッチとクエリ応答器(ランダム化、適応、クエリ分布に合わせて調整されたものを含む)に適用する。
我々の下界構造は、Johnson Lindenstrauss変換とAMSスケッチの特殊推定器によって達成された、既知の tilde(Omega)($k^2$) の上界と強く一致する。
スケッチの他に,画像分類における対立攻撃に対する構造的並列性を明らかにし,圧縮表現の基本的脆弱性を明らかにする。
関連論文リスト
- Refined Risk Bounds for Unbounded Losses via Transductive Priors [58.967816314671296]
線形回帰の逐次変分を2乗損失、ヒンジ損失の分類問題、ロジスティック回帰で再検討する。
我々の鍵となるツールは、慎重に選択された導出先を持つ指数重み付けアルゴリズムに基づいている。
論文 参考訳（メタデータ） (2024-10-29T00:01:04Z) - Sparse Linear Bandits with Blocking Constraints [22.01704171400845]
データ・ポーア・システマにおける高次元スパース線形包帯問題について検討する。
線形モデルに対するラッソ推定器の新たなオフライン統計的保証を示す。
本稿では,最小限のコストで最適空間パラメータ$k$の知識を必要としない相関に基づくメタアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-10-26T01:42:03Z) - $σ$-zero: Gradient-based Optimization of $\ell_0$-norm Adversarial Examples [14.17412770504598]
入力摂動の作成には$ell_infty$-normの制約が使用できることを示す。
我々は $sigma$NISTtt- と呼ばれる新しい $ell_infty$-norm 攻撃を提案する。
論文 参考訳（メタデータ） (2024-02-02T20:08:11Z) - Asymptotically free sketched ridge ensembles: Risks, cross-validation, and tuning [5.293069542318491]
我々は、スケッチされたリッジ回帰アンサンブルの予測リスクを推定するために、ランダム行列理論を用いて、一般化されたクロスバリデーション(GCV)の整合性を確立する。
正方形の予測リスクに対して,無作為な等価な暗黙のリッジバイアスとスケッチに基づく分散を分解し,無限アンサンブルにおけるスケッチサイズのみによるグローバルなチューニングが可能であることを証明した。
また,小型のスケッチ付きリッジ・アンサンブルを用いて,GCVを用いて非ケッチ・リッジ・レグレッションのリスクを効率的に推定できるアンサンブル・トリックを提案する。
論文 参考訳（メタデータ） (2023-10-06T16:27:43Z) - Iterative Sketching for Secure Coded Regression [66.53950020718021]
分散線形回帰を高速化する手法を提案する。
具体的には、方程式の系の基礎をランダムに回転させ、次にサブサンプルブロックを回転させ、情報を同時に確保し、回帰問題の次元を小さくする。
論文 参考訳（メタデータ） (2023-08-08T11:10:42Z) - On the Robustness of CountSketch to Adaptive Inputs [22.34019676119989]
CountSketchは、ベクトルをランダム化線形測定を用いて低次元にマッピングする一般的な次元削減手法である。
古典的推定器はロバストではなく、スケッチサイズの順序の複数のクエリで攻撃可能であることを示す。
本研究では,スケッチサイズで2次的なクエリ数を推定できるロバストな推定器を提案する。
論文 参考訳（メタデータ） (2022-02-28T13:04:41Z) - Mean Nystr\"om Embeddings for Adaptive Compressive Learning [25.89586989444021]
本研究では,データ依存型Nystr"om近似に基づくスケッチ処理の考え方について検討する。
我々はk平均クラスタリングとガウスモデルについて、固定されたスケッチサイズでは、Nystr"omのスケッチはランダムな特徴で構築されたスケッチよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-10-21T09:05:58Z) - Transferable Sparse Adversarial Attack [62.134905824604104]
オーバーフィッティング問題を緩和するジェネレータアーキテクチャを導入し、転送可能なスパース対逆例を効率的に作成する。
提案手法は,他の最適化手法よりも700$times$高速な推論速度を実現する。
論文 参考訳（メタデータ） (2021-05-31T06:44:58Z) - Learning-Augmented Sketches for Hessians [54.97773807211337]
第二次手法の文脈でヘッセンの学習スケッチを設計する方法を紹介します。
学習したスケッチは,「学習されていない」スケッチと比較して,重要な問題に対する近似精度が向上することを示す。
論文 参考訳（メタデータ） (2021-02-24T14:50:59Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳（メタデータ） (2020-09-04T04:10:39Z) - Sharp Statistical Guarantees for Adversarially Robust Gaussian
Classification [54.22421582955454]
逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。
結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
論文 参考訳（メタデータ） (2020-06-29T21:06:52Z) - Error Estimation for Sketched SVD via the Bootstrap [60.67199274260768]
本稿では,スケッチ化された特異ベクトル/値の実際の誤差を数値的に推定する完全データ駆動型ブートストラップ法を開発した。
この方法は、スケッチされたオブジェクトのみで動作するため、計算コストが安い。
論文 参考訳（メタデータ） (2020-03-10T19:14:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。