acceptodds
Under review as a conference paper at ICLR 2027

The Rank Cost of Forgetting: When One Deletion Requires a High-Rank Update

Abstract

Removing a record from a training dataset leaves the fitted model unchanged. Machine unlearning seeks to remove its influence without repeating the full training procedure. When the model parameter is a matrix, a low-rank update is compact, but can it reproduce the change caused by retraining? We answer this question in regularized bilinear regression. A rank-one deletion gradient can produce a retraining correction that low-rank updates cannot approximate to an arbitrarily small relative error. For independent Gaussian feature pairs, when the sample size is proportional to the number of matrix entries and regularization is fixed and positive, we derive an exact asymptotic formula for the minimum relative squared prediction error, uniformly over all positive ranks. For a nonzero deletion effect, every nonzero rank growing more slowly than the matrix dimension leaves the same positive asymptotic error, even if an oracle knows the exact retrained model. Any fixed relative tolerance below this threshold requires a rank proportional to the matrix dimension. This is a relative error, so it can persist while the absolute deletion effect becomes small. We also identify Hessians that preserve rank and give computable approximation bounds to distinguish an insufficient rank from an inaccurate numerical solution. Experiments on frozen text representations show improved agreement with retraining at higher update ranks, including binary decisions after regularization is selected for validation accuracy. On one real-data instance, a verified bound excludes every rank-one correction at a stated absolute prediction tolerance, while an explicit rank-eight update meets it.

Primary area:
learning theory
Keywords:
machine unlearning, low-rank approximation, random matrix theory, high-dimensional statistics, LoRA

Reviews

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

The paper considers the setting where samples from the training set are deleted and a new parameter is trained. Under this setting, the paper asks the question of what's the rank of the difference between the previous parameter and the new parameter. The paper assumes Gaussian data in a bilinear model, considers a regularized MSE, and derives asymptotic bound when d2/n→∞d^2 / n \rightarrow \infty. The paper accompanies the result with experiments on Gaussian data and some transformer settings.

Critical strengths
  1. It seems that the problem considered by the paper is fairly new.
  2. Based on the theoretical result, the author provided a prescription to choose the rank.
  3. The paper has results on transformer setup.
Critical weaknesses
  1. The theoretical setup is fairly simple. It assumes Gaussian inputs, linear model, and response with roughly no structure that depend on the input.
  2. Bounds are derived in asymptotic style, leaving out a functional form τ\tau that is hard to interpret.
  3. From a significance perspective, the problem of "how to correct the parameter under deletion" would be more complicated than an expressivity perspective. Current analysis only reviews a bound that says "larger rank recovers better". However, in practice more questions such as optimization difficulty should be considered. Therefore, I think the prescription provided has limited significance, especially given that there is no experimental results supporting the effectiveness of the prescription.
  4. Concerns about the paper's soundness is present. In Section 5. the definitions of mm and m2m_2 are unclear, with the only info "We now compare the correction’s component along U with its total squared norm. Their limits will be denoted by mm and m2m_2." This is insufficient since it is unclear what "their" is referring to. Given this ambiguous definition, the paper immediately claimed "These quantities are expressed through the mean-one Marchenko–Pastur law" with no justification. The same issue lies in the rest of Section 5 from Eq. (9) to Eq. (12). In Section 5.1, the paper claims The theorem below describes the normalized squared singular values of the remaining correction block through the aspect-one Marchenko–Pastur law μ1:=MP1\mu_1 := \text{MP}_1", but no theorem is given in Section 5.1 and MP1\text{MP}_1 is never defined explicitly. The following two sentences "In contrast, νγ\nu_{\gamma} describes eigenvalues of the feature covariance. The law μ1\mu_1 has support [0,4]." are also unclear and not justified sufficiently. There are more locations in the paper that has similar issues. I urge the authors to double check that claims are supported with sufficient evidence. Without a satisfying response addressing all the soundness issues (not limited to the examples I pointed out above), I will likely not raise my score.
  5. It seems unclear how the derived result predicts the transformer's experiment.
  6. Writings are unclear in many locations, for instance: a). WDW_D and WRW_R need to be explicitly defined. Right now they are only associated with ambiguous notions of "full and retained objectives". b). Statement of Proposition 1, "the right-hand side is ...". It is unclear what is "the right-hand side" from the equation above, which contains two eqaulties. c). Eq. (5), the notations rg(B)\text{rg}(B) is not defined.
  7. I also suggest the author to explicitly say which theorem is proved in which appendix section.
