論文の概要: Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation
- arxiv url: http://arxiv.org/abs/2610.05174v1
- Date: Sun, 04 Oct 2026 12:31:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-10 22:54:23.271312
- Title: Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation
- Title（参考訳）: p-指数カーネルの局所感性ハッシュと密度推定への応用
- Abstract要約: カーネル $k(x,y)$ が LSHable であるとは、局所性に敏感なハッシュスキーム $H$ が存在して、$k(x,y)=Pr_hsim H[h(x)=h(y)]$ for all $x,y$ が成り立つことである。
この研究で、$p$-exponential kernel $k(x,y)=exp(-lVert x-y rVert_p)$ は、すべての $1pleq2 の有界領域で LSH 可能であることを示す。
- 参考スコア（独自算出の注目度）: 10.27725229355938
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A kernel $k(x,y)$ is LSHable if there exists a locality sensitive hashing scheme $H$ such that $k(x,y)=\Pr_{h\sim H}[h(x)=h(y)]$ for all $x,y$. This notion plays a key role in efficient kernel methods in high dimensions. In this work, we show that the $p$-exponential kernel $k(x,y)=\exp(-\lVert x-y \rVert_p)$ is LSHable in bounded regions for all $1<p\leq2$. Previously, this was known only for $p=1$. Our new "mosaic LSH" scheme is based on a Poisson hyperplane process with hyperplanes sampled as $\ell_1$-biased $p$-stable vectors, for which we develop efficient sampling procedures. As applications, our results yield new and efficient density estimation methods based on LSHability for those $p$-exponential kernels.
- Abstract（参考訳）: カーネル $k(x,y)$ が LSHable であるとは、局所性に敏感なハッシュスキーム $H$ が存在して、$k(x,y)=\Pr_{h\sim H}[h
(x)=h
(y)]$ for all $x,y$.
この概念は、高次元における効率的なカーネルメソッドにおいて重要な役割を果たす。
この研究で、$p$-exponential kernel $k(x,y)=\exp(-\lVert x-y \rVert_p)$は、すべての$<p\leq2$に対して有界領域でLSH許容であることを示す。
以前は、これは$p=1$でしか知られていなかった。
我々の新しい「モザイク型LSH」スキームは、超平面が$\ell_1$-biased $p$-stableベクターとしてサンプリングされたポアソン超平面プロセスに基づいており、効率的なサンプリング手順を開発する。
応用として、これらの$p$-exponentialカーネルのLSH性に基づく新しい,効率的な密度推定法が得られた。
関連論文リスト
- Computational Hardness of Private Coreset [84.99100741615423]
与えられた点の入力集合に対して、コアセットは任意の候補解に対する$k$-meansの目的が乗法的な$(, 1/n(1))$ factor(およびいくつかの加法因子)まで保存されるような点の別の集合である。
no-time $(, 1/n(1))$-DPアルゴリズムは、ある定数$> 0$(およびいくつかの定数加法因子)に対して$ell_infty$-metricの$k$-meansのコアセットを計算することができることを示す。
$k$-means in the
論文 参考訳（メタデータ） (2026-02-19T15:58:49Z) - Sandwich test for Quantum Phase Estimation [0.0]
量子位相推定(QPE)は多くの実用的な応用を通じて科学的革命の可能性を秘めている。
多くのQPEアルゴリズムは、大きな整数$k$に対して$langle psi|Uk|psirangle$を推定するためにHadamardテストを使用する。
本稿では,このボトルネックに対処する新しいアルゴリズムであるSANDWICHを提案する。
論文 参考訳（メタデータ） (2025-07-31T16:45:07Z) - Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
本稿では,MNL関数近似を用いたMDPの新たなクラスについて検討し,状態空間上の確率分布の正当性を保証する。
その大きな利点にもかかわらず、非線形関数を組み込むことは、統計的および計算効率の両方において重大な課題を提起する。
我々は,$widetildemathcalO(dH2sqrtK + kappa-1d2H2)$を後悔するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-27T11:31:54Z) - The $L^\infty$ Learnability of Reproducing Kernel Hilbert Spaces [3.2931415075553576]
カーネル空間の学習可能性(RKHS)を$Linfty$ノルムで解析する。
球面上のドット積核に対しては、ヒルベルトサンプルを用いて$Linfty$学習が達成できる条件を特定する。
論文 参考訳（メタデータ） (2023-06-05T12:29:13Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds [0.8594140167290096]
有限体上のランダムに選択された線型写像が $ell_infty$ の意味でよいハッシュ関数を与えることを示す。
負荷分散文献[RS98]からの既知のバウンダリにより、この結果は厳密であり、線形関数とトラリーランダム関数がエントロピー損失の定数因子であることを示す。
論文 参考訳（メタデータ） (2022-04-04T17:21:10Z) - On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
カーネル群に基づく暗黙の空間性誘導機構について述べる。
アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
論文 参考訳（メタデータ） (2021-10-12T09:36:41Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。