論文の概要: On the Robustness of CountSketch to Adaptive Inputs
- arxiv url: http://arxiv.org/abs/2202.13736v1
- Date: Mon, 28 Feb 2022 13:04:41 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-02 00:27:54.650098
- Title: On the Robustness of CountSketch to Adaptive Inputs
- Title（参考訳）: 適応入力に対するcountsketchのロバスト性について
- Authors: Edith Cohen, Xin Lyu, Jelani Nelson, Tam\'as Sarl\'os, Moshe Shechner,
Uri Stemmer
- Abstract要約: CountSketchは、ベクトルをランダム化線形測定を用いて低次元にマッピングする一般的な次元削減手法である。
古典的推定器はロバストではなく、スケッチサイズの順序の複数のクエリで攻撃可能であることを示す。
本研究では,スケッチサイズで2次的なクエリ数を推定できるロバストな推定器を提案する。
- 参考スコア（独自算出の注目度）: 22.34019676119989
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: CountSketch is a popular dimensionality reduction technique that maps vectors
to a lower dimension using randomized linear measurements. The sketch supports
recovering $\ell_2$-heavy hitters of a vector (entries with $v[i]^2 \geq
\frac{1}{k}\|\boldsymbol{v}\|^2_2$). We study the robustness of the sketch in
adaptive settings where input vectors may depend on the output from prior
inputs. Adaptive settings arise in processes with feedback or with adversarial
attacks. We show that the classic estimator is not robust, and can be attacked
with a number of queries of the order of the sketch size. We propose a robust
estimator (for a slightly modified sketch) that allows for quadratic number of
queries in the sketch size, which is an improvement factor of $\sqrt{k}$ (for
$k$ heavy hitters) over prior work.
- Abstract（参考訳）: CountSketchは、ベクトルをランダム化線形測定を用いて低次元にマッピングする一般的な次元削減手法である。
このスケッチは、ベクトルの$\ell_2$-heavyヒットタの回収をサポートする($v[i]^2 \geq \frac{1}{k}\|\boldsymbol{v}\|^2_2$)。
入力ベクトルが先行入力からの出力に依存する可能性のある適応的設定におけるスケッチのロバスト性について検討する。
適応的な設定は、フィードバックや敵攻撃を伴うプロセスで発生する。
古典的推定器はロバストではなく、スケッチサイズの順序の複数のクエリで攻撃可能であることを示す。
我々は,先行作業よりも$\sqrt{k}$ ($k$ heavy hitters)の改善係数である,スケッチサイズにおけるクエリの二次数を可能にするロバストな推定器を提案する。
関連論文リスト
- 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) - SketchINR: A First Look into Sketches as Implicit Neural Representations [120.4152701687737]
暗黙的ニューラルモデルを用いてベクトルスケッチの表現を前進させるSketchINRを提案する。
可変長ベクトルスケッチは、時間とストロークの関数として下層の形状を暗黙的に符号化する固定次元の潜時空間に圧縮される。
初めてSketchINRは、ストロークの数と複雑さの点で、さまざまな抽象化でスケッチを再現する人間の能力をエミュレートする。
論文 参考訳（メタデータ） (2024-03-14T12:49:29Z) - Sketched Ridgeless Linear Regression: The Role of Downsampling [5.615701056715101]
スケッチしたリッジレス最小2乗推定器のサンプル外予測リスクを2つ検討した。
サンプル外予測リスクを最小限に抑える最適なスケッチサイズを同定する。
我々は解析を拡張し、中心極限定理と不特定モデルをカバーする。
論文 参考訳（メタデータ） (2023-02-02T13:21:09Z) - Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of
CountSketch to Adaptive Inputs [25.724067100459916]
入力が適応的であれば、$O(ell)$クエリの後に逆入力を構築することができる。
我々の攻撃は「自然な」非適応入力(最終逆入力のみが適応的に選択される)を使用し、あらゆる正しい推定器で普遍的に適用する。
論文 参考訳（メタデータ） (2022-07-03T05:00:55Z) - Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured
Inputs [2.737640280995564]
我々はネットワーク埋め込みを用いてテンソルネットワーク構造入力の次元的低減を行う。
このような埋め込みを用いて、入力データを効率的にスケッチするアルゴリズムを提供する。
列車のラウンドリングのための既存のアルゴリズムの最適性を示す。
論文 参考訳（メタデータ） (2022-05-26T05:27:31Z) - Complex-to-Real Sketches for Tensor Products with Applications to the
Polynomial Kernel [15.535749953841274]
p$ベクトルの積のランダム化されたスケッチは、統計効率と計算加速度のトレードオフに従う。
本稿では、実乱射影を複素射影に置き換える、よく知られたスケッチの単純な複素対Real (CtR) 修正を提案する。
本手法は,文献の他のランダム化近似と比較して,精度と速度の面で最先端の性能を達成することを示す。
論文 参考訳（メタデータ） (2022-02-04T09:15:43Z) - A Precise Performance Analysis of Support Vector Regression [105.94855998235232]
我々は,n$の線形測定に応用したハードおよびソフトサポートベクター回帰法について検討した。
得られた結果は、ハードおよびソフトサポートベクトル回帰アルゴリズムの設計に介入するパラメータを最適に調整するために使用される。
論文 参考訳（メタデータ） (2021-05-21T14:26:28Z) - Learning-Augmented Sketches for Hessians [54.97773807211337]
第二次手法の文脈でヘッセンの学習スケッチを設計する方法を紹介します。
学習したスケッチは,「学習されていない」スケッチと比較して,重要な問題に対する近似精度が向上することを示す。
論文 参考訳（メタデータ） (2021-02-24T14:50:59Z) - Learning the Positions in CountSketch [51.15935547615698]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習アルゴリズムを提案する。
このアルゴリズムは, 従来よりも低階近似の精度を向上し, 初めて$k$-meansクラスタリングのような他の問題に適用できることを示す。
論文 参考訳（メタデータ） (2020-07-20T05:06:29Z) - Error Estimation for Sketched SVD via the Bootstrap [60.67199274260768]
本稿では,スケッチ化された特異ベクトル/値の実際の誤差を数値的に推定する完全データ駆動型ブートストラップ法を開発した。
この方法は、スケッチされたオブジェクトのみで動作するため、計算コストが安い。
論文 参考訳（メタデータ） (2020-03-10T19:14:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。