Questions for authors

Section 4 relies heavily on the separability of the Hessian. What does it mean for the objective considered?

From a high-level perspective, how does the Hessian-based analysis help the derived asymptotic bound?

2 comments
AuthorsOpenReview ↗

Response to Reviewer zrhX

W1–W2. What assumptions does the theorem use, and what does it give for the error at each rank?

Assumption 1 uses pairs of independent standard Gaussian feature vectors and a deletion chosen independently of the sample. It also requires d2/nd^2/n to tend to a finite positive constant, so the number of examples and the number of parameters grow in proportion. With positive regularization held fixed, Theorem 2 gives the limiting error curve χτ(r/d)\chi\tau(r/d) uniformly over all positive ranks. Equations (13)–(14) give τ\tau explicitly. For example, when d2/nd^2/n tends to 1 and regularization is 0.5, any positive rank that grows more slowly than dd leaves 25% of the squared prediction change in the limit. We can then use the same curve to choose a rank for a smaller error. For a target of 5%, the required rank is about 39% of full rank.

The theorem allows responses that depend on the features. Indeed, for a single deletion, the response enters the correction through a scalar residual, which cancels from the relative error whenever the correction is nonzero.

W3. Is there experimental evidence for rank selection?

Section 8.1 and Appendix K.4 compare the rank suggested by the limiting formula with the smallest rank that meets the tolerance. The rank suggested by the formula missed 22 of 1,350 targets, while the numerical bounds identified the smallest sufficient rank for every target. Thus, the formula supplies a starting rank and the bounds can then check it for a particular fit.

W4. What do mm, m2m_2 and the two spectral distributions describe?

Let MM be the result of applying the inverse Hessian to the unit gradient direction UU. The quantity mm is the limit of ⟨M,U⟩\langle M,U\rangle, the component along UU. The quantity m2m_2 is the limit of ∥MF∥2\lVert M_{F}\rVert^2, the squared size of the whole matrix. Appendix G.1 derives both limits from the covariance eigenvalue distribution νγ\nu_\gamma and concentration in the independent direction UU (Eqs. (G.5)–(G.6)).

Together, these limits give m2−m2m_2-m^2 as the limiting squared size of the component orthogonal to UU. To obtain the error curve, we then need to know how that size is spread across singular values. Appendix G shows that the normalized squared singular values of the remaining block follow μ1\mu_1 in the limit, with density (4−t)/t/(2π)\sqrt{(4-t)/t}/(2\pi) on (0,4)(0,4). Hence, we integrate tt against μ1\mu_1 below the cutoff to find the fraction of the block's squared mass left at a given rank.

W6–W7. Can we clarify the notation and give more direct references to the proofs?

We will define WDW_D and WRW_R as the minimizers of Eq. (2) over the full and retained index sets, respectively. We will also write out the grouped-deletion form of Eq. (4) and use rank⁡(B)\operatorname{rank}(B) in Eq. (5). We will add the density next to Eq. (13) and point from Theorem 2 directly to its proof in Appendix G (Theorem S3).

Q1–Q2. What does Hessian separability mean here, and how does the Hessian enter the proof?

Separability means that the full retained Hessian, including regularization, acts by multiplying the update on the left and right. If HR[A]=PAQH_R[A]=PAQ, then its inverse sends xz⊤xz^\top to P−1xz⊤Q−1P^{-1}xz^\top Q^{-1}, which still has rank one. In the Gaussian model, however, the Hessian can mix these directions. The proof therefore studies what happens when its inverse acts on the deleted example's gradient. This gives the part of the correction that a low-rank update misses.

W5. How does the theorem relate to the experiments with transformer features?

In the text experiments, we keep the transformer features fixed and refit the head after deletion. In §N.6, we compare Frobenius errors with the Gaussian curve to see how the weight approximation changes with rank on these features. The formula itself applies under Assumption 1.

To test whether a similar effect appears when the features can change, we also trained a small nonlinear network on handwritten digits. We then refit all weights after each deletion, starting from the original model. Across four settings with 40 random deletions each, the mean error left by the best rank-one update ranged from 32% to 50% of the squared change in the hidden-layer weights. At rank eight, it fell to between 2% and 8%. The comparison is therefore with the weight change from a local refit.

