# Large deviations in the perceptron model and consequences for active learning

H Cui, L Saglietti, L Zdeborová

► To cite this version:

H Cui, L Saglietti, L Zdeborová. Large deviations in the perceptron model and consequences for active learning. Machine Learning: Science and Technology, 2021, 2 (4), pp.045001. 10.1088/2632-2153/abfbbb.cea-04542510

HAL Id: cea-04542510

https://cea.hal.science/cea-04542510

Submitted on 11 Apr 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Large deviations in the perceptron model and consequences for active learning

H Cui, L Saglietti, L Zdeborová

► To cite this version:

H Cui, L Saglietti, L Zdeborová. Large deviations in the perceptron model and consequences for active learning. Machine Learning: Science and Technology, 2021, 2 (4), pp.045001. 10.1088/2632-2153/abfbbb.cea-04542510

HAL Id: cea-04542510

https://cea.hal.science/cea-04542510v1

Submitted on 11 Apr 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Large Deviations for the Perceptron Model and Consequences for Active Learning

Hugo Cui*

École Normale Supérieure, PSL University, Paris, France

Luca Saglietti†

LPENS, CNRS & Sorbonnes Universités, École Normale Supérieure, PSL University, Paris, France

Lenka Zdeborová‡

Institut de Physique Théorique, CNRS & CEA & Université Paris-Saclay, Saclay, France

(Dated: December 10, 2019)

Active learning is a branch of machine learning that deals with problems where unlabeled data is abundant yet obtaining labels is expensive. The learning algorithm has the possibility of querying a limited number of samples to obtain the corresponding labels, subsequently used for supervised learning. In this work, we consider the task of choosing the subset of samples to be labeled from a fixed finite pool of samples. We assume the pool of samples to be a random matrix and the ground truth labels to be generated by a single-layer teacher random neural network. We employ replica methods to analyze the large deviations for the accuracy achieved after supervised learning on a subset of the original pool. These large deviations then provide optimal achievable performance boundaries for any active learning algorithm. We show that the optimal learning performance can be efficiently approached by simple message-passing active learning algorithms. We also provide a comparison with the performance of some other popular active learning strategies.

Keywords: Active learning, Large Deviations, Perceptron Model, Message-passing algorithms

# I. INTRODUCTION

Supervised learning consists in presenting a parametric function (often a neural network) with a series of samples (samples) and labels, and adjusting (training) the parameters (network weights) so as to match the network output with the labels as closely as possible. Active learning (AL) is concerned with choosing the most informative samples so that the training requires the least number of labeled samples to reach the same test accuracy. Active learning is relevant in situations where the potential set of samples is large, but obtaining the labels is expensive (computationally or otherwise). There exist many strategies for active learning, see e.g. [1] for a review. In membership-based active learning [2], [3], [4] the algorithm is allowed to query the label of any sample, most often one it generates itself. In stream-based active learning [5] an infinite sequence of samples is presented to the learner which can decide whether or not to query its label. In pool-based active learning, which is the object of the present work, the learner can only query samples that belong to a pre-existing, fixed pool of samples. It therefore needs to choose according to some strategy which samples to query so as to have the best possible test accuracy.

Pool-based active learning is relevant for many machine learning applications, e.g. because not every possible input vector is of relevance. A beautiful recent application of active learning is in computational chemistry [6] where a neural network is trained to predict inter-atomic potentials. In this case the pool of data is large and consists in all possible alloys, but not of arbitrary input vectors, and labelling is extremely expensive, as it demands resource-intensive ab initio simulations. Consequently, only a limited number of samples can be labeled, i.e. one only possesses a certain budget for the cardinal of the training set. Another setting where a cheap large pool of input data is readily available but labelling is expensive is drug discovery [7], where given a target molecule one aims to find new compounds among the pool able to bind it. Another example would be on text classification [8], [9], [10], where labelling a text requires non-negligible human input, while a large pool of texts is readily available on the internet. Establishing efficient pool-based active learning procedures in this case implies to select a priori the most informative data samples for labelling.

Main-stream works on active learning focus on designing heuristic algorithmic strategies in a variety of settings, and analyzing the performance thereof. It is very rarely known what are the information-theoretic limitations an active learning algorithm can face and hence evaluating the distance from optimality is mostly an open question. The main

<footnote>* hugo.cui@ens.fr</footnote>

<footnote>† luca.saglietti@lpens.ens.fr</footnote>

<footnote>‡ lenka.zdeborova@cea.fr</footnote>
Large Deviations for the Perceptron Model and Consequences for Active Learning

Hugo Cui*

École Normale Supérieure, PSL University, Paris, France

Luca Saglietti†

LPENS, CNRS & Sorbonnes Universités, École Normale Supérieure, PSL University, Paris, France

Lenka Zdeborová‡

Institut de Physique Théorique, CNRS & CEA & Université Paris-Saclay, Saclay, France

(Dated: December 10, 2019)

Active learning is a branch of machine learning that deals with problems where unlabeled data is abundant yet obtaining labels is expensive. The learning algorithm has the possibility of querying a limited number of samples to obtain the corresponding labels, subsequently used for supervised learning. In this work, we consider the task of choosing the subset of samples to be labeled from a fixed finite pool of samples. We assume the pool of samples to be a random matrix and the ground truth labels to be generated by a single-layer teacher random neural network. We employ replica methods to analyze the large deviations for the accuracy achieved after supervised learning on a subset of the original pool. These large deviations then provide optimal achievable performance boundaries for any active learning algorithm. We show that the optimal learning performance can be efficiently approached by simple message-passing active learning algorithms. We also provide a comparison with the performance of some other popular active learning strategies.

Keywords: Active learning, Large Deviations, Perceptron Model, Message-passing algorithms

# I. INTRODUCTION

Supervised learning consists in presenting a parametric function (often a neural network) with a series of samples (samples) and labels, and adjusting (training) the parameters (network weights) so as to match the network output with the labels as closely as possible. Active learning (AL) is concerned with choosing the most informative samples so that the training requires the least number of labeled samples to reach the same test accuracy. Active learning is relevant in situations where the potential set of samples is large, but obtaining the labels is expensive (computationally or otherwise). There exist many strategies for active learning, see e.g. [1] for a review. In membership-based active learning [2], [3], [4] the algorithm is allowed to query the label of any sample, most often one it generates itself. In stream-based active learning [5] an infinite sequence of samples is presented to the learner which can decide whether or not to query its label. In pool-based active learning, which is the object of the present work, the learner can only query samples that belong to a pre-existing, fixed pool of samples. It therefore needs to choose according to some strategy which samples to query so as to have the best possible test accuracy.

Pool-based active learning is relevant for many machine learning applications, e.g. because not every possible input vector is of relevance. A beautiful recent application of active learning is in computational chemistry [6] where a neural network is trained to predict inter-atomic potentials. In this case the pool of data is large and consists in all possible alloys, but not of arbitrary input vectors, and labelling is extremely expensive, as it demands resource-intensive ab initio simulations. Consequently, only a limited number of samples can be labeled, i.e. one only possesses a certain budget for the cardinal of the training set. Another setting where a cheap large pool of input data is readily available but labelling is expensive is drug discovery [7], where given a target molecule one aims to find new compounds among the pool able to bind it. Another example would be on text classification [8], [9], [10], where labelling a text requires non-negligible human input, while a large pool of texts is readily available on the internet. Establishing efficient pool-based active learning procedures in this case implies to select a priori the most informative data samples for labelling.

Main-stream works on active learning focus on designing heuristic algorithmic strategies in a variety of settings, and analyzing the performance thereof. It is very rarely known what are the information-theoretic limitations an active learning algorithm can face and hence evaluating the distance from optimality is mostly an open question. The main

<footnote>* hugo.cui@ens.fr</footnote>

<footnote>† luca.saglietti@lpens.ens.fr</footnote>

<footnote>‡ lenka.zdeborova@cea.fr</footnote>
contribution of the present work is to provide a toy model that is at the one hand challenging for active learning, and at the same time where the optimal performance of pool-based active learning can be computed and heuristic algorithms hence evaluated and bench-marked against the optimal solution. To our knowledge, this is the first work to derive optimal performance results for pool-based active learning procedures are computed. More specifically we study the random perceptron model [11]. The available pool of samples is assumed to be i.i.d. normal vectors, the teacher generating the labels is taken to be also a perceptron with the vector of teacher-weights having i.i.d. normal components. We compute the large deviation function for how likely one is to find a subset of the samples that leads to a given learning accuracy. Our results are based on the replica method computation of this large deviation function, that is an exact method (modulo the possibility of the so-called replica symmetry breaking that we are not evaluating in the present work) originating in theoretical statistical physics [12]; [13]; [14]. Providing a rigorous proof of the obtained results or turning them into rigorous bounds would be a natural, and rather challenging, next step. In the algorithmic part of this work we benchmark several existing algorithms and also propose two new algorithms relying on the approximate-message-passing algorithm for estimation of the label uncertainty for yet unlabeled sample, showing that they closely achieve, in the studied cases, the relevant information-theoretic limitations.

The paper is organized as follows: the problem is defined and related work discussed in section II. In section III, we propose a measure to quantify the informativeness of given subsets of samples. In section IV, we derive the large deviation function over all possible subset choices and deduce performance boundaries that apply to any pool-based active learning strategy. In section V, we then compare these theoretical results with the performance of existing active learning algorithms and propose two new ones, based on approximate-message-passing.

## II. DEFINITION OF THE PROBLEM AND RELATED WORK

A natural modeling framework for analyzing learning processes and generalization properties is the so-called teacher-student (or planted) perceptron model [15], where the input samples are assumed to be random i.i.d. vectors, and the ground truth labels are assumed to be generated by a neural network (denoted as the teacher) belonging to the same hypothesis class as the student-neural-network. In this work we will restrict to single-layer neural networks (without hidden units) for which this setting was defined and studied in [16]. Specifically we collect the input vectors into a matrix $\mathbf{F} \in \mathbb{R}^{P \times N}$ where $N$ is the dimension of the input space and $P$ is the number of samples. The teacher generating the labels, called teacher perceptron, is characterized by a teacher-vector of weights $\mathbf{x}^0$ and produces the label vector $\mathbf{Y} \in \mathbb{R}^P$ according to $\mathbf{Y} = \text{sign}(\mathbf{F} \cdot \mathbf{x}^0)$. Learning is then done using a student perceptron and consists in finding a vector $\mathbf{x}$ so that for the training set $\mathbf{F}$ we have as closely as possible $\mathbf{Y} = \text{sign}(\mathbf{F} \cdot \mathbf{x})$. The relevant notion of error is the test accuracy (generalization error) measuring the agreement between the teacher and the student on a new sample not presented in the training set. Since both teacher and student possess the same architecture, the training process can be rephrased in terms of an inference problem (as discussed for instance in [15]): the student aims to infer the teacher weights, used to generate the labels, from the knowledge of a set of input-output associations. This scenario allows for nice geometrical insights (see for example [17]), as the generalization properties are linked to the distance in weight space between teacher and student functions. Note that, in the case of a noiseless labelling process, the teacher-student scenario guarantees that perfect training is always possible.

Active learning was previously studied in the context of the teacher-student perceptron problem. Best known is the line of work on Query by Committee [4, 18, 19], dealing with the membership based active learning setting, i.e. where the samples are picked one by one into the training set and can be absolutely arbitrary $N$-dimensional vectors. The active learning is in that case more a strategy for designing the samples rather than one for selecting them smartly from an predefined set. In the original work [4] the new samples are chosen so that a committee of several student-neural-networks has the maximum possible disagreement on the new sample. The paper shows that in this way one can reach a generalization error that decreases exponentially with the size of the training set, while for a random training set the generalization error can decrease only inversely proportionally to the size of the set [17]. However, in many practical applications the possible set of samples to be picked into the training set is not arbitrarily big, e.g. not every input vector represents an encoding of a molecular structure. We hence argue that the pool-based active learning, studied in the present paper, where the samples are selected from a pre-defined set is of larger relevance to many applications.

The theoretical part of this paper is presented for a generalization of the perceptron model, specifically the for the random teacher-student Generalized Linear Models (GLM), see e.g. [20]. An instance of a GLM is specified by a prior measure on the weights $P_X(\cdot)$, from which the true generative model is assumed to be sampled, and an output channel measure $P_{\text{out}}(\cdot|\cdot)$, defining the generative process for the labels given the pre-activations. In the part where results of this work are presented we focus on the prototypical case of the noiseless continuous perceptron, where $P_X(x) = e^{-\frac{x^2}{2}}/\sqrt{2\pi}$ and $P_{\text{out}}(y|h) = \delta(y - \text{sign}(h))$ where for example $\mu$ we have $h^\mu = \mathbf{F}^\mu \cdot \mathbf{x}$. Moreover, we will consider the setting where the learning model is matched to the generative model and thus the student has perfect
contribution of the present work is to provide a toy model that is at the one hand challenging for active learning, and at the same time where the optimal performance of pool-based active learning can be computed and heuristic algorithms hence evaluated and bench-marked against the optimal solution. To our knowledge, this is the first work to derive optimal performance results for pool-based active learning procedures are computed. More specifically we study the random perceptron model [11]. The available pool of samples is assumed to be i.i.d. normal vectors, the teacher generating the labels is taken to be also a perceptron with the vector of teacher-weights having i.i.d. normal components. We compute the large deviation function for how likely one is to find a subset of the samples that leads to a given learning accuracy. Our results are based on the replica method computation of this large deviation function, that is an exact method (modulo the possibility of the so-called replica symmetry breaking that we are not evaluating in the present work) originating in theoretical statistical physics [12]; [13]; [14]. Providing a rigorous proof of the obtained results or turning them into rigorous bounds would be a natural, and rather challenging, next step. In the algorithmic part of this work we benchmark several existing algorithms and also propose two new algorithms relying on the approximate-message-passing algorithm for estimation of the label uncertainty for yet unlabeled sample, showing that they closely achieve, in the studied cases, the relevant information-theoretic limitations.

The paper is organized as follows: the problem is defined and related work discussed in section II. In section III, we propose a measure to quantify the informativeness of given subsets of samples. In section IV, we derive the large deviation function over all possible subset choices and deduce performance boundaries that apply to any pool-based active learning strategy. In section V, we then compare these theoretical results with the performance of existing active learning algorithms and propose two new ones, based on approximate-message-passing.

## II. DEFINITION OF THE PROBLEM AND RELATED WORK

A natural modeling framework for analyzing learning processes and generalization properties is the so-called teacher-student (or planted) perceptron model [15], where the input samples are assumed to be random i.i.d. vectors, and the ground truth labels are assumed to be generated by a neural network (denoted as the teacher) belonging to the same hypothesis class as the student-neural-network. In this work we will restrict to single-layer neural networks (without hidden units) for which this setting was defined and studied in [16]. Specifically we collect the input vectors into a matrix $\mathbf{F} \in \mathbb{R}^{P \times N}$ where $N$ is the dimension of the input space and $P$ is the number of samples. The teacher generating the labels, called teacher perceptron, is characterized by a teacher-vector of weights $\mathbf{x}^0$ and produces the label vector $\mathbf{Y} \in \mathbb{R}^P$ according to $\mathbf{Y} = \text{sign}(\mathbf{F} \cdot \mathbf{x}^0)$. Learning is then done using a student perceptron and consists in finding a vector $\mathbf{x}$ so that for the training set $\mathbf{F}$ we have as closely as possible $\mathbf{Y} = \text{sign}(\mathbf{F} \cdot \mathbf{x})$. The relevant notion of error is the test accuracy (generalization error) measuring the agreement between the teacher and the student on a new sample not presented in the training set. Since both teacher and student possess the same architecture, the training process can be rephrased in terms of an inference problem (as discussed for instance in [15]): the student aims to infer the teacher weights, used to generate the labels, from the knowledge of a set of input-output associations. This scenario allows for nice geometrical insights (see for example [17]), as the generalization properties are linked to the distance in weight space between teacher and student functions. Note that, in the case of a noiseless labelling process, the teacher-student scenario guarantees that perfect training is always possible.

Active learning was previously studied in the context of the teacher-student perceptron problem. Best known is the line of work on Query by Committee [4, 18, 19], dealing with the membership based active learning setting, i.e. where the samples are picked one by one into the training set and can be absolutely arbitrary $N$-dimensional vectors. The active learning is in that case more a strategy for designing the samples rather than one for selecting them smartly from an predefined set. In the original work [4] the new samples are chosen so that a committee of several student-neural-networks has the maximum possible disagreement on the new sample. The paper shows that in this way one can reach a generalization error that decreases exponentially with the size of the training set, while for a random training set the generalization error can decrease only inversely proportionally to the size of the set [17]. However, in many practical applications the possible set of samples to be picked into the training set is not arbitrarily big, e.g. not every input vector represents an encoding of a molecular structure. We hence argue that the pool-based active learning, studied in the present paper, where the samples are selected from a pre-defined set is of larger relevance to many applications.

The theoretical part of this paper is presented for a generalization of the perceptron model, specifically the for the random teacher-student Generalized Linear Models (GLM), see e.g. [20]. An instance of a GLM is specified by a prior measure on the weights $P_X(\cdot)$, from which the true generative model is assumed to be sampled, and an output channel measure $P_{\text{out}}(\cdot|\cdot)$, defining the generative process for the labels given the pre-activations. In the part where results of this work are presented we focus on the prototypical case of the noiseless continuous perceptron, where $P_X(x) = e^{-\frac{x^2}{2}}/\sqrt{2\pi}$ and $P_{\text{out}}(y|h) = \delta(y - \text{sign}(h))$ where for example $\mu$ we have $h^\mu = \mathbf{F}^\mu \cdot \mathbf{x}$. Moreover, we will consider the setting where the learning model is matched to the generative model and thus the student has perfect
knowledge on the correct form of the two above defined measures.

The pool-based active learning task can now be more formally stated as follows: given a set of $N$-dimensional samples $S = \{F^\mu\}$ of cardinality $|S| = P = \alpha N$, the goal is to select and query the labels of a subset $S \in S$ of cardinality $|S| = nN$, $0 < n \le \alpha$, according to some active learning criterion. We will refer to $n$ as the budget of the student. The true labels are then obtained through $y^\mu \sim P_{\text{out}}(y^\mu|F^\mu \cdot x^0)$, $x^0 \sim P_X(x^0)$. Henceforth measures with vector arguments are understood to be products over the coordinates of the corresponding scalar measures. For technical reasons, we rely on the strong (but customary) assumption that the samples are i.i.d. Gaussian distributed, $F_i^\mu \sim N(0, 1)$, $\forall i \in \{1, ..., N\}$, $\forall \mu \in \{1, ..., P\}$. Note that, while this assumption implies that the full set $S$ of input data is generally unstructured and uncorrelated, it does not prevent non-trivial correlations to appear in any smaller labeled subset $S$, selected through an active learning procedure.

In pool-based active learning settings, it is assumed that the student has a fixed budget $n$ for building its training set, i.e. that only up to $nN$ labels can be queried for training. The active learning goal is to select, among the pool $S$ of available samples, the $nN$ most informative labels, to present to the student so that the latter achieves the best possible generalization performance. While many criteria of informativeness have been considered in the literature, see e. g. [1], in the teacher-student setting there exist a natural measure of informativeness, which we shall define in the next section.

### III. THE GARDNER VOLUME AS A MEASURE OF OPTIMALITY

A natural strategy for ranking the possible subset selections is to evaluate the mutual information between the teacher vector $x^0$ and each subset of labels $Y$, conditioned on the corresponding inputs $F$. Good selections contain larger amounts of information about the ground truth, encoded in the labels, and make the associated inference problem for the student easier. Conversely, bad selections are characterized by less informative labels. In the case of the teacher-student perceptron, where the output channel $P_{\text{out}}(\cdot|\cdot)$ is completely deterministic and binary, the mutual information can be rewritten (following [20]) as

$$ \begin{aligned} \mathcal{I}(x^0; Y|F) &= \mathcal{H}(Y|F) - \mathcal{H}(Y|F, x^0) = \mathcal{H}(Y|F) \\ &= -\int dY \int dx^0 P_X(x^0) P_{\text{out}}(Y|F \cdot x^0) \ln \int dx P_X(x) P_{\text{out}}(Y|F \cdot x). \end{aligned} \quad (1) $$

Equation (1) allows a connection with a quantity well-known in statistical physics, the so-called Gardner volume [11], [21], [17], denoted in the following by $v$

$$ \ln v = \frac{1}{N} \mathbb{E}_{x^0, Y} \ln \int dx P_X(x) P_{\text{out}}(Y|F \cdot x). \quad (2) $$

The Gardner volume $v$ represents the extent of the version space [22], i.e. the entropy of hypotheses in the model class consistent with the labeled training set. This provides a natural measure of the quality of the student training. A narrower volume implies less uncertainty about the ground truth $x^0$ and is thus a desirable objective in an active learning framework. We shall focus the rest of our discussion on the large deviation properties of the Gardner volume, but we invite the reader to keep in mind that this is equivalent to studying the above defined mutual information.

There exist other natural measures of informativeness, e.g. the student generalization error $\epsilon_g$ and the magnetization (or teacher/student overlap) $m = x \cdot x^0/N$. In the thermodynamic limit $N \uparrow \infty$, $\epsilon_g$ is a decreasing function of $m$ (see the appendix D for more details). Moreover we will show analytical and numerical evidence that all these measures co-vary, at least in the simple teacher-student setting studied in this work. A numerical check at finite $N$ of the correlation between $v$ and $m$ can also be found in appendix E.

### IV. LARGE DEVIATIONS OF THE GARDNER VOLUME

We consider the problem of sampling labeled subsets of cardinality $nN$, $0 < n \le \alpha$, from a fixed pool of data of cardinality $\alpha N$, $\alpha \sim O(1)$, and study the variations in the associated Gardner volumes. We will hereby consider that, for any fixed pool and subset size, the Gardner volume probability distribution follows a large deviation principle, i.e. that there exist an exponential number $e^{N\Sigma(n,v)}$ of subsets choices that produce Gardner volumes equal to $v$. Employing a statistical physics terminology, we will refer to the rate function, $\Sigma(n,v)$, as the complexity of labeled subsets associated to a budget $n$ and a volume $v$.

In the large $N$ limit, the overwhelming majority of subsets will thus realize a Gardner volume $v^*$, such that $v^* = \argmax_v \Sigma(n,v)$. This means that, since the fluctuations around this typical value are exponentially rare, random
knowledge on the correct form of the two above defined measures.

The pool-based active learning task can now be more formally stated as follows: given a set of $N$-dimensional samples $S = \{F^\mu\}$ of cardinality $|S| = P = \alpha N$, the goal is to select and query the labels of a subset $S \in S$ of cardinality $|S| = nN$, $0 < n \le \alpha$, according to some active learning criterion. We will refer to $n$ as the budget of the student. The true labels are then obtained through $y^\mu \sim P_{\text{out}}(y^\mu|F^\mu \cdot x^0)$, $x^0 \sim P_X(x^0)$. Henceforth measures with vector arguments are understood to be products over the coordinates of the corresponding scalar measures. For technical reasons, we rely on the strong (but customary) assumption that the samples are i.i.d. Gaussian distributed, $F_i^\mu \sim \mathcal{N}(0, 1)$, $\forall i \in \{1, ..., N\}$, $\forall \mu \in \{1, ..., P\}$. Note that, while this assumption implies that the full set $S$ of input data is generally unstructured and uncorrelated, it does not prevent non-trivial correlations to appear in any smaller labeled subset $S$, selected through an active learning procedure.

In pool-based active learning settings, it is assumed that the student has a fixed budget $n$ for building its training set, i.e. that only up to $nN$ labels can be queried for training. The active learning goal is to select, among the pool $S$ of available samples, the $nN$ most informative labels, to present to the student so that the latter achieves the best possible generalization performance. While many criteria of informativeness have been considered in the literature, see e. g. [1], in the teacher-student setting there exist a natural measure of informativeness, which we shall define in the next section.

### III. THE GARDNER VOLUME AS A MEASURE OF OPTIMALITY

A natural strategy for ranking the possible subset selections is to evaluate the mutual information between the teacher vector $x^0$ and each subset of labels $Y$, conditioned on the corresponding inputs $F$. Good selections contain larger amounts of information about the ground truth, encoded in the labels, and make the associated inference problem for the student easier. Conversely, bad selections are characterized by less informative labels. In the case of the teacher-student perceptron, where the output channel $P_{\text{out}}(\cdot|\cdot)$ is completely deterministic and binary, the mutual information can be rewritten (following [20]) as

$$ 
\begin{aligned}
\mathcal{I}(x^0; Y|F) &= \mathcal{H}(Y|F) - \mathcal{H}(Y|F, x^0) = \mathcal{H}(Y|F) \\
&= -\int dY \int dx^0 P_X(x^0) P_{\text{out}}(Y|F \cdot x^0) \ln \int dx P_X(x) P_{\text{out}}(Y|F \cdot x).
\end{aligned} 
\quad (1) 
$$

Equation (1) allows a connection with a quantity well-known in statistical physics, the so-called Gardner volume [11], [21], [17], denoted in the following by $v$

$$ \ln v = \frac{1}{N} \mathbb{E}_{x^0, Y} \ln \int dx P_X(x) P_{\text{out}}(Y|F \cdot x). \quad (2) $$

The Gardner volume $v$ represents the extent of the version space [22], i.e. the entropy of hypotheses in the model class consistent with the labeled training set. This provides a natural measure of the quality of the student training. A narrower volume implies less uncertainty about the ground truth $x^0$ and is thus a desirable objective in an active learning framework. We shall focus the rest of our discussion on the large deviation properties of the Gardner volume, but we invite the reader to keep in mind that this is equivalent to studying the above defined mutual information.

There exist other natural measures of informativeness, e.g. the student generalization error $\epsilon_g$ and the magnetization (or teacher/student overlap) $m = x \cdot x^0/N$. In the thermodynamic limit $N \uparrow \infty$, $\epsilon_g$ is a decreasing function of $m$ (see the appendix D for more details). Moreover we will show analytical and numerical evidence that all these measures co-vary, at least in the simple teacher-student setting studied in this work. A numerical check at finite $N$ of the correlation between $v$ and $m$ can also be found in appendix E.

### IV. LARGE DEVIATIONS OF THE GARDNER VOLUME

We consider the problem of sampling labeled subsets of cardinality $nN$, $0 < n \le \alpha$, from a fixed pool of data of cardinality $\alpha N$, $\alpha \sim \mathcal{O}(1)$, and study the variations in the associated Gardner volumes. We will hereby consider that, for any fixed pool and subset size, the Gardner volume probability distribution follows a large deviation principle, i.e. that there exist an exponential number $e^{N\Sigma(n,v)}$ of subsets choices that produce Gardner volumes equal to $v$. Employing a statistical physics terminology, we will refer to the rate function, $\Sigma(n, v)$, as the complexity of labeled subsets associated to a budget $n$ and a volume $v$.

In the large $N$ limit, the overwhelming majority of subsets will thus realize a Gardner volume $v^*$, such that $v^* = \argmax_v \Sigma(n, v)$. This means that, since the fluctuations around this typical value are exponentially rare, random
sampling will almost certainly yield Gardner volumes extremely close to $v^*$. However, the aim of active learning is to find strategies for accessing the atypically informative subsets (i.e., the atypically small volumes $v < v^*$), whence the necessity of analyzing the large deviations properties of the subset selection process.

