論文の概要: Exploiting Hankel-Toeplitz Structures for Fast Computation of Kernel Precision Matrices

• arxiv url: http://arxiv.org/abs/2408.02346v1
• Date: Mon, 5 Aug 2024 09:45:31 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-06 13:56:46.282596
• Title: Exploiting Hankel-Toeplitz Structures for Fast Computation of Kernel Precision Matrices
• Title（参考訳）: カーネル精度行列の高速計算のためのハンケル・トエプリッツの爆発的構造
• Authors: Frida Viset, Anton Kullberg, Frederiek Wesel, Arno Solin,
• Abstract要約: ヒルベルト空間ガウス過程(HGP)アプローチは、GP推論を高速化するための超独立基底関数近似を提供する。 本稿では,この計算複雑性を,余分な近似を伴わずに$mathcalO(NM)$に下げる。 我々の貢献は、いくつかの既存の、広く使われているGP近似の純粋なスピードアップを提供するが、それ以上の近似は行わない。
• 参考スコア（独自算出の注目度）: 14.25435308779899
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Hilbert-space Gaussian Process (HGP) approach offers a hyperparameter-independent basis function approximation for speeding up Gaussian Process (GP) inference by projecting the GP onto M basis functions. These properties result in a favorable data-independent $\mathcal{O}(M^3)$ computational complexity during hyperparameter optimization but require a dominating one-time precomputation of the precision matrix costing $\mathcal{O}(NM^2)$ operations. In this paper, we lower this dominating computational complexity to $\mathcal{O}(NM)$ with no additional approximations. We can do this because we realize that the precision matrix can be split into a sum of Hankel-Toeplitz matrices, each having $\mathcal{O}(M)$ unique entries. Based on this realization we propose computing only these unique entries at $\mathcal{O}(NM)$ costs. Further, we develop two theorems that prescribe sufficient conditions for the complexity reduction to hold generally for a wide range of other approximate GP models, such as the Variational Fourier Feature (VFF) approach. The two theorems do this with no assumptions on the data and no additional approximations of the GP models themselves. Thus, our contribution provides a pure speed-up of several existing, widely used, GP approximations, without further approximations.
• Abstract（参考訳）: ヒルベルト空間ガウス過程(HGP)アプローチは、GPをM基底関数に射影することでガウス過程(GP)推論を高速化するための超パラメータ非依存基底関数近似を提供する。 これらの性質は、ハイパーパラメータ最適化中にデータ独立な$\mathcal{O}(M^3)$計算の複雑さをもたらすが、$\mathcal{O}(NM^2)$演算を犠牲にする精度行列の1時間前計算を必要とする。 本稿では,この計算複雑性を,余分な近似を伴わない$\mathcal{O}(NM)$に下げる。 これは、精度行列がハンケル・トゥープリッツ行列の和に分解できることに気づき、それぞれが$\mathcal{O}(M)$一意なエントリを持つからである。 この実現に基づいて、これらのユニークなエントリのみを$\mathcal{O}(NM)$コストで計算することを提案する。 さらに、複雑性低減のための十分な条件を規定する2つの定理を、変分フーリエ特徴(VFF)アプローチのような、他の近似GPモデルに対して一般に保持する2つの定理を開発した。 2つの定理は、データに対する仮定がなく、GPモデル自体のさらなる近似も不要である。 このように、我々の貢献は、いくつかの既存の、広く使われているGP近似の純粋なスピードアップを提供するが、それ以上の近似は行わない。

関連論文リスト

• Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
  一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。 最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。 我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
  論文  参考訳（メタデータ） (2024-04-19T06:24:22Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Efficient displacement convex optimization with particle gradient descent [57.88860627977882]
  粒子勾配降下は確率測度の関数の最適化に広く用いられている。 本稿では, 有限個の粒子による粒子勾配降下について考察し, その理論的保証を定式化して, 測度に置換凸となる関数を最適化する。
  論文  参考訳（メタデータ） (2023-02-09T16:35:59Z)
• 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)
• Exact Gaussian Processes for Massive Datasets via Non-Stationary Sparsity-Discovering Kernels [0.0]
  本稿では,カーネルがスパース構造を誘導する代わりに,自然に構造されたスパース性を活用することを提案する。 超フレキシブル、コンパクトサポート、非定常カーネルの原理とHPCと制約付き最適化を組み合わせることで、500万のデータポイントを超える正確なGPをスケールできる。
  論文  参考訳（メタデータ） (2022-05-18T16:56:53Z)
• Reducing the Variance of Gaussian Process Hyperparameter Optimization with Preconditioning [54.01682318834995]
  プレコンディショニングは、行列ベクトル乗算を含む反復的な方法にとって非常に効果的なステップである。 プレコンディショニングには、これまで検討されていなかった付加的なメリットがあることを実証する。 基本的に無視可能なコストで、同時に分散を低減することができる。
  論文  参考訳（メタデータ） (2021-07-01T06:43:11Z)
• High-Dimensional Gaussian Process Inference with Derivatives [90.8033626920884]
  低データ状態の$ND$では、Gram行列は$mathcalO(N2D + (N2)3)$に推論のコストを下げる方法で分解できることを示す。 最適化や予測勾配を持つハミルトニアンモンテカルロなど、機械学習に関連する様々なタスクでこの可能性を実証する。
  論文  参考訳（メタデータ） (2021-02-15T13:24:41Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHS [19.252319300590653]
  ブラックボックス関数 $f:mathcalX mapto mathbbR$ は、$f$がよりスムーズで、与えられたカーネル $K$ に関連する RKHS の有界ノルムを持つという仮定の下で最適化される。 本稿では,H の局所多項式 (LP) 推定器を用いて通常の GP 代理モデルを拡張した新しいアルゴリズム (textttLP-GP-UCB) を提案する。
  論文  参考訳（メタデータ） (2020-05-11T01:55:39Z)
• Efficient algorithms for multivariate shape-constrained convex regression problems [9.281671380673306]
  最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。 一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
  論文  参考訳（メタデータ） (2020-02-26T11:18:43Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。