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

1 Answer 1

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$
8
  • $\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
    Commented Apr 3, 2019 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$ Commented Apr 3, 2019 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
    Commented Apr 4, 2019 at 5:23
  • $\begingroup$ I realize that inverse of 𝐴=𝐴+𝑥𝑚+1𝑥𝑇𝑚+1−𝑥𝑚−𝐿𝑥𝑇𝑚−𝐿 and 𝐴−1𝑡−(𝐴−1𝑡(𝑥𝑡−𝑥𝑡−𝐿))(𝐴−1𝑡(𝑥𝑡−𝑥𝑡−𝐿))𝑇1+(𝑥𝑡−𝑥𝑡−𝐿)𝑇𝐴−1𝑡(𝑥𝑡−𝑥𝑡−𝐿). Any idea? $\endgroup$
    – lwang024
    Commented Apr 4, 2019 at 9:37
  • $\begingroup$ Could you write that using LaTeX formatting? It's hard to read in plain text. $\endgroup$ Commented Apr 4, 2019 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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