article · 2007
Sample Complexity versus Approximation Error
Peter L. Bartlett, Robert C. Williamson
Cited by 0Abstract and details only
Abstract
We consider the problem of learning an unknown real-valued function from a sequence of values of the function at randomly chosen points when the estimates are constrained to some class of functions called the hypothesis class. Ideally, thehypothesis class should be able to approximate a wide variety of target functions, yet not need an excessive number of examples to ensure that a learning algorithm can choose a near-optimal approximation to the target function. We show that these two objectives are incompatible, in the sense that as the approximation error of the hypothesis class decreases, a lower bound on the sample complexity must increase. The approximation error is the largest distance between an element of the class of candidate target functions and its best approximation in the hypothesis class. The sample complexity isthenumber of examples necessary for a nearoptimal estimate of any target function. The relationship between approximation error and sample complexity depends on a combinatorial dimension of the class of candidate target functions which are to be approximated. We give an example of this relationship for the
Cite this paper
Bartlett, P. L., & Williamson, R. C. (2007). Sample Complexity versus Approximation Error.
Bartlett, Peter L., and Robert C. Williamson. “Sample Complexity versus Approximation Error.” 2007.
Bartlett, Peter L., and Robert C. Williamson. 2007. “Sample Complexity versus Approximation Error.”
Bartlett, P.L. and Williamson, R.C. (2007) ‘Sample Complexity versus Approximation Error’.
@article{bartlett2007sample,
title = {{Sample Complexity versus Approximation Error}},
author = {Bartlett, Peter L. and Williamson, Robert C.},
year = {2007}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.