論文の概要: On The Relative Error of Random Fourier Features for Preserving Kernel
Distance
- arxiv url: http://arxiv.org/abs/2210.00244v2
- Date: Thu, 13 Apr 2023 13:57:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-14 20:33:34.744983
- Title: On The Relative Error of Random Fourier Features for Preserving Kernel
Distance
- Title（参考訳）: カーネル距離保存のためのランダムフーリエ特徴の相対誤差について
- Authors: Kuan Cheng, Shaofeng H.-C. Jiang, Luojian Wei, Zhide Wei
- Abstract要約: 有名なラプラシアカーネルを含むかなりの範囲のカーネルに対して、RFFは低次元を用いて小さな相対誤差でカーネル距離を近似することはできないことを示す。
一般シフト不変カーネルに対するデータ公開次元還元に向けての第一歩を踏み出し、ラプラシアンカーネルに対して同様の$mathrmpoly(epsilon-1 log n)$ dimension を得る。
- 参考スコア（独自算出の注目度）: 7.383448514243228
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The method of random Fourier features (RFF), proposed in a seminal paper by
Rahimi and Recht (NIPS'07), is a powerful technique to find approximate
low-dimensional representations of points in (high-dimensional) kernel space,
for shift-invariant kernels. While RFF has been analyzed under various notions
of error guarantee, the ability to preserve the kernel distance with
\emph{relative} error is less understood. We show that for a significant range
of kernels, including the well-known Laplacian kernels, RFF cannot approximate
the kernel distance with small relative error using low dimensions. We
complement this by showing as long as the shift-invariant kernel is analytic,
RFF with $\mathrm{poly}(\epsilon^{-1} \log n)$ dimensions achieves
$\epsilon$-relative error for pairwise kernel distance of $n$ points, and the
dimension bound is improved to $\mathrm{poly}(\epsilon^{-1}\log k)$ for the
specific application of kernel $k$-means. Finally, going beyond RFF, we make
the first step towards data-oblivious dimension-reduction for general
shift-invariant kernels, and we obtain a similar $\mathrm{poly}(\epsilon^{-1}
\log n)$ dimension bound for Laplacian kernels. We also validate the
dimension-error tradeoff of our methods on simulated datasets, and they
demonstrate superior performance compared with other popular methods including
random-projection and Nystr\"{o}m methods.
- Abstract（参考訳）: Rahimi and Recht (NIPS'07) によるセミナー論文で提案されたランダムフーリエ特徴法(RFF)は、シフト不変カーネルに対して、(高次元)カーネル空間における点の近似低次元表現を求める強力な手法である。
RFFは様々なエラー保証の概念で分析されているが、\emph{relative} エラーでカーネル距離を保存する能力は理解されていない。
有名なラプラシアカーネルを含むかなりの範囲のカーネルに対して、RFFは低次元を用いて小さな相対誤差でカーネル距離を近似することはできないことを示す。
我々は、シフト不変なカーネルが解析的である限り、rff と $\mathrm{poly}(\epsilon^{-1} \log n)$次元が 1 対のカーネル距離が $n$ である場合の $\epsilon$-relative error を達成し、その次元境界が $\mathrm{poly}(\epsilon^{-1}\log k)$ に改善されることを示した。
最後に、rff を越え、一般シフト不変核のデータ-oblivious dimension-reduction への第一歩を踏み出し、ラプラシアン核に対して同様の $\mathrm{poly}(\epsilon^{-1} \log n)$ 次元を得る。
また,シミュレーションデータセット上での手法の次元誤差トレードオフを検証し,ランダム投影法やnystr\"{o}m法など他の一般的な手法と比較して優れた性能を示す。
関連論文リスト
- Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - The phase diagram of kernel interpolation in large dimensions [8.707305374058794]
大きな次元におけるカーネルの一般化能力は、最近のカーネル回帰のルネサンスにおいて、最も興味深い問題の1つかもしれない。
各種ソース条件$sgeq 0$において,大次元カーネルの偏差と偏差の正確な順序を完全に特徴づけた。
我々は、カーネルが極小最適、準最適、矛盾する$(s,gamma)$-planeの領域を決定した。
論文 参考訳（メタデータ） (2024-04-19T03:04:06Z) - Fast Kernel Summation in High Dimensions via Slicing and Fourier Transforms [0.0]
カーネルベースの手法は機械学習で多用されている。
彼らは考慮されたデータポイントの$O(N2)$複雑さに悩まされる。
近似法を提案し、この複雑さを$O(N)$に削減する。
論文 参考訳（メタデータ） (2024-01-16T10:31:27Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Uniform Approximations for Randomized Hadamard Transforms with
Applications [8.985261743452986]
RHT(Randomized Hadamard Transforms)は、高密度な非構造的ランダム行列の計算効率の代替として登場した。
我々は、カーネル近似と距離推定という高次元状態における2つの応用の保証を改善するために、我々の不等式を利用する。
論文 参考訳（メタデータ） (2022-03-03T09:56:39Z) - 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) - Taming Nonconvexity in Kernel Feature Selection---Favorable Properties
of the Laplace Kernel [77.73399781313893]
カーネルベースの特徴選択の客観的機能を確立することが課題である。
非言語最適化に利用可能な勾配に基づくアルゴリズムは、局所ミニマへの収束を保証できるだけである。
論文 参考訳（メタデータ） (2021-06-17T11:05:48Z) - Towards Unbiased Random Features with Lower Variance For Stationary
Indefinite Kernels [26.57122949130266]
本アルゴリズムは,既存のカーネル近似法と比較して,より低い分散と近似誤差を達成する。
もともと選択されたカーネルの近似性が向上し、分類精度と回帰能力が向上する。
論文 参考訳（メタデータ） (2021-04-13T13:56:50Z) - Fourier Sparse Leverage Scores and Approximate Kernel Learning [29.104055676527913]
我々はガウス測度とラプラス測度の両方の下でフーリエ関数のレバレッジスコアに新しい明示的な上限を証明した。
私たちの限界は、機械学習における2つの重要な応用によって動機付けられています。
論文 参考訳（メタデータ） (2020-06-12T17:25:39Z) - 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) - Improved guarantees and a multiple-descent curve for Column Subset
Selection and the Nystr\"om method [76.73096213472897]
我々は,データ行列のスペクトル特性を利用して近似保証を改良する手法を開発した。
我々のアプローチは、特異値減衰の既知の速度を持つデータセットのバウンダリが大幅に向上する。
RBFパラメータを変更すれば,改良された境界線と多重発振曲線の両方を実データセット上で観測できることが示される。
論文 参考訳（メタデータ） (2020-02-21T00:43:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。