0
$\begingroup$

I am working on a project where I use multilinear regression on many large data sets. Each data point is formatted as (time, data). Lets say I calculate a regression polynomial based on the past month of data, then a week passes and I want to come up with an updated regression polynomial. Can I use the past week's data and the old regression polynomial to come up with an updated polynomial? Would this be algorithmically faster than doing multilinear regression on the full month+week's worth of data?

Considering the amount of data I'm processing, any processor time I can save is essential.

For more background I am planning on just using typical least square regression. Not sure if this makes a difference.

$\endgroup$
2
  • $\begingroup$ This type of algorithm is typically called "online". So for example "online regression". There are loads of them out there. $\endgroup$
    – user126540
    Commented Jul 2, 2017 at 9:26
  • $\begingroup$ Google 'update regression'. Several possibly useful discussions on cross-validated site. $\endgroup$
    – BruceET
    Commented Jul 2, 2017 at 20:07

1 Answer 1

0
$\begingroup$

Say you're using the OLS estimator $\hat\beta=(X^T X)^{-1}X^T y$, where $X\in\mathbb R^{n\times p}$. There are two ways that updating for a new point is faster than fitting the entire thing again:

  1. Keep the sufficient statistic $\hat\Sigma=X^T X$ and $\hat\gamma = X^T y$. Updating $\hat\gamma$ can be clearly done in $O(p)$ time. Updating $\hat\Sigma$ and $\hat\Sigma^{-1}$ is trickier: one might need to use the Sherman-Morrison formula. In general the updating can be done in $O(p^2)$ time, compared to the raw $O(np^2+p^3)$ fitting time.

  2. Suppose you're using gradient descent or its variants to fit the OLS model. Then under the assumption that the model does not drift too much over time, you may want to do warm start (using the last fitted model as initializer in the new model). This way saves time.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .