Efficient algorithms for learning functions with bounded variation

We show that the class F BV 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 F 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 F BV with a sample complexity bound of O 1 ϵ log 1 δ; this also matches a known lower bound to within a constant factor.

Authors

• Philip M. Long

Keywords

• Statistical learning theory
• Computational learning theory
• Sample complexity
• Bounded variation
• Nonparametric regression