acceptodds
Under review as a conference paper at ICLR 2027

Certified Data Attribution After Model Reselection

Abstract

Data deletion can change the configuration selected by validation as well as its fitted parameters. We study attribution to the resulting retrain-and-reselect procedure over a finite menu of strongly convex learners. A selected output can be certified without identifying the winning configuration. We characterize the feasible attribution set under interval information with deterministic ties and derive its minimax absolute-error radius. Residual regions and validation-conditioned prediction bounds give an adaptive procedure whose refinement bound depends on disagreement among near-optimal candidates. A three-observation ridge construction has a nonzero deletion effect and an output-certification cost independent of an arbitrarily small validation gap under a shared damped-Newton schedule. Full Newton steps remove this separation, showing that refinement granularity matters. Across 4,800 classification queries, reselection occurs in 12.3–19.1% of queries by setting. Output stopping saves no refinements at a joint signed-logit tolerance. A complete probability-output sweep yields 1.5–12.4% fewer refinements than equally certified winner identification for individual targets, with substantially smaller gains for simultaneous outputs. Additional conditioning contributes little and does not improve measured latency. The results characterize when the output, tolerance, and solver permit computational savings.

Primary area:
interpretability and explainable AI
Keywords:
training data attribution, model reselection, certified attribution, influence functions, hyperparameter selection, data deletion, convex optimization, adaptive refinement

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_8h8kOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies retraining and reselection after data are removed from the training set. In particular, such a process may include different levels of choices: 1. parameter changes, such as different gradients in training. 2. configuration changes, such as due to different validation results. The paper's key observation is that you may early stop if you observe that the final range of candidates is narrow and drop the ones that cannot win. The range is predicted through gradient descent, and the curvature bound is assumed, assuming the objective is convex.

Critical strengths

The setting is interesting, and the observation could be useful for saving training time.

Critical weaknesses

The paper is very hard to follow without an LLM's help. The goal of each section is very hard to follow. The authors should add an overview of the goal for each section. The terms should be defined or explained, like "menu", "race," and "rectangular". There is no explanation of what theorems 2, 4, and 5 are trying to achieve. The theorems are very hard to parse. The experiment section is also very unstructured and hard to read. The answers to the proposed three questions at the beginning are very hard to find.

Questions for authors

See weakness.

2 comments
AuthorsOpenReview ↗

Clarifying the problem, terminology, and theorem roles

Thank you for identifying the exposition problems. We explain the main idea and theorem roles below, then specify the planned changes.

  1. The problem. The training procedure selects among fitted configurations using validation data. Deleting a training group can change both the fitted parameters and the selected configuration. We seek the change in the selected prediction after repeating that procedure. Refitting only the old winner can answer a different question. Proposition 1 and the fixed-exact baseline isolate this from approximation error.

  2. Terminology and assumptions. A “menu” is a finite ordered list of configurations, such as 19 regularization strengths. A “race” refines candidate fits and eliminates candidates proved unable to win. It is not a stochastic competition. “Rectangular” means using separate scalar intervals for validation scores and outputs, without their joint dependence through the same parameter. Conditioning uses that dependence by requiring a winning candidate's validation loss to be below the best available upper bound.

Damped Newton supplies iterates, not predicted future trajectories. The certificate uses the actual retained-data gradient and a known strong-convexity lower bound. Strong convexity, not convexity alone, is required for the residual region. The intervals are deterministic optimization enclosures, not statistical confidence intervals. The float64 implementation is evaluated numerically, not formally verified.

  1. What Theorems 2, 4, and 5 answer. Theorem 2 characterizes attributions compatible with the current intervals. It handles deterministic ties and combines the outputs of all possible winners. The midpoint's worst-case error is half the combined interval's width. The minimax claim concerns independent interval information, not unrestricted dataset access.

For example, two candidates can have overlapping score intervals but output intervals [0.49,0.51][0.49,0.51] and [0.50,0.52][0.50,0.52]. With known zero baseline, the selected attribution is in [0.49,0.52][0.49,0.52] regardless of the winner. Tolerance 0.02 is satisfied. If the second output interval were [0.90,0.92][0.90,0.92], it would not be. Thus identity and output uncertainty differ.

Theorem 4 proves safety during refinement and elimination. With valid input bounds, the true winner remains and every returned interval contains the target. A bound conditional on winning need only retain the actual winner's output. An unresolved computation returns no point estimate. This proves safety, not finite termination in every tie case.

Theorem 5 bounds refinement work. Under the stated synchronous schedule and shrinking score/output intervals, the bound depends on prediction disagreement among near-optimal candidates. Agreement can make score separation unnecessary. Disagreement beyond the tolerance requires more information. The contraction assumption belongs to this work bound, not the safety theorem.

  1. Answers to the three experimental questions. Does reselection matter? In this study, winners change in 12.3–19.1% of queries by setting. On switched queries, exact refitting of the old winner has only 55.7–64.8% mean sign accuracy.

Does output stopping save refinements? Sometimes. It saves none on 4,800 stringent joint-logit queries. The probability study gives 1.49–12.36% scalar savings and 0–2.60% joint savings against an equally certified winner race. These depend on tolerance and target count.

Do those savings lower query time? Rectangular stopping gives modest scalar pooled-time savings of 1.9–4.9%. Conditioning is slower overall. Point estimates at matched work are already accurate. Certification justifies stopping rather than improving the observed point estimate.

  1. Planned changes and the soundness concern. We will add a roadmap: Section 2 defines the counterfactual, Section 3 constructs its interval, Section 4 gives the algorithm and conditional work bound, Section 5 answers the three questions above, and Section 6 explains prior work and scope. The revision will define terms before use, precede theorems with their purpose, and bring the probability frontier and ridge full-step control into the main text.

Established regions and selection guarantees remain credited to Suzuki et al. (2014), Xiang et al. (2017), and Wilson et al. (2020). We will also distinguish predictive-model reselection from tuning an attribution estimator, as studied by Wang et al. [1].

