Learning Geometric Concepts via Gaussian Surface Area

We study the learnability of sets in Rⁿ under the Gaussian distribution, taking Gaussian surface area as the “complexity measure” of the sets being learned. Let C_S denote the class of all (measurable) sets with surface area at most S. We first show that the class C_S is learnable to any constant accuracy in time n^O(S2), even in the arbitrary noise (“agnostic”) model. Complementing this, we also show that any learning algorithm for C_S information-theoretically requires 2^Ω(S2) 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.