Fugu-MT 論文翻訳(概要): Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations

論文の概要: 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$ を選択することができる。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Combinatorial optimization of the coefficient of determination [0.0]
決定係数が最も高い平面上の$n$点の$k$-部分集合を選択するための効率的なアルゴリズムを開発する。誤差のない$n=30$までの試行で,提案手法の最適性を実験的に実証した。
論文参考訳（メタデータ） (2024-10-12T00:53:25Z)
$\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)
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)
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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。