CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees

• URL: http://arxiv.org/abs/2607.14545v1
• Date: Thu, 16 Jul 2026 04:02:15 GMT
• Title: CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees
• Abstract summary: Machine-learned predictions can speed up offline NP-hard optimization, but asking a predictor what to do amounts to asking it to solve the problem.<n> CASP (Certificate-Augmented Solution Pruning) instead asks which parts of the search space may be ignored, and accepts each answer only after a sound-time verifier has checked it.<n>With trained predictors, unverified pruning loses up to $26%$ of the optimum under distribution shift, while the verified deployment of the same predictions loses nothing.
• Score: 1.7545090618311434
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Machine-learned predictions can speed up offline NP-hard optimization, but asking a predictor what to do amounts to asking it to solve the problem, and committing an unchecked prediction forfeits every worst-case guarantee. CASP (Certificate-Augmented Solution Pruning) instead asks which parts of the search space may be ignored, and accepts each answer only after a sound polynomial-time verifier has checked it, so correctness never depends on prediction quality. We develop the learning theory of this design. The verifier makes the induced loss class uniformly bounded, so certificate parameters are learnable from $\tilde O(\varepsilon^{-2}\log K)$ samples ($K$ the maximum instance size), whereas the unverified commitment class admits no distribution-free rate and, under cost spread $R$, none below $Ω(R/\varepsilon^2)$. Filtering noisy predictions by verifiable confidence dominates the standard min-combiner, with a margin we compute in closed form, and the prediction stays useful even given the LP, because it breaks ties on degenerate optimal faces, where every symmetric LP policy, meaning one whose commitments depend on the instance only through the verifiable confidence values, provably stalls. Experiments on five problems test the theory's quantitative predictions. With trained predictors, unverified pruning loses up to $26%$ of the optimum under distribution shift, while the verified deployment of the same predictions loses nothing.

Related papers

• Replicable Conformal Prediction [0.3058685580689604]
  Two analysts calibrate the same predictive model on independent samples every time.<n>No one can verify that two calibrations produced the same object.<n>We show that sharing a single random seed and rounding the calibrated threshold up to a coarse shared grid resolves the tension.
  arXiv  Detail & Related papers  (2026-08-23T17:47:40Z)
• $TCP_α$: Margin-Controlled Confidence estimation for reliable Music Information Retrieval [7.679660052685777]
  Deep neural networks are often overconfident, assigning high confidence even to incorrect predictions.<n>Existing targets suffer from inherent ambiguity: they assign overlapping confidence values to correct and incorrect predictions, while errors near the decision boundary receive confidence scores indistinguishable from correct predictions.<n>We propose $ TCP_$, a novel confidence target that resolves these limitations by introducing a margin-controlled penalty for misclassified samples.
  arXiv  Detail & Related papers  (2026-08-20T17:58:50Z)
• How to Verify Consistency of Probabilistic Claims [49.47758039235095]
  We construct an interactive PCP to prove a predictive model's consistency.<n>We show how a small additive-soundness gap removes dependence on B.<n>We view our interactive PCP as a first step toward predictive models to prove their own consistency.
  arXiv  Detail & Related papers  (2026-08-11T17:41:39Z)
• Online Conformal Prediction Beyond Feedback [28.843690637682915]
  Uncertainty quantification is essential when deploying machine learning models in safety-critical applications.<n>Online conformal prediction (OCP) provides theoretically principled uncertainty quantification for arbitrary black-box classifiers and non-i.i.d. data streams.<n>We develop OCP with queries (OCPQ) by adapting the label efficient forecaster of Cesa-Bianchi, Lugosi, and Stoltz (2004) to our setting.
  arXiv  Detail & Related papers  (2026-08-07T11:58:48Z)
• Distribution-informed Online Conformal Prediction [53.674678995825666]
  We propose Conformal Optimistic Prediction (COP), an online conformal prediction algorithm incorporating underlying data pattern into the update rule.<n>COP produces tighter prediction sets when predictable pattern exists, while retaining valid coverage guarantees even when estimates are inaccurate.<n>We prove that COP can achieve valid coverage and construct shorter prediction intervals than other baselines.
  arXiv  Detail & Related papers  (2025-12-08T17:51:49Z)
• ZIP-RC: Optimizing Test-Time Compute via Zero-Overhead Joint Reward-Cost Prediction [57.799425838564]
  We present ZIP-RC, an adaptive inference method that equips models with zero-overhead inference-time predictions of reward and cost.<n> ZIP-RC improves accuracy by up to 12% over majority voting at equal or lower average cost.
  arXiv  Detail & Related papers  (2025-12-01T09:44:31Z)
• Classification with Reject Option: Distribution-free Error Guarantees via Conformal Prediction [1.1380162891529535]
  We formalise the approach to machine learning with reject option in binary classification.<n>We provide theoretical guarantees on the resulting error rate.<n>Error-reject curves illustrate the trade-off between error rate and reject rate.
  arXiv  Detail & Related papers  (2025-06-26T23:04:25Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• Robust Conformal Prediction with a Single Binary Certificate [58.450154976190795]
  Conformal prediction (CP) converts any model's output to prediction sets with a guarantee to cover the true label with (adjustable) high probability.<n>We propose a robust conformal prediction that produces smaller sets even with significantly lower MC samples.
  arXiv  Detail & Related papers  (2025-03-07T08:41:53Z)
• On Computationally Efficient Multi-Class Calibration [9.032290717007065]
  Project calibration gives strong guarantees for all downstream decision makers. It ensures that the probabilities predicted by summing the probabilities assigned to labels in $T$ are close to some perfectly calibrated binary predictor.
  arXiv  Detail & Related papers  (2024-02-12T17:25:23Z)
• Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations [78.23408201652984]
  Top-k predictions are used in many real-world applications such as machine learning as a service, recommender systems, and web searches. Our work is based on randomized smoothing, which builds a provably robust classifier via randomizing an input. For instance, our method can build a classifier that achieves a certified top-3 accuracy of 69.2% on ImageNet when an attacker can arbitrarily perturb 5 pixels of a testing image.
  arXiv  Detail & Related papers  (2020-11-15T21:34:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.