We hope these clarifications address your concerns about the theorem's regime, the explicit error formula, and the evidence for rank selection. In light of the results already in the submitted paper, we ask you to reconsider your score of 1.

I have read the rebuttal. However, I don't think the rebuttal clearly respond to the weaknesses pointed out in my review. ICLR allows an updated version of the paper to be submitted, but I don't see revisions of the paper that addresses my concern. Therefore, I choose to maintain the score I give.

Reviewer_XTPVOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks how well a low-rank update can reproduce exact retraining after deleting one training point. The model is ridge-regularized bilinear regression and the paper measures the error of the best rank-r matrix. The authors present a few findings: 1. If the curvature acts on rows and columns separately, the retraining change stays rank one and a low-rank update is exact (when low rank is sufficient). 2. The retraining change splits into two parts: a) a part along the deleted example’s gradient, which a rank-one update can capture; b) a spread-out, noise-like part that holds a fixed share of the change. Any update whose rank is small compared with the matrix size misses that whole share. This holds even if the update is computed with full knowledge of the retrained model. Recovering more of it requires a rank that is a fixed fraction of the matrix size. 3. One deletion’s effect shrinks as the training set grows, so the missed share can be negligible in absolute terms. Simulation experiments closely match the theorem, and a softmax head on image features shows similar trends.

Critical strengths
  1. The paper asks how close the best possible low-rank update can get to retraining, so its limits apply however the update is computed. It also handles a subtle point correctly: it keeps the loss normalization fixed after deletion, so a change in the effective regularization is not mistaken for a rank effect.

  2. The main result appears correct, and its proof is a real contribution: proofs have no critical errors, the formulas and quoted numbers reproduce. The proof does not rely on the common simplifying assumption that the curvature is randomly rotated; it uses a careful conditioning argument instead.

Critical weaknesses
  1. The main claim is about relative error, and the absolute effect is tiny. The theorem says a low-rank update always misses a fixed share of the retraining change. But the whole change from deleting one example shrinks as the training set grows, so the missed part is a share of something very small. The paper's own experiments show this too, and the example that makes the effect look large (Section L) does so by measuring the combined distribution of many noisy responses, a choice that scales the effect back up. Besides, the missed share is large only in a narrow setting, and the paper does not make this clear. The share is substantial only when the number of training examples is close to the number of parameters and regularization is weak. In that setting it is roughly 25-50%. With more data, stronger regularization, or far more parameters than examples (which in general holds for over-parameterized neural nets), it becomes small.

  2. The setting is not how low-rank unlearning is used in practice. The comparison is with retraining the full weight matrix. When a model is fine-tuned with LoRA, the retrained model is itself a low-rank change to the same base. The authors acknowledge this, but it does not mean it is fair. The theory assumes Gaussian, independent feature pairs, a squared loss, and a deleted example chosen without regard to the data. This excludes outliers and unusual examples, which are often the ones people want to unlearn and remove.

  3. The experiments are small and do not show that the effect matters. The real-data models are tiny bilinear heads (16- or 32-dimensional), with the training size chosen to match the theory. The theory also does not predict the real-data numbers. Real sentence pairs are strongly related to each other, so the error measure the theory uses understates the actual prediction error of the rank-one update. On predictions, simple fitted updates beat the update the theory calls optimal.

  4. The method contributions have limited practical value. The proposed rank-selection procedure needs the exact retraining change before it can choose a rank, which for this model defeats the purpose. The calibrated version needs about 30 independent datasets from the same distribution. No method is given for computing a good low-rank update without retraining.

Questions for authors

Please see weaknesses. With realistic tolerances and tuned regularization, how often does a single deletion actually need more than a rank-one update? Does the result still hold in three cases: when the deleted example is chosen because it is unusual (an outlier or high-influence point), when the two feature vectors are related as in real sentence pairs, and when several examples are deleted together? Can a low-rank update with a guaranteed error be computed without first computing the full retraining change?

2 comments
AuthorsOpenReview ↗

Response to Reviewer XTPV

Q1. With tuned regularization and an absolute tolerance, how often does a single deletion need more than rank one?

In the Gaussian fit in Table 1, even the best rank-one update missed a tolerance of 1% of the response standard deviation on 204 of the 1,037 deletions that needed an update. Among those 204 deletions, the median minimum rank was six. When we increase the tolerance to 2%, however, rank one suffices for every deletion that still needs an update. Thus, the answer can change considerably even for the same fitted model.

