Cet article démontre que les réseaux de neurones à propagation directe utilisant la fonction d'activation ReLU peuvent se généraliser à des données bien définies et peu complexes. Étant donné des données iid générées à l'aide d'un langage de programmation simple, un réseau de neurones à propagation directe à longueur de compétence minimale (MDL) interpolant les données généralise avec une forte probabilité. L'article définit ce langage de programmation simple et le concept de longueur de compétence pour un tel réseau de neurones. Il fournit plusieurs exemples de tâches de calcul élémentaires, telles que la détection de primalité. Pour la détection de primalité, le théorème énonce ce qui suit : considérons un échantillon iid de n nombres tirés uniformément au hasard de 1 à N. Pour chaque nombre xi, si xi est premier, yi = 1 ; sinon, yi = 0. Ensuite, un réseau MDL interpolant répond correctement à la question de savoir si un nombre nouvellement tiré de 1 à N est premier ou non, avec une probabilité d'erreur de 1-O(ln N)/n). Notez que le réseau n'est pas conçu pour détecter les nombres premiers ; l'apprentissage de la compétence minimale découvre les réseaux qui le font. Les extensions aux données bruyantes sont également discutées, suggérant que les interpolateurs de réseaux neuronaux MDL peuvent présenter un léger surajustement.
