An Information-Theoretic Framework for Deep Learning
Authors: Hong Jun Jeon
Benjamin Van Roy
Venue: NeurIPS 2022 Accept (2022)
Keywords: Information Theory
Deep Learning
Nonparametric Statistics

Abstract: Each year, deep learning demonstrate 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. We use this framework to study the sample complexity of learning from data generated by deep ReLU neural networks and deep networks that are infinitely wide but have a bounded sum of weights. We establish that the sample complexity of learning under these data generating processes is at most linear and quadratic, respectively, in network depth.

An Information-Theoreel Framework for Deep Learning
Hong Jun Jeon
Benjamin Van Roy
Department of Computer Science
Department of Electrical Engineering
Stanford University
Department of Management
Stanford, CA 94305 hj jijeensttanford edu
Science and Engineering Stanford University Stanford, CA 94305
bvr@stanford.ccm edu
Abstract
Each year, deep learning demonstrates new and improved empirical results with deeper and wider neural networks. Meanwhile, with existing theoretical frame- works, it is difficult to analyze networks deeper than two layers without resorting to counting parameters or encountering sample complexity bounds that are expo- nential in depth. Perhaps it may be fruitful to try to analyze modern machine learn- ing under a different lens. this paper, we propose a novel ieformmaion-thhoreee framework with its own notions of regret and sample complexity for analyzing the data requirements of machine learning. We use this framework to study the sam- ple complexity of learning from data generated by deep ReLU neural networks and deep networks that are infinitely wide but have bounded sum of weights. We establish that the sample complexity of learning under these data generating processes is at most linear and quadratic, respectively, network depth.
Introduction
In modern machine learning, the apparent capabilities of empirical methods have rapidly outpaced what is soundly understood theoretically. Modern neural network architectures have scaled im- mensely in both parameter count and depth. GPT3, for example, encodes about 175 billion parame- ters in 96 decoder blocks, each with many layers within. Yet, contrary to traditional intuition, these deep neural networks with gargantuan parameter counts are able to generalize well and produce useful models with tractable amounts of data. This gap between what has been shown theoretically versus empirically makes quite enticing to develop a coherent framework that could potentially explain this phenomenon.
Existing theory breaks down when trying to explain learning under models that are simultaneously very deep (many layers) and wide (many hidden units per layer). Classical results such as those of Haussler [1992] and Bartlett et al. [1998] can potentially handle the deep but narrow case. These results bound the sample complexity of learning neural network function in terms of the num- ber of parameters and the depth. More recently, Harvey et al. [2017] established a general result that suggests that for neural networks with piccewise-lines linear activation units, the sample complexity grows linearly in the product of parameter count and depth.
However, when consider neural networks with arbitrary width, these bounds become vacuous. As an alternative to parameter count methods, researchers have produced sample complexity bounds
36th Conference Neural Information Processing Systems (NeurIPS 2022).

---