We will here give a brief outline of the analytic computation, based on standard methods from physics of disordered systems [12], [13], [14], and refer the reader to appendices A, B and C for a more detailed derivation. It is convenient to introduce a vector of selection variables $\{\sigma_\mu\}_{0\le\mu\le\alpha N} \in \{0, 1\}^{\alpha N}$, such that $\sigma_\mu = 1$ when the sample $F_\mu \in S$ is selected (and added to the labeled training set), while $\sigma_\mu = 0$ otherwise. In this notation the selected subset $S \subset S$ is easily defined as $S = \{F_\mu \in S | \sigma_\mu = 1\}$.

Since a direct computation of the complexity is not straightforward, as customary in this type of analyses [23] we derive it by first evaluating its Legendre transform. We introduce the (unnormalized) measure over the selection variables

$$ \mathbb{P}_{\beta, \phi}(\{\sigma_{\mu}\}) = \left[ \int dx P_X(x) \prod_{\mu=1}^{\alpha N} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \cdot \mathbf{x})^{\sigma_{\mu}} \right]^{\beta} e^{\phi \sum_{\mu} \sigma_{\mu}} \quad (3) $$

and the associated free entropy

$$ \Phi(\beta, \phi) = \mathbb{E}_{F, x^0} \frac{1}{N} \ln \Xi = \mathbb{E}_{F, x^0} \frac{1}{N} \ln \sum_{\sigma_{\mu}} \mathbb{P}_{\beta, \phi}(\{\sigma_{\mu}\}). \quad (4) $$

From a statistical physics perspective, $\Xi$ can be regarded as a grand-canonical partition function, with $\beta$ playing the role of an inverse temperature, the Gardner volume being the associated energy function, and where $\phi$ is an effective chemical potential controlling the cardinality of the selection subset, $|S|$. In the thermodynamic limit $N \uparrow \infty$, by applying the saddle-point method one can easily see that $\Phi(\beta, \phi)$ will be dominated by a subset of selection vectors $\{\sigma_\mu\}$ whose budget and energy, $n^*$ and $v^*$, are given by

$$ \Phi(\beta, \phi) = \underset{v,n}{\operatorname{extr}} \{\Sigma(n, v) + \beta \ln v + \phi n\}. \quad (5) $$

Thus, inverting the Legendre transform yields the sought complexity

$$ \Sigma(n, v) = \Phi(\beta, \phi) - \beta \ln v - n\phi|_{\partial_{\beta}\Phi=\text{inv}, \partial_{\phi}\Phi=n}. \quad (6) $$

At fixed budget $n$, the range of values of the volume $v$ associated to positive complexities, i.e. with $\Sigma(n, v) > 0$, effectively spans all the achievable Gardner volumes for subsets of that given cardinality, agnostic of the actual strategy for selecting them. In particular, $\inf_{v}\{v|\Sigma(n, v) > 0\}$ and $\sup_{v}\{v|\Sigma(n, v) > 0\}$ define the minimal and maximal Gardner volumes and provide theoretical algorithmic boundaries for all realizable active learning strategies. Note that this means that our prototypical model, albeit being idealized, constitutes a nice benchmark for comparing known pool-based active learning heuristics.

## A. Replica symmetric formula for the large deviations

In practice, the analytic evaluation of $\Phi(\beta, \phi)$ involves the computation of a quenched average of a log-partition function and is not feasible via rigorous methods. In order to perform the computation, we resort to the replica method from statistical physics [12], [13], [14], based on the identity

$$ \Phi(\beta, \phi) = \mathbb{E}_{F, x^0} \frac{1}{N} \ln \Xi = \mathbb{E}_{F, x^0} \frac{1}{N} \lim_{s \to 0} \Xi^s, \quad (7) $$

and the fact that for integer values $s$ the $\mathbb{E}_{F, x^0} \Xi^s$ can be computed. We refer the interested reader to appendix B, where the computation is explicit in the more general case of a generalized linear model [24], [20], and then specialized to the case of interest of a teacher-student perceptron. The final analytic expression for the replica symmetric free entropy $\Phi_{RS}$ in this special case reads

$$ \begin{aligned} \Phi_{RS}(\beta, \phi) = \underset{\hat{m}, \hat{r}, \hat{q}, \hat{Q}, m, r, q, Q}{\operatorname{extr}} & \left\{ \frac{\beta}{2} r \hat{r} - \beta m \hat{m} - \frac{\beta(\beta-1)}{2} Q \hat{Q} + \frac{\beta^2}{2} q \hat{q} - \frac{\beta-1}{2} \ln(1+\hat{r}+\hat{Q}) \right. \\ & \left. - \frac{1}{2} \ln(1+\hat{r}-(\beta-1)\hat{Q}+\beta\hat{q}) + \frac{\beta}{2} \frac{\hat{q}+\hat{m}^2}{1+\hat{r}-(\beta-1)\hat{Q}+\beta\hat{q}} \right. \\ & \left. + 2\alpha \int D\eta H \left( -\sqrt{\frac{m^2}{q-m^2}\eta} \right) \ln \left[ 1+e^{\phi} \int D\zeta H \left( -\frac{1}{\sqrt{r-Q}}(\sqrt{Q-q\zeta}+\sqrt{q\eta}) \right)^{\beta} \right] \right\}, \end{aligned} \quad (8) $$
sampling will almost certainly yield Gardner volumes extremely close to $v^*$. However, the aim of active learning is to find strategies for accessing the atypically informative subsets (i.e., the atypically small volumes $v < v^*$), whence the necessity of analyzing the large deviations properties of the subset selection process.

We will here give a brief outline of the analytic computation, based on standard methods from physics of disordered systems [12], [13], [14], and refer the reader to appendices A, B and C for a more detailed derivation. It is convenient to introduce a vector of selection variables $\{\sigma_\mu\}_{0\le\mu\le\alpha N} \in \{0, 1\}^{\alpha N}$, such that $\sigma_\mu = 1$ when the sample $F_\mu \in S$ is selected (and added to the labeled training set), while $\sigma_\mu = 0$ otherwise. In this notation the selected subset $S \subset S$ is easily defined as $S = \{F_\mu \in S | \sigma_\mu = 1\}$.

Since a direct computation of the complexity is not straightforward, as customary in this type of analyses [23] we derive it by first evaluating its Legendre transform. We introduce the (unnormalized) measure over the selection variables

$$ \mathbb{P}_{\beta, \phi}(\{\sigma_{\mu}\}) = \left[ \int dx P_X(x) \prod_{\mu=1}^{\alpha N} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \cdot \mathbf{x})^{\sigma_{\mu}} \right]^{\beta} e^{\phi \sum_{\mu} \sigma_{\mu}} \quad (3) $$

and the associated free entropy

$$ \Phi(\beta, \phi) = \mathbb{E}_{F, x^0} \frac{1}{N} \ln \Xi = \mathbb{E}_{F, x^0} \frac{1}{N} \ln \sum_{\sigma_{\mu}} \mathbb{P}_{\beta, \phi}(\{\sigma_{\mu}\}). \quad (4) $$

From a statistical physics perspective, $\Xi$ can be regarded as a grand-canonical partition function, with $\beta$ playing the role of an inverse temperature, the Gardner volume being the associated energy function, and where $\phi$ is an effective chemical potential controlling the cardinality of the selection subset, $|S|$. In the thermodynamic limit $N \uparrow \infty$, by applying the saddle-point method one can easily see that $\Phi(\beta, \phi)$ will be dominated by a subset of selection vectors $\{\sigma_\mu\}$ whose budget and energy, $n^*$ and $v^*$, are given by

$$ \Phi(\beta, \phi) = \underset{v,n}{\operatorname{extr}} \{\Sigma(n, v) + \beta \ln v + \phi n\}. \quad (5) $$

Thus, inverting the Legendre transform yields the sought complexity

$$ \Sigma(n, v) = \Phi(\beta, \phi) - \beta \ln v - n\phi|_{\partial_{\beta}\Phi=\text{inv}, \partial_{\phi}\Phi=n}. \quad (6) $$

At fixed budget $n$, the range of values of the volume $v$ associated to positive complexities, i.e. with $\Sigma(n, v) > 0$, effectively spans all the achievable Gardner volumes for subsets of that given cardinality, agnostic of the actual strategy for selecting them. In particular, $\inf_v \{v|\Sigma(n, v) > 0\}$ and $\sup_v \{v|\Sigma(n, v) > 0\}$ define the minimal and maximal Gardner volumes and provide theoretical algorithmic boundaries for all realizable active learning strategies. Note that this means that our prototypical model, albeit being idealized, constitutes a nice benchmark for comparing known pool-based active learning heuristics.

## A. Replica symmetric formula for the large deviations

In practice, the analytic evaluation of $\Phi(\beta, \phi)$ involves the computation of a quenched average of a log-partition function and is not feasible via rigorous methods. In order to perform the computation, we resort to the replica method from statistical physics [12], [13], [14], based on the identity

$$ \Phi(\beta, \phi) = \mathbb{E}_{F, x^0} \frac{1}{N} \ln \Xi = \mathbb{E}_{F, x^0} \frac{1}{N} \lim_{s \to 0} \Xi^s, \quad (7) $$

and the fact that for integer values $s$ the $\mathbb{E}_{F, x^0} \Xi^s$ can be computed. We refer the interested reader to appendix B, where the computation is explicit in the more general case of a generalized linear model [24], [20], and then specialized to the case of interest of a teacher-student perceptron. The final analytic expression for the replica symmetric free entropy $\Phi_{RS}$ in this special case reads

$$ \begin{aligned} \Phi_{RS}(\beta, \phi) = \underset{\hat{m}, \hat{r}, \hat{q}, \hat{Q}, m, r, q, Q}{\operatorname{extr}} & \left\{ \frac{\beta}{2} r \hat{r} - \beta m \hat{m} - \frac{\beta(\beta-1)}{2} Q \hat{Q} + \frac{\beta^2}{2} q \hat{q} - \frac{\beta-1}{2} \ln(1+\hat{r}+\hat{Q}) \right. \\ & \left. - \frac{1}{2} \ln(1+\hat{r}-(\beta-1)\hat{Q}+\beta\hat{q}) + \frac{\beta}{2} \frac{\hat{q}+\hat{m}^2}{1+\hat{r}-(\beta-1)\hat{Q}+\beta\hat{q}} \right. \\ & \left. + 2\alpha \int D\eta H \left( -\sqrt{\frac{m^2}{q-m^2}\eta} \right) \ln \left[ 1+e^{\phi} \int D\zeta H \left( -\frac{1}{\sqrt{r-Q}}(\sqrt{Q-q\zeta}+\sqrt{q\eta}) \right)^{\beta} \right] \right\}, \end{aligned} \quad (8) $$
<figure><img src="image_2.png" /><figcaption>FIG. 1. (Left) Complexity-volume curves $\Sigma(n, v)$ for various budgets $n$, at pool size $\alpha = 3$ extracted from the large deviation computations. These curves reach their maxima at a point with coordinates corresponding to the Gardner volume of randomly chosen $nN$ samples, and log-number of choices of $nN$ elements among $\alpha N$ ones. (Right) The magnetization order parameter $m$ (in other words the teacher-student overlap) as a function of the Gardner volume $v$ for a pool of cardinality $\alpha = 3$, as extracted from the large deviation computations. As is physically intuitive, smaller Gardner volumes imply larger values of the magnetization.</figcaption></figure>

where we introduced the definitions $\int \mathcal{D}x = \int \frac{dx}{\sqrt{2\pi}} e^{-x^2/2}$ and $H(x) = \int_x^\infty \mathcal{D}x$. The extremum operation entailed in the free entropy computation is performed over a set of overlap order parameters, amenable of the following geometric interpretation

* $q = \frac{1}{N} \sum_i \langle \langle x_i \rangle_{x|S} \rangle_S^2$, typical overlap between students with different labeled subsets.

* $Q = \frac{1}{N} \sum_i \langle \langle x_i \rangle_{x|S}^2 \rangle_S$, typical overlap between students with the same labeled subset.

* $r = \frac{1}{N} \sum_i \langle \langle x_i^2 \rangle_{x|S} \rangle_S$, typical norm of a student.

* $m = \frac{1}{N} \sum_i \langle \langle x_i x_i^0 \rangle_{x|S} \rangle_S$, typical magnetization of a student.

Once the free entropy is evaluated, the complexity can be obtained via a numerical implementation of the extremization prescribed by the inverse Legendre transform (6).

We remark at this point that the presented replica calculation was obtained in the so-called replica symmetric ansatz. In general, it is possible for the replica symmetric result not to be exact, requiring replica symmetry breaking (RSB) in order to evaluate the correct free entropy $\Phi(\beta, \phi)$ [14]. In this model, while RSB is surely not needed close to the maximum of the complexity curves (as implied by results in [20]), it is plausibly arising for highly frustrated cases, either very large or very negative $\beta$, corresponding to the values of complexity close to zero. At the same time, the presence of RSB usually entails corrections that are very small in magnitude. We leave the (technically more challenging) investigation of the RSB solution for the large deviations for future work.

## B. Large deviation results

In Fig. 1, we show the results of the large deviation analysis at $\alpha = 3$. Note that the qualitative picture is unaltered when $\alpha$ is varied (e.g., equivalent results for $\alpha = 10$ are shown in appendix C). The different curves, obtained at fixed values of the budget $n$, show the complexity (i.e., the exponential rate of the number) of possible subset choices, $\Sigma$, that realize the corresponding Gardner volumes $v$. As expected, the maximum of each curve is observed at $\beta = 0$, and yields the typical Gardner volume of a teacher-student perceptron that has learned to correctly classify $nN$ i.i.d. Gaussian input patterns. The associated complexity is simply given by the binomial distribution.

The cases where the extremum in equation (6) is realized for positive values of $\beta$ describe choices of the labeled subsets that induce atypically large Gardner volumes: these correspond to active learning scenarios where the student
<figure><img src="image_2.png" /><figcaption>FIG. 1. (Left) Complexity-volume curves $\Sigma(n, v)$ for various budgets $n$, at pool size $\alpha = 3$ extracted from the large deviation computations. These curves reach their maxima at a point with coordinates corresponding to the Gardner volume of randomly chosen $nN$ samples, and log-number of choices of $nN$ elements among $\alpha N$ ones. (Right) The magnetization order parameter $m$ (in other words the teacher-student overlap) as a function of the Gardner volume $v$ for a pool of cardinality $\alpha = 3$, as extracted from the large deviation computations. As is physically intuitive, smaller Gardner volumes imply larger values of the magnetization.</figcaption></figure>

where we introduced the definitions $\int \mathcal{D}x = \int \frac{dx}{\sqrt{2\pi}} e^{-x^2/2}$ and $H(x) = \int_{x}^{\infty} \mathcal{D}x$. The extremum operation entailed in the free entropy computation is performed over a set of overlap order parameters, amenable of the following geometric interpretation

* $q = \frac{1}{N} \sum_i \langle \langle x_i \rangle_{x|S} \rangle_S^2$, typical overlap between students with different labeled subsets.

* $Q = \frac{1}{N} \sum_i \langle \langle x_i \rangle_{x|S}^2 \rangle_S$, typical overlap between students with the same labeled subset.

* $r = \frac{1}{N} \sum_i \langle \langle x_i^2 \rangle_{x|S} \rangle_S$, typical norm of a student.

* $m = \frac{1}{N} \sum_i \langle \langle x_i x_i^0 \rangle_{x|S} \rangle_S$, typical magnetization of a student.

Once the free entropy is evaluated, the complexity can be obtained via a numerical implementation of the extremization prescribed by the inverse Legendre transform (6).

We remark at this point that the presented replica calculation was obtained in the so-called replica symmetric ansatz. In general, it is possible for the replica symmetric result not to be exact, requiring replica symmetry breaking (RSB) in order to evaluate the correct free entropy $\Phi(\beta, \phi)$ [14]. In this model, while RSB is surely not needed close to the maximum of the complexity curves (as implied by results in [20]), it is plausibly arising for highly frustrated cases, either very large or very negative $\beta$, corresponding to the values of complexity close to zero. At the same time, the presence of RSB usually entails corrections that are very small in magnitude. We leave the (technically more challenging) investigation of the RSB solution for the large deviations for future work.

## B. Large deviation results

In Fig. 1, we show the results of the large deviation analysis at $\alpha = 3$. Note that the qualitative picture is unaltered when $\alpha$ is varied (e.g., equivalent results for $\alpha = 10$ are shown in appendix C). The different curves, obtained at fixed values of the budget $n$, show the complexity (i.e., the exponential rate of the number) of possible subset choices, $\Sigma$, that realize the corresponding Gardner volumes $v$. As expected, the maximum of each curve is observed at $\beta = 0$, and yields the typical Gardner volume of a teacher-student perceptron that has learned to correctly classify $nN$ i.i.d. Gaussian input patterns. The associated complexity is simply given by the binomial distribution.

The cases where the extremum in equation (6) is realized for positive values of $\beta$ describe choices of the labeled subsets that induce atypically large Gardner volumes: these correspond to active learning scenarios where the student
<figure><img src="image_3.png" /><figcaption>FIG. 2. Typical Gardner volume (purple, decreasing linearly at large $\alpha$) and information theoretically smallest achievable one (orange, yellow and blue) extracted from the large deviation computation for $\alpha \in \{3, 10, 100\}$. The horizontal lines depict the value of the Gardner volume corresponding to the whole pool, we see the fast saturation of the lowest volumes at these lines. The information-theoretic volume-halving limit $2^{-n}$ for label-agnostic active learning procedures is plotted in a dotted line. We notice that the qualitative picture is essentially unchanged when $\alpha$ is varied.</figcaption></figure>

query is worse than random sampling. The number of possible realizations of these scenarios decreases exponentially as one approaches the right-hand extremum of where the complexity curve is positive, describing the largest possible volume at that given budget $n$. An important remark is that as soon as $\beta > 0$, the statistics of the input patterns in the labeled set is no longer i.i.d., but has increasing correlations for larger $\beta$.

On the other side, negative $\beta$ induces atypically small Gardner volumes and labeled subsets with high information content. Again, as one spans smaller and smaller volumes the associated complexity drops, making the problem of finding these desirable subsets harder and harder. The left positive-complexity extremum of the curves in the left plot of Fig. 1 corresponds to the smallest reachable Gardner volumes. We observe in the figure that for larger values of budgets the complexity curves saturate fast very close to the smallest possible Gardner volume corresponding to the Gardner volume for entire pool of samples $v(\alpha)$.

In the right plot of Fig. 1, we also show the prediction for the typical value of the magnetization, i.e. the overlap between teacher and students, as the Gardner volume is varied. As mentioned in section III, small Gardner volumes induce high magnetizations and thus low generalization errors.

In Fig. 2 the typical (purple) and corresponding minimum (orange, yellow, cyan) Gardner volumes are depicted as a function of the budget $n$ for various pool sizes $\alpha = 3, 10, 100$. Note that the qualitative picture is unaltered when $\alpha$ is varied. We further observe that the minimum volume becomes very close to the Gardner volume of the entire pool of samples $v(\alpha)$ already for very small budgets $n$.

# V. ALGORITHMIC IMPLICATIONS

## A. Generic considerations

The setting investigated in this paper provides a unique chance to benchmark the algorithmic performance of any given pool-based active learning algorithm against the optimal achievable performance, and to measure how closely are the large deviations results approached. Before going to such algorithmic performance we should make a distinction between two active learning strategies

* Label-agnostic algorithms, where the student is not able to extract any knowledge on the labels. In this case, for binary labels there is a simple lower bound on the Gardner volume reachable with $nN$ samples $v \ge 2^{-n}$ which is obtained by the argument that every new sample can at best divide the current volume by a factor two [4]. This strategy is explored in the famous query by committee active learning strategy, and the classical work [4]
<figure><img src="image_3.png" /><figcaption>FIG. 2. Typical Gardner volume (purple, decreasing linearly at large $\alpha$) and information theoretically smallest achievable one (orange, yellow and blue) extracted from the large deviation computation for $\alpha \in \{3, 10, 100\}$. The horizontal lines depict the value of the Gardner volume corresponding to the whole pool, we see the fast saturation of the lowest volumes at these lines. The information-theoretic volume-halving limit $2^{-n}$ for label-agnostic active learning procedures is plotted in a dotted line. We notice that the qualitative picture is essentially unchanged when $\alpha$ is varied.</figcaption></figure>

query is worse than random sampling. The number of possible realizations of these scenarios decreases exponentially as one approaches the right-hand extremum of where the complexity curve is positive, describing the largest possible volume at that given budget $n$. An important remark is that as soon as $\beta > 0$, the statistics of the input patterns in the labeled set is no longer i.i.d., but has increasing correlations for larger $\beta$.

On the other side, negative $\beta$ induces atypically small Gardner volumes and labeled subsets with high information content. Again, as one spans smaller and smaller volumes the associated complexity drops, making the problem of finding these desirable subsets harder and harder. The left positive-complexity extremum of the curves in the left plot of Fig. 1 corresponds to the smallest reachable Gardner volumes. We observe in the figure that for larger values of budgets the complexity curves saturate fast very close to the smallest possible Gardner volume corresponding to the Gardner volume for entire pool of samples $v(\alpha)$.

In the right plot of Fig. 1, we also show the prediction for the typical value of the magnetization, i.e. the overlap between teacher and students, as the Gardner volume is varied. As mentioned in section III, small Gardner volumes induce high magnetizations and thus low generalization errors.

In Fig. 2 the typical (purple) and corresponding minimum (orange, yellow, cyan) Gardner volumes are depicted as a function of the budget $n$ for various pool sizes $\alpha = 3, 10, 100$. Note that the qualitative picture is unaltered when $\alpha$ is varied. We further observe that the minimum volume becomes very close to the Gardner volume of the entire pool of samples $v(\alpha)$ already for very small budgets $n$.

# V. ALGORITHMIC IMPLICATIONS

## A. Generic considerations

The setting investigated in this paper provides a unique chance to benchmark the algorithmic performance of any given pool-based active learning algorithm against the optimal achievable performance, and to measure how closely are the large deviations results approached. Before going to such algorithmic performance we should make a distinction between two active learning strategies

* Label-agnostic algorithms, where the student is not able to extract any knowledge on the labels. In this case, for binary labels there is a simple lower bound on the Gardner volume reachable with $nN$ samples $v \ge 2^{-n}$ which is obtained by the argument that every new sample can at best divide the current volume by a factor two [4]. This strategy is explored in the famous query by committee active learning strategy, and the classical work [4]
argues that the volume halving can be actually achieved when unlimited set of samples is available. Plotting this volume-halving bound in Fig. 2 we see that even though there exist subsets leading to smaller Gardner volumes, they cannot be found in a label-agnostic way

* Label-informed algorithms, where external knowledge of the labels is available and can be exploited for extracting information about which sample to choose. While in our toy setting, the additional information can only consist of disclosing the true labels, which would defy the very point of active learning, in applications with structured data the structure in the input space could be exploited (e.g., through clustering, transfer learning, etc) for making unsupervised guesses of the labels. A concrete example where external insight is available is drug discovery [7], where additional information can be inferred from the presence of chemical functional groups (or absence thereof) on the molecules in the data pool. In the present work, we study whether it is possible, with full access to the labels, to devise an efficient method for finding a subset of samples that achieves close to the minimal Gardner volume (note that this is still an algorithmically non-trivial problem).

In this section we will investigate both the label-agnostic and label-informed strategies. We will benchmark several well known active learning algorithms on the model studied in the present paper as well as design and test a new message passing based active learning algorithm. Before doing that let us describe the general strategy.

Many of the commonly used active learning criteria rely on some form of label-uncertainty measure. Uncertainty sampling [1], [25] is an active learning scheme based on the idea of iteratively selecting and labelling data-points where the prediction of the available trained model is the least confident. In general, the computational complexity associated to this type of scheme is of order $O(N^3)$, requiring an extensive number of runs of a training algorithm (which can scale as $O(N^2)$ at best). Since even training a single model per pattern addition can become expensive in the large $N$ setting, in all our numerical tests we opted for adding to the labeled set batches of $k = 20$ samples instead of a single sample per iteration. We remark that, despite the $k$-fold speed-up, the observed performance deterioration is negligible. The structure of this type of algorithm is sketched in Algorithm 1.

**Algorithm 1 Uncertainty sampling**

Select heuristic strategy from Table I
Define batch size $k$
Initialize $S \subset S = \{F_{\mu}\}_{1\le\mu\le\alpha N}$ ($|S| > 0$)

while $|S| < nN$ do
  Obtain required estimates given $S$
  Obtain model predictions at data-points in $S^c$
  Sort predictions according to sorting criterion
  Add first $k$ elements in the sorting permutation to $S$

end while

## B. Approximate message passing for active learning (AL-AMP)

In general, estimating the Gardner volume on a given training set or the label-uncertainty of a new sample is a computationally hard problem. However, in perceptrons (or more general GLMs) with i.i.d. Gaussian input data $F$, at large system size $N$ one can rely on the estimate provided by a well known algorithm for approximate inference, Approximate Message Passing (AMP) (historically also referred to as the Thouless-Anderson-Palmer (TAP) equations, see [26]). The AMP algorithm [27, 28], [15] yields (at convergence) an estimator of the posterior means, $\hat{x}$, and variances, $\hat{\Delta}$, thus accounting for uncertainty in the inference process including the label of a new sample. The Gardner volume $v$ (corresponding to the so-called Bethe free entropy) can then be expressed as a simple function of the AMP fixed-point messages (see [29] for an example). We provide a pseudo-code of AMP in the case of the perceptron in Algorithm 2. An important remark is that when the training set is not sampled randomly from the pool, as in the active learning context, correlations can arise and AMP is no longer rigorously guaranteed to converge nor to provide a consistent estimate of the Gardner volume. In the present work, we can only argue that its employment seems to be justified a posteriori by observing the agreement between theoretical predictions and numerical experiments for instance for the generalization error.
argues that the volume halving can be actually achieved when unlimited set of samples is available. Plotting this volume-halving bound in Fig. 2 we see that even though there exist subsets leading to smaller Gardner volumes, they cannot be found in a label-agnostic way

* Label-informed algorithms, where external knowledge of the labels is available and can be exploited for extracting information about which sample to choose. While in our toy setting, the additional information can only consist of disclosing the true labels, which would defy the very point of active learning, in applications with structured data the structure in the input space could be exploited (e.g., through clustering, transfer learning, etc) for making unsupervised guesses of the labels. A concrete example where external insight is available is drug discovery [7], where additional information can be inferred from the presence of chemical functional groups (or absence thereof) on the molecules in the data pool. In the present work, we study whether it is possible, with full access to the labels, to devise an efficient method for finding a subset of samples that achieves close to the minimal Gardner volume (note that this is still an algorithmically non-trivial problem).

In this section we will investigate both the label-agnostic and label-informed strategies. We will benchmark several well known active learning algorithms on the model studied in the present paper as well as design and test a new message passing based active learning algorithm. Before doing that let us describe the general strategy.

Many of the commonly used active learning criteria rely on some form of label-uncertainty measure. Uncertainty sampling [1], [25] is an active learning scheme based on the idea of iteratively selecting and labelling data-points where the prediction of the available trained model is the least confident. In general, the computational complexity associated to this type of scheme is of order $O(N^3)$, requiring an extensive number of runs of a training algorithm (which can scale as $O(N^2)$ at best). Since even training a single model per pattern addition can become expensive in the large $N$ setting, in all our numerical tests we opted for adding to the labeled set batches of $k = 20$ samples instead of a single sample per iteration. We remark that, despite the $k$-fold speed-up, the observed performance deterioration is negligible. The structure of this type of algorithm is sketched in Algorithm 1.

