On-line learning of smooth functions of a single variable

D. Kimber and P. M. Long. On-line learning of smooth functions of a single variable. Theoretical Computer Science, 148(1):141-156, 1995.

(Available in Postscript and PDF formats.)

Abstract
We study the on-line learning of classes of functions of a single real variable formed through bounds on various norms of functions' derivatives. We determine the best bounds obtainable on the worst-case sum of squared errors (also ``absolute'' errors) for several such classes. We prove upper bounds for these classes of smooth functions for other loss functions, and prove upper and lower bounds in terms of the number of trials.