We agree that a large relative error can come from a small deletion effect. Appendix L shows how the absolute effect shrinks as the dataset grows when the deleted residual stays bounded in probability. Its noisy-response example concerns several observed responses together. The submitted QQP experiment checks a fixed tolerance on prediction scores directly. For one deletion on 2,000 evaluation pairs, interval arithmetic verifies that every rank-one update exceeds the 0.001 RMS tolerance, while a specific rank-eight update meets it (§8.2 and Appendix N.8).

We then checked whether rank affects decisions. In a separate experiment with regularization selected on validation data, moving from rank one to rank eight reduced disagreements with retraining from 135 to 30 on QQP and from 212 to 64 on PAWS, out of 300,000 comparisons per corpus (Table 4).

Q2(a). What happens when the deleted example is unusual?

In the Gaussian fit, the most influential 1% of deletions changed predictions about four times as much as the median deletion. Yet their average relative rank-one error remained close to the overall average (34.1% and 34.3%). Similarly, in the Fashion-MNIST experiment, deleting a deliberately mislabelled pair had a median effect 2.2–2.6 times that of deleting a clean pair. The exact deletion equation still applies to these selected examples. For the limiting theorem, however, we assume that the example is chosen independently of the data.

Q2(b). Does the effect persist when the two feature vectors are related?

In eight simulations with coordinatewise correlation 0.9 and unequal feature variances, we measured prediction error under the joint distribution of the two vectors. The numerical lower bound on the best rank-one error averaged 13.7% of the squared prediction change. A rank-eight candidate missed 7.7% on the same runs.

Truncated SVD gives the best rank-rr approximation to the weight change in Frobenius norm. Under Eq. (6), it also gives the best approximation to the change in predictions. Equation (21), however, measures prediction error on the evaluation pairs, where the features can be related. A fitted update can therefore beat truncated SVD on that measure. Appendix N.6 compares the original pairs with shuffled pairs and Gaussian controls.

Q2(c). What happens when several examples are deleted together?

Proposition 1 gives the correction for a group by applying the inverse Hessian to the sum of the deleted examples' gradients at the original fit, with the same 1/n1/n factor as in the training loss. To see how much error remains when the rank equals the number of deleted records, we simulated groups of 16 related records. The best rank-16 update left 16.2% mean relative squared error. Increasing the rank to 64 reduced that error to 2.7%. Appendix N reports related experiments on groups of text pairs.

W2. What if the original model was trained with a low-rank adapter?

If both fits use rank-r0r_0 adapters on the same frozen base, their difference has rank at most 2r02r_0. In our comparison, however, we refit the head with all its weights free to change. We then evaluate both the best possible update and the candidate updates against that same refit.

Q3. Can a low-rank update with an error guarantee be computed without the full retraining correction?

We construct the rank-one update in Table 2 from GG and then bound its error without computing the full correction. At d=128d=128, d2/n≈1d^2/n\approx1 and regularization 0.5, six Lanczos steps put the upper bound below 26% of the squared prediction change on each of three draws. The quadrature bounds hold in exact arithmetic, and we evaluate them in floating point. More generally, Eq. (18) bounds the weight error of any candidate from its residual in the deletion equation.

Checking a candidate leaves a separate question about which rank to choose. Algorithm 1 uses an approximate full correction and returns the first rank whose upper bound meets the tolerance. A lower bound above tolerance at the preceding rank certifies minimality. Appendix M instead bounds the failure probability by 1/(b+1)1/(b+1), averaged over bb independent calibration datasets and the new dataset. Computing an update at the selected rank is a separate step.

Thank you for the thorough response and the new experiments. The results on groups of deletions and on correlated feature pairs are useful. So is the rank-one update B = mG with its Lanczos certificate, which shows that at any rank growing more slowly than d the best update is essentially a rescaled gradient step. I think this deserves a place in the main text. I also need to correct my review. The missed share χ exceeds 50% at γ = 1 with weak regularization and stays above about 10% over a wide range of γ, so "narrow" was too strong. In the Frobenius metric, the Gaussian law also matches the real-data minima well; my concern there is only the prediction metric.

