Beyond the Storage Capacity: Data-Driven Satisfiability Transition

Pietro Rotondo, Mauro Pastore, and Marco Gherardi
Phys. Rev. Lett. 125, 120601 – Published 14 September 2020

Abstract

Data structure has a dramatic impact on the properties of neural networks, yet its significance in the established theoretical frameworks is poorly understood. Here we compute the Vapnik-Chervonenkis entropy of a kernel machine operating on data grouped into equally labeled subsets. At variance with the unstructured scenario, entropy is nonmonotonic in the size of the training set, and displays an additional critical point besides the storage capacity. Remarkably, the same behavior occurs in margin classifiers even with randomly labeled data, as is elucidated by identifying the synaptic volume encoding the transition. These findings reveal aspects of expressivity lying beyond the condensed description provided by the storage capacity, and they indicate the path towards more realistic bounds for the generalization error of neural networks.

  • Figure
  • Figure
  • Received 24 May 2020
  • Revised 22 July 2020
  • Accepted 13 August 2020

DOI:https://doi.org/10.1103/PhysRevLett.125.120601

© 2020 American Physical Society

Physics Subject Headings (PhySH)

Statistical Physics & ThermodynamicsNetworks

Authors & Affiliations

Pietro Rotondo1,2, Mauro Pastore1,2, and Marco Gherardi2,1,*

  • 1Istituto Nazionale di Fisica Nucleare, sezione di Milano, via Celoria 16, 20133 Milano, Italy
  • 2Università degli Studi di Milano, via Celoria 16, 20133 Milano, Italy

  • *marco.gherardi@mi.infn.it

See Also

Statistical learning theory of structured data

Mauro Pastore, Pietro Rotondo, Vittorio Erba, and Marco Gherardi
Phys. Rev. E 102, 032119 (2020)

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 125, Iss. 12 — 18 September 2020

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×