Could you identify the assumption, equation, or proof underlying the significant soundness concern? The written weaknesses identify presentation problems, which we accept, but no specific mathematical defect. We would appreciate a specific objection, or reconsideration of the soundness assessment in light of these clarifications.

[1] Wang et al., “Taming Hyperparameter Sensitivity in Data Attribution,” NeurIPS 2025.

AuthorsOpenReview ↗

Revision: definitions, theorem explanations, and experimental structure

Thank you for identifying the exposition problems. The revision, marked in blue, adds definitions, a section roadmap, theorem explanations, three main-text figures, and experimental headings that answer the motivating questions.

  1. State the problem and define the terminology. The training procedure fits several configurations, selects one using validation data, and reports its prediction. Deleting observations can change both the fitted parameters and the configuration selected. The attribution is the prediction change after repeating this complete procedure. Exactly refitting only the old winner can therefore answer a different question.

Section 1 now defines a “menu” as a fixed, ordered list of configurations, such as regularization strengths. Section 3 defines “rectangular” information as separate intervals for validation scores and outputs, without their joint dependence through the fitted parameter. Section 4 defines a “race” as repeated refinement and certified exclusion of candidates that cannot win.

Section 4 also clarifies that the algorithm does not predict future gradients. Newton supplies successive parameter iterates. The certificate uses the actual retained-data gradient and a known strong-convexity bound. The resulting intervals describe optimization uncertainty, not statistical confidence about a population.

  1. Explain what Theorems 2, 4, and 5 are trying to achieve. Theorem 2 answers: which selected attributions are still possible? It combines the outputs of candidates that can win, respecting the specified tie order. Under the stated independent interval information, the best worst-case absolute-error radius is half the width of the resulting hull.

Figure 1 and the two-candidate example make this concrete. Suppose validation intervals overlap, while output intervals are 0.49,0.510.49,0.51 and 0.50,0.520.50,0.52. With a known zero baseline, the selected attribution lies in 0.49,0.520.49,0.52. Its midpoint has error at most 0.015, so tolerance 0.02 is met without knowing which model wins. Changing the second output interval to 0.90,0.920.90,0.92 prevents that conclusion. Output agreement can therefore determine termination before score separation.

Theorem 4 answers: does refinement preserve correctness? With valid input bounds, the true selected candidate is never removed, and every returned interval contains the target. Every returned point estimate meets the requested tolerance. A bound conditional on winning need only retain the actual winner's output. Unresolved cases retain an enclosure without an unjustified point estimate.

Theorem 5 answers: how much refinement is sufficient? Under its stated synchronous schedule and shrinking interval widths, the bound depends on prediction disagreement among near-optimal candidates. If their predictions already agree sufficiently, separating their validation scores is unnecessary. The theorem explicitly separates this work guarantee from the safety statement.

  1. Organize the experiments around the questions. Section 5 now uses the following result headings.

“Does reselection change attribution?” Winners change in 12.3–19.1% of queries by setting. On switched queries, exact refitting of the old winner gives 55.7–64.8% mean sign accuracy. This isolates a change in the attribution target from ordinary approximation error.

“When does output stopping save refinements?” Figure 3 and Table 2 show 1.49–12.36% fewer scalar refinements in the probability study, versus 0–2.60% for joint outputs. The 4,800 stringent joint-logit queries retain their zero additional savings. This comparison holds the certificate tolerance and candidate-pruning procedure fixed.

“Do fewer refinements reduce query time?” Rectangular stopping takes 95.1–98.1% of the winner race's pooled time for scalar queries. Conditioning is slower, so the revision identifies rectangular stopping as the practical default for these workloads. Figure 2 places the full-Newton control beside Proposition 6 and makes its solver dependence visible.

  1. Make the section purposes and contribution easy to locate. The introduction now explains the progression: Section 2 defines the counterfactual, Section 3 constructs its enclosure, Section 4 establishes correctness and refinement bounds, Section 5 answers the empirical questions, and Section 6 distinguishes the contribution from prior work. Table 3 identifies the established ingredients from Suzuki, Xiang, Wilson, and Jamieson–Talwalkar beside the present results.

These changes address the presentation issues while preserving the mathematics and data. We would appreciate reassessment of the revised version. If a specific assumption, equation, or proof motivates the significant soundness concern, please identify it so that we can respond precisely. The written weaknesses currently concern exposition rather than a specified mathematical defect.

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

The paper studies data attribution when deleting training observations can change both fitted parameters and the configuration selected by validation. It constructs deterministic intervals for the resulting selected output over a finite menu of strongly convex learners. The proposed switch-aware attribution procedure can stop when the output is sufficiently resolved, even if the validation winner has not been identified.

Critical strengths
  1. Certifying a selected output without necessarily identifying the selected configuration is an interesting distinction.
  2. The paper reports negative and limited results explicitly, including cases with no additional refinement saving and increased latency from conditioning.
Critical weaknesses
  1. The presentation should be substantially improved. There are no figures in the main paper, despite the geometric construction and the extensive experimental discussion. Figures 1 and 2 appear only on page 30, and the refinement-saving frontier is Figure 3 on page 36. It is recommended to move the most informative results into the main text. A simple diagram showing the residual ball, the validation halfspace, and the prediction interval would make Section 3 much easier to understand.

  2. The new contribution should be separated more clearly from established ingredients. The paper acknowledges that the shifted residual ball, validation pruning, and dome-support formula are inherited. The rectangular interval characterization is useful but relatively elementary. The authors should explain more directly which theoretical or algorithmic result provides a substantial advance beyond combining these ingredients for a selected-output target.

  3. The numerical results do not establish a strong practical advantage for the additional stopping and conditioning machinery. At the joint 10^-3 signed-logit tolerance, all 4,800 queries use the same refinement counts as winner identification. In Table 2, scalar savings range from 1.49% to 12.36%, while joint savings range from 0% to 2.60%. The conditioning variant takes 105.3-109.2% of the winner race's pooled time. These results are reported honestly, but they leave the practical case unresolved. Please identify a realistic workload where the proposed method provides a meaningful end-to-end benefit over the simpler rectangular or winner-required alternatives.

