- 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
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.
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.
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.