Recursive (online) regularised least squares algorithm

Can anyone point me in the direction of an online (recursive) algorithm for Tikhonov Regularisation (regularised least squares)?

In an offline setting, I would calculate \hat\beta=(X^TX+λI)^{−1}X^TY using my original data set where λ is found using n-fold cross validation. A new y value can be predicted for a given x using y=x^T\hat\beta.

In an online setting I continually draw new data points. How can I update \hat\beta when I draw new additional data samples without doing a full recalculation on the whole data set (original + new)?

Answer

\hat\beta_n=(XX^T+λI)^{−1} \sum\limits_{i=0}^{n-1} x_iy_i

Let M_n^{-1} = (XX^T+λI)^{−1}, then

\hat\beta_{n+1}=M_{n+1}^{−1} (\sum\limits_{i=0}^{n-1} x_iy_i + x_ny_n) , and

M_{n+1} – M_n = x_nx_n^T, we can get

\hat\beta_{n+1}=\hat\beta_{n}+M_{n+1}^{−1} x_n(y_n – x_n^T\hat\beta_{n})

According to Woodbury formula, we have

M_{n+1}^{-1} = M_{n}^{-1} – \frac{M_{n}^{-1}x_nx_n^TM_{n}^{-1}}{(1+x_n^TM_n^{-1}x_n)}

As a result,

\hat\beta_{n+1}=\hat\beta_{n}+\frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n} x_n(y_n – x_n^T\hat\beta_{n})

Polyak averaging indicates you can use \eta_n = n^{-\alpha}
to approximate \frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n} with \alpha ranges from 0.5 to 1. You may try in your case to select the best \alpha for your recursion.


I think it also works if you apply a batch gradient algorithm:

\hat\beta_{n+1}=\hat\beta_{n}+\frac{\eta_n}{n} \sum\limits_{i=0}^{n-1}x_i(y_i – x_i^T\hat\beta_{n})

Attribution
Source : Link , Question Author : rnoodle , Answer Author : lennon310

Leave a Comment