論文の概要: Sub-quadratic Algorithms for Kernel Matrices via Kernel Density
Estimation
- arxiv url: http://arxiv.org/abs/2212.00642v1
- Date: Thu, 1 Dec 2022 16:42:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-02 17:43:34.065056
- Title: Sub-quadratic Algorithms for Kernel Matrices via Kernel Density
Estimation
- Title（参考訳）: カーネル密度推定によるカーネル行列のサブ量子アルゴリズム
- Authors: Ainesh Bakshi, Piotr Indyk, Praneeth Kacham, Sandeep Silwal and Samson
Zhou
- Abstract要約: カーネルグラフ上では$textitweighted edge sample$、カーネルグラフ上では$textitweighted walk$、行列で$textitweighted sample$からKernel Density Estimationへ効率よく還元する。
当社の削減は、それぞれのアプリケーションにおいて中心的な要素であり、それらが独立した関心事である可能性があると信じています。
- 参考スコア（独自算出の注目度）: 24.166833799353476
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Kernel matrices, as well as weighted graphs represented by them, are
ubiquitous objects in machine learning, statistics and other related fields.
The main drawback of using kernel methods (learning and inference using kernel
matrices) is efficiency -- given $n$ input points, most kernel-based algorithms
need to materialize the full $n \times n$ kernel matrix before performing any
subsequent computation, thus incurring $\Omega(n^2)$ runtime. Breaking this
quadratic barrier for various problems has therefore, been a subject of
extensive research efforts.
We break the quadratic barrier and obtain $\textit{subquadratic}$ time
algorithms for several fundamental linear-algebraic and graph processing
primitives, including approximating the top eigenvalue and eigenvector,
spectral sparsification, solving linear systems, local clustering, low-rank
approximation, arboricity estimation and counting weighted triangles. We build
on the recent Kernel Density Estimation framework, which (after preprocessing
in time subquadratic in $n$) can return estimates of row/column sums of the
kernel matrix. In particular, we develop efficient reductions from
$\textit{weighted vertex}$ and $\textit{weighted edge sampling}$ on kernel
graphs, $\textit{simulating random walks}$ on kernel graphs, and
$\textit{importance sampling}$ on matrices to Kernel Density Estimation and
show that we can generate samples from these distributions in
$\textit{sublinear}$ (in the support of the distribution) time. Our reductions
are the central ingredient in each of our applications and we believe they may
be of independent interest. We empirically demonstrate the efficacy of our
algorithms on low-rank approximation (LRA) and spectral sparsification, where
we observe a $\textbf{9x}$ decrease in the number of kernel evaluations over
baselines for LRA and a $\textbf{41x}$ reduction in the graph size for spectral
sparsification.
- Abstract（参考訳）: カーネル行列は、それらで表される重み付きグラフと同様に、機械学習、統計、その他の関連分野においてユビキタスなオブジェクトである。
カーネルメソッド(カーネル行列を用いた学習と推論)を使用する主な欠点は効率である。$n$の入力ポイントが与えられた場合、ほとんどのカーネルベースのアルゴリズムは、その後の計算を実行する前にフル$n \times n$のカーネル行列を実体化する必要がある。
そのため、この二次障壁を突破することは広範な研究の課題となっている。
二次障壁を破って、いくつかの基本線形代数およびグラフ処理プリミティブに対する$\textit{subquadratic}$時間アルゴリズムを得る。例えば、トップ固有値および固有ベクトルの近似、スペクトルスパーシフィケーション、線形系を解くこと、局所クラスタリング、低ランク近似、アルボリシティ推定、重み付き三角形の計数などである。
最近のカーネル密度推定フレームワークに基づいて構築し、(n$の時間的サブクアドラティックな前処理の後)カーネルマトリックスの行/カラム和の見積もりを返すことができる。
特に、$\textit{weighted vertex}$および$\textit{weighted edge sample}$ on kernel graphs, $\textit{simulating random walk}$ on kernel graphs, $\textit{importance sample}$ on matrices to Kernel Density Estimation から$\textit{sublinear}$(分布のサポート)時間でこれらの分布からサンプルを生成することができることを示す。
私たちの還元は、それぞれのアプリケーションにおいて中心的な要素であり、それらが独立した関心事であると信じています。
低ランク近似(LRA)とスペクトルスペーシフィケーション(スペクトルスペーシフィケーション)に対するアルゴリズムの有効性を実証的に実証し、LRAのベースラインよりもカーネル評価が減少する$\textbf{9x}$とスペクトルスペーシフィケーションのためのグラフサイズが減少する$\textbf{41x}$を観察した。
関連論文リスト
- Data-Driven Linear Complexity Low-Rank Approximation of General Kernel
Matrices: A Geometric Approach [0.9453554184019107]
K_ij = kappa(x_i,y_j)$ ここで $kappa(x,y)$ はカーネル関数である。
我々は、点の集合 X$ と $Y$ が大きいカーネル行列に対する低ランク近似を求める。
論文 参考訳（メタデータ） (2022-12-24T07:15:00Z) - Scalable First-Order Bayesian Optimization via Structured Automatic
Differentiation [4.061135251278187]
広い範囲のカーネルが構造化行列を生じさせ、勾配観測のための正確な$mathcalO(n2d)$Matrix-vector multiplyとヘッセン観測のための$mathcalO(n2d2)$を可能にした。
提案手法は,ほぼすべての標準カーネルに適用され,ニューラルネットワーク,放射基底関数ネットワーク,スペクトル混合カーネルなどの複雑なカーネルに自動的に拡張される。
論文 参考訳（メタデータ） (2022-06-16T17:59:48Z) - Leverage Score Sampling for Tensor Product Matrices in Input Sparsity
Time [54.65688986250061]
我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。
我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
論文 参考訳（メタデータ） (2022-02-09T15:26:03Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Two-way kernel matrix puncturing: towards resource-efficient PCA and
spectral clustering [43.50783459690612]
この方法は、データマトリックス$XinmathbbCptimes n$と対応するカーネル(Gram)マトリックス$K$の両方をBernoulliマスクを介してランダムに「切断」する。
我々は、GAN生成した画像データベースを実証的に確認し、データを劇的にパンクし、巨大な計算とストレージのゲインを提供することができることを確認した。
論文 参考訳（メタデータ） (2021-02-24T14:01:58Z) - Faster Kernel Matrix Algebra via Density Estimation [46.253698241653254]
正半定核行列 $K の基本特性を $n$ 点に対応する n$ で計算するための高速アルゴリズムについて研究する。
論文 参考訳（メタデータ） (2021-02-16T18:25:47Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection [58.5350491065936]
グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。
最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。
本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-10-25T18:12:50Z) - Fourier Sparse Leverage Scores and Approximate Kernel Learning [29.104055676527913]
我々はガウス測度とラプラス測度の両方の下でフーリエ関数のレバレッジスコアに新しい明示的な上限を証明した。
私たちの限界は、機械学習における2つの重要な応用によって動機付けられています。
論文 参考訳（メタデータ） (2020-06-12T17:25:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。