Rademacher complexity and spin glasses: A link between the replica and statistical theories of learning

Alia Abbaras, Benjamin Aubin, Florent Krzakala, Lenka Zdeborová
Proceedings of The First Mathematical and Scientific Machine Learning Conference, PMLR 107:27-54, 2020.

Abstract

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 \emph{typical-case} synthetic models from statistical physics, involving quantities known as \emph{Gardner capacity} and \emph{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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v107-abbaras20a, title = {Rademacher complexity and spin glasses: {A} link between the replica and statistical theories of learning}, author = {Abbaras, Alia and Aubin, Benjamin and Krzakala, Florent and Zdeborov\'a, Lenka}, booktitle = {Proceedings of The First Mathematical and Scientific Machine Learning Conference}, pages = {27--54}, year = {2020}, editor = {Lu, Jianfeng and Ward, Rachel}, volume = {107}, series = {Proceedings of Machine Learning Research}, month = {20--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v107/abbaras20a/abbaras20a.pdf}, url = {https://proceedings.mlr.press/v107/abbaras20a.html}, abstract = {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 \emph{typical-case} synthetic models from statistical physics, involving quantities known as \emph{Gardner capacity} and \emph{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.} }
Endnote
%0 Conference Paper %T Rademacher complexity and spin glasses: A link between the replica and statistical theories of learning %A Alia Abbaras %A Benjamin Aubin %A Florent Krzakala %A Lenka Zdeborová %B Proceedings of The First Mathematical and Scientific Machine Learning Conference %C Proceedings of Machine Learning Research %D 2020 %E Jianfeng Lu %E Rachel Ward %F pmlr-v107-abbaras20a %I PMLR %P 27--54 %U https://proceedings.mlr.press/v107/abbaras20a.html %V 107 %X 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 \emph{typical-case} synthetic models from statistical physics, involving quantities known as \emph{Gardner capacity} and \emph{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.
APA
Abbaras, A., Aubin, B., Krzakala, F. & Zdeborová, L.. (2020). Rademacher complexity and spin glasses: A link between the replica and statistical theories of learning. Proceedings of The First Mathematical and Scientific Machine Learning Conference, in Proceedings of Machine Learning Research 107:27-54 Available from https://proceedings.mlr.press/v107/abbaras20a.html.

Related Material