- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This manuscript proves that given deep neural network (the teacher network) a smaller network can be found that represents the same function over bounded input. The strategy is to match derivatives at intermediate layers and leverage, essentially, Taylor approximations using those matched derivatives.
Critical strengths
The manuscripts main theoretical contributions seem sound and may be useful to understand, broadly, certain behavior of such models. Moreover, the core derivative matching idea is interesting and clearly workable, if not practical at scale.
Critical weaknesses
I think the theoretical developments here are fine and the derivative matching approach is, to the best of my knowledge, novel in this context. However, I do not really feel there is a substantiate contribution in the overall narrative of the manuscript. This is due to a few factors.
Given the relative complexity and looseness of the theoretical claims and number of "hidden" dependencies it is not clear to me how descriptive or insightful the results are. While some suggestions are made in the manuscript I don't think the connections are sufficiently supported by the results as presented (perhaps via intermediary results in the appendix?)
For example, I think the manuscript oversells its "width independence" claim. In fact, it is not even clear what this means given the implicit dependence on the teacher network. The relevant properties presumably depend on the underlying architecture, data, and training process. How they all factor in is opaque at best.
Building on this point, while there seems to be a discussion in the appendix showing that there are regimes where the bounds are not vacuous it is not clear how common this is. For example, is there any hope (omitting the restriction on activation functions away from ReLU) for anything non-vacuous on any "real world" model? Notably, even the very restricted networks used for numerical experiments simply show the derivative matching scheme is workable at small scale and not that the resulting model is close to a theoretical bound (i.e., there are no bounds to compare with in Fig. 1).
The above critique could be mollified by a practical algorithm. And, perhaps, it is remarkable that the construction from the proof is workable at all (though framed as derivative matching for Taylor approximations it is less surprising). However, as the manuscript notes, the scheme is not particularly scalable.
In summary, on the theoretical front (which is the claimed contribution) I find the manuscript lacking in insight. Importantly, it never satisfactorily answers the question: why is this specific theoretical result interesting.
Questions for authors
-
What does it mean for to be in this context? For big-O notation to make sense there needs to be a natural parameter that is being scaled. E.g., in eq. (2) it could be or Is this just supposed to suggest that is some small constant much less than the intermediary sizes? If F is fixed then so is
-
Is there any regime where the bounds are informative enough to be compared with experiments?
Thank you for the careful report. Short answers first:
1. Why is this specific theoretical result interesting?
Our contribution is theoretical, and we believe it is a large step. Previous works mostly report empirical pruning by a constant fraction, say 90% (Section 3); previous theoretical bounds are limited in scope. Very few works anticipated that a network can be compressed to a vanishing fraction of its original width. We prove that it can: polylog(1/ε) neurons per hidden layer suffice. This is the true value of our derivative-matching construction: a surprising proof, not a practical algorithm. This is pointed out in Sections 3 and 6.
We agree that our algorithm is not practical as-is when din is large. This is not a peculiarity of our construction but an information-theoretic limit: the Kolmogorov widths of analytic function classes grow in the same way, as [log(1/ε)]din (Appendix E).
2. "There are no bounds to compare with in Fig. 1" (Q2).
This was a gap in our presentation. In Fig. 1(a) ([3,2048,2048], default initialization) the first-layer row norms are at most 1 and the outgoing norms at most 2048. The certified error ratio per step ek+1/ek asymptotically equals R/π by Theorem 5. The submitted bound gives:
Reading. Non-vacuous for R≤1; the measured decay is geometric, as predicted, and faster than certified at every covered radius. The sigmoid-specific corollary we add (Appendix H) even covers R=4 (reply to Ydfw, Q2). "Vacuous" means the certified width exceeds the original 2048.
More tests (new Appendix I.1–I.2). On 36 networks that satisfies all of assumptions 1-4 (one or three hidden layers, untrained and trained), the error bound is never exceeded; the certified width is at the order of 10 times the width needed numerically.
Action. Certified and measured ratios tabulated in the new Appendix I.4; tests in I.1–I.2.
3. Overselling of "width independence"; "hidden" dependencies.
"Width-independent" means independent of the widths at fixed weight norms. The submission states this in Section 2, Remark 7, but not prominently enough: the abstract and introduction leave it unclear. We keep the title, where "width-independent" carries this meaning, and state it explicitly at first use in both the abstract and the introduction. The certificate depends on the teacher only through the input radius and the row norms of its weights, so it holds uniformly over all networks with bounded row norms, of any width.
If one naively assumes each neuron's weight to be of order 1, then the ℓ1 norm grows with width. But in actual cases, whether norms stay bounded as width grows depends on normalization and training; in practice they usually do, because of the weight regularization typically used in training. This is discussed in Appendix F.
4. How common is the non-vacuous regime? Any hope for "real world" models?
It is narrow, because real-world models (especially generative AIs) usually have a large input dimension. Unless we find a small bottleneck dimension, in the data or in the network (reply to Ydfw, Q4), our compression is not applicable as-is. Our Section 6 explicitly says so.
5. What does din=O(1) mean? (Q1)
Only that din is a small fixed integer. You are right that for a fixed teacher din is not scaled; our wording was imprecise. We replace it by "din is a fixed integer with din≪dℓ".