Questions for authors
  1. When should a practitioner choose conditioning over the simpler rectangular stopping rule, given the measured latency increase?
  2. Can the method provide a substantial runtime gain under an efficient solver on a larger external dataset?
  3. Can the main theoretical construction and the tolerance-versus-work results be illustrated in the main paper?
2 comments
AuthorsOpenReview ↗

Exposition, inherited ingredients, and practical guidance

Thank you for recognizing the selected-output distinction. We agree that its explanation and practical limits need greater prominence.

  1. Main-text figures and organization. We will move the probability frontier and finite-data separation into the main text, retaining unfavorable controls. The frontier must show individual and joint targets, not only the favorable scalar curve. The ridge figure must show full Newton alongside half steps. A geometric schematic will distinguish the residual ball, validation halfspace, and projected output interval.

For a running example, let both validation intervals be [0.20,0.21][0.20,0.21], so either candidate can win. With a known zero baseline and output intervals [0.49,0.51][0.49,0.51] and [0.50,0.52][0.50,0.52], the selected attribution lies in [0.49,0.52][0.49,0.52]. The midpoint error is at most 0.015, satisfying tolerance 0.02 without model identification. Replacing the second output interval by [0.90,0.92][0.90,0.92] prevents that conclusion. If both validation scores are exactly equal, the prescribed tie rule resolves identity. This is an interval illustration, not a new experiment.

We will introduce this example and the terms “menu,” “race,” and “rectangular” before the formal statements.

  1. Which result goes beyond inherited ingredients? The residual region and validation pruning are due to Suzuki et al. (2014). The dome formula is credited to Xiang et al. (2017). Wilson et al. (2020) already establish deterministic approximate-CV guarantees. Neither reusing those formulas nor taking an interval hull alone constitutes a substantial advance.

The contribution connects three questions. Theorem 2 specifies possible selected outputs and the best worst-case accuracy justified by independent interval information. Theorem 4 shows that refinement remains safe with deterministic ties and bounds conditional on winning. Theorem 5 relates work to prediction disagreement among near-optimal candidates, not only the validation gap. Proposition 6 realizes the distinction with finite-data residual certificates and a nonzero deletion effect, under an explicitly specified solver schedule.

These distinguish information, correctness, and work, without claiming universal acceleration. We will move the result-level comparison from Appendix M.1 into the main text. Recent stagewise-attribution work [1] studies influence changes during learning. Our narrower question concerns the selected output after deletion and validation-based reselection. We claim no improvement over its neural attribution results.

  1. When should conditioning be chosen? For the measured workloads, rectangular stopping is preferable when elapsed time is the objective. Table 21 gives scalar pooled-time ratios of 0.951–0.981 versus winner identification, whereas conditioning takes 1.053–1.092. There is no evidence for recommending the dome calculation as a faster default.

Its mathematical benefit is endpoint tightening when the validation halfspace cuts off the output extremum of the ball. For a nondegenerate upper endpoint, the output/validation-gradient cosine must exceed the normalized halfspace threshold in Appendix M.6. This is testable, but tightening matters computationally only if it avoids enough later work. Table 20 shows why geometric activity is insufficient: another output can govern the maximum width, or one Newton step can cross both stopping thresholds. A policy predicting when conditioning pays for itself remains unvalidated.

  1. Practical value and efficient solvers. Table 2 gives 1.49–12.36% scalar refinement savings over an equally certified winner race, versus 0–2.60% for joint outputs. At tolerance 0.01, the intervals report 75.8% of effect signs and 65.4% of intervention orders, with no incorrect assertions against the numerical reference under the stated allowance. These are computational decisions on the evaluated data, not population confidence guarantees.

Certification does not improve point-estimation accuracy at matched work. Proposition 6 does not establish savings with full Newton: that control removes the separation. The 20,000-record simulation also gives no additional output-stopping savings at that size. Thus the current evidence does not substantiate a substantial runtime gain on a larger external dataset.

The practical conclusion is: a user requiring justified accuracy or a sign decision can stop according to output uncertainty, with rectangular bounds as the measured low-overhead choice. A user satisfied with a point estimate may prefer a few Newton refinements. Small validation gaps alone do not justify extra computation. We will make this guidance explicit and retain the negative findings in the abstract, main figures, and conclusions.

[1] Lee et al., “Influence Dynamics and Stagewise Data Attribution,” ICLR 2026.

AuthorsOpenReview ↗

Revision: main-text figures, contribution map, and practical guidance

Thank you for recognizing the selected-output distinction. Your presentation suggestions have been implemented, with revised prose in blue. The theorem statements and results are preserved.

  1. Bring the geometry and informative results into the main paper. The main text now contains three figures. Figure 1 shows the residual ball, the validation halfspace implied by winning, and projection onto the queried output. Its second panel illustrates sufficiently precise attribution with unresolved winner identity. Figure 2 places the finite-data separation beside Proposition 6, including the full-Newton control. Figure 3 presents the probability-tolerance frontier, retaining both individual-target and joint-target curves.

We also define “menu,” “race,” and “rectangular” at first use, add a section roadmap, and explain the purpose of Theorems 2, 4, and 5 before stating them. Section 5 now answers its three experimental questions through explicit result headings. The problem, guarantee, and measured benefit now follow a common explanatory route.

  1. Separate the contribution from established ingredients. Table 3 is now in the main text. It credits Suzuki et al. for parameter regions and validation pruning, Xiang et al. for dome support, Wilson et al. for approximate-CV guarantees, and Jamieson and Talwalkar for candidate identification.

The selected-output analysis links three results. Theorem 2 determines which attributions remain possible and what accuracy is justified by independent interval information, with exact tie handling. Theorem 4 preserves this guarantee as information is refined and conditioned on winning. Theorem 5 identifies prediction disagreement among near-optimal candidates as the quantity controlling output-resolution work. Proposition 6 realizes the distinction through actual finite-data residual regions and a nonzero deletion effect. This identifies the contribution at the result level.

  1. When should a practitioner choose conditioning? Section 5 now gives the direct recommendation: rectangular stopping is the practical default for the measured workloads. Table 21 reports scalar pooled-time ratios of 0.951–0.981 relative to equally certified winner identification. Conditioning takes 1.053–1.092, so its added endpoint precision does not offset its evaluation cost here.

