2
$\begingroup$

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 :)

$\endgroup$
  • $\begingroup$ @ Simon Boge Brant Thank you, just edited the question. $\endgroup$ – lwang024 Apr 3 at 12:31
  • $\begingroup$ 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. $\endgroup$ – whuber Apr 5 at 14:21
  • $\begingroup$ @whuber Let's assume that the data is raw, not centred nor scaled. $\endgroup$ – lwang024 Apr 5 at 18:48
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – lwang024 Apr 3 at 14:58
  • $\begingroup$ 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. $\endgroup$ – JP Trawinski Apr 3 at 16:42
  • $\begingroup$ 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. $\endgroup$ – lwang024 Apr 4 at 5:23
  • $\begingroup$ I realize that inverse of 𝐴=𝐴+π‘₯π‘š+1π‘₯π‘‡π‘š+1βˆ’π‘₯π‘šβˆ’πΏπ‘₯π‘‡π‘šβˆ’πΏ and π΄βˆ’1π‘‘βˆ’(π΄βˆ’1𝑑(π‘₯π‘‘βˆ’π‘₯π‘‘βˆ’πΏ))(π΄βˆ’1𝑑(π‘₯π‘‘βˆ’π‘₯π‘‘βˆ’πΏ))𝑇1+(π‘₯π‘‘βˆ’π‘₯π‘‘βˆ’πΏ)π‘‡π΄βˆ’1𝑑(π‘₯π‘‘βˆ’π‘₯π‘‘βˆ’πΏ). Any idea? $\endgroup$ – lwang024 Apr 4 at 9:37
  • $\begingroup$ Could you write that using LaTeX formatting? It's hard to read in plain text. $\endgroup$ – JP Trawinski Apr 4 at 12:40

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.