論文の概要: Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation

• arxiv url: http://arxiv.org/abs/2510.23039v1
• Date: Mon, 27 Oct 2025 06:05:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 15:28:15.468645
• Title: Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
• Title（参考訳）: 近似近辺近傍のサブリニアスケッチとカーネル密度推定
• Authors: Ved Danait, Srijan Das, Sujoy Bhore,
• Abstract要約: 動的データストリームに対して,ANNとA-KDEの両方に対して,サブ線形空間とクエリ時間保証を実現する新しいスケッチアルゴリズムを開発した。 提案手法は,サブ線形クエリ時間,バッチクエリをサポートし,より一般的なTurnstileモデルに拡張する。 Sliding-WindowモデルにおけるA-KDEに対して、$mathcalOleft(RW cdot frac1sqrt1+epsilon - 1 log2 Nright)$のスケッチを提案する。
• 参考スコア（独自算出の注目度）: 14.369905129159449
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Approximate Nearest Neighbor (ANN) search and Approximate Kernel Density Estimation (A-KDE) are fundamental problems at the core of modern machine learning, with broad applications in data analysis, information systems, and large-scale decision making. In massive and dynamic data streams, a central challenge is to design compact sketches that preserve essential structural properties of the data while enabling efficient queries. In this work, we develop new sketching algorithms that achieve sublinear space and query time guarantees for both ANN and A-KDE for a dynamic stream of data. For ANN in the streaming model, under natural assumptions, we design a sublinear sketch that requires only $\mathcal{O}(n^{1+\rho-\eta})$ memory by storing only a sublinear ($n^{-\eta}$) fraction of the total inputs, where $\rho$ is a parameter of the LSH family, and $0<\eta<1$. Our method supports sublinear query time, batch queries, and extends to the more general Turnstile model. While earlier works have focused on Exact NN, this is the first result on ANN that achieves near-optimal trade-offs between memory size and approximation error. Next, for A-KDE in the Sliding-Window model, we propose a sketch of size $\mathcal{O}\left(RW \cdot \frac{1}{\sqrt{1+\epsilon} - 1} \log^2 N\right)$, where $R$ is the number of sketch rows, $W$ is the LSH range, $N$ is the window size, and $\epsilon$ is the approximation error. This, to the best of our knowledge, is the first theoretical sublinear sketch guarantee for A-KDE in the Sliding-Window model. We complement our theoretical results with experiments on various real-world datasets, which show that the proposed sketches are lightweight and achieve consistently low error in practice.
• Abstract（参考訳）: Approximate Nearest Neighbor (ANN) Search and Approximate Kernel Density Estimation (A-KDE)は、データ分析、情報システム、大規模意思決定など、現代の機械学習のコアにおける基本的な問題である。 大規模でダイナミックなデータストリームでは、効率的なクエリを可能にしながら、データの本質的な構造的特性を保持するコンパクトなスケッチを設計することが中心的な課題である。 本研究では,データストリームの動的ストリームに対して,ANNとA-KDEの両方に対して,サブ線形空間とクエリ時間保証を実現するための新しいスケッチアルゴリズムを開発する。 ストリーミングモデルにおいて、ANNは、自然な仮定の下で、全入力のサブリニア(n^{-\eta}$)分だけを格納することで、$\mathcal{O}(n^{1+\rho-\eta})$メモリのみを必要とするサブリニアスケッチを設計する。 提案手法は,サブ線形クエリ時間,バッチクエリをサポートし,より一般的なTurnstileモデルに拡張する。 以前の研究はExact NNに重点を置いていたが、これはメモリサイズと近似誤差のほぼ最適トレードオフを実現するANNの最初の結果である。 次に、Sliding-WindowモデルにおけるA-KDEに対して、$\mathcal{O}\left(RW \cdot \frac{1}{\sqrt{1+\epsilon} - 1} \log^2N\right)$, where $R$ is the number of sketch rows, $W$ is the LSH range, $N$ is the window size, $\epsilon$ is the approximation error。 我々の知る限り、これはスライディング・ウィンドウモデルにおけるA-KDEに対する最初の理論的サブ線形スケッチ保証である。 提案手法は,提案したスケッチが軽量であり,実際の誤差が一貫して低いことを示す。

関連論文リスト

• Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation [19.363672064425504]
  ランダムな特徴写像を用いた非線形カーネルの近似は、カーネルメソッドを大規模データセットにスケーリングする強力な手法となった。 近似誤差を理論的に保証し、その結果のカーネル関数の推定精度を保証します。
  論文  参考訳（メタデータ） (2025-05-13T00:47:17Z)
• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
  論文  参考訳（メタデータ） (2024-08-21T20:14:54Z)
• Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model [38.66115499136791]
  局所微分プライバシー(LDP)モデルにおける疎線形回帰の問題を再考する。 そこで本研究では,この問題の第一種である革新的NLDPアルゴリズムを提案する。 その結果, 疎線形回帰問題における非私的ケース, 中央DPモデル, 局所DPモデルとの基本的差異が明らかとなった。
  論文  参考訳（メタデータ） (2023-10-11T10:34:52Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation [25.60689712525918]
  本稿では,遷移確率と報酬関数が線形な線形関数近似を用いた強化学習について検討する。 本稿では,新たなアルゴリズムLSVI-UCB$+$を提案し,$H$がエピソード長,$d$が特徴次元,$T$がステップ数である場合に,$widetildeO(HdsqrtT)$ regretboundを実現する。
  論文  参考訳（メタデータ） (2022-06-23T06:04:21Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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