Conditioning remains an optional way to tighten a valid certificate. Appendix M.6 states the geometric condition: for a nondegenerate upper endpoint, the output/validation-gradient cosine must exceed the normalized halfspace threshold. Table 20 distinguishes this endpoint activity from avoided refinements. Another output may control the maximum width, or one solver step may cross both stopping thresholds. Accordingly, the revision separates three decisions: pruning candidates, stopping on output accuracy, and paying for additional conditioning.

  1. What useful workload does output stopping address? Figure 3 and Table 2 evaluate a specified task: certifying changes in individual true-label probabilities after data deletion. At tolerance 0.01, scalar output stopping saves 7.00% of refinements. At 0.05, it saves 12.36%. Requiring all 16 outputs simultaneously gives 0.33% and 2.60%, respectively. All cases, including zero-gain cases, are retained.

The intervals also support decisions. At tolerance 0.01, they resolve 75.8% of effect signs and 65.4% of intervention orders, with no incorrect assertion against the numerical reference under the stated allowance. These are reporting rates on the evaluated data. A sign or order is asserted only when the intervals justify it. This connects requested accuracy to an actionable attribution output, rather than treating refinement count as the sole objective.

  1. Efficient solvers, larger data, and point estimation. The main-text Figure 2 shows exactly how solver granularity enters: full Newton resolves both ridge candidates in one step each. Proposition 6 compares stopping rules under its specified schedule. Theorem 4 applies to any backend providing valid bounds, and Theorem 5 states the additional assumptions for its work guarantee.

The 20,000-record study is a controlled sample-size experiment at 65 parameters. Its results, including equal adaptive refinement counts at that size, remain in the paper. The revision also brings the repeated-step comparison into Section 5: two rounds leave 2.8% observed point failures at probability tolerance 10−310^{-3}, while three leave none. Their certification rates are 78.8% and 95.1%. These estimates share the refinement schedule, rather than representing an independently timed point-only solver.

The practical guidance is to use the output certificate for justified per-intervention accuracy, signs, or orders, with rectangular stopping as the measured lower-overhead choice. The main-text figures and comparison table make the supporting evidence easy to assess.

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

This paper studies data attribution when deleting training examples can change not only the fitted parameters but also the model configuration selected by validation. The authors propose Switch-Aware Attribution (SWA), which is for certifying post-deletion prediction changes without necessarily identifying the exact validation winner. The main theorems establish valid attribution intervals, a minimax characterization under interval information, and refinement bounds depending on the prediction disagreement among near-optimal candidates.

Critical strengths

This manuscript address a meaningful limitation of conventional data attribution. Fixing the original model configuration can produce misleading attribution estimates when data deletion changes the validation winner. Then, Proposition 1 and the experiments provide useful evidence for this distinction.

The theoretical formulation is clear. In particular, Theorem 2, 4, 5 provide a principle way to certify selected outputs without requiring exact winner identification. Moreover, the connection between near-optimal prediction disagreement and refinement complexity is an interesting perspective.

3 experiments include matched certified baselines, different output tolerances, and complete-query runtime measurements. I appreciate that the authors explicitly report negative results and acknowledge the limitations of their proposed method.

Critical weaknesses

My primary concern is that the central motivation of SWA is to avoid unnecessary computation by certifying outputs before identifying the winning model. However, the results in Section 5 provide rather limited evidence that this advantage is practically significant. SWA shows no refinement savings over winner-required stopping at ε=10−3\varepsilon=10^{-3}, while the dense-menu ablation saves only 6 out of 58,086 refinements. Even in Table 2, individual-output savings remain modest (1.49--12.36%) and drop to 0--2.60% when certifying all 16 outputs jointly. Although the theoretical motivation is interesting, these results suggest that output certification is rarely substantially cheaper than winner identification in practice. Stronger evidence is needed to demonstrate when the proposed approach provides meaningful computational benefits.

The additional winner-conditioned prediction bounds provide only modest refinement savings. Eg., at ε=0.01\varepsilon=0.01, conditioning improves refinement counts by just 0.73% over rectangular stopping. More importantly, the complete-query timing study reports that conditional stopping takes 105.3--109.2% of the winner-required runtime for individual probability outputs. Hence, the additional geometric conditioning appears to increase computational overhead rather than improve overall efficiency in the evaluated settings.

In Prop. 6, the separation between output certification and winner identification is demonstrated under a specific damped-Newton schedule. But with full Newton steps, both methods require the same number of refinements. So I think this suggest that the claim about computational separation may be sensitive to the optimization procedure rather than being a broadly useful algorithmic advantage.

Several central components of the proposed method are inherited from well-established results, for example: residual-based parameter regions, validation-based candidate elimination, ball-halfspace, deterministic guarantees for approximate model assessment and selection... [1,2]. Though the authors appropriately acknowledge these connections, the new contribution lies primarily in combining these ingredients for selected-output attribution and deriving the corresponding stopping and complexity results. Thereby I believe the method is incremental rather than bringing a novel idea.

Further, The experiments mainly involve small classification datasets, regularized logistic regression, and convex heads on frozen features. And that, the larger study is a controlled simulation rather than an external-data benchmark. So it remains unclear whether the proposed framework can offer meaningful benefits for larger models or more computationally demanding attribution problems.

[1] Zhen James Xiang, Yun Wang, and Peter J. Ramadge. 2017. Screening Tests for Lasso Problems. IEEE Trans. Pattern Anal. Mach. Intell. 39, 5 (May 2017), 1008–1027.

[2] Wilson, A., Kasy, M., Mackey, L.. (2020). Approximate Cross-validation: Guarantees for Model Assessment and Selection. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:4530-4540.

Questions for authors

Can the authors identify the empirical conditions under which SWA is substantially more efficient?

Given that conditional bounds often increase total runtime, what practical advantage do they provide over the simpler rectangular stopping method?

