N. Littlestone, P. M. Long and M. K. Warmuth. On-line learning of linear functions. Computational Complexity, 5:1-23, 1995. (Preliminary version in STOC'91.)

---

Abstract
We present an algorithm for the on-line learning of linear functions which is optimal to within a constant factor with respect to bounds on the sum of squared errors for a worst case sequence of trials. The bounds are logarithmic in the number of variables. Furthermore, the algorithm is shown to be optimally robust with respect to noise in the data (again to within a constant factor).