- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies the statistical query (SQ) learnability of Boolean functions specified by a DAG with and without intermediate supervision (CoT). The main result states that, analogously to previous results on learning with intermediate supervision, trace supervision makes functions learnable that would otherwise not be. In particular, the paper shows that general DAGs with bounded fan in are SQ-learnable given access to queries that can enquire about functions of the intermediate activations as well. This relies on two natural distributional assumptions that make the topology of the graph discoverable. This allows the authors to give another view of the known exponential gap in the sample complexity of subset parity with and without intermediate supervision.
Critical strengths
- The work extends a growing body of literature on how CoT not only makes models more powerful, but also makes the learning problem easier. In this realm, the main result adds a welcome generalization of existing results, which mostly consider subset parity.
- I particularly like the fact that the results abstract away architectural considerations and thus hold beyond
- I think the problem setup is quite natural and the two main assumptions are well-justified.
- The results are easy to follow and are understandable. The proofs also seem correct.
Critical weaknesses
- This is not a big weakness, but I feel like some writing and exposition could be improved. For example, the first part of the Abstract (Lines 11–23) repeats many points twice, and Fig. 1 is never even mentioned in the text (nor are the experiments that produced it).
- Similarly, the Introduction jumps ahead of the exposition a few times, such as saying that “the learner may query arbitrary bounded functions” on Line 63 without explaining what “querying functions” means.
- Smaller inconsistencies:
- “and (3, 1/8, 1/16)” in Cor. 1 comes out of nowhere.
- Some additional results are promised in the Introduction but never elaborated on. For example, the effects of imperfect/noisy observations are briefly touched upon in the Introduction and never mentioned again. The same holds for propositional compositional reasoning.
- I am familiar with some existing results on CoT learnability (e.g., the Wies and Kim&Suzuki references), but less so with the standard SQ literature. It would be helpful to understand the inspirations behind the algorithms and the proofs. For example, the algorithm at a high level looks like an exhaustive search over potential parent sets, and I imagine it has some existing analogues. Similarly, I am not sure whether the assumptions made have some precedent in the literature.
- In general, I believe my assessment of the paper could be better if I understood better how it contrasts with existing (classic) SQ learning literature.
- Connected to Fig. 1 not being elaborated on in the main text, I am not sure what the experiments are even supposed to show: If they are simply running the enumeration algorithms, they follow the derived complexities by construction, so the agreement is expected.
- The tree-learning result is unclear to me. The authors provide a CoT-learning algorithm and classify it as “similar to the parity one”, but I don’t see the same exponential gap as in parity. Can such trees not be learned without CoT supervision (I suppose they could be, since conjunctions are not hard to learn)?
Questions for authors
- Can these proof techniques or results be used to understand the SQ learnability of more general circuits. I suppose the bounded fan-in requirement narrows the scope to NC classes, but would the results in any way translate to growing-depth circuit families (e.g., )?
- On a similar note, would the algorithm of Section 4.1 work without knowing (could one loop the algorithm with growing values of , for example)?
- How easy are the derived results to specialize to specific neural architectures?