論文の概要: 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)$クエリの後に、スケッチに非常に偏りがある逆入力ベクトルを生成するような攻撃を設計する。
攻撃は「自然な」非適応入力(最終敵入力のみを適応的に選択する)を使用し、攻撃者に未知のものを含む任意の正しい推定器に普遍的に適用される。
そこで本手法の本質的脆弱性を明らかにする。
関連論文リスト
- Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳（メタデータ） (2024-08-27T18:28:31Z) - 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) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - 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) - 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) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。