Leave-one-out cross-validation estimates how well a model will predict new data. It refits the model N times, each time holding out one of the N training points, and averages the errors on the held-out points. For ridge regression and Gaussian processes this costs almost nothing: a textbook identity turns every training residual into its leave-one-out residual with one division. Support vector regression (SVR) is a widely used kernel method that fits a function while ignoring errors smaller than a tolerance ε. It is generally believed to have no such shortcut, because its loss has corners and so there is no fixed linear "hat matrix" mapping targets to predictions. We argue this belief is only half right. The SVR solution is piecewise affine in the targets. Within one "active set" (the assignment of each point to inside the ε-tube, on its boundary, or outside it), a small local hat matrix exists. Leave-one-out predictions can then be computed exactly by low-rank downdates of that matrix. A cheap optimality check certifies each one, and a warm-started repair handles the rare point whose removal changes the active set.
Exactness matters for a second reason. Once per-sample leave-one-out losses are cheap for every configuration of SVR's three hyperparameters (penalty C, tube width ε, kernel bandwidth γ), we get a full matrix of losses: samples by configurations. That matrix is what honest tuning needs. It lets us estimate how strongly neighbouring configurations are correlated. From that we can build simultaneous confidence statements over the whole grid that are tighter than Bonferroni-style corrections, and we can flag "overtuning", the case where the apparently best configuration actually generalizes worse than the default.
Core Claim
SVR admits a single-pass, certified exact leave-one-out procedure. Its cost is one factorization of the boundary-point system plus a rank-one downdate for each support vector. Points strictly inside the tube cost nothing, because removing them leaves the solution unchanged. The per-sample loss matrix this produces over a dense (C, ε, γ) grid supports a correlation-aware max-statistic bootstrap. That bootstrap returns a confidence set of near-optimal configurations and a test of "tuned beats default", with family-wise error control and more power than Holm–Bonferroni.
The first half fills a gap the literature leaves explicit. Closed-form identities such as the one used by Approximately unbiased estimation of conditional variance in heteroscedastic kernel ridge regression require squared loss. Smooth approximate cross-validation, including ProxACV in Approximate Cross-validation: Guarantees for Model Assessment and Selection, handles a non-smooth penalty but needs a twice-differentiable loss. A Consolidated Cross-Validation Algorithm for Support Vector Machines via Data Reduction gets exact leave-one-out for hinge-loss classifiers by relabelling and warm-started reduced solves, but it never treats the ε-insensitive regression loss. It still solves one reduced problem per held-out point rather than downdating a shared factorization, and it attaches no uncertainty to the tuning outcome. The second half builds on Cross-validation Confidence Intervals for Test Error. That paper gives valid intervals for one model or one pairwise comparison; we extend its logic to simultaneous inference over hundreds of correlated configurations.
Why SVR Has a Local Hat Matrix
Write the SVR predictor as $f(x)=\sum_j \beta_j k(x_j,x)+b$, where $\beta_j\in[-C,C]$ are the dual coefficients and $k$ is the kernel. At the optimum, each training point falls into one of three sets:
- the interior set $\mathcal I$, with $\beta_j=0$ and residual strictly smaller than ε;
- the margin set $\mathcal M$, with $0<|\beta_j|<C$ and residual exactly $\pm\varepsilon$;
- the error set $\mathcal E$, with $|\beta_j|=C$ and residual larger than ε.
With $s_{\mathcal M}$ the signs of the margin coefficients and $\beta_{\mathcal E}$ fixed at $\pm C$, the margin coefficients and intercept solve a bordered linear system:
$$ \begin{bmatrix} K_{\mathcal M\mathcal M} & \mathbf 1 \\ \mathbf 1^\top & 0\end{bmatrix} \begin{bmatrix}\beta_{\mathcal M}\\ b\end{bmatrix} = \begin{bmatrix} y_{\mathcal M}-\varepsilon s_{\mathcal M}-K_{\mathcal M\mathcal E}\beta_{\mathcal E}\\ -\mathbf 1^\top\beta_{\mathcal E}\end{bmatrix}. $$
Here $K_{AB}$ is the kernel matrix between point sets $A$ and $B$. As long as the active set does not change, predictions everywhere are affine in $y_{\mathcal M}$, which is exactly a local hat matrix.
Leave-one-out then splits by case:
- Interior point removed. The solution is unchanged, so the leave-one-out prediction is the full-data prediction.
- Margin or error point removed. We delete its row and column from the bordered system by a Schur-complement downdate costing $O(|\mathcal M|^2)$. For an error point, we also move its fixed contribution $C s_i$ out of the right-hand side. We then recompute predictions on the remaining points in $O(N|\mathcal M|)$ and check the optimality conditions: interior points stay inside the tube, margin coefficients keep their sign within $(0,C)$, and error points stay outside.
- Check fails. We run a few warm-started active-set pivots from the downdated solution.
Every reported leave-one-out value is therefore exact; nothing is approximated. The only question is how often the repair step runs, and that is an empirical quantity we will measure. We expect the repair fraction to grow as C increases and ε shrinks, since more points then sit near the tube edge. This is the low-curvature regime where Iterative Approximate Cross-Validation and Wilson et al. report that Taylor-based approximations break down. The repair fraction is thus also a cheap diagnostic of where fast approximations would fail. It speaks to the problem left open by Multiple-Comparison Testing for Cross-Validation Path Optimization Benchmarks: A Hessian-Mismatch Diagnostic for Holm--Bonferroni Failure Modes, whose early-iteration curvature estimate had a 100% false-positive rate.
Research Program
The first component is the algorithm. We will implement the downdate-and-certify procedure on top of a standard SVR solver, sweeping C and ε at fixed γ with warm starts. For each configuration we store the length-N vector of leave-one-out absolute and squared errors, plus the repair count. We will prove two statements. First, the certificate is sufficient for exactness. Second, total cost is $O(|\mathcal M|^3+(|\mathcal M|+|\mathcal E|)N|\mathcal M|)$ plus repair cost. We will state conditions on the tube width under which the repair count stays bounded.
The second component is inference over the grid. Let $L_{im}$ be the leave-one-out loss of sample $i$ under configuration $m$, and let $d_{im}=L_{im}-L_{i,m_0}$ be the loss difference relative to a reference configuration $m_0$ (the default, or the grid minimizer). We form the studentized mean differences $t_m=\sqrt N\,\bar d_m/\hat\sigma_m$. Here $\bar d_m$ is the mean of $d_{im}$ over samples and $\hat\sigma_m$ is a per-sample variance estimate of the kind Cross-validation Confidence Intervals for Test Error justifies under algorithmic stability. We then calibrate $\max_m t_m$ by a Gaussian multiplier bootstrap over samples.
Because neighbouring configurations have nearly identical loss vectors, the bootstrap maximum behaves like a maximum over a few effective tests, not hundreds. That is the source of the power gain over Holm–Bonferroni, which treats every comparison as potentially independent. The procedure produces three outputs:
- a simultaneous confidence set of configurations not distinguishable from the best;
- a one-sided test of whether the tuned configuration beats the default;
- a winner's-curse-corrected estimate of the selected configuration's error, obtained by subtracting the bootstrap quantile from its leave-one-out error.
SVR with bounded C has a Lipschitz loss and a strongly convex regularizer. This is the stability setting in which the Bayle et al. central limit theorem applies. We will check that condition rather than assume it, especially at large C.
The third component is benchmarking in the style of Overtuning in Hyperparameter Optimization. That work finds that about 10% of tuning runs end with a configuration worse than the default. We will test whether our "tuned beats default" test, when it fails to reject, predicts exactly those runs.
Baselines
Brute-force leave-one-out. The naive reference point retrains LIBSVM once per held-out point with no shortcuts. It defines ground truth for exactness and the runtime ceiling. On classification, A Consolidated Cross-Validation Algorithm for Support Vector Machines via Data Reduction reports that this took over 1.5 hours on arrhythmia, against under one minute for ccvsvm. No reported SVR leave-one-out timing was found on Lacuna. We run it on identical data, kernels and solver tolerance, on the same machine.
Brute-force 10-fold cross-validation. This is standard practice. It is also the strongest practical competitor, because its out-of-fold per-sample losses can feed the same max-bootstrap. We give it the identical grid and parallel cores, and we apply both our simultaneous procedure and Holm–Bonferroni to its outputs. Beating it means matching its selected-model test error, within the paired noise estimated across repetitions, at lower wall-clock time on the full grid. Where the two differ, we will report whether leave-one-out's lower variance per sample yields smaller confidence sets.
CVST. The strongest existing fast-tuning method for SVR is Fast cross-validation via sequential testing. It prunes configurations with Friedman tests on growing subsamples and reports speedups of up to 120× over full cross-validation, with MSE ratios of the selected models often close to 1.0 on the regression sets we reuse. We run the authors' default meta-parameters on the same grid and data. Beating it means equal or lower test MSE of the selected model at comparable wall-clock time. Since CVST offers no error guarantee, the confidence-set outputs have no counterpart there.
Warm-started reduced solves. This ablation isolates the key ingredient, the shared factorization. It computes leave-one-out exactly by warm-started re-solves with interior points skipped, i.e. an SVR port of the ccvsvm strategy. It shares our exactness and our "interior points are free" saving, so any speed difference is attributable to downdating instead of re-solving.
Smoothed SVR with Newton-step ACV. We Huberize the ε-insensitive loss and apply the Newton-step approximation that Wilson et al. analyze. For ProxACV on the Graphical Lasso they report 14× to 27× speedups at relative error below 2%. We measure both its leave-one-out error and its shift in the selected hyperparameters.
Kernel ridge regression with its exact closed form. This is the reference for whether SVR is needed at all, run on the same kernels and bandwidth grid.
Why not just…?
Why not just run 10-fold cross-validation in parallel? For inference this is a genuine threat. The max-bootstrap needs per-sample losses, and 10-fold supplies them. We therefore present the inference procedure as usable with either estimator, and we let the experiments decide whether leave-one-out adds anything beyond speed. The computational claim still stands on its own. A dense three-dimensional grid multiplies the ten refits per configuration by hundreds of configurations. Our method needs one fit per configuration plus downdates that we expect, but must show, to be much cheaper than re-solves.
Why not just smooth the loss and use existing approximate cross-validation? Smoothing changes the estimator and destroys the dual sparsity that makes interior points free, as the ccvsvm results illustrate. Wilson et al. developed ProxACV precisely because smoothing non-smooth terms degraded their approximations. The smoothed baseline above measures both effects directly: approximation error against exact SVR leave-one-out, and drift of the selected (C, ε, γ).
Why not just use kernel ridge regression, which already has an exact shortcut? If kernel ridge regression predicts as well as SVR, the algorithmic half of this work matters only to people who have already committed to SVR. We test the claim that SVR's ε-insensitive, linear-tailed loss helps under heavy-tailed or outlier-contaminated noise. If kernel ridge regression ties SVR even there, we will say so, and the inference half will be reported as applying equally to kernel ridge regression.
Why not just apply Holm–Bonferroni? Holm–Bonferroni works on the eleven-dataset solver benchmark of Yu and Deng. Across hundreds of nearly identical configurations it divides α by the grid size and loses power. It also inherits miscalibrated fold t-tests, which Bayle et al. show under-cover. We measure the size of the confidence set and the power of the "tuned beats default" test under both corrections, at matched family-wise error.
Proposed Experiments
We use the regression suite from Krueger et al.: bank, kin, pumadyn, blocks, bumps, doppler, heavisine and Noisy sinc. We add the Williams heteroscedastic sine design from Talbot et al., plus copies of each dataset with 5–10% of targets replaced by heavy-tailed outliers. For each dataset we draw repeated training samples at N between 500 and 5,000. This range matters because Wistuba et al. report that overtuning drops sharply between these sizes. We hold out a large disjoint pool whose error serves as the true risk.
Check 1: exactness. Our leave-one-out vector must agree with brute-force LIBSVM to within solver tolerance on every configuration. We also report the fraction of support vectors needing repair as a function of C and ε.
Check 2: speed. We report wall-clock time for the full grid against 10-fold cross-validation, CVST and warm-started reduced solves. The downdating ablation should be clearly faster; otherwise the shared factorization contributes nothing.
Check 3: inference. The simultaneous confidence set should contain the configuration that is truly best on the held-out pool in at least 95% of repetitions, while being smaller than the Holm–Bonferroni set. Among runs where the tuned configuration is truly worse than the default, the "tuned beats default" test should fail to reject at a far higher rate than in other runs.
If Check 1 holds but repairs dominate at practically chosen C and ε, the algorithmic claim fails. If Check 3 shows no power gain over Holm–Bonferroni applied to Bayle-corrected p-values, the correlation-aware inference is not worth its complexity.
References
- Approximately unbiased estimation of conditional variance in heteroscedastic kernel ridge regression
- Approximate Cross-validation: Guarantees for Model Assessment and Selection
- A Consolidated Cross-Validation Algorithm for Support Vector Machines via Data Reduction
- Cross-validation Confidence Intervals for Test Error
- Iterative Approximate Cross-Validation
- Multiple-Comparison Testing for Cross-Validation Path Optimization Benchmarks: A Hessian-Mismatch Diagnostic for Holm--Bonferroni Failure Modes
- Overtuning in Hyperparameter Optimization
- Fast cross-validation via sequential testing