Do Highly Over-Parameterized Neural Networks Generalize Since Bad Solutions are Rare?

Area of Science:

• Machine Learning
• Optimization
• Statistical Learning Theory

Background:

• Over-parameterized classifiers often achieve zero training error via empirical risk minimization (ERM).
• Multiple global minima exist in these settings, varying in their generalization performance.
• Understanding generalization in highly parameterized models remains a key challenge.

Purpose of the Study:

• To theoretically analyze the generalization properties of over-parameterized classifiers.
• To identify conditions under which the proportion of poorly generalizing solutions diminishes with increasing data.
• To provide an explanation for the effective generalization of over-parameterized neural networks.

Main Methods:

• Theoretical analysis of global minima distribution in over-parameterized settings.
• Derivation of bounds on the fraction of "bad" global minima based on true error distribution.
• Empirical validation using synthetic datasets and benchmark image datasets (MNIST, Caltech101).

Main Results:

• The fraction of "bad" global minima decays exponentially with the number of training samples (n).
• This decay rate depends on the true error distribution, not necessarily model complexity.
• Theoretical findings are supported by experiments on synthetic and real-world data.

Conclusions:

• The study offers a theoretical framework for understanding generalization in over-parameterized classifiers.
• Exponential decay of "bad" minima with data size explains effective neural network generalization.
• The findings highlight the importance of error distribution over function space for generalization analysis.