論文の概要: Representing Additive Gaussian Processes by Sparse Matrices
- arxiv url: http://arxiv.org/abs/2305.00324v1
- Date: Sat, 29 Apr 2023 18:53:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-02 15:54:48.571576
- Title: Representing Additive Gaussian Processes by Sparse Matrices
- Title（参考訳）: スパース行列による加法ガウス過程の表現
- Authors: Lu Zou, Haoyuan Chen, Liang Ding
- Abstract要約: Mat'ern Gaussian Processes (GP) は、最も人気のあるスケーラブルな高次元問題の一つである。
バックフィッティングアルゴリズムは、後進平均の計算時間の複雑さを$O(n3)$から$O(nlog n)$ timeに減らすことができる。
後方分散と最大対数類似度を効率的に計算するためにこれらのアルゴリズムを一般化することは、未解決の問題である。
- 参考スコア（独自算出の注目度）: 18.618437338490487
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Among generalized additive models, additive Mat\'ern Gaussian Processes (GPs)
are one of the most popular for scalable high-dimensional problems. Thanks to
their additive structure and stochastic differential equation representation,
back-fitting-based algorithms can reduce the time complexity of computing the
posterior mean from $O(n^3)$ to $O(n\log n)$ time where $n$ is the data size.
However, generalizing these algorithms to efficiently compute the posterior
variance and maximum log-likelihood remains an open problem. In this study, we
demonstrate that for Additive Mat\'ern GPs, not only the posterior mean, but
also the posterior variance, log-likelihood, and gradient of these three
functions can be represented by formulas involving only sparse matrices and
sparse vectors. We show how to use these sparse formulas to generalize
back-fitting-based algorithms to efficiently compute the posterior mean,
posterior variance, log-likelihood, and gradient of these three functions for
additive GPs, all in $O(n \log n)$ time. We apply our algorithms to Bayesian
optimization and propose efficient algorithms for posterior updates,
hyperparameters learning, and computations of the acquisition function and its
gradient in Bayesian optimization. Given the posterior, our algorithms
significantly reduce the time complexity of computing the acquisition function
and its gradient from $O(n^2)$ to $O(\log n)$ for general learning rate, and
even to $O(1)$ for small learning rate.
- Abstract（参考訳）: 一般化された加法モデルの中で、加法的Mat\'ern Gaussian Processes (GPs) はスケーラブルな高次元問題において最もよく用いられる。
彼らの加法構造と確率微分方程式表現のおかげで、バックフィッティングに基づくアルゴリズムは、後進平均の計算の時間的複雑さを$O(n^3)$から$O(n\log n)$ timeに減らすことができる。
しかし、これらのアルゴリズムを一般化して後方分散と最大対数類似度を効率的に計算することは未解決の問題である。
本研究では,加法的Mat\'ern GP に対して,後続平均だけでなく,後続分散,対数類似度,勾配もスパース行列とスパースベクトルのみを含む式で表すことができることを示した。
これらのスパース式を用いてバックフィッティングに基づくアルゴリズムを一般化し,これら3つの関数の後方平均,後方分散,対数類似度,勾配を,すべてo(n \log n)$ timeで効率的に計算する方法を示す。
我々はベイジアン最適化にアルゴリズムを適用し、ベイジアン最適化における後方更新、ハイパーパラメータ学習、および取得関数の計算とその勾配の効率的なアルゴリズムを提案する。
後者を考えると、アルゴリズムは、取得関数とその勾配を一般の学習率で$o(n^2)$から$o(\log n)$に、小さな学習率で$o(1)$まで計算する時間の複雑さを大幅に削減します。
関連論文リスト
- Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process
Regression with Mat\'ern Correlations [23.560067934682294]
マタン相関を用いた1次元ガウス過程回帰のための正確でスケーラブルなアルゴリズムを開発した。
提案アルゴリズムは,計算時間と予測精度の両方において,既存の代替手法よりもはるかに優れている。
論文 参考訳（メタデータ） (2022-03-07T03:30:35Z) - Computing the Newton-step faster than Hessian accumulation [8.147652597876862]
関数の計算グラフを考えると、この境界は$O(mtau3)$に縮めることができ、$tau, m$はグラフのツリー分解の幅と大きさである。
提案アルゴリズムは,LQRに基づく非線形最適制御法を一般化し,ヘシアンが高密度である場合においても,反復複雑度において非自明なゲインを提供する。
論文 参考訳（メタデータ） (2021-08-02T11:22:08Z) - Efficient Matrix-Free Approximations of Second-Order Information, with
Applications to Pruning and Optimization [16.96639526117016]
Inverse-Hessian Vector Products (IHVPs) の行列のない線形時間アプローチについて検討する。
これらのアルゴリズムは、既存の2階法と比較して計算オーバーヘッドが低いネットワークプルーニングと最適化の最先端結果をもたらす。
論文 参考訳（メタデータ） (2021-07-07T17:01:34Z) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳（メタデータ） (2021-03-04T19:01:20Z) - 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) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。