On the sample complexity of learning smooth cuts on a manifold
Hariharan Narayanan, Partha Niyogi · Conference on Learning Theory · 2009
Modern data sets, though typically high dimensional, are often generated by processes possessing few essential degrees of freedom, as is the case with human speech. In recent years, such considerations have lead to the notion that high dimensional data may be modeled to lie on a submanifold of low intrinsic dimension. We derive bounds on the number of random samples needed before it is possible to approximately separate data into two classes using smooth decision boundaries with high probability.