論文の概要: Improving \textit{Tug-of-War} sketch using Control-Variates method
- arxiv url: http://arxiv.org/abs/2203.02432v1
- Date: Fri, 4 Mar 2022 17:01:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-07 17:19:59.855441
- Title: Improving \textit{Tug-of-War} sketch using Control-Variates method
- Title（参考訳）: Control-Variates 法による \textit{Tug-of-War} スケッチの改良
- Authors: Rameshwar Pratap and Bhisham Dev Verma and Raghav Kulkarni
- Abstract要約: 我々はモンテカルロ・シミュレーションの分散還元で主に知られている古典的な制御-分散性ラベンベルクの手法を用いる。
本稿では,提案手法の理論的解析を行い,実世界のデータセットと合成実験を補完する。
- 参考スコア（独自算出の注目度）: 0.12891210250935145
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Computing space-efficient summary, or \textit{a.k.a. sketches}, of large
data, is a central problem in the streaming algorithm. Such sketches are used
to answer \textit{post-hoc} queries in several data analytics tasks. The
algorithm for computing sketches typically requires to be fast, accurate, and
space-efficient. A fundamental problem in the streaming algorithm framework is
that of computing the frequency moments of data streams. The frequency moments
of a sequence containing $f_i$ elements of type $i$, are the numbers
$\mathbf{F}_k=\sum_{i=1}^n {f_i}^k,$ where $i\in [n]$. This is also called as
$\ell_k$ norm of the frequency vector $(f_1, f_2, \ldots f_n).$ Another
important problem is to compute the similarity between two data streams by
computing the inner product of the corresponding frequency vectors. The seminal
work of Alon, Matias, and Szegedy~\cite{AMS}, \textit{a.k.a. Tug-of-war} (or
AMS) sketch gives a randomized sublinear space (and linear time) algorithm for
computing the frequency moments, and the inner product between two frequency
vectors corresponding to the data streams. However, the variance of these
estimates typically tends to be large. In this work, we focus on minimizing the
variance of these estimates. We use the techniques from the classical
Control-Variate method~\cite{Lavenberg} which is primarily known for variance
reduction in Monte-Carlo simulations, and as a result, we are able to obtain
significant variance reduction, at the cost of a little computational overhead.
We present a theoretical analysis of our proposal and complement it with
supporting experiments on synthetic as well as real-world datasets.
- Abstract（参考訳）: 大規模データの空間効率の高いサマリー計算、または \textit{a.k.a. sketches} は、ストリーミングアルゴリズムの中心的な問題である。
このようなスケッチは、いくつかのデータ分析タスクで \textit{post-hoc} クエリに答えるために使われる。
スケッチの計算アルゴリズムは通常、高速で正確で、空間効率が要求される。
ストリーミングアルゴリズムフレームワークの根本的な問題は、データストリームの周波数モーメントを計算することである。
i$ 型の $f_i$ 要素を含む列の周波数モーメントは、$\mathbf{f}_k=\sum_{i=1}^n {f_i}^k,$ ここで $i\in [n]$ である。
これは周波数ベクトル $(f_1, f_2, \ldots f_n) の $\ell_k$ norm とも呼ばれる。
もう一つの重要な問題は、対応する周波数ベクトルの内部積を計算することによって、2つのデータストリーム間の類似性を計算することである。
Alon, Matias, and Szegedy~\cite{AMS}, \textit{a.k.a. Tug-of-war} (または AMS) のスケッチは、周波数モーメントを計算するためのランダム化された部分線型空間(および線形時間)アルゴリズムと、データストリームに対応する2つの周波数ベクトル間の内部積を与える。
しかし、これらの推定値のばらつきは通常大きい傾向にある。
本研究では,これらの推定値のばらつきを最小化することに注力する。
我々はモンテカルロシミュレーションの分散還元で主に知られている古典的制御-変数法~\cite{Lavenberg}の手法を用いており、計算オーバーヘッドの少ないコストで大きな分散還元を得ることができる。
本稿では,提案手法の理論的解析を行い,実世界のデータセットと合成実験を補完する。
関連論文リスト
- Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - On Computing Pairwise Statistics with Local Differential Privacy [55.81991984375959]
例えば$binomn2-1 sum_i ne j f(x_i, x_j)$, $x_i$ は$i$thユーザへの入力を表し、ローカルモデルでは差分プライバシ(DP)である。
この定式化は、Kendallの$tau$ coefficient、Area Under Curve、Giniの平均差、Giniのエントロピーなどの重要なメトリクスをキャプチャする。
論文 参考訳（メタデータ） (2024-06-24T04:06:09Z) - Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。
我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。
ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-06-01T07:33:41Z) - Finding Decision Tree Splits in Streaming and Massively Parallel Models [1.3654846342364308]
観測データのストリームが与えられた場合、目標はデータを2つのセットに分割する最適な$j$を見つけることである。
これらの問題に対してサブ線形空間と少数のパスを使用する高速ストリーミングアルゴリズムを提供する。
これらのアルゴリズムは、超並列計算モデルにも拡張することができる。
論文 参考訳（メタデータ） (2024-03-28T22:26:38Z) - A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。
我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
論文 参考訳（メタデータ） (2024-03-07T18:23:51Z) - Differentially Private Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。
我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - 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) - Streaming Coresets for Symmetric Tensor Factorization [9.181791777532608]
ストリーミング環境でテンソルを効率的に分解する方法を示す。
本稿では,オンラインフィルタリングとカーネル化という2つの新しいアルゴリズム手法を紹介する。
単一トピックモデリング学習におけるアルゴリズムの適用例を示す。
論文 参考訳（メタデータ） (2020-06-01T19:55:34Z) - A Deterministic Streaming Sketch for Ridge Regression [15.256452294422294]
リッジ回帰を推定するための決定論的空間効率アルゴリズムを提案する。
これは、ソリューションエラーが保証された最初の$o(d2)$空間決定論的ストリーミングアルゴリズムである。
合成データセットと実世界のデータセットのランダムなスケッチアルゴリズムと比較して、我々のアルゴリズムは空間と類似時間が少なくて経験的誤差が少ない。
論文 参考訳（メタデータ） (2020-02-05T22:08:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。