A Swiss Army Infinitesimal Jackknife

By Ryan Giordano, William T. Stephenson, Runjing Liu, Michael I. Jordan, Tamara Broderick. 2018

122 citations recorded by the source corpus.

The error or variability of machine learning algorithms is often assessed by repeatedly refitting a model with different weighted versions of the observed data. The ubiquitous tools of cross-validation (CV) and the bootstrap are examples of this technique. These methods are powerful in large part due to their model agnosticism but can be slow to run on modern, large data sets due to the need to repeatedly re-fit the model. In this work, we use a linear approximation to the dependence of the fitting procedure on the weights, producing results that can be faster than repeated re-fitting by an order of magnitude. This linear approximation is sometimes known as the “infinitesimal jackknife” in the statistics literature, where it is mostly used as a theoretical tool to prove asymptotic results. We provide explicit finite-sample error bounds for the infinitesimal jackknife in terms of a small number of simple, verifiable assumptions. Our results apply whether the weights and data are stochastic or deterministic, and so can be used as a tool for proving the accuracy of the infinitesimal jackknife on a wide variety of problems. As a corollary, we state mild regularity conditions under which our approximation consistently estimates true leave k-out cross-validation for any fixed k. These theoretical results, together with modern automatic differentiation software, support the application of the infinitesimal jackknife to a wide variety of practical problems in machine learning, providing a “Swiss Army infinitesimal jackknife.” We demonstrate the accuracy of our methods on a range of simulated and real datasets.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Mixed-Privacy Forgetting in Deep Networks (2020, methodology): “In the context of model interpretability and cross-validation, [27, 14] provided a hessian based method for estimating the influence of a training point on the model predictions.”
Uncertainty Estimation with Infinitesimal Jackknife, Its Distribution and Mean-Field Approximation (2020, methodology): “Recent studies have brought (renewed) interests in applying this methodology to machine learning problems [17, 25].”
Influence Functions in Deep Learning Are Fragile (2020, background): “Prior theoretical work [14, 15] have focused on quantifying the finite sample error-bounds for influence estimates when compared to the ground-truth re-training procedures.”
LQF: Linear Quadratic Fine-Tuning (2020, methodology): “We leave various applications of LQF to future work, including its use in (i) uncertainty quantification, (ii) backward compatibility [44], (iii) leave-one-out cross validation without a validation set [9], (iv) active/online learning [45], (v) counterfactual analysis in the first order, (vi) contin”
Approximate Data Deletion from Machine Learning Models: Algorithms and Evaluations (2020, methodology): “The influence function ap- proach (henceforth referred to as the influence method) uses the linear approximation to θ(w) about w = 1 to estimate θ\k. (Giordano et al., 2018; Koh and Liang, 2017) show that the linear approximation is given by θinf = θfull − [∇2θLfull(θfull)]−1∇θL\k(θfull).”
An Automatic Finite-Sample Robustness Metric: When Can Dropping a Little Data Make a Big Difference? (2020, methodology): “Giordano et al. (2019b) states conditions under which the ﬁrst-order Taylor series approximation to ˆ θ ( ~w ) is accurate—precisely when using the derivative as given in Eq.”
Forgetting Outside the Box: Scrubbing Deep Networks of Information Accessible from Input-Output Observations (2020, methodology): “[24,15] provide a newton based method for computing the influence of a training point on the model predictions in the context of model interpretation and cross-validation, however, such an approach can also be used for data removal.”
Fast Yet Effective Machine Unlearning (2021, background): “Estimating the effect of a data sample or a class of data samples on the deep model parameters is a challenging problem [17, 27, 28].”
On the Accuracy of Influence Functions for Measuring Group Effects (2019, methodology): “On the theoretical front, Giordano et al. (2019b) established ﬁnite-sample error bounds that apply to groups, e.g., showing that the leave-k -out approximation is consistent as the fraction of removed points α → 0 .”