Approximate leave-one-out (ALO) methods are a class of techniques that estimate the risk of leaving out a single training point without refitting the model from scratch. They have drawn renewed interest because of their connections to machine unlearning and data valuation. Standard ALO derivations rely on Newton steps, which require both the loss and the regularizer to be smooth. In high-dimensional settings, however, regularizers are often nonsmooth, and practitioners have used heuristic ALO variants that lack rigorous justification.
In this paper, Lin et al. analyze one such heuristic ALO method for a broad class of non-differentiable penalties that encourage block sparsity. Working in the proportional high-dimensional regime and assuming uniformly bounded block sizes, they prove that the expected average absolute discrepancy between the exact leave-one-out loss and the ALO approximation is O(log^{3/2}(en)/√n). This is a stronger guarantee under weaker assumptions than previous results.
The proof departs from earlier techniques. Instead of relying on smoothness, the authors obtain sharp bounds on the number of active groups whose status changes when a single data point is removed. This perspective not only yields the error bound but also offers new insight into the stability of sparse estimators under small perturbations of the training data.