**Algorithm 1 Uncertainty sampling**

Select heuristic strategy from Table I
Define batch size $k$
Initialize $S \subset S = \{F_{\mu}\}_{1\le\mu\le\alpha N}$ ($|S| > 0$)

while $|S| < nN$ do
  Obtain required estimates given $S$
  Obtain model predictions at data-points in $S^c$
  Sort predictions according to sorting criterion
  Add first $k$ elements in the sorting permutation to $S$

end while

## B. Approximate message passing for active learning (AL-AMP)

In general, estimating the Gardner volume on a given training set or the label-uncertainty of a new sample is a computationally hard problem. However, in perceptrons (or more general GLMs) with i.i.d. Gaussian input data $F$, at large system size $N$ one can rely on the estimate provided by a well known algorithm for approximate inference, Approximate Message Passing (AMP) (historically also referred to as the Thouless-Anderson-Palmer (TAP) equations, see [26]). The AMP algorithm [27, 28], [15] yields (at convergence) an estimator of the posterior means, $\hat{x}$, and variances, $\hat{\Delta}$, thus accounting for uncertainty in the inference process including the label of a new sample. The Gardner volume $v$ (corresponding to the so-called Bethe free entropy) can then be expressed as a simple function of the AMP fixed-point messages (see [29] for an example). We provide a pseudo-code of AMP in the case of the perceptron in Algorithm 2. An important remark is that when the training set is not sampled randomly from the pool, as in the active learning context, correlations can arise and AMP is no longer rigorously guaranteed to converge nor to provide a consistent estimate of the Gardner volume. In the present work, we can only argue that its employment seems to be justified a posteriori by observing the agreement between theoretical predictions and numerical experiments for instance for the generalization error.
<table><caption>TABLE I. Table summarizing the specifics of the uncertainty sampling strategies considered in this paper.</caption><thead><tr><th colspan="3">Uncertainty sampling strategies</th></tr><tr><th>Heuristic</th><th>Required estimates</th><th>Sorting criterion</th></tr></thead><tbody><tr><td>Agnostic AL-AMP</td><td>x&#x0302;<sub>AMP</sub>, Δ&#x0302;<sub>AMP</sub></td><td>arg min<sub>μ</sub> | erf ( (F'<sup>μ</sup> x&#x0302;<sub>AMP</sub>) / √2(F'<sup>μ</sup>)<sup>2</sup> Δ&#x0302;<sub>AMP</sub> ) |</td></tr><tr><td>Informed AL-AMP</td><td>x&#x0302;<sub>AMP</sub>, Δ&#x0302;<sub>AMP</sub></td><td>arg max<sub>μ</sub> | y<sup>μ</sup> - erf ( (F'<sup>μ</sup> x&#x0302;<sub>AMP</sub>) / √2(F'<sup>μ</sup>)<sup>2</sup> Δ&#x0302;<sub>AMP</sub> ) |</td></tr><tr><td>Query by committee</td><td>{x&#x0302;<sub>SGD</sub>}<sup>K</sup><sub>k=1</sub></td><td>arg min<sub>μ</sub> | Σ<sup>K</sup><sub>k=1</sub> sign (F'<sup>μ</sup> x&#x0302;<sub>SGD</sub>) |</td></tr><tr><td>Logistic regression</td><td>x<sub>log</sub></td><td>arg min<sub>μ</sub> | F'<sup>μ</sup> x&#x0302;<sub>log</sub> |</td></tr><tr><td>Perceptron learning</td><td>x<sub>perc</sub></td><td>arg min<sub>μ</sub> | F'<sup>μ</sup> x&#x0302;<sub>perc</sub> |</td></tr></tbody></table>

**Algorithm 2** single-instance AMP for the perceptron

Initialize $\hat{x} \leftarrow 0$
Initialize $\hat{\Delta} \leftarrow 1$
Initialize $g_{\text{out}} \leftarrow 0$
while Convergence criterion not satisfied do
    $\Gamma_{\mu}^{t} \leftarrow \sum_{i} (F_{i}^{\mu})^{2} \Delta_{i}^{t-1}$
    $\omega_{\mu}^{t} \leftarrow \sum_{i} F_{i}^{\mu} \hat{x}_{i}^{t-1} - \Gamma_{\mu}^{t} g_{\text{out}}^{t-1}$
    $g_{\text{out},\mu}^{t} \leftarrow \frac{y^{\mu}}{\sqrt{2\pi\Gamma_{\mu}^{t}}} \frac{e^{-\frac{(\omega_{\mu}^{t})^{2}}{2\Gamma_{\mu}^{t}}}}{H\left(-\frac{y^{\mu}\omega_{\mu}^{t}}{\sqrt{\Gamma_{\mu}^{t}}}\right)}$
    $(\Sigma_{i}^{t})^{-1} \leftarrow -\sum_{\mu} (F_{i}^{\mu})^{2} \left(-\frac{\omega_{\mu}^{t}}{\sqrt{2\pi}} g_{\text{out}}^{t} - (g_{\text{out}}^{t})^{2}\right)$
    $R_{i}^{t} \leftarrow \hat{x}_{i}^{t-1} + \Sigma_{i}^{t} \sum_{\mu} F_{i}^{\mu} g_{\text{out}}^{t}$
    $\hat{x}_{i}^{t} \leftarrow \frac{R_{i}^{t}}{1+\Sigma_{i}^{t}}$
    $\hat{\Delta}_{i}^{t} \leftarrow \frac{\Sigma_{i}^{t}}{1+\Sigma_{i}^{t}}$
end while

We use the AMP algorithm to introduce a new uncertainty sampling procedure relying on the information contained in the AMP messages, denoted as AL-AMP in the following. At each iteration, the single-instance AMP equations are run on the current training subset to yield posterior mean estimate $\hat{x}$ and variance $\hat{\Delta}$. These quantities can then be used to evaluate, for all the unlabeled samples, the output magnetization (i.e. the Bayesian prediction) defined as

$$m_{\text{out}}^{\mu} = \text{erf}(\omega^{\mu} / \sqrt{2\Gamma^{\mu}}) \quad \forall \mu | \sigma_{\mu} = 0, \qquad (9)$$

where we introduced the output overlaps $\omega = F' \cdot \hat{x}$ and variances $\Gamma = (F' \odot F') \cdot \hat{\Delta}$, where $\odot$ is the component-wise product. The output magnetizations correspond to the weighted output average over all the estimators contained in the current version space, and their magnitude represents the overall confidence in the classification of the still unlabeled samples. This means that AMP provides an extremely efficient way of obtaining the information on uncertainty. The specifics of the algorithm can be found in Tab. I.

We also explore numerically the label-informed active learning regime introduced in the previous section. We consider its limiting case by introducing the informed AL-AMP strategy, which can fully access the true labels $Y$ in order to query the samples $F^{\mu}$ whose output magnetisation $m_{\text{out}}^{\mu}$ (9) is maximally distant from the correct classification $y^{\mu}$. This selection process can iteratively reduce the Gardner volume of factors larger than 2. Again, the relevant specifics of informed AL-AMP algorithm are detailed in Tab. I.

## C. Other tested measures of uncertainty

One of the widely used uncertainty sampling procedure is the so-called Query by Committee (QBC) strategy [4], [18]. In QBC, at each time step, a committee of $K$ students is to be sampled from the version space (e.g., via the
<table><caption>TABLE I. Table summarizing the specifics of the uncertainty sampling strategies considered in this paper.</caption><thead><tr><th colspan="3">Uncertainty sampling strategies</th></tr><tr><th>Heuristic</th><th>Required estimates</th><th>Sorting criterion</th></tr></thead><tbody><tr><td>Agnostic AL-AMP</td><td>x&#x0302;<sub>AMP</sub>, Δ&#x0302;<sub>AMP</sub></td><td>arg min<sub>μ</sub> | erf ( (F'<sup>μ</sup> x&#x0302;<sub>AMP</sub>) / √2(F'<sup>μ</sup>)<sup>2</sup> Δ&#x0302;<sub>AMP</sub> ) |</td></tr><tr><td>Informed AL-AMP</td><td>x&#x0302;<sub>AMP</sub>, Δ&#x0302;<sub>AMP</sub></td><td>arg max<sub>μ</sub> | y<sup>μ</sup> - erf ( (F'<sup>μ</sup> x&#x0302;<sub>AMP</sub>) / √2(F'<sup>μ</sup>)<sup>2</sup> Δ&#x0302;<sub>AMP</sub> ) |</td></tr><tr><td>Query by committee</td><td>{x&#x0302;<sub>SGD</sub>}<sup>K</sup><sub>k=1</sub></td><td>arg min<sub>μ</sub> | Σ<sup>K</sup><sub>k=1</sub> sign (F'<sup>μ</sup> x&#x0302;<sub>SGD</sub>) |</td></tr><tr><td>Logistic regression</td><td>x<sub>log</sub></td><td>arg min<sub>μ</sub> | F'<sup>μ</sup> x&#x0302;<sub>log</sub> |</td></tr><tr><td>Perceptron learning</td><td>x<sub>perc</sub></td><td>arg min<sub>μ</sub> | F'<sup>μ</sup> x&#x0302;<sub>perc</sub> |</td></tr></tbody></table>

**Algorithm 2** single-instance AMP for the perceptron

Initialize $\hat{x} \leftarrow 0$

Initialize $\hat{\Delta} \leftarrow 1$

Initialize $g_{\text{out}} \leftarrow 0$

while Convergence criterion not satisfied do

$$ \Gamma_{\mu}^{t} \leftarrow \sum_{i} (F_{i}^{\mu})^{2} \Delta_{i}^{t-1} $$

$$ \omega_{\mu}^{t} \leftarrow \sum_{i} F_{i}^{\mu} \hat{x}_{i}^{t-1} - \Gamma_{\mu}^{t} g_{\text{out}}^{t-1} $$

$$ g_{\text{out},\mu}^{t} \leftarrow \frac{y^{\mu}}{\sqrt{2\pi\Gamma_{\mu}^{t}}} \frac{e^{-\frac{(\omega_{\mu}^{t})^{2}}{2\Gamma_{\mu}^{t}}}}{H\left(-\frac{y^{\mu}\omega_{\mu}^{t}}{\sqrt{\Gamma_{\mu}^{t}}}\right)} $$

$$ (\Sigma_{i}^{t})^{-1} \leftarrow -\sum_{\mu} (F_{i}^{\mu})^{2} \left(-\frac{\omega_{\mu}^{t}}{\sqrt{2\Gamma_{\mu}^{t}}} g_{\text{out}}^{t} - (g_{\text{out}}^{t})^{2}\right) $$

$$ R_{i}^{t} \leftarrow \hat{x}_{i}^{t-1} + \Sigma_{i}^{t} \sum_{\mu} F_{i}^{\mu} g_{\text{out}}^{t} $$

$$ \hat{x}_{i}^{t} \leftarrow \frac{R_{i}^{t}}{1+\Sigma_{i}^{t}} $$

$$ \hat{\Delta}_{i}^{t} \leftarrow \frac{\Sigma_{i}^{t}}{1+\Sigma_{i}^{t}} $$

end while

We use the AMP algorithm to introduce a new uncertainty sampling procedure relying on the information contained in the AMP messages, denoted as AL-AMP in the following. At each iteration, the single-instance AMP equations are run on the current training subset to yield posterior mean estimate $\hat{x}$ and variance $\hat{\Delta}$. These quantities can then be used to evaluate, for all the unlabeled samples, the output magnetization (i.e. the Bayesian prediction) defined as

$$ m_{\text{out}}^{\mu} = \text{erf}(\omega^{\mu} / \sqrt{2\Gamma^{\mu}}) \quad \forall \mu | \sigma_{\mu} = 0, \qquad (9) $$

where we introduced the output overlaps $\omega = F' \cdot \hat{x}$ and variances $\Gamma = (F' \odot F') \cdot \hat{\Delta}$, where $\odot$ is the component-wise product. The output magnetizations correspond to the weighted output average over all the estimators contained in the current version space, and their magnitude represents the overall confidence in the classification of the still unlabeled samples. This means that AMP provides an extremely efficient way of obtaining the information on uncertainty. The specifics of the algorithm can be found in Tab. I.

We also explore numerically the label-informed active learning regime introduced in the previous section. We consider its limiting case by introducing the informed AL-AMP strategy, which can fully access the true labels $Y$ in order to query the samples $F^{\mu}$ whose output magnetisation $m_{\text{out}}^{\mu}$ (9) is maximally distant from the correct classification $y^{\mu}$. This selection process can iteratively reduce the Gardner volume of factors larger than 2. Again, the relevant specifics of informed AL-AMP algorithm are detailed in Tab. I.

## C. Other tested measures of uncertainty

One of the widely used uncertainty sampling procedure is the so-called Query by Committee (QBC) strategy [4], [18]. In QBC, at each time step, a committee of $K$ students is to be sampled from the version space (e.g., via the
Gibbs algorithm). The committee is then employed to choose the labels to be queried, by identifying the samples where maximum disagreement in the committee members outputs is observed. The QBC algorithm was introduced as a proxy for doing bisection, i.e. cutting version space into two equal-volume halves. As already mentioned, this constitutes the optimal information gain in an label-agnostic setting [30]. Note that, however, the QBC procedure can achieve volume-halving only in the infinite-size committee limit, $K \uparrow \infty$, with uniform version space sampling and with availability of infinitely many samples. Obviously, running a large number $K$ of ergodic Gibbs sampling procedures quickly becomes computationally unfeasible. Moreover in the pool-based active learning the pool of samples is limited. In order to allow comparison with other strategies at finite sizes, we approximated the uniform sampling with a set of greedy optimization procedures (e.g., stochastic gradient descent) from random initialization conditions, checking numerically that this yields a committee of students reasonably spread out in version space. It is possible to ensure a greater coverage of the version space by performing a short Monte-Carlo random walk for each committee member. The effect has been found to be small for computationally reasonable lengths of walk.

We also implemented an alternative uncertainty sampling strategy, relying on a single training procedure (e.g., training with the perceptron algorithm or logistic regression) per iteration: in this case, the uncertainty information is extracted from the magnitude of the pre-activations measured at the unlabeled samples after each training cycle. This strategy implements the intuitive geometric idea of looking for the samples that are most orthogonal to the available updated estimator, which are more likely to halve the version space independently of the value of the true label.

## D. Algorithmic results

<figure><img src="image_4.png" /><figcaption>FIG. 3. (Left) Performance of the label-agnostic (yellow circles) and label-informed (blue circles) AL-AMP, plotted together with the minimum and maximum values of the Gardner volume extracted from the large deviation computation (purple and green) and the volume-halving curve (dotted black). For comparison we also plot the typical Gardner volume (cyan) and the one obtained by random sampling (orange squares). Numerical experiments were run for system size $N = 2 \cdot 10^3$ and pool size $\alpha = 3$. For each algorithmic performance curve the average over 10 samples is presented. Fluctuations were found to be negligible around the average and are not shown. (Right) The same plot with the Gardner volume replaced by the Bayesian test accuracy, derived in Appendix D. For the AL-AMP algorithm the accuracy is evaluated using a test set of size $P_{\text{test}} = 5 \cdot 10^4$. The qualitative picture is very similar to the one for the Gardner volume curves (left), once more confirming that Gardner volumes and generalization errors both constitute good measures for informativeness.</figcaption></figure>

In Fig. 3, we compare the minimum Gardner volume obtained from the large deviation calculation with the algorithmic performance obtained on synthetic data at finite size, $N = 2 \cdot 10^3$, by the AL-AMP algorithms detailed in Algorithm 1 and Tab. I. The data-pool size is fixed to $\alpha = 3$. The large deviation analysis yields values for the minimum and maximum achievable Gardner volumes at any budget $n$. We compare the algorithmic results also with the prediction for the typical case and with the volume-halving curve $2^{-n}$. Since in the considered pool-based setting the volume-halving performance cannot be achieved for volumes smaller than the Gardner volume corresponding to the entire pool $v(\alpha)$, the relevant volume-halving bound should be more precisely $\max(2^{-n}, v(\alpha))$. Random sampling displays good agreement with the expected typical volumes. Most notably, the label-agnostic AL-AMP algorithm tightly follows the volume-halving bound $\max(2^{-n}, v(\alpha))$, thus reaching close to optimal possible performance. Since
Gibbs algorithm). The committee is then employed to choose the labels to be queried, by identifying the samples where maximum disagreement in the committee members outputs is observed. The QBC algorithm was introduced as a proxy for doing bisection, i.e. cutting version space into two equal-volume halves. As already mentioned, this constitutes the optimal information gain in an label-agnostic setting [30]. Note that, however, the QBC procedure can achieve volume-halving only in the infinite-size committee limit, $K \uparrow \infty$, with uniform version space sampling and with availability of infinitely many samples. Obviously, running a large number $K$ of ergodic Gibbs sampling procedures quickly becomes computationally unfeasible. Moreover in the pool-based active learning the pool of samples is limited. In order to allow comparison with other strategies at finite sizes, we approximated the uniform sampling with a set of greedy optimization procedures (e.g., stochastic gradient descent) from random initialization conditions, checking numerically that this yields a committee of students reasonably spread out in version space. It is possible to ensure a greater coverage of the version space by performing a short Monte-Carlo random walk for each committee member. The effect has been found to be small for computationally reasonable lengths of walk.

We also implemented an alternative uncertainty sampling strategy, relying on a single training procedure (e.g., training with the perceptron algorithm or logistic regression) per iteration: in this case, the uncertainty information is extracted from the magnitude of the pre-activations measured at the unlabeled samples after each training cycle. This strategy implements the intuitive geometric idea of looking for the samples that are most orthogonal to the available updated estimator, which are more likely to halve the version space independently of the value of the true label.

## D. Algorithmic results

<figure><img src="image_4.png" /><figcaption>FIG. 3. (Left) Performance of the label-agnostic (yellow circles) and label-informed (blue circles) AL-AMP, plotted together with the minimum and maximum values of the Gardner volume extracted from the large deviation computation (purple and green) and the volume-halving curve (dotted black). For comparison we also plot the typical Gardner volume (cyan) and the one obtained by random sampling (orange squares). Numerical experiments were run for system size $N = 2 \cdot 10^3$ and pool size $\alpha = 3$. For each algorithmic performance curve the average over 10 samples is presented. Fluctuations were found to be negligible around the average and are not shown. (Right) The same plot with the Gardner volume replaced by the Bayesian test accuracy, derived in Appendix D. For the AL-AMP algorithm the accuracy is evaluated using a test set of size $P_{test} = 5 \cdot 10^4$. The qualitative picture is very similar to the one for the Gardner volume curves (left), once more confirming that Gardner volumes and generalization errors both constitute good measures for informativeness.</figcaption></figure>

In Fig. 3, we compare the minimum Gardner volume obtained from the large deviation calculation with the algorithmic performance obtained on synthetic data at finite size, $N = 2 \cdot 10^3$, by the AL-AMP algorithms detailed in Algorithm 1 and Tab. I. The data-pool size is fixed to $\alpha = 3$. The large deviation analysis yields values for the minimum and maximum achievable Gardner volumes at any budget $n$. We compare the algorithmic results also with the prediction for the typical case and with the volume-halving curve $2^{-n}$. Since in the considered pool-based setting the volume-halving performance cannot be achieved for volumes smaller than the Gardner volume corresponding to the entire pool $v(\alpha)$, the relevant volume-halving bound should be more precisely $\max(2^{-n}, v(\alpha))$. Random sampling displays good agreement with the expected typical volumes. Most notably, the label-agnostic AL-AMP algorithm tightly follows the volume-halving bound $\max(2^{-n}, v(\alpha))$, thus reaching close to optimal possible performance. Since
<figure><img src="image_5.png" /><figcaption>FIG. 4. (Left) Performance of the label-agnostic algorithms presented in Tab. I is plotted against the budget $n$ and compared to the volume-halving lower bound. Experiments were performed at system size $N = 2 \cdot 10^3$, and pool size $\alpha = 10$. For each algorithm the average over 10 samples is presented. Note that error bars are smaller than marker size. (Left) (Bayesian) test accuracy of the same heuristics for various budgets $n$. The test set size was chosen to be $P_{test} = 5 \cdot 10^4$. In blue the Bayesian test accuracy for a typical subset, see appendix D. Again, the qualitative picture is unchanged going from the Gardner volume to the test accuracy.</figcaption></figure>

for large $\alpha$ the behaviour of $v(\alpha) = \text{const.}/\alpha$ [17] we conclude that the AL-AMP algorithm will reach close to minimum possible Gardner volumes for a budget $n \sim \mathcal{O}[\log(\alpha)]$. We thus obtain an exponential reduction in the number of samples even in the pool-based active learning similarly to the original Query by Committee work [4].

The label-informed AL-AMP also approaches the theoretically minimal volume but not as closely. We remark that an important limit of the AL-AMP algorithm comes from the fact that AMP is not guaranteed to provide good estimators (or converge at all) with correlated data. For example, in the numerical experiments for obtaining the informed AL-AMP curve, we had to resort to mild damping schemes in the message-passing to allow fixed-points being reached. This effect was stronger for the label-informed algorithm than for the label-agnostic one.

In Fig. 4, we provide a numerical comparison of the performance of the agnostic AL-AMP and the other above mentioned label-agnostic active learning algorithms. The finite size experiments were run at $N = 2.10^3$, while here we set $\alpha = 10$. Note that, while the mentioned different active learning strategies where employed for selecting the labeled subset, in all cases supervised learning and the related performance estimates were obtained by running AMP. In the plot, we can see that, while AL-AMP is able to extract very close to the maximum amount of information from each query (one bit per pattern, until the volume $v(\alpha)$ is saturated), other heuristics with the same computational complexity are sub-optimal. In particular, in the simplified query by committee procedure we observe that increasing the size $K$ of the committee does not yield very noticeable change in its performance, most probably because the committee cannot cover a sufficient portion of the version space if the computational cost is to be kept reasonable. On the other hand, using the information of the magnitude pre-activations allows better performance while being also more time-efficient, since only a single perceptron, rather than a committee thereof, has to be trained at each step. The logistic loss allows a rather good performance, close to that of AL-AMP, while the uncertainty sampling with the perceptron algorithm yields a mitigated performance.

We leave a more systematic bench-marking of the many existing strategies for future work, stressing the fact that, while there certainly exist more involved procedures that can yield better performance than the presented heuristics, the absolute performance bounds still apply, agnostic of the implemented active learning strategy.

## VI. CONCLUSIONS

Using the replica method for large deviation calculation of the Gardner volume, we computed for the teacher-student perceptron model the minimum Gardner volume (equivalently, maximum mutual information) achievable by selecting a subset with fixed cardinality from a pre-existing pool of i.i.d. normal samples. We evaluated the large deviation function based on the replica symmetric assumption; checking for replica symmetry breaking and evaluating the eventual corrections to the presented results is left for future work, as well as rigorous establishment of the presented results. Our result for the information-theoretic limit of pool-based active learning in this setting complements the
<figure><img src="image_5.png" /><figcaption>FIG. 4. (Left) Performance of the label-agnostic algorithms presented in Tab. I is plotted against the budget $n$ and compared to the volume-halving lower bound. Experiments were performed at system size $N = 2 \cdot 10^3$, and pool size $\alpha = 10$. For each algorithm the average over 10 samples is presented. Note that error bars are smaller than marker size. (Left) (Bayesian) test accuracy of the same heuristics for various budgets $n$. The test set size was chosen to be $P_{test} = 5 \cdot 10^4$. In blue the Bayesian test accuracy for a typical subset, see appendix D. Again, the qualitative picture is unchanged going from the Gardner volume to the test accuracy.</figcaption></figure>

for large $\alpha$ the behaviour of $v(\alpha) = \text{const.}/\alpha$ [17] we conclude that the AL-AMP algorithm will reach close to minimum possible Gardner volumes for a budget $n \sim \mathcal{O}[\log(\alpha)]$. We thus obtain an exponential reduction in the number of samples even in the pool-based active learning similarly to the original Query by Committee work [4].

The label-informed AL-AMP also approaches the theoretically minimal volume but not as closely. We remark that an important limit of the AL-AMP algorithm comes from the fact that AMP is not guaranteed to provide good estimators (or converge at all) with correlated data. For example, in the numerical experiments for obtaining the informed AL-AMP curve, we had to resort to mild damping schemes in the message-passing to allow fixed-points being reached. This effect was stronger for the label-informed algorithm than for the label-agnostic one.

In Fig. 4, we provide a numerical comparison of the performance of the agnostic AL-AMP and the other above mentioned label-agnostic active learning algorithms. The finite size experiments were run at $N = 2.10^3$, while here we set $\alpha = 10$. Note that, while the mentioned different active learning strategies where employed for selecting the labeled subset, in all cases supervised learning and the related performance estimates were obtained by running AMP. In the plot, we can see that, while AL-AMP is able to extract very close to the maximum amount of information from each query (one bit per pattern, until the volume $v(\alpha)$ is saturated), other heuristics with the same computational complexity are sub-optimal. In particular, in the simplified query by committee procedure we observe that increasing the size $K$ of the committee does not yield very noticeable change in its performance, most probably because the committee cannot cover a sufficient portion of the version space if the computational cost is to be kept reasonable. On the other hand, using the information of the magnitude pre-activations allows better performance while being also more time-efficient, since only a single perceptron, rather than a committee thereof, has to be trained at each step. The logistic loss allows a rather good performance, close to that of AL-AMP, while the uncertainty sampling with the perceptron algorithm yields a mitigated performance.

We leave a more systematic bench-marking of the many existing strategies for future work, stressing the fact that, while there certainly exist more involved procedures that can yield better performance than the presented heuristics, the absolute performance bounds still apply, agnostic of the implemented active learning strategy.

## VI. CONCLUSIONS

Using the replica method for large deviation calculation of the Gardner volume, we computed for the teacher-student perceptron model the minimum Gardner volume (equivalently, maximum mutual information) achievable by selecting a subset with fixed cardinality from a pre-existing pool of i.i.d. normal samples. We evaluated the large deviation function based on the replica symmetric assumption; checking for replica symmetry breaking and evaluating the eventual corrections to the presented results is left for future work, as well as rigorous establishment of the presented results. Our result for the information-theoretic limit of pool-based active learning in this setting complements the
already known volume-halving bound for label-agnostic strategies. We hope our result may serve as a guideline to benchmark future heuristic algorithms on the present model, while our modus operandi regarding the derivation of the large deviations may help for future endeavour in theoretical analysis of active learning in more realistic settings. We presented the performance of some known heuristics, plus we suggested the AL-AMP algorithms to perform the uncertainty based active learning. We show numerically that on the present model the label-agnostic AL-AMP algorithm performs very close to the optimal bound, thus being able to achieve accuracy corresponding to the entire pool of samples with exponentially fewer samples.

ACKNOWLEDGMENTS

We want to thank Guilhem Semerjian for clarifying discussions in early stages on this work. This work is supported
by the ERC under the European Unions Horizon 2020 Research and Innovation Program 714608-SMiLe.

[1] Burr Settles, *Active Learning Literature Survey*, Computer Sciences Technical Report (2009).

