# How to compute the change of Ridge regression solution when one row of data changes?

I understand that $$\boldsymbol{\beta} = (X^TX + \lambda I)^{-1}X^T\mathbf{ Y}$$ is the closed form solution of Ridge regression.

So sometimes, when I run a rolling window, meaning everytime I run the regression, I remove one row of data and add in a new row, how do I tell how much $$\beta$$ has changed from this closed form solution.

Better still, is it possible for me to express the change in $$\beta$$ in terms of the Euclidean distance between the rows that are removed and added? Or set a lower bound for change in $$\beta$$ based on the Euclidean distance between the rows?

• @ Simon Boge Brant Thank you, just edited the question. – lwang024 Apr 3 at 12:31
• It depends on what you mean by "$X.$" If that is intended to refer to the raw data matrix, then an efficient rolling ridge regression formula can be derived fairly easily. But if, as is usual with ridge regression, "$X$" refers to the centered, scaled variables, the problem is that adding or deleting even a single observation changes every component of $X$ in a nonlinear fashion, which will substantially complicate the analysis and the formulas. – whuber Apr 5 at 14:21
• @whuber Let's assume that the data is raw, not centred nor scaled. – lwang024 Apr 5 at 18:48

## Online Moving-Window Ridge Regression

You can use this same closed-form solution to update your $$\beta$$ online, even in a moving-window context. Suppose you have $$m$$ data points $$x_1, \ldots, x_m$$ and m responses $$y_1, \ldots, y_m$$ and your moving-window size is $$L \leq m$$.

Note that you can rewrite the closed-form solution as $$\left(\sum_{i=1}^L x_ix_i^T + \lambda I\right)^{-1}\sum_{i=1}^L y_ix_i = A^{-1}b$$.

1. Initialize $$A = \sum_{i=1}^L x_ix_i^T + \lambda I$$ and $$b = \sum_{i=1}^L y_ix_i$$.
2. A new point $$x_{m+1}$$ comes in.
3. Set $$A = A + x_{m+1}x_{m+1}^T - x_{m-L}x_{m-L}^T$$. This adds the information in the new data point to $$A$$ while removing the information from the old data point now outside the moving window.
4. Predict $$f(x_{m+1}) = b^TA^{-1}x_{m+1}$$
5. Receive $$y_{m+1}$$
6. Update $$b = b + y_{m+1}x_{m+1} - y_{m-L}x_{m-L}$$

You can also use the Sherman-Morrison formula to update $$A^{-1}$$ directly instead of recomputing the inverse every time. You can see this paper for more information about online moving-window ridge regression.

## Change in $$\beta$$ Analytically

TBD...

• Thank you, the paper is good :) May I know is it possible to write out the change in \beta analytically? Or set a analytical lower bound of change in \beta. I want to show that when the removed and the added data are not identical, the Ridge regression result will definitely change. – lwang024 Apr 3 at 14:58
• Intuitively, $\beta$ will not change as long as the new data point $(x_t, y_t)$ does not lie on the hyperplane that $\beta$ represents. It is possible to write out the change in $\beta$ analytically using the Sherman-Morrison formula. I'll edit my answer to include this. – JP Trawinski Apr 3 at 16:42
• Wow, thank you so much. This answer is great :) Unfortunately, I am under 15 reputations, so I upvoted you, but the vote cannot be shown publicly. I wonder whether I can show that the change in \beta is non-zero whenever the new data point differs from the old data point. – lwang024 Apr 4 at 5:23
• I realize that inverse of 𝐴=𝐴+𝑥𝑚+1𝑥𝑇𝑚+1−𝑥𝑚−𝐿𝑥𝑇𝑚−𝐿 and 𝐴−1𝑡−(𝐴−1𝑡(𝑥𝑡−𝑥𝑡−𝐿))(𝐴−1𝑡(𝑥𝑡−𝑥𝑡−𝐿))𝑇1+(𝑥𝑡−𝑥𝑡−𝐿)𝑇𝐴−1𝑡(𝑥𝑡−𝑥𝑡−𝐿). Any idea? – lwang024 Apr 4 at 9:37
• Could you write that using LaTeX formatting? It's hard to read in plain text. – JP Trawinski Apr 4 at 12:40