Revisiting inverse Hessian vector products for calculating influence functions

We thank the reviewer for valuable feedback. We hope that the revised version can address the reviewer's concerns. Below we address each question separately.

1. "There's a lot of batch-SGD analyses which at first glance may already contain the theorem. For example: A) Jain, Kakade, Kidambi, Netrapalli, Sidford. "Parallelizing.." 2018 JMLR B) Varre, Pillaud-Vivien, Flammarion. "Last iterate convergnece.." 2021 NeurIPS C) Ma, Bassily, Belkin. "The power of Interpolation..." 2018 ICML Can you argue why your analysis is novel, comparing to existing literature like the above?"

Indeed, it is an oversight to our side, the analysis of linear regression in Ma, Bassily, Belkin is pretty much the same as ours. In the revised version, we moved Theorem 1 to the appendix as part of the proof of the Corollary (which is now called Theorem). We do so to focus more on the condition C.1 which is missing from the previous literature. In particular, Ma, Bassily, Belkin do not provide an expression for critical batch size that depends solely on Tr(H) and lambda_max(H). In addition, we provide a counter example that shows if the batch size condition is broken, the algorithm does not observe. In our counter example, H can be arbitrary and the condition C.1 is met. Ma, Bassily, Belkin provide a similar counter example but only for the case H = cI. The results in Jain, Kakade, Kidambi, Netrapalli, Sidford. Parallelizing.. and also Dieuleveut et al. Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression are slightly different, they allow a reduced learning rate compared to optimal step in the deterministic case $\eta = 1 / \lambda_{\max}$

2. "Can you show why the theorems apply to the setups in B3? Currently, this is `almost' done but not completely."

In the revised version, we make a precise statement in the main part of the text.

3. "Can you show empirically that C1 occurs, in the norm sense? (tracial vs norm-type behavior is rarely equivalent in random matrix contexts)."

We find it is rather difficult to evaluate the norm of $\tilde{H}_t^{2}$. We compute a relatively low-dimensional random projection ($d = 96$) of the difference of RHS and LHS for a small GPT2 model, results shown in Figure 5 in the revised version

4. "Figure 1 is appears to be discussed in the text (l368-370) and 3 cases are explained. Considering Figure 1, why are these the 3 cases, (especially, which illustrates case '3'? Where do you argue that 'PBO finetunning stirs away the model too far for the quadratic approximation to hold'. (and what does that mean?)"

Simply because the values of the influence are much larger than in rest of the pictures. The locality in "..quadratic approximation" depends on epsilon in formula (5), but we also cannot take it too small, since we can encounter problems with floating point.

5. "Figure 3. Why does the difference picture show what you claim it does? (In particular why do you average over the 10x10 square, and why are you not measuring the diagonals?). When you write (l464-466). ``As a result the influence similarity between an orignal sentence and a rewritten one appears to be consistently higher than between unrelated sentence." Can you explain this?"

Here, the diagonal (at positions [0, 10], [1, 11], ... etc) correspond to the similarity of a sentence and it's paraphrased version, while the off-diagonal elements correspond to similarity of completely unrelated sentences.

6. "Can you explain precisely how you picked the 'batch' in Table 1, and moreover, what is the general procedure you suggest for selecting LiSSA parameters? (It seems you almost do this, but being extra-clear would help, especially as regard the batch.)"

The batch is chosen based on Theorem 1's condition $|B| >= C Tr(H) / \lambda_{\max}(H)$; we take $C = 2$ conventionally. This requires evaluation trace and largest eigenvalue. Trace is rather trivial, through random gaussian quadratic form, we can even calculate the std which is shown in Table 1. Largest eigenvalue is more complicated. We use sketches (Swartworth and Woodruff), however the quality of the approximation depends on the dimension, and the $Tr(H^2)$. We select $d = 5000$ based on some evaluations in the appendix (lines 963-971) However, we do not have a rigorous way to evaluate error of estimation for lambda_max.

We thank the reviewer for minor corrections, we make the corresponding changes in the revised version.

We thank the reviewer for feedback. We address the question in the review below:

"Since this topic is about hyperparameter tuning, can we connect the proposed theory/results with iterative gradient-based optimization methods? More specifically, I know that for optimization algorithms like GD, its behavior will be influenced by the Hessian near equilibrium (i.e., the condition number of Hessian). So I am curious if this phenomenon is related to what is proposed in this paper."

This is an interesting point, thank you for bringing this to our attention. Perhaps you are referring to "edge of stability" https://arxiv.org/pdf/2103.00065 ? It seems it is not that straightforward to make the connection to our work, the optimisers that are used to train neural nets are more complicated than the plain SGD.

rt

We thank the reviewer for valuable feedback. Below we address some of the comments in the review

1. "The contribution is somewhat limited because the convergence analysis seems to be standard, and the algorithm is only for computing the influence function."