[2] Dana Angluin, “Queries and concept learning,” Machine Learning 2, 319–342 (1988).

[3] David A. Cohn, Les E. Atlas, and Richard E. Ladner, “Improving generalization with active learning,” Machine Learning 15, 201–221 (1994).

[4] H. Sebastian Seung, Manfred Opper, and Haim Sompolinsky, “Query by committee,” COLT 5, 287–294 (1992).

[5] Les E. Atlas, David A. Cohn, and Richard E. Ladner, “Training connectionist networks with queries and selective sampling,” NIPS 2, 566–573 (1990).

[6] Linfeng Zhang, De-Ye Lin, Han Wang, Roberto Car, and E Weinan, “Active learning of uniformly accurate interatomic potentials for materials simulation,” Phys. Rev. Materials 3, 023804 (2019).

[7] Manfred K. Warmuth, Gunnar Rätsch, Michael Mathieson, Jun Liao, and Christian Lemmen, “Active learning in drug discovery,” NIPS 14, 1449–1456 (2001).

[8] Andrew K. McCallum and Kamal Nigam, “Employing em and pool-based active learning for text classification,” ICML, 350–358 (1998).

[9] Simon Tong and Daphne Koller, “Support vector machine active learning with applications to text classification,” Journal of Machine Learning Reasearch 2, 45–66 (2000).

[10] Steven C.H. Hoi, Rong Jin, Jianke Zhu, and Michael R. Lyu, “Batch mode active learning and its application to medical image classification,” ICML 6, 417–424 (2006).

[11] Elizabeth Gardner and Bernard Derrida, “Optimal storage properties of neural network models,” J. Phys. A: Math. Gen. 21, 271–284 (1988).

[12] Giorgio Parisi, “Towards a mean field theory for spin glasses,” Phys. Lett 73, 203–205 (1979).

[13] Giorgio Parisi, “Order parameter for spin glasses,” Phys. Rev. Lett 50, 1946–1948 (1983).

[14] Marc Mézard, Miguel A. Virasoro, and Giorgio Parisi, *Spin Glass Theory and Beyond* (World scientific Lecture Notes in Physics, 1986).

[15] Lenka Zdeborová and Florent Krzakala, “Statistical physics of inference: thresholds and algorithms,” Adv. Phys. 5, 453–552 (2016).

[16] Elizabeth Gardner and Bernard Derrida, “Three unfinished works on the optimal storage capacity of networks,” Journal of Physics A: Mathematical and General 22, 1983 (1989).

[17] Andreas Engels and Christian P.L. van den Broeck, *Statistical mechanics of learning* (Cambridge University Press, 2001).

[18] Yoav Freund, Eli Shamir, H. Sebastian Seung, and Naftali Tishby, “Information, prediction, and query by committee,” NIPS 5, 483–490 (1992).

[19] Hai-Jun Zhou, “Active online learning in the binary perceptron problem,” Communications in Theoretical Physics 71, 243 (2019).

[20] Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zdeborová, “Optimal errors and phase transitions in high-dimensional generalized linear models,” Proc. Nat. Ac. Sc. 116, 5451–5460 (2019).

[21] Hidetoshi Nishimori, *Statistical physics of spin glasses and information processing* (Oxford Science Publications, 2001).

[22] Tom M. Mitchell, “Generalization as search,” Artificial intelligence 18, 203–226 (1982).

[23] Victor Dotsenko, Silvio Franz, and Marc Mézard, “Partial annealing and overfrustration in disordered systems,” J. Phys. A: Math. Gen. 27, 2351–2365 (1994).

[24] Florent Krzakala, Marc Mézard, François Sausset, Sun Yifan, and Lenka Zdeborová, “Probabilistic reconstruction in compressed sensing: Algorithms, phase diagrams and treshold achieving matrices,” J. Stat. Mech. 2012, P08009 (2012).

[25] David D. Lewis and William A. Gale, “A sequential algorithm for training text classifiers,” SIGIR 17, 3–12 (1994).

[26] David J. Thouless, Philip W. Anderson, and Richard G. Palmer, “Solution of solvable model of spin glass,” Phil. Mag. 35, 593–601 (1977).

[27] David L. Donoho, Arian Maleki, and Andrea Montanari, “Message-passing algorithms for compressed sensing,” Proceedings of the National Academy of Sciences 106, 18914–18919 (2009).
already known volume-halving bound for label-agnostic strategies. We hope our result may serve as a guideline to benchmark future heuristic algorithms on the present model, while our modus operandi regarding the derivation of the large deviations may help for future endeavour in theoretical analysis of active learning in more realistic settings. We presented the performance of some known heuristics, plus we suggested the AL-AMP algorithms to perform the uncertainty based active learning. We show numerically that on the present model the label-agnostic AL-AMP algorithm performs very close to the optimal bound, thus being able to achieve accuracy corresponding to the entire pool of samples with exponentially fewer samples.

ACKNOWLEDGMENTS

We want to thank Guilhem Semerjian for clarifying discussions in early stages on this work. This work is supported
by the ERC under the European Unions Horizon 2020 Research and Innovation Program 714608-SMiLe.

[1] Burr Settles, *Active Learning Literature Survey*, Computer Sciences Technical Report (2009).

[2] Dana Angluin, “Queries and concept learning,” Machine Learning **2**, 319–342 (1988).

[3] David A. Cohn, Les E. Atlas, and Richard E. Ladner, “Improving generalization with active learning,” Machine Learning **15**, 201–221 (1994).

[4] H. Sebastian Seung, Manfred Opper, and Haim Sompolinsky, “Query by committee,” COLT **5**, 287–294 (1992).

[5] Les E. Atlas, David A. Cohn, and Richard E. Ladner, “Training connectionist networks with queries and selective sampling,” NIPS **2**, 566–573 (1990).

[6] Linfeng Zhang, De-Ye Lin, Han Wang, Roberto Car, and E Weinan, “Active learning of uniformly accurate interatomic potentials for materials simulation,” Phys. Rev. Materials **3**, 023804 (2019).

[7] Manfred K. Warmuth, Gunnar Rätsch, Michael Mathieson, Jun Liao, and Christian Lemmen, “Active learning in drug discovery,” NIPS **14**, 1449–1456 (2001).

[8] Andrew K. McCallum and Kamal Nigam, “Employing em and pool-based active learning for text classification,” ICML, 350–358 (1998).

[9] Simon Tong and Daphne Koller, “Support vector machine active learning with applications to text classification,” Journal of Machine Learning Reasearch **2**, 45–66 (2000).

[10] Steven C.H. Hoi, Rong Jin, Jianke Zhu, and Michael R. Lyu, “Batch mode active learning and its application to medical image classification,” ICML **6**, 417–424 (2006).

[11] Elizabeth Gardner and Bernard Derrida, “Optimal storage properties of neural network models,” J. Phys. A: Math. Gen. **21**, 271–284 (1988).

[12] Giorgio Parisi, “Towards a mean field theory for spin glasses,” Phys. Lett **73**, 203–205 (1979).

[13] Giorgio Parisi, “Order parameter for spin glasses,” Phys. Rev. Lett **50**, 1946–1948 (1983).

[14] Marc Mézard, Miguel A. Virasoro, and Giorgio Parisi, *Spin Glass Theory and Beyond* (World scientific Lecture Notes in Physics, 1986).

[15] Lenka Zdeborová and Florent Krzakala, “Statistical physics of inference: thresholds and algorithms,” Adv. Phys. **5**, 453–552 (2016).

[16] Elizabeth Gardner and Bernard Derrida, “Three unfinished works on the optimal storage capacity of networks,” Journal of Physics A: Mathematical and General **22**, 1983 (1989).

[17] Andreas Engels and Christian P.L. van den Broeck, *Statistical mechanics of learning* (Cambridge University Press, 2001).

[18] Yoav Freund, Eli Shamir, H. Sebastian Seung, and Naftali Tishby, “Information, prediction, and query by committee,” NIPS **5**, 483–490 (1992).

[19] Hai-Jun Zhou, “Active online learning in the binary perceptron problem,” Communications in Theoretical Physics **71**, 243 (2019).

[20] Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zdeborová, “Optimal errors and phase transitions in high-dimensional generalized linear models,” Proc. Nat. Ac. Sc. **116**, 5451–5460 (2019).

[21] Hidetoshi Nishimori, *Statistical physics of spin glasses and information processing* (Oxford Science Publications, 2001).

[22] Tom M. Mitchell, “Generalization as search,” Artificial intelligence **18**, 203–226 (1982).

[23] Victor Dotsenko, Silvio Franz, and Marc Mézard, “Partial annealing and overfrustration in disordered systems,” J. Phys. A: Math. Gen. **27**, 2351–2365 (1994).

[24] Florent Krzakala, Marc Mézard, François Sausset, Sun Yifan, and Lenka Zdeborová, “Probabilistic reconstruction in compressed sensing: Algorithms, phase diagrams and treshold achieving matrices,” J. Stat. Mech. **2012**, P08009 (2012).

[25] David D. Lewis and William A. Gale, “A sequential algorithm for training text classifiers,” SIGIR **17**, 3–12 (1994).

[26] David J. Thouless, Philip W. Anderson, and Richard G. Palmer, “Solution of solvable model of spin glass,” Phil. Mag. **35**, 593–601 (1977).

[27] David L. Donoho, Arian Maleki, and Andrea Montanari, “Message-passing algorithms for compressed sensing,” Proceedings of the National Academy of Sciences **106**, 18914–18919 (2009).
[28] Sundeep Rangan, “Generalized approximate message passing for estimation with random linear mixing,” in *2011 IEEE International Symposium on Information Theory Proceedings* (IEEE, 2011) pp. 2168–2172.

[29] Florent Krzakala, André Manoel, Éric W. Tramel, and Lenka Zdeborová, “Variational free energy for compressed sensing,” *ISIT*, 1499–1503 (2014).

[30] Sanjoy Dasgupta, “Analysis of a greedy active learning strategy,” *NIPS* **17**, 337–344 (2005).

[31] Fabrizio Antenucci, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová, “Approximate survey propagation for statistical inference,” *J. Stat. Mech. 2019*, 023401 (2019).

[32] Marc Mézard, Giorgio Parisi, Nicolas Sourlas, Gérard Toulouse, and Miguel A. Virasoro, “Replica symmetry breaking and the nature of the spin glass phase,” *J. Phys. France* **45**, 843–854 (1984).

[33] Carlo Baldassi, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina, “Subdominant dense clusters allow for simple learning and high computational performance in neural networks with discrete synapses.” *Physical review letters* **115 12**, 128101 (2015).
[28] Sundeep Rangan, “Generalized approximate message passing for estimation with random linear mixing,” in *2011 IEEE International Symposium on Information Theory Proceedings* (IEEE, 2011) pp. 2168–2172.

[29] Florent Krzakala, André Manoel, Éric W. Tramel, and Lenka Zdeborová, “Variational free energy for compressed sensing,” *ISIT*, 1499–1503 (2014).

[30] Sanjoy Dasgupta, “Analysis of a greedy active learning strategy,” *NIPS* **17**, 337–344 (2005).

[31] Fabrizio Antenucci, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová, “Approximate survey propagation for statistical inference,” *J. Stat. Mech. 2019*, 023401 (2019).

[32] Marc Mézard, Giorgio Parisi, Nicolas Sourlas, Gérard Toulouse, and Miguel A. Virasoro, “Replica symmetry breaking and the nature of the spin glass phase,” *J. Phys. France* **45**, 843–854 (1984).

[33] Carlo Baldassi, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina, “Subdominant dense clusters allow for simple learning and high computational performance in neural networks with discrete synapses.” *Physical review letters* **115 12**, 128101 (2015).
# Appendix A: Notations and Large-Deviation (LD) measure for GLMs

In this appendix we set the replica calculation in the more general setting of a generalized linear model (GLM) with arbitrary teacher/student prior/posterior. We allow the inference to be mismatched, i.e. we allow the teacher and student measures to be different. The specialization to the particular case of the teacher-student perceptron with no mismatch (Bayes-optimal) will be carried out in appendix C. Our computation borrows from [24] and [20] which study the simple measure. Because we study large deviations, our formalism has some semblance with one-step Replica Breaking (1RSB) equations, a discussion of which can be found for example in [31], [32], [14].

## 1. Definition of the problem

We consider a student GLM ([24]) with $N$-dimensional weights learning from $\alpha N$ samples $\mathbf{F}^{\mu} \in \mathbb{R}^N$ stacked in a matrix $\mathbf{F} \in \mathcal{M}_{\alpha N, N}(\mathbb{R})$ and the corresponding labels $y^{\mu}$ stacked into $\mathbf{Y} \in \mathbb{R}^{\alpha N}$. We assume the student-teacher (or planted) setting ([15]), where the labels are generated by the ground truth (teacher weights) $\mathbf{x}^0$ with the channel measure $\overline{P}_{\text{out}}(y^{\mu}|\mathbf{F}^{\mu} \cdot \mathbf{x}^0)$. The teacher weight itself is drawn with prior $\overline{P}_{\mathbf{X}}(\cdot)$. Given $\mathbf{F}$ and $\mathbf{Y}$, the student perceptron is trained so that its own weight vector $\mathbf{x}$ tries to match the ground truth $\mathbf{x}^0$. The inference is carried out with the student prior $P_{\mathbf{X}}(\cdot)$ and posterior $P_{\text{out}}(\mathbf{Y}|\mathbf{F} \cdot \mathbf{x})$. Note that the cases where $P_{\mathbf{X}}(\cdot) \neq \overline{P}_{\mathbf{X}}(\cdot)$ or $P_{\text{out}}(\cdot) \neq \overline{P}_{\text{out}}(\cdot)$ mean that the student ignores the precise Markov chain wherefrom the labels are generated, as discussed in section II, see also [15]. The likelihood that a vector $\mathbf{x}$ is the ground truth vector is then $P_{\mathbf{X}}(\mathbf{x})P_{\text{out}}(\mathbf{Y}|\mathbf{F} \cdot \mathbf{x})$. A reasonable measure of the average lack of accuracy of the student's guess is then given by the Gardner volume, viz. the partition function associated with the likelihood

$$v = \left( \int d\mathbf{x} P_{\mathbf{X}}(\mathbf{x}) P_{\text{out}}(\mathbf{Y} | \mathbf{F} \cdot \mathbf{x}) \right)^{\frac{1}{\alpha}}. \qquad (A1)$$

The smaller $v$, the easier the student inference, see section II in the main text. The validity of the Gardner volume as a measure of informativeness is justified for the Bayes-optimal perceptron in section III of the main text.

We consider here pool-based active learning, where only a subset $S$ of the pool $S = \{\mathbf{F}^{\mu}\}_{1\le\mu\le\alpha N}$ is used for training. The choice of subset can be conveniently parametrized by the Boolean $\sigma_{\mu} \in \{0,1\}$, where $\sigma_{\mu} = 1$ means sample $\mathbf{F}_{\mu}$ is used, while $\sigma_{\mu} = 0$ means $\mathbf{F}_{\mu}$ is not selected. For a given budget $0 \le n = \frac{1}{N}|S| = \frac{1}{N} \sum_{\mu=1}^{\alpha N} \sigma_{\mu} \le \alpha$, we intend to find the selection $S$ that minimizes the Gardner volume $v(\sigma_{\mu})$, viz. that allows the best student guess. To do this we shall compute the complexity $\Sigma(n, v)$, with $e^{N\Sigma(n,v)}$ the number of ways to select $nN$ samples so that the Gardner volume associated with the training of the student is $v$, as in section IV of the main text.

## 2. Assumption

To simplify, the samples are taken to be identically and independently distributed according to a normal distribution $\forall (i, \mu)$, $F_i^{\mu} \stackrel{d}{=} \mathcal{N}(0, \frac{1}{\sqrt{N}})$. Moreover all measures over vectors are assumed to be separable, that is factorizable as a product of identical measures over the components. Notation-wise $P_X(\mathbf{x})$ for example is therefore understood to mean $\prod_{i=1}^{N} P_X(x_i)$.

## 3. LD measure

The goal is to compute the averaged log partition function (free entropy in statistical physics terms)

$$\Phi(\beta, \phi) = \mathbb{E}_{\mathbf{F}, \mathbf{Y}, \mathbf{x}^0} \frac{1}{N} \ln \Xi = \mathbb{E}_{\mathbf{F}, \mathbf{Y}, \mathbf{x}^0} \frac{1}{N} \ln \sum_{\sigma_{\mu}} \left[ \int d\mathbf{x} P_{\mathbf{X}}(\mathbf{x}) \prod_{\mu=1}^{\alpha N} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \cdot \mathbf{x})^{\sigma_{\mu}} \right]^{\beta} e^{\phi \sum_{\mu} \sigma_{\mu}}. \qquad (A2)$$

$\beta$ can be seen as an inverse temperature and $\phi$ as a chemical potential, see section IV in the main text. The reason why we compute $\Phi(\beta, \phi)$ is that this quantity is the Legendre transform of the complexity $\Sigma(n, v)$

$$\Phi(\beta, \phi) = \underset{v,n}{\text{extr}} \{\Sigma(n, v) + \beta \ln v + \phi n\}. \qquad (A3)$$
# Appendix A: Notations and Large-Deviation (LD) measure for GLMs

In this appendix we set the replica calculation in the more general setting of a generalized linear model (GLM) with arbitrary teacher/student prior/posterior. We allow the inference to be mismatched, i.e. we allow the teacher and student measures to be different. The specialization to the particular case of the teacher-student perceptron with no mismatch (Bayes-optimal) will be carried out in appendix C. Our computation borrows from [24] and [20] which study the simple measure. Because we study large deviations, our formalism has some semblance with one-step Replica Breaking (1RSB) equations, a discussion of which can be found for example in [31], [32], [14].

## 1. Definition of the problem

We consider a student GLM ([24]) with $N$-dimensional weights learning from $\alpha N$ samples $\mathbf{F}^{\mu} \in \mathbb{R}^N$ stacked in a matrix $\mathbf{F} \in \mathcal{M}_{\alpha N, N}(\mathbb{R})$ and the corresponding labels $y^{\mu}$ stacked into $\mathbf{Y} \in \mathbb{R}^{\alpha N}$. We assume the student-teacher (or planted) setting ([15]), where the labels are generated by the ground truth (teacher weights) $\mathbf{x}^0$ with the channel measure $\overline{P}_{\text{out}}(y^{\mu}|\mathbf{F}^{\mu} \cdot \mathbf{x}^0)$. The teacher weight itself is drawn with prior $\overline{P}_{\mathbf{X}}(\cdot)$. Given $\mathbf{F}$ and $\mathbf{Y}$, the student perceptron is trained so that its own weight vector $\mathbf{x}$ tries to match the ground truth $\mathbf{x}^0$. The inference is carried out with the student prior $P_{\mathbf{X}}(\cdot)$ and posterior $P_{\text{out}}(\mathbf{Y}|\mathbf{F} \cdot \mathbf{x})$. Note that the cases where $P_{\mathbf{X}}(\cdot) \neq \overline{P}_{\mathbf{X}}(\cdot)$ or $P_{\text{out}}(\cdot) \neq \overline{P}_{\text{out}}(\cdot)$ mean that the student ignores the precise Markov chain wherefrom the labels are generated, as discussed in section II, see also [15]. The likelihood that a vector $\mathbf{x}$ is the ground truth vector is then $P_{\mathbf{X}}(\mathbf{x})P_{\text{out}}(\mathbf{Y}|\mathbf{F} \cdot \mathbf{x})$. A reasonable measure of the average lack of accuracy of the student's guess is then given by the Gardner volume, viz. the partition function associated with the likelihood

$$v = \left( \int d\mathbf{x} P_{\mathbf{X}}(\mathbf{x}) P_{\text{out}}(\mathbf{Y}|\mathbf{F} \cdot \mathbf{x}) \right)^{\frac{1}{\alpha}}. \qquad (A1)$$

The smaller $v$, the easier the student inference, see section II in the main text. The validity of the Gardner volume as a measure of informativeness is justified for the Bayes-optimal perceptron in section III of the main text.

We consider here pool-based active learning, where only a subset $S$ of the pool $S = \{\mathbf{F}^{\mu}\}_{1\le\mu\le\alpha N}$ is used for training. The choice of subset can be conveniently parametrized by the Boolean $\sigma_{\mu} \in \{0,1\}$, where $\sigma_{\mu} = 1$ means sample $\mathbf{F}_{\mu}$ is used, while $\sigma_{\mu} = 0$ means $\mathbf{F}_{\mu}$ is not selected. For a given budget $0 \le n = \frac{1}{N}|S| = \frac{1}{N} \sum_{\mu=1}^{\alpha N} \sigma_{\mu} \le \alpha$, we intend to find the selection $S$ that minimizes the Gardner volume $v(\sigma_{\mu})$, viz. that allows the best student guess. To do this we shall compute the complexity $\Sigma(n, v)$, with $e^{N\Sigma(n,v)}$ the number of ways to select $nN$ samples so that the Gardner volume associated with the training of the student is $v$, as in section IV of the main text.

## 2. Assumption

To simplify, the samples are taken to be identically and independently distributed according to a normal distribution $\forall (i, \mu)$, $F_{i}^{\mu} \stackrel{d}{=} \mathcal{N}(0, \frac{1}{\sqrt{N}})$. Moreover all measures over vectors are assumed to be separable, that is factorizable as a product of identical measures over the components. Notation-wise $P_{\mathbf{X}}(\mathbf{x})$ for example is therefore understood to mean $\prod_{i=1}^{N} P_{\mathbf{X}}(x_i)$.

## 3. LD measure

The goal is to compute the averaged log partition function (free entropy in statistical physics terms)

$$\Phi(\beta, \phi) = \mathbb{E}_{\mathbf{F}, \mathbf{Y}, \mathbf{x}^0} \frac{1}{N} \ln \Xi = \mathbb{E}_{\mathbf{F}, \mathbf{Y}, \mathbf{x}^0} \frac{1}{N} \ln \sum_{\sigma_{\mu}} \left[ \int d\mathbf{x} P_{\mathbf{X}}(\mathbf{x}) \prod_{\mu=1}^{\alpha N} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \cdot \mathbf{x})^{\sigma_{\mu}} \right]^{\beta} e^{\phi \sum_{\mu} \sigma_{\mu}}. \qquad (A2)$$

$\beta$ can be seen as an inverse temperature and $\phi$ as a chemical potential, see section IV in the main text. The reason why we compute $\Phi(\beta, \phi)$ is that this quantity is the Legendre transform of the complexity $\Sigma(n, v)$

$$\Phi(\beta, \phi) = \underset{v,n}{\text{extr}} \{\Sigma(n, v) + \beta \ln v + \phi n\}. \qquad (A3)$$
Inverting the Legendre transform is then straightforward and yields $\Sigma(n, v)$

$$ \Sigma(n, v) = \Phi(\beta, \phi) - \beta \ln v - n\phi|_{\partial_{\beta}\Phi=\ln v, \partial_{\phi}\Phi=n}. \quad (A4) $$

The spectrum of values of $v$ such that $\Sigma(n, v) > 0$ for any given fixed $n$ corresponds to all achievable Gardner volumes for a budget $n$. In particular, $\inf_{v}\{v|\Sigma(n, v) > 0\}$ is the minimal Gardner volume when the $nN$ samples are chosen in an optimal way. Contrariwise, $\sup_{v}\{v|\Sigma(n, v) > 0\}$ is the maximal Gardner volume when the $nN$ samples are chosen in the least informative way for the student, so that the student inference problem is hardest. Finally note that the selection variables $\{\sigma_{\mu}\}$ play in the grand-canonical partition function (A2) the role of an annealed disorder in disordered systems terminology [14], and shall be sometimes referred to as such in the following.

# Appendix B: Replica computation

## 1. Replica trick

The standard way of taking care of the logarithm in equation (A2) is the replica trick ([12], [13], [14]),

$$ \Phi(\beta, \phi) = \lim_{s \to 0} \frac{1}{s} \mathbb{E}_{F, Y, x^0} \Xi^s. \quad (B1) $$

To compute $\mathbb{E}_{F, Y, x^0} \Xi^s$, one needs to further replicate $\beta$ times to care for the power $\beta$ involved in the summand in equation (A2)

$$ \begin{aligned} \mathbb{E}_{F, x^0} \Xi^s &= \mathbb{E}_F \int dx^0 \overline{P_X}(x^0) \int dy \prod_{\mu=1}^{\alpha N} \overline{P_{\text{out}}}(y^{\mu} | \mathbf{F}^{\mu} \cdot \mathbf{x}^0) \\ & \qquad \sum_{S_a^{\mu}} \int \prod_{a=1}^{s} \prod_{\alpha=1}^{\beta} (dx^{a\alpha} P_X(x^{a\alpha})) \prod_{a\alpha} \prod_{\mu} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \cdot \mathbf{x}^{a\alpha}) e^{\phi \sigma_{\mu}^{a}} \\ &= \mathbb{E}_F \sum_{S_a^{\mu}} \int \prod_{a\alpha} (dx^{a\alpha} P_X(x^{a\alpha})) e^{-\phi} \prod_{a\alpha} \prod_{\mu} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \cdot \mathbf{x}^{a\alpha}) e^{\phi \sigma_{\mu}^{a}}. \end{aligned} \quad (B2) $$

In the present problem we thus introduced two replication levels. Each replica is hence characterized by a set of two indices: the first $a$ index runs from 1 to $s$ and specifies the disorder replica, the second $\alpha$ index, running from 1 to $\beta$ is related to the replication in $\beta$. In total there are therefore $s \times \beta$ replicas. The teacher is set as replica 0. Implicitly henceforth $a\alpha$ when summed over will be running over $[1, s] \times [1, \beta] \cup 0$. But

