Variance-Reducing Couplings for Random Features

• URL: http://arxiv.org/abs/2405.16541v2
• Date: Wed, 02 Oct 2024 20:02:27 GMT
• Title: Variance-Reducing Couplings for Random Features
• Authors: Isaac Reid, Stratis Markou, Krzysztof Choromanski, Richard E. Turner, Adrian Weller,
• Abstract summary: Random features (RFs) are a popular technique to scale up kernel methods in machine learning. We find couplings to improve RFs defined on both Euclidean and discrete input spaces. We reach surprising conclusions about the benefits and limitations of variance reduction as a paradigm.
• Score: 57.73648780299374
• License:
• Abstract: Random features (RFs) are a popular technique to scale up kernel methods in machine learning, replacing exact kernel evaluations with stochastic Monte Carlo estimates. They underpin models as diverse as efficient transformers (by approximating attention) to sparse spectrum Gaussian processes (by approximating the covariance function). Efficiency can be further improved by speeding up the convergence of these estimates: a variance reduction problem. We tackle this through the unifying lens of optimal transport, finding couplings to improve RFs defined on both Euclidean and discrete input spaces. They enjoy theoretical guarantees and sometimes provide strong downstream gains, including for scalable approximate inference on graphs. We reach surprising conclusions about the benefits and limitations of variance reduction as a paradigm, showing that other properties of the coupling should be optimised for attention estimation in efficient transformers.

Related papers

• Sample-efficient Bayesian Optimisation Using Known Invariances [56.34916328814857]
  We show that vanilla and constrained BO algorithms are inefficient when optimising invariant objectives. We derive a bound on the maximum information gain of these invariant kernels. We use our method to design a current drive system for a nuclear fusion reactor, finding a high-performance solution.
  arXiv  Detail & Related papers  (2024-10-22T12:51:46Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  Noise-contrastive estimation(NCE) has been proposed by formulating the objective as the logistic loss of the real data and the artificial noise. In this paper, we study it a direct approach for optimizing the negative log-likelihood of unnormalized models.
  arXiv  Detail & Related papers  (2023-06-13T01:18:16Z)
• FAVOR#: Sharp Attention Kernel Approximations via New Classes of Positive Random Features [39.282051468586666]
  We propose parameterized, positive, non-trigonometric RFs which approximate Gaussian and softmax- Kernels. We show that our methods lead to variance reduction in practice and outperform previous methods in a kernel regression task. We also present FAVOR#, a method for self-attention approximation in Transformers.
  arXiv  Detail & Related papers  (2023-02-01T22:43:29Z)
• Hybrid Random Features [60.116392415715275]
  We propose a new class of random feature methods for linearizing softmax and Gaussian kernels called hybrid random features (HRFs) HRFs automatically adapt the quality of kernel estimation to provide most accurate approximation in the defined regions of interest.
  arXiv  Detail & Related papers  (2021-10-08T20:22:59Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  We analyze a Newton algorithm for homogeneous distributed convex optimization, where each machine can calculate gradients of the same population objective. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance.
  arXiv  Detail & Related papers  (2021-10-07T17:51:10Z)
• 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)
• Towards Unbiased Random Features with Lower Variance For Stationary Indefinite Kernels [26.57122949130266]
  Our algorithm achieves lower variance and approximation error compared with the existing kernel approximation methods. With better approximation to the originally selected kernels, improved classification accuracy and regression ability is obtained.
  arXiv  Detail & Related papers  (2021-04-13T13:56:50Z)
• Beyond the Mean-Field: Structured Deep Gaussian Processes Improve the Predictive Uncertainties [12.068153197381575]
  We propose a novel variational family that allows for retaining covariances between latent processes while achieving fast convergence. We provide an efficient implementation of our new approach and apply it to several benchmark datasets. It yields excellent results and strikes a better balance between accuracy and calibrated uncertainty estimates than its state-of-the-art alternatives.
  arXiv  Detail & Related papers  (2020-05-22T11:10:59Z)
• The k-tied Normal Distribution: A Compact Parameterization of Gaussian Mean Field Posteriors in Bayesian Neural Networks [46.677567663908185]
  Variational Bayesian Inference is a popular methodology for approxing posteriorimating over Bayesian neural network weights. Recent work has explored ever richer parameterizations of the approximate posterior in the hope of improving performance. We find that by decomposing these variational parameters into a low-rank factorization, we can make our variational approximation more compact without decreasing the models' performance.
  arXiv  Detail & Related papers  (2020-02-07T07:33:15Z)

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.