How much of the proposed benefit remains under alternative optimization schedules or stronger solvers? Is there a broader class of realistic optimization problems where output certification remains substantially cheaper than winner identification?

Can the authors provide a comparison with an independently optimized point-estimation baseline, including total runtime and error distributions?

3 comments
AuthorsOpenReview ↗

Selected-output guarantees, empirical regimes, and comparators

Thank you for the careful assessment. The relevant comparator is an equally certified winner race, not uniform refitting.

  1. What is the theoretical contribution? The question is whether the selected output is accurate enough before its model is identified. Theorem 2 identifies the feasible attribution set under independent score, output, and baseline intervals, with deterministic ties. Its minimax claim is information-relative, not a dataset-access lower bound. Theorem 4 preserves containment under refinement and winner-conditional information. Theorem 5 gives diam⁡(IG(k))≤ω(2Bqk)+2Aqk+d0\operatorname{diam}(I_G^{(k)})\le\omega(2Bq^k)+2Aq^k+d_0, where ω(t)\omega(t) is the output spread among candidates within tt of optimal validation loss. Here AqkAq^k and BqkBq^k bound output and score widths, and d0d_0 is baseline width. This identifies when score separation is unnecessary, a question winner-identification guarantees alone do not answer.

We do not claim the shifted ball, dome formula, or candidate elimination. Suzuki et al. (2014), Xiang et al. (2017), and Wilson et al. (2020) establish those foundations and approximate-CV guarantees. Our target is a specified deletion's selected output, rather than a cross-validation assessment functional. Recent work on attribution hyperparameters [1] tunes the attribution estimator. Here, the reselected hyperparameter belongs to the predictive learner. We will move the result-level comparison in Appendix M.1 into the main text.

  1. When does output stopping help? The favorable combination is ambiguous validation ranking, close queried predictions, and enough remaining refinement work to avoid. The measured benefit is restricted.

Table 2 includes all prescribed cases. At probability tolerance 0.01, scalar stopping saves 7.00% of refinements and helps 881/4,608 case/menu/target combinations. At 0.05, it saves 12.36% and helps 1,487/4,608. Jointly certifying all 16 outputs reduces savings to 0.33% and 2.60%. The combinations are not independent deletions. At 0.05, split-level scalar savings range from 2.10% to 26.29%. These are not uniform gains.

The stringent joint-logit result remains negative: small score gaps alone do not ensure savings.

  1. Should a practitioner pay for conditioning? For the measured workloads, no. Rectangular stopping is the better default. Conditioning gives valid tighter bounds under the premise that a candidate wins, but saves only 0.73% additional refinements at tolerance 0.01 and increases pooled elapsed time. Table 21 reports 105.3–109.2% of winner-required time for individual outputs, versus 95.1–98.1% without conditioning. There is no demonstrated wall-clock advantage from the dome calculation.

Table 20 explains why tightening need not help: another coordinate can determine stopping, or a discrete solver step can resolve both stopping criteria together. Conditioning would be worth using only when avoided refinement costs outweigh its overhead. We have not validated a deployment policy making that choice.

  1. Alternative solvers and larger problems. Proposition 6 depends on its half-Newton schedule, as you note. Full Newton removes it, and that control is reported. Safety accepts any backend supplying valid bounds, but the work theorem requires the stated synchronous schedule and contraction envelopes. We have not established a general efficiency advantage under optimized Newton, quasi-Newton, or first-order solvers.

The larger study has 20,000 simulated observations and 65 parameters, not a large external-data benchmark. At that size the adaptive variants again have identical refinement counts. We do not claim that sample-size scaling establishes practical superiority.

  1. Independently optimized point estimation. Tables 17–18 provide more than a one-step comparison, but not the complete comparison you request. At matched refinements, the point estimator meets every tested probability tolerance and usually has smaller median error than the certified midpoint. Three rounds have no observed failures at joint probability tolerance 10−310^{-3}, while 95.1% of cases are certified. The point comparator shares the certificate-driven elimination schedule and is not independently tuned or timed. Its standalone runtime advantage remains unmeasured.

Recent TRAK analysis [2] also distinguishes ranking from magnitude accuracy. It does not resolve our missing runtime comparison. Our supported contribution is a computable, tolerance-dependent stopping certificate and a characterization of its limits, not empirical dominance over optimized point estimation. This distinction matters when the requested output is a per-intervention accuracy or sign guarantee rather than a useful ranking alone.

[1] Wang et al., “Taming Hyperparameter Sensitivity in Data Attribution,” NeurIPS 2025.

[2] Tong et al., “Imperfect Influence, Preserved Rankings: A Theory of TRAK for Data Attribution,” arXiv:2602.01312, 2026.

AuthorsOpenReview ↗

Revision: selected-output guarantees, empirical regimes, and baseline scope

Thank you for the detailed assessment. We have addressed your questions through targeted changes, marked in blue. Figures 1–3 and Table 3 now present the geometry, empirical comparisons, and prior-work distinctions in the main text.

  1. What remains new after established screening and selection results? Table 3, moved into Section 6, separates the inherited tools from the contribution. Suzuki et al. (2014) provide suboptimal-model regions and validation exclusion. Xiang et al. provide the dome support formula. Wilson et al. (2020) give deterministic approximate-CV assessment and selection guarantees. Jamieson and Talwalkar (2016) study non-stochastic candidate identification.

Our results concern a different stopping objective: the output of the specified retrain-and-reselect procedure. Theorem 2 characterizes feasible attributions and their minimax radius under independent interval information. Theorem 4 guarantees containment while candidates are refined and information is conditioned on winning. Theorem 5 gives diam⁡(IG(k))≤ω(2Bqk)+2Aqk+d0\operatorname{diam}(I_G^{(k)})\le\omega(2Bq^k)+2Aq^k+d_0, where ω\omega measures prediction disagreement among near-optimal candidates, AqkAq^k and BqkBq^k bound output and score widths, and d0d_0 is baseline uncertainty. The revised explanations distinguish identification, correctness, and work. Together, these results characterize selected-output attribution.

  1. Which conditions favor output stopping? Section 4.1 now states the conditions directly: validation ranking remains ambiguous, the queried predictions agree at the requested precision, and refinement has work left to avoid. Figure 3 makes the target-count and tolerance dependence visible.

