Optimal Kernel Quantile Learning with Random Features

• URL: http://arxiv.org/abs/2408.13591v1
• Date: Sat, 24 Aug 2024 14:26:09 GMT
• Title: Optimal Kernel Quantile Learning with Random Features
• Authors: Caixing Wang, Xingdong Feng,
• Abstract summary: This paper presents a generalization study of kernel quantile regression with random features (KQR-RF) Our study establishes the capacity-dependent learning rates for KQR-RF under mild conditions on the number of RFs. By slightly modifying our assumptions, the capacity-dependent error analysis can also be applied to cases with Lipschitz continuous losses.
• Score: 0.9208007322096533
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The random feature (RF) approach is a well-established and efficient tool for scalable kernel methods, but existing literature has primarily focused on kernel ridge regression with random features (KRR-RF), which has limitations in handling heterogeneous data with heavy-tailed noises. This paper presents a generalization study of kernel quantile regression with random features (KQR-RF), which accounts for the non-smoothness of the check loss in KQR-RF by introducing a refined error decomposition and establishing a novel connection between KQR-RF and KRR-RF. Our study establishes the capacity-dependent learning rates for KQR-RF under mild conditions on the number of RFs, which are minimax optimal up to some logarithmic factors. Importantly, our theoretical results, utilizing a data-dependent sampling strategy, can be extended to cover the agnostic setting where the target quantile function may not precisely align with the assumed kernel space. By slightly modifying our assumptions, the capacity-dependent error analysis can also be applied to cases with Lipschitz continuous losses, enabling broader applications in the machine learning community. To validate our theoretical findings, simulated experiments and a real data application are conducted.

Related papers

• Sharp Analysis for KL-Regularized Contextual Bandits and RLHF [52.519416266840814]
  Reverse-Kullback-Leibler (KL) regularization has emerged to be a predominant technique used to enhance policy optimization in reinforcement learning. We show that a simple two-stage mixed sampling strategy can achieve a sample complexity with only an additive dependence on the coverage coefficient. Our results provide a comprehensive understanding of the roles of KL-regularization and data coverage in RLHF, shedding light on the design of more efficient RLHF algorithms.
  arXiv  Detail & Related papers  (2024-11-07T11:22:46Z)
• Stein Random Feature Regression [18.477250397403722]
  Stein random features (SRF) can be used to generate high-quality RFF samples and flexibly approximate non-analytical spectral measure posteriors. SRFs require only the evaluation of log-probability gradients to perform both kernel approximation and Bayesian kernel learning. We empirically validate the effectiveness of SRFs by comparing them to baselines on kernel approximation and well-known GP regression problems.
  arXiv  Detail & Related papers  (2024-06-01T13:24:48Z)
• Benign Overfitting in Deep Neural Networks under Lazy Training [72.28294823115502]
  We show that when the data distribution is well-separated, DNNs can achieve Bayes-optimal test error for classification. Our results indicate that interpolating with smoother functions leads to better generalization.
  arXiv  Detail & Related papers  (2023-05-30T19:37:44Z)
• Error Bounds for Learning with Vector-Valued Random Features [2.375038919274297]
  This paper provides a comprehensive error analysis of learning with vector-valued random features (RF) The theory is developed for RF ridge regression in a fully general infinite-dimensional input-output setting.
  arXiv  Detail & Related papers  (2023-05-26T18:00:08Z)
• Simplex Random Features [53.97976744884616]
  We present Simplex Random Features (SimRFs), a new random feature (RF) mechanism for unbiased approximation of the softmax and Gaussian kernels. We prove that SimRFs provide the smallest possible mean square error (MSE) on unbiased estimates of these kernels. We show consistent gains provided by SimRFs in settings including pointwise kernel estimation, nonparametric classification and scalable Transformers.
  arXiv  Detail & Related papers  (2023-01-31T18:53:39Z)
• 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)
• Oversampling Divide-and-conquer for Response-skewed Kernel Ridge Regression [20.00435452480056]
  We develop a novel response-adaptive partition strategy to overcome the limitation of the divide-and-conquer method. We show the proposed estimate has a smaller mean squared error (AMSE) than that of the classical dacKRR estimate under mild conditions.
  arXiv  Detail & Related papers  (2021-07-13T04:01:04Z)
• NeRF in detail: Learning to sample for view synthesis [104.75126790300735]
  Neural radiance fields (NeRF) methods have demonstrated impressive novel view synthesis. In this work we address a clear limitation of the vanilla coarse-to-fine approach -- that it is based on a performance and not trained end-to-end for the task at hand. We introduce a differentiable module that learns to propose samples and their importance for the fine network, and consider and compare multiple alternatives for its neural architecture.
  arXiv  Detail & Related papers  (2021-06-09T17:59:10Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  Empirical risk minimization (ERM) is the workhorse of machine learning, but its model-agnostic guarantees can fail when we use adaptively collected data. We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over a hypothesis class. For policy learning, we provide rate-optimal regret guarantees that close an open gap in the existing literature whenever exploration decays to zero.
  arXiv  Detail & Related papers  (2021-06-03T09:50:13Z)
• Random Forest (RF) Kernel for Regression, Classification and Survival [1.8275108630751844]
  We elucidate the performance and properties of the data driven RF kernels used by regularized linear models. We show that for continuous and survival targets, the RF kernels are competitive to RF in higher dimensional scenarios. We also provide the results from real life data sets for the regression, classification and survival to illustrate how these insights may be leveraged in practice.
  arXiv  Detail & Related papers  (2020-08-31T20:21:27Z)

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.