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

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.