- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies an important question of what intermediate information, about the inference process, can help in learning. This is a very well-posed timely question. One of the central challenges in such problems is to model correctly the type of intermediate information to be studied.
The model presented in this work is the intermediate calculations of a piecewise linear machine: intermediate calculation are divided into "activation" (s) and output (h). The paper first conclusion is that learning is possible in the face of both. In the second part they show that s are enough and finally they show that permuted s are also sufficient.
Since such models rarely capture reality faithfully, their main contribution often lies in the novelty of the ideas and techniques they introduce. So my review will focus on two issues. The first is the technical strength of the results which, overall, I think they are sound and and require some sophistication. The second issue is related the literature survey, which I find more imminent.
The first result seems technically trivial. This is not something bad, I think it is good to start with a technically simple setting to illustrate the scope. But overall, the first setting simply allow to learn each output-node individually, and the final output follows recursively. From my understanding the current paper doesn't improve on this approach.
The second result seems more technically involved as the outputs are not given. A naive approach could learn for each sign-configuration a classifier but that would be exponential in depth. The authors observe the linearity of each output layer and hence are able to achieve bounds that are polynomial in width.
The third result, when order of signals is not provided, I found least appealing: The result seems exponential in the number of nodes. With that, I don't see the advantage of their suggested solution that simply going brute-force over all permutation and perform pac learning using the second result. As far as I can see that would give almost the same dependence: it is K! instead of 2^{K}. There is some incremental improvement, but if this improvement is the point, then it should be put in better context.
As to related work. There seems to be several paper that touched the issue and I think those should have been discussed.
-
Neural Path Features and Neural Path Kernel :Understanding the role of gates in deep learning: Their proposition suggests an embedding of each example in an ambient space given the signs. This result, I believe allows to learn a classifier at the same rate as suggested in this work. It is true that at inference, the signs are not given. So I think some discussion is warranted, but there is enough novelty here.
-
Auto-Regressive Next-Token Predictors are Universal Learners: This paper studies a seemingly different problem of learning a kind of next bit prediction problem. But they specifically state that such relus with activations can be cast into their model, hence suggesting an algorithm to learn this problem (theorems 3.3 3.6 3.8 all seem relevant)
-
Learning Complicated Concepts eliably and Usefully: This is indeed an old work, but section 2.2 deals with the question of learning when the pieces of a circuit are presented. The current paper speaks in a modern language of networks, but morally, these are not that different.
Critical strengths
The problem is timely and the model is natural.
Critical weaknesses
Related work is was not properly investigated.
Questions for authors
I have no questions.
2 comments
Thank you for the rebuttal and for addressing the points raised in my review. I have read your response and will take it into account when reassessing my score during the discussion period.
We thank the reviewer for the careful review. Below we address the reviewer’s comments and questions, and we would be happy to provide further clarification if needed.
Q1. Related work was not properly investigated ...
A1. A key contribution is a computational separation: complete activation signs can leave learning hard, whereas numerical activations make the same ReLU class efficiently learnable.
Theorem 4 establishes this by constructing networks whose entire sign trace is computable from the input independently of the unknown target, while the numerical states actually carry the hard computation. Cryptographic hardness therefore persists even when the signs are available at prediction time. In contrast, Corollary 1 gives polynomial-time learning from numerical activations revealed only during training, under the same distribution-free setting and output-disagreement loss.
Our positive results identify when learning remains possible despite the missing numerical states. Theorem 2 shows how to combine learners for the individual steps into a predictor for the full computation, reconstructing the intermediate trace instead of requiring it at test time. Corollaries 2–3 construct distribution-free learners from ReLU signs and attention traces, including reconstruction at prediction time. Theorem 3 quantifies error propagation for inexact traces, and Theorem 5 gives an efficient regime under explicit path-margin and norm conditions. Together, these results establish the capabilities but also the limitations of partial intermediate supervision.
These works are closely related, and we will cite and discuss them explicitly. Our results address what can be learned when signs or routes are observed but numerical states remain hidden. More specifically, the cited works do not establish the separation we just mentioned between learning from signs and learning from numerical activations.
Q2. The first result seems technically trivial ...
A2. The complete-trace result is intentionally the simplest setting. Corollary 1 gives a proper, distribution-free learner for ReLU networks with polynomial dependence on dimension, width, and depth, using numerical activations only during training. This provides the baseline against which the partial-trace results can be understood. We will connect it explicitly to earlier circuit-learning work, including Rivest & Sloan's Section 2.2.
Q3. Neural Path Features and Neural Path Kernel ... allows to learn a classifier at the same rate ...
A3. The path representation makes the output linear once the gates are known. Our learning problem also requires recovering those gates from the input, since the teacher's trace is unavailable at prediction time. Corollary 2 establishes this by learning each gate in features constructed from earlier signs and composing the learned predictors. We will credit the existing representation and make this additional learning guarantee explicit.
Q4. Auto-Regressive Next-Token Predictors are Universal Learners ...
A4. Malach's Theorems 3.3 and 3.6 show how learning individual steps can yield accurate predictions for the full computation. The difference is what the intermediate supervision reveals. In the Boolean-circuit construction of Theorem 3.8, each observed bit is the value passed to subsequent gates. Our ReLU signs are also bits, but they reveal only whether a neuron is active; subsequent layers use its numerical activation, which remains hidden. We show that you can actually use these partial observations to construct useful features that make the local prediction problems learnable, and we will clarify this connection in the related-work discussion.
Q5. I don't see the advantage of their suggested solution ... going brute-force over all permutation ...
A5. Enumerating candidate orders is a valid baseline. Appendix E instead uses subset features and validation to progressively learn a usable prediction order, without recovering the teacher's original ordering. Its guarantee is polynomial in d2K, where K is the number of gates, and therefore remains exponential. We will explain the comparison with enumeration explicitly and clarify the result's role: extending learnability to traces whose gate identities and layer assignments are unknown.