Accuracy of approximate leave-one-out with blockwise nonsmooth regularization

How accurately can restricted-fit approximations replace exact leave-one-out fits in block-sparse regression? The setting fixes bounded block sizes and a partition, Gaussian design with covariance eigenvalues comparable to 1/p, n/p bounded above and below, positive deterministic ridge and penalty parameters, smooth convex loss, finite third score moments and the stated one-sided likelihood-curvature condition.

Why it matters and what counts as progress

Why it matters: Controlled approximations make leave-one-out risk estimation possible without refitting every nonsmooth block-sparse model from scratch.

What counts as progress: Prove a vanishing expected average loss discrepancy under these assumptions, sharpen the O(log^(3/2)(en)/√n) target, or admit broader nonsmooth penalties.

How the problem developed

2016 · Approximation method [1]
Tomoyuki Obuchi and Yoshiyuki Kabashima Derived approximate leave-one-out formulas for LASSO cross-validation to reduce computation; the analysis used a large-sample setting and random-matrix methods.
13 Feb 2024 · Partial result [2]
Haolin Zou, Arnab Auddy, Kamiar Rahnama Rad and Arian Maleki Gave finite-sample error bounds for exact leave-one-out risk estimates with nondifferentiable penalties in proportional high dimensions.
20 Oct 2026 · Reported claim [3]
Authors of the blockwise ALO preprint The preprint bounds average absolute error of approximate leave-one-out in a proportional-dimensional model with blockwise nonsmooth penalties and uniformly bounded block sizes.

AI contribution

On the Accuracy of Approximate Leave-One-Out with Blockwise Nonsmooth Regularization in High-dimensions

Honghao Lin, Songbin Liu, Arian Maleki, Vahab Mirrokni, Chen Shang, David P. Woodruff, Hanbo Yang, Wenjin Zhang

Under Assumptions 2.1–2.5, the expected average absolute loss discrepancy between exact leave-one-out fits and each of the two restricted-fit approximations is O(log^(3/2)(en)/√n). The setting has bounded block sizes, a fixed block partition, Gaussian design with covariance eigenvalues comparable to 1/p, n/p bounded above and below, positive deterministic ridge and penalty parameters, smooth convex loss, finite third score moments and the stated one-sided likelihood-curvature condition.

AI involvementAI-led

ImportanceNotable

Technical verificationFormal (human)

Human understandingFull