$$ \begin{aligned} \mathbb{E}_F \prod_{a\alpha} \prod_{\mu} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \cdot \mathbf{x}^{a\alpha}) e^{\sigma_{\mu}^{a}} &= \int \prod_{\mu} \prod_{a\alpha} dh_{a\alpha}^{\mu} (\det 2\pi Q)^{-\frac{\alpha N}{2}} e^{-\frac{1}{2} \sum_{\mu} \sum_{a\alpha, c\gamma} h_{a\alpha}^{\mu} (Q^{-1})^{a\alpha} c\gamma h_{c\gamma}^{\mu}} \\ & \qquad \int \prod_{a\alpha \neq c\gamma} dq_{a\alpha, c\gamma} \int \prod_{a\alpha \neq c\gamma} d\hat{q}_{a\alpha, c\gamma} e^{\sum_{a\alpha \neq c\gamma} \hat{q}_{a\alpha, c\gamma} (\mathbf{x}^{a\alpha} \cdot \mathbf{x}^{c\gamma} - N q_{a\alpha, c\gamma}} \\ & \qquad \prod_{a\alpha} \prod_{\mu} P_{\text{out}}(y^{\mu} | h_{a\alpha}^{\mu}) e^{\sigma_{\mu}^{a}}, \end{aligned} \quad (B3) $$

where we defined $h_{a\alpha}^{\mu} \equiv \mathbf{F}^{\mu} \cdot \mathbf{x}^{a\alpha}$ Gaussian because of the central limit theorem and enforced the definition of its covariance matrix $Q$ with integral representations of Dirac deltas. The conjugate matrix is $\hat{Q}$. Matrix elements are noted with small $q$. Then

$$ \begin{aligned} \mathbb{E}_{F, x^0} \Xi^s &= \int d\hat{Q} dQ e^{-N \text{Tr} \hat{Q} Q} \left( \int \prod_{a\alpha} dx^{a\alpha} P_X(x^{a\alpha}) e^{\sum_{a\alpha \neq c\gamma} x^{a\alpha} \hat{q}_{a\alpha, c\gamma} x^{c\gamma}} \right)^N \\ & \qquad \left( \sum_{S^a} e^{\phi(\sum_a S^a - 1)} \int dy \prod_{a\alpha} dh_{a\alpha} (\det 2\pi Q)^{-\frac{1}{2}} e^{-\frac{1}{2} \sum_{a\alpha, c\gamma} h_{a\alpha}(Q^{-1})^{a\alpha} c\gamma h_{c\gamma}} \prod_{a\alpha} P_{\text{out}}(y^{\mu} | h_{a\alpha})^{S^a} \right)^{\alpha N}, \end{aligned} \quad (B4) $$
Inverting the Legendre transform is then straightforward and yields $\Sigma(n, v)$

$$ \Sigma(n, v) = \Phi(\beta, \phi) - \beta \ln v - n\phi|_{\partial_{\beta}\Phi=\ln v, \partial_{\phi}\Phi=n}. \quad (A4) $$

The spectrum of values of $v$ such that $\Sigma(n, v) > 0$ for any given fixed $n$ corresponds to all achievable Gardner volumes for a budget $n$. In particular, $\inf_{v}\{v|\Sigma(n, v) > 0\}$ is the minimal Gardner volume when the $nN$ samples are chosen in an optimal way. Contrariwise, $\sup_{v}\{v|\Sigma(n, v) > 0\}$ is the maximal Gardner volume when the $nN$ samples are chosen in the least informative way for the student, so that the student inference problem is hardest. Finally note that the selection variables $\{\sigma_{\mu}\}$ play in the grand-canonical partition function (A2) the role of an annealed disorder in disordered systems terminology [14], and shall be sometimes referred to as such in the following.

# Appendix B: Replica computation

## 1. Replica trick

The standard way of taking care of the logarithm in equation (A2) is the replica trick ([12], [13], [14]),

$$ \Phi(\beta, \phi) = \lim_{s \to 0} \frac{1}{s} \mathbb{E}_{F, Y, x^0} \Xi^s. \quad (B1) $$

To compute $\mathbb{E}_{F, Y, x^0} \Xi^s$, one needs to further replicate $\beta$ times to care for the power $\beta$ involved in the summand in equation (A2)

$$ \begin{aligned} \mathbb{E}_{F, x^0} \Xi^s &= \mathbb{E}_{F} \int dx^0 \overline{P_X}(x^0) \int dy \prod_{\mu=1}^{\alpha N} \overline{P_{\text{out}}}(y^{\mu} | \mathbf{F}^{\mu} \cdot \mathbf{x}^0) \\ & \qquad \sum_{S_a^{\mu}} \int \prod_{a=1}^{s} \prod_{\alpha=1}^{\beta} (dx^{a\alpha} P_X(\mathbf{x}^{a\alpha})) \prod_{a\alpha} \prod_{\mu} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \cdot \mathbf{x}^{a\alpha}) e^{\phi \sigma_{\mu}^{a}} \\ &= \mathbb{E}_{F} \sum_{S_a^{\mu}} \int \prod_{a\alpha} (dx^{a\alpha} P_X(\mathbf{x}^{a\alpha})) e^{-\phi} \prod_{a\alpha} \prod_{\mu} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \cdot \mathbf{x}^{a\alpha}) e^{\phi \sigma_{\mu}^{a}}. \end{aligned} \quad (B2) $$

In the present problem we thus introduced two replication levels. Each replica is hence characterized by a set of two indices: the first $a$ index runs from 1 to $s$ and specifies the disorder replica, the second $\alpha$ index, running from 1 to $\beta$ is related to the replication in $\beta$. In total there are therefore $s \times \beta$ replicas. The teacher is set as replica 0. Implicitly henceforth $a\alpha$ when summed over will be running over $[1, s] \times [1, \beta] \cup 0$. But

$$ \begin{aligned} \mathbb{E}_{F} \prod_{a\alpha} \prod_{\mu} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \cdot \mathbf{x}^{a\alpha}) e^{\sigma_{\mu}^{a}} &= \int \prod_{\mu} \prod_{a\alpha} dh_{a\alpha}^{\mu} (\det 2\pi Q)^{-\frac{\alpha N}{2}} e^{-\frac{1}{2} \sum_{\mu} \sum_{a\alpha, c\gamma} h_{a\alpha}^{\mu} (Q^{-1})^{a\alpha} c\gamma h_{c\gamma}^{\mu}} \\ & \qquad \int \prod_{a\alpha \neq c\gamma} dq_{a\alpha, c\gamma} \int \prod_{a\alpha \neq c\gamma} d\hat{q}_{a\alpha, c\gamma} e^{\sum_{a\alpha \neq c\gamma} \hat{q}_{a\alpha, c\gamma} (\mathbf{x}^{a\alpha} \cdot \mathbf{x}^{c\gamma} - N q_{a\alpha, c\gamma}}} \\ & \qquad \prod_{a\alpha} \prod_{\mu} P_{\text{out}}(y^{\mu} | h_{a\alpha}^{\mu}) e^{\sigma_{\mu}^{a}}, \end{aligned} \quad (B3) $$

where we defined $h_{a\alpha}^{\mu} \equiv F^{\mu} \cdot x^{a\alpha}$ Gaussian because of the central limit theorem and enforced the definition of its covariance matrix $Q$ with integral representations of Dirac deltas. The conjugate matrix is $\hat{Q}$. Matrix elements are noted with small $q$. Then

$$ \begin{aligned} \mathbb{E}_{F, x^0} \Xi^s &= \int d\hat{Q} dQ e^{-N \text{Tr} \hat{Q} Q} \left( \int \prod_{a\alpha} dx^{a\alpha} P_X(x^{a\alpha}) e^{\sum_{a\alpha \neq c\gamma} x^{a\alpha} \hat{q}_{a\alpha, c\gamma} x^{c\gamma}} \right)^N \\ & \qquad \left( \sum_{S^a} e^{\phi(\sum_a S^a - 1)} \int dy \prod_{a\alpha} dh_{a\alpha} (\det 2\pi Q)^{-\frac{1}{2}} e^{-\frac{1}{2} \sum_{a\alpha, c\gamma} h_{a\alpha}(Q^{-1})^{a\alpha} c\gamma h_{c\gamma}} \prod_{a\alpha} P_{\text{out}}(y^{\mu} | h_{a\alpha})^{S^a} \right)^{\alpha N}, \end{aligned} \quad (B4) $$
where we factorized both in i indices (first parenthesis) and in µ indices (second parenthesis). The free entropy defined in (A2) then reads

$$ \Phi(\beta, \phi) = \lim_{s \to 0} \frac{1}{s} \mathrm{extr} \left\{ -\mathrm{Tr} \hat{Q} Q + \ln I_X(\hat{Q}) + \alpha \ln I_Y(Q) \right\}, \qquad (B5) $$

with

$$ I_X = \int \prod_{a\alpha} d\mathbf{x}^{a\alpha} P_X(\mathbf{x}^{a\alpha}) e^{\frac{1}{a\alpha} \sum_{\alpha\gamma} x^{a\alpha} \hat{q}_{a\alpha, c\gamma} x^{c\gamma}}, \qquad (B6) $$

$$ I_Y = \sum_{S^a} e^{\phi(\sum_a S^a - 1)} \int dy \prod_{a\alpha} dh_{a\alpha} (\det 2\pi Q)^{-\frac{1}{2}} e^{-\frac{1}{2} \sum_{a\alpha, c\gamma} h_{a\alpha}(Q^{-1})^{a\alpha} c\gamma h_{c\gamma}} \prod_{a\alpha} P_{\mathrm{out}}(y^{\mu} | h_{a\alpha})^{S^a}. \qquad (B7) $$

## 2. Replica Symmetric (RS) ansatz

The extremization in equation (B5) is hard to carry out. As is now standard in the disordered systems literature we can reduce the number of parameters to be extremized over by enforcing the so-called Replica Symmetric (RS) ansatz ([14]) on both replication levels

$$ q^{0,0} = r^0, \quad \hat{q}^{0,0} = \hat{r}^0 \qquad (B8) $$

$$ q^{a\alpha,0} = m, \quad \hat{q}^{a\alpha,0} = \hat{m} \qquad (B9) $$

$$ q^{a\alpha,a\alpha} = r, \quad \hat{q}^{a\alpha,a\alpha} = -\frac{1}{2}\hat{r} \qquad (B10) $$

$$ q^{a\alpha,a\gamma} = Q, \quad \hat{q}^{a\alpha,a\gamma} = \hat{Q} \qquad (B11) $$

$$ q^{a\alpha,c\gamma} = q, \quad \hat{q}^{a\alpha,c\gamma} = \hat{q}, \qquad (B12) $$

where $q < Q$. Physically, the ansatz (B8)-(B12) means that two replicas seeing the same realisation of disorder (i.e., possessing the same first index) have an overlap $Q$ greater than the overlap between students seeing different realisations (an thus possessing different a-index). The $-\frac{1}{2}$ in the definition of $\hat{r}$ (B10) is just introduced for latter convenience.

Note finally that while the ansatz (B8) to (B12) is replica-symmetric for both replications, it gives a set of equations that are formally those of a 1RSB problem ([32]). This is also a reason why taking 1RSB ansatz ([14]) in the present large deviation calculation would be rather involved as it would lead to equations in the usual 2RSB form that are numerically involved to be solved.

We plug the RS ansatz (B8)-(B12) into the three contributions that make up equation (B5). The trace term is

$$ - \mathrm{Tr} \hat{Q} Q = - \hat{r}^0 r^0 - \beta s m \hat{m} + \frac{1}{2} \beta s r \hat{r} - s \frac{\beta(\beta-1)}{2} Q \hat{Q} - \beta^2 \frac{s(s-1)}{2} q \hat{q} \qquad (B13) $$

We can decompose the exponent in (B6) according to the ansatz (B8)-(B12)

$$ \sum_{a\alpha \neq c\gamma} x^{a\alpha} \hat{q}_{a\alpha, c\gamma} x^{c\gamma} = \hat{r}^0(x^0)^2 + \hat{m}x^0 \sum_{a\alpha \neq 0} x^{a\alpha} - \frac{\hat{r} + \hat{Q}}{2} \sum_{a\alpha \neq 0} (x^{a\alpha})^2 + \frac{\hat{Q} - \hat{q}}{2} \sum_{a \neq 0} \sum_{\alpha, \gamma} x^{a\alpha} x^{a\gamma} \\ + \frac{\hat{q}}{2} \sum_{a\alpha \neq 0, c\gamma \neq 0} x^{a\alpha} x^{c\gamma}. \qquad (B14) $$

In the last but one term index 0 does not intervene. Introducing Hubbard-Stratonovitch fields {$\lambda_a$} for the last but one term and Hubbard-Stratonovitch field $\xi$ for the last, $I_X$ reads

$$ I_X = \int D\xi \int dx^0 \overline{P_X}(x^0) e^{\hat{r}^0(x^0)^2} \left[ \int D\lambda \left( \int dx P_X(x) e^{\hat{m}x^0 x - \frac{\hat{r}+\hat{Q}}{2} x^2 + \sqrt{\hat{Q}-\hat{q}} \lambda x + \sqrt{\hat{q}} \xi x} \right)^{\beta} \right]^s. \qquad (B15) $$

To carry out the computation for $I_Y$ (equation (B7)) we need to explicitly compute the inverse of the Parisi matrix $Q$ involved in equation (B7). This is done in the following subsection.
where we factorized both in $i$ indices (first parenthesis) and in $\mu$ indices (second parenthesis). The free entropy defined in (A2) then reads

$$ \Phi(\beta, \phi) = \lim_{s \to 0} \frac{1}{s} \mathrm{extr} \left\{ -\mathrm{Tr} \hat{Q} Q + \ln I_X(\hat{Q}) + \alpha \ln I_Y(Q) \right\}, \qquad (B5) $$

with

$$ I_X = \int \prod_{a\alpha} d\mathbf{x}^{a\alpha} P_X(\mathbf{x}^{a\alpha}) e^{\frac{1}{a\alpha} \sum_{\alpha\gamma} x^{a\alpha} \hat{q}_{\alpha\alpha, c\gamma} x^{c\gamma}}, \qquad (B6) $$

$$ I_Y = \sum_{S^a} e^{\phi(\sum_a S^a - 1)} \int dy \prod_{a\alpha} dh_{a\alpha} (\det 2\pi Q)^{-\frac{1}{2}} e^{-\frac{1}{2} \sum_{a\alpha, c\gamma} h_{a\alpha}(Q^{-1})^{a\alpha} c\gamma h_{c\gamma}} \prod_{a\alpha} P_{\mathrm{out}}(y^{\mu} | h_{a\alpha})^{S^a}. \qquad (B7) $$

## 2. Replica Symmetric (RS) ansatz

The extremization in equation (B5) is hard to carry out. As is now standard in the disordered systems literature we can reduce the number of parameters to be extremized over by enforcing the so-called Replica Symmetric (RS) ansatz ([14]) on both replication levels

$$ q^{0,0} = r^0, \quad \hat{q}^{0,0} = \hat{r}^0 \qquad (B8) $$

$$ q^{a\alpha,0} = m, \quad \hat{q}^{a\alpha,0} = \hat{m} \qquad (B9) $$

$$ q^{a\alpha,a\alpha} = r, \quad \hat{q}^{a\alpha,a\alpha} = -\frac{1}{2}\hat{r} \qquad (B10) $$

$$ q^{a\alpha,a\gamma} = Q, \quad \hat{q}^{a\alpha,a\gamma} = \hat{Q} \qquad (B11) $$

$$ q^{a\alpha,c\gamma} = q, \quad \hat{q}^{a\alpha,c\gamma} = \hat{q}, \qquad (B12) $$

where $q < Q$. Physically, the ansatz (B8)-(B12) means that two replicas seeing the same realisation of disorder (i.e., possessing the same first index) have an overlap $Q$ greater than the overlap between students seeing different realisations (an thus possessing different $a$-index). The $-\frac{1}{2}$ in the definition of $\hat{r}$ (B10) is just introduced for latter convenience.

Note finally that while the ansatz (B8) to (B12) is replica-symmetric for both replications, it gives a set of equations that are formally those of a 1RSB problem ([32]). This is also a reason why taking 1RSB ansatz ([14]) in the present large deviation calculation would be rather involved as it would lead to equations in the usual 2RSB form that are numerically involved to be solved.

We plug the RS ansatz (B8)-(B12) into the three contributions that make up equation (B5). The trace term is

$$ - \mathrm{Tr} \hat{Q} Q = - \hat{r}^0 r^0 - \beta s m \hat{m} + \frac{1}{2} \beta s r \hat{r} - s \frac{\beta(\beta-1)}{2} Q \hat{Q} - \beta^2 \frac{s(s-1)}{2} q \hat{q} \qquad (B13) $$

We can decompose the exponent in (B6) according to the ansatz (B8)-(B12)

$$ \sum_{a\alpha \neq c\gamma} x^{a\alpha} \hat{q}_{a\alpha, c\gamma} x^{c\gamma} = \hat{r}^0(x^0)^2 + \hat{m}x^0 \sum_{a\alpha \neq 0} x^{a\alpha} - \frac{\hat{r} + \hat{Q}}{2} \sum_{a\alpha \neq 0} (x^{a\alpha})^2 + \frac{\hat{Q} - \hat{q}}{2} \sum_{a \neq 0} \sum_{\alpha, \gamma} x^{a\alpha} x^{a\gamma} \\ + \frac{\hat{q}}{2} \sum_{a\alpha \neq 0, c\gamma \neq 0} x^{a\alpha} x^{c\gamma}. \qquad (B14) $$

In the last but one term index 0 does not intervene. Introducing Hubbard-Stratonovitch fields {$\lambda_a$} for the last but one term and Hubbard-Stratonovitch field $\xi$ for the last, $I_X$ reads

$$ I_X = \int D\xi \int dx^0 \overline{P_X}(x^0) e^{\hat{r}^0(x^0)^2} \left[ \int D\lambda \left( \int dx P_X(x) e^{\hat{m}x^0 x - \frac{\hat{r}+\hat{Q}}{2}x^2 + \sqrt{\hat{Q}-\hat{q}}\lambda x + \sqrt{\hat{q}}\xi x} \right)^{\beta} \right]^s. \qquad (B15) $$

To carry out the computation for $I_Y$ (equation (B7)) we need to explicitly compute the inverse of the Parisi matrix $Q$ involved in equation (B7). This is done in the following subsection.
Some linear algebra for hierarchical matrices Name $\tilde{Q} \equiv Q^{-1}$ the inverse of the overlap matrix $Q$. Since $\tilde{Q}$ is clearly of the same form as $Q$, we can parametrize its coefficient in an identical fashion as those of $Q \tilde{r}^0, \tilde{m}, \tilde{r}, \tilde{q}, \tilde{Q}$. $\tilde{Q}Q = 1_{\beta s+1}$ means

$$r^0 \tilde{r}^0 + \beta s m \tilde{m} = 1 \qquad (B16)$$

$$r^0 \tilde{m} + m \tilde{r} + (\beta - 1) \tilde{Q} m + \beta(s-1) \tilde{q} m = 0 \qquad (B17)$$

$$\tilde{r}^0 m + \tilde{m}(r + (\beta - 1)Q + \beta(s-1)q) = 0 \qquad (B18)$$

$$m \tilde{m} + r \tilde{r} + (\beta - 1) Q \tilde{Q} + \beta(s-1) q \tilde{q} = 1 \qquad (B19)$$

$$m \tilde{m} + r \tilde{Q} + \tilde{r} Q + (\beta - 2) Q \tilde{Q} + \beta(s-1) q \tilde{q} = 0 \qquad (B20)$$

$$m \tilde{m} + r \tilde{q} + (\beta - 1) Q \tilde{q} + q \tilde{r} + (\beta - 1) q \tilde{Q} + \beta(s-2) q \tilde{q} = 0, \qquad (B21)$$

yielding

$$\tilde{r}^0 = \frac{r + (\beta - 1)Q + \beta(s-1)q}{r^0(r + (\beta - 1)Q + \beta(s-1)q) - \beta s m^2} \qquad (B22)$$

$$\tilde{m} = \frac{-m}{r^0(r + (\beta - 1)Q + \beta(s-1)q) - \beta s m^2} \qquad (B23)$$

$$\tilde{r} = \frac{\beta m^2 (q - 2Q = r) + \beta((1-s)q^2 + Q(3Q - 2r) + (s-2)q(2Q - r))r^0}{(Q-r)(r + (\beta-1)Q - \beta q)(r^0(r + (\beta-1)Q + \beta(s-1)q) - \beta s m^2)} + \frac{\beta^2(q-Q)(-m^2s + ((-1+s)q+Q)r^0) + (Q-r)(m^2 + (-2Q+r)r^0)}{(Q-r)(r + (\beta-1)Q - \beta q)(r^0(r + (\beta-1)Q + \beta(s-1)q) - \beta s m^2)} \qquad (B24)$$

$$\tilde{Q} = \frac{(Q - r)(m^2 - Q r^0) + \beta(q - Q)(m^2 s - ((s - 1)q + Q)r^0)}{(Q - r)(r + (\beta - 1)Q - \beta q)(r^0(r + (\beta - 1)Q + \beta(s - 1)q) - \beta s m^2)} \qquad (B25)$$

$$\tilde{q} = \frac{-m^2 + q r^0}{(r + (\beta - 1)Q - \beta q)(r^0(r + (\beta - 1)Q + \beta(s - 1)q) - \beta s m^2)}. \qquad (B26)$$

We'll also need the determinant of $Q$. To do this, the simplest way is to guess the eigenvectors. For $(x, 1, 1, ...1)^T$ we get two eigenvalues $\lambda_{\pm}$ whose product is

$$\lambda_{+} \lambda_{-} = r^0 (r + (\beta - 1)Q + (s - 1)\beta q) - \beta s m^2. \qquad (B27)$$

Then come $s(\beta - 1)$ eigenvectors $e_i - e_{i+1}$, $i \neq 0[\beta]$ (we are indexing starting from 0), with associated eigenvalues $(r - Q)$. Then for $0 \le s \le s - 2$, $\sum_{k=s\beta+1}^{(s+1)\beta} e_k - \sum_{k=(s+1)\beta+1}^{(s+2)\beta} e_k$ is an eigenvector with eigenvalue $r + (\beta - 1)Q - \beta q$. Then

$$\ln \det Q = \ln(r^0(r + (\beta - 1)Q + (s - 1)\beta q) - \beta m^2) + (s - 1)\ln(r + (\beta - 1)Q - \beta q) + (\beta - 1)\ln(r - Q). \qquad (B28)$$

The same equality holds with tilde quantities in the right-hand side provided the signs are inverted, since $\ln \det Q = -\ln \det \tilde{Q}$. Identifying term by term results straightforwardly in a set of relations between tilde and non-tilde quantities (henceforth referred as determinant relations),

$$r^0(r + (\beta - 1)Q + (s - 1)\beta q) - \beta m^2 = [\tilde{r}^0(\tilde{r} + (\beta - 1)\tilde{Q} + (s - 1)\beta \tilde{q}) - \beta \tilde{m}^2]^{-1} \qquad (B29)$$

$$r + (\beta - 1)Q - \beta q = [\tilde{r} + (\beta - 1)\tilde{Q} - \beta \tilde{q}]^{-1} \qquad (B30)$$

$$r - Q = [\tilde{r} - \tilde{Q}]^{-1}. \qquad (B31)$$

Now decomposing the exponent in $I_Y$ (B7)

$$-\frac{1}{2} \sum_{a\alpha, c\gamma} h_{a\alpha} \tilde{q}_{a\alpha, c\gamma} h_{c\gamma} = -\frac{1}{2} \tilde{r}^0 (h^0)^2 - \tilde{m} h^0 \sum_{a\alpha \neq 0} h_{a\alpha} - \frac{\tilde{r} - \tilde{Q}}{2} \sum_{a\alpha \neq 0} (h_{a\alpha})^2 + (\tilde{q} - \tilde{Q}) \sum_a \sum_{\alpha, \gamma} h_{a\alpha} h_{a\gamma} - \tilde{q} \sum_{a\alpha \neq 0, c\gamma \neq 0} h_{a\alpha} h_{c\gamma}. \qquad (B32)$$
Some linear algebra for hierarchical matrices Name $\tilde{Q} \equiv Q^{-1}$ the inverse of the overlap matrix $Q$. Since $\tilde{Q}$ is clearly of the same form as $Q$, we can parametrize its coefficient in an identical fashion as those of $Q \tilde{r}^0, \tilde{m}, \tilde{r}, \tilde{q}, \tilde{Q}$. $\tilde{Q}Q = 1_{\beta s+1}$ means

$$r^0 \tilde{r}^0 + \beta s m \tilde{m} = 1 \qquad (B16)$$

$$r^0 \tilde{m} + m \tilde{r} + (\beta - 1) \tilde{Q} m + \beta(s-1) \tilde{q} m = 0 \qquad (B17)$$

$$\tilde{r}^0 m + \tilde{m}(r + (\beta - 1)Q + \beta(s-1)q) = 0 \qquad (B18)$$

$$m \tilde{m} + r \tilde{r} + (\beta - 1) Q \tilde{Q} + \beta(s-1) q \tilde{q} = 1 \qquad (B19)$$

$$m \tilde{m} + r \tilde{Q} + \tilde{r} Q + (\beta - 2) Q \tilde{Q} + \beta(s-1) q \tilde{q} = 0 \qquad (B20)$$

$$m \tilde{m} + r \tilde{q} + (\beta - 1) Q \tilde{q} + q \tilde{r} + (\beta - 1) q \tilde{Q} + \beta(s-2) q \tilde{q} = 0, \qquad (B21)$$

yielding

$$\tilde{r}^0 = \frac{r + (\beta - 1)Q + \beta(s-1)q}{r^0(r + (\beta - 1)Q + \beta(s-1)q) - \beta s m^2} \qquad (B22)$$

$$\tilde{m} = \frac{-m}{r^0(r + (\beta - 1)Q + \beta(s-1)q) - \beta s m^2} \qquad (B23)$$

$$\tilde{r} = \frac{\beta m^2 (q - 2Q = r) + \beta((1-s)q^2 + Q(3Q - 2r) + (s-2)q(2Q - r))r^0}{(Q-r)(r + (\beta-1)Q - \beta q)(r^0(r + (\beta-1)Q + \beta(s-1)q) - \beta s m^2)} + \frac{\beta^2(q-Q)(-m^2s + ((-1+s)q+Q)r^0) + (Q-r)(m^2 + (-2Q+r)r^0)}{(Q-r)(r + (\beta-1)Q - \beta q)(r^0(r + (\beta-1)Q + \beta(s-1)q) - \beta s m^2)} \qquad (B24)$$

$$\tilde{Q} = \frac{(Q - r)(m^2 - Q r^0) + \beta(q - Q)(m^2 s - ((s - 1)q + Q)r^0)}{(Q - r)(r + (\beta - 1)Q - \beta q)(r^0(r + (\beta - 1)Q + \beta(s - 1)q) - \beta s m^2)} \qquad (B25)$$

$$\tilde{q} = \frac{-m^2 + q r^0}{(r + (\beta - 1)Q - \beta q)(r^0(r + (\beta - 1)Q + \beta(s - 1)q) - \beta s m^2)}. \qquad (B26)$$

We'll also need the determinant of $Q$. To do this, the simplest way is to guess the eigenvectors. For $(x, 1, 1, \dots, 1)^T$ we get two eigenvalues $\lambda_{\pm}$ whose product is

$$\lambda_{+} \lambda_{-} = r^0 (r + (\beta - 1)Q + (s - 1)\beta q) - \beta s m^2. \qquad (B27)$$

Then come $s(\beta - 1)$ eigenvectors $e_i - e_{i+1}$, $i \neq 0$ [β] (we are indexing starting from 0), with associated eigenvalues $(r - Q)$. Then for $0 \le s \le s - 2$, $\sum_{k=s\beta+1}^{(s+1)\beta} e_k - \sum_{k=(s+1)\beta+1}^{(s+2)\beta} e_k$ is an eigenvector with eigenvalue $r + (\beta - 1)Q - \beta q$. Then

$$\ln \det Q = \ln(r^0(r + (\beta - 1)Q + (s - 1)\beta q) - \beta m^2) + (s - 1)\ln(r + (\beta - 1)Q - \beta q) + (\beta - 1)\ln(r - Q). \qquad (B28)$$

The same equality holds with tilde quantities in the right-hand side provided the signs are inverted, since $\ln \det Q = -\ln \det \tilde{Q}$. Identifying term by term results straightforwardly in a set of relations between tilde and non-tilde quantities (henceforth referred as determinant relations),

$$r^0(r + (\beta - 1)Q + (s - 1)\beta q) - \beta m^2 = [\tilde{r}^0(\tilde{r} + (\beta - 1)\tilde{Q} + (s - 1)\beta \tilde{q}) - \beta \tilde{m}^2]^{-1} \qquad (B29)$$

