“Learning and Generalization in a Two-Layer Neural Network: The Role of the Vapnik-Chervonvenkis Dimension”, Manfred Opper1994-03-28 (neural net)⁠:

Bounds for the generalization ability of neural networks based on Vapnik-Chervonenkis (VC) theory are compared with statistical mechanics results for the case of the parity machine.

For fixed phase space dimension, the VC dimension can grows arbitrarily by increasing the number K of hidden units. Generalization is impossible up to a critical number of training examples that grows with the VC dimension [a phase transition]. The asymptotic decrease of the generalization error ε_G comes out independent of K and the VC bounds strongly overestimate ε_G.

This shows that phase space dimension and VC dimension can play independent and different roles for the generalization process.

See Also:

• Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning behavior

• Learning through atypical “phase transitions” in overparameterized neural networks

• Statistical mechanics of learning from examples

• A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning