Certifying Retraining Regret through Residual Structure

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 $10^{-5}$. 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.

46 pages, 5 figures. Code and reproduction materials: this https URL

Machine Learning (cs.LG)

arXiv:2610.41410 [cs.LG]

(or arXiv:2610.41410v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2610.41410 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

code/FROZEN_VALIDATION_V2.json

code/PROTOCOL_ADAPTIVE_V33.json

code/aggregate_split.py

code/anchor_energy.py

code/arrowhead_certificate.py

code/audit_adaptive_general_v33.py

code/audit_arrow_tree_v29.py

code/audit_arrowhead_exact.py

code/audit_compressed_arrow_v27.py

code/audit_compressed_exact.py

code/audit_contraction_real.py

code/audit_curvature_controls.py

code/audit_energy_decisions.py

code/audit_first_stages.py

code/audit_general_compact_v32.py

code/audit_general_refinement.py

code/audit_localized_refinement.py

code/audit_matched_controls.py

code/audit_panel_alignment.py

code/audit_profile_outer_v31.py

code/audit_real_world.py

code/audit_refinement_cover.py

code/audit_row_edge_refinement.py

code/audit_scip_objective.py

code/audit_sdp_exact.py

code/audit_structure.py

code/audit_tail_diagnostics.py

code/audit_zorro_matched.py

code/audit_zorro_refined.py

code/auto_energy.py

code/auto_energy_audit.py

code/auto_energy_protocol.md

code/auto_energy_run.py

code/automatic_basis.py

code/calibration_analyze.py

code/calibration_protocol.md

code/calibration_run.py

code/calibration_sensitivity.py

code/centered_signal_energy.py

code/compressed_edge_arrow_v27.py

code/compressed_offline_v29.json

code/compressed_polynomial.py

code/confirmation_protocol.md

code/contraction_energy.py

code/contraction_settings.json

code/curvature_controls.py

code/datasets.py

code/decision_settings.json

code/discounted_planar_oracle.py

code/download_contraction_data.py

code/download_extra.py

code/download_public.py

code/dual_certificate.py

code/edge_polynomial.py

code/epsilon_audit.py

code/epsilon_energy.py

code/epsilon_protocol.md

code/epsilon_run.py

code/experiment_settings.json

code/extend_validation_baselines.py

code/fast_interval.py

code/fixed_point_contract.py

code/fresh_arrow_v29.py

code/greedy_audit.py

code/greedy_basis.py

code/greedy_pool.json

code/greedy_protocol.md

code/greedy_run.py

code/halfspace_moment.py

code/independent_mask_settings.json

code/independent_moment_audit.py

code/independent_planar_rows.py

code/interval_arithmetic.py

code/intrinsic_dimension.py

code/leakage_audit.py

code/leakage_energy.py

code/leakage_protocol.md

code/leakage_run.py

code/local_residual.py

code/localized_moment.py

code/metric_audit.py

code/metric_basis.py

code/metric_protocol.md

code/metric_run.py

code/moment_reference.py

code/moment_tail.py

code/multirank_audit.py

code/multirank_run.py

code/nuisance_scale.py

code/nuisance_scale_protocol.md

code/observed_anchor.py

code/pilot_arrow_tree_v28.py

code/planar_audit.py

code/planar_density_run.py

code/planar_oracle.py

code/planar_protocol.md

code/planar_refine.py

code/planar_run.py

code/plot_final_scope.py

code/plot_paper_figures.py

code/polynomial_majorant.py

code/prepare_public_data.py

code/profile_offline_v32.json

code/profile_outer_v31.py

code/profile_query_v31.py

code/project_paths.py

code/protocol.md

code/public_energy_rank3_run.py

code/public_energy_run.py

code/public_problems.py

code/quadratic_majorant.py

code/rank_certificate.py

code/real_world_design.py

code/refinement_pipeline.py

code/rep_pool_pools.json

code/rep_pool_protocol.md

code/rep_pool_run.py

code/residual_energy.py

code/robust_reference.py

code/row_edge_exact.py

code/row_edge_input.py

code/row_edge_offline_checks.json

code/row_edge_oracle.py

code/row_edge_screen.py

code/run_adaptive_general_v33.py

code/run_additional_components.py

code/run_component_base.py

code/run_confirmation.py

code/run_contraction_real.py

code/run_dense_compressed.py

code/run_dense_refinement.py

code/run_energy_decisions.py

code/run_frozen_refinement.py

code/run_general_compact_v32.py

code/run_general_refinement.py

code/run_independent_masks.py

code/run_localized_refinement.py

code/run_matched_controls.py

code/run_multirank_exact.py

code/run_precision_controls.py

code/run_real_world.py

code/run_row_edge_refinement.py

code/run_saved_refinement.py

code/run_scip.py

code/run_scip_matched.py

code/run_structure.py

code/run_tail_diagnostics.py

code/run_zorro_matched.py

code/run_zorro_refined.py

code/sdp_residual.py

code/uniform_curvature_v28.py

code/verify_compressed_v29.py

code/verify_contraction_offline.py

code/verify_offline.py

code/verify_profile_v32.py

code/verify_refinement_offline.py

code/verify_row_edge_offline.py

code/zorro_refined.py

code/zorro_regret.py

requirements-general-linux.txt

requirements-refinement-windows.txt

requirements.txt

results/acquisition/calibration_audit.json

results/acquisition/calibration_plan.json

results/acquisition/calibration_summary.csv

results/acquisition/public_energy_rank3_results.json

results/contraction_real/adaptive_independent_audit.json

results/contraction_real/aggregate.json

results/contraction_real/independent_audit.json

results/contraction_real/pure_energy_summary.csv

results/contraction_real/summary.csv

results/dimension_and_decisions/calibration_endpoints.json

results/dimension_and_decisions/calibration_sensitivity.json

results/dimension_and_decisions/intrinsic_dimension_audit.json

results/energy_decisions/FROZEN_DESIGN.json

results/energy_decisions/aggregate.json

results/energy_decisions/conditions.json

results/energy_decisions/fresh_fixed_point_contract.json

results/energy_decisions/independent_audit.json

results/energy_decisions/primary_fixed_point_contract.json

results/energy_decisions/sensitivity.json

results/energy_decisions/summary.csv

results/energy_mechanism/auto_energy_audit_results.json

results/energy_mechanism/auto_energy_results.json

results/energy_mechanism/curvature_audit.json

results/energy_mechanism/curvature_controls.json

results/energy_mechanism/nuisance_scale_results.json

results/general_adaptive_v33/all_conditions.json

results/general_adaptive_v33/conditions.csv

results/general_adaptive_v33/environment.json

results/general_adaptive_v33/protocol.json

results/general_adaptive_v33/summary.json

results/general_coarsening/additional_components.json

results/general_coarsening/confirmation_summary.csv

results/independent_masks/aggregate.json

results/independent_masks/independent_audit.json

results/independent_masks/summary.csv

results/matched_controls/aggregate.json

results/matched_controls/independent_audit.json

results/matched_controls/regret_levels.json

results/matched_controls/summary.csv

results/matched_controls/tail_components.json

results/matched_external/anytime_curves.json

results/matched_external/midpoint_increments.json

results/matched_external/scip_all_masks.csv

results/matched_external/scip_all_masks.json

results/matched_external/scip_strict_results.json

results/matched_external/scip_summary.csv

results/matched_external/scip_target_results.json

results/matched_external/zorro_independent_audit.json

results/matched_external/zorro_refined_independent_audit.json

results/matched_external/zorro_refined_summary.json

results/matched_external/zorro_summary.json

results/metric_and_leakage/leakage_audit_results.json

results/metric_and_leakage/leakage_results.json

results/metric_and_leakage/metric_audit.json

results/metric_and_leakage/metric_comparison.json

results/multiple_directions/multirank_audit_results.json

results/multiple_directions/multirank_results.json

results/precision_and_scip/SCIP_FOLLOWUP_REPORT.json

results/precision_and_scip/precision_row_summary.csv

results/precision_and_scip/scip_followup_summary.csv

results/precision_and_scip/scip_objective_audit.json

results/real_world/confirmation_summary.csv

results/real_world/independent_audit_results.json

results/real_world/public_energy_aggregate.json

results/refinement_v92/FROZEN_GENERAL_V3.json

results/refinement_v92/FROZEN_VALIDATION_V2.json

results/refinement_v92/audit_summary.json

results/refinement_v92/controls_baseline_extended.json

results/refinement_v92/decisions_baseline_extended.json

results/refinement_v92/dense_edge_summary.json

results/refinement_v92/extended_decision_comparison.json

results/refinement_v92/frozen_controls.json

results/refinement_v92/frozen_decisions.json

results/refinement_v92/frozen_independent.json

results/refinement_v92/frozen_validation.json

results/refinement_v92/general_superconductivity.json

results/refinement_v92/multirank_exact.json

results/refinement_v92/summary.csv

results/refinement_v92/validation_baseline_extended.json

results/residual_controls/corrected_direction_summary.json

results/residual_controls/epsilon_independent_audit.json

results/residual_controls/epsilon_results.json

results/row_geometry/planar_audit.json

results/row_geometry/planar_density_results.json

results/row_geometry/planar_refinement.json

results/row_geometry/planar_results.json

results/row_geometry/structure_robust_results.json

results/structure/independent_structure_audit.json

results/structure/structure_results.json

results/structure/structure_summary.csv

results/tail_diagnostics/diagnostics.csv

results/tail_diagnostics/independent_gram_audit.json

results/tail_diagnostics/summary.json

(251 additional files not shown) You must enabled JavaScript to view entire file list.

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.