$$r + (\beta - 1)Q - \beta q = [\tilde{r} + (\beta - 1)\tilde{Q} - \beta \tilde{q}]^{-1} \qquad (B30)$$

$$r - Q = [\tilde{r} - \tilde{Q}]^{-1}. \qquad (B31)$$

Now decomposing the exponent in $I_Y$ (B7)

$$-\frac{1}{2} \sum_{a\alpha, c\gamma} h_{a\alpha} \tilde{q}_{a\alpha, c\gamma} h_{c\gamma} = -\frac{1}{2} \tilde{r}^0 (h^0)^2 - \tilde{m} h^0 \sum_{a\alpha \neq 0} h_{a\alpha} - \frac{\tilde{r} - \tilde{Q}}{2} \sum_{a\alpha \neq 0} (h_{a\alpha})^2 + (\tilde{q} - \tilde{Q}) \sum_a \sum_{\alpha, \gamma} h_{a\alpha} h_{a\gamma} - \tilde{q} \sum_{a\alpha \neq 0, c\gamma \neq 0} h_{a\alpha} h_{c\gamma}. \qquad (B32)$$
Introducing HS fields {$\zeta_a$} and $\eta$ for the last two sums of (B32) and factorizing in the index $a$

$$ I_Y = \frac{1}{\sqrt{\det 2\pi \overline{Q}}} \int dy \int D\eta \int dh^0 \overline{P_{\text{out}}}(y|h^0) e^{-\frac{1}{2} \hat{r}^0 (h^0)^2} \left[ \sum_{S=0,1} \int D\zeta e^{\phi S} \left( \int dh P_{\text{out}}(y|h)^S e^{-\hat{m}h^0 h - \frac{\hat{r}-\overline{Q}}{2} h^2 + \sqrt{\hat{q}-\overline{q}} \zeta h + \sqrt{-\hat{q}\eta h}} \right)^\beta \right]^S . \quad (B33) $$

Now that all terms are computed the next step is then to divide by $s$ and take the $s \to 0$ limit as prescribed by the replica trick (B1). First, we need to enforce that all non-vanishing order 0 contribution cancel out, since the free entropy should not be diverging. Then, one needs to actually compute first order terms that will contribute in $\Phi$ (B5).

Order 0 At order 0, $I_Y = 1$ since

$$ \begin{aligned} \lim_{s \to 0} \ln \det (2\pi \overline{Q}) &= \frac{1}{2} \ln (2\pi \hat{r}^0) \\ &= -\ln \int dy \int D\eta \int dh^0 \overline{P_{\text{out}}}(y|h^0) e^{-\frac{1}{2} \hat{r}^0 (h^0)^2}. \end{aligned} \quad (B34) $$

The cancellation of order 0 terms imposes

$$ 0 = \hat{r}^0 r^0 + \ln \int dx^0 \overline{P_X}(x^0) e^{\hat{r}^0 (x^0)^2}, \quad (B35) $$

where the first term comes from the trace term (B13). It follows that $\hat{r}^0 = 0$. Moreover, because of the saddle point equality

$$ q_{a\alpha,c\gamma} = \frac{\int \prod_{d\delta} (dx^{d\delta} P_X(x^{d\delta})) x^{a\alpha} x^{c\gamma} e^{\sum_{d\delta \neq e\epsilon} x^{d\delta} \hat{q}_{d\delta, e\epsilon} x^{e\epsilon}}}{\int \prod_{d\delta} (dx^{d\delta} P_X(x^{d\delta})) e^{\sum_{d\delta \neq e\epsilon} x^{d\delta} \hat{q}_{d\delta, e\epsilon} x^{e\epsilon}}}, \quad (B36) $$

derived straightforwardly from (B5) we also have

$$ r^0 = \int dx^0 \overline{P_X}(x^0) (x^0)^2. \quad (B37) $$

Order 1

a. $I_X$ Carrying out a change of variables $\xi \to \xi + \hat{q}^{-\frac{1}{2}} \hat{m} x^0$ in equation (B15), $I_X$ assumes the compact form

$$ \lim_{s \to 0} \frac{1}{s} I_X = \int D\xi I_X^0(\xi) \ln I_X^1(\xi), \quad (B38) $$

where

$$ I_X^0(\xi) = \int dx^0 \overline{P_X}(x^0) e^{-\frac{\hat{m}^2}{2\hat{q}}(x^0)^2 + \frac{\hat{m}\hat{q}}{\sqrt{\hat{q}}} \xi x^0} \quad (B39) $$

$$ I_X^1(\xi) = \int D\lambda \left[ \int dx P_X(x) e^{-\frac{\hat{r}+\overline{Q}}{2} x^2 + \left( \sqrt{\overline{Q}-\hat{q}}\lambda + \sqrt{\hat{q}}\xi \right) x} \right]^\beta . \quad (B40) $$

b. $I_Y$ Changing $\eta \to \eta - \frac{\hat{m}}{\sqrt{-\hat{q}}} h^0$ in (B33) yields

$$ I_Y = \frac{1}{\sqrt{\det 2\pi \overline{Q}}} \int dy \int D\eta g^0(y, \eta) (g^1(y, \eta))^s, \quad (B41) $$

with

$$ g^0(y, \eta) = \int dh^0 \overline{P_{\text{out}}}(y|h^0) e^{-\frac{1}{2}(\hat{r}^0 - \frac{\hat{m}^2}{\hat{q}})(h^0)^2 - \frac{\hat{m}}{\sqrt{-\hat{q}}} h^0 \eta} \quad (B42) $$

$$ g^1(y, \eta) = \sum_{S=0,1} \int D\zeta e^{\phi S} \left( \int dh P_{\text{out}}(y|h)^S e^{-\frac{\hat{r}-\overline{Q}}{2}h^2 + \sqrt{\hat{q}-\overline{q}}\zeta h + \sqrt{-\hat{q}\eta h}} \right)^\beta . \quad (B43) $$
Introducing HS fields {$\zeta_a$} and $\eta$ for the last two sums of (B32) and factorizing in the index $a$

$$ I_Y = \frac{1}{\sqrt{\det 2\pi \overline{Q}}} \int dy \int D\eta \int dh^0 \overline{P_{\text{out}}}(y|h^0) e^{-\frac{1}{2} \hat{r}^0 (h^0)^2} \left[ \sum_{S=0,1} \int D\zeta e^{\phi S} \left( \int dh P_{\text{out}}(y|h)^S e^{-\hat{m}h^0} e^{-\frac{\hat{r}-\overline{Q}}{2}h^2 + \sqrt{\hat{q}-\overline{q}}\zeta h + \sqrt{-\hat{q}\eta}h} \right)^\beta \right]^S . \quad (B33) $$

Now that all terms are computed the next step is then to divide by $s$ and take the $s \to 0$ limit as prescribed by the replica trick (B1). First, we need to enforce that all non-vanishing order 0 contribution cancel out, since the free entropy should not be diverging. Then, one needs to actually compute first order terms that will contribute in $\Phi$ (B5).

Order 0 At order 0, $I_Y = 1$ since

$$ \begin{aligned} \lim_{s \to 0} \ln \det(2\pi \overline{Q}) &= \frac{1}{2} \ln(2\pi \hat{r}^0) \\ &= -\ln \int dy \int D\eta \int dh^0 \overline{P_{\text{out}}}(y|h^0) e^{-\frac{1}{2} \hat{r}^0 (h^0)^2}. \end{aligned} \quad (B34) $$

The cancellation of order 0 terms imposes

$$ 0 = \hat{r}^0 r^0 + \ln \int dx^0 \overline{P_X}(x^0) e^{\hat{r}^0 (x^0)^2}, \quad (B35) $$

where the first term comes from the trace term (B13). It follows that $\hat{r}^0 = 0$. Moreover, because of the saddle point equality

$$ q_{a\alpha,c\gamma} = \frac{\int \prod_{d\delta} (dx^{d\delta} P_X(x^{d\delta})) x^{a\alpha} x^{c\gamma} e^{\sum_{e\epsilon} x^{d\delta} \hat{q}_{d\delta, e\epsilon} x^{e\epsilon}}}{\int \prod_{d\delta} (dx^{d\delta} P_X(x^{d\delta})) e^{\sum_{e\epsilon} x^{d\delta} \hat{q}_{d\delta, e\epsilon} x^{e\epsilon}}}, \quad (B36) $$

derived straightforwardly from (B5) we also have

$$ r^0 = \int dx^0 \overline{P_X}(x^0)(x^0)^2. \quad (B37) $$

Order 1

a. $I_X$ Carrying out a change of variables $\xi \to \xi + \hat{q}^{-\frac{1}{2}} \hat{m} x^0$ in equation (B15), $I_X$ assumes the compact form

$$ \lim_{s \to 0} \frac{1}{s} I_X = \int D\xi I_X^0(\xi) \ln I_X^1(\xi), \quad (B38) $$

where

$$ I_X^0(\xi) = \int dx^0 \overline{P_X}(x^0) e^{-\frac{\hat{m}^2}{2\hat{q}}(x^0)^2 + \frac{\hat{m}\hat{q}}{\sqrt{\hat{q}}} \xi x^0} \quad (B39) $$

$$ I_X^1(\xi) = \int D\lambda \left[ \int dx P_X(x) e^{-\frac{\hat{r}+\overline{Q}}{2}x^2 + (\sqrt{\overline{Q}-\hat{q}}\lambda + \sqrt{\hat{q}}\xi)x} \right]^\beta . \quad (B40) $$

b. $I_Y$ Changing $\eta \to \eta - \frac{\hat{m}}{\sqrt{-\hat{q}}} h^0$ in (B33) yields

$$ I_Y = \frac{1}{\sqrt{\det 2\pi \overline{Q}}} \int dy \int D\eta g^0(y, \eta) (g^1(y, \eta))^s, \quad (B41) $$

with

$$ g^0(y, \eta) = \int dh^0 \overline{P_{\text{out}}}(y|h^0) e^{-\frac{1}{2}(\hat{r}^0 - \frac{\hat{m}^2}{\hat{q}})(h^0)^2 - \frac{\hat{m}}{\sqrt{-\hat{q}}} h^0 \eta} \quad (B42) $$

$$ g^1(y, \eta) = \sum_{S=0,1} \int D\zeta e^{\phi S} \left( \int dh P_{\text{out}}(y|h)^S e^{-\frac{\hat{r}-\overline{Q}}{2}h^2 + \sqrt{\hat{q}-\overline{q}}\zeta h + \sqrt{-\hat{q}\eta}h} \right)^\beta . \quad (B43) $$
Expanding ln$I_Y$ to $\mathcal{O}(s)$ (subscripts in parentheses standing for order in $s$) gives

$$ \frac{1}{s} \ln I_Y = -\frac{1}{2} \ln(\det 2\pi Q)_{(1)} + \frac{1}{\sqrt{2\pi r^0}} \int D\eta \int dy [g_{(1)}^0(y, \eta) + g_{(0)}^0(y, \eta) \ln g_{(0)}^1(y, \eta)]. \quad (B44) $$

We used the fact that at order 0 terms canceled, and the identity $\int D\eta \int dy g^0(y, \eta) = \sqrt{2\pi r^0} + \mathcal{O}(s)$. But

$$ \begin{aligned} \frac{1}{\sqrt{2\pi r^0}} \int D\eta \int dy g_{(1)}^0(y, \eta) &= \lim_{s \to 0} \frac{1}{\sqrt{2\pi r^0}} \partial_s \left( \int D\eta \int dy g^0(y, \eta) \right) \\ &= \lim_{s \to 0} \frac{1}{\sqrt{2\pi r^0}} \partial_s \sqrt{\frac{2\pi}{\hat{r}^0}} \\ &= \frac{-\beta m^2}{2r^0(r + (\beta - 1)Q - \beta q)}, \end{aligned} \quad (B45) $$

thus

$$ \begin{aligned} \frac{1}{s} \ln I_Y = & -\frac{1}{2} \frac{\beta q}{r + (\beta - 1)Q - \beta q} - \frac{1}{2} \ln(r + (\beta - 1)Q - \beta q) - \frac{1}{2}(\beta - 1) \ln(r - Q) \\ & + \frac{1}{\sqrt{2\pi r^0}} \int dy \int D\eta g_{(0)}^0(y, \eta) \ln g_{(0)}^1(y, \eta). \end{aligned} \quad (B46) $$

It's actually possible to proceed to Gaussian changes of variables in the last term so as to exactly cancel the first three contributions in (B46). To do this

$$ h \to \sqrt{r - Q}h + (r - Q)(\sqrt{\tilde{q} - \tilde{Q}}\zeta + \sqrt{-\tilde{q}}\eta) \quad (B47) $$

$$ \zeta \to \frac{1}{\sqrt{1 - \beta(r - Q)(\tilde{q} - \tilde{Q})}} \zeta - \frac{\beta \sqrt{-\tilde{q}(\tilde{q} - \tilde{Q})(r - Q)}}{1 - \beta(r - Q)(\tilde{q} - \tilde{Q})\eta}, \quad (B48) $$

(we used the determinant relations (B29)-(B31)) allowing to rewrite the last term in (B46) as

$$ \begin{aligned} \frac{1}{\sqrt{2\pi r^0}} \int dy \int D\eta g_{(0)}^0(y, \eta) \ln g_{(0)}^1(y, \eta) = & \frac{\beta}{2} \ln(r - Q) - \frac{1}{2} \ln(1 - \beta(r - Q)(\tilde{q} - \tilde{Q})) \\ & + \int \frac{dy}{\sqrt{2\pi r^0}} \int D\eta g_{(0)}^0(y, \eta) \ln \left( 1 + e^{\phi} \int D\zeta \left( \int dh P_{\text{out}}(y|\ast) \right)^\beta \right) \\ & + \frac{1}{2} \left( -\beta(r - Q)\tilde{q} + \frac{\beta^2(-\tilde{q}(\tilde{q} - \tilde{Q})(r - Q)^2)}{1 - \beta(r - Q)(\tilde{q} - \tilde{Q})} \right) \int D\eta \eta^2 \int \frac{dy}{\sqrt{2\pi r^0}} g_{(0)}^0(y, \eta), \end{aligned} \quad (B49) $$

with

$$ * = \sqrt{r - Q}h + (r - Q) \left( \sqrt{\frac{\tilde{q} - \tilde{Q}}{1 - \beta(r - Q)(\tilde{q} - \tilde{Q})}} \zeta + \frac{\sqrt{-\tilde{q}}}{1 - \beta(r - Q)(\tilde{q} - \tilde{Q})} \eta \right). \quad (B50) $$

It is straightforward to see

$$ \int D\eta \eta^2 \int \frac{dy}{\sqrt{2\pi r^0}} g_{(0)}^0(y, \eta) = \frac{\hat{r}^0 \tilde{q} - \tilde{m}^2}{\hat{r}^0 \tilde{q}}, \quad (B51) $$

so the last term in (B49) is

$$ \begin{aligned} & \frac{1}{2} \left( -\beta(r - Q)\tilde{q} + \frac{\beta^2(-\tilde{q}(\tilde{q} - \tilde{Q})(r - Q)^2)}{1 - \beta(r - Q)(\tilde{q} - \tilde{Q})} \right) \int D\eta \eta^2 \int \frac{dy}{\sqrt{2\pi r^0}} g_{(0)}^0(y, \eta) \\ &= -\frac{\beta}{2} \frac{\hat{r}^0 \tilde{q} - \tilde{m}^2}{\hat{r}^0 (\tilde{r} + (\beta - 1)\tilde{Q} - \beta \tilde{q})} \\ &= \frac{1}{2} \frac{\beta q}{r + (\beta - 1)\tilde{Q} - \beta q}. \end{aligned} \quad (B52) $$
Expanding $\ln I_Y$ to $\mathcal{O}(s)$ (subscripts in parentheses standing for order in $s$) gives

$$ \frac{1}{s} \ln I_Y = -\frac{1}{2} \ln(\det 2\pi Q)_{(1)} + \frac{1}{\sqrt{2\pi r^0}} \int D\eta \int dy [g_{(1)}^0(y, \eta) + g_{(0)}^0(y, \eta) \ln g_{(0)}^1(y, \eta)]. \quad (B44) $$

We used the fact that at order 0 terms canceled, and the identity $\int D\eta \int dy g^0(y, \eta) = \sqrt{2\pi r^0} + \mathcal{O}(s)$. But

$$ \begin{aligned} \frac{1}{\sqrt{2\pi r^0}} \int D\eta \int dy g_{(1)}^0(y, \eta) &= \lim_{s \to 0} \frac{1}{\sqrt{2\pi r^0}} \partial_s \left( \int D\eta \int dy g^0(y, \eta) \right) \\ &= \lim_{s \to 0} \frac{1}{\sqrt{2\pi r^0}} \partial_s \sqrt{\frac{2\pi}{\hat{r}^0}} \\ &= \frac{-\beta m^2}{2r^0(r + (\beta - 1)Q - \beta q)}, \end{aligned} \quad (B45) $$

thus

$$ \begin{aligned} \frac{1}{s} \ln I_Y = & -\frac{1}{2} \frac{\beta q}{r + (\beta - 1)Q - \beta q} - \frac{1}{2} \ln(r + (\beta - 1)Q - \beta q) - \frac{1}{2}(\beta - 1)\ln(r - Q) \\ & + \frac{1}{\sqrt{2\pi r^0}} \int dy \int D\eta g_{(0)}^0(y, \eta) \ln g_{(0)}^1(y, \eta). \end{aligned} \quad (B46) $$

It's actually possible to proceed to Gaussian changes of variables in the last term so as to exactly cancel the first three contributions in (B46). To do this

$$ h \to \sqrt{r-Qh} + (r-Q)(\sqrt{\tilde{q}-\tilde{Q}}\zeta + \sqrt{-\tilde{q}\eta}) \quad (B47) $$

$$ \zeta \to \frac{1}{\sqrt{1 - \beta(r - Q)(\tilde{q} - \tilde{Q})}} \zeta - \frac{\beta \sqrt{-\tilde{q}(\tilde{q} - \tilde{Q})(r - Q)}}{1 - \beta(r - Q)(\tilde{q} - \tilde{Q})\eta}, \quad (B48) $$

(we used the determinant relations (B29)-(B31)) allowing to rewrite the last term in (B46) as

$$ \begin{aligned} \frac{1}{\sqrt{2\pi r^0}} \int dy \int D\eta g_{(0)}^0(y, \eta) \ln g_{(0)}^1(y, \eta) = & \frac{\beta}{2} \ln(r - Q) - \frac{1}{2} \ln(1 - \beta(r - Q)(\tilde{q} - \tilde{Q})) \\ & + \int \frac{dy}{\sqrt{2\pi r^0}} \int D\eta g_{(0)}^0(y, \eta) \ln \left( 1 + e^{\phi} \int D\zeta \left( \int dh P_{\text{out}}(y|\ast) \right)^{\beta} \right) \\ & + \frac{1}{2} \left( -\beta(r - Q)\tilde{q} + \frac{\beta^2(-\tilde{q}(\tilde{q} - \tilde{Q})(r - Q)^2)}{1 - \beta(r - Q)(\tilde{q} - \tilde{Q})} \right) \int D\eta \eta^2 \int \frac{dy}{\sqrt{2\pi r^0}} g_{(0)}^0(y, \eta), \end{aligned} \quad (B49) $$

with

$$ * = \sqrt{r-Qh} + (r-Q) \left( \sqrt{\frac{\tilde{q}-\tilde{Q}}{1-\beta(r-Q)(\tilde{q}-\tilde{Q})}} \zeta + \frac{\sqrt{-\tilde{q}}}{1-\beta(r-Q)(\tilde{q}-\tilde{Q})} \eta \right). \quad (B50) $$

It is straightforward to see

$$ \int D\eta \eta^2 \int \frac{dy}{\sqrt{2\pi r^0}} g_{(0)}^0(y, \eta) = \frac{\hat{r}^0 \tilde{q} - \tilde{m}^2}{\hat{r}^0 \tilde{q}}, \quad (B51) $$

so the last term in (B49) is

$$ \begin{aligned} & \frac{1}{2} \left( -\beta(r - Q)\tilde{q} + \frac{\beta^2(-\tilde{q}(\tilde{q} - \tilde{Q})(r - Q)^2)}{1 - \beta(r - Q)(\tilde{q} - \tilde{Q})} \right) \int D\eta \eta^2 \int \frac{dy}{\sqrt{2\pi r^0}} g_{(0)}^0(y, \eta) \\ &= -\frac{\beta}{2} \frac{\hat{r}^0 \tilde{q} - \tilde{m}^2}{\hat{r}^0 (\tilde{r} + (\beta - 1)\tilde{Q} - \beta \tilde{q})} \\ &= \frac{1}{2} \frac{\beta q}{r + (\beta - 1)\tilde{Q} - \beta q}. \end{aligned} \quad (B52) $$
Similarly the first terms in (B49) are

$$ \begin{aligned} & \frac{\beta}{2}\ln(r-Q) - \frac{1}{2}\ln(1-\beta(r-Q)(\tilde{q}-\tilde{Q})) = -\frac{\beta-1}{2}\ln(\tilde{r}-\tilde{Q}) - \frac{1}{2}\ln(\tilde{r} + (\beta-1)\tilde{Q} - \beta\tilde{q}) \\ & = \frac{1}{2}\ln(r + (\beta-1)Q - \beta q) + \frac{1}{2}(\beta-1)\ln(r-Q). \end{aligned} \quad (B53) $$

We again used the determinant identity (B29)-(B31) in the last line. Then tilde quantities in the $s=0$ limit can be accordingly be replaced by their expressions (B22)-(B26)

$$ \lim_{s \to 0} \tilde{r}^0 - \frac{\tilde{m}^2}{\tilde{q}} = \frac{q}{qr^0 - m^2} \quad (B54) $$

$$ \lim_{s \to 0} \frac{\tilde{m}}{\sqrt{-\tilde{q}}} = \sqrt{\frac{m^2}{r^0(qr^0 - m^2)}} \quad (B55) $$

$$ \lim_{s \to 0} \sqrt{\frac{\tilde{q} - \tilde{Q}}{1 - \beta(r - Q)(\tilde{q} - \tilde{Q})}} = \frac{\sqrt{Q - q}}{r - Q} \quad (B56) $$

$$ \lim_{s \to 0} \frac{\sqrt{-\tilde{q}}}{1 - \beta(r - Q)(\tilde{q} - \tilde{Q})} = \sqrt{\frac{qr^0 - m^2}{r^0(r - Q)^2}} \quad (B57) $$

Ultimately some changes of variables can be used to bring $g_{(0)}^0$ to a more compact form

$$ h \to \sqrt{\frac{qr^0 - m^2}{q}} h^0 + \sqrt{\frac{m^2(qr^0 - m^2)}{qr^0}}, \quad \eta \to \sqrt{\frac{qr^0}{qr^0 - m^2}} \eta. \quad (B58) $$

Finally

$$ \lim_{s \to 0} \frac{1}{s} I_Y = \int D\eta \int dy I_Y^0(y, \eta) \ln I_Y^1(y, \eta), \quad (B59) $$

with

$$ I_Y^0(y, \eta) = \int Dh^0 \overline{P_{\text{out}}}(y) \left| \sqrt{\frac{qr^0 - m^2}{q}} h^0 + \sqrt{\frac{m^2}{q}} \eta \right|, \quad (B60) $$

$$ I_Y^1(y, \eta) = 1 + e^{\phi} \int D\zeta \left( \int dh P_{\text{out}}(y | \sqrt{r-Q}h + \sqrt{Q-q}\zeta + \sqrt{q}\eta) \right)^{\beta}. \quad (B61) $$

Replica symmetric free entropy for GLM Putting everything together the replica free entropy (B5) reads

$$ \Phi_{\text{RS}} = \underset{\tilde{m}, \tilde{r}, \tilde{q}, \tilde{Q}, r, q, Q}{\text{extr}} \left\{ -\beta m \tilde{m} + \frac{\beta}{2} r \tilde{r} - \frac{\beta(\beta-1)}{2} Q \tilde{Q} + \frac{\beta^2}{2} q \tilde{q} + \int D\xi I_X^0(\xi) \ln I_X^1(\xi) \right. \\ \left. + \alpha \int D\eta \int dy I_Y^0(y, \eta) \ln I_Y^1(y, \eta) \right\} \quad (B62) $$

$$ r^0 = \int dx^0 \overline{P_X}(x^0)(x^0)^2 \quad (B63) $$

$$ I_X^0(\xi) = \int dx^0 \overline{P_X}(x^0) e^{-\frac{\tilde{m}^2}{2\tilde{q}}(x^0)^2 + \frac{\tilde{m}^2}{\sqrt{\tilde{q}}} \xi x^0} \quad (B64) $$

$$ I_X^1(\xi) = \int D\lambda \left[ \int dx P_X(x) e^{-\frac{\tilde{r}+\tilde{Q}}{2}x^2 + (\sqrt{\tilde{Q}-\tilde{q}}\lambda + \sqrt{\tilde{q}}\xi)x} \right]^\beta \quad (B65) $$

$$ I_Y^0(y, \eta) = \int Dh^0 \overline{P_{\text{out}}}(y) \left| \sqrt{\frac{qr^0 - m^2}{q}} h^0 + \sqrt{\frac{m^2}{q}} \eta \right| \quad (B66) $$

$$ I_Y^1(y, \eta) = 1 + e^{\phi} \int D\zeta \left( \int dh P_{\text{out}}(y | \sqrt{r-Q}h + \sqrt{Q-q}\zeta + \sqrt{q}\eta) \right)^{\beta} \quad (B67) $$
Similarly the first terms in (B49) are

$$ 
\begin{aligned}
& \frac{\beta}{2}\ln(r-Q) - \frac{1}{2}\ln(1-\beta(r-Q)(\tilde{q}-\tilde{Q})) = -\frac{\beta-1}{2}\ln(\tilde{r}-\tilde{Q}) - \frac{1}{2}\ln(\tilde{r}+(\beta-1)\tilde{Q}-\beta\tilde{q}) \\
& = \frac{1}{2}\ln(r+(\beta-1)Q-\beta q) + \frac{1}{2}(\beta-1)\ln(r-Q).
\end{aligned}
\quad \text{(B53)}
$$

We again used the determinant identity (B29)-(B31) in the last line. Then tilde quantities in the $s=0$ limit can be accordingly be replaced by their expressions (B22)-(B26)

$$ \lim_{s \to 0} \tilde{r}^0 - \frac{\tilde{m}^2}{\tilde{q}} = \frac{q}{qr^0 - m^2} \quad \text{(B54)} $$

$$ \lim_{s \to 0} \frac{\tilde{m}}{\sqrt{-\tilde{q}}} = \sqrt{\frac{m^2}{r^0(qr^0 - m^2)}} \quad \text{(B55)} $$

$$ \lim_{s \to 0} \sqrt{\frac{\tilde{q} - \tilde{Q}}{1 - \beta(r - Q)(\tilde{q} - \tilde{Q})}} = \frac{\sqrt{Q - q}}{r - Q} \quad \text{(B56)} $$

$$ \lim_{s \to 0} \frac{\sqrt{-\tilde{q}}}{1 - \beta(r - Q)(\tilde{q} - \tilde{Q})} = \sqrt{\frac{qr^0 - m^2}{r^0(r - Q)^2}} \quad \text{(B57)} $$

Ultimately some changes of variables can be used to bring $g_{(0)}^0$ to a more compact form

