論文の概要: Improving LSH via Tensorized Random Projection

• arxiv url: http://arxiv.org/abs/2402.07189v1
• Date: Sun, 11 Feb 2024 12:54:07 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-13 17:08:08.293579
• Title: Improving LSH via Tensorized Random Projection
• Title（参考訳）: 引張ランダム投影によるLSHの改善
• Authors: Bhisham Dev Verma and Rameshwar Pratap
• Abstract要約: テンソルデータに対するユークリッド距離とコサイン類似性に対する高速かつ空間効率な局所性感度ハッシュ関数を提案する。 我々のアプローチは空間効率が高く、低ランクの$CP$または$TT$テンソルに効率的に適用することができる。
• 参考スコア（独自算出の注目度）: 0.07252027234425332
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Locality sensitive hashing (LSH) is a fundamental algorithmic toolkit used by data scientists for approximate nearest neighbour search problems that have been used extensively in many large scale data processing applications such as near duplicate detection, nearest neighbour search, clustering, etc. In this work, we aim to propose faster and space efficient locality sensitive hash functions for Euclidean distance and cosine similarity for tensor data. Typically, the naive approach for obtaining LSH for tensor data involves first reshaping the tensor into vectors, followed by applying existing LSH methods for vector data $E2LSH$ and $SRP$. However, this approach becomes impractical for higher order tensors because the size of the reshaped vector becomes exponential in the order of the tensor. Consequently, the size of LSH parameters increases exponentially. To address this problem, we suggest two methods for LSH for Euclidean distance and cosine similarity, namely $CP-E2LSH$, $TT-E2LSH$, and $CP-SRP$, $TT-SRP$, respectively, building on $CP$ and tensor train $(TT)$ decompositions techniques. Our approaches are space efficient and can be efficiently applied to low rank $CP$ or $TT$ tensors. We provide a rigorous theoretical analysis of our proposal on their correctness and efficacy.
• Abstract（参考訳）: 局所性感度ハッシュ (Locality sensitive hashing, LSH) は、データ科学者が近接探索問題に近く、近接検出、近接探索、クラスタリングなど多くの大規模データ処理アプリケーションで広く使われている基本的なアルゴリズムツールキットである。 本研究では,ユークリッド距離とテンソルデータのコサイン類似性に対して,より高速で空間効率の良い局所性センシティブなハッシュ関数を提案する。 典型的には、テンソルデータのLSHを得るためには、まずテンソルをベクトルに変換し、続いてベクトルデータに$E2LSH$と$SRP$に既存のLSHメソッドを適用する。 しかし、この手法はテンソルの順序で再形ベクトルのサイズが指数関数となるため、高次テンソルに対しては実用的ではない。 その結果、LSHパラメータのサイズは指数関数的に増加する。 この問題を解決するために、ユークリッド距離とコサイン類似性のためのLSHの2つの方法、すなわち、$CP-E2LSH$、$TT-E2LSH$、$CP-SRP$、$TT-SRP$をそれぞれ提案する。 私たちのアプローチは空間効率が良く、低ランクの$cp$や$tt$テンソルに効率的に適用できます。 我々は,提案の正確性と有効性に関する厳密な理論的分析を行う。

関連論文リスト

• Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization [38.67914746910537]
  我々は,ラゲールセル推定と密度支持推定の類似性を用いて,OTマップに対して$mathcalO(t-1)$の低いバウンダリレートを証明した。 所望の速さをほぼ達成するために,サンプル数に応じて減少するエントロピー正規化スキームを設計する。
  論文  参考訳（メタデータ） (2024-05-23T11:46:03Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。 SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
  論文  参考訳（メタデータ） (2023-10-21T18:48:45Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37: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)
• Robust Methods for High-Dimensional Linear Learning [0.0]
  統計的に頑健で計算効率の良い線形学習法を高次元バッチ設定で提案する。 バニラスパース、グループスパース、低ランク行列回復など、いくつかのアプリケーションでフレームワークをインスタンス化する。 バニラ $s$-sparsity の場合、重いテールと $eta$-corruption の下で $slog (d)/n$ レートに達することができます。
  論文  参考訳（メタデータ） (2022-08-10T17:00:41Z)
• FRAPPE: $\underline{\text{F}}$ast $\underline{\text{Ra}}$nk $\underline{\text{App}}$roximation with $\underline{\text{E}}$xplainable Features for Tensors [5.39764619690516]
  FRAPPEは、CDDを計算することなくテンソルの正準ランクを推定する最初の方法である。 最高のパフォーマンスのベースラインよりも24倍以上高速で、合成データセット上でMAPEが10%改善されている。
  論文  参考訳（メタデータ） (2022-06-19T03:19:59Z)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。 各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。 一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-23T09:03:24Z)
• Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximation [15.319335698574932]
  The first efficient convergence result with primal-dual actor-critic with a convergence of $mathcalOleft ascent(Nright)Nright)$ under Polyian sample。 Open GymAI連続制御タスクの結果。
  論文  参考訳（メタデータ） (2022-02-28T15:16:23Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Beyond Lazy Training for Over-parameterized Tensor Decomposition [69.4699995828506]
  過度なパラメータ化対象の勾配勾配は遅延学習体制を超え、データ中の特定の低ランク構造を利用する可能性があることを示す。 以上の結果から,過パラメータ化対象の勾配勾配は遅延学習体制を超え,データ中の特定の低ランク構造を利用する可能性が示唆された。
  論文  参考訳（メタデータ） (2020-10-22T00:32:12Z)

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

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