A common way to solve a huge ridge regression faster is to fit it on a small subset of rows. The safe textbook recipe draws rows with probability proportional to their leverage scores, a measure of how much each row alone determines the fit. Computing those scores costs about as much as solving the problem, so in practice people often just sample rows uniformly and hope. Worst-case theory says this hope fails on coherent data, meaning data where a few rows carry most of the structure. Yet uniform schemes keep working on real coherent datasets. The authors of Newton-LESS flag exactly this gap and leave it unexplained.
This note proposes that the textbook quantity is the wrong one. Maximum coherence controls whether a subsample fails in the worst case. The expected prediction error of a subsampled ridge estimator, to leading order, is controlled by two averages instead: the mean square of the ridge-adjusted leverage scores, and a residual-weighted mean of them. Both averages can be estimated from a few hundred rows, which the maximum cannot, because finding the maximum means searching for a needle in a haystack. Together with a free bound from row norms that catches dangerous rows, these averages give a pre-test. It is far cheaper than computing leverage scores, and it predicts how much accuracy uniform sampling loses and whether paying for importance sampling will beat simply drawing a bigger uniform sample in the same wall-clock time.
Core Claim
Write $A \in \mathbb{R}^{n\times d}$ for the data, $a_i$ for row $i$, $\lambda$ for the ridge penalty, and $H_\lambda = A^\top A + \lambda I$. The ridge leverage of a row and the effective degrees of freedom (the number of directions the penalty leaves unsuppressed) are
$$\ell_i^\lambda = a_i^\top H_\lambda^{-1} a_i, \qquad d_\lambda = \sum_i \ell_i^\lambda = \sum_j \frac{\sigma_j^2}{\sigma_j^2+\lambda},$$
where $\sigma_j^2$ are the eigenvalues of $A^\top A$.
Now draw $m$ rows with probabilities $p_i$ and reweight them by $1/(mp_i)$. Two error terms arise, measured in the norm induced by $H_\lambda$.
The first is the error of the sketched Hessian. Its expected squared Frobenius size is $\frac{1}{m}\sum_i (\ell_i^\lambda)^2/p_i$, up to a lower-order correction. This term drives the bias of the "Hessian sketch" in Sketched Ridge Regression.
The second is the error of the sketched gradient, $\frac{1}{m}\sum_i \ell_i^\lambda e_i^2/p_i$, where $e_i$ is the residual of row $i$ at the full ridge solution. This term drives the variance of the "classical sketch" in the same paper.
Plugging in uniform sampling ($p_i = 1/n$) and exact ridge-leverage sampling ($p_i = \ell_i^\lambda/d_\lambda$), the ratios of uniform to importance-sampled error are
$$\rho_\lambda = \frac{n\sum_i (\ell_i^\lambda)^2}{d_\lambda^2}, \qquad \kappa_\lambda = \frac{n}{d_\lambda}\cdot\frac{\sum_i \ell_i^\lambda e_i^2}{\sum_i e_i^2}.$$
The curvature ratio $\rho_\lambda$ always lies between 1 and the ridge coherence $\mu_\lambda = \frac{n}{d_\lambda}\max_i \ell_i^\lambda$. The label ratio $\kappa_\lambda$ is a residual-weighted average of normalized leverages, each of which has mean exactly 1. Under homoscedastic noise, high-leverage rows have shrunken residuals, so $\kappa_\lambda$ tends to sit near or below 1 even when $\mu$ is enormous.
This gives a concrete and falsifiable explanation of the uniform-sampling paradox. Uniform sampling loses little whenever $\rho_\lambda$ is moderate, which happens when the penalty caps the few spikes so they barely move the mean square. It also needs $\kappa_\lambda$ near 1, which holds when noise is not concentrated on influential rows.
The form "error $\propto$ ratio$/m$" comes from a first-order expansion of the sketched ridge solution. It should therefore hold once $m$ is a modest multiple of $d_\lambda$, and part of the program is to find where it breaks down.
Two facts make the averages cheap to use. First, $\ell_i^\lambda \le \|a_i\|^2/\lambda$, and row norms cost one pass over the data. Second, the number of rows whose norm bound exceeds a threshold $\tau$ is at most $\|A\|_F^2/(\lambda\tau)$. The proposal therefore keeps these flagged rows deterministically. On the remaining rows every leverage is at most $\tau$, so $\rho_\lambda$ and $\kappa_\lambda$ can be estimated by uniformly sampling a few hundred rows, with bounded variance. To evaluate $\ell_i^\lambda$ on just those rows, the method uses a sparse oblivious sketch of $H_\lambda$ built in input-sparsity time. This is the step the maximum cannot match: no small uniform probe reliably finds the largest leverage, but the norm cap rules out the cases where missing it would matter.
Relation to Prior Work
Several papers motivate this proposal by exposing the gap. Newton-LESS builds leverage-sparsified sketches for Newton steps and reports that its uniform variant succeeds on coherent data without a theory. We supply a candidate theory and test it on the same datasets.
The classical failure results also motivate the work. These are Talwalkar et al. and Jin et al. for Nyström approximation, and the analysis in Uniform Sampling for Matrix Approximation. All three bound worst-case spectral error through the maximum leverage. We argue that statistical risk in expectation is governed by different, average quantities. Those papers remain correct about failure probability, which is why we keep a norm-based safeguard instead of discarding the maximum entirely.
Sketched Ridge Regression supplies the decomposition we extend. It shows that the classical sketch carries extra variance and the Hessian sketch carries extra bias, but only for oblivious random projections. We attach a data-dependent multiplier to each side, $\kappa_\lambda$ for the variance and $\rho_\lambda$ for the bias, so the same split applies to row subsampling.
Unconditional Coresets for Regularized Loss Minimization shows that a penalty scaling like $\sqrt n$ bounds every row's sensitivity, so uniform coresets of size $\Theta(d\sqrt n)$ suffice. That result is worst-case and penalty-specific. Ours is an expected-risk statement for any $\lambda$, and it predicts the size of the loss rather than only a sufficient sample size.
The leverage-approximation literature constrains the cost model. This includes the fast estimator of Mahoney et al., Recursive Sampling for the Nystrom Method, and the density-based Fast Statistical Leverage Score Approximation in KRR. These methods set the price of importance sampling that our decision rule weighs against a larger uniform sample. None of them asks whether the price was worth paying for a given dataset and $\lambda$.
Asymptotically Free Sketched Ridge Ensembles shows that generalized cross-validation becomes inconsistent under observation sketching, which removes the obvious cheap tuning route for row subsampling. Our ratio estimates are a partial substitute: they predict relative risk without refitting on held-out folds.
Research Program
The work has three parts.
The first is analytical. We will derive the second-order expansion of the excess risk of row-subsampled ridge, for both the classical and the Hessian sketch, under general sampling probabilities. We will state precisely when $\rho_\lambda$ and $\kappa_\lambda$ capture the leading term, and bound the remainder in terms of $m/d_\lambda$ and the norm threshold $\tau$. We will also characterize when $\kappa_\lambda > 1$. The expected case is heteroscedastic noise whose variance grows with leverage, and this is the regime where uniform sampling should genuinely lose.
The second part is the estimator. It makes one pass to compute row norms and flag rows, builds a sparse sketch of $H_\lambda$ in input-sparsity time, and evaluates ridge leverage on $k$ uniformly drawn unflagged rows. For $\kappa_\lambda$ it adds residuals from a pilot ridge fit on a separate uniform sample. The pilot is cross-fit so the residuals and leverages are not computed on the same rows. We will prove concentration of both estimators given the cap $\tau$, and measure how sensitive $\kappa_\lambda$ is to pilot error. This pilot sensitivity is the same weakness that affects gradient-based sampling, but it should hurt less here because only a scalar average is needed.
The third part is a decision rule. Given a time budget $T$ and a measured cost $T_{\text{lev}}$ for approximate leverage computation, it compares the predicted risk of importance sampling at the affordable $m$ with that of uniform sampling at the larger $m_u$ that $T_{\text{lev}}$ could have bought instead. Both risks use the error-ratio-over-sample-size form above. The rule also chooses $m$, which addresses the oracle-tuning problem that Compressed Least-Squares Regression leaves open for projection dimension.
Baselines
The naive reference point is plain uniform row subsampling with weight $n/m$, solved by the classical and the Hessian sketch at the same $m$. This is what practitioners default to, and the proposal must predict, not merely beat, its error.
The strongest competitor is ridge-leverage sampling with approximate scores. For linear problems we use the double-projection estimator of Mahoney et al. with ridge regularization added. Where a kernel or Nyström view applies, we use recursive ridge leverage sampling. The relevant reported numbers are all costs, not accuracies. Recursive sampling built a 2,000-landmark approximation and finished ridge regression on YearPredictionMSD in about 8.5 minutes. On a 500,000-point synthetic set, recursive ridge-leverage computation took 94.3 seconds versus 35.8 seconds for the density method, per Fast Statistical Leverage Score Approximation in KRR.
No reported held-out risk result for row-subsampled linear ridge on these datasets was found on Lacuna. We will therefore produce the risk curves ourselves, using identical data splits, an identical $\lambda$ grid, and the same solver applied to each subsample. Beating this baseline means one of two things. Either our rule reaches the same held-out risk in less total wall-clock time, with all preprocessing counted. Or, at equal time, it reaches lower risk, on datasets where the rule chooses uniform-plus-flagged sampling.
We also run three other competitors. The uniform-then-refine method of Cohen et al. repairs coherence in input-sparsity time. A sparse oblivious sketch (CountSketch or the subsampled randomized Hadamard transform) represents the approach of making the data incoherent by rotation. Gradient-based sampling was reported roughly 10x faster than approximate leverage sampling at $n = 5{,}000{,}000$. All of these get the same time budget and the same tuning grid for $m$ and $\lambda$.
Two ablations isolate the key ingredient. The first keeps norm-flagged rows and samples the rest uniformly but uses no diagnostic, which tests whether the safeguard alone explains the gains. The second runs the same decision rule driven by estimated $\mu_\lambda$ instead of $\rho_\lambda$ and $\kappa_\lambda$, which tests directly whether averages beat the maximum.
Why not just…?
Why not just always sample uniformly, since regularization tames coherence anyway? Unconditional Coresets supports this only for penalties that grow like $\sqrt n$. For small $\lambda$, recursive sampling reports much worse approximation than leverage sampling on Cod-RNA and YearPredictionMSD. Our theory predicts that uniform sampling is near-optimal exactly when $\rho_\lambda$ and $\kappa_\lambda$ are near 1, and loses by those factors otherwise. The planted-spike and heteroscedastic experiments are designed so that uniform sampling should lose there. If it does not, the theory is wrong.
Why not just always compute approximate leverage scores? Their cost is real: it is the 94.3-second versus 35.8-second gap above, and it repeats for every $\lambda$, because ridge leverage depends on the penalty. When $\rho_\lambda \approx \kappa_\lambda \approx 1$, that time is better spent on a larger uniform sample. The time-to-risk curves will show on which datasets this happens.
Why not just rotate the data with a randomized Hadamard transform or CountSketch so coherence disappears? This is a serious competitor for dense data. However, rotation densifies sparse inputs such as RCV1 and destroys row identity, which matters when the subsample must remain interpretable or reusable. We include it at equal time, and we expect it to win on dense, small-$d$ problems. The claim is limited to settings where it loses on memory or speed.
Why not just use Cohen et al.'s uniform-then-refine algorithm? It is the closest threat. However, it targets a full-rank, unregularized spectral guarantee scaling with $d$, not $d_\lambda$, so it may refine more than the risk requires. Running it as a baseline settles the question. If it matches our rule's time-to-risk, the contribution narrows to the explanation and the prediction, not the algorithm.
Proposed Experiments
The datasets are dense tabular data (YearPredictionMSD, Cod-RNA, covtype, CASP, OnlineNewsPopularity), image features (MNIST, CIFAR-10), sparse text (RCV1), and the Newton-LESS datasets (Musk, WESAD, CIFAR-10). We add the high-coherence synthetic design of Sketched Ridge Regression: $n=10^5$, $d=500$, condition number $10^{12}$. On it we plant spikes and introduce noise whose variance is correlated with leverage. Each dataset is run over a $\lambda$ grid spanning $d_\lambda$ from near $d$ down to a few dozen.
The first and decisive check is predictive validity. For every dataset and $\lambda$, we compute the exact $\rho_\lambda$, $\kappa_\lambda$, and $\mu_\lambda$ offline. We then compare them with the measured ratio of held-out excess risk between uniform and exact-leverage sampling, separately for the classical and the Hessian sketch, across $m$. Excess risk is measured relative to the full ridge fit, mirroring the risk ratio of 0.99 reported for deterministic leverage selection on the TCGA LGG dataset in Ridge Regression and Provable Deterministic Ridge Leverage Score Sampling. The proposal succeeds if $\rho_\lambda$ predicts the Hessian-sketch ratio and $\kappa_\lambda$ predicts the classical-sketch ratio, both within a constant factor once $m$ is several times $d_\lambda$, while $\mu_\lambda$ systematically over-predicts loss on CIFAR-10, Musk, and WESAD. It fails if the averages track measured loss no better than the maximum does.
The second check is the estimator. We measure the relative error of the probe estimates of $\rho_\lambda$ and $\kappa_\lambda$ against the probe size $k$ and the threshold $\tau$, and compare their cost with a full approximate-leverage pass. We stress-test the pilot with deliberately poor pilot fits.
The third check is end-to-end. We plot held-out risk against total wall-clock time, preprocessing included, for every baseline and both ablations. We report the regimes where the rule picks importance sampling, and verify that those are the regimes where importance sampling actually wins.
References
- Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update
- Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging
- Matrix Coherence and the Nystrom Method
- Improved Bounds for the Nyström Method With Application to Kernel Classification
- Uniform Sampling for Matrix Approximation.
- Unconditional Coresets for Regularized Loss Minimization
- Fast approximation of matrix coherence and statistical leverage
- Recursive Sampling for the Nystrom Method
- Fast Statistical Leverage Score Approximation in Kernel Ridge Regression
- Asymptotically Free Sketched Ridge Ensembles: Risks, Cross-Validation, and Tuning
- Gradient-based Sampling: An Adaptive Importance Sampling for Least-squares
- Compressed Least-Squares Regression
- Ridge Regression and Provable Deterministic Ridge Leverage Score Sampling