$$ h \to \sqrt{\frac{qr^0 - m^2}{q}} h^0 + \sqrt{\frac{m^2(qr^0 - m^2)}{qr^0}}, \quad \eta \to \sqrt{\frac{qr^0}{qr^0 - m^2}} \eta. \quad \text{(B58)} $$

Finally

$$ \lim_{s \to 0} \frac{1}{s} I_Y = \int D\eta \int dy I_Y^0(y, \eta) \ln I_Y^1(y, \eta), \quad \text{(B59)} $$

with

$$ I_Y^0(y, \eta) = \int Dh^0 \overline{P_{\text{out}}}(y) \left| \sqrt{\frac{qr^0 - m^2}{q}} h^0 + \sqrt{\frac{m^2}{q}} \eta \right|, \quad \text{(B60)} $$

$$ I_Y^1(y, \eta) = 1 + e^{\phi} \int D\zeta \left( \int dh P_{\text{out}}(y | \sqrt{r-Q}h + \sqrt{Q-q}\zeta + \sqrt{q}\eta) \right)^{\beta}. \quad \text{(B61)} $$

Replica symmetric free entropy for GLM Putting everything together the replica free entropy (B5) reads

$$ \Phi_{\text{RS}} = \underset{\tilde{m}, \tilde{r}, \tilde{q}, \tilde{Q}, r, q, Q}{\text{extr}} \left\{ -\beta m \tilde{m} + \frac{\beta}{2} r \tilde{r} - \frac{\beta(\beta-1)}{2} Q \tilde{Q} + \frac{\beta^2}{2} q \tilde{q} + \int D\xi I_X^0(\xi) \ln I_X^1(\xi) \right. \\ \left. + \alpha \int D\eta \int dy I_Y^0(y, \eta) \ln I_Y^1(y, \eta) \right\} \quad \text{(B62)} $$

$$ r^0 = \int dx^0 \overline{P_X}(x^0)(x^0)^2 \quad \text{(B63)} $$

$$ I_X^0(\xi) = \int dx^0 \overline{P_X}(x^0) e^{-\frac{\tilde{m}^2}{2\tilde{q}}(x^0)^2 + \frac{\tilde{m}^2}{\sqrt{\tilde{q}}\xi}x^0} \quad \text{(B64)} $$

$$ I_X^1(\xi) = \int D\lambda \left[ \int dx P_X(x) e^{-\frac{\tilde{r}+\tilde{Q}}{2}x^2 + (\sqrt{\tilde{Q}-\tilde{q}}\lambda + \sqrt{\tilde{q}}\xi)x} \right]^\beta \quad \text{(B65)} $$

$$ I_Y^0(y, \eta) = \int Dh^0 \overline{P_{\text{out}}}(y) \left| \sqrt{\frac{qr^0 - m^2}{q}} h^0 + \sqrt{\frac{m^2}{q}} \eta \right| \quad \text{(B66)} $$

$$ I_Y^1(y, \eta) = 1 + e^{\phi} \int D\zeta \left( \int dh P_{\text{out}}(y | \sqrt{r-Q}h + \sqrt{Q-q}\zeta + \sqrt{q}\eta) \right)^{\beta} \quad \text{(B67)} $$
Appendix C: Specialization to perceptron

The Bayes-optimal teacher-student setting for the perceptron is defined by the following measures (see section II in the main text)

$$ \overline{P_X}(x) = P_X(x) = \frac{1}{\sqrt{2\pi}} e^{-\frac{1}{2}x^2} \qquad (C1) $$

$$ \overline{P_{\text{out}}}(y|h) = P_{\text{out}}(y|h) = \delta(y - \text{sgn}(h)) \qquad (C2) $$

1. Replica symmetric free entropy for the perceptron

We shall simply plug into the generic GLM (B62) expressions the particular priors and posteriors for the perceptron (C1)-(C2). First,

$$ I_X^0(\xi) = \int \frac{1}{\sqrt{2\pi}} dx^0 e^{-\frac{1}{2}\left(1+\frac{\hat{m}^2}{\hat{q}}\right)(x^0)^2+\frac{\hat{m}^2}{\sqrt{\hat{q}}}\xi x^0} \qquad (C3) $$

$$ = \frac{1}{\sqrt{2\pi(1 + \frac{\hat{m}^2}{\hat{q}})}} e^{\frac{1}{2} \frac{\hat{m}^2}{\hat{q} + \hat{m}^2} \xi^2}, \qquad (C4) $$

while two straightforward Gaussian integrals yield

$$ I_X^1(\xi) = \int D\lambda \left[ \int \frac{1}{\sqrt{2\pi}} dx P_X(x) e^{-\frac{1}{2}(\hat{r}+\hat{Q})x^2 + \left(\sqrt{\hat{Q}-\hat{q}}\lambda + \sqrt{\hat{q}}\xi\right)x} \right]^\beta \qquad (C5) $$

$$ = \int d\lambda \frac{1}{(1 + \hat{r} + \hat{Q})^{\frac{\beta}{2}}} e^{-\frac{1}{2}\left(1 - \beta \frac{\hat{Q} - \hat{q}}{1 + \hat{r} + \hat{Q}}\right)\lambda^2 + \beta \frac{\sqrt{\hat{q}(\hat{Q} - \hat{q})}}{1 + \hat{r} + \hat{Q}}\xi\lambda + \frac{\beta}{2}\frac{\hat{q}}{1 + \hat{r} + \hat{Q}}\xi^2} \qquad (C6) $$

$$ = (1 + \hat{r} + \hat{Q})^{\frac{1-\beta}{2}} (1 + \hat{r} - (\beta - 1)\hat{Q} + \beta\hat{q})^{-\frac{1}{2}} e^{\frac{\beta\hat{q}}{2(1 + \hat{r} - (\beta - 1)\hat{Q} + \beta\hat{q})}} \xi^2. \qquad (C7) $$

Thus

$$ \int D\xi I_X^0(\xi) \ln I_X^1(\xi) = -\frac{\beta - 1}{2} \ln(1 + \hat{r} + \hat{Q}) - \frac{1}{2} \ln(1 + \hat{r} - (\beta - 1)\hat{Q} + \beta\hat{q}) + \frac{\beta}{2} \frac{\hat{q} + \hat{m}^2}{1 + \hat{r} - (\beta - 1)\hat{Q} + \beta\hat{q}} \qquad (C8) $$

Now defining the special function $H(x) = \frac{1}{\sqrt{2\pi}} \int_x^\infty Dt$

$$ I_Y^0(y, \eta) = \int Dh^0 \delta(y - \operatorname{sgn}\left(\sqrt{\frac{q-m^2}{q}}h^0 + \sqrt{\frac{m^2}{q}}\eta\right)) = H\left(-y\sqrt{\frac{m^2}{q-m^2}\eta}\right). \qquad (C9) $$

In writing so we took into account the fact that $y = \pm 1$, which implies also to replace the integral over $y$ in the energetic part by a sum over $\{\pm 1\}$. Furthermore

$$ I_Y^1(y, \eta) = 1 + e^{\phi} \int D\zeta H \left( -\frac{y}{\sqrt{r-Q}} \left( \sqrt{Q-q\zeta} + \sqrt{q\eta} \right) \right)^{\beta}, \qquad (C10) $$

from which it follows that the energetic term in equation (B62) reads

$$ \alpha \int D\eta \sum_{y=\pm 1} I_Y^0(y, \eta) \ln I_Y^1(y, \eta) = 2\alpha \int D\eta H \left( -\sqrt{\frac{m^2}{q-m^2}\eta} \right) \ln \left[ 1 + e^{\phi} \int D\zeta H \left( -\frac{1}{\sqrt{r-Q}} \left( \sqrt{Q-q\zeta} + \sqrt{q\eta} \right) \right)^{\beta} \right]. \qquad (C11) $$
Appendix C: Specialization to perceptron

The Bayes-optimal teacher-student setting for the perceptron is defined by the following measures (see section II in the main text)

$$ \overline{P_X}(x) = P_X(x) = \frac{1}{\sqrt{2\pi}} e^{-\frac{1}{2}x^2} \qquad (C1) $$

$$ \overline{P_{\text{out}}}(y|h) = P_{\text{out}}(y|h) = \delta(y - \text{sgn}(h)) \qquad (C2) $$

1. Replica symmetric free entropy for the perceptron

We shall simply plug into the generic GLM (B62) expressions the particular priors and posteriors for the perceptron (C1)-(C2). First,

$$ I_X^0(\xi) = \int \frac{1}{\sqrt{2\pi}} dx^0 e^{-\frac{1}{2}\left(1+\frac{\hat{m}^2}{\hat{q}}\right)(x^0)^2+\frac{\hat{m}^2}{\sqrt{\hat{q}}}\xi x^0} \qquad (C3) $$

$$ = \frac{1}{\sqrt{2\pi(1 + \frac{\hat{m}^2}{\hat{q}})}} e^{\frac{1}{2} \frac{\hat{m}^2}{\hat{q} + \hat{m}^2} \xi^2}, \qquad (C4) $$

while two straightforward Gaussian integrals yield

$$ I_X^1(\xi) = \int D\lambda \left[ \int \frac{1}{\sqrt{2\pi}} dx P_X(x) e^{-\frac{1}{2}(\hat{r}+\hat{Q})x^2 + \left(\sqrt{\hat{Q}-\hat{q}}\lambda + \sqrt{\hat{q}}\xi\right)x} \right]^\beta \qquad (C5) $$

$$ = \int d\lambda \frac{1}{(1 + \hat{r} + \hat{Q})^{\frac{\beta}{2}}} e^{-\frac{1}{2}\left(1 - \beta \frac{\hat{Q} - \hat{q}}{1 + \hat{r} + \hat{Q}}\right)\lambda^2 + \beta \frac{\sqrt{\hat{q}(\hat{Q} - \hat{q})}}{1 + \hat{r} + \hat{Q}}\xi\lambda + \frac{\beta}{2}\frac{\hat{q}}{1 + \hat{r} + \hat{Q}}\xi^2} \qquad (C6) $$

$$ = (1 + \hat{r} + \hat{Q})^{\frac{1-\beta}{2}} (1 + \hat{r} - (\beta - 1)\hat{Q} + \beta\hat{q})^{-\frac{1}{2}} e^{\frac{\beta\hat{q}}{2(1 + \hat{r} - (\beta - 1)\hat{Q} + \beta\hat{q})}} \xi^2. \qquad (C7) $$

Thus

$$ \int D\xi I_X^0(\xi) \ln I_X^1(\xi) = -\frac{\beta - 1}{2} \ln(1 + \hat{r} + \hat{Q}) - \frac{1}{2} \ln(1 + \hat{r} - (\beta - 1)\hat{Q} + \beta\hat{q}) + \frac{\beta}{2} \frac{\hat{q} + \hat{m}^2}{1 + \hat{r} - (\beta - 1)\hat{Q} + \beta\hat{q}} \qquad (C8) $$

Now defining the special function $H(x) \equiv \frac{1}{\sqrt{2\pi}} \int_x^\infty Dt$

$$ I_Y^0(y, \eta) = \int Dh^0 \delta(y - \operatorname{sgn}(\sqrt{\frac{q-m^2}{q}}h^0 + \sqrt{\frac{m^2}{q}}\eta)) = H\left(-y\sqrt{\frac{m^2}{q-m^2}\eta}\right). \qquad (C9) $$

In writing so we took into account the fact that $y = \pm 1$, which implies also to replace the integral over $y$ in the energetic part by a sum over $\{\pm 1\}$. Furthermore

$$ I_Y^1(y, \eta) = 1 + e^{\phi} \int D\zeta H\left(-\frac{y}{\sqrt{r-Q}}(\sqrt{Q-q}\zeta + \sqrt{q}\eta)\right)^{\beta}, \qquad (C10) $$

from which it follows that the energetic term in equation (B62) reads

$$ \alpha \int D\eta \sum_{y=\pm 1} I_Y^0(y, \eta) \ln I_Y^1(y, \eta) = 2\alpha \int D\eta H\left(-\sqrt{\frac{m^2}{q-m^2}\eta}\right) \ln\left[1 + e^{\phi} \int D\zeta H\left(-\frac{1}{\sqrt{r-Q}}(\sqrt{Q-q}\zeta + \sqrt{q}\eta)\right)^{\beta}\right]. \qquad (C11) $$
The $y = 1$ and $y = -1$ being equal modulo a double change of variable $\zeta, \eta \to -\zeta, -\eta$ whence the factor 2. Thus for the perceptron

$$ \Phi_{RS} = \underset{\hat{m}, \hat{r}, \hat{q}, \hat{Q}, r, q, Q}{\operatorname{extr}} \left\{ \frac{\beta}{2} r \hat{r} - \beta m \hat{m} - \frac{\beta(\beta-1)}{2} Q \hat{Q} + \frac{\beta^2}{2} q \hat{q} - \frac{\beta-1}{2} \ln(1+\hat{r}+\hat{Q}) \right. \\ - \frac{1}{2} \ln(1+\hat{r}-(\beta-1)\hat{Q}+\beta\hat{q}) + \frac{\beta}{2} \frac{\hat{q}+\hat{m}^2}{1+\hat{r}-(\beta-1)\hat{Q}+\beta\hat{q}} \\ \left. + 2\alpha \int D\eta H \left( -\sqrt{\frac{m^2}{q-m^2}\eta} \right) \ln \left[ 1 + e^{\phi} \int D\zeta H \left( -\frac{1}{\sqrt{r-Q}}(\sqrt{Q-q\zeta}+\sqrt{q\eta}) \right)^{\beta} \right] \right\} \quad (C12) $$

## 2. Saddle-point equations for the perceptron

The canonical way of carrying out the extremization in equation (C12) is to take the saddle-point equations (zero-gradient conditions) and to solve them. The saddle point equations associated to $\Phi(\beta, \phi)$ (equation (C12)) read

$$ m^t = \frac{\hat{m}^t}{1 + \hat{r}^t - (\beta - 1)\hat{Q}^t + \beta\hat{q}^t} \quad (C13) $$

$$ q^t = \frac{\hat{q}^t + (\hat{m}^t)^2}{(1 + \hat{r}^t - (\beta - 1)\hat{Q}^t + \beta\hat{q}^t)^2} \quad (C14) $$

$$ Q^t = \frac{\hat{q}^t + (\hat{m}^t)^2}{(1 + \hat{r}^t - (\beta - 1)\hat{Q}^t + \beta\hat{q}^t)^2} + \frac{1}{\beta} \frac{1}{1 + \hat{r}^t - (\beta - 1)\hat{Q}^t + \beta\hat{q}^t} - \frac{1}{\beta} \frac{1}{1 + \hat{r}^t + \hat{Q}^t} \quad (C15) $$

$$ r^t = \frac{\hat{q}^t + (\hat{m}^t)^2}{(1 + \hat{r}^t - (\beta - 1)\hat{Q}^t + \beta\hat{q}^t)^2} + \frac{1}{\beta} \frac{1}{1 + \hat{r}^t - (\beta - 1)\hat{Q}^t + \beta\hat{q}^t} + \frac{\beta - 1}{\beta} \frac{1}{1 + \hat{r}^t + \hat{Q}^t} \quad (C16) $$

$$ X^t = - \frac{1}{\sqrt{r^t - Q^t}} (\sqrt{Q^t - q^t}\zeta + \sqrt{q^t}\eta) \quad (C17) $$

$$ \hat{q}^{t+1} = 2\alpha \int D\eta H \left( -\sqrt{\frac{(m^t)^2}{q^t - (m^t)^2}\eta} \right) \frac{e^{2\phi}}{2\pi(r^t - Q^t)} \left[ \frac{\int D\zeta H(X^t)^{\beta-1} e^{-\frac{1}{2}(X^t)^2}}{1 + e^{\phi} \int D\zeta H(X^t)^{\beta}} \right]^2 \quad (C18) $$

$$ \hat{m}^{t+1} = 2\alpha \int d\eta \frac{1}{(2\pi)^{\frac{3}{2}}\sqrt{r-Q}} \frac{1}{\sqrt{1-\frac{(m^t)^2}{q^t}}} e^{-\frac{1}{2}\frac{\eta^2}{1-(m^t)^2 q^t}} \frac{e^{\phi} \int D\zeta H(X^t)^{\beta-1} e^{-\frac{1}{2}(X^t)^2}}{1+e^{\phi} \int D\zeta H(X^t)^{\beta}} \quad (C19) $$

$$ \hat{Q}^{t+1} = \frac{2\alpha}{r^t - Q^t} \int D\eta H \left( -\sqrt{\frac{(m^t)^2}{q^t - (m^t)^2}\eta} \right) \frac{\int D\zeta H(X^t)^{\beta-2} e^{-(X^t)^2}}{1 + e^{\phi} \int D\zeta H(X^t)^{\beta}} \frac{1}{\sqrt{2\pi}} \quad (C20) $$

$$ \hat{r}^{t+1} = -\frac{2\alpha}{r^t - Q^t} \int D\eta H \left( -\sqrt{\frac{(m^t)^2}{q^t - (m^t)^2}\eta} \right) \frac{\int D\zeta H(X^t)^{\beta-1} X^t e^{-\frac{1}{2}(X^t)^2}}{1 + e^{\phi} \int D\zeta H(X^t)^{\beta}} \frac{1}{\sqrt{2\pi}} \quad (C21) $$

In practice, equations (C13)-(C21) are iterated until convergence. The time indices are derived from an independent computation using Approximate Message Passing ([15], [31]), not shown here. They indicate in which order the equations ought to be iterated in order to converge. Remark that the update schedule very simply consists in updating in parallel all order parameters $m, q, Q, r$ then all auxiliary (hatted) order parameters $\hat{m}, \hat{q}, \hat{Q}, r$. After convergence the order parameters can be used in equation (8) to evaluate the free entropy $\Phi$ and subsequently evaluate the complexity $\Sigma(n, v)$ by inverting the Legendre transform (6).

We present for illustration in Fig. 5 the complexity curves for $\alpha = 10$ for some budgets $n$, and refer the interested reader to Fig. 1 for the same plot at pool size $\alpha = 3$. As the budget $n$ is increased, smaller values of Gardner volumes become accessible, provided sufficiently informative subset are found. A detailed discussion can further be found in section IV in the main text.
The $y = 1$ and $y = -1$ being equal modulo a double change of variable $\zeta, \eta \to -\zeta, -\eta$ whence the factor 2. Thus for the perceptron

$$ \Phi_{RS} = \underset{\hat{m}, \hat{r}, \hat{q}, \hat{Q}, r, q, Q}{\text{extr}} \left\{ \frac{\beta}{2} r\hat{r} - \beta m\hat{m} - \frac{\beta(\beta-1)}{2} Q\hat{Q} + \frac{\beta^2}{2} q\hat{q} - \frac{\beta-1}{2} \ln(1+r\hat{r}+\hat{Q}) \right. \\ \left. - \frac{1}{2} \ln(1+r - (\beta-1)\hat{Q} + \beta\hat{q}) + \frac{\beta}{2} \frac{\hat{q} + \hat{m}^2}{1+r - (\beta-1)\hat{Q} + \beta\hat{q}} \right. \\ \left. + 2\alpha \int D\eta H \left( -\sqrt{\frac{m^2}{q-m^2}\eta} \right) \ln \left[ 1 + e^{\phi} \int D\zeta H \left( -\frac{1}{\sqrt{r-Q}}(\sqrt{Q-q\zeta} + \sqrt{q\eta}) \right)^{\beta} \right] \right\} \quad (C12) $$

## 2. Saddle-point equations for the perceptron

The canonical way of carrying out the extremization in equation (C12) is to take the saddle-point equations (zero-gradient conditions) and to solve them. The saddle point equations associated to $\Phi(\beta, \phi)$ (equation (C12)) read

$$ m^t = \frac{\hat{m}^t}{1 + \hat{r}^t - (\beta - 1)\hat{Q}^t + \beta\hat{q}^t} \quad (C13) $$

$$ q^t = \frac{\hat{q}^t + (\hat{m}^t)^2}{(1 + \hat{r}^t - (\beta - 1)\hat{Q}^t + \beta\hat{q}^t)^2} \quad (C14) $$

$$ Q^t = \frac{\hat{q}^t + (\hat{m}^t)^2}{(1 + \hat{r}^t - (\beta - 1)\hat{Q}^t + \beta\hat{q}^t)^2} + \frac{1}{\beta} \frac{1}{1 + \hat{r}^t - (\beta - 1)\hat{Q}^t + \beta\hat{q}^t} - \frac{1}{\beta} \frac{1}{1 + \hat{r}^t + \hat{Q}^t} \quad (C15) $$

$$ r^t = \frac{\hat{q}^t + (\hat{m}^t)^2}{(1 + \hat{r}^t - (\beta - 1)\hat{Q}^t + \beta\hat{q}^t)^2} + \frac{1}{\beta} \frac{1}{1 + \hat{r}^t - (\beta - 1)\hat{Q}^t + \beta\hat{q}^t} + \frac{\beta - 1}{\beta} \frac{1}{1 + \hat{r}^t + \hat{Q}^t} \quad (C16) $$

$$ X^t = - \frac{1}{\sqrt{r^t - Q^t}} (\sqrt{Q^t - q^t}\zeta + \sqrt{q^t}\eta) \quad (C17) $$

$$ \hat{q}^{t+1} = 2\alpha \int D\eta H \left( -\sqrt{\frac{(m^t)^2}{q^t - (m^t)^2}\eta} \right) \frac{e^{2\phi}}{2\pi(r^t - Q^t)} \left[ \frac{\int D\zeta H(X^t)^{\beta-1} e^{-\frac{1}{2}(X^t)^2}}{1 + e^{\phi} \int D\zeta H(X^t)^{\beta}} \right]^2 \quad (C18) $$

$$ \hat{m}^{t+1} = 2\alpha \int d\eta \frac{1}{(2\pi)^{\frac{3}{2}}\sqrt{r-Q}} \frac{1}{\sqrt{1-\frac{(m^t)^2}{q^t}}} e^{-\frac{1}{2}\frac{\eta^2}{1-\frac{(m^t)^2}{q^t}}} \frac{e^{\phi} \int D\zeta H(X^t)^{\beta-1} e^{-\frac{1}{2}(X^t)^2}}{1+e^{\phi} \int D\zeta H(X^t)^{\beta}} \quad (C19) $$

$$ \hat{Q}^{t+1} = \frac{2\alpha}{r^t - Q^t} \int D\eta H \left( -\sqrt{\frac{(m^t)^2}{q^t - (m^t)^2}\eta} \right) \frac{\int D\zeta H(X^t)^{\beta-2} e^{-(X^t)^2}}{1 + e^{\phi} \int D\zeta H(X^t)^{\beta}} \frac{1}{\sqrt{2\pi}} \quad (C20) $$

$$ \hat{r}^{t+1} = -\frac{2\alpha}{r^t - Q^t} \int D\eta H \left( -\sqrt{\frac{(m^t)^2}{q^t - (m^t)^2}\eta} \right) \frac{\int D\zeta H(X^t)^{\beta-1} X^t e^{-\frac{1}{2}(X^t)^2}}{1 + e^{\phi} \int D\zeta H(X^t)^{\beta}} \frac{1}{\sqrt{2\pi}} \quad (C21) $$

In practice, equations (C13)-(C21) are iterated until convergence. The time indices are derived from an independent computation using Approximate Message Passing ([15], [31]), not shown here. They indicate in which order the equations ought to be iterated in order to converge. Remark that the update schedule very simply consists in updating in parallel all order parameters $m, q, Q, r$ then all auxiliary (hatted) order parameters $\hat{m}, \hat{q}, \hat{Q}, r$. After convergence the order parameters can be used in equation (8) to evaluate the free entropy $\Phi$ and subsequently evaluate the complexity $\Sigma(n, v)$ by inverting the Legendre transform (6).

We present for illustration in Fig. 5 the complexity curves for $\alpha = 10$ for some budgets $n$, and refer the interested reader to Fig. 1 for the same plot at pool size $\alpha = 3$. As the budget $n$ is increased, smaller values of Gardner volumes become accessible, provided sufficiently informative subset are found. A detailed discussion can further be found in section IV in the main text.
<figure><img src="image_6.png" /><figcaption>FIG. 5. Complexity $\Sigma(n, v)$ as a function of the Gardner volume $v$ for budgets $n \le 2$ at pool size $\alpha = 10$ extracted from the large deviation computations, see also Fig. 1 for the same curves at different pool size. For any budget $n$ the maximum complexity corresponds to the volume reached by random subset selection (passive learning), see discussion in section IV in the main text. We invite the reader to notice that the qualitative allure of the complexity curves remains significantly unchanged as the pool size $\alpha$ is varied (see Fig. 1 for $\alpha = 3$.)</figcaption></figure>

## Appendix D: Optimal generalization error for the large deviation perceptron

We derive here the expression for the optimal generalization error $\epsilon_g$ (in the Bayesian sense) associated to a subset of volume $v$ and of budget $n$ as a function of the perceptron order parameters $m$ and $q$, see appendix B and C. The Bayesian $\epsilon_g$ was introduced for example in [33] and, unlike the test error yielded by training the perceptron on some loss, is independent of the training procedure and thus may serve as a nice measure of informativeness for subsets. For the usual perceptron model, it is known that the optimal generalization error is achieved when the student classification is performed by averaging the predicted label over the student measure $P_X(\cdot)P_{\text{out}}(Y|\mathbf{F})$ and taking the sign thereof. Note that the average predicted label is but the output magnetization $\mathbf{m}_{\text{out}}$ discussed in section V of the main text. Transposition to the large deviation setting, which allows to fix the budget $n$ and the volume $v$, is straightforward provided one averages over the large deviation measure (A2). By definition the test error is the probability that a new sample $\mathbf{F}_{\text{new}} \stackrel{d}{=} \mathcal{N}(0, 1)$ is correctly classified by the student according to the output magnetization $\mathbb{E}_{\mathbf{x},\phi}^{\beta,\phi}\text{sgn}(\mathbf{x} \cdot \mathbf{F}_{\text{new}})$

$$1 - \epsilon_g = \mathbb{E}_{\mathbf{x}^0, Y, \mathbf{F}, \mathbf{F}_{\text{new}}} \Theta[\text{sgn}(\mathbf{x}^0 \cdot \mathbf{F}_{\text{new}}) \mathbb{E}_{\mathbf{x},\phi}^{\beta,\phi} \text{sgn}(\mathbf{x} \cdot \mathbf{F}_{\text{new}})], \quad (\text{D1})$$

where $\mathbb{E}_{\mathbf{x},\phi}^{\beta,\phi}$ denote the average with respect to the large deviation posterior measure (A2) with control parameters $\beta$ and $\phi$. Introducing an integral representation for a Dirac delta and expanding the resulting exponential

$$1 - \epsilon_g = \mathbb{E}_{\mathbf{x}^0, Y, \mathbf{F}_{\text{new}}} \int dv d\hat{v} e^{iv\hat{v}} \Theta[\text{sgn}(\mathbf{x}^0 \cdot \mathbf{F}_{\text{new}})v] \sum_{j=0}^{\infty} \frac{(i\hat{v})^j}{j!} \mathbb{E}_{\mathbf{F}}(\mathbb{E}_{\mathbf{x},\phi}^{\beta,\phi} \text{sgn}(\mathbf{x} \cdot \mathbf{F}_{\text{new}}))^j \quad (\text{D2})$$

