- 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 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
-
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.
-
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 , so their entropy integral on a bounded state space is at most of order . 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.
-
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 . Section H.2 likewise lists an estimation term of order . Corollary 2 instead attributes a profile to this layerwise bound and says the profiles hold up to constants. A factor growing as 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.
-
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 , 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 , 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
-
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.
-
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.
-
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.
-
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 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).
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∞(ε):=supkN(B(k,F),d∞,ε) at every resolution. The depth-independent profile n−1/2 requires in addition that V∞:=∫0DˉlogN∞(ε)dε 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.
W2 / Q2 (the expanding ReLU example)
We have not proved a lower bound that is linear in k for FΛ. We withdraw the word "attained" and state separately what is proved.
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 klogk/n, and no sharper estimate was intended. The revised Corollary 2 and Sec. 4.2 display the logk in the formulas and say "up to logarithmic factors" in the text. For γ=1 the balance becomes k∗≍(n/logn)1/(2β+1) with the rate (logn/n)β/(2β+1). The profile 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 logk/n drawn in the left panel of Fig. 2, the bound keeps increasing beyond k∗ and equals logk/logk∗ times its value at k∗. For k≤(k∗)c it therefore stays within the factor c. In the EL case k∗≍logn, so the rate loglogn/n is kept for depths up to a polynomial in logn, while k=n gives logn/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.