Research map / Learning theory and algorithms / Kernels and regression theory
Towards Theoretical Understanding of Learning Large-scale Dependent Data via 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.
Analyzes kernel ridge regression with random features (KRR-RF) for τ-mixing dependent data, proving minimax-optimal rates under exponential mixing decay and sub-optimal rates under polynomial decay.
Problem
Existing theory for random feature kernel ridge regression assumes i.i.d. data; it is unclear whether its minimax learning accuracy holds when observations are dependent (τ-mixing).
Approach
Extends the i.i.d. random-feature analysis of Rudi & Rosasco (2017) to τ-mixing processes by proving Lipschitz continuity of the random feature map via a sub-exponential tail assumption on the feature derivative, and applying a Bernstein inequality for τ-mixing sequences; the resulting rate depends on the mixing decay type.
Key results
- Under exponential τ-mixing decay, KRR-RF attains the i.i.d. minimax rate n^{-2r/(2r+α)} (up to log factors) with the same number of random features as in the i.i.d. case.
- Under polynomial τ-mixing decay, the proven rate is slower than the minimax rate, with the required number of random features reduced by using a tighter bound based on the maximum effective dimension.
- Experiments on synthetic AR and Markov chain data show prediction error decreasing with n and stabilizing, and an M/n ratio of about 0.01 offering a good runtime–accuracy tradeoff.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use KRR with random features on exponentially τ-mixing data rather than relying on an i.i.d. data assumption | KRR-RF · τ-mixing data with exponential decay | squared prediction error rate | No clear effect |
| Use KRR with random features on polynomially τ-mixing data rather than relying on an i.i.d. data assumption | KRR-RF · τ-mixing data with polynomial decay | squared prediction error rate | Hurt |
| Increase the number of random features | KRR-RF · synthetic dependent-data examples | prediction error | Helped |
| Use a random-feature ratio of 0.001 or 0.005 instead of larger ratios | KRR-RF · Example 5.1 | prediction error | Hurt |
| Use a random-feature ratio of 0.01 rather than 0.05 or 0.1 | KRR-RF · synthetic dependent-data examples | prediction error | No clear effect |
| Use 30 random features | KRR-RF · Delhi daily climate time series | prediction accuracy | Helped |
Surprising findings
- Under strong polynomial dependence, far fewer random features suffice (the required M shrinks), which the authors attribute to dependence diminishing the information in the kernel matrix.
Limitations
- Polynomial-decay rate is sub-optimal and it is unresolved whether this is a technical artifact or an inherent limitation; no minimax lower bound is established under polynomial mixing.
- Requires bounded response |Y| ≤ U and bounded feature |ψ| ≤ κ, plus sub-exponential tail on the feature derivative (Assumption 4.1).
Experimental setup
Datasets: synthetic nonparametric time series (Example 5.1) synthetic Markov chain (Example 5.2) daily climate time series Delhi (Kaggle)
Benchmarks: synthetic time series Markov chain Delhi climate daily time series
Metrics: prediction error (root mean squared error on test set) runtime (seconds)
Baselines: KRR with i.i.d. analysis (Rudi & Rosasco 2017) full KRR Nystrom KRR
Builds on: Rudi & Rosasco (2017) Blanchard & Zadorozhnyi (2019) Rahimi & Recht (2007) Caponnetto & De Vito (2007)
Closest papers by meaning
- Kernel Regression in Structured Non-IID Settings: Theory and Implications for Denoising Score Learning (NeurIPS 2025 · similarity 0.89)
- Optimal Kernel Quantile Learning with Random Features (ICML 2024 · similarity 0.88)
- A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression (NeurIPS 2024 · similarity 0.88)
- Kernel conditional tests from learning-theoretic bounds (NeurIPS 2025 · similarity 0.88)
- Dimension-free deterministic equivalents and scaling laws for random feature regression (NeurIPS 2024 · similarity 0.88)
- Computational Efficiency under Covariate Shift in Kernel Ridge Regression (NeurIPS 2025 · similarity 0.86)
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.