$$= \mathbb{E}_{\mathbf{F}_{\text{new}}} \sum_{j=0}^{\infty} \int dv d\hat{v} e^{iv\hat{v}} \frac{(i\hat{v})^j}{j!} \mathbb{E}_{\mathbf{x}^0, Y} \Theta[\text{sgn}(\mathbf{x}^0 \cdot \mathbf{F}_{\text{new}})v] \mathbb{E}_{\mathbf{F}}(\mathbb{E}_{\mathbf{x},\phi}^{\beta,\phi} \text{sgn}(\mathbf{x} \cdot \mathbf{F}_{\text{new}}))^j. \quad (\text{D3})$$

For any fixed $j$, the computation of $\mathbb{E}_{\mathbf{x}^0, Y} \Theta[\text{sgn}(\mathbf{x}^0 \cdot \mathbf{F}_{\text{new}})v] \mathbb{E}_{\mathbf{F}}(\mathbb{E}_{\mathbf{x},\phi}^{\beta,\phi})^j$ is formally very similar to the one detailed in appendix B and follows the same lines. First notice that using the replica trick $\mathbb{E}_{\mathbf{x},\phi}^{\beta,\phi}\text{sgn}(\mathbf{x} \cdot \mathbf{F}_{\text{new}})$ prescribes to
<figure><img src="image_6.png" /><figcaption>FIG. 5. Complexity $\Sigma(n, v)$ as a function of the Gardner volume $v$ for budgets $n \le 2$ at pool size $\alpha = 10$ extracted from the large deviation computations, see also Fig. 1 for the same curves at different pool size. For any budget $n$ the maximum complexity corresponds to the volume reached by random subset selection (passive learning), see discussion in section IV in the main text. We invite the reader to notice that the qualitative allure of the complexity curves remains significantly unchanged as the pool size $\alpha$ is varied (see Fig. 1 for $\alpha = 3$.)</figcaption></figure>

## Appendix D: Optimal generalization error for the large deviation perceptron

We derive here the expression for the optimal generalization error $\epsilon_g$ (in the Bayesian sense) associated to a subset of volume $v$ and of budget $n$ as a function of the perceptron order parameters $m$ and $q$, see appendix B and C. The Bayesian $\epsilon_g$ was introduced for example in [33] and, unlike the test error yielded by training the perceptron on some loss, is independent of the training procedure and thus may serve as a nice measure of informativeness for subsets. For the usual perceptron model, it is known that the optimal generalization error is achieved when the student classification is performed by averaging the predicted label over the student measure $P_X(\cdot)P_{\text{out}}(Y|\mathbf{F})$ and taking the sign thereof. Note that the average predicted label is but the output magnetization $\mathbf{m}_{\text{out}}$ discussed in section V of the main text. Transposition to the large deviation setting, which allows to fix the budget $n$ and the volume $v$, is straightforward provided one averages over the large deviation measure (A2). By definition the test error is the probability that a new sample $\mathbf{F}_{\text{new}} \stackrel{d}{=} \mathcal{N}(0, 1)$ is correctly classified by the student according to the output magnetization $\mathbb{E}_{\mathbf{x}}^{\beta, \phi}\text{sgn}(\mathbf{x} \cdot \mathbf{F}_{\text{new}})$

$$1 - \epsilon_g = \mathbb{E}_{\mathbf{x}^0, Y, \mathbf{F}, \mathbf{F}_{\text{new}}} \Theta[\text{sgn}(\mathbf{x}^0 \cdot \mathbf{F}_{\text{new}}) \mathbb{E}_{\mathbf{x}}^{\beta, \phi} \text{sgn}(\mathbf{x} \cdot \mathbf{F}_{\text{new}})], \quad (\text{D1})$$

where $\mathbb{E}_{\mathbf{x}}^{\beta, \phi}$ denote the average with respect to the large deviation posterior measure (A2) with control parameters $\beta$ and $\phi$. Introducing an integral representation for a Dirac delta and expanding the resulting exponential

$$1 - \epsilon_g = \mathbb{E}_{\mathbf{x}^0, Y, \mathbf{F}_{\text{new}}} \int dv d\hat{v} e^{iv\hat{v}} \Theta[\text{sgn}(\mathbf{x}^0 \cdot \mathbf{F}_{\text{new}})v] \sum_{j=0}^{\infty} \frac{(i\hat{v})^j}{j!} \mathbb{E}_{\mathbf{F}}(\mathbb{E}_{\mathbf{x}}^{\beta, \phi} \text{sgn}(\mathbf{x} \cdot \mathbf{F}_{\text{new}}))^j \quad (\text{D2})$$

$$= \mathbb{E}_{\mathbf{F}_{\text{new}}} \sum_{j=0}^{\infty} \int dv d\hat{v} e^{iv\hat{v}} \frac{(i\hat{v})^j}{j!} \mathbb{E}_{\mathbf{x}^0, Y} \Theta[\text{sgn}(\mathbf{x}^0 \cdot \mathbf{F}_{\text{new}})v] \mathbb{E}_{\mathbf{F}}(\mathbb{E}_{\mathbf{x}}^{\beta, \phi} \text{sgn}(\mathbf{x} \cdot \mathbf{F}_{\text{new}}))^j. \quad (\text{D3})$$

For any fixed $j$, the computation of $\mathbb{E}_{\mathbf{x}^0, Y} \Theta[\text{sgn}(\mathbf{x}^0 \cdot \mathbf{F}_{\text{new}})v] \mathbb{E}_{\mathbf{F}}(\mathbb{E}_{\mathbf{x}}^{\beta, \phi})^j$ is formally very similar to the one detailed in appendix B and follows the same lines. First notice that using the replica trick $\mathbb{E}_{\mathbf{x}}^{\beta, \phi}\text{sgn}(\mathbf{x} \cdot \mathbf{F}_{\text{new}})$ prescribes to
introduce as precedently $\beta$s replicas

$$ \mathbb{E}_{\mathbf{x}}^{\beta, \phi} \operatorname{sgn}(\mathbf{x} \cdot \mathbf{F}_{\text{new}}) = \lim_{s \to 0} \Xi^{s-1} \sum_{\{\sigma_{\mu}\}} e^{\phi \sum_{\mu} S_{\mu}} \left[ \int d\mathbf{x} P_X(\mathbf{x}) \prod_{\mu} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \mathbf{x})^{\sigma_{\mu}} \right]^{\beta-1} \int d\mathbf{x} P_X(\mathbf{x}) \prod_{\mu} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \mathbf{x})^{\sigma_{\mu}} \operatorname{sgn}(\mathbf{x} \cdot \mathbf{F}_{\text{new}}) \quad (\text{D4}) $$

$$ = \lim_{s \to 0} \sum_{\boldsymbol{\sigma}^1, \dots, \boldsymbol{\sigma}^n} \int \prod_{a=1}^{s} \prod_{\alpha=1}^{\beta} dx^{a\alpha} P_X(\mathbf{x}) \prod_{\mu} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \mathbf{x}^{a\alpha})^{\sigma_{\mu}^{a}} e^{\phi \sum_{a,\mu} \sigma_{\mu}^{a}} \operatorname{sgn}(\mathbf{x}^{11} \cdot \mathbf{F}_{\text{new}}). \quad (\text{D5}) $$

From which it follows that

$$ (\mathbb{E}_{\mathbf{x}}^{\beta, \phi} \operatorname{sgn}(\mathbf{x} \cdot \mathbf{F}_{\text{new}}))^j = \lim_{s \to 0} \sum_{1 \le l \le j, 1 \le a \le s} \int \prod_{a=1}^{s} \prod_{l=1}^{j} \prod_{\alpha=1}^{\beta} dx^{a\alpha} P_X(\mathbf{x}^{la\alpha}) \prod_{\mu} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \mathbf{x}^{la\alpha})^{\sigma_{\mu}^{la}} e^{\phi \sum_{l,a,\mu} \sigma_{\mu}^{la}} \prod_{l=1}^{j} \operatorname{sgn}(\mathbf{x}^{l11} \cdot \mathbf{F}_{\text{new}}). \quad (\text{D6}) $$

The net effect is simply to transform the first index $a$ into a double index $(l, a)$, thereby introducing a third level of replication. Pursuing equation (D2),

$$ 1 - \epsilon_g = \lim_{s \to 0} \sum_{j=0}^{\infty} \int dv d\hat{v} e^{iv\hat{v}} \frac{(i\hat{v})^j}{j!} \mathbb{E}_{\mathbf{x}^0, \mathbf{Y}, \mathbf{F}} \sum_{1 \le l \le j, 1 \le a \le s} \int \prod_{a=1}^{s} \prod_{l=1}^{j} \prod_{\alpha=1}^{\beta} dx^{a\alpha} P_X(\mathbf{x}^{la\alpha}) \prod_{\mu} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \mathbf{x}^{la\alpha})^{\sigma_{\mu}^{la}} e^{\phi \sum_{l,a,\mu} \sigma_{\mu}^{la}} \mathbb{E}_{\mathbf{F}_{\text{new}}} \prod_{l=1}^{j} \operatorname{sgn}(\mathbf{x}^{l11} \cdot \mathbf{F}_{\text{new}}) \Theta[\operatorname{sgn}(\mathbf{x}^0 \cdot \mathbf{F}_{\text{new}})v] \quad (\text{D7}) $$

$$ = \lim_{s \to 0} \sum_{j=0}^{\infty} \int dv d\hat{v} e^{iv\hat{v}} \frac{(i\hat{v})^j}{j!} e^{sjN\Phi(\beta, \phi)} \int dh^0 \prod_{l=1}^{j} dh^l \frac{e^{-\frac{1}{2}h^T Q^{-1} h}}{\sqrt{(2\pi)^{j+1} \det Q}} \Theta[\operatorname{sgn}(h^0)v] \prod_{l=1}^{j} \operatorname{sgn}(h^l). \quad (\text{D8}) $$

In going from the second to the last line we introduced overlap variables $h$ as in appendix B. The rest of the large deviation measure in equation (D6) factorize into $e^{Nsj\Phi(\beta, \phi)}$, with $\Phi$ the free entropy computed in appendices B and C, and goes to 1 as the $s \to 0$ limit is taken. We also introduced an overlap matrix $Q$ of RS form

$$ Q_{00} = r^0 \quad (\text{D9}) $$

$$ Q_{0l} = m \quad \forall 1 \le l \le j \quad (\text{D10}) $$

$$ Q_{ll} = r \quad \forall 1 \le l \le j \quad (\text{D11}) $$

$$ Q_{lk} = q \quad \forall 1 \le l \neq k \le j. \quad (\text{D12}) $$

The order parameters $r^0, r, m$ and $q$ were defined in the replica ansatz equations (B8)-(B12). Note that the relevant overlap is $q$, rather than $Q$, since the $j$-fold replication in equation (D6) affects also the selection variables $\sigma$ and thus the variables $\mathbf{x}^{l11}$ see different disorders, see appendix B. The inverse $\tilde{Q} = Q^{-1}$ is characterized by the coefficients

$$ \tilde{r}^0 = \frac{r + (j - 1)q}{r^0(r + (j - 1)q) - jm^2} \quad (\text{D13}) $$

$$ \tilde{r} = \frac{r^0(r + (j - 2)q) - (j - 1)m^2}{(r - q)(r^0(r + (j - 1)q) - jm^2)} \quad (\text{D14}) $$

$$ \tilde{m} = \frac{-m}{(r^0(r + (j - 1)q) - jm^2)} \quad (\text{D15}) $$

$$ \tilde{r} = \frac{m^2 - r^0 q}{(r - q)(r^0(r + (j - 1)q) - jm^2)}. \quad (\text{D16}) $$

(D17)
introduce as precedently $\beta$s replicas

$$ \mathbb{E}_{\mathbf{x}}^{\beta, \phi} \operatorname{sgn}(\mathbf{x} \cdot \mathbf{F}_{\text{new}}) = \lim_{s \to 0} \Xi^{s-1} \sum_{\{\sigma_{\mu}\}} e^{\phi \sum_{\mu} S_{\mu}} \left[ \int d\mathbf{x} P_X(\mathbf{x}) \prod_{\mu} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \mathbf{x})^{\sigma_{\mu}} \right]^{\beta-1} \int d\mathbf{x} P_X(\mathbf{x}) \prod_{\mu} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \mathbf{x})^{\sigma_{\mu}} \operatorname{sgn}(\mathbf{x} \cdot \mathbf{F}_{\text{new}}) \quad (\text{D4}) $$

$$ = \lim_{s \to 0} \sum_{\boldsymbol{\sigma}^1, \dots, \boldsymbol{\sigma}^n} \int \prod_{a=1}^{s} \prod_{\alpha=1}^{\beta} dx^{a\alpha} P_X(\mathbf{x}) \prod_{\mu} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \mathbf{x}^{a\alpha})^{\sigma_{\mu}^{a}} e^{\phi \sum_{a,\mu} \sigma_{\mu}^{a}} \operatorname{sgn}(\mathbf{x}^{11} \cdot \mathbf{F}_{\text{new}}). \quad (\text{D5}) $$

From which it follows that

$$ (\mathbb{E}_{\mathbf{x}}^{\beta, \phi} \operatorname{sgn}(\mathbf{x} \cdot \mathbf{F}_{\text{new}}))^j = \lim_{s \to 0} \sum_{1 \le l \le j, 1 \le a \le s} \int \prod_{a=1}^{s} \prod_{l=1}^{j} \prod_{\alpha=1}^{\beta} dx^{a\alpha} P_X(\mathbf{x}^{la\alpha}) \prod_{\mu} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \mathbf{x}^{la\alpha})^{\sigma_{\mu}^{la}} e^{\phi \sum_{l,a,\mu} \sigma_{\mu}^{la}} \prod_{l=1}^{j} \operatorname{sgn}(\mathbf{x}^{l11} \cdot \mathbf{F}_{\text{new}}). \quad (\text{D6}) $$

The net effect is simply to transform the first index $a$ into a double index $(l, a)$, thereby introducing a third level of replication. Pursuing equation (D2),

$$ 1 - \epsilon_g = \lim_{s \to 0} \sum_{j=0}^{\infty} \int dv d\hat{v} e^{iv\hat{v}} \frac{(i\hat{v})^j}{j!} \mathbb{E}_{\mathbf{x}^0, \mathbf{Y}, \mathbf{F}} \sum_{1 \le l \le j, 1 \le a \le s} \int \prod_{a=1}^{s} \prod_{l=1}^{j} \prod_{\alpha=1}^{\beta} dx^{a\alpha} P_X(\mathbf{x}^{la\alpha}) \prod_{\mu} P_{\text{out}}(y^{\mu} | \mathbf{F}^{\mu} \mathbf{x}^{la\alpha})^{\sigma_{\mu}^{la}} e^{\phi \sum_{l,a,\mu} \sigma_{\mu}^{la}} \mathbb{E}_{\mathbf{F}_{\text{new}}} \prod_{l=1}^{j} \operatorname{sgn}(\mathbf{x}^{l11} \cdot \mathbf{F}_{\text{new}}) \Theta[\operatorname{sgn}(\mathbf{x}^0 \cdot \mathbf{F}_{\text{new}})v] \quad (\text{D7}) $$

$$ = \lim_{s \to 0} \sum_{j=0}^{\infty} \int dv d\hat{v} e^{iv\hat{v}} \frac{(i\hat{v})^j}{j!} e^{sjN\Phi(\beta, \phi)} \int dh^0 \prod_{l=1}^{j} dh^l \frac{e^{-\frac{1}{2}h^T Q^{-1} h}}{\sqrt{(2\pi)^{j+1} \det Q}} \Theta[\operatorname{sgn}(h^0)v] \prod_{l=1}^{j} \operatorname{sgn}(h^l). \quad (\text{D8}) $$

In going from the second to the last line we introduced overlap variables $h$ as in appendix B. The rest of the large deviation measure in equation (D6) factorize into $e^{Nsj\Phi(\beta, \phi)}$, with $\Phi$ the free entropy computed in appendices B and C, and goes to 1 as the $s \to 0$ limit is taken. We also introduced an overlap matrix $Q$ of RS form

$$ Q_{00} = r^0 \quad (\text{D9}) $$

$$ Q_{0l} = m \quad \forall 1 \le l \le j \quad (\text{D10}) $$

$$ Q_{ll} = r \quad \forall 1 \le l \le j \quad (\text{D11}) $$

$$ Q_{lk} = q \quad \forall 1 \le l \neq k \le j. \quad (\text{D12}) $$

The order parameters $r^0, r, m$ and $q$ were defined in the replica ansatz equations (B8)-(B12). Note that the relevant overlap is $q$, rather than $Q$, since the $j$-fold replication in equation (D6) affects also the selection variables $\sigma$ and thus the variables $\mathbf{x}^{l11}$ see different disorders, see appendix B. The inverse $\tilde{Q} = Q^{-1}$ is characterized by the coefficients

$$ \tilde{r}^0 = \frac{r + (j - 1)q}{r^0(r + (j - 1)q) - jm^2} \quad (\text{D13}) $$

$$ \tilde{r} = \frac{r^0(r + (j - 2)q) - (j - 1)m^2}{(r - q)(r^0(r + (j - 1)q) - jm^2)} \quad (\text{D14}) $$

$$ \tilde{m} = \frac{-m}{(r^0(r + (j - 1)q) - jm^2)} \quad (\text{D15}) $$

$$ \tilde{r} = \frac{m^2 - r^0 q}{(r - q)(r^0(r + (j - 1)q) - jm^2)}. \quad (\text{D16}) $$

(D17)
The last integral in equation (D8) can be taken core of in the usual manner, by decomposing the exponent and introducing a Hubbard-Stratonovitch field $\eta$, see for example appendix B. Similarly the expression can then be factorized in $l$ indices. The result is

$$ \int dh^0 \prod_{l=1}^{j} dh^l e^{-\frac{1}{2}h^T Q^{-1}h} \Theta[\operatorname{sgn}(h^0)v] \prod_{l=1}^{j} \operatorname{sgn}(h^l) = \int \frac{D\eta dh^0}{\sqrt{(2\pi)^{j+1} \det Q}} e^{-\frac{1}{2}\hat{r}^0(h^0)^2} e^{\frac{j}{2}\left(\sqrt{\frac{-\tilde{q}}{r-q}}\eta - \sqrt{\frac{\tilde{m}}{r-q}}h^0\right)^2} \\ \left[1 - 2H\left(\sqrt{\frac{-\tilde{q}}{\tilde{r}-\tilde{q}}}\eta - \frac{\tilde{m}}{\sqrt{\tilde{r}-\tilde{q}}}h^0\right)\right]^j \quad (D18) $$

$$ = \int D\eta D h^0 \left[ 1 - 2H \left( \sqrt{\frac{m^2 - qr^0}{r^0(q-r)}}\eta - \sqrt{\frac{m^2}{r^0(r-q)}}h^0 \right) \right]^j. \quad (D19) $$

This terminates the computation of $\epsilon_g$, since from equation (D8)

$$ 1 - \epsilon_g = \int D\eta D h^0 \Theta[h^0(1 - 2H \left( \sqrt{\frac{m^2 - qr^0}{r^0(q-r)}}\eta - \sqrt{\frac{m^2}{r^0(r-q)}}h^0 \right))] \quad (D20) $$

$$ = \int D\eta D h^0 \Theta[h^0(\sqrt{r^0 q - m^2} \eta - mh^0)] \quad (D21) $$

$$ = 1 - \frac{1}{\pi} \cos^{-1} \frac{m}{\sqrt{q}}. \quad (D22) $$

We used the fact that $x \to 1 - 2H(x)$ was odd and the fact that $r^0 = 1$ for the perceptron model with Gaussian priors, see appendix C.

## Appendix E: Additional numerical confirmation

We supply numerical evidence for some assumptions made in this work, in particular the replica trick (B1) and the use of the Gardner volume as a measure of informativeness (see section III in the main text).

First, we sample numerically at random subsets of cardinalities $n \in \{0.3, 0.6, 0.9, 2.7\}$ out of a pool of cardinal given by $\alpha = 3$, and plot the complexity extracted therefrom in Fig. 6. The volumes were evaluated using the AMP algorithm 2, and simulations were performed at $N = 20$, with $10^7$ draws. Because of computational limitations $N$ has been kept small, while AMP is known to be valid only in the $N \uparrow \infty$ limit, hence inducing errors due to finite size. Nevertheless, the agreement with the theoretical curves for $\Sigma(n, v)$ is quite good.

We finally present a numerical check of the theoretical prediction for the $m(v)$ curves, see Fig. 1. At large instance size, $N = 2000$, it is not computationally feasible to obtain sufficient statistics for observing the large deviations of the volume through passive subset sampling, as it was done in the previous experiment. Thus, we resorted to the label-informed AL-AMP active learning strategy for biasing the subset selection towards more/less informative subsets. In particular, we constructed each subset by mixing varying ratios of maximally informative samples (selected according to the informed AL-AMP procedure, see algorithm 1 and Tab. I) and minimally informative samples (selected according to the same procedure but with the reversed sorting order). In the figure, the pool size is $\alpha = 10$ and the budget is fixed to $n = 1.5$. For each subset, the AMP algorithm 2 was run to get the estimator $\hat{x}$ and the magnetization $m$ was deduced therefrom. This incidentally corroborates once more that using the Gardner volume instead of the magnetization to judge for the informativeness of a selection is coherent.
The last integral in equation (D8) can be taken core of in the usual manner, by decomposing the exponent and introducing a Hubbard-Stratonovitch field $\eta$, see for example appendix B. Similarly the expression can then be factorized in $l$ indices. The result is

$$ \int dh^0 \prod_{l=1}^{j} dh^l e^{-\frac{1}{2}h^T Q^{-1}h} \Theta[\operatorname{sgn}(h^0)v] \prod_{l=1}^{j} \operatorname{sgn}(h^l) = \int \frac{D\eta dh^0}{\sqrt{(2\pi)^{j+1} \det Q}} e^{-\frac{1}{2}\hat{r}^0(h^0)^2} e^{\frac{j}{2}\left(\sqrt{\frac{-\hat{q}}{r-q}}\eta - \sqrt{\frac{\hat{m}}{r-q}}h^0\right)^2} \left[1 - 2H\left(\sqrt{\frac{-\hat{q}}{r-q}}\eta - \frac{\hat{m}}{\sqrt{r-q}}h^0\right)\right]^j \quad (D18) $$

$$ = \int D\eta Dh^0 \left[1 - 2H\left(\sqrt{\frac{m^2 - qr^0}{r^0(q-r)}}\eta - \sqrt{\frac{m^2}{r^0(r-q)}}h^0\right)\right]^j. \quad (D19) $$

This terminates the computation of $\epsilon_g$, since from equation (D8)

$$ 1 - \epsilon_g = \int D\eta Dh^0 \Theta[h^0(1 - 2H\left(\sqrt{\frac{m^2 - qr^0}{r^0(q-r)}}\eta - \sqrt{\frac{m^2}{r^0(r-q)}}h^0\right))] \quad (D20) $$

$$ = \int D\eta Dh^0 \Theta[h^0(\sqrt{r^0 q - m^2} \eta - mh^0)] \quad (D21) $$

$$ = 1 - \frac{1}{\pi} \cos^{-1} \frac{m}{\sqrt{q}}. \quad (D22) $$

We used the fact that $x \to 1 - 2H(x)$ was odd and the fact that $r^0 = 1$ for the perceptron model with Gaussian priors, see appendix C.

## Appendix E: Additional numerical confirmation

We supply numerical evidence for some assumptions made in this work, in particular the replica trick (B1) and the use of the Gardner volume as a measure of informativeness (see section III in the main text).

First, we sample numerically at random subsets of cardinalities $n \in \{0.3, 0.6, 0.9, 2.7\}$ out of a pool of cardinal given by $\alpha = 3$, and plot the complexity extracted therefrom in Fig. 6. The volumes were evaluated using the AMP algorithm 2, and simulations were performed at $N = 20$, with $10^7$ draws. Because of computational limitations $N$ has been kept small, while AMP is known to be valid only in the $N \uparrow \infty$ limit, hence inducing errors due to finite size. Nevertheless, the agreement with the theoretical curves for $\Sigma(n, v)$ is quite good.

We finally present a numerical check of the theoretical prediction for the $m(v)$ curves, see Fig. 1. At large instance size, $N = 2000$, it is not computationally feasible to obtain sufficient statistics for observing the large deviations of the volume through passive subset sampling, as it was done in the previous experiment. Thus, we resorted to the label-informed AL-AMP active learning strategy for biasing the subset selection towards more/less informative subsets. In particular, we constructed each subset by mixing varying ratios of maximally informative samples (selected according to the informed AL-AMP procedure, see algorithm 1 and Tab. I) and minimally informative samples (selected according to the same procedure but with the reversed sorting order). In the figure, the pool size is $\alpha = 10$ and the budget is fixed to $n = 1.5$. For each subset, the AMP algorithm 2 was run to get the estimator $\hat{x}$ and the magnetization $m$ was deduced therefrom. This incidentally corroborates once more that using the Gardner volume instead of the magnetization to judge for the informativeness of a selection is coherent.
<figure><img src="image_7.png" /><figcaption>FIG. 6. Complexity vs volume curves for $\alpha = 3$, and $n \in \{0.3, 0.6, 0.9, 2.7\}$. The dots are the values extracted from numerical experiments performed at $N = 20$ by repeatedly sampling passively $10^7$ times a subset of cardinality $n$ out of a fixed pool of size $\alpha = 3$. Solid lines are the theoretical complexities as predicted by the large deviation computations, see also Fig. 1. Volumes were evaluated using the AMP Algorithm 2. The agreement is rather good knowing the discrepancies that ought to be expected because of running AMP Algorithm 2 at finite and small $N$.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>FIG. 7. Magnetization $m$ against Gardner volume $v$ for various subsets. The experiments were performed at system size $N = 10^3$, pool size $\alpha = 10$ and budget $n = 1.5$. Subsets covering a wide range of volumes were designed by varying the ratio of informative samples (using label-informed AL-AMP, see section V) and uninformative samples (selected using simple passive learning). Magnetizations and volumes were evaluated using the AMP procedure 2. In solid line is the typical $m(v)$ curve predicted by the large deviation computations, which agrees quite well with the numerical simulations.</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>FIG. 6. Complexity vs volume curves for $\alpha = 3$, and $n \in \{0.3, 0.6, 0.9, 2.7\}$. The dots are the values extracted from numerical experiments performed at $N = 20$ by repeatedly sampling passively $10^7$ times a subset of cardinality $n$ out of a fixed pool of size $\alpha = 3$. Solid lines are the theoretical complexities as predicted by the large deviation computations, see also Fig. 1. Volumes were evaluated using the AMP Algorithm 2. The agreement is rather good knowing the discrepancies that ought to be expected because of running AMP Algorithm 2 at finite and small $N$.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>FIG. 7. Magnetization $m$ against Gardner volume $v$ for various subsets. The experiments were performed at system size $N = 10^3$, pool size $\alpha = 10$ and budget $n = 1.5$. Subsets covering a wide range of volumes were designed by varying the ratio of informative samples (using label-informed AL-AMP, see section V) and uninformative samples (selected using simple passive learning). Magnetizations and volumes were evaluated using the AMP procedure 2. In solid line is the typical $m(v)$ curve predicted by the large deviation computations, which agrees quite well with the numerical simulations.</figcaption></figure>