We point out that the convergence analysis is slightly tighter than in more general results who rely on a weaker bound on $\mathbf{E} || \tilde{H}_t ||^{2}$. The closest result to ours is the analysis in Ma, Bassily, Belkin Interpolation...:, who consider the linear regression case. Although they also address the question of critical batch size, they do not make a connection to $Tr(H)$, rather rely on a uniform bound on the feature norm (in our case it is equivalent to norm of the gradient). We also note that our counter example showing that batch size has to be sufficiently large, accounts for arbitrary $H$, unlike Ma, Bassily and Belkin who only consider $H = cI$. Naturally, this is thanks to our condition C.1. In the revised version we put more emphasis on explaining why we believe it is a reasonable assumption, and we also add additional validation experiment.

2. *"Some results in section 4 (Figure 1) seem to indicate that, in some situations, the influence function is not a good indicator of how the sensitive the optimal weights are with respect to newly added data points, as the LiSSA influence and PBRF influences are not correlated at all." *

We elaborate why this may happen in lines 385-388: either both influences are small, in which case they both approximate 0, or both influences are large, in which case the local Taylor approximation of PBO may not take place.

3. "The paper can be strengthened by reviewing more related work. E.g., are there other related algorithms for computing the influence function? Are there other variants of the influence function? Other work that analyze inverse Hessian-vector products (which are listed in the conclusion)? This can show the paper's position within the broader literature"

We added some relevant literature in the revised version.

4. "In section 5, the paper claims that the idea of inverse Hessian makes sense because small eigenvalues correspond to more specific and informative content. However, in traditional interpretation, small eigenvalues correspond to noise and carry little to no information. What is it not the case here? Moreover, are there references for the claim that large eigenvalues correspond to general language structure?"

Thank you for pointing this out. For better clarity, we change "small" to "remaining", that is not from the top of the spectrum.

Higher information is traditionally associated with something that is less likely to observe. We could think of top eigenvectors as something that is more likely to observe. We also make a comparison to popular TF-IDF index in lines 482-487, where more frequent words are weighted less, i.e. bearing less information.

Perhaps the following argument can also help the reviewer agree with us. The information may be interpreted as something that helps the model learning, especially given that we are talking about the distribution of the gradients. In the early deep learning work, such as Martens. Deep learning via Hessian-free optimization and Sutskever et al. On the importance of momentum and initialization, the authors argue that it is more efficient to train in low-curvature directions ("valley") where the gradients are more persistent along the training path.

"The Hutchinson estimation and randomized sketching are used to estimate Tr(H) and lambda_max. In the experiments, how many Hessian-vector products are needed to get a good estimation?"

For Hutchinson estimation, it is straighforward to evaluate std, which we give in Table 2. For evaluation of lambda_max with sketching we do not have a way to calculate std. The bound in Swartworth and Woodruff depends on Tr(H^2). Based on our evaluation of Tr(H^2), we suggest to take projection dimension 5000, see lines 968-971

5. "In Figure 3, lambda=5 is used, which seems to be large given that the GNH matrix in (7) is already SPSD. How does the results change using a smaller lambda?"

Typically the Hessian itself is nearly singular, for example, some analysis is available in Schioppa (2024) Gradient Sketches for Training Data Attribution and Studying the Loss Landscape. The value of lambda directly affects the speed of convergence, the lower the value $1 - \lambda\eta$, the better. We choose lambda = 5 so we can take a relatively adequate number of steps. Notice that the top eigenvalue is much larger than 5 (780 for OPT, Table 2).

We are grateful to the reviewer for elaborate comments and suggestions. Below we address each comment separately.

1. "The submission does not address the large optimization literature on stochastic gradient descent, which has derived many similar convergence guarantees. The rates are not typically written in terms of a linear + constant term, as this is not convergent, and the literature is typically concerned with decreasing step-sizes (see e.g. Bach and Moulines, 2013) or other schemes that can guarantee convergence. But the linear + constant result still appears regularly, for example see Theorem 2.1 in the work of Needell et al., 2015, Theorem 1 in the work of Dieuleveut et al., 2016, of Theorem 5.8 in the handbook of Garrigos and Gower. Given those results, the additional insights provided by the current submission appears small, but I might have missed a point that is specific to the inverse Hessian-product setting. If so, a discussion of existing literature in optimization and highlighting what makes the iHVP problem special would make the submission stronger."

Thank you for pointing this literature out. We find that general optimization results often are not sufficient for accurate analysis. In particular, among the papers that you have mentioned, only Theorem 1 considers a form of average in-batch smoothness, however, they require learning rate to be as small as $1/ Tr(H)$ which is much smaller. Our goal is to match the standard choice $\eta = 1/\lambda_{\max}(H)$ with just the right batch size. Tang et el (2020) that we were already citing requires a weaker condition, a bound on $\mathbf{E} || \tilde{H}_t ||^{2}$, which also would require reducing the learning rate. The closest to our work is Ma, Bassily, and Belkin The Power of Interpolation (2018) https://arxiv.org/pdf/1712.06559, in particular their proof of the linear regression case is indeed very close to ours. However, they do not have an equivalent of condition C.1, instead they require a uniform upper bound on the norm of features (equivalent to our gradients). For this reason, we decided to put more emphasis on the condition in the revised version. We also note that we also include a lower bound that adds more value compared to Ma, Bassily, and Belkin.

