cs.LGOct 30, 2025

Cross-Epoch Bias in SGD-based Leave-One-Out Influence: Analysis and Accumulative Correction

Authors: Yunxiao Shi, Shuo Yang, Yixin Su, Rui Zhang, Min Xu

Organizations: University of Technology Sydney Sydney, NSW, Australia · Wuhan, Hubei, China

Abstract

Training-data influence estimates support data selection and cleansing by predicting the effects of removing individual examples. The standard multi-epoch SGD-Influence Estimator (SGD-IE) aggregates contributions from a sample's repeated appearances along the recorded trajectory. When used to approximate finite deletion, it omits an interaction: later removals act on the parameter displacement accumulated from earlier removals. We introduce the Accumulative SGD-Influence Estimator (ACC-SGD-IE) to account for how earlier removals change the effect of removing the same sample again. It uses the sample's Hessian at subsequent appearances to correct the estimated parameter change. Our non-convex analysis shows that this correction removes SGD-IE's additional interaction contribution from the finite-horizon error bound: the omitted interaction produces a local error linear in the accumulated parameter change, while the remaining Taylor remainder is bounded quadratically under Lipschitz-Hessian assumptions. The bounds characterize how training propagates the remaining error. In non-convex experiments across clean and noisy tabular, text, and vision datasets, ACC-SGD-IE reduces validation-loss-change RMSE by 10.8% and improves Jaccard@10% by 15.2% on average relative to SGD-IE. These gains also translate into lower test misclassification rates after data cleansing on MNIST and CIFAR10 at the evaluated removal budgets. On noisy industrial datasets, it reduces aggregate parameter RMS error with a mean relative reduction of 53.4%. We further discuss computational tradeoffs, provide complementary theoretical analysis and experimental evaluation for strongly convex objectives, and explore potential extensions of the accumulative correction mechanism to other influence estimators.

Figures & tables

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Dec 9, 2023

Generalized Influence Functions for Better Model Change Estimates

Influence functions (IFs) approximate the effect of removing or reweighting training data on a trained model, but their linear approximation often lacks the accuracy required for reliable post hoc model editing. We identify two culprits and propose generalized influence functions (GIFs) and pseudo-LiSSA (p-LiSSA) to address each in turn. First, classical IFs update all parameters indiscriminately, leading to unnecessary updates to data-irrelevant parameters. GIFs instead restrict edits to a data-relevant subspace and leave the remaining parameters fixed. We theoretically show that GIFs achieve a tighter error bound than classical IFs when the parameter subset is properly selected, and that effective subspace selection requires avoiding low-curvature directions while retaining a sufficiently large component of the target gradient. Second, LiSSA iterations are destabilized by negative Hessian eigenvalues, which existing methods handle via ℓ2\ell_2 damping, at the cost of a biased inverse-Hessian-vector product (iHVP) estimate. p-LiSSA eliminates this bias by solving the restricted inverse-Hessian problem without such damping. We further show that the presence of low-curvature directions slows p-LiSSA convergence, and that the data-relevant subspace selected by GIFs mitigates this. Across five image and text unlearning benchmarks, GIFs update only 10% of the parameters yet preserve accuracy up to 2.12 percentage points better than IF-based baselines, while improving unlearning performance by up to 2.73 percentage points. Moreover, p-LiSSA improves restricted iHVP estimation by reducing the residual by 9.6×\times over existing iHVP baselines, while using 19.8% less memory with comparable computation time. Code is available at https://github.com/hslyu/GIF.
May 4, 2026

Robust and Fast Training via Per-Sample Clipping

We propose a robust gradient estimator based on per-sample gradient clipping and analyze its properties both theoretically and empirically. We show that the resulting method, per-sample clipped SGD (PS-Clip-SGD), achieves optimal in-expectation convergence rates for non-convex optimization problems under heavy-tailed gradient noise. Moreover, we establish high-probability convergence guarantees that match the in-expectation rates up to polylogarithmic factors in the failure probability. We complement our theoretical results with multiple numerical experiments. In particular, we demonstrate that PS-Clip-SGD outperforms both vanilla SGD with momentum and standard gradient clipping when training AlexNet on the CIFAR-100 dataset, even after accounting for the additional computational time caused by per-sample clipping. We also empirically show that, in the presence of gradient accumulation, applying clipping at the mini-batch level can improve training performance while incurring virtually no additional computational cost. This finding is particularly interesting, as it contradicts the common practice of applying clipping only after all accumulation steps have been completed.
May 19, 2026

Increasing Missingness to Reduce Bias: Richardson-SGD with Missing Data

Stochastic gradient methods are central to modern large-scale learning, but their use with incomplete covariates remains delicate since imputation schemes generally introduce systematic gradient biases, as shown for linear models. In this work, we prove that all parametric models exhibit similar gradient bias for various imputation procedures and characterize exactly the dependence on the missingness ratio vector pp, with O(∥p∥)O(\|p\|) as the leading term. We exploit this analysis to propose a simple debiasing procedure for stochastic gradient descent (SGD) with missing values based on Richardson extrapolation, which leverages the exact expression of the gradient bias. The key idea is to deliberately add missingness: from an already incomplete observation, we generate a further-thinned version at a higher, controlled missingness level, and combine the two resulting stochastic gradients to cancel the leading bias term. We prove that one Richardson step reduces the gradient bias from O(∥p∥)O(\|p\|) to O(∥p∥2)O(\|p\|^2) under several missingness scenarios. Our proposed method is computationally efficient, model-agnostic and applies to any parametric loss whose stochastic gradient can be computed after imputation. Furthermore, when missing indicators are independent, the population gradient bias is a multilinear polynomial in pp and depends only on population gradient errors induced by declaring a single coordinate missing. In this case, our method generalizes to a multi-step Richardson procedure which recursively cancels higher-order terms. Empirically, Richardson debiasing improves optimization and estimation across several generalized linear models and combines positively with widely used imputation procedures such as MICE. These results suggest that, somewhat counter-intuitively, adding controlled missingness on top of existing missing data can make stochastic learning from incomplete data more accurate.