acceptodds
Under review as a conference paper at ICLR 2027

From Local Scores to Post Hoc Certificates

Abstract

Data selection often scores examples using local derivatives at a reference model, although subset quality is set by retraining. We ask when these scores certify that no alternative in a declared exchange neighbourhood improves a returned subset beyond a tolerance. Existing uniform approximation bounds support such guarantees, but symmetric corrections also account for overestimated gains. Since overprediction preserves an upper bound, we focus on correcting underestimated gains. To bound these gains, we represent an exchange as continuous weight transfer, with its local prediction giving the starting slope of the retrained-utility curve. Under verifiable smoothness and curvature conditions, we derive a one-sided correction that retains target curvature’s suppression while controlling training-curvature variation and curvature differences between exchanged examples. Combined with scores recomputed at the returned subset’s trained model, this correction covers the neighbourhood in one computation, without retraining or enumerating alternatives. Exhaustive CIFAR-10 one-swap auditing demonstrates certification despite prediction error, with 14.3% local overprediction of the maximum retrained gain and an analytic correction adding 0.011% to that prediction. On a fixed empirical detection target, our verified certificate covers four exchanges at tolerance 0.02, versus two for symmetric and one for convex tangent bounds.

Primary area:
learning theory
Keywords:
data selection, influence functions, selection certification, bilevel optimization, subset selection

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_8dFjOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies post hoc certification for data subset selection, aiming to determine whether any allowed exchange can improve a selected subset's utility beyond a specified tolerance after retraining. The authors propose a one-sided curvature correction that bounds potential underestimation by local influence scores while exploiting favorable target curvature and accounting for variations in training curvature and example-level Hessians. By combining these bounds with verified parameter regions, the proposed framework provides certificates over entire exchange neighborhoods without retraining or enumerating individual alternatives.

Critical strengths

1.Meaningful problem formulation.

The paper considers an interesting problem: how to assess the quality of an already selected data subset without retraining all possible alternatives. I find the proposed connection between local influence scores and retraining-based certification useful. The curvature analysis provides a way to bound potential improvements over an entire exchange neighborhood, rather than relying only on the accuracy of local predictions.

2.Careful theoretical and experimental analysis.

The paper provides detailed theoretical derivations and examines the conditions required for valid certification. I particularly appreciate the exhaustive CIFAR-10 experiment covering over 1.8 million one-swap alternatives, together with the additional numerical verification. These experiments provide useful evidence for the validity of the proposed bounds.

Critical weaknesses

1. Unclear distinction from existing data selection methods.

Many existing data selection methods already optimize subset quality, and some provide guarantees on the quality of the selected subset. Therefore, I am not fully convinced that post hoc certification offers a sufficiently distinct contribution. Although the authors argue that their method can evaluate arbitrary selected subsets, it remains unclear what additional guarantees or practical benefits it provides over existing selection methods. A more direct comparison with their quality guarantees would help clarify the novelty and necessity of the proposed framework.

2. Limited applicability to practical deep learning.

The main guarantees rely on strong assumptions, including positive definite Hessians and bounded curvature along exchange paths. Most full-neighborhood certification experiments use fixed features and small prediction heads. The Qwen3 and OLMo3 experiments mainly evaluate prediction accuracy rather than rigorous certification. It remains unclear whether the method can be applied effectively to realistic end-to-end training.

3. Insufficient evidence of certificate tightness and practical advantages.

The exhaustive one-swap experiments support the validity of the certificates, but their advantages remain unclear. The strict second-order baseline achieves tighter bounds on all ten CIFAR-10 seeds with only about 20% additional computation. For larger exchanges, the true maximum gain is unknown. In the detection experiments at eight exchanges, the observed improvement reaches only 9.59% of the certified upper bound, leaving its tightness uncertain.

Questions for authors

Q1. Distinction from existing data selection methods.

