Rademacher complexity and spin glasses: A link between the replica and statistical theories of learning
This work bridges theoretical frameworks in machine learning and statistical physics, offering insights for researchers in both fields, though it is incremental in linking established concepts.
The paper connects Rademacher complexity from statistical learning theory with ground state energy from replica theories in statistical physics, showing they are closely related in synthetic-data models and enabling reinterpretation of existing results as rigorous bounds.
Statistical learning theory provides bounds of the generalization gap, using in particular the Vapnik-Chervonenkis dimension and the Rademacher complexity. An alternative approach, mainly studied in the statistical physics literature, is the study of generalization in simple synthetic-data models. Here we discuss the connections between these approaches and focus on the link between the Rademacher complexity in statistical learning and the theories of generalization for typical-case synthetic models from statistical physics, involving quantities known as Gardner capacity and ground state energy. We show that in these models the Rademacher complexity is closely related to the ground state energy computed by replica theories. Using this connection, one may reinterpret many results of the literature as rigorous Rademacher bounds in a variety of models in the high-dimensional statistics limit. Somewhat surprisingly, we also show that statistical learning theory provides predictions for the behavior of the ground-state energies in some full replica symmetry breaking models.