acceptodds
Under review as a conference paper at ICLR 2027

Why and When Deep is Better than Shallow: Implementation-Agnostic State-Transition Model of Deep Learning

Abstract

We ask when adding hidden layers improves generalization, in a model that keeps the layers fixed and varies only their number. A hidden layer is a self-map of a state space, a depth- network composes at most hidden layers with an output layer, and depth is compared within the nested family built from one class of hidden layers; this compares a deep network with shallower networks built from the same layers, not with wider ones. Our message is that the statistical cost of depth is the metric entropy of the set of compositions. The estimation error is bounded by an entropy integral over with constants that do not depend on the depth, and the bound is matched from below when the output layer can see the hidden states. For Lipschitz layers on a bounded state space this entropy grows at most polynomially in , and it stays bounded, or grows only like , under contraction, equicontinuity, or nilpotent structure. Balanced against the approximation error, this gives depths that grow with the sample size, and it separates the models whose estimation error is independent of the depth from those whose estimation error grows with it. Deep ReLU networks, unrolled solvers, and chain-of-thought computation are worked out; for the last two the number of steps is derived rather than assumed. All statements are machine-checked in Lean 4.

Primary area:
learning theory
Keywords:
depth, generalization, metric entropy, covering numbers, Rademacher complexity, statistical learning theory, state-transition model, compositions of Lipschitz maps, unrolled solvers, chain-of-thought, Lean 4

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.60 over 5 reviews, above 70% of the others.
Reviewer_kN6wOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3(+1)
Soundness
3(+1)
Read review
Paper summary

The paper models depth through compositions of maps from a fixed class of state transitions, followed by an output map. It relates generalization bounds to the empirical metric entropy of the resulting composition class and separates approximation, implementation, and estimation terms. It gives a layerwise covering bound and discusses mechanisms such as contraction, equicontinuity, controlled algebraic growth, separation, and memory-preserving expansion. These mechanisms are used to derive depth-dependent complexity profiles and bias-estimation tradeoffs. The paper develops examples for ReLU networks, iterative solvers, symbolic scratchpads, and refinement or integration schemes. Its validation consists primarily of theoretical arguments and computed illustrations. The conditional complexity lower bound is not a lower bound on the risk of every learning algorithm.

Critical strengths
  • Unified complexity framework. The composition-class formulation provides a useful common language for connecting state-transition structure to statistical complexity. Separating implementation error from approximation and estimation makes the scope of the abstract model clearer and helps compare examples with different realizations.

  • Empirical entropy of branching computation. The empirical covering argument for branching symbolic computation in Appendix L is informative. Lemma 15 distinguishes exponential growth in the uniform metric from the much smaller complexity visible on a finite sample, yielding an upper bound O(log⁡(k+1))O(\sqrt{\log(k+1)}) for the empirical entropy integral as depth increases. This is a concrete example of why counting all distinguishable compositions can overstate their statistical cost.

Critical weaknesses
  1. The general saturation profile lacks an explicit integrability condition. Theorem 3(i) establishes a depth-uniform covering number at every fixed positive resolution, which alone does not ensure that the entropy integral is finite near zero. Proposition 5(i) explicitly assumes an integrable envelope, while Corollary 2 states the depth-independent estimation profile without making that condition explicit. Proposition 8(ii) similarly concludes a constant entropy integral from compactness and non-expansion. A sample-independent quantitative bound is needed for the claimed statistical rate by this argument. Some specific examples supply such bounds, so this concern addresses the general implication rather than invalidating all saturation examples.

  2. The expanding ReLU example does not establish the advertised sharpness. The main ReLU example and Proposition 8(iii) associate the linear-in-depth entropy-integral upper bound with an attaining construction. The stated two-generator expand-and-reset example supplies an exponential uniform packing, and the proposition gives only a square-root-in-depth lower bound. Compositions of these two fixed maps up to depth k number at most 2k+1−12^{k+1}-1, so their entropy integral on a bounded state space is at most of order k\sqrt{k}. This subclass therefore cannot establish a linear matching lower bound. The square-root-in-depth upper bound just derived applies to the two-map subclass and cannot automatically be extended to the full parameterized ReLU class. A matching linear-in-depth lower bound for that full class requires additional evidence, and the separate general memory-preserving construction is not by itself a matching realization for the specified ReLU class.

  3. A logarithmic factor disappears between the layerwise theorem and the profile summary. For fixed parametric dimension p and non-expanding layers, Theorem 2 gives an entropy-integral upper bound of order kplog⁡k\sqrt{kp\log k}. Section H.2 likewise lists an estimation term of order klog⁡k/n\sqrt{k\log k/n}. Corollary 2 instead attributes a k/n\sqrt{k/n} profile to this layerwise bound and says the profiles hold up to constants. A factor growing as log⁡k\sqrt{\log k} cannot be absorbed into a depth-independent constant. The smaller profile might hold under stronger structure or an improved argument, but it does not follow from the displayed layerwise bound alone. This discrepancy matters for the precision of the claimed rates and depth recommendations, without showing that a sharper result is impossible.

  4. The depth-selection discussion conflates saturation with slow growth. Figure 2's left panel explicitly uses a root-logarithmic estimation term, yet its caption describes the marked depth as a threshold beyond which deeper models are as good in the bound. That conclusion is justified for a depth-independent estimation bound, but not in general for the displayed term log⁡k/n\sqrt{\log k/n}, which continues to increase with depth. For example, with exponentially decaying bias, taking depth k = n instead of order log n gives an estimation term of order log⁡n/n\sqrt{\log n/n}, rather than the balanced root-log-log rate. The discussion below the figure correctly explains the saturated case, so the problem is the unqualified transfer of this advice to the root-logarithmic example. The admissible range of depths or intended approximation needs to be stated to make the practical depth-selection message reliable.

Questions for authors
  1. Integrable envelope. What sample-independent integrable entropy envelope justifies the saturation profile in Corollary 2 and Proposition 8(ii)? Please identify any assumptions beyond compactness and equicontinuity and distinguish the general claim from the specific examples with explicit quantitative entropy bounds. This affects whether the advertised estimation rate follows under the stated hypotheses.

  2. Matching ReLU lower bound. Is there a matching entropy-integral lower bound linear in k for the expanding ReLU class in Proposition 8(iii)? Please explain what establishes more than square-root growth beyond the stated two-generator example, or distinguish the proved lower bound from the upper bound and revise the attainment claim. This affects the claimed sharpness.

  3. Logarithmic factor in the non-expanding case. How does Corollary 2 obtain a root-k estimation profile from Theorem 2 when Theorem 2 and Section H.2 retain a square-root-log-k factor? Is the corollary intended to suppress logarithmic factors rather than hold up to constants, or is there a sharper bound under additional conditions? Please clarify the corresponding interpretation of the balancing rates.

  4. When is deeper equally good? For Figure 2's left panel, does the threshold interpretation refer to true saturation or to the displayed root-logarithmic profile? Under what range of depths does the claim that deeper models are as good hold? Please reconcile the caption with the growing estimation term and distinguish this from the valid depth-independent case. I am asking about the existing depth-selection claim, not requesting new empirical benchmarks.

