論文の概要: Random Fourier Features in Near-Linear Time
- arxiv url: http://arxiv.org/abs/2610.14751v1
- Date: Sat, 10 Oct 2026 09:16:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-20 11:52:58.666546
- Title: Random Fourier Features in Near-Linear Time
- Title（参考訳）: 近距離時間におけるランダムフーリエ特性
- Abstract要約: ほぼ直線時間で計算できるランダムな特徴写像は, ほぼ亜ガウス濃度が得られることを示す。
我々は、Le, Sarls, SmolaのFastfood特徴写像を、より厳密に分析することで、それを得る。
- 参考スコア（独自算出の注目度）: 23.626665465710172
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Random Fourier features approximate a shift-invariant kernel in $\mathbb{R}^d$, such as the Gaussian kernel $\exp(-\tfrac12\|x-y\|_2^2)$, using independent samples from its spectral measure to construct an unbiased estimator for the kernel value with subgaussian concentration. However, generating $m$ such features requires $O(md)$ time. A long line of work on structured random features has accelerated this computation for the Gaussian kernel and other radial kernels, albeit with weaker concentration guarantees. We close this gap by showing a random feature map that can be computed in near-linear time $O((d+m)\log d)$ and yields near-subgaussian concentration. We obtain it through a new and tighter analysis of the Fastfood feature map of Le, Sarlós and Smola (ICML 2013), using Brascamp-Lieb inequalities and the Schoenberg representation of radial kernels.
- Abstract（参考訳）: ランダムフーリエは、ガウス核 $\exp(-\tfrac12\|x-y\|_2^2)$ のような $\mathbb{R}^d$ のシフト不変核を、そのスペクトル測度から独立したサンプルを用いて、亜ガウス濃度のカーネル値の非バイアス推定器を構築する。
しかし、$m$のような機能を生成するには、$O(md)$時間が必要です。
構造化ランダムな特徴に関する長い研究により、ガウスカーネルや他のラジアルカーネルの計算が加速した。
我々はこのギャップを、ほぼ直線時間$O((d+m)\log d)$で計算できるランダムな特徴写像を示し、準ガウス濃度を得ることによって閉じる。
我々は、Brascamp-Lieb不等式とSchoenberg表現を用いたLe, Sarlós and Smola (ICML 2013) のFastfood特徴写像のより厳密な解析によりこれを得られる。
関連論文リスト
- Graph Random Features for Scalable Gaussian Processes [52.89901965157282]
離散入力空間上のスケーラブルなガウス過程へのグラフランダム特徴(GRF)の適用について検討する。
我々は、(穏やかな仮定の下で) GRF に対するベイズ的推論が、正確なカーネルに対して$O(N3)$のノード数に対して$O(N3/2)$の時間複雑性を楽しむことを証明した。
論文 参考訳（メタデータ） (2025-09-03T20:13:23Z) - Concentration of the Langevin Algorithm's Stationary Distribution [29.244631254978597]
任意の非自明な段数 $eta > 0$ に対して、$pi_eta$ はポテンシャルが凸であるときに部分指数であることを示す。
また、これらの濃度境界がランゲヴィンアルゴリズムの軌道に沿って全ての反復に広がることを示す。
論文 参考訳（メタデータ） (2022-12-24T01:39:02Z) - A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points [50.90125395570797]
このことは対数的因子の中でのciteSaundersonCPW12 の予想をほぼ成立させる。
後者の予想は、機械学習とある種の統計上の問題に対する2乗下界との結びつきから、過去10年間で大きな注目を集めている。
論文 参考訳（メタデータ） (2022-12-21T17:48:01Z) - Strong uniform convergence of Laplacians of random geometric and
directed kNN graphs on compact manifolds [0.0]
この作用素の微分ラプラス・ベルトラミ作用素へのほぼ確実に一様収束は、$n$が無限大の傾向にあるときに研究する。
この研究は、過去15年間の既知の結果を拡張した。
論文 参考訳（メタデータ） (2022-12-20T14:31:06Z) - 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) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - 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) - Spectral density estimation with the Gaussian Integral Transform [91.3755431537592]
スペクトル密度作用素 $hatrho(omega)=delta(omega-hatH)$ は線形応答論において中心的な役割を果たす。
スペクトル密度を近似する近似量子アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2020-04-10T03:14:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。