# Asymptotically free sketched ridge ensembles: Risks, cross-validation, and tuning arXiv: https://arxiv.org/abs/2310.04357 · HTML: https://mlsanity.com/paper/2310.04357/ ## Key facts - Cited by 11 papers in the map (data through 14 Oct 2026). - Builds on 31 of its 69 references that are in the map. - First posted on arXiv 6 Oct 2023. ## Builds on (most cited first, 30 of 31) - [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019) - [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019) - [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014) - [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (2019) - [High-Dimensional Asymptotics of Prediction: Ridge Regression and Classification](https://mlsanity.com/paper/1507.03003/) (2015) - [Evaluation of Neural Architectures Trained with Square Loss vs Cross-Entropy in Classification Tasks](https://mlsanity.com/paper/2006.07322/) (2020) - [The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalization](https://mlsanity.com/paper/2008.06786/) (2020) - [On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regression](https://mlsanity.com/paper/2006.05800/) (2020) - [More Than a Toy: Random Matrix Models Predict How Real-World Neural Representations Generalize](https://mlsanity.com/paper/2203.06176/) (2022) - [Asymptotics of Ridge (less) Regression under General Source Condition](https://mlsanity.com/paper/2006.06386/) (2020) - [Optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization](https://mlsanity.com/paper/1805.10939/) (2018) - [High-dimensional analysis of double descent for linear regression with random projections](https://mlsanity.com/paper/2303.01372/) (2023) - [The Lasso with general Gaussian designs with applications to hypothesis testing](https://mlsanity.com/paper/2007.13716/) (2020) - [Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software](https://mlsanity.com/paper/2302.11474/) (2023) - [The Implicit Regularization of Ordinary Least Squares Ensembles](https://mlsanity.com/paper/1910.04743/) (2019) - [Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update](https://mlsanity.com/paper/2107.07480/) (2021) - [Distributed linear regression by averaging](https://mlsanity.com/paper/1810.00412/) (2018) - [Sparse sketches with small inversion bias](https://mlsanity.com/paper/2011.10695/) (2020) - [Ridge Regression: Structure, Cross-Validation, and Sketching](https://mlsanity.com/paper/1910.02373/) (2019) - [WONDER: Weighted one-shot distributed ridge regression in high dimensions](https://mlsanity.com/paper/1903.09321/) (2019) - [Out-of-sample error estimate for robust M-estimators with convex penalty](https://mlsanity.com/paper/2008.11840/) (2020) - [Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling](https://mlsanity.com/paper/1910.11561/) (2019) - [MISSION: Ultra Large-Scale Feature Selection using Count-Sketches](https://mlsanity.com/paper/1806.04310/) (2018) - [Bagging in overparameterized learning: Risk characterization and risk monotonization](https://mlsanity.com/paper/2210.11445/) (2022) - [Subsample Ridge Ensembles: Equivalences and Generalized Cross-Validation](https://mlsanity.com/paper/2304.13016/) (2023) - [Generalized equivalences between subsampling and ridge regularization](https://mlsanity.com/paper/2305.18496/) (2023) - [Asymptotics of the Sketched Pseudoinverse](https://mlsanity.com/paper/2211.03751/) (2022) - [Derivatives and residual distribution of regularized M-estimators with application to adaptive tuning](https://mlsanity.com/paper/2107.05143/) (2021) - [Sketched Ridgeless Linear Regression: The Role of Downsampling](https://mlsanity.com/paper/2302.01088/) (2023) - [The Flip Side of the Reweighted Coin: Duality of Adaptive Dropout and Regularization](https://mlsanity.com/paper/2106.07769/) (2021) ## Built on by (most cited first, 11 of 11) - [Scaling and renormalization in high-dimensional regression](https://mlsanity.com/paper/2405.00592/) (2024) - [Risk and cross validation in ridge regression with correlated samples](https://mlsanity.com/paper/2408.04607/) (2024) - [Analysis of Bootstrap and Subsampling in High-dimensional Regularized Regression](https://mlsanity.com/paper/2402.13622/) (2024) - [Failures and Successes of Cross-Validation for Early-Stopped Gradient Descent](https://mlsanity.com/paper/2402.16793/) (2024) - [A replica analysis of under-bagging](https://mlsanity.com/paper/2404.09779/) (2024) - [Implicit Regularization Paths of Weighted Neural Representations](https://mlsanity.com/paper/2408.15784/) (2024) - [RandALO: Out-of-sample risk estimation in no time flat](https://mlsanity.com/paper/2409.09781/) (2024) - [Newton Meets Marchenko-Pastur: Massively Parallel Second-Order Optimization with Hessian Sketching and Debiasing](https://mlsanity.com/paper/2410.01374/) (2024) - [Revisiting Randomization in Greedy Model Search](https://mlsanity.com/paper/2506.15643/) (2025) - [Free Random Projection for In-Context Reinforcement Learning](https://mlsanity.com/paper/2504.06983/) (2025) - [Mallows-type model averaging: Non-asymptotic analysis and all-subset combination](https://mlsanity.com/paper/2505.02637/) (2025) ## Abstract (arXiv) We employ random matrix theory to establish consistency of generalized cross validation (GCV) for estimating prediction risks of sketched ridge regression ensembles, enabling efficient and consistent tuning of regularization and sketching parameters. Our results hold for a broad class of asymptotically free sketches under very mild data assumptions. For squared prediction risk, we provide a decomposition into an unsketched equivalent implicit ridge bias and a sketching-based variance, and prove that the risk can be globally optimized by only tuning sketch size in infinite ensembles. For general subquadratic prediction risk functionals, we extend GCV to construct consistent risk estimators, and thereby obtain distributional convergence of the GCV-corrected predictions in Wasserstein-2 metric. This in particular allows construction of prediction intervals with asymptotically correct coverage conditional on the training data. We also propose an "ensemble trick" whereby the risk for unsketched ridge regression can be efficiently estimated via GCV using small sketched ridge ensembles. We empirically validate our theoretical results using both synthetic and real large-scale datasets with practical sketches including CountSketch and subsampled randomized discrete cosine transforms.