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

Question

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?

Thank you in advance :)

Answer 1

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...