My main concern remains, and the new Table 1 sharpens it. Rank above one matters only when the tolerance is close to the size of the deletion effect itself. At 2% of the response SD, no Gaussian deletion needs it, and on Fashion-MNIST with tuned regularization rank one fails for only 16 of 6,375. The Gaussian test of influential deletions cannot probe unusual examples: in an isotropic model, selecting by influence acts through the residual rather than the direction. The mislabelled-pair test reports only effect size. The certified rank-one update also stops at the floor χ, so any tighter tolerance still needs the full correction. I would suggest that the title and abstract reflect this. I keep my score.

Reviewer_bsihOpenReview ↗
Rating
2
Confidence
2
Informativeness
2(+1)
Presentation
2
Soundness
2
Read review
Paper summary

This paper analyzes, in regularized bilinear regression, how well a low-rank update can reproduce the difference between the original model and a model retrained after removing one training sample. The gradient of the removed sample is rank 1, but the correction produced by retraining passes through the inverse Hessian and its rank increases. The authors analyze the relative error that remains even when an oracle with exact knowledge of the retrained model chooses the best rank-r correction, and show that under Gaussian features and fixed regularization, this error converges to a single closed-form curve over all ranks. As a result, any rank that grows slower than the dimension leaves the same amount of error, and reducing the error below that requires a rank proportional to the dimension.

Critical strengths

(S1) By using the oracle’s best approximation rather than a specific algorithm as the reference, the paper clearly shows the expressiveness limit of low-rank updates that no method can exceed.

(S2) The result is given as a single closed-form curve over all ranks, and the experiments reproduce this curve without fitting. The conditions under which low rank is sufficient are also given, so the scope of the result is clear.

Critical weaknesses

(W1)This paper focuses on proving the limit of low-rank updates and does not present a way to mitigate it or to compute the correction efficiently. Algorithm 1 also has to compute the full correction first, so it does not appear to offer a cost advantage. If the conclusion is that the rank must grow in proportion to the dimension, this partly conflicts with the motivation for using low rank in the first place.

(W2) The main theorem holds when the features are isotropic Gaussian and the two paired features are independent, but real embeddings are unlikely to satisfy either assumption.

(W3) The theorem holds when the number of samples is on the same order as the number of parameters and the unit of removal is a single observation. In LLM pre-training, where the number of samples is far larger, the effect disappears, and since real removal is done at the document level, the rank-1 gradient starting point does not hold. More discussion of what this result means in practical unlearning settings would be helpful.

(W4) There is no direct comparison with LoRA-based unlearning methods (LoKU, SEMU, etc.). Also, for full fine-tuning rather than unlearning, the observation that weight changes are high-rank has already been reported at LLM scale (Biderman et al., 2024; Shuttleworth et al., 2025), so it would be helpful to position the contribution of this paper in relation to these works.

I'm not an expert in this area, and will actively reconsider the score if the authors answer these questions clearly.

Questions for authors

See Weaknesses.

2 comments
AuthorsOpenReview ↗

Response to Reviewer bsih

W1. Can the result help compute the update more efficiently?

Once we have the deletion gradient, we can construct the rank-one update in Table 2 without any Hessian products. For the middle row, we then used six products per draw to check its error and obtained an upper bound below 26%. For comparison, computing the full correction to high accuracy took 38 products per draw. Numerical method for the bounds

Algorithm 1 uses an approximate full correction because it checks which rank meets the tolerance. Section 7.1 therefore includes the cost of computing that correction. The theorem explains why this rank check matters. Rank one is enough in the limit if the error tolerance is above χ\chi. However, for a fixed tolerance below χ\chi, the required rank grows in proportion to the matrix dimension. Hence, even a method given the exact retrained model faces the same rank requirement.

W2–W3. How sensitive is the result to the features, the amount of data and the unit of deletion?

The exact formula assumes independent Gaussian pairs. Appendix K.6 tests other feature distributions, and Appendix N.6 tests whether the pairing matters for real text features. The new tests with related features and grouped deletions are described in our responses to XTPV, Q2(b) and Q2(c).

The limiting rank-one error satisfies χ<min⁡(γ,1/γ)\chi<\min(\gamma,1/\gamma), so it can become small when the sample and parameter counts are very far apart. In new Gaussian runs with regularization set to minimize expected prediction error under the simulated model, the best rank-one update left 22.7%, 50.2%, and 18.1% relative squared error at parameter-to-sample ratios of 0.25, 1, and 4. For a group of kk deleted observations, the summed gradient has rank at most kk, and Proposition 1 gives the correction. Applying the rank law to document deletion in LLM pretraining would require modeling which records are removed together and how much that removal changes the fitted model.