At probability tolerance 0.01, scalar stopping saves 7.00% of refinements and helps 881/4,608 case/menu/target combinations. At 0.05, it saves 12.36% and helps 1,487/4,608. Jointly certifying all 16 outputs gives 0.33% and 2.60% savings. All prescribed cases are included, and repeated targets are not treated as independent deletions. The original zero-gain joint-logit result is retained. Together, these comparisons identify an output-specific operating regime rather than attributing candidate-pruning savings to the new stopping rule.

  1. What is the practical advantage of conditioning? The revision distinguishes optional conditioning from output stopping. For the measured workloads, rectangular stopping is the practical default: scalar pooled time is 95.1–98.1% of winner-required time, compared with 105.3–109.2% for conditioning (Table 21). Conditioning supplies tighter valid endpoints, but its additional cost exceeds the refinements it saves in these timings.

The distinction is explained geometrically in Figure 1 and empirically in Table 20. A tightened endpoint saves work only when it changes the stopping decision. Another output can still determine the hull width, or one Newton step can cross both thresholds. This gives a concrete implementation choice while retaining the conditional certificate as an optional refinement.

  1. What survives stronger solvers and larger problems? Figure 2 now shows the full-Newton control beside Proposition 6. The three-observation construction establishes a finite-data separation under the stated shared half-step schedule, with nonzero attribution. A full step per candidate removes that separation. Safety requires valid bounds and is independent of this choice, while the work theorem states its schedule and width assumptions explicitly.

Section 3.1 clarifies that the theorem is not restricted to the experimental sample sizes or dimensions. The empirical scope is also explicit: public classification tasks, frozen-feature convex heads, and a controlled study up to 20,000 observations. The latter measures sample-size scaling at 65 parameters and retains the equality of adaptive refinement counts at its largest size. It is a simulation, not an external-data benchmark.

  1. Comparison with an independently optimized point estimator. The revision now explains Tables 17–18 in the main text. Repeated-refinement point estimates share the certifying method's schedule. They meet all evaluated stopping tolerances and often have lower median error than the interval midpoint. At joint probability tolerance 10−310^{-3}, three rounds have no observed failures, while 95.1% of cases are certified.

This is a matched-work comparison, not independent optimization and timing of a standalone point-only method. We identify that distinction explicitly. Its purpose is to isolate what the certificate adds: a stopping decision justified by each query's available bounds. At tolerance 0.01, the resulting intervals also resolve 75.8% of signs and 65.4% of intervention orders, with no incorrect assertions against the numerical reference under the stated allowance (Table 16). The revised paper connects the theorem to these concrete attribution decisions.

Reviewer_nR6LOpenReview ↗

Response to rebuttal

Dear authors,

I appreciate the effort you put into the rebuttal, clearer explanation, and revision. However, I still find the theoretical advance incremental, and the benchmarks show only modest computational gains in the settings evaluated. My concerns about both the theoretical and empirical contributions thereby remain, and I will keep my original rating.

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

This paper studies certified data attribution when deleting a training subset GG changes not just the fitted parameters on D∖GD \setminus G, but also which model wins on a validation set out of KK strongly convex candidates. The proposed method (SWA) warm-starts from an influence step and uses strong-convexity residual balls and ball–halfspace ("dome") cuts to prune candidates and bound the output change within ±ε\pm \varepsilon.

Critical strengths
  1. Formulating data attribution across model reselection is well-motivated. When the validation winner switches (12%–19% of queries here), standard fixed-model attribution—even retraining the original winner to convergence—barely beats random guessing on sign accuracy.
  2. The math is clean, and the authors are commendably honest in reporting negative ablation results rather than burying them.
Critical weaknesses
  • The huge reduction in Newton steps comes entirely from standard validation-bound pruning (Suzuki et al., 2014). The paper's two main algorithmic novelties—stopping early when candidate outputs agree, and tightening intervals via winner-conditioned dome cuts—do almost nothing in practice. On all 4,800 main joint-logit queries, SWA, rectangular bounds, and simply racing until one winner remains take the exact same number of Newton steps (saving 0 steps; and only 6 out of 58k steps on the dense grid in Table 10). Worse, the extra overhead of dome cuts makes SWA 5%–13% slower in wall-clock time than just racing to a single winner (Table 21).
  1. The separation between output stopping and winner identification in Proposition 6 is contrived: it relies on a 2D ridge problem where the Newton step is artificially damped by 1/21/2, whereas a single full Newton step solves ridge regression exactly. With full Newton steps converging quadratically (O(log⁡log⁡(1/δ))O(\log\log(1/\delta))), closing a tiny validation gap δ\delta only takes 1–2 extra steps anyway, which explains why early output stopping rarely helps.
  2. Because the residual ball radius scales as ∥rh∥/(2λh)\|r_h\|/(2\lambda_h), the method is restricted to small strongly convex problems (p≤65,n≤1078p \le 65, n \le 1078) and blows up when λh\lambda_h is small.
Questions for authors
  1. In Table 21, dome conditioning is consistently slower in wall-clock time than both rectangular bounds and winner-required racing (Rect. ms < Winner ms < Cond. ms). Is there any realistic regime where dome conditioning gives a net wall-clock speedup?
  2. On the λh\lambda_h grid down to 10−610^{-6}, the 1/(2λh)1/(2\lambda_h) factor inflates the initial ball radius by 5×1055 \times 10^5. How much of SWA's runtime is spent purely shrinking tiny-λh\lambda_h balls before they can be pruned, and how does total runtime compare to just running 2–3 uncertified Newton steps (Table 18)?
2 comments
AuthorsOpenReview ↗

Contribution, conditioning costs, weak regularization

Thank you for recognizing the motivation and mathematical care. We agree that fewer refinements and lower runtime are different claims. The paper should not be assessed as a generally faster alternative to certified model selection.

