論文の概要: Fourier Sparse Leverage Scores and Approximate Kernel Learning
- arxiv url: http://arxiv.org/abs/2006.07340v3
- Date: Thu, 8 Jul 2021 01:55:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-22 04:52:59.492548
- Title: Fourier Sparse Leverage Scores and Approximate Kernel Learning
- Title（参考訳）: Fourier Sparse Leverage Scoresと近似カーネル学習
- Authors: Tam\'as Erd\'elyi and Cameron Musco and Christopher Musco
- Abstract要約: 我々はガウス測度とラプラス測度の両方の下でフーリエ関数のレバレッジスコアに新しい明示的な上限を証明した。
私たちの限界は、機械学習における2つの重要な応用によって動機付けられています。
- 参考スコア（独自算出の注目度）: 29.104055676527913
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove new explicit upper bounds on the leverage scores of Fourier sparse
functions under both the Gaussian and Laplace measures. In particular, we study
$s$-sparse functions of the form $f(x) = \sum_{j=1}^s a_j e^{i \lambda_j x}$
for coefficients $a_j \in \mathbb{C}$ and frequencies $\lambda_j \in
\mathbb{R}$. Bounding Fourier sparse leverage scores under various measures is
of pure mathematical interest in approximation theory, and our work extends
existing results for the uniform measure [Erd17,CP19a]. Practically, our bounds
are motivated by two important applications in machine learning:
1. Kernel Approximation. They yield a new random Fourier features algorithm
for approximating Gaussian and Cauchy (rational quadratic) kernel matrices. For
low-dimensional data, our method uses a near optimal number of features, and
its runtime is polynomial in the $statistical\ dimension$ of the approximated
kernel matrix. It is the first "oblivious sketching method" with this property
for any kernel besides the polynomial kernel, resolving an open question of
[AKM+17,AKK+20b].
2. Active Learning. They can be used as non-uniform sampling distributions
for robust active learning when data follows a Gaussian or Laplace
distribution. Using the framework of [AKM+19], we provide essentially optimal
results for bandlimited and multiband interpolation, and Gaussian process
regression. These results generalize existing work that only applies to
uniformly distributed data.
- Abstract（参考訳）: 我々はガウス測度とラプラス測度の両方の下でフーリエスパース関数のレバレッジスコアに新しい明示的な上限を証明した。
特に、係数 $a_j \in \mathbb{C}$ および周波数 $\lambda_j \in \mathbb{R}$ に対して、$f(x) = \sum_{j=1}^s a_j e^{i \lambda_j x}$ という形の $s$-sparse 関数を研究する。
様々な測度の下でフーリエスパースをうまく活用することは近似理論に純粋に数学的な関心を持ち、我々の研究は、一様測度 [Erd17,CP19a] に対する既存の結果を拡張している。
実際、我々の限界は機械学習における2つの重要な応用によって動機付けられている: 1. Kernel Approximation。
それらは、ガウスおよびコーシー(有理二次)核行列を近似する新しいランダムフーリエ特徴アルゴリズムを与える。
低次元データに対して、我々の手法は、ほぼ最適な特徴数を使い、その実行時間は、近似されたカーネル行列の$statistical\ dimension$の多項式である。
AKM+17,AKK+20b]のオープンな問題を解決するため、多項式カーネル以外の任意のカーネルに対してこの特性を持つ最初の"oblivious sketching method"である。
2. アクティブラーニング。
データはガウス分布やラプラス分布に従えば、一様でないサンプリング分布として使用することができる。
AKM+19] の枠組みを用いて、帯域制限とマルチバンド補間、ガウス過程の回帰に対して本質的に最適な結果を与える。
これらの結果は、一様分散データにのみ適用される既存の作業を一般化する。
関連論文リスト
- Universality of kernel random matrices and kernel regression in the quadratic regime [18.51014786894174]
本研究では、カーネルカーネルの回帰の研究を二次構造にまで拡張する。
我々は、元のカーネルランダム行列と二次カーネルランダム行列の差分に限定した作用素ノルム近似を確立する。
我々は、$n/d2$が非ゼロ定数に収束する二次状態におけるKRRの正確なトレーニングと一般化誤差を特徴づける。
論文 参考訳（メタデータ） (2024-08-02T07:29:49Z) - Dimensionality Reduction for General KDE Mode Finding [12.779486428760373]
高次元確率分布のモードを$D$で見つけることは、統計学とデータ解析の基本的な問題である。
我々は、$mathitP = MathitNP$ でない限り、カーネル密度推定のモードを見つけるための時間アルゴリズムがないことを示す。
論文 参考訳（メタデータ） (2023-05-30T05:39:59Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process
Regression with Mat\'ern Correlations [23.560067934682294]
マタン相関を用いた1次元ガウス過程回帰のための正確でスケーラブルなアルゴリズムを開発した。
提案アルゴリズムは,計算時間と予測精度の両方において,既存の代替手法よりもはるかに優れている。
論文 参考訳（メタデータ） (2022-03-07T03:30:35Z) - Uniform Approximations for Randomized Hadamard Transforms with
Applications [8.985261743452986]
RHT(Randomized Hadamard Transforms)は、高密度な非構造的ランダム行列の計算効率の代替として登場した。
我々は、カーネル近似と距離推定という高次元状態における2つの応用の保証を改善するために、我々の不等式を利用する。
論文 参考訳（メタデータ） (2022-03-03T09:56:39Z) - Leverage Score Sampling for Tensor Product Matrices in Input Sparsity
Time [54.65688986250061]
我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。
我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
論文 参考訳（メタデータ） (2022-02-09T15:26:03Z) - 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) - Quantization Algorithms for Random Fourier Features [25.356048456005023]
ランダムフーリエ特徴の方法(rff)も、ガウス核の近似として普及している。
RFFは、ランダムな投影から投影されたデータに特定の非線形変換を適用する。
本稿では,RFFの量子化アルゴリズムの開発に焦点を当てる。
論文 参考訳（メタデータ） (2021-02-25T18:51:39Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - 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) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。