Many existing data selection methods already optimize subset quality, and some provide theoretical guarantees [1][2]. What additional guarantees does the proposed post hoc certification offer beyond these methods? Could the authors clarify this distinction with concrete examples or comparisons?

Q2. Novelty of the proposed certification framework.

Existing methods, including AMIP [3], higher-order influence approximations [4][5], self-concordant influence analysis [6], and robustness auditing [7][8], have already studied finite data perturbations and related guarantees. What is the key theoretical or practical advantage of the proposed one-sided curvature correction over these approaches? Could the authors provide more direct comparisons?

Q3. Applicability to realistic deep learning.

Most full-neighborhood certification experiments use fixed features and small prediction heads. Can the proposed framework provide meaningful certificates for end-to-end neural network training, rather than only evaluating retraining predictions on large models?

Q4. Certificate tightness and computational cost.

The strict second-order baseline achieves tighter bounds with only about 20% additional computation. Under what conditions is the proposed method preferable? Also, how does certificate tightness change as the exchange neighborhood becomes larger?

References

[1] Killamsetty et al. GLISTER: Generalization Based Data Subset Selection for Efficient and Robust Learning. AAAI, 2021.

[2] Sivasubramanian et al. Training Data Subset Selection for Regression with Controlled Generalization Error. ICML, 2021.

[3] Broderick et al. An Automatic Finite-Sample Robustness Metric: When Can Dropping a Little Data Make a Big Difference? arXiv, 2020.

[4] Giordano et al. A Higher-Order Swiss Army Infinitesimal Jackknife. arXiv, 2019.

[5] Giordano et al. A Swiss Army Infinitesimal Jackknife. AISTATS, 2019.

[6] Fisher et al. Influence Diagnostics Under Self-Concordance. AISTATS, 2023.

[7] Moitra and Rohatgi. Provably Auditing Ordinary Least Squares in Low Dimensions. ICLR, 2023.

[8] Rubinstein and Hopkins. Robustness Auditing for Linear Regression: To Singularity and Beyond. ICLR, 2025.

3 comments
AuthorsOpenReview ↗

What certification adds to selection, and what the new evidence establishes

Q1&W1. What additional guarantee does post hoc certification offer beyond selection methods? The additional guarantee is a stopping certificate for the subset actually returned: every allowed replacement improves its retrained utility by at most ε under the specified training rule and target.

GLISTER's guarantee concerns its one-update validation objective; SELCON gives approximation guarantees for regression selection with validation constraints, under their respective conditions. Our certificate checks the returned subset against all allowed retrained alternatives. It applies after different selectors when the verification conditions hold.

For a concrete decision, all five iteratively selected detection subsets in J.4 certify ε=.005 through four exchanges. After obtaining that certificate, searching this neighborhood for a retrained improvement greater than .005 is unnecessary: no replacement of up to four examples achieves it on the fixed empirical target.

Q2. What is novel about the certification framework, and how does it compare with existing guarantees? The novelty is a shared one-sided curvature correction for the maximum retrained gain over fixed-budget exchanges, including additions (8)–(11).

Theoretical advantage. A symmetric error bound covers both over- and underestimation; an upper certificate only needs to control underestimation. Retaining curvature that suppresses gain avoids charging for overestimation. Our theorem extends this principle beyond concave utility under verified path conditions.

Practical advantage and direct comparison. This can change the stopping decision for the same predictor: in Remark B.6, zero correction certifies zero regret, whereas the smallest symmetric correction yields 1.5. Shared regional bounds also cover all allowed exchanges without retraining each alternative.

Relation to prior guarantees. AMIP/IJ bounds finite-perturbation errors; Fisher uses self-concordant influence bounds; Moitra–Rohatgi and Rubinstein–Hopkins certify regression deletion robustness. Our contribution combines a signed upper correction with whole-neighborhood coverage for budget-preserving exchanges. J.3 directly compares HOIJ2 predictions and certified bounds on 160 fixed witnesses.