that depend on the product of norms of realized weight matrices. Bartlett et al. [2017] and Neyshabur et al. [2018], for example, establish sample complexity bounds that scale with the product of spectral norms. Neyshabur et al. [2015] and Golowich et al. [2018] establish similar bounds that instead seale in the product of Frobenius norms. While this line of work provides sample complexity bounds that are indeeeiindeeenentt they pay for it via an exponential dependence on depth, which is also inconsistent with empirical results.
A large line of work has tried to ameliorate this exponential depth dependence via so-called data- dependent quantities Dziugaite and Roy [2017], Arora et al. [2018], Nagarajan and Kolter [2018], Wei and Ma [2019]. Among these, the most relevant to our work is Wei and Ma [2019], which bounds sample complexity as function of depth and statistics of trained neural network weights. While difficult interpret due to dependence suggests a nonic dependence depth. Arora et al. [2018] also utilize concepts of compression in their analysis, which we generalize and expand upon. While they establish a sample complexity bound that suggests quadratic dependence on depth, further dependence may be hidden in data- dependent terms.
complicated data-dependent statísties, their bound
We suspect that the looseness of these results in comparison to empirical findings are due to a worst- case analysis framework. In this paper, we study average-case notion of regret and sample com- plexity that is motivated by information theory. Our information-theoredd framework generalizes that developed by Haussler et al. [1994], which provided a basis for understanding the relationship between prediction error and information. In similar vein, Russo and Zou [2019] introduced tools that establish general relationships between mutual information and error. Using these results, Xu and Raginsky [2017] established upper bounds on the generalization error of learning algorithms with countably infinite hypothesis spaces. We extend these results in several directions to enable analysis of data generating processes related deep learning. For example, the results of Haus- sler al. [1994] do not address noisy observations, and all three aforementioned papers do not accommodate continuous parameter spaces, let alone nonparametric data generating processes. A distinction of our work is that it builds on rate-distortion theory to address these limitations. While Nokleby et al. [2016] also use rate-distortion theory to study bayes risk, these results are again lim- ited to parametric classification and only offer lower bounds. The rate-distortion function that we study is equivalent to one defined the information bottleneck Tishby et al. [2000]. However, instead of using it as basis for optimization methods as do Shwartz-ZZi -Ziv and Tishby [2017]. we develop tools to study sample complexity and arrive at concrete and novel results.
In this paper, we consider contexts in which an agent learns from an iid sequence of data pairs. We establish tight upper and lower bounds for the average regret and sample complexity that depend on the rate-distortion function. With these information-theoretie tools, we analyze two deep neural network data generating processes and quantify the number of samples required to arrive a useful model. We establish novel sample complexity bounds for ReLU neural network data generat- ing processes that are roughly linear in the parameter count (as opposed linear in the product of parameter count and depth as in Harvey et al. [2017]). For multilayer process with arbi- trary width but bounded sum of weights, we establish sample complexity bounds with only quadratic depth dependence as opposed to exponential or high-order polynomial dependence as in Bartlett et al. [2017] and Wei and Ma [2019] respectively. The main contribution of this paper is an elegant and intuitive ieformation-theoreee lems. We demonstrate its promise by deriving the two aforementioned theoretical results pertaining to deep neural networks which were not possible to show with existing analysis methods.
framework for analyzing machine learning prob-
2 Prediction and Error
We begin by introducing the structure of data generating processes we consider in our framework and defining notions of error and sample complexity.
2

---

