論文の概要: No Escape from the Quadratic Barrier: Adaptive Attacks on Linear $\ell_2$ Sketches

• arxiv url: http://arxiv.org/abs/2610.25008v1
• Date: Sun, 18 Oct 2026 04:24:26 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-10-20 22:37:11.20859
• Title: No Escape from the Quadratic Barrier: Adaptive Attacks on Linear $\ell_2$ Sketches
• Title（参考訳）: 二次障壁からの脱出:Linear $\ell_2$ Sketchesのアダプティブアタック
• Abstract要約: 線形スケッチは、固定された低次元射影からの高次元入力の推定特性を示す。 一定の精度で、ランダム化されたユークリッドノルムスケッチは、スケッチ次元$k$で指数関数的に多くの非適応的なクエリをサポートする。 適応的なブラックボックスクエリでは、既知のプライバシベースのディフェンスによって$widetilde(k2)$が保証され、より強力な保証が可能かどうかが公開されたままだった。
• 参考スコア（独自算出の注目度）: 24.793707078723845
• License:
• Abstract: Linear sketches estimate properties of high-dimensional inputs from a fixed low-dimensional projection. At constant accuracy, randomized Euclidean-norm sketches, notably the Johnson-Lindenstrauss transform, support exponentially many nonadaptive queries in sketch dimension $k$. For adaptive black-box queries, known privacy-based defenses guarantee $\widetildeΩ(k^2)$ and it remained open whether stronger guarantees were possible. Prior attacks used more queries, restricted the responder, or provided weaker failure guarantees. We show that the quadratic guarantee is optimal up to logarithmic factors, even with a computationally unbounded responder that knows the matrix, attack algorithm, history, and query distributions and may change its randomized rule after every query. For every fixed hidden $A\in\mathbb{R}^{k\times n}$ with $n>40k$ and target accuracy $α\in (0,1]$, our black-box attack uses $O(k+α^2k^2\log(2+α^2k))$ queries in $\widetilde{O}(1+α^2k)$ adaptive rounds to force, with constant probability, a round in which a constant fraction of answers have $Ω(α)$ relative error. Our results clarify the limits of defending a fixed compressive linear representation by adapting the prediction rule.
• Abstract（参考訳）: 線形スケッチは、固定された低次元射影からの高次元入力の推定特性を示す。 一定の精度で、ランダム化されたユークリッドノルムスケッチ、特にジョンソン・リンデンシュトラウス変換は、スケッチ次元$k$で指数関数的に多くの非適応的クエリをサポートする。 適応的なブラックボックスクエリでは、既知のプライバシベースのディフェンスによって$\widetildeΩ(k^2)$が保証され、より強力な保証が可能かどうかが保証された。 以前の攻撃では、より多くのクエリを使用したり、レスポンスを制限したり、より弱い障害保証を提供したりしていた。 行列, 攻撃アルゴリズム, 履歴, クエリ分布を知っており, 問合せ毎のランダム化規則を変更できる非有界応答器であっても, 二次保証は対数因子に最適であることを示す。 固定されたすべての$A\in\mathbb{R}^{k\times n}$ with $n>40k$とターゲット精度$α\in (0,1]$に対して、我々のブラックボックス攻撃は$O(k+α^2k^2\log(2+α^2k))$ query in $\widetilde{O}(1+α^2k)$ Adaptive rounds to force, with constant probability, a round in a constant fraction of answer has $Ω(α)$ relative error。 その結果, 予測規則を適応させることにより, 固定圧縮線形表現の限界を明らかにした。

関連論文リスト

• Instance-Adaptive Online Multiclass Multicalibration [11.377412007104363]
  我々は、T$ラウンド以上のオンラインマルチクラス多重校正について研究し、余計な保証付きアルゴリズムを提供する。 逆選択された結果の列が次元$s$のアフィン部分空間にある場合、高い確率でエラー$widetilde O(n1/(s+2)T(s+1)/(s+2))$を得る。
  論文  参考訳（メタデータ） (2026-10-11T22:21:57Z)
• Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee [12.89814955033651]
  ランダム化されたスケッチと解法アルゴリズムは、入力を小さな問題に置き換えることで、過剰に制約された$ell$レグレッションを加速する。 我々のスケッチは$ell_infty$ guarantee with $m=O(-2dlog d)$ rows, using one Hadamard pass with a padded internal dimension $N=widetildeO(n+-2d3)$, and is effective to apply。
  論文  参考訳（メタデータ） (2026-08-27T02:43:30Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation [26.519824862057547]
  線形スケッチによる次元の低減は強力で広く使われている手法であるが、敵の入力に弱いことが知られている。 ここでは、Rk × n$ の固定されたスケッチ行列 $A が Rn$ の高次元ベクトル $v を Rk$ の低次元スケッチ $A v に写像する。 我々は、$tildeO(k2)$クエリを使用して、ノルム推定の失敗または逆入力を構成する、普遍的で非適応的な攻撃を示す。
  論文  参考訳（メタデータ） (2025-07-22T08:25:05Z)
• Enjoying Non-linearity in Multinomial Logistic Bandits [56.28491566735463]
  我々は,学習者が期待される報酬を最大化するために行動を選択することで,学習者が環境と相互作用する,多項ロジスティック・バンディット問題を考える。 本稿では,ロジスティックモデルの非線形性の影響を多項集合に拡張し,効率的なアルゴリズムを提案する。 我々のメソッドは、次数 $ smashwidetildemathcalO(R d sqrtKT/kappa_*)$ の問題依存的後悔境界を生じる。
  論文  参考訳（メタデータ） (2025-07-07T08:18:25Z)
• Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update [62.96781471194877]
  ヘビーテール付きバンディットには、ヘビーテール付きノイズ、トランケーション、中央値の2つの基本戦略が導入されている。 本稿では,オンラインミラー降下フレームワークに基づくEmphone-passアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-03-01T09:41:45Z)
• Smoothed Analysis with Adaptive Adversaries [28.940767013349408]
  オンライン問題に対する新しいアルゴリズムの保証を平滑化解析モデルで証明する。 このモデルでは、敵は各時間に一様分布の$tfrac1sigma$倍の密度関数を持つ入力分布を選択する。 本研究の結果は,アルゴリズムの決定と前回の時間ステップにおける入力の実現に基づいて,入力分布を選択可能な適応的敵に対して成り立っている。
  論文  参考訳（メタデータ） (2021-02-16T20:54:49Z)
• 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)

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

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