2. "The text uses the word "converges" loosely,"

Corrected, where possible. In some cases we have to use it loosely, such as in the experiment in Figure 2.

3. "The condition C.1 seems convenient but it isn't clear from the main text why it is introduced..."

We've put more emphasis on this condition in the main text, stating it as a lemma under some relatively weak distributional condition in classification case + incoherence condition in the language modelling case. We do not quite understand how we can compare to Zhang et al . They compare Hessian with covariance of the gradient. While we compare Hessian with average squared-batched-Hessian. I believe the confusion comes from the fact that the model in Zhang et al does not include the linear part, which would typically be associated with gradients.

4. "The text "confirms the inverse scaling with batch size". ... adding evidence for the scaling would strengthen the claim."

We note that the scaling with trace is confirmed by considering different models with different traces in Figure 4. To strengthen this argument, we added comparison of projected LHS and RHS as matrices of dimension 96 x 96. This is rather expensive experiment and we only consider a small GPT2 model, which incidentally corresponds to the dependent sampling case.

5. "Re: "Koh and Liang (2017) proposed ..."

Corrected, thank you

6. "Description such as "Basu et al. (2020) criticize the LiSSA [algorithm], suggesting that it lacks convergence for deep networks" and "we carefully analyze the convergence of the Lissa [algorithm]" should be made more specific..."

Thank you for pointing this out. Indeed, it sounds vague and we made it more specific in the revised version.

7. "The sentence "SGD is known to work at least as well ... should be removed."

Indeed, this paper is not relevant. We removed this sentence from the revised version.

8. "The equality in Eq. (3) should be replaced by an as it is the result from a truncated Taylor expansion"

This is equality for the derivative, which is taken at epsilon = 0

9. "L27-28, "interpret the internal computations in an understandable to a human way"

Added "of neural networks"

10. "I do not recall Martens making this argument, and it is not clear what is meant by "low-noise distribution".

Thank you for this comment. We changed the reference to Kunstner et al. Limitations of the empirical fisher approximation for natural gradient descent; we also changed "low-noise" to "realizable", the term they use in Section 4.2. By low-noise we mean a model that converged to $p(y|x) \approx 1$ on the training data, which is better described as realizable.

Thank you for clarifying your concern further. We agree with the reviewer that it is important to explicitly state that the algorithm does not really converge with a constant learning rate.

Our observation is that in practice the sampling error appears to be not as important. In case of large models, where $\eta$ is already small, the corresponding sampling error can be negligible. Although technically the algorithm does not converge, it can provide sufficient approximation.

We do agree with the reviewer that our choice of hyper parameters should be stated as heuristic.

Below we suggest the following evaluations for some models we mention in the paper:

Here, $u_T$ is computed according to the hyperparmeters in Table 1, and we evaluate $\hat{u}^{*}$ by running LiSSA with a 2x smaller learning rate, a 4x larger batch size, and a 4x larger T. Sampling error is evaluated proportionally to $g^T$ $\hat{u}$.

Upon reviewing the sampling error, we found a mistake. In Theorem 1, the term $\eta^2 \frac{Tr(H)}{|B|} g^T(H + \lambda)^{-1} g$ has to be replaced with $\frac{\eta Tr(H)}{\lambda |B|} g^T(H + \lambda)^{-1} g$. The proof stands the same, we only forgot to multiply the error term $\| \tilde{\Delta}\|^{2}$ by $\delta^{-1}$ when applying Lemma 2 at the end of the proof of Theorem 1.

We will make the corresponding changes in case we get the chance to update the submission. To make the distinction between "convergence" and "approximation", e.g. replacing "we find that the batch size has to be sufficiently large for LiSSA to converge" will be replaced with "we find that the batch size must be sufficiently large for reliable approximation of iHVP" in the abstract; furthermore, we will emphasise this difference in the passage directly after Theorem 1, perhaps including the evaluations above.

Regarding the optimality of the choice of learning rate, we want to emphasize the paper does not actually that it is optimal, we refer to the previous work for this choice. We agree that in order to avoid misleading the reader, we should make it explicit that this choice is not necessarily optimal and other choices might work as well.

Regarding the reference to Ma, Bassily, Belkin, we will remove the part about critical batch size. Indeed, their definition of critical batch size is different. However, there is similarity. In our result, we show that batch size |B| >= m^{*} is sufficient for learning in $O(\lambda_{\max} / \lambda)$ steps. If we double the batch size, the sampling error decreases, but we can no longer proportionally increase the learning rate. Therefore, we still need to conduct the same number of steps due to the convergence error. This example corresponds to their "saturation" regime.

Thanks a lot you for your efforts and valuable feedback, we really appreciate it.