# RandALO: Out-of-sample risk estimation in no time flat

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 45 references that are in the map.
- First posted on arXiv 15 Sep 2024.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [TRAK: Attributing Model Behavior at Scale](https://mlsanity.com/paper/2303.14186/) (2023)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Differentiating Through a Cone Program](https://mlsanity.com/paper/1904.09043/) (2019)
- [Cross-validation: what does it estimate and how well does it do it?](https://mlsanity.com/paper/2104.00673/) (2021)
- [Theseus: A Library for Differentiable Nonlinear Optimization](https://mlsanity.com/paper/2207.09442/) (2022)
- [Hutch++: Optimal Stochastic Trace Estimation](https://mlsanity.com/paper/2010.09649/) (2020)
- [Clarabel: An interior-point solver for conic programs with quadratic objectives](https://mlsanity.com/paper/2405.12762/) (2024)
- [Consistent Risk Estimation in Moderately High-Dimensional Linear Regression](https://mlsanity.com/paper/1902.01753/) (2019)
- [Asymptotically free sketched ridge ensembles: Risks, cross-validation, and tuning](https://mlsanity.com/paper/2310.04357/) (2023)
- [Iterative Approximate Cross-Validation](https://mlsanity.com/paper/2303.02732/) (2023)
- [Stochastic diagonal estimation: probabilistic bounds and an improved algorithm](https://mlsanity.com/paper/2201.10684/) (2022)
- [LPGD: A General Framework for Backpropagation through Embedded Optimization Layers](https://mlsanity.com/paper/2407.05920/) (2024)
- [A Fast and Scalable Pathwise-Solver for Group Lasso and Elastic Net Penalized Regression via Block-Coordinate Descent](https://mlsanity.com/paper/2405.08631/) (2024)
- [Tractable Evaluation of Stein's Unbiased Risk Estimate with Convex Regularizers](https://mlsanity.com/paper/2211.05947/) (2022)

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

- [MAGIC: Near-Optimal Data Attribution for Deep Learning](https://mlsanity.com/paper/2504.16430/) (2025)

## Abstract (arXiv)

Estimating out-of-sample risk for models trained on large high-dimensional datasets is an expensive but essential part of the machine learning process, enabling practitioners to optimally tune hyperparameters. Cross-validation (CV) serves as the de facto standard for risk estimation but poorly trades off high bias (K-fold CV) for computational cost (leave-one-out CV). We propose a randomized approximate leave-one-out (RandALO) risk estimator that is not only a consistent estimator of risk in high dimensions but also less computationally expensive than K-fold CV. We support our claims with extensive simulations on synthetic and real data and provide a user-friendly Python package implementing RandALO available on PyPI as randalo and at https://github.com/cvxgrp/randalo.