Efficient algorithms for learning functions with bounded variation

P. M. Long. Efficient algorithms for learning functions with bounded variation. Information and Computation, 188(1):99-115, 2004.

(Available in Postscript and PDF formats.)

Abstract
We show that the BV class 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/eps^2) log(1/delta)) 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 BV 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 BV with a sample complexity bound of O((1/eps)log(1/delta)); this also matches a known lower bound to within a constant factor.