We will lead with this distinction and a main-text illustration.

  1. What remains beyond standard pruning? The 63.0–72.9% reduction against uniform refinement comes from established candidate elimination, not our output rule. The zero additional savings on 4,800 joint-logit queries and six saved refinements on the dense grid are stated in Section 5. These gains are not a new screening contribution.

The contribution concerns what must be resolved after a deletion. Theorem 2 characterizes possible selected outputs, with exact ties, and gives the minimax radius under independent interval information. Theorem 4 makes the certificate valid throughout refinement. Theorem 5 relates work to prediction disagreement among near-optimal candidates, rather than requiring their identities to be distinguished. Suzuki et al. (2014) supply the parameter regions and validation exclusion. Wilson et al. (2020) already give deterministic approximate-CV assessment and selection guarantees. Our additional target is the output of the stipulated retrain-and-reselect procedure, not the invention of guaranteed selection.

  1. Does conditioning improve wall-clock time? Not in the tested workloads. Table 21 gives scalar pooled-time ratios of 1.053–1.092 for conditioning versus winner identification, while rectangular output stopping gives 0.951–0.981. We therefore recommend rectangular stopping for these workloads. Conditioning is optional, not necessary for the selected-output certificate. Its added endpoint precision does not justify its cost here.

The probability study does identify a limited output-stopping benefit: 7.00% fewer scalar refinements at tolerance 0.01 and 12.36% at 0.05, including all cases. The corresponding joint-output savings are only 0.33% and 2.60%. These are refinement results, not matching runtime gains. The useful finding is precisely that target count and requested precision determine whether winner identification is avoidable.

  1. Is the ridge separation artificial? It is a controlled separation between specified procedures, not a lower bound against an optimized ridge solver. Proposition 6 explicitly includes the full-Newton control: one step per candidate resolves both tasks. The half-step construction establishes that the distinction is realizable using a finite training sample and the actual residual bounds, with nonzero attribution. It does not recommend damping a quadratic problem. We will emphasize this limitation beside the statement and move the full-step comparison into a main-text figure. Theorem 5 is conditional on interval contraction, and the safety theorem does not assume that contraction. Quadratic convergence does not supply a uniform one- or two-step guarantee across objectives and initializations, although it can erase the advantage, as our control shows.

  2. Small regularization and scale. Your concern about ρh=∣rh∣/(2λh)\rho_h=|r_h|/(2\lambda_h) is justified. A small regularizer can make this global-curvature certificate expensive. The multiplier 5×1055\times10^5 at λ=10−6\lambda=10^{-6} is not itself a measured radius, since the residual also changes, but it exposes genuine conservatism.

For this response, we reaggregated the stored joint-probability traces at ε=10−3\varepsilon=10^{-3}. Across 144 case/menu combinations with grid [10−6,1][10^{-6},1], 4,164 of 4,489 refinements concern λ<10−3\lambda<10^{-3}. The counts are identical for conditional, rectangular, and winner-required races. This locates much of the shared work in weakly regularized candidates. It does not identify the fraction of runtime caused specifically by loose balls: candidate-level timers were not recorded, and optimization difficulty is confounded with certificate conservatism.

The theorems impose no p≤65p\le65 or n≤1078n\le1078 restriction. Those describe the external-data experiments. The 20,000-observation simulation does not establish high-dimensional or external-data effectiveness.

  1. Why not stop after two or three Newton rounds? Table 18 supports that competitor. At probability tolerance 10−310^{-3}, two rounds leave 2.8% observed point failures, whereas three leave none. Certification rates are 78.8% and 95.1%, respectively. These trajectories share our elimination schedule, so they are not an independently optimized, independently timed point-only baseline. We cannot infer that runtime comparison from Table 21. The distinction is a per-query stopping justification, not superior measured point accuracy. Recent TRAK theory likewise separates ranking preservation from magnitude approximation [1].

[1] Tong et al. (2026), “Imperfect Influence, Preserved Rankings: A Theory of TRAK for Data Attribution,” arXiv:2602.01312.

AuthorsOpenReview ↗

Revision: contribution, solver dependence, and weak regularization

Thank you for recognizing the motivation and mathematical care. We have revised the paper directly around your concerns. Changes are blue. Figures 1–3 and Table 3 now make the method, solver comparison, empirical tradeoffs, and contribution visible in the main text.

  1. What is new beyond validation-bound pruning? Section 5 now makes the equally certified winner race the principal comparator for output stopping. The 63.0–72.9% saving over uniform refinement remains attributed to established candidate elimination. The zero additional savings on 4,800 stringent joint-logit queries and six saved dense-grid refinements remain reported.

The new result concerns the quantity that must be resolved. Theorem 2 characterizes the selected-attribution set and its minimax radius under independent interval information, including exact ties. Theorem 4 preserves correctness under refinement and winner-conditional bounds. Theorem 5 connects work to prediction disagreement among near-optimal candidates. Table 3 distinguishes this contribution from Suzuki et al.'s validation pruning, Xiang et al.'s dome formula, and Wilson et al.'s approximate-CV guarantees. This gives an output-specific stopping guarantee even when model identity remains unresolved.

  1. Does conditioning justify its elapsed-time cost? The practical recommendation is now explicit in Sections 4–5: use rectangular output stopping for the measured workloads. Conditioning is optional. Table 21 reports rectangular scalar-query time at 95.1–98.1% of equally certified winner-identification time, with initialization, certificate evaluation, pruning, and refinement included. Conditioning takes 105.3–109.2%, so tighter endpoints alone do not justify its overhead here.

The output rule itself has a measurable benefit. Table 2 and the main-text Figure 3 show 7.00% fewer scalar refinements at probability tolerance 0.01 and 12.36% at 0.05, including all prescribed cases. Joint-output savings are 0.33% and 2.60%. The revision separates these work counts from the timing results rather than presenting them as the same speedup.

  1. Why include the damped ridge construction? Section 4.2 now places Figure 2 beside Proposition 6, showing half-step and full-step Newton together. The proposition holds initialization, score bounds, and refinement schedule fixed, then changes only whether termination requires the winner's identity. It realizes this distinction with actual finite-data residual regions and a nonzero deletion effect. Full Newton resolves both tasks in one step per candidate, as stated in the proposition and shown in the figure.

