論文の概要: Kernel Multigrid: Accelerate Back-fitting via Sparse Gaussian Process Regression
- arxiv url: http://arxiv.org/abs/2403.13300v1
- Date: Wed, 20 Mar 2024 04:57:27 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-21 17:58:10.500795
- Title: Kernel Multigrid: Accelerate Back-fitting via Sparse Gaussian Process Regression
- Title（参考訳）: Kernel Multigrid: スパースガウスプロセス回帰によるバックフィッティングの高速化
- Authors: Lu Zou, Liang Ding,
- Abstract要約: 本稿では,加法GPをトレーニングするためのKernel Multigrid (KMG) アルゴリズムを提案する。
KMG は時間と空間の複雑さを保ちながら、必要な反復を $mathcalO(log n)$ に減らす。
数値的には、KMGは5回の反復で高次元目標の正確な近似を生成することができる。
- 参考スコア（独自算出の注目度）: 12.627210483313402
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Additive Gaussian Processes (GPs) are popular approaches for nonparametric feature selection. The common training method for these models is Bayesian Back-fitting. However, the convergence rate of Back-fitting in training additive GPs is still an open problem. By utilizing a technique called Kernel Packets (KP), we prove that the convergence rate of Back-fitting is no faster than $(1-\mathcal{O}(\frac{1}{n}))^t$, where $n$ and $t$ denote the data size and the iteration number, respectively. Consequently, Back-fitting requires a minimum of $\mathcal{O}(n\log n)$ iterations to achieve convergence. Based on KPs, we further propose an algorithm called Kernel Multigrid (KMG). This algorithm enhances Back-fitting by incorporating a sparse Gaussian Process Regression (GPR) to process the residuals subsequent to each Back-fitting iteration. It is applicable to additive GPs with both structured and scattered data. Theoretically, we prove that KMG reduces the required iterations to $\mathcal{O}(\log n)$ while preserving the time and space complexities at $\mathcal{O}(n\log n)$ and $\mathcal{O}(n)$ per iteration, respectively. Numerically, by employing a sparse GPR with merely 10 inducing points, KMG can produce accurate approximations of high-dimensional targets within 5 iterations.
- Abstract（参考訳）: 加法ガウス過程(GP)は非パラメトリックな特徴選択のための一般的なアプローチである。
これらのモデルの一般的な訓練方法はベイズバックフィッティングである。
しかし、加法GPのトレーニングにおけるバックフィッティングの収束率は依然として未解決の問題である。
Kernel Packets (KP) と呼ばれる手法を利用することで、バックフィッティングの収束速度が 1-\mathcal{O}(\frac{1}{n}))^t$ よりも高速であることを証明する。
したがって、バックフィッティングは収束を達成するために$\mathcal{O}(n\log n)$イテレーションを最小限にする必要がある。
さらに,KPをベースとしたKernel Multigrid (KMG)アルゴリズムを提案する。
このアルゴリズムは、粗いガウスプロセス回帰(GPR)を組み込むことでバックフィッティングを強化し、バックフィッティングのイテレーションごとに残余を処理する。
これは、構造化データと散乱データの両方を持つ加法的GPに適用できる。
理論的には、KMG は所要の反復を $\mathcal{O}(\log n)$ に減らし、それぞれ $\mathcal{O}(n\log n)$ と $\mathcal{O}(n)$ で時間と空間の複雑さを保存することを証明している。
数値的には、わずか10個の誘導点を持つスパースGPRを用いることで、KMGは5回の反復で高次元目標の正確な近似を生成することができる。
関連論文リスト
- Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Representing Additive Gaussian Processes by Sparse Matrices [18.618437338490487]
Mat'ern Gaussian Processes (GP) は、最も人気のあるスケーラブルな高次元問題の一つである。
バックフィッティングアルゴリズムは、後進平均の計算時間の複雑さを$O(n3)$から$O(nlog n)$ timeに減らすことができる。
後方分散と最大対数類似度を効率的に計算するためにこれらのアルゴリズムを一般化することは、未解決の問題である。
論文 参考訳（メタデータ） (2023-04-29T18:53:42Z) - Sparse Kernel Gaussian Processes through Iterative Charted Refinement
(ICR) [0.0]
本稿では,ガウス過程をモデル化するためのICR(Iterative Charted Refinement)という新しい生成手法を提案する。
ICRは、様々な解像度でモデル化された場所のビューとユーザが提供する座標チャートを組み合わせることで、長距離および短距離の相関を表現している。
ICRは、CPUとGPUの1桁の計算速度で既存の手法より優れています。
論文 参考訳（メタデータ） (2022-06-21T18:00:01Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文 参考訳（メタデータ） (2022-04-20T07:14:21Z) - Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process
Regression with Mat\'ern Correlations [23.560067934682294]
マタン相関を用いた1次元ガウス過程回帰のための正確でスケーラブルなアルゴリズムを開発した。
提案アルゴリズムは,計算時間と予測精度の両方において,既存の代替手法よりもはるかに優れている。
論文 参考訳（メタデータ） (2022-03-07T03:30:35Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - Convergence of Sparse Variational Inference in Gaussian Processes
Regression [29.636483122130027]
計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
論文 参考訳（メタデータ） (2020-08-01T19:23:34Z) - Differentially Quantized Gradient Methods [53.3186247068836]
微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。
あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
論文 参考訳（メタデータ） (2020-02-06T20:40:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。