Q3&W2. How does the framework apply to realistic deep learning and end-to-end training? Our demonstrated certification scope covers retraining heads on fixed deep features and end-to-end training of a small all-layer network; the Qwen3/OLMo3 studies evaluate influence predictions and retrained outcomes at larger scale.

End-to-end route and evidence. The finite-update route follows the declared training map without requiring a positive-definite ERM Hessian (Theorem B.17). On Iris, all 131 tanh-network parameters train from random initialization, reducing target cross-entropy by 47–56%. We verify all 144 one-swap alternatives for each of three subsets: two certify ε=.01 with bounds .005035/.007476; the third has a verified replacement improving loss by .04722 (L.8, pp. 63–64). On matched path cells, signed bounds .005479/.007937 meet ε=.01, versus absolute bounds .033657/.051335.

Thus feature learning is included in the certified training process. Applying this route to larger networks requires useful derivative bounds over trajectories covering every allowed exchange. The large-model prediction results and the small-network certificates address these different coverage levels.

Q4&W3. How should tightness and computation be traded off, and what changes in larger neighborhoods? Tradeoff and preference conditions. Choose the cheaper analytic bound when it meets the required ε; choose Taylor2 when its extra tightness changes that decision. On all ten original CIFAR cases at ε=.02, Taylor2's roughly 20% extra construction cost leaves the decision unchanged. In the N=4096, k=N/2 study, analytic bounds are 3.7–5.4% above Taylor2 across 160–640-parameter heads, while median construction times are 34–35% lower. These matched float64 measurements quantify the price of saving construction work; formal verification costs are separate (L.2/L.4, pp. 60–61).

Effect of neighborhood size. In three exhaustively retrained CIFAR instances, increasing from one to two exchanges raises bound/true-maximum ratios from 1.4–1.7 to 2.5–3.2. The correction's share rises from 14–19% to 46–56% (D.7): controlling a larger perturbation adds more slack.

A separate endpoint study certifies complete four-exchange neighborhoods at twelve anchors. Verified upper/witness-lower ratios of 1.421–1.564 upper-bound the certificate/true-maximum ratios, at a median paired 25.3% extra construction cost over the fixed-response baseline (Appendix K). For the original eight-exchange anchors, the median witness-lower/family-upper ratio remains 9.59% after expanded search. That interval bounds the unknown true maximum; L.6 reports it separately from the four-exchange study.

I think the topic and the problem addressed in this paper are very interesting. However, I still have some concerns about the experiments. The certification results are mainly based on small models or fixed features, and it is unclear how well the method scales to larger models. Also, the bounds become quite loose as the exchange neighborhood grows, which may limit their practical usefulness. More experiments on computational costs and scalability would help strengthen the paper. In addition, I think the presentation and visualizations could be improved, as the paper is somewhat difficult to follow. I appreciate the authors' efforts in addressing my concerns, but I will maintain my original score.

AuthorsOpenReview ↗

To Reviewer 8dFj

Thank you for reading the revision so carefully. We have verified complete exchange neighborhoods for models trained on fixed features and for a small network trained end to end. As the neighborhood grows, the bound can become too loose to tell us when to stop. When the cheaper analytic bound already rules out an improvement above the chosen threshold, however, we can stop the search without the extra cost of computing a tighter bound. We will improve the exposition and visual presentation of these results in the camera-ready version.

Reviewer_ZyxvOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a post hoc certification framework to evaluate the quality of selected training-data subsets without retraining all alternatives. The method combines local influence scores with a one-sided curvature correction to bound the potential improvement from exchanging training examples. It also considers estimation, numerical, and training errors to provide reliable certification decisions. Experiments on CIFAR-10 and language-related tasks demonstrate the effectiveness of the proposed framework in the evaluated settings.

Critical strengths

