Learning curves for the multi-class teacher-student perceptron

Abstract

One of the most classical results in high-dimensional learning theory provides a closed-form expression for the generalisation error of binary classification with the single-layer teacher-student perceptron on i.i.d. Gaussian inputs. Both Bayes-optimal estimation and empirical risk minimisation (ERM) were extensively analysed for this setting. At the same time, a considerable part of modern machine learning practice concerns multi-class classification. Yet, an analogous analysis for the corresponding multi-class teacher-student perceptron was missing. In this manuscript we fill this gap by deriving and evaluating asymptotic expressions for both the Bayes-optimal and ERM generalisation errors in the high-dimensional regime. For Gaussian teacher weights, we investigate the performance of ERM with both cross-entropy and square losses, and explore the role of ridge regularisation in approaching Bayes-optimality. In particular, we observe that regularised cross-entropy minimisation yields close-to-optimal accuracy. Instead, for a binary teacher we show that a first-order phase transition arises in the Bayes-optimal performance.

arXiv comment14 pages + appendix

References in corpus (15)

• Scikit-learn: Machine Learning in Python
• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Benign Overfitting in Linear Regression
• Statistical physics of inference: Thresholds and algorithms
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Modelling the influence of data structure on learning in neural networks: the hidden manifold model
• Learning curves of generic features maps for realistic datasets with a teacher-student model
• Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization
• The committee machine: Computational to statistical gaps in learning a two-layers neural network
• Kernel Alignment Risk Estimator: Risk Prediction from Training Data
• The estimation error of general first order methods
• Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View
• Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation

Cited by in corpus (5)

• Phase transitions in the mini-batch size for sparse and dense two-layer neural networks
• The Copycat Perceptron: Smashing Barriers Through Collective Learning
• Neural-prior stochastic block model
• The RL Perceptron: Generalisation Dynamics of Policy Learning in High Dimensions
• Inference in Spreading Processes with Neural-Network Priors