W4. How does this relate to LoRA-based unlearning and earlier studies of fine-tuning?

Biderman et al. and Shuttleworth et al. measure the rank and structure of fine-tuning updates. We measure how accurately an update of a given rank can match full retraining after one deletion. We will make this comparison explicit in §2, which already discusses SEMU and LoKU. Biderman et al., Shuttleworth et al., SEMU, LoKU

To test the effect of choosing directions from the gradient, we used single deletions in three synthetic bilinear fits (d=64d=64, n=4,096n=4{,}096). We restricted the update to the gradient's nonzero left and right singular directions and chose the best coefficients using the retrained model. This left 24.7% of the squared prediction change at every tested rank budget. With other directions available, the best error fell from 22.9% at rank one to 9.0% at rank sixteen. Because both comparisons use the retrained model, the difference comes from which directions the update can use. This experiment isolates the gradient-subspace mechanism. A direct benchmark of the LoKU and SEMU implementations would address their performance on their intended tasks.

Thank you for the detailed response and additional experiments. The rebuttal clarified that the lower bound below χ is clear and well established, so I have raised my Informativeness score from 1 to 2. However, two concerns remain, so I will keep my overall rating.

(1) There still seems to be a gap between the theory's assumptions and practical settings. The new experiments show that the error does not easily vanish, but they are small-scale and mostly synthetic. The error also varies with the data (13.7% with correlated pairs, about twice the predicted value on real text heads), which the theory does not explain. In addition, the effect becomes small when data far exceeds or falls well short of the number of parameters, which is close to most settings where large models are used.

(2) It would have been helpful to see a way to overcome this limit. The cheap update is close to a single gradient step, and rank selection requires the full correction or several independent datasets, so the practical guidance comes down to choosing between no update, rank one, or a full correction. I hope future work can address this.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Common response

To address the reviewers' common questions about when rank one is sufficient, we evaluated every single deletion in one simulated Gaussian fit and six Fashion-MNIST models that predict whether two images show the same class. In the Gaussian fit (d=64d=64, n=4,096n=4{,}096), we use λ=0.25\lambda=0.25, which minimizes expected prediction error under the simulated model. For Fashion-MNIST, we select regularization on validation data. At each tolerance, we first check whether leaving the model unchanged is accurate enough and then ask whether rank one suffices for the deletions that still need an update.

Table 1. Single deletions at different tolerances for prediction error.

SettingRMS toleranceNeed updateRank one insufficient
Gaussian0.5% of response SD2,339/4,0961,362/2,339 (58.2%)
Gaussian1% of response SD1,037/4,096204/1,037 (19.7%)
Gaussian2% of response SD86/4,0960/86
Fashion-MNIST0.001 score units6,375/9,21616/6,375
Fashion-MNIST0.002 score units3,762/9,2160 detected
Fashion-MNIST0.005 score units492/9,2160 detected

In the Gaussian fit, we compute the best possible rank-one error. For Fashion-MNIST, we evaluate a lower bound on that error in floating-point arithmetic on 5,000 held-out pairs. The last column counts only the deletions for which that numerical bound exceeds the tolerance. The denominator in that column counts the deletions that need an update.

The best possible error at each rank is also the focus of our theoretical contribution. We let the method use the exact retrained model, so any error left by its best update comes from the rank constraint. Equation (11) then suggests a simple rank-one update, B=mGB=mG, where GG is the deletion gradient in Eq. (4) and mm is the coefficient in Eq. (9). Once GG is available, this update takes no Hessian products to construct. Under the theorem's assumptions, it has the same limiting error as the best rank-one update. Table 2 shows how close the two are at a finite dimension.

Table 2. Mean relative squared prediction error for the rank-one update at d=128d=128.

d²/nRegularizationBest rank-one errorEq. (9) errorGap (pp)
0.50.135.29%36.61%1.32
1.00.524.07%25.02%0.95
2.00.524.56%25.54%0.98

Each row averages three Gaussian draws. We compute the best rank-one update from the full retraining correction for comparison. The gap is in percentage points. See our response to XTPV, Q3, for the cost of checking the error of the update from Eq. (9).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.