2 comments

Thank you for the precise comments. All four points are correct: in each, the summary in the main text departed from the precise statement in the appendix. The appendix statements and the formalized statements are unchanged; we correct the main text and the wording of Proposition 8 as follows.

W1 / Q1 (integrability in the saturated profile)

Theorem 3(i), (ii) gives the finiteness of the depth-uniform bound N∞(ε):=sup⁡kN(B(k,F),d∞,ε)N_\infty(\varepsilon):=\sup_kN(B(k,F),d_\infty,\varepsilon) at every resolution. The depth-independent profile n−1/2n^{-1/2} requires in addition that V∞:=∫0Dˉlog⁡N∞(ε)dε\mathsf V_\infty:=\int_0^{\bar D}\sqrt{\log N_\infty(\varepsilon)}d\varepsilon is finite. This is the assumption of Proposition 5(i); it was lost when we summarized the result in Corollary 2 and in Proposition 8(ii). Integrability is the only assumption needed beyond compactness and equicontinuity.

  • General claim. Integrability holds automatically for uniformly contractive parametric layers whose invariant set is a bounded finite-dimensional set (log⁡N∞(ε)≲plog⁡2(1/ε)\log N_\infty(\varepsilon)\lesssim p\log^2(1/\varepsilon)). Under equicontinuity alone (Theorem 3(i)) it is an additional assumption.
  • Examples with explicit bounds: Proposition 8(i), Lemma 13, and App. M.2.
  • Proposition 8(ii) will read: at every resolution the covering numbers are bounded uniformly in the depth; if the envelope is integrable, then Vk(S)≤V∞\mathsf V_k(S)\le\mathsf V_\infty (the formalized statement has this assumption); the quantitative bound that holds without it is the layerwise O(kplog⁡k)O(\sqrt{kp\log k}).

W2 / Q2 (the expanding ReLU example)

We have not proved a lower bound that is linear in kk for FΛF_\Lambda. We withdraw the word "attained" and state separately what is proved.

  1. Upper bound. For Λ>1\Lambda > 1, Vk(S)=O(kplog⁡Λ)\mathsf V_k(S)=O(k\sqrt{p\log\Lambda}) (Theorem 2).
  2. Lower bound for the entropy in the uniform distance. FΛF_\Lambda contains two expand-and-reset blocks, and N(B(k,FΛ),d∞,ε)≥2kN(B(k,F_\Lambda),d_\infty,\varepsilon)\ge2^k for ε<1/16\varepsilon < 1/16. Hence for Λ>1\Lambda > 1 the covering numbers in the uniform distance do not saturate. This inequality is what is formalized.
  3. Entropy on a sample. As you note, the two maps have at most 2k+1−12^{k+1}-1 compositions and cannot give a lower bound beyond k\sqrt k. Moreover, the counting argument of Lemma 15 applies to these two maps, because compositions of the same length differ from a constant map only on pairwise disjoint sets of inputs. On every sample, therefore, the covering number is at most 3+∑j≤kmin⁡{2j,n,ε−2}3+\sum_{j\le k}\min\lbrace2^j,n,\varepsilon^{-2}\rbrace and the entropy integral is O(log⁡k)O(\sqrt{\log k}). We also remove the sentence of Proposition 8(iii) that claims growth of order k\sqrt k on a sample containing the probe points. These blocks are thus a second instance of the phenomenon of Sec. 6.3: entropy linear in kk in the uniform distance and logarithmic on a sample.
  4. Attainment of the linear order. The layerwise covering bound is attained by memory-preserving expansion (Theorem 3(v), Corollary 7). That construction lives on an infinite-dimensional state space and, as you say, is not a realization within FΛF_\Lambda. For piecewise-linear networks without constraints, the VC dimension is of order WLWL up to logarithmic factors (Bartlett et al., 2019), which corresponds to the same linear order for W=kpW=kp and L=kL=k.

The places to be corrected are Example 1 ("attained by ping-pong blocks" is replaced by item 2), Proposition 8(iii), the summary of the examples (App. J), and the list of profiles (App. H.2, where we state that E2 is matched by Corollary 3 only when the separation is visible on the sample).

W3 / Q3 (logarithmic factor)

The layerwise bound for non-expanding parametric layers is klog⁡k/n\sqrt{k\log k/n}, and no sharper estimate was intended. The revised Corollary 2 and Sec. 4.2 display the log⁡k\log k in the formulas and say "up to logarithmic factors" in the text. For γ=1\gamma=1 the balance becomes k∗≍(n/log⁡n)1/(2β+1)k^\ast\asymp(n/\log n)^{1/(2\beta+1)} with the rate (log⁡n/n)β/(2β+1)(\log n/n)^{\beta/(2\beta+1)}. The profile k/n\sqrt{k/n} without a logarithm holds for classes consisting of finitely many layers (Theorem 3(iv), Proposition 5(iii)).

W4 / Q4 (the threshold reading of the left panel of Fig. 2)

The threshold reading is valid only when the estimation bound does not depend on the depth. For the term log⁡k/n\sqrt{\log k/n} drawn in the left panel of Fig. 2, the bound keeps increasing beyond k∗k^\ast and equals log⁡k/log⁡k∗\sqrt{\log k/\log k^\ast} times its value at k∗k^\ast. For k≤(k∗)ck\le(k^\ast)^c it therefore stays within the factor c\sqrt c. In the EL case k∗≍log⁡nk^\ast\asymp\log n, so the rate log⁡log⁡n/n\sqrt{\log\log n/n} is kept for depths up to a polynomial in log⁡n\log n, while k=nk=n gives log⁡n/n\sqrt{\log n/n}, as in your example. The revised caption and the corresponding paragraph of Sec. 5 state this range and restrict "deeper models are as good" to the depth-independent case. The figure itself is unchanged.

Thank you for the detailed response. The clarification of the integrability condition addresses my concern about the saturation profile. I also appreciate the withdrawal of the unsupported ReLU sharpness claim and the distinction between uniform and empirical entropy in that example. The correction of the logarithmic factor and the corresponding balancing rates, together with the clarified scope of the threshold interpretation in Figure 2, addresses my remaining concerns.

Please ensure that these corrections are consistently incorporated throughout the revised manuscript. With the claims appropriately qualified, I consider the unified framework and empirical entropy analysis valuable contributions. These clarifications sufficiently address my main concerns, and I am raising my rating from 2 to 3 (Weak acceptance).

