The Copycat Perceptron: Smashing Barriers Through Collective Learning
Giovanni Catania (Complutense University of Madrid)
The context of this talk is related to inference problems in the so-called teacher-student scenario (or planted setting), where the goal is to retrieve a ground-truth signal (specified by a teacher) from a set of – possibly noisy, or incomplete – data provided to a student. This setting offers a natural connection with Bayesian inference and statistical physics, which allows to determine specific algorithmic thresholds separating regimes – or phases in a thermodynamic sense – where signal recovery is possible or not. Among the class of inference problems that are typically studied, some of them are characterized by a « hard » inference regime, a mechanism related to the presence of first-order transitions where any polynomial optimization algorithm fails to find the solution. I this talk, I will focus on a famous example of an inference problem with an inference-hard phase, namely the binary perceptron in the teacher-student scenario, and the algorithmic properties of a specific optimization algorithm – Simulated Annealing (SA) – in its ability to find the planted configuration (i.e, the teacher’s weight vector), depending on the fraction of examples provided to the student and an external thermal noise. It is well known how SA is sensible to the presence of metastable states that can trap the dynamics into local minima with poor generalization performances; in this model, such a phenomenon occurs even in a portion of the thermodynamically easy-inference phase, where other Bayes-optimal algorithms are supposed to find the solution in polynomial time . In a different inference problem, it has recently been conjectured that replicating the systems and adding a ferromagnetic interaction between real replicas favours the resulting algorithm (Replicated SA, or RSA) to find solutions where the single system does not, as a consequence of a peculiar modification of the free energy landscape that allows the coupled system to avoid these metastable local minima. I will discuss how to characterize the phase diagram of a system made of several coupled perceptron students using techniques stemming from the statistical physics of spin-glasses, and how it modifies when considering a thermal noise affecting the generation capabilities of each of them. In this context, the replicated system can be considered as a model of collective learning among a class of students that try to learn the teacher’s rule while « cooperating » with each other. These results provide additional analytic and numerical evidence for the recently conjectured Bayes-optimal property of Replicated Simulated Annealing (RSA) for a sufficient number of replicas. From a learning perspective, these results also suggest that multiple students working together (in this case reviewing the same data) are able to learn the same rule both faster and with fewer examples, a property that could be exploited in the context of federated learning. Reference: G. Catania, A. Decelle, B. Seoane, arXiv:2308.03743