Section 5.3, paragraph 3Explicit layer bounds, depth versus size, and remaining learning difficulties
Informal interpretation Motivation, interpretation or scope; not a formal claim.
1 Paper text
Membership in does not guarantee a small or readily learnable network. For the complete two-frame move selector built on this difference computation, our modular construction gives an upper bound of 42 threshold layers; one shootout-controller step has a bound of 70 (Appendix C). These are constructive bounds, not necessary depths. Any Boolean function has a depth-two AND–OR representation with negated inputs, but its size can be exponential; requires polynomial size as the input grows. We have not optimised this depth–size trade-off. Removing the expressivity obstruction therefore leaves practical network design, training procedures and hyperparameter choices open. The layer bounds do not establish the cause of the experimental learning plateaus.
Generated from paper_jmlr.tex, lines 513–513.
2 Explain this
An AC0 construction can still be large and inconvenient to train. The paper's uniform compiler gives at most 42 threshold layers for the complete two-frame move selector, and at most 70 for a shootout-controller tick. These bounds include more than computing a bounded-change difference alone. They do not say that 42 or 70 layers are necessary, or that all instantiated circuits reach those bounds.
Any Boolean function can be written as a depth-two AND–OR circuit with negated inputs by listing all satisfying assignments. But that representation may be exponentially large. AC0 requires polynomial size as the input grows, so depth and size must be considered together. The construction does not optimise this trade-off or prove that training will find its weights. The observed learning plateaus require separate empirical explanation.
See Appendix C, table for checked bounds and Section C, “Where the layer counts come from” for their derivation.
3 How this is formalised
The numerical upper bounds are checked in Family.rest_net and Shootout.sh_net, as described in Appendix C, table. The discussion of training is an interpretation, not a formal learning theorem. The general depth-two truth-table observation is standard Boolean algebra and is not a new claim of Lean coverage.
| Paper anchor | c-depth-learning (website anchor; the manuscript has no label here) |
|---|---|
| Displayed as | Section 5.3, paragraph 3 |
| Claim | Explicit layer bounds, depth versus size, and remaining learning difficulties |
| Coverage category | Informal interpretation |
| Statement source | paper_jmlr.tex lines 513–513; SHA-256 of the normalised block source e0ad234d0e79392a… |
| Depends on | Appendix C, table, Section C, “Where the layer counts come from” |
| Explanations | explain/c-depth-learning, formal/c-depth-learning |
| Build evidence | fresh isolated rebuild, audit report |
4 Lean statement and source
No Lean statement corresponds to this claim. This is interpretation or motivation, not a formal mathematical claim.
Build evidence: fresh isolated rebuild of all 38 bundled modules with Lean (version 4.26.0, started 2026-10-10T15:21:56Z, finished 2026-10-10T15:27:00Z: 38/38 modules compiled, 1588 axiom reports, no errors. See Build for the commands and the independent audit of 2026-10-10 (dated evidence).