Research map / Learning theory and algorithms / Kernels and regression theory
Optimal Kernel Quantile Learning with Random Features
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives capacity-dependent minimax-optimal learning rates for kernel quantile regression with random features (KQR-RF) in both realizable and agnostic settings, with fewer random features via leverage-score sampling.
Problem
Generalization of kernel quantile regression with random features (KQR-RF) with a non-smooth check loss, especially in the agnostic setting where the true quantile function may lie outside the RKHS, and the trade-off between number of random features and statistical accuracy.
Approach
Introduces a refined error decomposition with a least-squares approximation term linking the non-smooth check-loss RF estimator to a KRR-RF estimator, using an adaptive self-calibration condition to get local strong convexity; extends to r in (0,1] via compatibility conditions and data-dependent (leverage score) sampling, and generalizes to Lipschitz losses.
Key results
- Worst-case (uniform sampling) theory gives excess risk O(|D|^{-2r/(2r+gamma)} log^2|D|) with M ~ |D|^{1/(2r+gamma)} for r in (0,1/2), reducing the RF count from O(|D|) to O(|D|^{...}) for r in (0,1].
- Leverage-score sampling (benign case) reduces the required number of random features to M ~ |D|^{gamma/(2r+gamma)} for r in (0,1/2) while keeping the same optimal rate.
- Empirical log-log slopes of excess risk vs sample size were 0.81, 1.21, 1.63, 0.95 across four (r, gamma) scenarios, compared with theoretical rates for the agnostic and realizable cases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use leverage-score sampling instead of uniform sampling | KQR-RF · Agnostic case, r∈(0,1/2) | random feature count: from ${\cal O}(|D|^{\frac{1}{2r+\gamma}})$ to ${\cal O}(|D|^{\frac{\gamma}{2r+\gamma}})$ | Helped |
| Use leverage-score sampling instead of uniform sampling | KQR-RF · Realizable case, r∈[1/2,1] | random feature count: from ${\cal O}(|D|^{\frac{(2r-1)\gamma+1}{2r+\gamma}})$ to ${\cal O}(|D|^{\frac{2r+\gamma-1}{2r+\gamma}})$ | Helped |
| Use leverage-score sampling instead of uniform sampling | KQR-RF · Agnostic and realizable cases (2r+γ≥1) | excess risk rate: {\cal O}(|D|^{-\frac{2r}{2r+\gamma}}\log^2 |D|) | No clear effect |
| Extend the source condition to r∈(0,1], 2r+γ≥1 | KQR-RF · Agnostic KQR-RF | excess risk rate: {\cal O}(|D|^{-\frac{2r}{2r+\gamma}}\log^2 |D|) | Helped |
| Validate the predicted capacity-dependent learning rate in simulations | KQR-RF · Four simulated agnostic and realizable settings | excess risk learning-rate trend: 0.81,1.21,1.63,0.95 | Helped |
Limitations
- Experiments are mainly simulated; the real data application is brief and details are not given in the text.
- Analysis assumes bounded continuous random features and specific capacity and source conditions; the results rely on the adaptive self-calibration assumption.
- The estimator lacks an explicit solution, so theory relies on empirical process arguments rather than closed-form operator analysis.
Experimental setup
Datasets: simulated spline-kernel data (y = Lambda_{r/gamma+1/2}(x,0)+eps, x~U(0,1)) real data application (unspecified in text)
Benchmarks: simulated spline-kernel quantile regression real data application (unspecified)
Metrics: excess risk estimated vs true quantile curves log-log slope of excess risk vs sample size
Baselines: KRR-RF-Uniform KRR-RF-Leverage KQR Lipschitz-loss random features KSVM-RF
Builds on: kernel ridge regression with random features Bochner's theorem random features leverage score sampling for random features Nystrom data-dependent sampling
Closest papers by meaning
- Towards Theoretical Understanding of Learning Large-scale Dependent Data via Random Features (ICML 2024 · similarity 0.88)
- Kernel Regression in Structured Non-IID Settings: Theory and Implications for Denoising Score Learning (NeurIPS 2025 · similarity 0.86)
- Kernel conditional tests from learning-theoretic bounds (NeurIPS 2025 · similarity 0.86)
- A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression (NeurIPS 2024 · similarity 0.86)
- Kernel Quantile Embeddings and Associated Probability Metrics (ICML 2025 · similarity 0.85)
- Supervised Kernel Thinning (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.