Free to Choose: Investigating the Sample Complexity of Active Learning of Real Valued Functions

Abstract

In the classical framework of learning from examples, examples are randomly drawn and presented to the learner. In this paper, we consider the possibility of a more active learner who is allowed to choose his/her own examples. Our investigations are conducted in a function approximation setting. Specifically, we develop an adaptive sampling strategy (equivalent to adaptive approximation) motivated from the standpoint of optimal recovery (Micchelli and Rivlin, 1976). We provide a general formulation of the problem. We demonstrate the application of this general formulation to two special cases of functions on the real line 1) monotonically increasing functions and 2) functions with bounded derivative. An extensive investigation of the sample complexity of approximating these functions is conducted yielding both theoretical and empirical results on test functions. Our theoretical results (stated in PAC- style), along with the simulations demonstrate the superiority of our active scheme over both passive learning as well as classical optimal recovery.