Citations
Altmetric:
Alternative Title
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.
Keywords
Source Title
Proceedings of the Annual ACM Conference on Computational Learning Theory
Publisher
Series/Report No.
Collections
Rights
Date
1998
DOI
Type
Conference Paper