Reviewer_UGhnOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper considers a general setting of hierarchical models. Each layer of the model is treated as a map from a state-space to itself, repeated at most kk times (the layer functions can differ, they just map into the same state space), followed by an output map coming from a different family of functions. The hypothesis class in the learning problem is made of such deep models, the learning objective is to learn a predictor from i.i.d. input-label pairs, under a set of assumptions. The main contribution of the paper is a theoretical upper bound on the excess population risk, where the bounding term contains the implementation error, the approximation error, the optimization error and the Rademacher-complexity of the hypothesis class. This complexity term is then theoretically upper and lower bounded under certain additional assumptions. These upper bounds contain a certain function of the so-called metric entropy (a.k.a. the logarithm of the covering number) of the class of composition of functions realizing the hidden layers of the model. In some scenarios, the upper bound on the complexity term is independent of the depth, while in some other scenarios it is used to illustrate a bias-variance trade-off via the depth as a funciton of the training sample size. The intuition behind the theorems are illustrated numerically on two toy examples in the main text.

Critical strengths
  • The research idea is well motivated, understanding the role of depth for various model classes is crucial and a comprehensive, general theory is missing from the literature. The considered abstract model definition is general enough to include many kinds of hierarchical models. Most of the assumptions and learning framework are standard in the literature of Rademacher based generalization bounds.

  • The theorems are precisely written (with references to the appendix), and mostly well illustrated in the main text. A lean formalization of the proofs are included as supplementary material (although I can't judge if this formalization is correct or not). The proofs are comprehensively presented in the appendix, while the main ideas are also highlighted.

  • Several scenarios are presented where the bounding term can be estimated. In particular, in some cases lower bounds on the Rademacher complexity are also presented which is to my knowledge not that common in the literature.

  • The paper has an important example where, at a fixed resolution, the uniform covering number grows exponentially with depth, while the empirical covering number grows at most linearly (Example 2, Section 6.3). This is important because in the literature often uniform covering number arguments are employed.

  • The paper puts a lot of work in examining the connection between the established bounds and the depth of the model class.

Critical weaknesses
  1. Some other related work should be cited. First, there are those works which deal with in some sense general setups (i.e. not concrete choices of model architectures) and derive similar results. I am only aware of a few, such as https://arxiv.org/pdf/1905.03684. Some results simlar to Theorem 1 / (ii) in the current manuscript are in https://arxiv.org/abs/1411.2635 and https://arxiv.org/abs/2304.14474. Even considering the old Bartlett-Mendelson paper, is there any relation between the risk bounding results in Theorem 1 / (i) and those results?

  2. The paper rightfully claims that its model definition contain many popular architectures: ``unrolled optimization and fixed-point solvers, deep equilibrium models, neural ODEs, the samplers of diffusion and flow-matching models, Picard-type neural operators, and chain-of-thought reasoning in language models''. I am personally aware of many papers that proves generalization bounds for many of these architectures, however those are neither cited, their bounds are compared to the relevan special cases of the bounds in this manuscript. Some deep ReLU literature is cited, and there are some comparisons for ReLU network, however it would be beneficial to see if the current paper recovers those bounds under the same assumptions or not.

For the other architectures, there are generalization bounds for dynamical systems in https://arxiv.org/abs/2312.09793 (might not be directly comparable), for inverse problem solvers in https://arxiv.org/abs/2010.15658 and https://arxiv.org/abs/2304.09802, for implicit networks https://arxiv.org/abs/2410.07427, deep equilibrium models in https://openreview.net/pdf?id=VcB4QkSfyO, neural ODEs https://arxiv.org/abs/2305.06648 and https://arxiv.org/abs/2401.16655, etc.

In the appendix I only found references for Picard operators and CoT transformers.

  1. I found some claims in the main text that I cannot see how the theorems support.
  • ``For Lipschitz layers on a bounded state space this entropy grows at most polynomially in kk'' (abstract). However, Theorem 2 proves this only for parametric FF when log(N(F,d∞,ε))<plog(1/ε)+constantlog(N(F, d_\infty , \varepsilon)) < p log(1 / \varepsilon) + constant. For the nonparametric case, Theorem 2 and the discussion afterwards say exponential entropy (line 250) and has the term O(kΛqk/2)O(\sqrt{k}\Lambda^{qk/2}). Why does the polynomial upper bound hold then?

  • ``The estimation error is independent of the depth when composition creates no new distinguishable maps, and it grows with the depth when it does.'' (line 65) The theorems give upper bounds on the excess risk using Rademacher complexity, and there is a Rademacher lower bound. How is this a lower bound on the estimation error? In other words, why does growing of the bounding term imply growing of the error?

  • The previous argument goes for the title of the paper as well. In my understanding, the results say sth about ``why and when the upper bound for deep is better than the upper bound on shallow''.

  • The discussion after Theorem 2 says the product of layerwise norms enters the bound only through the diameter, which is a bit surprising to me. I tried to understand the proof which referred to Proposition 6 which referred to Proposition 7. Based on what I see there and the Remark afterwards (lines 2453-2463) to me it seems that the 11+∑iΛi\frac{1}{1 + \sum_i \Lambda^i} term in (5) is there exactly to deal with the propagation of each layer's approximation error. This aligns with my understanding of the proof of Proposition 7, however then the terms Λi\Lambda^i enter the bound via the covering numbers as well, not just the diameter.

  1. According to Corollary 2, it is possible to bound 12LHVk(S)/n=O(1/n)12 L_H V_k(S) / \sqrt{n} = O(1 / \sqrt{n}) which is common in PAC literature, and it refers to Proposition 5. However, proposition 5 / (i) explicitly assumes N(B(k,F),d∞,ε)≤N∞(ε)N(B(k,F), d_\infty, \varepsilon) \leq N_{\infty}(\varepsilon) and also ∫0Dˉlog(N∞(ε))dε<∞\int_0^{\bar{D}} \sqrt{log(N_\infty(\varepsilon))} d \varepsilon < \infty. I did not find the definition of N∞N_\infty, so I guess this is an assumed common upper bound, i.e. independent of the depth kk. I do not see this assumption anywhere in the main text. Does the corollary's O(1/n)O(1 / \sqrt{n}) rate hold without this? If not, it should be explicitly stated there and also discussed.
Questions for authors
  1. Please find related literature of the most important model classes your framework covers (see 1. and 2. under Critical weaknesses) and compare their results to your bounds, at least in O(⋅)O(\cdot) and in terms of depth and relevant hyperparameters and assumptions.

  2. Please address how the claims in the texts are supported by the results under criticla weaknesses / 3.

  3. Please address if Corollary 2 needs that extra assumption and if it does, discuss how restrictive it is.

  4. The term ``statistical cost'' is in the intro and abstract many times without a definition. Is this a statistical learning term that is well known or did you come up with it? Depending on the answer either add a citation to it, or define it at its first occurence (I believe this is also in the abstract).

  5. Phrases like ping-pong condition and Ascoli's theorem should have an immediate reference / link to the appendix where they are defined / cited (not just see Appendix F).

  6. While I found some discussions on the limitations of the paper and the size of the constants, these have to be puzzled from many parts of the Appendix. I think a straightforward limitations (and maybe future work) section would be nice (at least in the appendix with a reference to it in the main text). Can the bounds in Theorem 1 be nonvacuos in practice?

5 comments

Response (1/2): comparison with related work (W1, W2, Q1)

Thank you for the detailed review and for the valuable references. We will cite all of them in the revised version and add the comparison below, in more detail, to App. B.

W1 (work in general settings)

  • Bartlett and Mendelson (2002). Theorem 1(i) is the standard risk bound by Rademacher complexity that goes back to this paper. We only add the implementation error and the approximation error as separate terms.
  • Maurer (2014); Chu and Raginsky (2023). The chain rule G(F(Y))≤C1L(F)G(Y)+C2D(Y)R(F)+G(F(y0))G(F(Y))\le C_1L(F)G(Y)+C_2D(Y)R(F)+G(F(y_0)) for composite classes, and its Rademacher version. Theorem 1(ii) has the same structure when the outer class is the output-layer class HH and the inner set is B(k,F)B(k,F) on the sample. Three differences: (a) If the chain rule is iterated over KK layers, the constants accumulate as C1K−k∏jL(Fj)C_1^{K-k}\prod_jL(F_j), exponentially in the depth (Maurer, Sec. 3.4). We split once, at the output layer, and treat the depth through the metric entropy of B(k,F)B(k,F), so the constant is 12LH12L_H at every depth. (b) We measure the inner complexity by the entropy integral. In general it is weaker than G(Y)G(Y), but its growth in the depth can be computed (Sec. 4) and matched from below (Theorem 1(iii)). (c) The state space may be any metric space, which covers the symbolic example of Sec. 6.3.
  • Wei and Ma (2019). They use the norms of the hidden layers and of the interlayer Jacobians on the training data, and replace the dependence on the product of weight norms by a polynomial in the depth. The corresponding sample-level quantities in our paper are the empirical diameter Dk(S)D_k(S) and the empirical covering numbers of B(k,F)B(k,F). On a bounded state space and for parametric layers, Λk\Lambda^k enters the covering numbers only through its logarithm (Theorem 2).

W2 (bounds for specific architectures)

  • Golowich et al. (2018): d\sqrt d for layers of bounded Frobenius norm (Theorem 1), and a depth-independent bound at the rate n−1/4n^{-1/4} (Corollary 1). Ours: kplog⁡k\sqrt{kp\log k} for non-expanding parametric layers (Theorem 2; valid for any Lipschitz layer class, at the price of the dependence on pp), and depth-uniform covering numbers at every resolution (Theorem 3(i)). The rate n−1/2n^{-1/2} requires an integrable envelope (W4 in response 2/2).
  • Behboodi et al. (2020): unfolded ISTA with a dictionary shared by all layers; Dudley's integral gives log⁡L\sqrt{\log L} in the number of layers LL. Ours: for equal-step schemes with shared weights the covering number is at most 1+kN(⋅)1+kN(\cdot) and the profile is log⁡k\sqrt{\log k} (Lemma 18); without sharing it is kplog⁡k\sqrt{kp\log k}. The perturbation estimate is the same telescoping argument.
  • Shultzman et al. (2023): for ISTA and ADMM networks, a bound that is nonincreasing in the depth under constraints on the weight norms. This corresponds to our saturation for contractive and non-expanding layers.
  • Fung and Berkels (2024); Pabbaraju et al. (2021): bounds without a depth term for contractive, respectively strongly monotone, implicit networks (of order p/N\sqrt{p/N} in the former; depending on the strong-monotonicity parameter mm in the latter). Ours: saturation with the same contraction factor 1−hμ1-h\mu (Lemma 16, Proposition 11), and in addition the bias (1−hμ)k(1-h\mu)^k of finitely many iterations and k∗≍log⁡nk^\ast\asymp\log n.
  • Marion (2023): for residual networks scaled by 1/L1/L and for neural ODEs, a depth-independent bound under the constraint that the weights are Lipschitz in the depth (it contains a term n−1/4n^{-1/4}). In our paper this is fixed-horizon integration (Lemmas 17 and 18, Proposition 12): the estimation term is log⁡k/n\sqrt{\log k/n} plus the entropy integral of the class of drifts, and we add the bias k−pk^{-p} and k∗≍n1/(2p)k^\ast\asymp n^{1/(2p)}.
  • Hanson and Raginsky (2024): the Rademacher complexity of continuous-depth neural ODEs via Chen–Fliess series; there is no depth parameter. It is complementary.
  • Eringis et al. (2024): a PAC-Bayes bound for stable RNNs that does not grow with the number of steps. The mechanism is the same as our saturation by contraction, but the data are non-i.i.d. time series and the setting differs.

What is new relative to these works

The works above bound the generalization gap at a given depth, architecture by architecture. We add four things.

  1. One quantity, the metric entropy of B(k,F)B(k,F), yields all the depth dependences that appear above (depth-independent, log⁡k\sqrt{\log k}, k\sqrt k, kk) and says which structure gives which (Theorems 2 and 3).
  2. Lower bounds: the converse for the complexity (Theorem 1(iii)) and a construction that attains the layerwise covering bound (Theorem 3(v)).
  3. The approximation side and the balancing depth k∗(n)k^\ast(n); the number of steps is obtained as a consequence (Propositions 9–12).
  4. The gap between the entropy in the uniform distance and the entropy on a sample (Lemma 15).

Response (2/2): claims in the text and the theorems (W3, W4, Q2–Q6)

W3-1 ("at most polynomially" in the abstract)

You are right. The qualifier "parametric" of the introduction and of Theorem 2 was dropped in the abstract and the conclusion; we will restore it. Precisely, on a bounded state space the growth is polynomial for parametric Lipschitz layers; for nonparametric layers it is polynomial (k(1+q)/2k^{(1+q)/2}) if Λ≤1\Lambda\le1 and exponential if Λ>1\Lambda > 1.

W3-2 (growth of the bound versus growth of the error)

You are right about the wording. We prove an upper bound on the estimation error (Theorem 1(i), (ii)) and a lower bound on the Rademacher complexity of Hk\mathcal H_k (Theorem 1(iii)). The latter means that the depth dependence of the bound cannot be improved by an argument that goes through the complexity of Hk\mathcal H_k; it is not a lower bound on the risk of every learning algorithm, as Sec. 3 states. We will write "estimation bound" instead of "estimation error" in line 65 and in the abstract.

W3-3 (title)

The title states the question and does not contain the term estimation error. The comparison is delimited at the beginning of the abstract. The suggested paraphrase describes a comparison of upper bounds only, whereas the paper also contains the lower bound on the complexity (Theorem 1(iii)), the construction attaining the covering bound (Theorem 3(v)), and the approximation side. On the approximation side, every predictor in Hk\mathcal H_k has excess risk at least the approximation error εmodel(k)\varepsilon_{\rm model}(k). Hence, when the approximation error at a shallow depth k0k_0 exceeds the bound at depth k∗k^\ast, depth k∗k^\ast is better, and this does not rest on a comparison of two upper bounds.

That said, we are open to making the content more explicit in the subtitle, for example "Error Bounds for an Implementation-Agnostic State-Transition Model of Deep Learning".

W3-4 (how Λ\Lambda enters)

Your reading of the proof is correct; our sentence was imprecise. Precisely: Λ\Lambda enters the covering numbers through Sk(Λ)=1+Λ+⋯+Λk−1S_k(\Lambda)=1+\Lambda+\cdots+\Lambda^{k-1} in the radius. For parametric layers this appears as log⁡Sk(Λ)≤log⁡k+klog⁡Λ\log S_k(\Lambda)\le\log k+k\log\Lambda; it changes the profile from klog⁡k\sqrt{k\log k} to kk, but no factor Λk\Lambda^k arises. Λk\Lambda^k appears as a multiplicative factor only through the diameter, when the state space is unbounded. For nonparametric layers, Λqk/2\Lambda^{qk/2} enters through the covering numbers (Theorem 2). We will rewrite the passage.

W4 / Q3 (the rate O(1/n)O(1/\sqrt n) in Corollary 2)

You are right: an additional assumption is needed. The assumption of Proposition 5(i) was lost in the summary in the main text. N∞(ε)N_\infty(\varepsilon) is the depth-uniform bound sup⁡kN(B(k,F),d∞,ε)\sup_kN(B(k,F),d_\infty,\varepsilon) on the covering numbers; Theorem 3(i), (ii) gives its finiteness. The rate n−1/2n^{-1/2} requires in addition that ∫0Dˉlog⁡N∞(ε)dε\int_0^{\bar D}\sqrt{\log N_\infty(\varepsilon)}d\varepsilon is finite. Without this assumption Theorem 1(ii) still holds, but its right-hand side depends on nn through the empirical covering numbers, and n−1/2n^{-1/2} does not follow.

How restrictive it is:

  • It holds automatically for uniformly contractive parametric layers whose invariant set is a bounded finite-dimensional set (log⁡N∞(ε)≲plog⁡2(1/ε)\log N_\infty(\varepsilon)\lesssim p\log^2(1/\varepsilon)).
  • In the examples of the paper there are explicit bounds (Lemma 13, App. M.2, Proposition 8(i)).
  • Under equicontinuity alone (Theorem 3(i)) it is an additional condition on the size of the closure of all compositions. It fails, for instance, for all 1-Lipschitz self-maps of [0,1]m[0,1]^m, m≥2m\ge2 (entropy of order ε−m\varepsilon^{-m}).

We will state this assumption in Corollary 2 and Proposition 8(ii).

Q4 ("statistical cost")

It is our term for the depth-dependent part of the estimation bound, 12LHVk(S)/n12L_H\mathsf V_k(S)/\sqrt n. We will define it at its first occurrence.

Q5 (references for ping-pong and Ascoli)

We will add a direct reference to Condition E2 and a citation for Ascoli's theorem at its first use (App. A.2).

Q6 (limitations; can the bound be nonvacuous)

ICLR does not ask for a limitations section, and the statements about the scope are placed where they are used (Sec. 1, end of Sec. 3, Remark 3, App. E.4). We agree that they are easier to read in one place and will add a brief limitations paragraph in the final version, with a pointer from the main text.

The constants are explicit, so the sample size at which the bound falls below the range of the loss can be read off: nn must exceed a constant multiple of Vk(S)2\mathsf V_k(S)^2. In the saturated cases (Propositions 9 and 11) this does not depend on the depth. Under the layerwise bound it reads n≳kplog⁡kn\gtrsim kp\log k for non-expanding and n≳k2plog⁡Λn\gtrsim k^2p\log\Lambda for expanding layers, the same form as for VC-dimension bounds.

Reviewer_UGhnOpenReview ↗

Rebuttal acknowledgement

I thank the Authors for their work on the rebuttal.

I cannot seem to download the revised version of the paper, the pdf I can download looks identical to the original submission? Did the Authors maybe forget to upload their revision? Please note that unless ICLR policy / AC explicitly allows this, I cannot hold my score unless the revision where the points we discussed are addressed are uploaded before the end of the rebuttal section, because the discussion with the Authors led to the need of important changes in the text at several place. In my opinion it is just too significant change for a camera ready that can't be reviewed again. In case this is a technical error on my side, please inform me.

Please note that I do not ask for limitations and this much comparison to existing results (nor do I write them in my own papers) because of venue policies or traditional reasons. Comparison to related work, comparison to similar bounds, the strengths and limitations of the current results are very important for the reader (and mainly the reader, not the reviewer) to put the paper at hand into perspective and get the right mental image of it. For example, I am aware of several Rademacher-complexity based bounds in the literature. Whenever I encounter a new one, I am interested in how that relates to existing bounds, what model set they hold over, what constants do they depend on, what is their asymptotic rate, because that is how I know what to do with it, that's how I remember them to cite (I admit LLMs might change things here) and that is how I get suspicious if there is something in it I could build my on research on in the future; my other option as a reader is to carefully go through every notation, detail and proof steps to have the right mental image of the main theorem. Nobody has time for that when there is 50k submission for just one conference. It is ok to put that into the appendix with a reference in the main text, but without that, the paper is very easy to miss and be forgotten forever.

I'm generally satisfied with the answers, and I would like to see your response in the suitable form in the revision (not necessarily main text, up to you). The title can remain if nobody else complained or will complain about it, it could be my personal preference against overclaims in the title. Please make sure that the agreed fixes on the wording are corrected everywhere (e.g. W3-1 seems relevant for the conclusion and Section 4.1 as well, W3-2 is relevant not only for the abstract, but Section 3, the mechanism discussion, examples and conclusion, etc.).

Given that the revision agrees with the discussion here and I receive it in time, I am holding my score (3). I'll further process your answers, read the other reviews and consider clear acceptance that I am not 100% sure about yet.

Reviewer_dxC3OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies when increasing the maximum allowed depth can improve generalization within a fixed class of admissible hidden layers. It models each hidden layer as a transformation of a common state space and constructs predictors by composing up to (k) hidden transformations followed by an output layer. The statistical complexity of these predictors is analyzed through the metric entropy of the composed hidden maps, which measures their distinguishability at different resolutions. The paper derives an upper bound on excess prediction loss, relates the statistical contribution to an entropy integral, and establishes conditions governing how complexity grows with depth. It also provides conditional complexity lower bounds and constructions attaining certain growth rates.

The paper then balances the statistical bounds against approximation-error profiles to derive suitable depth scalings as a function of sample size. The framework is illustrated using small ReLU constructions, simplified symbolic computation, and iterative solvers. The contribution is primarily theoretical: the computed examples illustrate the proposed mechanisms, rather than validate depth selection on realistic neural-network benchmarks.

Critical strengths

The paper provides a unified mathematical perspective on the relationship between depth, expressiveness, and statistical complexity. It formalizes the intuition that allowing more layers can improve approximation while increasing the difficulty of selecting a predictor reliably from finite data. Its analysis also identifies structural conditions under which additional depth need not introduce a growing statistical penalty, emphasizing that layer count alone is insufficient to characterize the statistical cost of a network.

Although these broad intuitions are established in learning theory, organizing the analysis around the geometry of composed hidden maps offers a common framework for several settings. The distinction between different complexity-growth mechanisms, together with conditional lower bounds and explicit constructions, strengthens the theoretical account. The authors also distinguish approximation rates that are derived, borrowed from existing results, or assumed.

Critical weaknesses

The connection between the theoretical framework and practical depth selection remains insufficiently established. Applying the results requires verifying several assumptions and obtaining informative complexity and approximation bounds for the architecture and task. Some assumptions can be enforced through suitable constraints, but they do not automatically hold for conventional networks. The paper does not sufficiently demonstrate how these requirements can be satisfied together in a realistic learning problem.

Obtaining a useful bound on the entropy integral (V_k) appears difficult for realistic networks. Directly calculating covering numbers for the full family of weight configurations of a large ReLU CNN is generally impractical. Bounds based on weight constraints, Lipschitz constants, and parameter counts offer an alternative, but their numerical informativeness is not established. Although the paper provides conditional matching complexity bounds and constructions attaining certain growth rates, these results do not establish that the resulting prediction-error bounds are tight enough to guide depth selection on practical tasks.

The depth-selection results require approximation profiles that are generally unavailable for realistic tasks. To balance approximation error against statistical complexity, one needs a justified description or bound on how the best achievable expected loss improves with depth. The authors explicitly identify this requirement and address it in structured examples, but it remains unclear how a practitioner would obtain such information for a conventional CNN on an image-classification dataset. Consequently, the practical applicability of the derived depth scalings remains uncertain.

Questions for authors

1.Could you explain how the framework would be applied to a conventional ReLU CNN with a softmax output and cross-entropy loss on a dataset like CIFAR-10? In particular, which assumptions would require architectural constraints, loss modifications, or additional hypotheses about the task?

2.In this setting, how would one obtain the approximation-error profile needed for depth selection? Could the framework provide a useful recommendation without prior knowledge of how the best achievable expected loss varies with depth?

3.What evidence supports the numerical informativeness of the complexity bounds for realistic networks? Could you clarify which results establish worst-case tightness of complexity growth and which, if any, support useful predictions of task performance or preferred depth?

4.Should the depth-selection results be interpreted primarily as conditional theoretical scaling laws, or as actionable guidance for selecting network depth? Clarifying this distinction would help align the stated motivation with the demonstrated scope of the results.

2 comments

Thank you for the accurate summary. We first answer the three weaknesses together and then the questions.

Weaknesses (common answer)

The three points concern premises shared by the current statistical learning theory of deep networks; they are not specific to this paper.

  • Assumptions. A bounded range for the cross-entropy and control of the norms and Lipschitz constants of the layers are the standard assumptions of analyses based on Rademacher complexity or covering numbers.
  • Constants. No entropy bound for ReLU networks is known with optimal constants. The accepted standard of tightness is agreement of rates, and by that standard the paper shows matching upper and lower bounds (Q3).
  • Approximation profile. The decay of the approximation error follows from an assumption on the data-generating object (e.g. a smoothness class CsC^s); no method can prove it without such an assumption.
  • The review does not give "realistic" and "practical" a quantitative meaning. To answer in a verifiable form, we use the quantitative reading "rates under stated assumptions".

The questions focus on ReLU CNNs, the best-studied instance (App. B). The subject of the paper is the analysis of depth independently of the implementation, and we would be grateful if the new examples, chain of thought and unrolled solvers, were considered as well.

Q1 (a ReLU CNN on CIFAR-10)

This example is not worked out, not because the framework cannot treat it, but because it is one application among others and generalization analyses of deep CNNs for image classification exist (e.g. Oono and Suzuki, 2019; Long and Sedghi, 2020; Kohler et al., 2020). In our framework:

  • State space. The choice is free; for example, feature maps of different resolutions and channel counts (arrays in Rh×w×c\mathbb R^{h\times w\times c}) are discretizations of functions on [0,1]3[0,1]^3 and embed into one common space, e.g. a bounded subset of the Hölder space Cs([0,1]3)C^s([0,1]^3). Blocks of convolution, activation and pooling are self-maps of it. The law of natural images is not known a priori, so any analysis needs a model, and a smoothness class of this kind is the standard one.
  • Assumption 1 (loss). With a norm-bounded output layer on a bounded state space the logits lie in a bounded range, on which the cross-entropy is bounded and Lipschitz (Remark 2).
  • Assumption 2 (output layer). It holds for norm-bounded linear output layers (Proposition 1).
  • Assumption 3 (states and layers). We use bounded states (normalization or clipping) and a finite Lipschitz constant Λ\Lambda of a block (bounded weights); its value is not restricted. Theorem 2 then gives the profile.
  • Hypothesis on the task. The smoothness of the target, which gives the approximation profile.

Q2 (obtaining the approximation profile)

As in the common answer, the approximation profile comes from the assumption on the data. One recommendation does not need it. When the estimation bound does not depend on the depth (contractive layers, e.g. Proposition 8(i) and Lemma 13), the excess-risk bound is nonincreasing in the depth, because the bias is nonincreasing.

Q3 (numerical informativeness, tightness)

No generalization analysis is known to match constants, so we read tightness as agreement of rates (dependence on depth and sample size). The relevant results:

  • Matching depth dependence of the estimation term. When the output layer distinguishes the hidden states on the sample, a lower bound with the same depth dependence (k\sqrt k or log⁡k\sqrt{\log k}) holds (Theorem 1(iii), Corollary 1).
  • Attainment of the covering bound. The layerwise covering bound (Theorem 2) is attained, up to polynomial factors, by memory-preserving expansion (Theorem 3(v), App. G).
  • Agreement in the computed examples. The counts at a fixed resolution agree with the predicted laws: in Fig. 3, saturation at 3131, (k+1)(k+2)/2(k+1)(k+2)/2, and 2k+1−12^{k+1}-1; in Fig. 4, 11841184 on the sample (upper bound 13241324; 8857388573 programs in total) and saturation at 4040; in Fig. 5, saturation at 5757 and 3k+13k+1.

The predictions of a preferred depth are the k∗(n)k^\ast(n) of Propositions 9–12. The validation is the computation of the quantities the theory predicts (the number of distinguishable compositions and the decay of the bias); the paper contains no benchmark experiments.

Q4 (status of the results)

The depth-selection results are theoretical scaling laws. As theorems, they relate geometric conditions on the layer class acting on the state space (contraction, equicontinuity, nilpotent structure, separation) to the scaling of the estimation term in the depth and of the balancing depth in the sample size. The aim is a unified, geometric understanding of generalization analyses that have so far been carried out network by network and task by task. They serve design in the same way as rates do: they show which property to control to keep the cost of depth small.

Thank you for the detailed response and clarifications. My concerns about practical applicability remain. The paper does not work through a concrete CNN and show that the required constraints jointly yield informative results. The constructed examples demonstrate growth rates and counts of distinguishable compositions, but do not establish that the resulting prediction-error bounds are useful at realistic network sizes and sample sizes, or identify a useful depth. Moreover, the response does not explain how to obtain a justified approximation-error profile for a task such as CIFAR-10. The exception for contractive classes provides a conditional qualitative recommendation, but its usefulness for conventional CNNs remains unestablished.

The framework provides conditional theoretical insight, but its ability to guide architecture or depth selection in realistic learning problems remains insufficiently demonstrated. Nevertheless, in recognition of the theoretical results and the intuitions they provide, I raise my score to 3.

Reviewer_Hm6BOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies when increasing depth improves generalization by viewing a network as a composition of state transitions. It bounds the statistical complexity of these compositions and balances the resulting estimation bound against approximation error. Different assumptions on the transitions lead to different depth dependencies and choices of depth as a function of sample size.

Critical strengths
  • The distinction between approximation gains and the statistical cost of increasing depth is useful.
  • The basic definitions and notation are reasonably clear. The framework brings several types of compositions, including neural networks and iterative algorithms, into a common formulation.
Critical weaknesses
  • Unclear consequences for deep networks: The bounds are not connected convincingly enough to a concrete learning problem where they establish a new advantage of depth. Hierarchical target classes and approximation results are discussed in the appendices, but much of this discussion imports existing approximation rates. It remains unclear which substantive conclusion about learning such targets is new.
  • Limited discussion of proof novelty: Much of the framework uses established covering-number and complexity arguments. The paper would benefit from a clearer explanation of the new ideas and difficulties in applying these arguments to compositions. The current organization requires substantial movement between the main text and appendices, making the proof contribution difficult to assess.
  • No connection to gradient-based learning: The analysis assumes an approximately optimal empirical-risk minimizer. It does not explain whether gradient descent reaches the solutions covered by the bounds. Consequently, the results do not by themselves explain why training a deeper network should provide the stated advantage. The comparison also fixes the layer class rather than comparing deep networks with wider shallow alternatives.
Questions for authors
  • Can the authors provide a concrete hierarchical learning problem where the framework yields an advantage beyond the cited approximation and generalization results?
  • What assumptions would connect the stated bounds to networks trained by gradient descent?
1 comment

Thank you for the comments. We answer the weaknesses and the questions in turn.

W1 / Q1 (consequences for deep networks; a concrete learning problem)

The paper is about deep structures in general: compositions of layers on a state space. Deep ReLU networks are one instance, used to confirm that the known depth dependences appear as cases of the framework (App. B, K). The new conclusions concern chain of thought and unrolled solvers, where both the bias and the estimation term are derived within the framework; no existing rate is imported.

  • Append-only chain of thought (Proposition 9): the estimation bound does not depend on the number of steps and its constant is explicit; the bias is of order θk\theta^k, and k∗=log⁡n/(2log⁡(1/θ))+O(1)k^\ast=\log n/(2\log(1/\theta))+O(1).
  • Branching chain of thought (Lemma 15, Proposition 10): at least rkr^k programs are distinguishable in the uniform distance, but on every sample the covering number is at most 1+r+kmin⁡{n,ε−2}1+r+k\min\lbrace n,\varepsilon^{-2}\rbrace, so kk steps cost O(log⁡k/n)O(\sqrt{\log k/n}). No assumption on the input distribution is used.
  • Fixed-point iteration (Proposition 11): the bias is of order (1−hμ)k(1-h\mu)^k, the estimation bound does not depend on kk, and k∗≤log⁡n/(2hμ)+O(1)k^\ast\le\log n/(2h\mu)+O(1).
  • Fixed-horizon integration (Lemma 18, Proposition 12): the profile of the equal-step schemes is log⁡k\sqrt{\log k}, the bias is O(k−p)O(k^{-p}), and k∗≍n1/(2p)k^\ast\asymp n^{1/(2p)}.

These are the concrete learning problems of Q1: the targets form a compositional class generated by the same iteration, and the number of steps that minimizes the bound at sample size nn is a consequence, not an assumption. Independently of the implementation of the layers, the paper gives the layerwise covering bound (Theorem 2), a construction attaining it (Theorem 3(v)), and the converse lower bound (Theorem 1(iii)). The revised version lists the newly derived conclusions of each example in Sec. 6.1.

W2 (novelty of the proofs)

The tools (Dudley's chaining, a Sudakov-type lower bound, telescoping) are classical, as the main text says. The new points and the difficulties in applying them to compositions are these.

  1. A decomposition whose constant does not depend on the depth (Theorem 1(ii)). It has the structure of a chain rule, which splits the complexity of a composite class into an outer and an inner part (Maurer, 2014; Chu and Raginsky, 2023; we will cite both). Iterating a chain rule layer by layer makes the constants and the product of the Lipschitz constants accumulate exponentially in the depth. We split once, at the output layer, and treat the depth through the metric entropy of B(k,F)B(k,F), so the constant is 12LH12L_H at every depth.
  2. The layerwise covering bound (Theorem 2). For parametric layers, the Lipschitz constant Λk\Lambda^k of a composition enters only through its logarithm. Showing that this bound cannot be improved requires a construction in which later layers cannot erase what earlier layers distinguished; memory-preserving expansion (E3) provides it.
  3. Separation conditions for lower bounds. Freeness of the compositions does not give a lower bound, because contracting maps collapse many compositions to nearly the same map. We introduce conditions that provide a distinguishing point for each composition (E1, E2, Lemma 7).
  4. The gap between the entropy in the uniform distance and the entropy on a sample (Lemma 15). It uses that programs of the same length succeed on pairwise disjoint sets of inputs.

The revised version collects these four points in one paragraph of the main text, with pointers to the appendix.

W3 / Q2 (gradient-based learning; wide shallow networks)

The bound holds for every η\eta-approximate empirical risk minimizer, and the optimization error η\eta appears explicitly on the right-hand side. Moreover, the generalization-gap inequality holds uniformly over all elements of Hk\mathcal H_k (Theorem 5, App. C). Hence the answer to Q2 is two conditions.

  • The layers obtained by gradient descent belong to the layer class FF. The norm and Lipschitz constraints that define FF can be enforced by projection or normalization.
  • η\eta is the difference between the attained empirical risk and its infimum.

The bound then applies, as it stands, to the output of gradient descent. Which solution in the class gradient descent selects is a question of optimization. If the selected solution is known to belong to a subclass F′⊂FF'\subset F, the cost becomes the entropy of B(k,F′)B(k,F').

As stated in the abstract and in Sec. 1, the paper compares depths within the nested family H0⊂H1⊂⋯\mathcal H_0\subset\mathcal H_1\subset\cdots built from one layer class. This is the design question for models whose layers are shared by construction and whose depth is a number of iterations or steps. Width enters through the layer class FF: in the covering numbers of a single layer, in the bias, and in the implementation error (Remark 3).

Reviewer_btaHOpenReview ↗
Rating
2
Confidence
1(−1)
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This work studies the statistical cost of depth in deep learning models. For a given sample size, it asks how deep a model should be to balance approximation and estimation errors and achieve better generalization. Under assumptions such as Lipschitzness of the layers and bounded state spaces, the authors characterize how the statistical complexity grows with depth and derive conditions under which the optimal depth increases with sample size.

Critical strengths

1- The paper provides a mathematically rigorous framework for analyzing the statistical cost of depth when the layer class is fixed. Although the presentation is mathematically dense, the paper is generally well-written. It also considers iterative computation, including chain-of-thought, which is less explored in generalization studies.

Critical weaknesses

1- The practical implications of the proposed framework remain unclear. In particular, it is not established whether the assumptions and entropy-growth bounds used in the analysis yield informative predictions for practical deep-learning architectures.

Questions for authors

1- To what extent are the proposed bounds informative for practical overparameterized models? In particular, could the estimation error bound increase with depth while the actual generalization performance improves, and how should the paper's conclusions about the statistical cost of depth be interpreted in this case?

2 comments

Thank you for the careful review. We answer the weakness and the question in turn.

W1 (practical implications)

In each of the three worked examples (fully connected ReLU blocks, chain-of-thought-style step-by-step computation, and unrolled solvers including diffusion samplers) we verify the assumptions and then check numerically the quantity that the theory predicts. The computed quantity is the one that Theorem 1 identifies as the statistical cost of depth: the number of compositions that are distinguishable at a fixed resolution.

  • Deep ReLU (Fig. 3, Sec. 6.2). For three families of ReLU maps that differ only in their Lipschitz constant (1/41/4, 11, 2020), we count the compositions of depth at most kk that are distinguishable at resolution 10−210^{-2} in the uniform distance. The contractive family saturates at 3131 after four layers, the commuting non-expanding family gives (k+1)(k+2)/2(k+1)(k+2)/2, and the expanding family gives 2k+1−12^{k+1}-1. These are the three cases of Theorem 3.
  • Chain of thought (Fig. 4, Sec. 6.3). On a sample of 200200 inputs, 11841184 of the 8857388573 branching programs of length at most 1010 are distinguishable (the counting argument of Lemma 15 gives the upper bound 13241324). The append-only family saturates at 4040.
  • Unrolled solvers (Fig. 5, App. M). The fixed-point family saturates at 5757, and the equal-step Euler schemes give 3k+13k+1. The decay of the bias (geometric, and k−1k^{-1}) is computed as well.

Q1 (informativeness for overparameterized models; a bound that increases while generalization improves)

(1) What the bound measures. The estimation term is determined by the entropy integral Vk(S)\mathsf V_k(S) of B(k,F)B(k,F) on the sample, not by the number of parameters as such. Width enters only through the covering numbers of a single layer. The bound is below the range of the loss once nn exceeds a constant multiple of Vk(S)2\mathsf V_k(S)^2. For contractive layers this condition does not depend on the depth. Under the layerwise bound (Theorem 2) it reads n≳kplog⁡kn\gtrsim kp\log k for non-expanding layers and n≳k2plog⁡Λn\gtrsim k^2p\log\Lambda for expanding layers, where pp is the number of parameters per layer.

(2) The situation described in the question does occur, and the framework identifies when, in three forms.

  • For k≤k∗(n)k\le k^\ast(n) the estimation bound increases with the depth, but the approximation error decreases faster, so the excess-risk bound decreases with the depth (Sec. 5).
  • A lower bound matching the estimation bound holds when the output layer distinguishes the hidden states on the sample (Theorem 1(iii)). When it does not, the entropy of B(k,F)B(k,F) is not paid (end of Sec. 3, App. E.4).
  • The cost is decided by the entropy on the sample. For the branching computation of Sec. 6.3, the entropy in the uniform distance grows linearly in kk, while on every sample the cost is log⁡k/n\sqrt{\log k/n}.

(3) Interpretation. "The statistical cost of depth" means the depth-dependent part of the estimation bound, 12LHVk(S)/n12L_H\mathsf V_k(S)/\sqrt n. It is a guarantee that holds uniformly over the class Hk\mathcal H_k, hence for whichever predictor in the class training returns. If the trained layers belong to a subclass F′⊂FF'\subset F with more structure (smaller Lipschitz constants, commuting or contractive layers), the same theorem applies to F′F', and the cost is the entropy of B(k,F′)B(k,F'). In the terms of the paper, the observation that generalization improves with depth therefore corresponds to one of two cases: the decrease of the approximation error outweighs the increase of the estimation term, or the entropy of the subclass that contains the trained layers does not grow with the depth.

In the revised version we will state this definition and this reading in Sec. 3.

I thank the authors for their detailed response to my questions and for the corresponding revisions to the paper.

While the response clarifies the theoretical points in question, I still find it unclear how informative the results are for practical overparameterized networks. Therefore, I maintain my score of 2. However, given my broad familiarity with this topic, I acknowledge that I may not have fully grasped the significance of the work, and therefore lower my confidence to 1.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.