On the Accuracy of Approximate Leave-One-Out with Blockwise Nonsmooth Regularization in High-dimensions
Abstract
Approximate leave-one-out (ALO) refers to methods that provide computationally efficient and statistically accurate approximations to leave-one-out risk estimation. These methods have recently attracted increased attention because of their connections to other important problems, including machine unlearning and data valuation. For empirical risk minimization, ALO methods often rely on a few Newton steps and therefore require smooth loss functions and regularizers. In high-dimensional problems, however, regularizers are frequently non-smooth. This has motivated the development of heuristic ALO methods for non-smooth regularization, whose empirical accuracy is often strong but whose theoretical justification remains limited. In this paper, we study the accuracy of a heuristic ALO method for a broad class of non-differentiable penalties that promote block sparsity in the proportional high-dimensional regime. Assuming uniformly bounded block sizes, we prove that the expected average absolute discrepancy between the exact leave-one-out loss and its ALO approximation is O(log3/2(en)/√n). Our proof technique differs substantially from existing approaches and relies on obtaining sharp bounds on the number of active groups whose status changes between the full-data and leave-one-out estimators. In addition to yielding stronger guarantees under weaker assumptions than prior work, our analysis provides new insight into the stability of sparse estimators under perturbations of the training data.
Related
- Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence
- Self-regularization and structural adaptation of NPMLE for Gaussian mixture models in all dimensions
- On the Minimum Number of Linear Pieces Required to Approximate Nonlinear Functions under an Accuracy Constraint
- BRACE: Blockwise Rank Aggregation for Correlation Estimation
- Rotate the Loop: Blockwise Conformality for Looped Transformers
BibTeX
@misc{lin2026accuracy,
title = {{On the Accuracy of Approximate Leave-One-Out with Blockwise Nonsmooth Regularization in High-dimensions}},
author = {Honghao Lin and Songbin Liu and Arian Maleki and Vahab Mirrokni and Chen Shang and David P. Woodruff and Hanbo Yang and Wenjin Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.27502},
eprint = {2610.27502},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.27502},
}
RIS
TY - UNPB
TI - On the Accuracy of Approximate Leave-One-Out with Blockwise Nonsmooth Regularization in High-dimensions
AU - Honghao Lin
AU - Songbin Liu
AU - Arian Maleki
AU - Vahab Mirrokni
AU - Chen Shang
AU - David P. Woodruff
AU - Hanbo Yang
AU - Wenjin Zhang
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.27502
UR - https://arxiv.org/abs/2610.27502
AB - Approximate leave-one-out (ALO) refers to methods that provide computationally efficient and statistically accurate approximations to leave-one-out risk estimation. These methods have recently attracted increased attention because of their connections to other important problems, including machine unlearning and data valuation. For empirical risk minimization, ALO methods often rely on a few Newton steps and therefore require smooth loss functions and regularizers. In high-dimensional problems, however, regularizers are frequently non-smooth. This has motivated the development of heuristic ALO methods for non-smooth regularization, whose empirical accuracy is often strong but whose theoretical justification remains limited. In this paper, we study the accuracy of a heuristic ALO method for a broad class of non-differentiable penalties that promote block sparsity in the proportional high-dimensional regime. Assuming uniformly bounded block sizes, we prove that the expected average absolute discrepancy between the exact leave-one-out loss and its ALO approximation is O(log^3/2(en)/√n). Our proof technique differs substantially from existing approaches and relies on obtaining sharp bounds on the number of active groups whose status changes between the full-data and leave-one-out estimators. In addition to yielding stronger guarantees under weaker assumptions than prior work, our analysis provides new insight into the stability of sparse estimators under perturbations of the training data.
ER -