Are there algorithms for computing “running” linear or logistic regression parameters?

Question

A paper "Accurately computing running variance" at http://www.johndcook.com/standard_deviation.html shows how to compute running mean, variance and standard deviations.

Are there algorithms where the parameters of a linear or logistic regression model can be similarly "dynamically" updated as each new training record is provided?

Answer 1

For your two specific examples:

Linear Regression The paper "Online Linear Regression and Its Application to Model-Based Reinforcement Learning" by Alexander Strehl and Michael Littman describes an algorithm called "KWIK Linear Regression" (see algorithm 1) which provides an approximation to the linear regression solution using incremental updates. Note that this is not regularised (i.e. it is not Ridge Regression). I'm pretty sure that the method of Strehl & Littman cannot extend to that setting.

Logistic Regression

This thread sheds some light on the matter. Quoting:

Even without a regularization constraint, logistic regression is a nonlinear optimization problem. Already this does not have an analytic solution, which is usually a prerequisite to deriving an update solution. With a regularization constraint, it becomes a constrained optimization problem. This introduces a whole new set of non-analytic complications on top of the ones that the unconstrained problem already had.

There are however other online (or incremental) methods for regression that you might want to look at, for example Locally Weighted Projection Regression (LWPR)

Answer 2

Adding to tdc's answer, there are no known methods to compute exact estimates of the coefficients at any point in time with just constant time per iteration. However, there are some alternatives which are reasonable and interesting.

The first model to look at is the online learning setting. In this setting, the world first announces a value of x, your algorithm predicts a value for y, the world announces the true value y', and your algorithm suffers a loss l(y,y'). For this setting it is known that simple algorithms (gradient descent and exponentiated gradient, among others) achieve sublinear regret. This means that as you see more examples the number of extra mistakes your algorithm makes (when compared to the best possible linear predictor) does not grow with the number of examples. This works even in adversarial settings. There is a good paper explaining one popular strategy to prove these regret bounds. Shai Shalev-Schwartz's lecture notes are also useful.

There is an extension of the online learning setting called the bandit setting where your algorithm is only given a number representing how wrong it was (and no pointer to the right answer). Impressively, many results from online learning carry over to this setting, except here one is forced to explore as well as exploit, which leads to all sorts of interesting challenges.

Answer 3

Other answers have pointed to the world of machine learning, and that is certainly one place where this problem has been addressed.

However, another approach that may be better suited to your needs is the use of the QR factorization with with low rank updates. Approaches to doing this and using it to solve least squares problems are given in:

Updating the QR factorization and the least squares problem by Hammerling and Lucas.