論文の概要: Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of
CountSketch to Adaptive Inputs
- arxiv url: http://arxiv.org/abs/2207.00956v1
- Date: Sun, 3 Jul 2022 05:00:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-06 11:37:35.698720
- Title: Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of
CountSketch to Adaptive Inputs
- Title(参考訳): ハッシュ化トリックのトリック:適応入力に対するcountsketchのロバスト性について
- Authors: Edith Cohen, Jelani Nelson, Tam\'as Sarl\'os, Uri Stemmer
- Abstract要約: 入力が適応的であれば、$O(ell)$クエリの後に逆入力を構築することができる。
我々の攻撃は「自然な」非適応入力(最終逆入力のみが適応的に選択される)を使用し、あらゆる正しい推定器で普遍的に適用する。
- 参考スコア(独自算出の注目度): 25.724067100459916
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: CountSketch and Feature Hashing (the "hashing trick") are popular randomized
dimensionality reduction methods that support recovery of $\ell_2$-heavy
hitters (keys $i$ where $v_i^2 > \epsilon \|\boldsymbol{v}\|_2^2$) and
approximate inner products. When the inputs are {\em not adaptive} (do not
depend on prior outputs), classic estimators applied to a sketch of size
$O(\ell/\epsilon)$ are accurate for a number of queries that is exponential in
$\ell$. When inputs are adaptive, however, an adversarial input can be
constructed after $O(\ell)$ queries with the classic estimator and the best
known robust estimator only supports $\tilde{O}(\ell^2)$ queries. In this work
we show that this quadratic dependence is in a sense inherent: We design an
attack that after $O(\ell^2)$ queries produces an adversarial input vector
whose sketch is highly biased. Our attack uses "natural" non-adaptive inputs
(only the final adversarial input is chosen adaptively) and universally applies
with any correct estimator, including one that is unknown to the attacker. In
that, we expose inherent vulnerability of this fundamental method.
- Abstract(参考訳): CountSketch と Feature Hashing は、$\ell_2$-heavy hitter (keys $i$ where $v_i^2 > \epsilon \|\boldsymbol{v}\|_2^2$) と近似内積の回復をサポートする一般的なランダム化次元減少法である。
入力が適応的でない場合(事前の出力に依存しない)、$O(\ell/\epsilon)$のスケッチに適用される古典的な推定子は$\ell$で指数関数的な多くのクエリに対して正確である。
しかし、入力が適応的である場合、逆入力は古典的な推定器で$o(\ell)$クエリ後に構築することができ、最もよく知られたロバスト推定器は$\tilde{o}(\ell^2)$クエリのみをサポートする。
我々は、$O(\ell^2)$クエリの後に、スケッチに非常に偏りがある逆入力ベクトルを生成するような攻撃を設計する。
攻撃は「自然な」非適応入力(最終敵入力のみを適応的に選択する)を使用し、攻撃者に未知のものを含む任意の正しい推定器に普遍的に適用される。
そこで本手法の本質的脆弱性を明らかにする。
関連論文リスト
- Scaling Up Differentially Private LASSO Regularized Logistic Regression
via Faster Frank-Wolfe Iterations [51.14495595270775]
我々は,Frank-Wolfeアルゴリズムを$L_1$のペナル化線形回帰に適応させ,スパース入力を認識し,有効利用する。
この方法では,プライバシパラメータ$epsilon$の値とデータセットの分散度に応じて,最大2,200times$の係数でランタイムを削減できることを示す。
論文 参考訳(メタデータ) (2023-10-30T19:52:43Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳(メタデータ) (2022-05-23T17:59:18Z) - On the Robustness of CountSketch to Adaptive Inputs [22.34019676119989]
CountSketchは、ベクトルをランダム化線形測定を用いて低次元にマッピングする一般的な次元削減手法である。
古典的推定器はロバストではなく、スケッチサイズの順序の複数のクエリで攻撃可能であることを示す。
本研究では,スケッチサイズで2次的なクエリ数を推定できるロバストな推定器を提案する。
論文 参考訳(メタデータ) (2022-02-28T13:04:41Z) - Evaluating Probabilistic Inference in Deep Learning: Beyond Marginal
Predictions [37.92747047688873]
一般的に使われる$tau=1$は、多くの関心のある設定で良い決定を下すには不十分であることを示す。
さらに、$tau$が成長するにつれて、$mathbfd_mathrmKLtau$は任意の決定に対する普遍的な保証を回復する。
論文 参考訳(メタデータ) (2021-07-20T01:55:01Z) - Smoothed Analysis with Adaptive Adversaries [28.940767013349408]
オンライン問題に対する新しいアルゴリズムの保証を平滑化解析モデルで証明する。
このモデルでは、敵は各時間に一様分布の$tfrac1sigma$倍の密度関数を持つ入力分布を選択する。
本研究の結果は,アルゴリズムの決定と前回の時間ステップにおける入力の実現に基づいて,入力分布を選択可能な適応的敵に対して成り立っている。
論文 参考訳(メタデータ) (2021-02-16T20:54:49Z) - CountSketches, Feature Hashing and the Median of Three [18.85876632959721]
古典的なCountSketch法は、(高次元)ユークリッドベクトル $v$ を次元 $(2t-1) s$ に変換するスパースでランダムな射影である。
我々の主な貢献は、Count-Sketchの新しい分析であり、$t > 1$ のとき、$O(min|v|2/s2,|v|2/s2)$ への分散の改善を示す。
この結果は、基本的にCountSketchと同一であるが中央値を使用しないFeature Hashing法が可能であることを示唆している。
論文 参考訳(メタデータ) (2021-02-03T18:45:21Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳(メタデータ) (2020-11-21T01:33:15Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳(メタデータ) (2020-11-19T17:21:37Z) - Conditional Uncorrelation and Efficient Non-approximate Subset Selection
in Sparse Regression [72.84177488527398]
相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。
提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
論文 参考訳(メタデータ) (2020-09-08T20:32:26Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳(メタデータ) (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。