The paper introduces a one-sided curvature correction that focuses on underestimated gains rather than symmetric prediction errors. This design is well-motivated and enables tighter certification bounds under suitable conditions. The proposed framework also provides theoretical guarantees over a declared exchange neighborhood without retraining individual alternatives.

The paper provides extensive experiments to validate the proposed framework. In particular, the exhaustive evaluation of over 1.8 million one-swap alternatives on CIFAR-10 offers convincing evidence of the validity and tightness of the certification bounds in the tested setting. Additional experiments investigate different exchange radii, numerical errors, and finite-training effects, further supporting the proposed approach.

Critical weaknesses

Though the proposed method aims at reducing the computational cost of obtaining certification bounds, the results in Appendix H.4 show that the stringent second-order baseline can still provide much tighter bounds in all the 10 CIFAR-10 cases with only about 20% extra computation. For instance, this method could obtain a 1.143 bound-to-truth ratio and the second-order baseline could obtain a 1.027 ratio. Consequently, it is not evident that the computational saving is worth the cost of bound relaxation. If possible, the authors can discuss in which cases does their method outperform the strict second-order baseline.

Questions for authors

Along Appendix H.4, we find that even with only about 20% additional computation, the strict second-order baseline can still provide much tighter certification bounds. Would the authors please examine how the costs of these two methods scale with model size and the number of candidate examples? This would demonstrate the capability of the proposed method to achieve higher efficiency for larger models.

4 comments
AuthorsOpenReview ↗

Choosing the bound for the tolerance, with new measurements at larger scales

W1. When is the computational saving worth the bound relaxation? The saving is worthwhile when our cheaper bound meets the required ε: Taylor2's extra tightness then leaves the stopping decision unchanged, with both bounds meeting the requirement that no allowed replacement improve the subset by more than ε. A practical policy is to check the cheaper analytic bound first and use Taylor2 when extra tightness could change the decision. For example, reading the ten existing CIFAR bounds at ε=.0002, 100 times stricter than the original .02, both methods meet the tolerance in every case (L.2).

The larger-head results show the price of this saving directly. With 4096 candidates and half selected, our bounds are about 3.7–5.4% above Taylor2's across the three tested head sizes, while median construction times are about 34–35% lower. For the 640-parameter head, construction takes 4.468 seconds rather than Taylor2's 6.810 seconds. These measurements compare bound tightness and cost within the same configurations (L.4).

The required tolerance therefore gives a practical choice. At the original exhaustive anchor, both bounds meet ε=.0001; at ε=.00008, only Taylor2 does. The extra computation is useful when that extra tightness changes the decision. L.2 gives the intervals for all ten seeds. These comparisons measure float64 bound construction; formal interval verification is reported separately.

Q1. How do the two methods' costs scale with model size and the number of candidates? At 4096 candidates with 256 selected, increasing the head from 160 to 640 parameters raises our construction-time saving from .13 to .94 seconds; at 640 parameters with half the candidates selected, increasing the pool from 512 to 4096 raises it from .18 to 2.34 seconds. Our construction is faster in every tested configuration.

The table gives analytic/Taylor2 median seconds. N is the candidate count and k the selected subset size; the full sweep is in L.4, Table 25 (p. 61).

Trainable parameters; subset ruleN=512N=4096
160; k=256.272/.291.855/.986
320; k=256.336/.3891.684/2.015
640; k=256.703/.8814.287/5.225
640; k=N/2.698/.8754.468/6.810

The logs also show where Taylor2 spends the extra time. It evaluates a quadratic model for each of k(N−k) exchange pairs; our shared curvature bound avoids these separate evaluations. For the 640-parameter head with 4096 candidates, this stage takes about .90 seconds at k=256 and 2.28 seconds when half the pool is selected. Both methods' total times include the shared fitting and geometry work. Inputs and complete one-swap families are matched; full settings are in L.4.

AuthorsOpenReview ↗

Follow-up for Reviewer Zyxv

Dear Reviewer Zyxv,

