Learning Geometric Concepts via Gaussian Surface Area

We study the learnability of sets in R<sup>n</sup> under the Gaussian distribution, taking Gaussian surface area as the “complexity measure” of the sets being learned. Let C<sub>S</sub> denote the class of all (measurable) sets with surface area at most S. We first show that the class C<sub>S</sub> is learnable to any constant accuracy in time n<sup>O(S2)</sup>, even in the arbitrary noise (“agnostic”) model. Complementing this, we also show that any learning algorithm for C<sub>S</sub> information-theoretically requires 2<sup>Ω(S2)</sup> examples for learning to constant accuracy. These results together show that Gaussian surface area essentially characterizes the computational complexity of learning under the Gaussian distribution.