Certifying Retraining Regret through Residual Structure
Organizations: School of Basic Medical Sciences, Peking University.
Abstract
We certify a fixed ridge predictor's regret against full-feature retraining over every continuous completion of an interval-valued table. Our main theorem gives verifiable original-row residual conditions for a uniform error bound independent of nuisance-feature scale and rank, with an asymptotically sharp leading constant and quantitative leakage stability. Full-rank constructions separate certification dimension from feature dimension, including examples requiring directions beyond the candidate. Observed-row anchors make the conditions computable, while exact row geometry and global search return valid upper bounds and feasible original-table witnesses. A finite-scale contraction and common-domain moment fallback implement the structural result. Four real-world tasks retain all model features and certify twenty rank-three instances to width . Their primary median widths improve over centered moments. Joint residual refinement additionally certifies all twenty new response-independent masks to the same precision within 76.21 seconds. For a concrete fixed-point predictor contract, pure energy certifies thirteen of fifteen stopping decisions in ten seconds, versus five for moments. Refinement certifies all fifteen within 91.68 seconds at the same objective threshold.
Figures & tables
| Data | Increment bounds | A width | M width | Full width | Gain | ||
|---|---|---|---|---|---|---|---|
| Supercond. | 82 | 1664.298 | [23.232, 27.351] | 4.119 | 37.438 | 186.00 | 89.7% |
| Parkinsons | 20 | 817.937 | [10.773, 11.677] | 0.862 | 1.403 | 30.10 | 38.4% |
| Wine Quality | 12 | 424.515 | [2.323, 2.461] | 0.122 | 0.153 | 12.49 | 20.3% |
| Yacht | 7 | 744.339 | [17.220, 19.789] | 2.669 | 3.723 | 58.99 | 25.3% |
| Data | Ours width | M width | Ours (s) | Ours | M |
|---|---|---|---|---|---|
| Supercond. | 3.174 | 254.4 | 65.55 | 5/5 | 0/5 |
| Parkinsons | 0.1055 | 57.95 | 52.29 | 5/5 | 0/5 |
| Wine Quality | 6.321 | 7.278 | 6.03 | 5/5 | 5/5 |
| Yacht | 0.001748 | 25.39 | 9.92 | 5/5 | 0/5 |
| Data | A | M | SCIP |
|---|---|---|---|
| Supercond. | 4.119 / 6.82 | 37.44 / 6.29 | 106.6 / 9.96 |
| Parkinsons | 0.8616 / 4.06 | 1.403 / 4.16 | 0.7925 / 9.98 |
| Wine Quality | 0.1222 / 4.60 | 0.1532 / 4.31 | 0.2836 / 9.95 |
| Yacht | 2.669 / 5.29 | 3.723 / 5.12 | 0.002423 / 9.79 |
Appendix figures & tables34 assets
Supplementary material from the paper’s appendix.
Appendix
| Tail | Verified sufficient condition | Additive error | Role and evidence |
|---|---|---|---|
| Residual energy | Signal residual and coupling; exact support or verified leakage | ; leakage | Full-rank structural separation; nonzero residual and support-leakage series |
| Residual moment | Actual metric; aggregate gradient and cross-block bounds | General real-table certificate; fixed-rank direction controls and acquisition decisions | |
| Spectral | Uniform discarded, whitened covariance bounded by | Sharp benchmark and covariance-based regime; exact sharpness and high-rank separation |
| Cells | Moment width | Energy width | Energy tail | Moment (s) | Energy (s) | ||
|---|---|---|---|---|---|---|---|
| 17 | 32 | 0 | 0.535 | 0.501 | 0.000 | 0.09 | 0.07 |
| 17 | 32 | 1/64 | 5.685 | 0.540 | 0.195 | 0.15 | 0.07 |
| 17 | 32 | 1/32 | 22.740 | 0.657 | 0.781 | 0.14 | 0.07 |
| 17 | 32 | 1/16 | 90.968 | 0.750 | 3.125 | 0.14 | 0.07 |
| 65 | 128 | 0 | 0.535 | 0.501 | 0.000 | 0.75 | 0.72 |
| 65 | 128 | 1/64 | 14.268 | 0.540 | 0.195 | 0.77 | 0.66 |
| Scale | Actual | Energy | D | MT |
|---|---|---|---|---|
| 1 | 0.625 | 0.781 | 1.562 | 2.034 |
| 2 | 0.735 | 0.781 | 2.500 | 4.021 |
| 4 | 0.769 | 0.781 | 2.941 | 6.501 |
| 16 | 0.780 | 0.781 | 3.113 | 7.699 |
| 64 | 0.781 | 0.781 | 3.124 | 7.783 |
| 256 | 0.781 | 0.781 | 3.125 | 7.788 |
| Energy tail | Energy width | Moment width | Energy s | Moment s | |
|---|---|---|---|---|---|
| 0 | 0.7812 | 0.6569 | 57.07 | 0.550 | 0.871 |
| 0.7875 | 0.6628 | 57.12 | 0.545 | 0.870 | |
| 0.8063 | 0.6806 | 57.28 | 0.548 | 0.892 | |
| 0.8836 | 0.7538 | 57.91 | 0.541 | 0.893 | |
| 1.2286 | 0.6993 | 60.43 | 0.573 | 0.884 |
| Condition | Energy tail | Energy width | Moment width | |||
|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0.7813 | 0.6569 | 22.74 |
| 2 | 0 | 0 | 0.7860 | 0.6617 | 22.79 | |
| 3 | 0 | 0 | 0.7875 | 0.6625 | 22.77 | |
| 4 | 0 | 0.7923 | 0.6673 | 22.81 | ||
| 5 | 0 | 0.8258 | 0.6988 | 23.01 | ||
| 6 | 0.8019 | 0.6793 | 22.85 |
| Energy width | Moment width | Candidate-line width | Block width | Block (s) | |||
|---|---|---|---|---|---|---|---|
| 2 | 0 | 0 | 6.96 | 37.6 | 378 | 6.239 | 0.065 |
| 2 | 0 | 7.57 | 38.3 | 378 | 6.239 | 0.074 | |
| 2 | 0 | 509 | 415 | 509 | 6.239 | 0.068 | |
| 2 | 0 | 8.28 | 56.3 | 380 | 6.239 | 0.057 | |
| 2 | 9.31 | 56.5 | 380 | 6.239 | 0.075 | ||
| 2 | 519 | 433 | 519 | 6.239 | 0.072 |
| Work | Guaranteed quantity and mode | All completions | Full-dimensional comparison |
|---|---|---|---|
| Quarteroni et al. (2011), Sec. 6; Balabanov–Nouy (2019), Secs. 2.2–2.3 | Residual/coercivity solution and output-error certificates; Galerkin/POD spaces | Parameterwise certificates; uniformity requires parameter-domain bounds | Full-order parametrized equation solution |
| Chen et al. (2025), Thm. 5 | Distribution-averaged function error; Jacobian bounds | No such guarantee stated | Original function ; reduced function approximation |
| Patil–LeJeune (2024), Thms. 2–3 | Prediction-risk equivalence and GCV consistency; almost-sure asymptotics | No such guarantee stated | Unsketched -feature ridge at implicit ; finite-ensemble variance |
| Present residual-energy theorem | Additive enclosure of maximum completion-relative training regret; finite problem | Yes, under uniform row conditions | Exact retraining in all features at the original |
| Work | Domain and comparator | Guaranteed quantity / relation here |
|---|---|---|
| Reduced basis ( Quarteroni et al., 2011 ; Balabanov and Nouy, 2019 ) | Parametrized full-order equations; Galerkin/POD/greedy spaces | Residual/coercivity approximation and output-error certificates |
| Fixed-rank box-QP ( Hladík et al., 2021 ) | A fixed low-rank quadratic on a box | Global optimum by zonotope faces; foundation for our row geometry |
| Robust regret ( Vanli et al., 2015 ) | Norm-bounded matrix/response perturbations | SDP for a regularized minimax-regret formulation using a first-order comparator approximation |
| Completion-relative learning, 2024 ( Zhen et al., 2024a ) | Incomplete feature tables; published endpoint theorem assumes unbounded intervals | Learning under feature completions; the stated interval assumption matters for finite-box certification |
| Minimal repairs, 2026 ( Zhen et al., 2026a ) | Worst-repair suboptimality gap; Section 4.1 uses adversarial edge repairs | Repair selection and optimization; finite continuous boxes can also have interior worst regret (Proposition 2.1 ) |
| ZORRO, NeurIPS 2024 ( Zhu et al., 2024 ) | Uncertain training features/labels; all exact ridge optima at specified | Sound joint model/data zonotope; our same-target regret conversion and complete costs appear in Table 25 |
| Data | Pattern | Gradient | Metric POD | Metric greedy |
|---|---|---|---|---|
| Diabetes | Conc. | 76.62 | 94.69 | 101.39 |
| Diabetes | Disp. | 68.55 | 68.41 | 69.52 |
| Concrete | Conc. | 6.38 | 7.26 | 7.39 |
| Concrete | Disp. | 8.59 | 8.63 | 9.14 |
| Supercond. | Conc. | 1.19 | 1.32 | 1.55 |
| Supercond. | Disp. | 7.99 | 8.01 | 8.10 |
| Method | Coarse S | Extra S | V | U | Saved |
|---|---|---|---|---|---|
| anchor | 9 | 0 | 0 | 3 | 896 |
| gradient | 9 | 1 | 1 | 1 | 960 |
| metric pod | 9 | 1 | 1 | 1 | 960 |
| metric greedy | 9 | 1 | 1 | 1 | 960 |
| full | 9 | 0 | 1 | 2 | 896 |
| Study | Inputs and comparison | Targets and clock | Reported evidence |
|---|---|---|---|
| Structural family, 12 | Synthetic full-rank tables; rank-one energy/moment | width; 10 s search; setup separate | 12 energy successes; complete costs |
| Nuisance scale, 6 | Fixed ; scalar/moment/energy | Exact rational calculation | Scale-independent contraction |
| Multidimensional structure, 18 | Active ranks 2/3; residual and leakage changes | width; 2 s structural search; exact block refinement | 18 block successes; first-stage and candidate-line controls |
| Real-world tasks, 20 | Four datasets; finite-precision candidates; rank 3 | width, tail; 10 s complete | 20 final-width, 10 strict-tail successes |
| Precision/row controls, 24 | Four tasks, three precisions, two row rules | Same 33 cells; 10 s first stage, 600 s refinement cap | 24 refined successes; 15 centered-moment successes at the same cap |
| Independent masks, 40 | Two sets of five response-independent masks per task | width; 600 s complete cap | 40 refined successes; separate new-mask timings |
| Data | Pattern | 2 | 3 | 4 | 6 | |
|---|---|---|---|---|---|---|
| Diabetes | Conc. | 260.28 | 123.58 | 85.69 | 55.64 | 25.18 |
| Diabetes | Disp. | 123.09 | 109.31 | 108.92 | 95.33 | 59.16 |
| Concrete | Conc. | 14.86 | 8.34 | 5.09 | 3.83 | 1.77 |
| Concrete | Disp. | 11.33 | 10.18 | 8.79 | 7.15 | 4.11 |
| Supercond. | Conc. | 11.50 | 1.94 | 1.71 | 1.57 | 1.25 |
| Supercond. | Disp. | 10.87 | 9.23 | 10.10 | 9.09 | 5.58 |
| Setting | Cells | Lower | Upper | Width | Algorithm (s) | Audit (s) | ||
|---|---|---|---|---|---|---|---|---|
| Diabetes | 442 | 11 | 40 | 2.016236 | 2.026137 | 0.00990 | 37.11 | 1.27 |
| Synthetic, | 128 | 17 | 16 | 7.857718 | 7.867619 | 0.00990 | 61.05 | 2.40 |
| Synthetic, | 128 | 17 | 32 | 17.765885 | 17.775786 | 0.00990 | 96.12 | 3.58 |
| Synthetic, | 128 | 17 | 64 | 39.909574 | 39.919475 | 0.00990 | 812.99 | 96.50 |
| Evidence | Independently checked quantities | Complete trees |
|---|---|---|
| Core row/interval suite | 26 original-row cases, four sharpness controls; actual rounded metrics/projectors and original normal equations | Five synthetic/public trees |
| Automatic energy | Actual partition, direction, radius, leakage constants and original witnesses | Six trees across the fixed perturbation grid |
| Multidimensional structure | Original independent boxes, rational signal coefficients and exact star-block elimination | All eighteen block trees; two energy trees |
| Real-world energy | All twenty anchors, projectors, mixed moments, contraction constants, containing radii and original feasible witnesses | Four, first mask per dataset |
| Joint residual refinement | Original polynomial coefficients, actual metric, nonnegative dyadic duals, exact PSD factors and feasible witnesses | Complete covers for forty independent masks, forty primary/controls and fifteen decisions |
| Dense row-edge refinement | Original joint polynomial, coupling PSD, exact edge exclusions and feasible witnesses | All four complete residual-partition trees |
| Data | Signal width | Nuisance width | |||
|---|---|---|---|---|---|
| Superconductivity | 1024 | 82 | |||
| Parkinsons | 2048 | 20 | |||
| Wine Quality (white) | 2048 | 12 | |||
| Yacht | 308 | 7 |
| Adaptive energy | Centered moment | Full | |||||
|---|---|---|---|---|---|---|---|
| Data | Setup | Search | Total | Setup | Search | Total | Total |
| Supercond. | 2.653 | 4.211 | 6.823 | 1.884 | 4.428 | 6.287 | 10.021 |
| Parkinsons | 0.470 | 3.553 | 4.060 | 0.369 | 3.797 | 4.156 | 10.003 |
| Wine Quality | 0.329 | 4.216 | 4.601 | 0.220 | 4.089 | 4.314 | 10.002 |
| Yacht | 0.156 | 5.119 | 5.289 | 0.086 | 5.039 | 5.125 | 10.004 |
| Data | Original | Contraction | +Radius | +Mixed envelope |
|---|---|---|---|---|
| Supercond. | 7.476 | 5.547 | 5.547 | 4.453 |
| Parkinsons | 3.066 | 0.953 | 0.953 | 0.904 |
| Wine Quality | 1.867 | 0.143 | 0.142 | 0.134 |
| Yacht | 30.287 | 4.132 | 3.879 | 2.788 |
| Data | Median | Median |
|---|---|---|
| Supercond. | 1.689359 | 1.693478 |
| Parkinsons | 0.828699 | 0.829603 |
| Wine Quality | 0.426868 | 0.426990 |
| Yacht | 0.761605 | 0.764284 |
| Data | Rows | Bits | Cap | C width | A width | M width | R width | R seconds |
|---|---|---|---|---|---|---|---|---|
| Supercond. | R | yes | 1.791 | 1.791 | 1.791 | 1.791 | 10.04 | |
| Supercond. | R | 8 | yes | 3.726 | 3.726 | 4.228 | 3.726 | 9.83 |
| Supercond. | R | 4 | – | 3.911 | 3.911 | 35.711 | 3.911 | 10.05 |
| Supercond. | U | – | 75.400 | 75.400 | 75.400 | 8.04 | 459.68 | |
| Supercond. | U | 8 | – | 90.952 | 90.952 | 90.938 | 8.349 | 220.10 |
| Supercond. | U | 4 | – | 203.117 | 203.117 | 321.280 | 1.122 | 87.00 |
| Data | 10 s scaled | 30 s scaled | 10 s unscaled |
|---|---|---|---|
| Concrete | 9.583 | 9.583 | 7.980 |
| Supercond. | 36.305 | 36.305 | 151.492 |
| Airfoil | 7.012 | 7.012 | 7.012 |
| Power Plant | 6.194 | 6.194 | 6.195 |
| Data | Method | Width | Seconds | ||
|---|---|---|---|---|---|
| Supercond. | Adaptive energy | 1.690289243 | 1.694199943 | 3.910700 | 7.096 |
| Supercond. | Centered moment | 1.690288699 | 1.725999809 | 35.711110 | 6.287 |
| Supercond. | SCIP numerical | 1.690299779 | 1.850295633 | 159.995854 | 9.992 |
| Parkinsons | Adaptive energy | 0.828699094 | 0.829603046 | 0.903953 | 3.913 |
| Parkinsons | Centered moment | 0.828699094 | 0.830236015 | 1.536921 | 4.102 |
| Parkinsons | SCIP numerical | 0.828699094 | 0.829491585 | 0.792491 | 9.977 |
| Data | Complete cover | Attempts | Completed boxes | Unresolved boxes | Width | Seconds |
|---|---|---|---|---|---|---|
| Supercond. | – | 19 | 0 | 20 | 185.998 | 10.329 |
| Parkinsons | yes | 1 | 1 | 0 | 17.134 | 0.798 |
| Wine Quality | yes | 1 | 1 | 0 | 4.503 | 0.547 |
| Yacht | yes | 1 | 1 | 0 | 19.788 | 0.278 |
| Data | Midpoint | Increment | Increment |
|---|---|---|---|
| Supercond. | 1664.298 | 23.232 | 27.351 |
| Parkinsons | 817.937 | 10.773 | 11.677 |
| Wine Quality | 424.515 | 2.323 | 2.461 |
| Yacht | 744.339 | 17.220 | 19.789 |
| Data | Single-envelope width | Refined width | Completed envelopes | Complete seconds | Model-envelope cover |
|---|---|---|---|---|---|
| Supercond. | 185.998 | 185.998 | 0 | 10.058 | – |
| Parkinsons | 17.134 | 10.063 | 15 | 10.047 | yes |
| Wine Quality | 4.503 | 3.200 | 24 | 10.339 | yes |
| Yacht | 19.788 | 2.014 | 41 | 10.183 | yes |
| Data | Seed | A width | R width | M width | R seconds |
|---|---|---|---|---|---|
| Supercond. | 91311 | 275.5 | 7.706 | 312.7 | 62.32 |
| Supercond. | 91312 | 157.1 | 2.227 | 202.5 | 87.43 |
| Supercond. | 91313 | 291.2 | 7.927 | 412.4 | 255.06 |
| Supercond. | 91314 | 159.7 | 7.173 | 185.6 | 91.09 |
| Supercond. | 91315 | 214.8 | 1.256 | 252.1 | 90.26 |
| Parkinsons | 91311 | 27.96 | 0.009376 | 34.56 | 99.38 |
| Method | Pool 1 | Pool 2 | Pool 3 | Total STOP | Saved cells | Median STOP seconds |
|---|---|---|---|---|---|---|
| Coarse | 0 | 0 | 0 | 0 | 0 | – |
| Energy | 5 | 5 | 3 | 13 | 429 | 3.098 |
| Adaptive | 5 | 5 | 3 | 13 | 429 | 3.067 |
| Moment | 0 | 5 | 0 | 5 | 165 | 2.199 |
| SCIP numeric | 0 | 0 | 0 | 0 | 0 | – |
| ZORRO refined | 0 | 0 | 0 | 0 | 0 | – |
| Pool | Seed | Midpoint | E width | M width | E | A | M |
|---|---|---|---|---|---|---|---|
| 1 | 91411 | 2397.494 | 4.341 | 54.203 | S | S | U |
| 1 | 91412 | 2398.536 | 3.652 | 42.800 | S | S | U |
| 1 | 91413 | 2396.162 | 4.290 | 56.023 | S | S | U |
| 1 | 91414 | 2394.529 | 3.799 | 39.834 | S | S | U |
| 1 | 91415 | 2394.600 | 3.945 | 45.031 | S | S | U |
| 2 | 91411 | 2349.725 | 3.624 | 25.013 | S | S | S |
| Method | 1% | 2% | 5% |
|---|---|---|---|
| Coarse | 0 | 0 | 0 |
| Energy | 5 | 13 | 15 |
| Adaptive | 5 | 13 | 15 |
| Moment | 0 | 5 | 10 |
| SCIP numeric | 0 | 0 | 2 |
| ZORRO refined | 0 | 0 | 0 |
| Pool | Seed | R width | R seconds | 2% label | Saved cells |
|---|---|---|---|---|---|
| 1 | 91411 | 4.342 | 10.07 | STOP | 33 |
| 1 | 91412 | 3.652 | 10.04 | STOP | 33 |
| 1 | 91413 | 4.29 | 10.05 | STOP | 33 |
| 1 | 91414 | 3.799 | 10.05 | STOP | 33 |
| 1 | 91415 | 3.945 | 10.04 | STOP | 33 |
| 2 | 91411 | 3.624 | 9.84 | STOP | 33 |
| Data | Bin | Cols | Certified | Median width | Max width | Median(s) | Max(s) | Replay(s) | |
|---|---|---|---|---|---|---|---|---|---|
| Diabetes | 11 | 1/32 | 2 | 5/5 | 0.066 | 0.112 | 30.36 | 32.13 | 16.08 |
| Diabetes | 11 | 1/32 | 8 | 5/5 | 0.117 | 0.147 | 14.09 | 22.96 | 15.94 |
| Diabetes | 11 | 1/8 | 2 | 5/5 | 2.770 | 2.999 | 152.95 | 156.76 | 43.25 |
| Diabetes | 11 | 1/8 | 8 | 5/5 | 2.131 | 2.549 | 43.17 | 45.79 | 14.77 |
| Concrete | 9 | 1/32 | 2 | 5/5 | 0.656 | 0.706 | 0.29 | 0.44 | 1.23 |
| Concrete | 9 | 1/32 | 8 | 5/5 | 0.509 | 0.790 | 0.29 | 0.31 | 1.20 |
| Data | Cols | Base | Center | Metric | Anchor |
|---|---|---|---|---|---|
| Diabetes | 2 | 94.24 | 125.07 | 131.28 | 93.29 |
| Diabetes | 8 | 78.85 | 78.85 | 78.96 | 63.74 |
| Concrete | 2 | 5.21 | 10.27 | 11.11 | 5.32 |
| Concrete | 8 | 8.30 | 8.33 | 8.95 | 7.73 |
| Superconductivity | 2 | 2.65 | 6.35 | 7.57 | 1.96 |
| Superconductivity | 8 | 7.64 | 7.64 | 8.43 | 6.04 |
Certified Robustness
Certified robustness develops formal guarantees that model predictions remain reliable under specified input or system perturbations.
See all 98 papers