Variational Nearest Neighbor Gaussian Process

• URL: http://arxiv.org/abs/2202.01694v4
• Date: Thu, 21 Nov 2024 16:50:04 GMT
• Title: Variational Nearest Neighbor Gaussian Process
• Authors: Luhuan Wu, Geoff Pleiss, John Cunningham,
• Abstract summary: Variational approximations to Gaussian processes (GPs) typically use a small set of inducing points to form a low-rank approximation to the covariance matrix. We propose variational nearest neighbor Gaussian process (VNNGP), which introduces a prior that only retains correlations within $K$ nearest-neighboring observations. Using the variational framework, VNNGP's objective can be factorized over both observations and inducing points, enabling optimization with a time complexity of $O(K3)$.
• Score: 14.081462755946458
• License:
• Abstract: Variational approximations to Gaussian processes (GPs) typically use a small set of inducing points to form a low-rank approximation to the covariance matrix. In this work, we instead exploit a sparse approximation of the precision matrix. We propose variational nearest neighbor Gaussian process (VNNGP), which introduces a prior that only retains correlations within $K$ nearest-neighboring observations, thereby inducing sparse precision structure. Using the variational framework, VNNGP's objective can be factorized over both observations and inducing points, enabling stochastic optimization with a time complexity of $O(K^3)$. Hence, we can arbitrarily scale the inducing point size, even to the point of putting inducing points at every observed location. We compare VNNGP to other scalable GPs through various experiments, and demonstrate that VNNGP (1) can dramatically outperform low-rank methods, and (2) is less prone to overfitting than other nearest neighbor methods.

Related papers

• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  We introduce a new adaptive $k$-nearest neighbours ($kK$-NN) algorithm that explores the local curvature at a sample to adaptively defining the neighborhood size. Results on many real-world datasets indicate that the new $kK$-NN algorithm yields superior balanced accuracy compared to the established $k$-NN method.
  arXiv  Detail & Related papers  (2024-09-08T13:08:45Z)
• Variational sparse inverse Cholesky approximation for latent Gaussian processes via double Kullback-Leibler minimization [6.012173616364571]
  We combine a variational approximation of the posterior with a similar and efficient SIC-restricted Kullback-Leibler-optimal approximation of the prior. For this setting, our variational approximation can be computed via gradient descent in polylogarithmic time per iteration. We provide numerical comparisons showing that the proposed double-Kullback-Leibler-optimal Gaussian-process approximation (DKLGP) can sometimes be vastly more accurate for stationary kernels than alternative approaches.
  arXiv  Detail & Related papers  (2023-01-30T21:50:08Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  We present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems. Our work is based on the fact that the update rule of the Proximal Point method can be approximated up to accuracy.
  arXiv  Detail & Related papers  (2023-01-10T12:18:47Z)
• Sparse Kernel Gaussian Processes through Iterative Charted Refinement (ICR) [0.0]
  We present a new, generative method named Iterative Charted Refinement (ICR) to model Gaussian Processes. ICR represents long- and short-range correlations by combining views of the modeled locations at varying resolutions with a user-provided coordinate chart. ICR outperforms existing methods in terms of computational speed by one order of magnitude on the CPU and GPU.
  arXiv  Detail & Related papers  (2022-06-21T18:00:01Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  We study shuffling-based variants: minibatch and local Random Reshuffling, which draw gradients without replacement. For smooth functions satisfying the Polyak-Lojasiewicz condition, we obtain convergence bounds which show that these shuffling-based variants converge faster than their with-replacement counterparts. We propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.
  arXiv  Detail & Related papers  (2021-10-20T02:25:25Z)
• Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition [54.07797071198249]
  We introduce a new scalable variational Gaussian process approximation which provides a high fidelity approximation while retaining general applicability. We demonstrate that, on a range of regression and classification problems, our approach can exploit input space symmetries such as translations and reflections. Notably, our approach achieves state-of-the-art results on CIFAR-10 among pure GP models.
  arXiv  Detail & Related papers  (2021-06-10T18:17:57Z)
• Laplace Matching for fast Approximate Inference in Generalized Linear Models [27.70274403550477]
  We propose an approximate inference framework primarily designed to be computationally cheap while still achieving high approximation quality. The concept, which we call emphLaplace Matching, involves closed-form, approximate, bi-directional transformations between the parameter spaces of exponential families. This effectively turns inference in GLMs into conjugate inference (with small approximation errors)
  arXiv  Detail & Related papers  (2021-05-07T08:25:17Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  We develop a new algorithm for non-critical optimization that finds an $O(epsilon)$epsilon point in the optimal product. We validate our results on a variety of large-scale deep learning benchmarks and architectures.
  arXiv  Detail & Related papers  (2021-03-04T19:01:20Z)
• SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for Gaussian Process Regression with Derivatives [86.01677297601624]
  We propose a novel approach for scaling GP regression with derivatives based on quadrature Fourier features. We prove deterministic, non-asymptotic and exponentially fast decaying error bounds which apply for both the approximated kernel as well as the approximated posterior.
  arXiv  Detail & Related papers  (2020-03-05T14:33:20Z)
• Sparse Orthogonal Variational Inference for Gaussian Processes [34.476453597078894]
  We introduce a new interpretation of sparse variational approximations for Gaussian processes using inducing points. We show that this formulation recovers existing approximations and at the same time allows to obtain tighter lower bounds on the marginal likelihood and new variational inference algorithms.
  arXiv  Detail & Related papers  (2019-10-23T15:01:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.