Please use this identifier to cite or link to this item: http://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.

Page view(s)

39
checked on Nov 9, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.