1
Introduction
2
Setting
▶
2.1
Word balls and the semigroup generated by the hidden layers
2.2
Uniform and empirical metrics
2.3
Covering and packing numbers
2.4
Hypothesis classes and implementation error
2.5
Loss, risk, and empirical minimizers
2.6
Rademacher complexity
2.7
The entropy integral
2.8
Assumptions and auxiliary definitions of the main theorems
3
Implementation-agnostic generalization bounds
▶
3.1
Implementation-free bias–variance decomposition (proof: Appendix C, thm:bv, thm:bv-general)
3.2
Hidden–output decomposition (proof: Appendix D, thm:hidden-decomp / thm:mixed-sg, prop:hilbert-sg, prop:finite-lipschitz-sg)
3.3
A conditional Sudakov-type converse (proof: Appendix E, thm:sudakov-type, cor:matching, cor:sudakov-rates)
3.4
Output-layer realization of hidden geometry (Appendix E, prop:global_scalar_observable, prop:linear-interpolation, cor:rkhs-readout)
3.5
Tools not printed in the manuscript: a deterministic entropy decomposition (formerly App. E of the ICLR draft; kept in the library, see comparator/README.md)
3.6
Tools not printed in the manuscript: the deterministic entropy decomposition on the sample (formerly App. E of the ICLR draft; kept in the library)
4
Growth of the hidden class with depth
▶
4.1
Definitions for the growth conditions
4.2
Basic facts on covering and packing numbers (Appendix A, incl. lem:probes-packing)
4.3
Tools not printed in the manuscript: compact Arzelà–Ascoli for self-maps (formerly App. P of the ICLR draft; kept in the library, see comparator/README.md)
4.4
Saturation: equicontinuous semigroups and contraction to an invariant set (Appendix F.1, P1, P1’)
4.5
Polynomial growth under nilpotent control (Appendix F.2, P2)
4.6
Exponential growth: free semigroups and ping–pong coding (Appendix F.3, E1, E1’, E2)
4.7
Memory-preserving expansion: super- and double-exponential growth (Appendix F.4, E3)
4.8
The layerwise covering envelope and the reachable radius (Appendix G, prop:envelope, cor:envelope-profiles, lem:reachable-radius)
5
From growth mechanisms to variance profiles (Appendix H)
▶
5.1
An elementary logarithmic splitting lemma (Appendix H, lem:log-split)
5.2
Variance profiles from growth and diameter (Appendix H, prop:profiles)
5.3
The variance term and the table of profiles (Appendix H)
6
Depth bias–variance trade-offs (Appendix I)
▶
6.1
Bias laws, variance profiles, balancing depths (definitions)
6.2
Balancing depths and balanced rates (Appendix I, the four regimes EL, EP, PL, PP; lem:balancing, eq:tradeoff-table)
7
Worked examples (Appendices J–M)
▶
7.1
Shared glue for the worked examples (regimes)
7.2
Implementation with controlled uniform error (Appendix J, prop:implementation; proof in J.3)
7.3
Deep ReLU networks (Appendix K, lem:relu-layer-covering, prop:relu-regimes)
7.4
Chain-of-thought style symbolic computation (Appendix L)
7.5
Unrolled fixed-point iterations and ODE solvers (Appendix M)
Dependency graph
Generalization error bounds for deep models
Sho Sonoda
1
Introduction
2
Setting
2.1
Word balls and the semigroup generated by the hidden layers
2.2
Uniform and empirical metrics
2.3
Covering and packing numbers
2.4
Hypothesis classes and implementation error
2.5
Loss, risk, and empirical minimizers
2.6
Rademacher complexity
2.7
The entropy integral
2.8
Assumptions and auxiliary definitions of the main theorems
3
Implementation-agnostic generalization bounds
3.1
Implementation-free bias–variance decomposition (proof: Appendix C, thm:bv, thm:bv-general)
3.2
Hidden–output decomposition (proof: Appendix D, thm:hidden-decomp / thm:mixed-sg, prop:hilbert-sg, prop:finite-lipschitz-sg)
3.3
A conditional Sudakov-type converse (proof: Appendix E, thm:sudakov-type, cor:matching, cor:sudakov-rates)
3.4
Output-layer realization of hidden geometry (Appendix E, prop:global_scalar_observable, prop:linear-interpolation, cor:rkhs-readout)
3.5
Tools not printed in the manuscript: a deterministic entropy decomposition (formerly App. E of the ICLR draft; kept in the library, see comparator/README.md)
3.6
Tools not printed in the manuscript: the deterministic entropy decomposition on the sample (formerly App. E of the ICLR draft; kept in the library)
4
Growth of the hidden class with depth
4.1
Definitions for the growth conditions
4.2
Basic facts on covering and packing numbers (Appendix A, incl. lem:probes-packing)
4.3
Tools not printed in the manuscript: compact Arzelà–Ascoli for self-maps (formerly App. P of the ICLR draft; kept in the library, see comparator/README.md)
4.4
Saturation: equicontinuous semigroups and contraction to an invariant set (Appendix F.1, P1, P1’)
4.5
Polynomial growth under nilpotent control (Appendix F.2, P2)
4.6
Exponential growth: free semigroups and ping–pong coding (Appendix F.3, E1, E1’, E2)
4.7
Memory-preserving expansion: super- and double-exponential growth (Appendix F.4, E3)
4.8
The layerwise covering envelope and the reachable radius (Appendix G, prop:envelope, cor:envelope-profiles, lem:reachable-radius)
5
From growth mechanisms to variance profiles (Appendix H)
5.1
An elementary logarithmic splitting lemma (Appendix H, lem:log-split)
5.2
Variance profiles from growth and diameter (Appendix H, prop:profiles)
5.3
The variance term and the table of profiles (Appendix H)
6
Depth bias–variance trade-offs (Appendix I)
6.1
Bias laws, variance profiles, balancing depths (definitions)
6.2
Balancing depths and balanced rates (Appendix I, the four regimes EL, EP, PL, PP; lem:balancing, eq:tradeoff-table)
7
Worked examples (Appendices J–M)
7.1
Shared glue for the worked examples (regimes)
7.2
Implementation with controlled uniform error (Appendix J, prop:implementation; proof in J.3)
7.3
Deep ReLU networks (Appendix K, lem:relu-layer-covering, prop:relu-regimes)
7.4
Chain-of-thought style symbolic computation (Appendix L)
7.5
Unrolled fixed-point iterations and ODE solvers (Appendix M)