Online Learning of Smooth Functions

Consider a learner that wants to predict the next day's temperature range at a given location based on inputs such as the current day's temperature range, humidity, atmospheric pressure, precipitation, wind speed, solar radiation, location, and time of year. In our model, this learner is tested daily. On a given day, the learner gets inputs for that day, which it uses to output a prediction for the next day's temperature range; when the next day arrives, it sees the correct temperature range, then uses this feedback to update future predictions. As this is repeated, the learner accumulates information to help it make better predictions. A natural question arises: can the learner guarantee that its predictions become better over time, and if so, how quickly? We investigate a model of online learning of real-valued functions previously studied in [9, 12, 13, 1, 10, 11] where an algorithm A learns a real-valued function f from some class F in trials. Past research on this model focused on functions of one input, for example, predicting the temperature range solely based on the time of year. The research showed that, as long as the function is sufficiently smooth, the learner can become a good predictor fairly rapidly. Suppose that F consists of functions f: S R for some set S, and fix some f F. In each trial t = 0,...,m, A receives an input s