Research map / Learning theory and algorithms / Kernels and regression theory
Asymptotically Free Sketched Ridge Ensembles: Risks, Cross-Validation, and Tuning
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.
Proves consistency of generalized cross-validation (GCV) for risk, functionals, and distributions of sketched ridge regression ensembles under asymptotically free sketches, and proposes an ensemble trick to tune unsketched ridge.
Problem
Tuning hyperparameters (regularization, sketch size) of sketched ridge regression ensembles reliably and efficiently, since sketching implicitly regularizes and standard CV is costly or inconsistent in high dimensions.
Approach
Uses random matrix theory and free probability to show sketched ridge ensembles equal unsketched implicit ridge plus a 1/K variance inflation, and that GCV (extended as a plug-in to general pseudo-Lipschitz risk functionals and W2 distribution estimation) is consistent for these quantities for any K, including negative regularization.
Key results
- GCV estimates of squared test risk match the true risk for sketched ridge ensembles (K=5) on synthetic data and on RCV1 and RNA-Seq, improving on 2-fold CV especially when n is small.
- The ensemble trick gives 2R_2 - R_1 as an estimate of unsketched ridge risk, accurate even when the sketch variance term is large.
- Observation sketching yields GCV inconsistency for any finite K, while feature sketching yields consistency.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GCV to estimate squared prediction risk for feature-sketched ridge ensembles | Sketched ridge ensemble · Feature sketching | squared-risk estimation consistency | Helped |
| Use GCV instead of 2-fold CV for risk estimation | CountSketch ridge ensembles · RCV1 and RNA-Seq | risk-estimation accuracy | Helped |
| Sketch observations rather than features | Sketched ridge ensemble with finite K · Observation sketching | squared-risk estimation consistency | Hurt |
| Increase ensemble size K | Feature-sketched ridge ensemble · Squared prediction risk | sketch-induced variance: 1/K | Helped |
| Use the ensemble trick to estimate unsketched ridge risk from sketched ensembles | Ridge regression · Unsketched ridge risk estimation | risk-estimation consistency | Helped |
| Tune sketch size with an unregularized, increasingly large ensemble | Sketched ridge ensemble · Squared prediction risk | risk relative to unsketched ridge | Helped |
| Use GCV-corrected predictions for subquadratic risk functionals | Sketched ridge ensemble · General prediction-risk functionals | risk-estimation consistency | Helped |
| Use GCV-corrected predictions to estimate the joint response-prediction distribution | Sketched ridge ensemble · Joint response-prediction distribution | Wasserstein W2 convergence | Helped |
Surprising findings
- GCV is inconsistent for observation (sample) sketching at any finite ensemble size K, though the ensemble trick still works there.
- Negative regularization can be optimal for sketched ridge ensembles, and the theory covers it.
Limitations
- Results apply only to isotropic ridge regression; extension to general convex regularizers (GLMs) is left open.
- Requires random-matrix assumptions on features (independent entries with bounded 4+delta moments) and pseudo-Lipschitz order-2 error functions.
- GCV fails for observation sketching, so a corrected estimator needs unsketched data.
Experimental setup
Datasets: RCV1 RNA-Seq
Benchmarks: RCV1 RNA-Seq
Metrics: squared risk classification error prediction interval coverage normalized trace (asymptotic freeness check)
Baselines: k-fold cross-validation leave-one-out cross-validation unsketched ridge regression
Builds on: generalized cross-validation free probability (infinitesimal freeness) sketched ridge implicit regularization equivalence
Closest papers by meaning
- Subsample Ridge Ensembles: Equivalences and Generalized Cross-Validation (ICML 2023 · similarity 0.91)
- Sketched Ridgeless Linear Regression: The Role of Downsampling (ICML 2023 · similarity 0.90)
- Ridge Regression: Structure, Cross-Validation, and Sketching (ICLR 2020 · similarity 0.90)
- Risk and cross validation in ridge regression with correlated samples (ICML 2025 · similarity 0.90)
- No Free Lunch from Random Feature Ensembles: Scaling Laws and Near-Optimality Conditions (ICML 2025 · similarity 0.87)
- Optimal Ridge Regularization for Out-of-Distribution Prediction (ICML 2024 · 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.