Thus the example identifies the interaction between output agreement and refinement granularity. It is not a recommendation to damp ridge regression. Theorem 4's safety holds for any backend supplying valid bounds. Theorem 5 separately states the synchronous schedule and contraction assumptions needed for its work bound. These roles are now explained before the results.

  1. Weak regularization, the residual radius, and scale. Section 5 and Appendix M.6 now quantify where refinement work occurs. For 144 joint-probability cases with grids spanning 10−6,110^{-6},1 and tolerance 10−310^{-3}, candidates with λ<10−3\lambda<10^{-3} receive 4,164 of 4,489 refinements. Of these, 3,862 concern eventual losers. All three adaptive variants have identical counts. This reaggregation uses the existing trajectories.

At λ=10−6\lambda=10^{-6}, the radius is 5×105∣r∣5\times10^5|r|, rather than a fixed 5×1055\times10^5. The revision distinguishes candidate-level work from complete-query timing. Per-candidate timers were not recorded, so the counts cannot be interpreted as a runtime fraction caused by loose bounds. Section 3.1 now states that validity requires strong convexity, not p≤65p\le65 or n≤1078n\le1078. The 20,000-record experiment is identified as a controlled sample-size study.

  1. How does this compare with two or three Newton rounds? Section 5 now brings Table 18's iterative comparison into the main discussion. At joint probability tolerance 10−310^{-3}, two rounds leave 2.8% observed point failures and certify 78.8% of cases. Three rounds have no observed point failures and certify 95.1%. The shared schedule isolates empirical accuracy from a query-specific stopping guarantee. Table 21 times certified races, not a separately tuned point-only implementation.

The certificate answers whether the requested accuracy is justified for this deletion before consulting the reference retraining result. The revision now distinguishes that benefit from both ranking quality and fixed-budget point accuracy. We hope these specific changes support reassessment of the contribution and presentation.

Comments on the paper

4 comments
Area_Chair_DGqiOpenReview ↗

From AC.

Dear Authors,

Given the deadline on 18 November, please submit your responses to the reviews to facilitate a productive discussion with the reviewers.

Thanks, AC

Authors: your current responses are very hard to read. It would be helpful if you were able to answer questions from the reviewers directly, each time saying which exact question you are answering (stating it without substantial paraphrases) and leading with the question number as used by the reviewer.

Thank you for the feedback and patience. We will revise these shortly.

We thank all four reviewers and the Area Chair for their careful assessments. We appreciate the recognition in several reviews of the problem’s motivation and mathematical formulation. The feedback has guided a focused revision, with changes marked in blue. With the cutoff approaching, we summarize the principal changes and results below.

Reviewers tVyY and nR6L, and contribution and computational value. The paper certifies the prediction change after retraining and model reselection over a finite menu of strongly convex learners. The requested accuracy can be reached before the winning model is identified. The revised Table 3 distinguishes this contribution from established residual bounds, validation pruning, and screening geometry.

Theorem 2 characterizes feasible selected attributions and their minimax error under independent interval information, including exact ties. Theorem 4 preserves validity as candidates and bounds are refined. Under its stated schedule and contraction assumptions, Theorem 5 relates refinement work to prediction disagreement among near-optimal candidates. Together, these results give a query-specific justification for stopping once the requested output accuracy is reached.

Table 2 and Figure 3 show how the benefit depends on the requested tolerance and number of outputs. For conditional output stopping relative to equally certified winner identification:

Probability toleranceScalar refinements savedJoint 16-output refinements saved
0.00011.49%0.00%
0.0012.99%0.00%
0.017.00%0.33%
0.0512.36%2.60%

These comparisons hold the tolerance and candidate-elimination procedure fixed. They identify the favorable regime: the queried predictions agree at the requested precision while the validation ranking remains unresolved. The original zero-gain joint-logit results remain alongside this tolerance study.

Complete-query timings provide a separate implementation recommendation. Rectangular scalar-output stopping takes 95.1–98.1% of winner-identification time in the measured workloads (Table 21). Sections 4–5 therefore recommend rectangular stopping as the lower-overhead choice, with conditioning available as an optional way to tighten the certificate.

We have also made the supporting comparisons explicit:

  • Solver dependence. Figure 2 now places Proposition 6’s finite-data construction beside its full-Newton control. The comparison shows how refinement granularity affects the opportunity to stop early. Theorem 4’s correctness guarantee applies to any backend supplying valid bounds.
  • Point estimation. Section 5 brings the repeated-refinement comparison into the main discussion. At joint probability tolerance 0.001, two rounds leave 2.8% observed point failures and certify 78.8% of cases. Three rounds have no observed point failures and certify 95.1% (Table 18). These methods share the refinement schedule, allowing readers to distinguish observed accuracy from a computable stopping guarantee.
  • Weak regularization. Additional analysis of existing trajectories locates 4,164 of 4,489 refinements in candidates with regularization below 0.001, for the specified 144-case/menu subset. Section 5 and Appendix M.6 identify where refinement work occurs and distinguish these counts from query timing.

Reviewers wKi3 and 8h8km, and exposition and presentation. We have defined “menu,” “race,” and “rectangular” at first use, added a section roadmap, and explained the purpose of Theorems 2, 4, and 5 before their statements. Figures 1–3 now bring the certificate geometry, finite-data comparison, and probability-tolerance results into the main text. Table 3 makes the relationship to prior work explicit.

Section 5 now directly answers the three experimental questions: whether reselection changes attribution, when output stopping saves refinements, and whether those savings reduce query time. The revision also connects the intervals to attribution decisions. At probability tolerance 0.01, they resolve 75.8% of effect signs and 65.4% of intervention orders, with no incorrect assertions against the numerical reference under the stated allowance (Table 16).

We appreciate the reviewers’ suggestions, which have helped us present the contribution and its practical implications more clearly. The revised paper explains how to certify attribution for a learning procedure that includes model selection, and when the requested prediction change can be resolved before model identity. We hope the revision and detailed responses provide a clear basis for a favorable reassessment, and we welcome any remaining questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.