Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/99572
Title: | On the sample complexity of learning functions with bounded variation | Authors: | Long, Philip M. | Issue Date: | 1998 | Citation: | Long, Philip M. (1998). On the sample complexity of learning functions with bounded variation. Proceedings of the Annual ACM Conference on Computational Learning Theory : 126-133. ScholarBank@NUS Repository. | Abstract: | We show that the class FBV of [0, 1]-valued functions with total variation at most 1 can be agnostically learned with respect to the absolute loss in polynomial time from O (1/ε2 log 1/δ) examples, matching a known lower bound to within a constant factor. We establish a bound of O (1/m) on the expected error of a polynomial-time algorithm for learning FBV in the prediction model, also matching a known lower bound to within a constant factor. Applying a known algorithm transformation to our prediction algorithm, we obtain a polynomial-time PAC learning algorithm for FBV with a sample complexity bound of O (1/ε log 1/δ); this also matches a known lower bound to within a constant factor. | Source Title: | Proceedings of the Annual ACM Conference on Computational Learning Theory | URI: | http://scholarbank.nus.edu.sg/handle/10635/99572 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.