Leave-one-out cross-validation estimates how well a model will do on new data. It refits the model once per training example, each time with that example held out, and checks the prediction on the held-out case. For sparse linear classifiers on text with tens of thousands of features, this is the estimator high-dimensional theory trusts, but exact refitting is too slow. Approximate versions take a single Newton correction from the full fit. On the clean RCV1 news corpus they cut the estimated cost from over two weeks to three minutes, with errors often below 0.1%. Text produced by optical character recognition (OCR, software that turns scanned page images into text) breaks a hidden premise of these shortcuts. Misread characters turn one word into many rare garbage tokens, and many of those tokens occur in exactly one document. A feature that lives in a single document is the worst case for a leave-one-out shortcut. When that document is removed, the feature's column becomes all zeros and the feature must leave the model. The shortcut assumes the set of active features stays put.
We propose to treat these single-document ("private") features exactly and apply the Newton approximation only to features shared across documents. The private part needs no approximation at all: once its document is removed, the coefficient is zero. The remaining shared part is where the existing stability guarantees plausibly still hold. We predict this one change restores accurate leave-one-out risk estimates on OCR-corrupted text. We also predict it repairs a documented failure of sparse approximate cross-validation: its instability when used to choose the regularization strength at weak regularization. Our hypothesis is that much of that instability on text comes from low-document-frequency features, and that OCR noise sharply increases their number.
Core Claim
Exact leave-one-out remains a sound target on OCR text. Holding out document $i$ removes its private garbage tokens from training, which mirrors test time, where new documents bring new unseen misreadings. What fails is the cheap approximation to it. We make three claims. First, the number of support changes under single-document removal grows roughly in proportion to the character error rate and inversely with the regularization strength. This contrasts with the sublinear growth (between $p^{0.43}$ and $p^{0.52}$) measured on Gaussian designs by Approximate Leave-one-out Cross Validation for Regression with ℓ1 Regularizers. Second, standard sparse approximate cross-validation degrades accordingly on corrupted text. Third, a block-exact correction that zeroes private coordinates and takes a Newton step on shared coordinates keeps the approximation error near clean-text levels at essentially the same cost.
Research Program
The setting is $\ell_1$-penalized logistic regression on bag-of-words or character n-gram features. Let $\hat\theta$ be the full-data fit and $\hat S$ its active set. Let $P_i \subset \hat S$ be the active features whose column is nonzero only in document $i$, and $C_i = \hat S \setminus P_i$. The proposed leave-one-out parameter is
$$\tilde\theta_{-i}[P_i] = 0,\qquad \tilde\theta_{-i}[C_i] = \hat\theta[C_i] + \big(H_{-i}[C_i,C_i]\big)^{-1} g_i[C_i],$$
where $H_{-i}$ is the Hessian of the training loss with document $i$ excluded and $g_i$ is the gradient of document $i$'s loss at $\hat\theta$. That gradient is computed with the private coefficients included in document $i$'s score.
The first equation is exact for the lasso: an all-zero column receives a zero coefficient. The second is the standard sparse Newton step of Approximate Cross-Validation in High Dimensions with Guarantees, which supplies the method. Our version removes from it the coordinates whose curvature comes from a single document. In the uncorrected step those coordinates make document $i$'s influence on the fit (its leverage) approach one, so the correction divides by a near-zero quantity. The inverse of $H_{-i}[C_i,C_i]$ is obtained from one shared factorization by rank-one downdates, so the cost matches the existing method.
Features with document frequency two or three are not forced to zero by removal but are still fragile. We handle them with a small exact refit restricted to those coordinates, triggered only when such a feature is active in document $i$. The document-frequency cutoff for "fragile" is a tuning knob we will study.
The analysis has two parts. The first is a short proof that the private block is exact and that the remaining error is controlled by the number of fragile, non-private support changes. This extends the support-stability argument of Sparse Approximate Cross-Validation for High-Dimensional GLMs rather than replacing it. The second is an empirical characterization of how support changes scale with character error rate and with the regularization strength $\lambda$.
The work on risk estimation constrains what we claim. Theoretical Analysis of Leave-one-out Cross Validation for Non-differentiable Penalties under High-dimensional Settings shows that exact leave-one-out is consistent for lasso and elastic-net tuning at rate $O(1/n)$, but only with a small ridge term and on Gaussian designs. We therefore report results for both elastic net and pure lasso. We treat that theory as motivation for using leave-one-out as the target, not as a guarantee for corrupted designs. Uniform Consistency of Cross-Validation Estimators for High-Dimensional Ridge Regression covers ridge across the whole regularization path; we include a ridge control in which private features cannot be zeroed and the problem appears only as high leverage.
The OCR work motivates the mechanism. Cheap Character Noise for OCR-Robust Multilingual Embeddings documents how character errors fragment words into rare tokens and supplies our synthetic noise model: random substitutions, insertions, and deletions. That paper addresses robustness of trained representations, not how to estimate risk. Named Entity Extraction from Noisy Input: Speech and OCR gives the classical picture: a roughly linear loss of 0.6 F-measure per 1% word error rate, in a low-dimensional model with no risk-estimation question attached.
Baselines
The naive reference is a single fixed train/validation split. This is what most work on OCR-robust text pipelines reports. We run it with the same model and regularization grid, repeated over 20 random splits to expose its variance. Beating it means a lower mean absolute error to test risk and a lower regret in the chosen $\lambda$.
The strongest existing competitor is sparse approximate cross-validation (both the infinitesimal-jackknife and Newton-step variants) of Approximate Cross-Validation in High Dimensions with Guarantees. It is the only method with demonstrated speed and accuracy on high-dimensional text. On clean RCV1 it cut the estimated exact leave-one-out cost from "over two weeks" to "just three minutes" while "often maintaining errors below 0.1%". No reported result was found on Lacuna for this method on OCR-corrupted or character-noised text. We run it on the same full fits, regularization grid, and hardware as our method. Beating it means a lower relative error to exact leave-one-out at matched noise levels, and more stable selection at small $\lambda$, without exceeding 1.5 times its runtime.
Exact leave-one-out is the accuracy reference. It is computed by true refits on a random subset of 500 held-out documents per configuration, warm-started from the full fit. Ten-fold cross-validation with warm-started regularization paths is the practical competitor described below. The key ablation removes the private-block step but keeps everything else, including the fragile-feature refits. A second ablation keeps the private block but drops the fragile refits. Together these isolate whether the gain comes from exact handling of single-document features specifically.
Why not just…?
Why not just prune rare features with a minimum document frequency before fitting? This is the most serious threat, and we test it directly rather than argue around it. Pruning at document frequency of at least two removes private features by construction, after which standard sparse approximate cross-validation should work again. But pruning changes the model being deployed. The minimum frequency is itself a hyperparameter whose selection needs a risk estimate. And OCR produces systematic misreadings with document frequency two to five that pruning only partly removes. We run pruned-then-standard-shortcut at frequency cutoffs of 2, 3, and 5 as full arms, comparing both test accuracy and estimation error. If pruning at 2 matches the unpruned model's test risk and gives equally accurate estimates, the honest conclusion is that the problem is solved by preprocessing. In that case our contribution shrinks to a diagnosis plus a cheap way to choose the cutoff.
Why not just use ten-fold cross-validation? With warm-started paths, ten-fold cross-validation for a sparse logistic model is computationally affordable, so cost alone does not rule it out. The argument against it is statistical. ROTI-GCV: Generalized Cross-Validation for right-ROTationally Invariant Data shows k-fold estimates are inconsistent when features are comparable to samples, because training on 90% of the data shifts the risk being estimated. We Need to Talk about Standard Splits shows split choice destabilizes NLP conclusions. Whether this bias matters at RCV1 scale is an empirical question, and we measure it: we report ten-fold's estimation bias and selection regret against held-out test risk at each noise level.
Why not just clean the text upstream with post-correction or document image restoration? Correction reduces but does not remove noise. Multi-modular domain-tailored OCR post-correction leaves 15.4% word error rate on unseen historical data, and Common Corpus: The Largest Collection of Ethical Data for LLM Pre-Training states that perfect correction is impossible. Image restoration such as DocEnTr: An End-to-End Document Image Enhancement Transformer adds heavy compute per page. Our noise sweep includes the low-error regime that corrected text would occupy, so we can show at what residual error rate the standard shortcut becomes adequate.
Why not just use generalized cross-validation? That shortcut corrects training error with a single degrees-of-freedom term. It lacks a clean linear form for lasso-type estimators, and Failures and Successes of Cross-Validation for Early-Stopped Gradient Descent shows it fails when regularization depends on the data in ways the static correction misses. We include it only in the ridge control, where it is well defined.
Proposed Experiments
The main testbed is the RCV1 sparse categorization setup used by Stephenson and Broderick, with $N \approx 20{,}000$ and $D \approx 30{,}000$ (see RCV1: A New Benchmark Collection for Text Categorization Research). We corrupt the raw text with character noise at error rates of 0%, 2%, 5%, 10%, and 20%, rebuild word and character n-gram features, and refit. We repeat the protocol on IMDb sentiment, the text benchmark used in the leave-one-out theory paper. We add one corpus with natural OCR errors, the Werther OCR output used in the post-correction work, with a period or edition classification target. Whether this corpus is usable depends on obtaining the paired OCR text and labels.
For each configuration we report four quantities. The first is the count of support changes under single-document removal, split by document frequency. The second is relative error of each shortcut against exact leave-one-out on the 500-document subsample. The third is the regret in held-out test log-loss of the $\lambda$ each method selects. The fourth is wall-clock time.
Three checks decide the proposal. First, support changes on the clean corpus should look sublinear, as in prior work, but should grow roughly linearly with error rate on corrupted text, and most of the growth should come from private and fragile features. If it does not, the mechanism is wrong. Second, at 10% character error and the small-$\lambda$ end of the grid, our estimator should keep error to exact leave-one-out within a factor of two of its clean-text level while the standard shortcut does not. Third, the pruning arm must fail to match our method's combination of test accuracy and estimation accuracy. If pruning matches it, we will report that the simpler fix suffices.
References
- Approximate Leave-one-out Cross Validation for Regression with ℓ1 Regularizers
- Approximate Cross-Validation in High Dimensions with Guarantees
- Sparse Approximate Cross-Validation for High-Dimensional GLMs
- Theoretical Analysis of Leave-one-out Cross Validation for Non-differentiable Penalties under High-dimensional Settings
- Uniform Consistency of Cross-Validation Estimators for High-Dimensional Ridge Regression
- Cheap Character Noise for OCR-Robust Multilingual Embeddings
- Named Entity Extraction from Noisy Input: Speech and OCR
- ROTI-GCV: Generalized Cross-Validation for right-ROTationally Invariant Data
- We Need to Talk about Standard Splits
- Multi-modular domain-tailored OCR post-correction
- Common Corpus: The Largest Collection of Ethical Data for LLM Pre-Training
- DocEnTr: An End-to-End Document Image Enhancement Transformer
- Failures and Successes of Cross-Validation for Early-Stopped Gradient Descent
- RCV1: A New Benchmark Collection for Text Categorization Research