An Information-Theoretic Framework for Supervised Learning
  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 sign neural networks, deep ReLU neural
networks, and deep networks that are infinitely wide but have a bounded sum of
weights. For sign neural networks, we recover sample-complexity bounds that
follow from VC-dimension based arguments. For the latter two neural network
environments, we establish new results that suggest that the sample complexity
of learning under these data generating processes is at most linear and
quadratic, respectively, in network depth.
