The importance of convexity in learning with squared loss (vol 44, pg 1074, 1998)
The paper "The Importance of Convexity in Learning with Squared Loss" gave a lower bound on the sample complexity of learning with quadratic loss using a nonconvex function class. The proof contains an error. We show that the lower bound is true tinder a stronger condition that holds for many cases of interest.
lower bound sample complexity agnostic learning