The importance of convexity in learning with squared loss

Abstract

We show that if the closure of a function class F under the metric induced by some probability distribution is not convex, then the sample complexity for agnostically learning F with squared loss (using only hypotheses in F) is £2 (In (l/<5)/e2) where 1 -6 is the probability of success and f. is the required accuracy. In comparison, if the class F is convex and has finite pseudodimension, then the sample complexity is O ( 1/ε(in 1/ε+ In 1/σ) ). Ifa noncon vex class F has finite pseudodimension, then the sample complexity for agnostically learning the closure of the convex hull of f, is O ( 1/ε ( 1/ε In 1/ε+ln 1/σ) ). Hence, for agnostic learning, learning the convex hull provides better approximation capabilities with little sample complexity penalty. Show more