論文の概要: Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations
- arxiv url: http://arxiv.org/abs/2212.11408v1
- Date: Wed, 21 Dec 2022 23:23:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-23 15:20:05.720344
- Title: Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations
- Title(参考訳): Pairwise Summationsにおける適応型および動的マルチリゾリューションハッシュ
- Authors: Lianke Qin, Aravind Reddy, Zhao Song, Zhaozhuo Xu, Danyang Zhuo
- Abstract要約: 本稿では,適応的で動的なマルチレゾリューションハッシュデータ構造であるAdam-Hashを提案する。
提案したAdam-Hash は適応型 PSE クエリにも頑健であり,従来のクエリの出力に応じて mathbbRd$ のクエリ $q_j を選択することができる。
- 参考スコア(独自算出の注目度): 19.602149096819776
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we propose Adam-Hash: an adaptive and dynamic multi-resolution
hashing data-structure for fast pairwise summation estimation. Given a data-set
$X \subset \mathbb{R}^d$, a binary function $f:\mathbb{R}^d\times
\mathbb{R}^d\to \mathbb{R}$, and a point $y \in \mathbb{R}^d$, the Pairwise
Summation Estimate $\mathrm{PSE}_X(y) := \frac{1}{|X|} \sum_{x \in X} f(x,y)$.
For any given data-set $X$, we need to design a data-structure such that given
any query point $y \in \mathbb{R}^d$, the data-structure approximately
estimates $\mathrm{PSE}_X(y)$ in time that is sub-linear in $|X|$. Prior works
on this problem have focused exclusively on the case where the data-set is
static, and the queries are independent. In this paper, we design a
hashing-based PSE data-structure which works for the more practical
\textit{dynamic} setting in which insertions, deletions, and replacements of
points are allowed. Moreover, our proposed Adam-Hash is also robust to adaptive
PSE queries, where an adversary can choose query $q_j \in \mathbb{R}^d$
depending on the output from previous queries $q_1, q_2, \dots, q_{j-1}$.
- Abstract(参考訳): 本稿では,高速ペアワイズ和量推定のための適応的かつ動的マルチレゾリューションハッシュデータ構造であるadam-hashを提案する。
データ集合 $X \subset \mathbb{R}^d$, a binary function $f:\mathbb{R}^d\times \mathbb{R}^d\to \mathbb{R}$, and a point $y \in \mathbb{R}^d$, the Pairwise Summation Estimate $\mathrm{PSE}_X(y) := \frac{1}{|X|} \sum_{x \in X} f(x,y)$ が与えられる。
任意のデータセット $x$ に対して、クエリポイント $y \in \mathbb{r}^d$ が与えられた場合、データ構造は約$\mathrm{pse}_x(y)$ を推定し、$|x|$ のサブ線形であるようなデータ構造を設計する必要がある。
この問題に対する以前の取り組みは、データセットが静的でクエリが独立である場合にのみ焦点を当ててきた。
本稿では,ポイントの挿入,削除,置換を許容するより実用的な \textit{dynamic} 設定に適したハッシュベースのpseデータ構造を設計する。
さらに,提案したAdam-Hash は適応型 PSE クエリにも頑健であり,従来のクエリ $q_1, q_2, \dots, q_{j-1}$ の出力に依存するクエリ $q_j \in \mathbb{R}^d$ を選択することができる。
関連論文リスト
- $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳(メタデータ) (2023-07-11T08:51:53Z) - Dynamic Ranking and Translation Synchronization [3.946250592943285]
本研究では, エン翻訳同期問題の動的設定への拡張について検討する。
そこで我々は,2つの推定器を提案し,その1つはスムーズネスの最小二乗法に基づくものであり,もう1つは適切な滑らかさ演算子の低周波固有空間への射影に基づくものである。
論文 参考訳(メタデータ) (2022-07-04T14:45:12Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - Computational Complexity of Normalizing Constants for the Product of
Determinantal Point Processes [12.640283469603357]
正規化定数の計算における計算複雑性について検討する。
例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
論文 参考訳(メタデータ) (2021-11-28T14:08:25Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳(メタデータ) (2021-10-05T09:33:49Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳(メタデータ) (2021-09-06T14:21:43Z) - Semi-supervised Active Regression [21.51757844385258]
本稿では,学習課題における偏りのある部分ラベル付きデータの利用について検討する。
学習者は、追加のラベルクエリをほとんど行わずに、mathbbRd | X min_beta in mathbbRd | X beta - Y |2 end2 方程式でデータセット $X にアクセスすることができる。
論文 参考訳(メタデータ) (2021-06-12T03:28:43Z) - 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) - Sharp threshold for alignment of graph databases with Gaussian weights [1.6752182911522522]
重み付きグラフ(行列)データベースアライメントにおける再構成の基本的限界について検討する。
我々は、$pi*$の正確なリカバリには鋭いしきい値が存在することを証明している。
論文 参考訳(メタデータ) (2020-10-30T14:42:17Z) - An Algorithm for Learning Smaller Representations of Models With Scarce
Data [0.0]
データセットが小さすぎるか、完全に代表的でない状況下で、二項分類問題を解くための欲求的アルゴリズムを提案する。
それは、ゆるやかな精度の制約、反復的なハイパーパラメータプルーニング手順、新しいデータを生成するために使われる関数といった訓練されたモデルに依存している。
論文 参考訳(メタデータ) (2020-10-15T19:17:51Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳(メタデータ) (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。