Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond

• URL: http://arxiv.org/abs/2004.11154v5
• Date: Sun, 11 Jul 2021 18:59:32 GMT
• Title: Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• Authors: Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan A.K. Suykens
• Abstract summary: In this survey, we systematically review the work on random features from the past ten years. First, the motivations, characteristics and contributions of representative random features based algorithms are summarized. Second, we review theoretical results that center around the following key question: how many random features are needed to ensure a high approximation quality. Third, we provide a comprehensive evaluation of popular random features based algorithms on several large-scale benchmark datasets.
• Score: 35.32894170512829
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Random features is one of the most popular techniques to speed up kernel methods in large-scale problems. Related works have been recognized by the NeurIPS Test-of-Time award in 2017 and the ICML Best Paper Finalist in 2019. The body of work on random features has grown rapidly, and hence it is desirable to have a comprehensive overview on this topic explaining the connections among various algorithms and theoretical results. In this survey, we systematically review the work on random features from the past ten years. First, the motivations, characteristics and contributions of representative random features based algorithms are summarized according to their sampling schemes, learning procedures, variance reduction properties and how they exploit training data. Second, we review theoretical results that center around the following key question: how many random features are needed to ensure a high approximation quality or no loss in the empirical/expected risks of the learned estimator. Third, we provide a comprehensive evaluation of popular random features based algorithms on several large-scale benchmark datasets and discuss their approximation quality and prediction performance for classification. Last, we discuss the relationship between random features and modern over-parameterized deep neural networks (DNNs), including the use of high dimensional random features in the analysis of DNNs as well as the gaps between current theoretical and empirical results. This survey may serve as a gentle introduction to this topic, and as a users' guide for practitioners interested in applying the representative algorithms and understanding theoretical results under various technical assumptions. We hope that this survey will facilitate discussion on the open problems in this topic, and more importantly, shed light on future research directions.

Related papers

• Implicit Generative Prior for Bayesian Neural Networks [8.013264410621357]
  We propose a novel neural adaptive empirical Bayes (NA-EB) framework for complex data structures. The proposed NA-EB framework combines variational inference with a gradient ascent algorithm. We demonstrate the practical applications of our framework through extensive evaluations on a variety of tasks.
  arXiv  Detail & Related papers  (2024-04-27T21:00:38Z)
• Subject-specific Deep Neural Networks for Count Data with High-cardinality Categorical Features [1.2289361708127877]
  We propose a novel hierarchical likelihood learning framework for introducing gamma random effects into a Poisson deep neural network. The proposed method simultaneously yields maximum likelihood estimators for fixed parameters and best unbiased predictors for random effects. State-of-the-art network architectures can be easily implemented into the proposed h-likelihood framework.
  arXiv  Detail & Related papers  (2023-10-18T01:54:48Z)
• Regularization-Based Methods for Ordinal Quantification [49.606912965922504]
  We study the ordinal case, i.e., the case in which a total order is defined on the set of n>2 classes. We propose a novel class of regularized OQ algorithms, which outperforms existing algorithms in our experiments.
  arXiv  Detail & Related papers  (2023-10-13T16:04:06Z)
• Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
  We propose a new neural-symbolic method to support end-to-end learning using complex queries with provable reasoning capability. We develop a new dataset containing ten new types of queries with features that have never been considered. Our method outperforms previous methods significantly in the new dataset and also surpasses previous methods in the existing dataset at the same time.
  arXiv  Detail & Related papers  (2023-04-14T11:35:35Z)
• Deep networks for system identification: a Survey [56.34005280792013]
  System identification learns mathematical descriptions of dynamic systems from input-output data. Main aim of the identified model is to predict new data from previous observations. We discuss architectures commonly adopted in the literature, like feedforward, convolutional, and recurrent networks.
  arXiv  Detail & Related papers  (2023-01-30T12:38:31Z)
• Quantitative performance evaluation of Bayesian neural networks [0.0]
  Despite the growing litterature about uncertainty in deep learning, the quality of the uncertainty estimates remains an open question. In this work, we attempt to assess the performance of several algorithms on sampling and regression tasks.
  arXiv  Detail & Related papers  (2022-06-08T06:56:50Z)
• Large-Scale Sequential Learning for Recommender and Engineering Systems [91.3755431537592]
  In this thesis, we focus on the design of an automatic algorithms that provide personalized ranking by adapting to the current conditions. For the former, we propose novel algorithm called SAROS that take into account both kinds of feedback for learning over the sequence of interactions. The proposed idea of taking into account the neighbour lines shows statistically significant results in comparison with the initial approach for faults detection in power grid.
  arXiv  Detail & Related papers  (2022-05-13T21:09:41Z)
• Critically Examining the Claimed Value of Convolutions over User-Item Embedding Maps for Recommender Systems [14.414055798999764]
  In recent years, algorithm research in the area of recommender systems has shifted from matrix factorization techniques to neural approaches. We show through analytical considerations and empirical evaluations that the claimed gains reported in the literature cannot be attributed to the ability of CNNs to model embedding correlations.
  arXiv  Detail & Related papers  (2020-07-23T10:03:47Z)
• A Survey on Causal Inference [64.45536158710014]
  Causal inference is a critical research topic across many domains, such as statistics, computer science, education, public policy and economics. Various causal effect estimation methods for observational data have sprung up.
  arXiv  Detail & Related papers  (2020-02-05T21:35:29Z)
• Convolutional Neural Networks as Summary Statistics for Approximate Bayesian Computation [0.0]
  This paper proposes a convolutional neural network architecture for automatically learning informative summary statistics of temporal responses. We show that the proposed network can effectively circumvent the statistics selection problem of the preprocessing step for ABC inference.
  arXiv  Detail & Related papers  (2020-01-31T10:46:30Z)

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.