Thank you again for your careful review. Your question about when the computational savings are worth a looser bound helped us focus our comparison with Taylor2.

We posted our response on November 13 and wanted to check in before the discussion closes. We would appreciate hearing whether this comparison addresses your concerns. If anything is still unclear, we would be happy to clarify it while the discussion is open.

Thank you for your time.

Best regards, The Authors

Thank you for the additional experiments. I appreciate the clarification on when the compute savings justify a looser bound, as well as the new scaling results, which help address my original concerns.

However, I am not confident enough in judging the broader significance of the theoretical contributions to raise my score. Overall, I remain positive about the paper and will keep my score of 3.

AuthorsOpenReview ↗

Thank You for Your Feedback

Thank you for carefully reading our response and for your positive assessment. We are glad that the clarification of the computational trade-off and the additional scaling results helped address your concerns. We will further clarify the theoretical contributions and their practical implications in the camera-ready version.

Reviewer_BEUvOpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies post hoc certification of data selection. Given a returned subset, it asks whether any subset within a declared exchange neighborhood could achieve a target-utility improvement greater than a specified tolerance after retraining. The authors recompute local influence scores at the returned subset, express the retrained gain as an initial slope plus a curvature integral, and derive a one-sided upper bound on that integral. Verified regional bounds allow one computation to cover all exchanges in the neighborhood without retraining each alternative.

Critical strengths

A clear decision target. The paper addresses a meaningful gap between local data-selection scores and outcomes after retraining. Certifying the absence of a substantial improvement is more directly useful than merely predicting gains.

A well-motivated technical idea. For an upper certificate, overpredicting a gain is safe; underpredicting it is the relevant risk. The curvature decomposition uses this asymmetry to retain favorable curvature rather than paying for absolute prediction error.

Strong validation in tractable settings. One CIFAR-10 experiment retrains all 1,835,008 single-exchange alternatives. The resulting certificate is about 1.15 times the observed maximum gain after outward-rounded verification. The paper also reports frozen protocols, numerical checks, and cases where the method abstains.

Critical weaknesses

1. The paper is difficult to follow, especially in the appendices. It contains many lemmas, propositions, and theorems, but often does not explain why each result is needed or how it advances the central argument. A clearer roadmap would help readers assess the value and novelty of the contributions.

2. The presentation needs substantial editing. I appreciate the authors’ transparent AI-use statement, which discloses assistance with drafting and other aspects of the work. However, several passages are so compressed that their meaning is difficult to understand. The authors should clarify these passages and strengthen the transitions between technical results; the concern is the readability of the final manuscript, not the use of AI tools itself.

Questions for authors

Q1: Which result drives the reported “four versus two versus one exchanges” comparison? This result uses the later signed endpoint bound. The paper should make especially clear how much of the improvement comes from the central shared curvature theorem, the endpoint refinement, and the information or computation available to each baseline.

Q2: What is the end-to-end cost of a formally verified certificate? The CIFAR analytic construction takes 1.687 seconds, but outward-rounded verification takes a further 67.21 seconds. The widely quoted comparison with 282.558 seconds of exhaustive retraining also uses different hardware. A consolidated end-to-end cost table would make the practical trade-off easier to assess.

4 comments
AuthorsOpenReview ↗

How the endpoint refinement improves certification, and what verification costs

Q1. Which result drives “four versus two versus one exchanges”? The 4/2/1 comparison comes from Proposition I.1: signed, symmetric and convex-target endpoint bounds certify four, two and one exchanges. With the reported constants, the shared-curvature path theorem certifies one exchange.

Attribution. At four exchanges on the common verified region, one-sided path control lowers the symmetric path bound from 1.218524 to 1.064215 (12.7%). Endpoint stationarity with response-norm control gives .038106; retaining direction gives .015009; retaining sign gives .014218. Those endpoint variants certify through two, four and four exchanges. Direction extends coverage here, while sign tightens the bound by 5.3%; in the wider region, sign changes .020391 to .019761, crossing ε=.02 (L.5, Table 26, pp. 61–62).

