# Updating the lasso fit with new observations

I am fitting an L1-regularized linear regression to a very large dataset (with n>>p.) The variables are known in advance, but the observations arrive in small chunks. I would like to maintain the lasso fit after each chunk.

I can obviously re-fit the entire model after seeing each new set of observations. This, however, would be pretty inefficient given that there is a lot of data. The amount of new data that arrives at each step is very small, and the fit is unlikely to change much between steps.

Is there anything I can do to reduce the overall computational burden?

I was looking at the LARS algorithm of Efron et al., but would be happy to consider any other fitting method if it can be made to "warm-start" in the way described above.

Notes:

1. I am mainly looking for an algorithm, but pointers to existing software packages that can do this may also prove insightful.
2. In addition to the current lasso trajectories, the algorithm is of course welcome to keep other state.

Bradley Efron, Trevor Hastie, Iain Johnstone and Robert Tibshirani, Least Angle Regression, Annals of Statistics (with discussion) (2004) 32(2), 407--499.

-
The lasso is fitted through LARS (an iterative process, that starts at some initial estimate $\beta^0$). By default $\beta^0=0_p$ but you can change this in most implementation (and replace it by the optimal $\beta^*_{old}$ you already have). The closest $\beta^*_{old}$ is to $\beta_{new}^*$, the smaller the number of LARS iteration you will have to step to get to $\beta_{new}^*$.
Thanks, but I am afraid I don't follow. LARS produces a piecewise-linear path (with exactly $p+1$ points for the least angles and possibly more points for the lasso.) Each point has its own set of $\beta$. When we add more observations, all the betas can move (except $\beta^0$, which is always $0_p$.) Please could you expand on your answer? Thanks. –  NPE Nov 17 '10 at 11:34
I was looking to update the entire path. However, if there's a good way to do it for a fixed penalty ($\lambda$ in the formula below), this may be a good start. Is this what you are proposing? $$\hat{\beta}^{lasso} = \underset{\beta}{\operatorname{argmin}} \left \{ {1 \over 2} \sum_{i=1}^N(y_i-\beta_0-\sum_{j=1}^p x_{ij} \beta_j)^2 + \lambda \sum_{j=1}^p |\beta_j| \right \}$$ –  NPE Nov 17 '10 at 17:48
@aix. Yes, it all depends on the implementation you use and the facilities you have access to. For example: if you have access to a good lp solver, you can feed it with the past optimal values of $\beta$ and it'll carry the 1-2 step to the new solution very efficiently. You should add these details to your question. –  user603 Nov 20 '10 at 16:27