Statistical physics of learning and inference

6 problems

• Test error of interpolating two-layer networks in the feature-learning regime

  Partially resolved

  Networks with far more adjustable weights than training examples can fit noisy data exactly and still predict new data well, against the classical expectation of overfitting (memorizing noise). The task is to compute the error on new data for networks whose internal features adapt during training.

• Exact storage capacity of dense associative memories with p-body interactions

  Open

  A Hopfield network stores patterns as low points of an energy, and replacing pairwise couplings by couplings among p units at once lets it store vastly more patterns. The exact number of patterns it can store and still recall from a corrupted cue has not been computed with proof.

• A correct low-degree criterion for polynomial-time hardness of inference

  Contested

  A popular test predicts that a hidden signal cannot be found quickly whenever no low-degree polynomial (a simple formula built from products of a few data entries) can detect it. Recent counterexamples show this test fails in some cases, and the task is to find the exact conditions under which it is right.

• Polynomial-time algorithms beating the overlap-gap threshold for independent sets

  Open

  In a large random network, simple fast algorithms find a set of unconnected nodes only half as large as the largest one that exists. The overlap gap property (good solutions form separated clusters with no intermediate overlaps) blocks many algorithms, and the question is whether every fast algorithm is blocked.

• Predicting neural scaling-law exponents from properties of the data

  Partially resolved

  The error of large neural networks falls as a power of model size and data size, with exponents that are measured but not predicted. The task is to compute those exponents from features of the training data for networks that reshape their internal features while learning.

• Sample complexity of gradient training for multi-index targets

  Partially resolved

  A network trained by stochastic gradient descent (repeated small weight updates using random batches of data) must find a few hidden directions in a high-dimensional input. The question is how many training examples it needs as the input dimension grows, compared with the minimum any fast method needs.