2.1 Data Generating Process
We consider a stochastic process that generates a sequence ((X,, Y(+1): : = of data pairs. We refer to each X, as an input and each Y++1 as an output. We define these and all other random variables we will consider with respect to a probability space IP).
Elements of the sequence (Xe Denote the history of data generated through time by He (Xo, ,i...., Y, Xe). We assume that each (X,, Y(+1) pair is exchangeable. As a result of de Finetti's s theorem, there exists latent variable for which the pairs (X,, 1 are iid conditioned on &. Here, (the environment) a random function that specifies a conditional output distribution P(Y++1 E -|E, X, = x) = E(1(z) for each input z. Initial uncertainty about is expressed by the prior distribution P(E E).
O..... T - 1) are independent and identically distributed.
2.2 Prediction
We consider an agent that predict the next response Y,+1 given the history H₃. Rather than a point estimate, the agent provides as its prediction probability distribution Pt over possible responses. We characterize the agent in terms of function for which P. =HH)).
We now introduce some notation for referring to particular predictions. We will generally use Pt as a dummy variable - that is a generic prediction whose definition depends on context. We denote the prediction conditioned on the environment, which could only be produced by a prescient agent, by
P. = PP -IE = E-)(X.).
We will refer this the target distribution it represents what an agent aims to learn. Finally, use Pt to denote the preeecctt-e conditioned on H,, which will tum out to be optimal for the objective we will define next.
P₂ PP(44 E -HH,-
2.3 Error
We assess the error of prediction P. in terms of the KL-divergence relative Pt:
dKL (PF = / P. (dy) In d.P.
dP. (v).
This quantifies mismatch between the prediction P. and target distribution P This notion of error is closely related to more common eтror notions from machine learning. When Y takes values in countable set, this notion of error is equivalent to expected cross-entropy, loss. Meanwhile when Y continuous, this notion of error is upper and lower bounded by linear functions of mean-squared error under reasonable circumstances (refer to Appendix A).
3 Regret and Sample Complexity
We assess an agent's performance over duration 7 in terms of the expected cumulative error
R- (T) =
Σ d det
The focus of this paper is on understanding how well optimal agent perform, given particular data generating processes. We will use regret to refer to the optimal performance defined below.
Definition 1. (optimal regret) For all T E Z+, environments E and data generating processes ((Xo, Y1), (X1, 12)...... the optimal regret is
R(T) = inf R2 (T).
3

---

We will also consider sample complexity, which we take to be the duration required to attain ex- pected average error within some fraction 2 0 of an optimal uninformed prediction: Definition 2. (sample complexity) all 2 0, environments and data generating processes
((Xo, (1), (X1, .)). the sample complexity is
:= min T R(T)) $g.
Note that this definition of sample complexity measures the number of samples necessary to achieve average cumulative error below c. Traditionally, generalization error quantifies the number of sam- ples necessary achieve out-of-sample error (such T(YT+1; Hr)) below Due to simple monotonicity result, our notion of sample complexity upper bounds the one for out-of-sample error ie I(YT+1: E R(T)
3.1 Optimal Predictions
In this paper, we focus how well an optimal agent performs, rather than on how to design prac- tical agents that economize on memory and computation. Recall that an agent is characterized by function x, which generates predictions P: = xH,, Z,), where Z, represents algorithmic random- ness. The following result establishes that the conditional distribution P. P(Y+1 E -(H,) offers an optimal prediction.
Theorem 3. (optimal prediction) For all t 1 0,
E(dkL(P?))PP) H.] inf E(dkL(P He),
where P. n (H,,
proof may be found in Appendix A corollary that characterizes the performance shortfall of suboptimal agent may also be found there. This corrolary opens future avenues regarding learning under misspecification compute constraints. In the remainder of the paper will study agent that generates optimal predictions P: IP(++1 E (H,,, illustrated in Figure 1.
H, (Xo, Y2...,
p = P(Y+1 E
Figure I: We consider an agent that, given history H,, generates an optimal prediction P..
4
Information
We define concepts for quantifying uncertainty and the information gained from observations. The entropy HEE) the environment quantifies the agent's initial degree of uncertainty in terms of the information required to identify E. We will measure information nats, each of which is equivalent 1/ In 2 bits. For example, if & occupies countable range θ then H(E) 0) In IP A). Uncertainty time can be expressed in terms of the conditional entropy H(E which is the number of remaining nats after observing He. The mutual information I(E; H.) H[EE) H,) quantifies the information about & gained from H,. Proofs for all lemmas in this section may be found in Appendix B
Eece IP
4.1 Learning from Errors
Each data pair (Xe, Y441) provides I[E;; (X,, Ye+ Ye+1) Y:) nats of new information about the environment. By the chain rule of mutual information, this is the sum
I(E; (Xe, Ye+1))M,,1,, Yi) I[E; H, Y2) - I1E; H4)

---

of the information gained from X, and Y4+1- The former term ([E;X,|HH-111 is equal to 0 because X, is independent from both & and (H Y)). The latter term TI{E; ()) can be thought of as the level of surprise experienced by the agent upon observing Y++1- Surprise is associated with prediction error, and the following result formalizes the equivalence between error and information.
Lemma 4. (expected prediction error equals information gain) For all t E E+.
([d|I.(P7 (TE;; Yee;Y++HH.)).
and R(() I188; Hy).
The agent's ability to predict tends improve as it learns from experience. This is formalized by the following result, which establishes that expected prediction errors monotonically nonincreasing.
Lemma 5. (expected prediction error is monotonically nonincreasing) For all t Z.,,
(Pd (P;,,(P
5 General Bounds via Rate-Distortion Theory
An environment proxy is random variable E that provides information about the environment E but no additional information pertaining to inputs outputs. In other words, & 1. (X, Y)JE. We will denote the set of environment proxies by é. While an infinite amount of information must be acquired to identify the environment when H{)) = oo, there can be a proxy & with H{{)) < oc that enables accurate predictions. The minimal expected error attainable based on the proxy is achieved by a prediction P P(Y E X.). This results in expected error EjdxL ([dkk((P1]PP) (P)]
We will establish that the expected error E(dkı. (P* [P] equals the information gained, beyond that supplied by the proxy &, about the environment & from observing Y. This is intuitive: more is learned from Y if knowledge of enables a better prediction of Y than does E. We quantify this information gain in terms of the difference HYY|E, conditioned on & and that conditioned & This is equal to the mutual information T(E; YJE, X) = H(Y & X) H) E, X). The following result equates this with expected error. Lemma 6. (proxy error equals information gain) For all E E ê.
HY||E, between the uncertainty
E[dkL(P*)l1 [)] = I(E;Y\E X).
A proof may be found in Appendix C. ([d [[]]] is the distortion incurred by estimate of Y given only E as opposed to E. For example, & may be a quantization or lossy compression of E an E[dkk((**) P)] is measuring how inaccurate our prediction of Y is under this compression É.
Now we consider the following cooptimll set:
b. = f
θ E|dk c
+. denotes the set of proxies that produce predictions that incur distortion of no more than an c. One can imagine that for environments with simple input distributions, such as those constrained subspace or low-dimensional manifold, this set Ô, will be much larger since the average error need only be below in small subset of the domain.
With the distortion component of rate-distortion covered, the rate remains. The rate is I[E; E), the amount of information about the environment conveyed by the proxy. For example, a finer quantization would result in higher rate since & would capture E with more bits of precision. However, with this higher rate, the distortion incurred by & should in turn be lower. A higher fidelity compression should cost more bits but result in less distortion. The rate aate-iistortion function formalizes this trade-off concretely:
5

---

Definition 7. For e 2 0 and environments E, The rate-distortion w.r. distortioo B[dkL(P*1|)) is
HE(E) = inf I(E; εEê.
HI, characterizes the minimal amount of information that a proxy must convey about the environment in order to make e-accurate predictions. Even when H(EE) infinite and e is small, H. (E) can be manageable. Once again, if we consider environment with simple input distribution, the rate- distortion would be lower since would be taking infimum over larger set θ. Depending on the structure of the input distribution and the environment, one could imagine that the reduction could be significant. As we will see in the following section, both the regret and sample complexity of learning scales with H.. (E).
5.1 Bounding Regret and Sample Complexity via Rate-Distortion
With rate-distortion in place, we produce tight bounds on regret and sample complexity. These bounds very general, applying any data generating process. The results upper and lower bound error and sample complexity terms of rate-distortion. As such, for any particular data generating process, bounds can be produced by characterizing the associated rate-distortion function. Proofs for the following two theorems can be found in Appendix C.
The following result brackets the cumulative error of optimal predictions.
Theorem 8. (rate-distortion regret bounds) For all
sup min (E), eT} < R(T) < inf (8) +
e00
This upper bound intuitive. Knowledge of a proxy & E ô. enables an agent to limit prediction error to e per timestep. Getting to that level of prediction error requires (E) nats, and therefore, that much cumulative error. Hence, R(T) (E) + eT.
To motivate the lower bound, note that an agent requires (E) nats to attain per timestep error within c. Obtaining those nats requires cumulative error at least H. So prior to obtaining that many nats, the agent must incur at least error per timestep. hence the eT term in the minimum. Meanwhile, time T, the agent able to produce predictions with error less than it means that has already accumulated least IH, (E) nats of information about & (error).
Sample complexity bounds follow almost immediately from Theorem 8.
Theorem 9. (rate-distortion sample complexity bounds) For all 2 0,
(E)
H, HE))
21H, (
<
T
inf 6E(0,c] 8
<
E
6 Deep Neural Network Environments
We now study the rate-distortion function of multilayer environments. As we established, sample complexity is governed by the rate-distortion function (E). In this section, we will focus on characterizing this rate-distortion function, and hence the sample complexity, of two prototypical multilayer environments.
6.1
Prototypical Multilayer Environments
6.1.1 Prototypical Environment 1: (ReLU Neural Networks)
Prototypical Environment I mirrors the architecture of fully-connected feed-forward neural net- works (refer to Figure 2 left). Let
U fi( = ReLU(A + b()).

---

U1
f
W
Ex
Figure 2: (Left) Prototypical environment (Right) Prototypical environment 2.
where A E Rxd, B(1) E RV both with independent elements each with variance à. For k E {2. - 1]. let
Us = Su(UR-1) = Re. b(())
where A ANNN b(0) RN, both with independent elements each with variance N. For the final layer, let
UK (UKUK-I) A K-1
where A(K) RN with independent elements, each with variance N. In this environment, & is identified by (A(H), b()) for l (1,...: K and &K identified by A(K), We will refer to this environment as the deep ReLU network.
6.1.2 Prototypical Environment 2: (Deep Nonparametric Networks)
Prototypical Environment 2 considers a deep nonparametric neural network (refer to Figure 2 right). For E (1,..., li...,,K,
K). let
Uk fu((U=1)) = Ve. Σ
(k) a (k)
(1) (UK-1),
1=1
where e E Z444, (k) (a) ,..., (1) Dir (N, [....., N1). and kkk) sid Rademacher. For
k E (2...., K 1], the deterministic basis functions g/h² maps from R. RM (gn) (I...., N)) are maps from g2 + RMM and (gn (K) n E (l,....N) are maps from RrM + R. For
regularity, will assume that for all n and k. the basis functions satisfy Elgh (U+ S 1.
& is identified by (A)) @ a (R). We will refer to this environment (Exa) as the deep nonparametric network. For intractably large N, fE is effectively nonparametric. In this regime, parameter count becomes a vacuous description the data generating process's s complexity. However, the complex- ity is still controlled by fact that Σn Os due to Dirichlet prior. We will establish rate-distortion and sample complexity bounds that depend only logarithmically on N and linearly in
A natural example of such an environment one in which the basis functions are In Re X) where ||0||2 = and N may be prohibitively large i.e. exponential in the input dimension.
(k) (X) =
6.2 From Single Multilayer Environments
We interested in analyzing the depth dependence of the rate-distortion and sample com- plexity of these environments. We will use Eng and Eig for i 2 j to denote (E, E...... Ej) and EÉ,,E..,..., E,) respectively.
For multilayer environments, the error is cumbersome to reason about. Figure 3 (left) depicts the error incurred by using a multilayer proxy εK.1 to approximate multilayer environment Ex:1- Ev- idently, it seems difficult to manage the eтror propagation through the layers of the environment. Many traditional lines of analysis struggle on this front and result sample complexity bounds that exponential in the depth Bartlett al. [2017], Golowich al. [2018]. These papers consider worst-case reasoning under which an error between the first outputs U₁ and Un may blow up to
error when passed through remaining layers of the network (where is a spectral radius).

---

W
smw
UKC-
X-
8xcd
Ex
Ex
Figure 3: (Left) The error incurred by a multilayer proxy Ek:1 measures the difference between true output Y and the prediction (shown in red box). This difference is the result of emrr that builds up through layers of the environment (denoted by red dotted outline). (Right) A much easier system to analyze is one in which we measure the incremental error at each stage of the multilayer environment. each layer incurs an error of k. the total error incurred will be
would be much simpler to instead analyze the incremental error incurred at each stage of the network. Figure 3 (right) depicts this. consider that at each layer, we know the true input Uk-1 and simply measure the immediate error incurred the output Uş opposed the error incurred at the final output of the network Y.
Mathematically, the error incurred by the full system from using proxy Ex:1 can be expressed as [(Y&&uu | X). By the chain rule, we have that
Therefore, the error incurred from layer it can be expressed as & Ek1, X). This is cumbersome since we not given the true input Uk-1 but rather approximation from input measuring the error in the final output Y opposed to the
X and Ex-1:1- Furthermore, immediate output Us. It would be much more simple to analyze something like the following:
Σ I(U + E& Uk-1);
where W is independent O-mean gaussian noise with variance o² in each dimension. This sum is much easier to work with because the kth term only depends on & &x, Uk-1, and Ug. There is no inter-layer dependence.
The key insight that our two prototypical environments (and many others), something akin to the following will hold:
I(Y; EAlKsk+,K, Ex.,, X) s L(U + W; & Ex U2-
(3)
As result, the cumbersome The condition in inequality 3 involves two parts:
will be upper bounded by the nice sum
I(Y; ; &a ExI+11, & X) s
& Uk-1)
Conditioning on the true input U provides more information about & than condi- tioning on an approximation (E4-1.1,X) X).
2. T(Y: & & Uk-1) S T(U + W; E Uk-1)
The immediate output Us + W provides more information about & than the final output Y does.
1) holds for all proxies of the form غ (É,,..., Ekx where E. T E, for + We prove this result explicitly in Lemma 19 in Appendix E. It is rather intuitive that the pristine data pair (Uk-1,Y) would provide more information about & than (Uo, Ex-1:1, to be lost through the noisy reconstruction of UR-1 from Uo, Ex-1:1-
1 Y) would. We expect some information
2) will not hold exactly for our two environments. IIY; Ex Ek.k41, Uk-1) will not always be S I[U + W, Ex Ex, Up- However, I(Y; & EK Un-1) will be S very natural upper bound

---

of + W,& Es, Uk-1), which we detail in Lemma 20 of Appendix E. Intuitively Uk + W will provide more information about & than Y so long as in expectation, the layers fk+1--..,. fx don't t amplify the scale of the output. If they were to amplify the scale, then the signal to noise ratio of Y would look more favorable than that Uk + W, leading to potentially information.
Concretely, if
( 8thh ( m=zy== S 1,
L= sup E
then we will have the desired result. The expectation here taken over the randomness in the function f(A), For both of our prototypical data generating processes, this condition is met.
I can be thought of as expected squared Lipschitz constant of f((), The set of random functions for which L S. 1 is much broader than say I-Lipschitz functions because of both the square and the expectation. For example, f() = Ax is A||p-Lipschitz but if say cov [A] In. then -= 1.
For multilayer processes for which we can establish relationship akin inequality 3. have the following relationship between the rate-distortion function H. (Eka) and the individual rate- distortion functions H. (Ex) (proof in Appendix E).
Theorem 10. multilayer rate-distortion bound For all E E 0², c O, if is a multilayer environment such that for all k E (I,..., K} and 8 2 O, there exist E s.1.
(E;;&lEK:HHH) E,,, S I(Ux W Uk-1) $ where W -N(0,02)), then
(EKa) $ Σ H (Ex).
Am
6.3 Sample Complexity Bounds for Multilayer Environments
With Theorem 10 in place, we present the two main results (proof's can be found in Appendix F). Theorem 11. (relu neural network rate-distortion and sample complexity bound) For all N, K E++ and o², e if multilayer environment EK.1 is the deep ReLU network with input X Q + Rd s.t. V[X] Ia and output Y -NU,, then
= KN2 + dN
H.. (E ô
While this a parameter-count based bound in nature, it improves upon existing sample complexity results based VC Dimension Bartlett et al. Harvey al. [2017] which under notation would be D(K2N2 N2 + KdN). Note however that our result is average case while theirs holds with high probability. Regardless, the reduction in sample complexity by factor of K is notable.
For nonparametric deep networks, we have the following result.
Theorem 12. (nonparametrie network rate-distortion and sample complexity bound) For all dd N, M, K E Z4+, d².c 2 O, if multilayer environment εKa is the deep nonparametric network with input X Q + Red and output Y ~ NUK,, ,,ok,,²) o²), then
cK2 cK2 In(2N) T 2cK2 (n(2))(2N)
(.(E))) S
20
o²e²
The nonparametric network's 's sample complexity grows only quadratically in K not exponentially or high-order polynomially as in Bartlett et al. [2017] and Wei and Ma [2019] respectively.
7 Closing Remarks
We have introduced a novel and elegant information-theoreti framework for analyzing the sample complexity of data generating processes. We demonstrate its usefulness by proving two new theo- retical results that suggests that is possible to leam efficiently from data generated by deep and nonparametric functions.

---

Beyond the scope of this paper, we believe that the flexibility and simplicity of our framework will allow for the analysis of machine learning systems such as semi-supervised learning, multitask learning, bandits and reinforcement learning. We also believe that many of the nuances empir- ical deep learning such as batch-normalization,, pooling, and structured input distributions can be analyzed through the average-case nature of information theory and powerful tools such as the data processing inequality.
Notably omitted from this paper is any analysis of practical algorithms for estimating the environ- ment. We have assumed perfect Bayesian inference, while in practice, particular neural network architectures are used together with stochastic gradient descent. Whether practical algorithms of this sort can achieve sample complexity bounds similar what we have established for our multi- layer environments remains interesting subject for future research. Our discussion of suboptimal algorithms and misspecification in section 3.1 and Appendix B provide some starting points for such pursuit.
Acknowledgments and Disclosure of Funding
We thank Andrea Montari for suggesting that information-theorriic tools may be helpful to under- standing the dependence of sample complexity on depth. Financial support from Army Research Office (ARO) grant W911NF20 and the National Science Foundation (NSF) Graduate Re- search Fellowships Program (GRFP) are gratefully acknowledged.
10

---

References
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pages 254-263. PMLR, 2018.
Peter Bartlett, Dylan Foster, and Matus Telgarsky. networks. Advances in Neural Information Processing Systems, 30:6241-6250, 2017.
margin bounds for neural
Peter L Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear vc-dimension bounds for piecewise polynomial networks. Neural computation, 10(8):2159-2177) 1998.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecom- munications and Signal Processing). Viley-Interssceenc,, USA. 2006. ISBN 0471241954.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008, 2017.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceed- ings of the s1 Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 297-299. PMLR, 06-09 Jul 2018. URL htttt:::/prrceedingg mlr. .pres/ v75/ 775/golowich1e6 html...ml..
Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight VC-dimension bounds for piecewise linear neural networks. In Satyen Kale and Ohad Shamir, editors. Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 1064-1068. PMLR, 07-10 Jul 2017. URL https: /ttpe:://rrcceee http///ooceeen..c..o mml. walr.pres//ee press/v65/ harvey17a. html.
David Haussler. Decision theoretic generalizations of the pac model for neural net and other learning applications. Information and Computation, 100(1):78-150, 1992. ISSN 0890-5401. doi: http:///o.aany/ll.lllloooooss100
URL http:/wwww.cceeeedieec....
David Haussler, Michael Kearns, and Robert Schapire. Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension. Machine learning, 14(1): 83-113, 1994.
Vaishnavh Nagarajan and Zico Kolter. Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing voiss-resilience. In International Conference on Learning Representa- fions, 2018
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pages 1376-1401. PMLR, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-Bayesian approach to spectrally-normalzzed margin bounds for neural networks. In International Conference on Learn ing Representations, 2018
Matthew Nokleby, Ahmad Beirami, and Robert Calderbank. Rate-distortion bounds on bayes risk in supervised learning. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 2099-2103, 2016.
doi: 10.1 2..10099STTT2201.554411
Daniel Russo and James Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 66(1):302-323, 2019,
Ravid Shwartz-Zr Ziv and Naftali Tishby. Opening the black box of deep neural networks via informa- tion. arXiv preprint arXiv:1003.008/1 2017.

---

Naftali Tishby, Fernando C Pereira, and William Bialek. The information bottleneck method. arXiv preprint physicx/0000557, 2000.
Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lip- schitz augmentation. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019. URL https: httpp//ooddn...nnuuuee httpss.ccpppppp/e/ee /c/ppper//019/fille/ Oe795 0075540081440000dff7777622222222 Papseee pdf.
Aolin Xu and Maxim Raginsky. Information theoretic analysis of generalization capability of learn- ing algorithms. arXiv preprint arXiv: /00/:00090007009 2017.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No] or [N/A]. You are strongly encouraged to include justification to your answer. either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Section 7
(c) Did you discuss any potential negative societal impacts of your work? [N/A] It math paper.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state full set assumptions all theoretical results? [Yes] Either the theorem statement or in the respective section of the paper.
(b) Did you include complete proofs of all theoretical results? [Yes] In the Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report enror bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
12

---

(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "o42_yD1mGdQ", "reviewer": "Reviewer_B2L8", "summary": "This paper proposes an information-theoretic framework that builds on rate-distortion theory for analyzing sample complexity of learning with an average-case notion of regret based on KL divergence. Under this framework, analysis and complexity bounds for two specific network setups are also provided.", "questions": "My questions are outlined above.", "limitations": "No.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The main results motivated by the average-case analysis are interesting.\n2. The analysis for two network environments is interesting.\n\nWeaknesses:\n1. Lack of empirical justification.\n2. Organization of the paper could be improved. \n\nDetails:\n1. The main weakness in my opinion is the omission of any experimental justification for the proposed framework. Particularly, I am really curious about how the average-case analysis that this framework builds on holds in reality. For example, to what extent does the quadratic depth dependence hold? Since the paper already provides relevant analysis for some prototypical networks, I think it would strengthen the paper a lot more if some preliminary results can be provided to demonstrate the relevance of this framework in the real world. \n2. This paper builds on rate-distortion theory but related work provided in the paper is quite limited. A dedicated section of preliminaries would help improve the readability of the paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hq0iRurxD-G", "reviewer": "Reviewer_ePAL", "summary": "The authors proposed a novel information-theoretic framework with newly introduced notions of regret and sample complexity. The work is motivated by the gap between empirical success of generalizability of the deep neural networks and previous results on their complexity. By assuming an optimal agent and replace the out-of-sample error with average cumulative error, they provide general bounds on regret and sample complexity via rate-distortion theory. They further study the deep ReLU networks and deep non-parametric networks with the theory established earlier.", "questions": "The results in the paper are based on the \"optimality\" assumption, which may not be the case in the training process. This will change the monotonicity of the prediction errors. Can the authors elaborate on this?And does the current framework also provide a worth-case sample complexity?", "limitations": "The authors have included discussions on limitations and future directions in their paper.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors focus on the average case rather than the worst case scenarios, and thus are able to show sample complexity grows linear or quadratic in network depth. This brings the theoretical understanding closer to what is observed in practice. The introduction of new notions are very intuitive and easy to understand. \n\nThe reference style needs to be fixed. Many of the references are not covered by parentheses properly (use \\citep{} for example), so do equations (can use \\eqref{}). Minor typos are observed, like line 77, \"consider an our framework\". And the presentation of the paper could be greatly improved if the authors add more cross references in the paper when mention some equations/notations they defined earlier in the paper. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3VSCZoJRhD-", "reviewer": "Reviewer_BqHU", "summary": "This work proposes a novel information-theoretic framework for understanding deep learning. Under the proposed framework, the sample complexity of learning a deep neural network scales linearly with the number of layers rather than exponentially, a problem conventional PAC bounds suffer from.\n\nThe framework assumes target deep function can be treated as a sequence of “environments” — each environment transforms the output of the previous environment. Learning can be reduced to minimizing the mutual information between a sequence of proxy environments (i.e., the deep neural networks used to do the learning) and the true environment via samples from the true environment. The key insight is that, under some assumptions, the average-case error can be decomposed as a layer-wise sum of mutual information between the proxy environments and the true environments.", "questions": "See Strengths And Weaknesses", "limitations": "Most limitations are addressed.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Using the average-case analysis is crucial for the reduction from exponential sample complexity to linear in depth. Introducing information-theoretical analysis into understanding function approximation feels like a promising direction and may lead to future works that further utilize tools from information theory to understanding deep learning.\n\n**Problems**\n- More discussion of the connection to information bottleneck would be nice to have because the characterization that it is just an “optimization” method is in my opinion inadequate. It is fundamentally a study of “representation” and it also provides sample complexity.\n- Does not account for implicit regularization and inductive bias, both of which are key ingredients of deep learning, and it’s not clear how one could do it.\n- Following the previous point and as pointed out by the authors themselves, the resulting bound is essentially a parameter counting bound which is better than VC by a factor of depth. This reduction on a high level comes directly from the fact of the average case nature of the analysis; however, I am not convinced that this reduction is what is needed to fully understand why deep learning works. Notably, this bound is likely still loose for all intents and purposes and probably would not correlate well with generalization error [1,2].\n- Following the previous point, there is currently no empirical verification for the assumptions made. It would be good to see some experimental results that demonstrate the validity of the assumptions.\n- Can you also take advantage of the fact that the input $X$ usually has low entropy? As it stands, the framework only makes assumptions about the ground truth labeling function.\n\n\n\n**Typo**\n-  244. “Leading to potentially .. information” missing an adjective?\n\n**Reference**\n1. Fantastic Generalization Measures and Where to Find Them. Jiang & Neyshabur et al.\n2. In Search of Robust Measures of Generalization. Dziugaite & Drouin et al.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-5TjlZnTl-B", "reviewer": "Reviewer_rFcg", "summary": "The paper addresses a problem in Machine Learning very much deserving attention: to develop an information theoretic basis for Deep Learning (DL) Networks. Still largely heuristic, DL  would greatly benefit from an information theoretic perspective to help understand the complexity variation (or potentially required) of  a network with   breadth and depth. It promises in particular, an ability to consider several layers (i.e. varying depth) without necessarily invoking  an exponential dependence on the depth, with potentially infinite breadth with a constrained boundedness on the sum of the parameter weights.\nOverall the paper is clearly written with a good description of its objectives and an acceptable review of the current lay of the land.\n ", "questions": "1. Given that I was not privvy to the details of the proofs (no appendices), how does the independence assumption in IID property weaken the result?\n2. For a given distribution, and if one could associate an energy functional to the data (as in the Gibbs distribution expression), could one guide the analysis in estimating the (even a bound) depth complexity?\n", "limitations": "I have not really seen any development/statement of any significance in the societal impact direction.\nThey did mention that their paper had not addressed any practical issue related to their development. \n\n In addition, this reviewer did not think that the title of the paper was a adequately matched reflection of the results in the paper.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The goal of the paper is very legitimate and hence worthy, and understanding the complexity of a network (sample and parameterization) would be in the same vein as model order estimation/complexity in the linear world. This is a problem, as duly noted in the paper, investigated by a number of researchers and each with their set of assumptions.\nThe objectives are nicely motivated and clearly stated.\n\nWeaknesses:\nWhile a good effort is expended at maintaining some rigor, which is very welcome in this area, given the plethora of data-driven and data-dictated efforts, I would sadly add that some sloppy notation and some mathematically erroneous/misleading  statements were strewn here and there. While I could not verify the proofs to the theorems, since I had no access to the Appendices, I found some of the key assumptions that i inferred to be key to the claimed strength of the results were also impractical and hence of limited interest (e.g. IID property of data, which is certainly not the case in practice).\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept