The Symmetric Perceptron: a Teacher-Student Scenario
Authors: Giovanni Catania, Aurélien Decelle, Suhanee Korpe
Organizations: Departamento de Física Teórica, Universidad Complutense de Madrid, 28040 Madrid, Spain · Institute for Cross-disciplinary Physics and Complex Systems IFISC (CSIC-UIB), Campus Universitat Illes Balears, 07122 Palma de Mallorca, Spain. · Université Paris-Saclay, CNRS, INRIA Tau team, LISN, 91190 Gif-sur-Yvette, France. · GISC - Grupo Interdisciplinar de Sistemas Complejos 28040 Madrid, France. · Indian Institute of Science Education and Research, Bhopal 462066, India
We introduce and solve a teacher-student formulation of the symmetric binary Perceptron, turning a traditionally storage-oriented model into a planted inference problem with a guaranteed solution at any sample density. We adapt the formulation of the symmetric Perceptron which traditionally considers either the u-shaped potential or the rectangular one, by including labels in both regions. With this formulation, we analyze both the Bayes-optimal regime at for noise-less examples and the effect of thermal noise under two different potential/classification rules. Using annealed and quenched free-entropy calculations in the high-dimensional limit, we map the phase diagram in the three control parameters, namely the sample density α, the distance between the origin and one of the symmetric hyperplanes κ and temperature T, and identify a robust scenario where learning is organized by a second-order instability that creates teacher-correlated suboptimal states, followed by a first-order transition to full alignment. We show how this structure depends on the choice of potential, the interplay between metastability of the suboptimal solution and its melting towards the planted configuration, which is relevant for Monte Carlo-based optimization algorithms.
Figures & tables
Figure 1: Decision boundary for a symmetric Perceptron in N=2 with w=[−1/\penalty2,1/\penalty2] and κ=1 , illustrating a case where the data in the red region are labelled +1 , while the ones in the blue region are labeled −1 .
Figure 2: Left: the potential V(0) for both labels σ0=±1 . With this potential, any error has a fixed cost. Right: the linear potential V(1) for both labels σ0=±1 . This potential tends to penalize more errors that are far away from the decision boundary.
Figure 3: Snapshots of free energy profiles at 6 different values of κ , corresponding to the thin vertical lines in Fig. 4 (left panel). Each panel ( a ) → ( f ) shows several free energy profiles f(R) at different values of α . The thicker curves correspond to the values of the first/second order transition and the spinodal (when different). In blue we illustrate first order transitions, in red second order ones and in yellow the melting (spinodal) point of the sub-optimal solution 0<R<1 . The colors used here are the same as in Fig. 4 .
Figure 4: Left: Phase diagram of the symmetric binary Perceptron at T=0 , using the annealed approximation. Right: Phase diagram of the symmetric binary Perceptron at T=0 , using the quenched approximation in the Bayes-Optimal setting. The vertical lines indicate the values of κ used on Fig. 3 (resp. Fig. 5 ) for the annealed (resp. quenched) case. In both cases, the blue line indicated the first order transition, the red line the second order one and the yellow line the spinodal, that is when the sub-optimal solution disappear. In the range of κ where the second order phase transition occurs, the dashed-blue line only corresponding to when the unstable paramagnetic state and the teacher state have the same free energy.
Figure 5: Snapshots of free energy profiles at 6 different values of κ at T=0 in the Bayes-Optimal setting. We can observe a phase diagram that is qualitatively similar to the annealed case. From small values of κ , we observe first a first order phase transition, follow by a melting toward the teacher state at higher values of α . Then, we have the at larger κ a second order phase transition before the melting.
Figure 6: Left: Phase diagram of the constant potential V0 at κ=1 . Right: Phase diagram of the piece-wise constant potential V1 at κ=1 . As in the case of the Perceptron, the orange line is expected to terminate at (0,0) . In this parameter regime, the shape of the potential strongly influences the structure of the loss landscape. For V0 , and for sufficiently large T and α , there exists a phase in which the teacher dominates the equilibrium measure, while a typical experiment remains trapped in completely uncorrelated states. In contrast, for V1 , the second-order phase transition is always dominant with respect to the other transitions and provides information about the teacher well before the latter even becomes a metastable state.
We introduce a variational approach to a finite-temperature continuous-spin perceptron trained on a Gaussian mixture. The model allows for a broad class of concave utilities and log-concave separable prior measures on the spins. By combining the interpolation method with log-concavity and concentration estimates, we derive lower and upper minimax variational bounds for the limiting quenched pressure. Remarkably, the two bounds differ only in the order of optimization of two variational parameters, while all remaining extrema are controlled by the concave--convex structure of the variational potential. Whenever the two optimizations commute, the two bounds match and identify the solution of the model. The same potential yields the fixed-point equations as stationarity conditions and provides a unified route to the computation of the ground-state energy, training loss, and generalization error.
Francesco Camilli, Pierluigi Contucci, Federica Gerace +1
Department of Mathematics, Alma Mater Studiorum – Universit`a di Bologna, Piazza di Porta San Donato 5, 40126 Bologna, Italy
Teacher-student systems, in which a teacher neural network generates training labels so that a student neural network can learn to implement the same function, are widely used as an abstract setting to study learning. However, the structure of the teachers is often overlooked by assuming randomly-generated, normally-distributed parameters. This hides substantial variation in how learnable different teachers are. We formalize learnability as the success rate of converging to the global minimum, as a function of overparameterization, learning algorithm, student initialization distribution, and teacher geometry. We both identify an easy distribution that maximizes node dissimilarity and a hard distribution that minimizes it, and show that these two distributions induce markedly different success rates across a large range of settings and for different activation functions. To explain the gap, we study the loss landscape of small neural networks that contain two distinct kinds of suboptimal local minima, out-of-bounds (OOB) minima at the edge of the data distribution and interior minima within. Assuming infinite data and a fast readout layer, we analytically reduce the loss landscape of small networks to two dimensions, showing that the region of attraction of interior minima changes as a function of teacher structure. In larger networks, maximally dissimilar teachers induce more interior minima, while minimally dissimilar teachers induce more OOB minima. Motivated by these analyses, we show that differentially increasing the learning rate of the readout layer and decreasing the learning rate of the inner biases increases success rates. These findings provide an important step in narrowing the gap between the study of teacher-student networks and more structured functions that arise in practice.
Kai J. Sandbrink, Flavio Martinelli, Alexander van Meegen +2
Department of Experimental Psychology, University of Oxford · Department of Physics, RWTH Aachen
Optimization in non-convex neural network models is strongly influenced by the geometry of the solution space: sparse, isolated, point-like clusters are typically algorithmically inaccessible, whereas wide and flat regions can be found efficiently despite being relatively rare. At zero temperature this picture has been formalized in binary perceptrons through the overlap gap property (OGP), which limits algorithmic access to configurations with zero training error above a critical constraint density αOGP. Here we extend this description to finite temperature, where a positive training error is allowed and statistically penalized. We first show that the frozen one-step replica-symmetry-breaking solution, dominating the zero temperature equilibrium measure, survives at any finite temperature. We furthermore derive a general criterion, based on the smoothness of the single-pattern Gibbs weight near the decision boundary, that determines when a finite-temperature relaxation of the loss removes freezing. We then extend the OGP construction to finite temperature and show that dense, algorithmically accessible regions of finite-energy configurations persist beyond αOGP, up to a threshold αOGP(ε) that grows with the allowed training error ε. Finally, in the teacher-student setting, we show that these wide, finite-energy regions still retain good generalization. Using a finite energy message-passing algorithm, we demonstrate numerically that thermal noise enables effective generalization in the regime of constraint densities where both recovering the teacher and finding a zero temperature solution are computationally hard.
Enrico M. Malatesta, Alessandra Passalacqua, Riccardo Zecchina
Department of Computing Sciences, Bocconi University, Milano, Italy · Bocconi Institute for Data Science and Analytics (BIDSA)