On-line learning of linear functions

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).