Information and work. Signed and symmetric endpoint bounds share the anchor-Hessian solve for v, sorted local scores and exchange-Hessian action bound. Signed control uses a signed third-derivative bound along v and a target-curvature lower bound; symmetric control uses absolute third derivatives and a target-curvature upper bound. Both require directional matrices and spectral bounds. The convex-target bound uses convexity, the target gradient and verified radius: after containment, its formula is gradient norm × radius. All add the same training-residual correction.

The paired ablations fix the same data, anchor, target and verified region; the original endpoint bounds each optimize on the same radius grid. Shared quantities are reused, without retraining alternatives. The path theorem additionally needs pointwise Hessian and derivative bounds along every exchange chord.

Q2. What is the end-to-end cost of a formally verified certificate? The end-to-end cost from cached features to a formally verified certificate is a median 67.955 seconds on the CPU, including preparation, fitting and interval verification. One certificate covers all 1,835,008 single-exchange alternatives. L.2 details these costs, summarized below:

Stage or workloadSeconds
CPU preparation and fittingabout 1.06
CPU interval verificationabout 66.9
Directly measured CPU total, median67.955
Separate exhaustive retraining, two GPUs: kernel / total282.558 / 302.123

The 67.955-second figure directly times the combined pipeline; the historical 1.687 and 67.21 seconds came from separate executions. Subset selection, feature extraction and PCA fitting precede the timed pipeline, and the interval guarantee starts at the stored transformed inputs. The CPU rows describe certificate construction and verification; the GPU row is the separate exhaustive check, reported on its own hardware.

W1&W2. Why is each result needed, and how do the technical results connect? The revision addresses both concerns in the Introduction's roadmap (p. 2) and the expanded explanations in Sections 3–5 (pp. 3–8): why each result is needed and how it advances the argument.

W1: purpose and roadmap. The Introduction's “Reading the results” connects four steps. Local scores give the initial slope; the curvature theorem bounds the change toward the retrained endpoint; region verification makes that bound valid for every allowed exchange; error allowances turn it into a decision at ε. This explains the role of each result in the argument. Appendix C's opening separately identifies the computational obstacle, the regional construction that makes the constants computable, and the structured examples where the certificate is informative. The finite-update and endpoint routes are identified with their own conditions and supporting experiments.

W2: unpacking compressed arguments. Section 3.2 explains the score as the starting slope along a data-weight path. Section 4.2 unpacks the three curvature terms: favorable target curvature suppresses possible gain, training-curvature variation captures changes as parameters move, and example-Hessian differences capture the exchange. Section 4.3 then explains why a region-wide bound is needed: evaluating derivatives only at the anchor does not control every retrained endpoint. Section 5 states how sampling, numerical and training errors enter the final upper bound. These explanations make the transition from local prediction to a verified decision explicit, while preserving the existing technical structure and conclusions.

AuthorsOpenReview ↗

Follow-up for Reviewer BEUv

Dear Reviewer BEUv,

Thank you again for your careful review. Your question about why the three bounds certify different numbers of exchanges (4, 2, and 1) helped us clarify how much of that difference comes from the endpoint refinement.

We posted our response on November 13 and wanted to check in before the discussion closes. We would appreciate hearing whether our response addresses your concerns. If anything is still unclear, we would be happy to clarify it while the discussion is open.

Thank you for your time.

Best regards, The Authors

The detailed rebuttal partially addressed my concerns. Although I have low confidence in this paper, I am inclined to raise my score to weak acceptance.

AuthorsOpenReview ↗

Thank You for Your Feedback

Thank you for carefully reading our response and reconsidering your assessment of the paper. In the final version, we will further improve the exposition to make the role of each result and the connections between them clearer. We appreciate your time and suggestions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.