An Information-Theoretic Framework for Supervised Learning
Preprint
Abstract
Each year, deep learning demonstrates new and improved empirical results with deeper and wider neural networks. Meanwhile, with existing theoretical frameworks, it is difficult to analyze networks deeper than two layers without resorting to counting parameters or encountering sample complexity bounds that are exponential in depth. Perhaps it may be fruitful to try to analyze modern machine learning under a different lens. In this paper, we propose a novel information-theoretic framework with its own notions of regret and sample complexity for analyzing the data requirements of machine learning. With our framework, we first work through some classical examples such as scalar estimation and linear regression to build intuition and introduce general techniques. Then, we use the framework to study the sample complexity of learning from data generated by deep neural networks with ReLU activation units. For a particular prior distribution on weights, we establish sample complexity bounds that are simultaneously width independent and linear in depth. This prior distribution gives rise to high-dimensional latent representations that, with high probability, admit reasonably accurate low-dimensional approximations. We conclude by corroborating our theoretical results with experimental analysis of random single-hidden-layer neural networks.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross EntropyIEEE Transactions on Signal Processing, 2020
- How Much Does Your Data Exploration Overfit? Controlling Bias via Information UsageIEEE Transactions on Information Theory, 2019
- Cyclical Learning Rates for Training Neural Networks2017
- Rate-distortion bounds on Bayes risk in supervised learning2016
- Introduction to the non-asymptotic analysis of random matrices2012
- Decision theoretic generalizations of the PAC model for neural net and other learning applicationsInformation and Computation, 1992