# Optimal Kernel Quantile Learning with Random Features

arXiv: https://arxiv.org/abs/2408.13591 · HTML: https://mlsanity.com/paper/2408.13591/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 60 references that are in the map.
- First posted on arXiv 24 Aug 2024.

## Builds on (most cited first, 25 of 25)

- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity](https://mlsanity.com/paper/1602.05897/) (2016)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017)
- [On the Error of Random Fourier Features](https://mlsanity.com/paper/1506.02785/) (2015)
- [Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates](https://mlsanity.com/paper/1305.5029/) (2013)
- [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [Distributed learning with regularized least squares](https://mlsanity.com/paper/1608.03339/) (2016)
- [Optimal Rates for Random Fourier Features](https://mlsanity.com/paper/1506.02155/) (2015)
- [Learning with SGD and Random Features](https://mlsanity.com/paper/1807.06343/) (2018)
- [Scaling Neural Tangent Kernels via Sketching and Random Features](https://mlsanity.com/paper/2106.07880/) (2021)
- [But How Does It Work in Theory? Linear SVM with Random Features](https://mlsanity.com/paper/1809.04481/) (2018)
- [Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms](https://mlsanity.com/paper/1801.07226/) (2018)
- [On the Optimality of Misspecified Kernel Ridge Regression](https://mlsanity.com/paper/2305.07241/) (2023)
- [Distributed Kernel Ridge Regression with Communications](https://mlsanity.com/paper/2003.12210/) (2020)
- [Toward Large Kernel Models](https://mlsanity.com/paper/2302.02605/) (2023)
- [Towards a Unified Analysis of Kernel-based Methods Under Covariate Shift](https://mlsanity.com/paper/2310.08237/) (2023)
- [Optimal Rates for Multi-pass Stochastic Gradient Methods](https://mlsanity.com/paper/1605.08882/) (2016)
- [Analysis of regularized Nystr"om subsampling for regression functions of low smoothness](https://mlsanity.com/paper/1806.00826/) (2018)
- [Sharp Analysis of Random Fourier Features in Classification](https://mlsanity.com/paper/2109.10623/) (2021)
- [Towards Sharp Analysis for Distributed Learning with Random Features](https://mlsanity.com/paper/1906.03155/) (2019)

## Built on by (most cited first, 4 of 4)

- [Random Feature Representation Boosting](https://mlsanity.com/paper/2501.18283/) (2025)
- [Inertial Quadratic Majorization Minimization with Application to Kernel Regularized Learning](https://mlsanity.com/paper/2507.04247/) (2025)
- [Adaptive deep nonparametric regression from dependent data under covariate shift](https://mlsanity.com/paper/2607.20309/) (2026)
- [Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees](https://mlsanity.com/paper/2608.25513/) (2026)

## Abstract (arXiv)

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.