- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper combines / applies classical classical PAC type arguments with / to neural networks via a modular argument. If a (possibly complex) NN forms a DAG (which is a reasonable assumption), then by analyzing the learnability complexity of each type of node, and the connection between them, it should be possible to combine them. For each node, which can be, say, an attention layer, even if unbounded parameters are allowed, there is a limit to the class of functions learned. This pleasingly connects older foundations of learning theory like the VC dimension, to modern architectures. The paper includes specifically attention, pooling, normalization, positional encoding, etc., and at least claims to address GNNs.
Critical strengths
- I think the topic is an interesting tie in of classical shattering concepts and theory with more contemporary neural network architecture. I also think that the specific emphasis (attention & related like positional encoding) are interesting.
- The modular approach is a good way to approach arbitrary (DAG-like) networks
Critical weaknesses
Overall, the selling point of the paper being a modular approach to a shattering result, the main question is what does it add over other work.
- To the best of my understanding, ON SAMPLE COMPLEXITY OF NEURAL NETWORKS (https://arxiv.org/pdf/1910.11080) is uncited, and contains a large part of the selling point of the paper. To quote the abstract: "We consider functions defined by deep neural networks as definable objects in an o-miminal expansion of the real field, and derive an almost linear (in the number of weights) bound on sample complexity of such networks." While there are some added elements, I do think this weakens the incremental value of the paper by a lot.
- GNNs: a. They are stated as being "similar" to some proof, but the message passing is not developed. Unfortunately, this falls into one of two directions - either GNNs are fundamentally novel and the paper does not develop them, or they are very similar to MLPs, in which case point number 1 stands. b. The paper, IMHO, misrepresents VC dimension of Graph Neural Networks with. Pfaffian activation functions (https://arxiv.org/pdf/2401.12362). This paper states that this 2025 paper does not bring quantitative results based on depth, but I think it does. Here, too, if GNNs are similar, it begs the question of the added value of this paper.
Questions for authors
- Could you please explain the added value over the omitted ON SAMPLE COMPLEXITY OF NEURAL NETWORKS (https://arxiv.org/pdf/1910.11080)? If accepted, I think it should be cited too, but an explanation why not is also OK.
- Could you please clarify the two points regarding GNNs? In which way are the quantitative results here stronger than the VC GNN paper, and in what sense are GNNs similar to other architectures, but this paper different than that one?