Full Name
Mrs Katerina Mamali
Primary Department, Unit, or Institute
Computer Science
University/Company
Yale
Talk Title
Limits And New Foundations For Learning With Bounded Surface Area
Abstract
The foundation of learning theory lies in the characterization of PAC-learnability by the VC-dimension of the function class when we place no assumptions on the distribution of the data. The computational intractability of this distribution-independent approach has motivated the study of learning under distributional assumptions, such as Gaussian or uniform distributions.
Prior work has established a new notion of complexity for the function classes, called Surface Area, introducing algorithms with sample complexity and runtime polynomial in the dimension of the space but exponential in the required accuracy of the learning task. While this exponential dependence is known to be necessary for the runtime, it has been a longstanding open question whether it is also necessary for the sample complexity.
In this work, we answer this question in the affirmative by showing that the exponential dependence in the accuracy is indeed necessary even in the sample complexity of learning under the Gaussian or the uniform distribution. Moreover, we introduce a new measure of complexity for function classes, called Lipschitz Surface Area, which enables us to surpass some fundamental limitations of the standard Surface Area.
Prior work has established a new notion of complexity for the function classes, called Surface Area, introducing algorithms with sample complexity and runtime polynomial in the dimension of the space but exponential in the required accuracy of the learning task. While this exponential dependence is known to be necessary for the runtime, it has been a longstanding open question whether it is also necessary for the sample complexity.
In this work, we answer this question in the affirmative by showing that the exponential dependence in the accuracy is indeed necessary even in the sample complexity of learning under the Gaussian or the uniform distribution. Moreover, we introduce a new measure of complexity for function classes, called Lipschitz Surface Area, which enables us to surpass some fundamental limitations of the standard Surface Area.