Bayes Complexity of Learners vs Overfitting
We introduce a new notion of complexity of functions and we show that it has the following properties: (i) it governs a PAC Bayes-like generalization bound, (ii) for neural networks it relates to natural notions of complexity of functions (such as the variation), and (iii) it explains the generalization gap between neural networks and linear schemes. While there is a large set of papers which describes bounds that have each such property in isolation, and even some that have two, as far as we know, this is a first notion that satisfies all three of them. Moreover, in contrast to previous works, our notion naturally generalizes to neural networks with several layers. Even though the computation of our complexity is nontrivial in general, an upper-bound is often easy to derive, even for higher number of layers and functions with structure, such as period functions. An upper-bound we derive allows to show a separation in the number of samples needed for good generalization between 2 and 4-layer neural networks for periodic functions.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees
Meta-learning can successfully acquire useful inductive biases from data. Yet, its generalization properties to unseen learning tasks are poorly understood. Particularly if the number of meta-training tasks is small, thi…
Gaussian ProcessesGeneralization BoundsMeta-LearningStochastic OptimizationHuman Rademacher Complexity
We propose to use Rademacher complexity, originally developed in computational learning theory, as a measure of human learning capacity. Rademacher complexity measures a learners ability to fit random data, and can be u…
Generalization BoundsLearning TheoryEfficient Measuring of Readability to Improve Documents Accessibility for Arabic Language Learners
This paper presents an approach based on supervised machine learning methods to build a classifier that can identify text complexity in order to present Arabic language learners with texts suitable to their levels. The a…
BIG-bench Machine LearningBayesian Learning of Sum-Product Networks
Sum-product networks (SPNs) are flexible density estimators and have received significant attention due to their attractive inference properties. While parameter learning in SPNs is well developed, structure learning lea…
PAC-Bayesian Domain Adaptation Bounds for Multiclass Learners
Multiclass neural networks are a common tool in modern unsupervised domain adaptation, yet an appropriate theoretical description for their non-uniform sample complexity is lacking in the adaptation literature. To fill t…
Domain AdaptationUnsupervised Domain Adaptation