Error Estimation for Random Fourier Features

• URL: http://arxiv.org/abs/2302.11174v1
• Date: Wed, 22 Feb 2023 06:54:27 GMT
• Title: Error Estimation for Random Fourier Features
• Authors: Junwen Yao, N. Benjamin Erichson, Miles E. Lopes
• Abstract summary: This paper develops a bootstrap approach to numerically estimate the errors of RFF approximations. The error estimates are specific to the problem at hand, avoiding the pessimism of worst-case bounds. The approach enables adaptive computation, so that the user can quickly inspect the error of a rough initial kernel approximation.
• Score: 14.27855002079769
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Random Fourier Features (RFF) is among the most popular and broadly applicable approaches for scaling up kernel methods. In essence, RFF allows the user to avoid costly computations on a large kernel matrix via a fast randomized approximation. However, a pervasive difficulty in applying RFF is that the user does not know the actual error of the approximation, or how this error will propagate into downstream learning tasks. Up to now, the RFF literature has primarily dealt with these uncertainties using theoretical error bounds, but from a user's standpoint, such results are typically impractical -- either because they are highly conservative or involve unknown quantities. To tackle these general issues in a data-driven way, this paper develops a bootstrap approach to numerically estimate the errors of RFF approximations. Three key advantages of this approach are: (1) The error estimates are specific to the problem at hand, avoiding the pessimism of worst-case bounds. (2) The approach is flexible with respect to different uses of RFF, and can even estimate errors in downstream learning tasks. (3) The approach enables adaptive computation, so that the user can quickly inspect the error of a rough initial kernel approximation and then predict how much extra work is needed. Lastly, in exchange for all of these benefits, the error estimates can be obtained at a modest computational cost.

Related papers

• Empirical Error Estimates for Graph Sparsification [3.6095388702618414]
  Graph sparsification is a technique for accelerating graph-based learning algorithms. Because the sparsification error is random and unknown, users must contend with uncertainty about the reliability of downstream computations. We propose to address these issues by computing empirical error estimates.
  arXiv  Detail & Related papers  (2025-03-11T04:28:57Z)
• Data-driven Error Estimation: Upper Bounding Multiple Errors with No Technical Debt [26.81883988098551]
  We formulate the problem of simultaneously constructing valid confidence intervals (CIs) as estimating a high probability upper bound on the maximum error for a class/set of estimate-estimand-errors. We propose a completely data-driven approach to estimate an upper bound on the maximum error.
  arXiv  Detail & Related papers  (2024-05-07T19:38:26Z)
• DF2: Distribution-Free Decision-Focused Learning [53.2476224456902]
  Decision-focused learning (DFL) has recently emerged as a powerful approach for predictthen-optimize problems. Existing end-to-end DFL methods are hindered by three significant bottlenecks: model error, sample average approximation error, and distribution-based parameterization of the expected objective. We present DF2 -- the first textit-free decision-focused learning method explicitly designed to address these three bottlenecks.
  arXiv  Detail & Related papers  (2023-08-11T00:44:46Z)
• RFFNet: Large-Scale Interpretable Kernel Methods via Random Fourier Features [3.0079490585515347]
  We introduce RFFNet, a scalable method that learns the kernel relevances' on the fly via first-order optimization. We show that our approach has a small memory footprint and run-time, low prediction error, and effectively identifies relevant features. We supply users with an efficient, PyTorch-based library, that adheres to the scikit-learn standard API and code for fully reproducing our results.
  arXiv  Detail & Related papers  (2022-11-11T18:50:34Z)
• Probabilistically Robust Learning: Balancing Average- and Worst-case Performance [105.87195436925722]
  We propose a framework called robustness probabilistic that bridges the gap between the accurate, yet brittle average case and the robust, yet conservative worst case. From a theoretical point of view, this framework overcomes the trade-offs between the performance and the sample-complexity of worst-case and average-case learning.
  arXiv  Detail & Related papers  (2022-02-02T17:01:38Z)
• Learning to Estimate Without Bias [57.82628598276623]
  Gauss theorem states that the weighted least squares estimator is a linear minimum variance unbiased estimation (MVUE) in linear models. In this paper, we take a first step towards extending this result to non linear settings via deep learning with bias constraints. A second motivation to BCE is in applications where multiple estimates of the same unknown are averaged for improved performance.
  arXiv  Detail & Related papers  (2021-10-24T10:23:51Z)
• Scalable Personalised Item Ranking through Parametric Density Estimation [53.44830012414444]
  Learning from implicit feedback is challenging because of the difficult nature of the one-class problem. Most conventional methods use a pairwise ranking approach and negative samplers to cope with the one-class problem. We propose a learning-to-rank approach, which achieves convergence speed comparable to the pointwise counterpart.
  arXiv  Detail & Related papers  (2021-05-11T03:38:16Z)
• SLOE: A Faster Method for Statistical Inference in High-Dimensional Logistic Regression [68.66245730450915]
  We develop an improved method for debiasing predictions and estimating frequentist uncertainty for practical datasets. Our main contribution is SLOE, an estimator of the signal strength with convergence guarantees that reduces the computation time of estimation and inference by orders of magnitude.
  arXiv  Detail & Related papers  (2021-03-23T17:48:56Z)
• Estimating g-Leakage via Machine Learning [34.102705643128004]
  This paper considers the problem of estimating the information leakage of a system in the black-box scenario. It is assumed that the system's internals are unknown to the learner, or anyway too complicated to analyze. We propose a novel approach to perform black-box estimation of the g-vulnerability using Machine Learning (ML) algorithms.
  arXiv  Detail & Related papers  (2020-05-09T09:26:36Z)
• Error Estimation for Sketched SVD via the Bootstrap [60.67199274260768]
  This paper develops a fully data-driven bootstrap method that numerically estimates the actual error of sketched singular vectors/values. The method is computationally inexpensive, because it operates only on sketched objects, and it requires no passes over the full matrix being factored.
  arXiv  Detail & Related papers  (2020-03-10T19:14:08Z)

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.