論文の概要: The Price of Linear Time: Error Analysis of Structured Kernel Interpolation

• arxiv url: http://arxiv.org/abs/2502.00298v2
• Date: Tue, 04 Feb 2025 04:07:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-05 15:04:12.219676
• Title: The Price of Linear Time: Error Analysis of Structured Kernel Interpolation
• Title（参考訳）: 線形時間の価格:構造化カーネル補間における誤差解析
• Authors: Alexander Moreno, Justin Xiao, Jonathan Mei,
• Abstract要約: 構造化カーネル補間 (Structured Kernel Interpolation, SKI) はガウス過程 (GP) のスケールを支援する。 本稿では,SKIグラム行列の誤差境界を証明し,過度パラメータに対する誤差の影響について検討する。 本研究では,SKIグラムのスペクトル標準誤差と計算複雑性のトレードオフを規定する2つの次元規則を同定する。
• 参考スコア（独自算出の注目度）: 46.342033870324705
• License:
• Abstract: Structured Kernel Interpolation (SKI) (Wilson et al. 2015) helps scale Gaussian Processes (GPs) by approximating the kernel matrix via interpolation at inducing points, achieving linear computational complexity. However, it lacks rigorous theoretical error analysis. This paper bridges the gap: we prove error bounds for the SKI Gram matrix and examine the error's effect on hyperparameter estimation and posterior inference. We further provide a practical guide to selecting the number of inducing points under convolutional cubic interpolation: they should grow as $n^{d/3}$ for error control. Crucially, we identify two dimensionality regimes governing the trade-off between SKI Gram matrix spectral norm error and computational complexity. For $d \leq 3$, any error tolerance can achieve linear time for sufficiently large sample size. For $d > 3$, the error must increase with sample size to maintain linear time. Our analysis provides key insights into SKI's scalability-accuracy trade-offs, establishing precise conditions for achieving linear-time GP inference with controlled approximation error.
• Abstract（参考訳）: Structured Kernel Interpolation (SKI) (Wilson et al 2015) は、核行列をインジェクションポイントでの補間によって近似し、線形計算複雑性を実現することにより、ガウス過程(GP)のスケールを支援する。 しかし、厳密な理論上の誤り解析を欠いている。 本稿では,SKIグラム行列の誤差境界を証明し,過パラメータ推定と後部推定に対する誤差の影響について検討する。 さらに、畳み込み立方体補間の下での誘導点数を選択するための実用的なガイドを提供する:それらは誤り制御のために$n^{d/3}$として成長すべきである。 重要な点として、SKIグラムのスペクトル標準誤差と計算複雑性のトレードオフを規定する2つの次元規則を同定する。 $d \leq 3$の場合、任意のエラー耐性は十分に大きなサンプルサイズに対して線形時間を達成することができる。 $d > 3$の場合、線形時間を維持するために、サンプルサイズでエラーが増加する必要がある。 我々の分析はSKIのスケーラビリティ-精度トレードオフに関する重要な洞察を提供し、制御された近似誤差で線形時間GP推定を達成するための正確な条件を確立する。

関連論文リスト

• Scaling Gaussian Processes for Learning Curve Prediction via Latent Kronecker Structure [16.319561844942886]
  GPモデルは,学習曲線予測タスクにおいて,トランスフォーマーの性能と一致することを示す。 我々の方法は、$mathcalO(n3 + m3)$ timeと$mathcalO(n2 + m2)$ spaceのみを必要とする。
  論文  参考訳（メタデータ） (2024-10-11T20:24:33Z)
• Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias [13.642712817536072]
  問題の次元が$d$になるにつれて、所望の誤差内で収束を保証するのに必要なイテレーションの数が増加することを示す。 私たちが取り組んだ重要な技術的課題は、収束を測定するための$W_2,ellinfty$メートル法に一段階の縮約性がないことである。
  論文  参考訳（メタデータ） (2024-08-20T01:24:54Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。 特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-18T04:41:07Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• Precise Learning Curves and Higher-Order Scaling Limits for Dot Product Kernel Regression [41.48538038768993]
  本稿では,ドット積カーネルのカーネルリッジ回帰問題に焦点をあてる。 我々は、任意の整数$r$に対して$m approx dr/r!$が常に学習曲線のピークを観測し、複数のサンプルワイズと非自明な振る舞いを複数のスケールで達成する。
  論文  参考訳（メタデータ） (2022-05-30T04:21:31Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• High-Dimensional Gaussian Process Inference with Derivatives [90.8033626920884]
  低データ状態の$ND$では、Gram行列は$mathcalO(N2D + (N2)3)$に推論のコストを下げる方法で分解できることを示す。 最適化や予測勾配を持つハミルトニアンモンテカルロなど、機械学習に関連する様々なタスクでこの可能性を実証する。
  論文  参考訳（メタデータ） (2021-02-15T13:24:41Z)
• Faster Kernel Interpolation for Gaussian Processes [30.04235162264955]
  大規模データセットへのプロセス(GP)回帰のスケーリングにおける重要な課題は、正確な推論がnxnのカーネル行列を必要とすることである。 構造化カーネル(SKI)は最もスケーラブルな方法の一つである。 1つのO(n)時間前計算ステップの後、SKIをO(m log m)に還元できることが示される。 我々は, m と n の広い範囲で実際に高速化を実演し, 1億点を超える3次元気象レーダデータセット上でGP推定に適用した。
  論文  参考訳（メタデータ） (2021-01-28T00:09:22Z)
• Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step [2.0196229393131726]
  我々は著者の以前の論文で開発されたCGALPアルゴリズムの不正確さとバージョンを分析した。 これにより、いくつかの勾配、項、および/または線形最小化オラクルを不正確な方法で計算することができる。 ラグランジアンのアフィン制約の最適性と実現可能性への収束を示す。
  論文  参考訳（メタデータ） (2020-05-11T14:52:16Z)

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

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