arXiv preprint ·
On the Accuracy of Approximate Leave-One-Out with Blockwise Nonsmooth Regularization in High-dimensions
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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(\log^{3/2}(en)/\sqrt{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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Statistics Theory
A unified approach for estimation of unnormalized models via Stein operators
Anytime-Valid Runtime Monitoring of Learned Barrier Certificates
Asymmetric Likelihood-Free Hypothesis Testing
Optimal aggregation in multiclass classification
Existence of Minimizers for the Gaussian Mumford-Shah Model via Covariance Floors on the Value Distribution
Get the few papers worth your time in Statistics Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.