# A Large Dimensional Analysis of Multi-task Semi-Supervised Learning

Victor Léger, , Romain Couillet

###### Abstract

This article conducts a large dimensional study of a simple yet quite
versatile classification model, encompassing at once multi-task and semi-
supervised learning, and taking into account uncertain labeling. Using tools
from random matrix theory, we characterize the asymptotics of some key
functionals, which allows us on the one hand to predict the performances of
the algorithm, and on the other hand to reveal some counter-intuitive guidance
on how to use it efficiently. The model, powerful enough to provide good
performance guarantees, is also straightforward enough to provide strong
insights into its behavior.

###### Index Terms:

classification, random matrix theory, multi-task learning, semi-supervised
learning

##  I Introduction

If the multiple achievements of deep neural networks (DNNs) in various tasks
during the last decade are now a well-known fact, we also know that these
achievements have been strongly reliant on increases in computing power [1].
This escalation implies skyrocketing energy requirements, but another
fondamental consequence relates to tractability, and even technical
accessibility, which are, in the case of DNNs, out of reach to their own
designers (let alone to their users).

As an alternative viewpoint, following the notion of _conviviality of tools_
developed by the critical analyst Ivan Illich [2], the present article is part
of a renewed endeavour for techniques and tools which simultaneously _answer
an effective need_ (rather than create a new need), _are tractable and easily
apprehensible by their user_ , and _are flexible and robust enough not to
require constant adaptations and additional scientific complexification_.

That is, through the present article, we aim to open the path to all-
encompassing flexible tools for classification problems, buttressed on
elementary machine learning notions and rather basic mathematical tools.
Specifically, we propose here a classification method that addresses a wide
variety of real-life conditions, such as the possibility for only part of the
input data to be prelabeled (thereby encompassing supervised, semi-supervised
and unsupervised learning at once), the possibility for erroneous or uncertain
labels (here considering biases or controversial data labeling), the
possibility for strong imbalances in prelabeled classes of data (a very
classical issue when some key classes are rarely observed), etc. As such, our
base model combines what are usually considered as distinct learning
frameworks (multi-task learning, semi-supervised learning, uncertain labeling)
under a common umbrella.

Specifically, we develop a simple and quite technically accessible method
which perfoms linear classification in a multi-task and semi-supervised
framework, in a basic two-class setting (the extension to a multiclass setting
is briefly discussed in Section V-A). Considering Gaussian mixtures as data
model, we leverage random matrix theory (RMT) to characterize the asymptotics
of key functionals, such as the _decision function_ , which enables
classification by attributing a score to each new sample. In contrast to
classical statistics, we consider high dimensional data (_i.e.,_ the dimension
$p$ and the number of data $n$ are of the same order of magnitude – which is
more a fact than an assumption in modern data).

The relative simplicity of our model, along with the strength of RMT, make the
proposed method quite powerful as it is in particular able to _predict its own
performances_. In a nutshell, our theoretical analysis allows us to:

  * •

Tune the hyperparameters of the model without running the algorithm, therefore
avoiding any cross-validation (costly in data and computational resources).

  * •

Choose wisely (and automatically) the values of labels (rather than the
standard $\pm 1$ values) to discriminate more efficiently the data, and tackle
the problems induced by unbalanced classes.

  * •

Understand better and avoid the classical problem of negative transfer.

  * •

Estimate how good the algorithm is in comparison with optimal bounds from
information theory.

Both multi-task learning and semi-supervised learning have already been
studied with RMT tools, usually separately though. Specifically, [3] provides
a theoretical analysis (in a single-task framework) of the graph-based semi-
supervised scheme we use in this article [4, 5]. In particular, it reveals a
fundamental flaw of graph-based algorithms, but most importantly, it proposes
a simple way to tackle it. Indeed, many algorithms appear to be unable to
learn effectively from unlabeled data, even though it is a fundamental aspect
of semi-supervised learning [6, 7, 8, 9].

Meanwhile, [10] provides a similar analysis of a well-known multi-task
framework [11], in a fully supervised setting. In particular, it introduces
(for the first time, as far as we know) the counter-intuitive idea of choosing
the values of labels differently from the standard $\pm 1$. This idea, which
is one of the keys to our present algorithm, appears to be an easy and
intuitive way to tackle the issue of negative transfer.

The remainder of the article is organized as follows. Section II introduces
the assumptions made, the problem formulation and its solution. Section III
presents the main theoretical results of the article, upon which our algorithm
is built. Section IV extends these results to the case of uncertain labeling.
Section V sheds light on some limitations of our method. Finally, Section VI
presents simulations on both synthetic data and real datasets, to validate and
further analyse the results of Section III.

In what follows, matrices are represented by bold uppercase letters (_i.e.,_
matrix ${\mathbf{A}}$). Vectors are denoted in bold lowercase letters (_i.e.,_
vector ${\mathbf{v}}$) and scalars without bold letters (_i.e.,_ variable
$a$). “tasks” are denoted by an index $t$ and the number of tasks will be
referred as $T$. Quantities with superscript $t$ are belonging to Task $t$.
The quantities associated to labeled and unlabeled data are respectively
denoted by a subscript $\ell$ and $u$. As such the notations $n_{\ell}^{t}$
and $n_{u}^{t}$ denote respectively the number of labeled and unlabeled data
of Task $t$. The subscript $j$ is used to specify that a quantity is specific
to the Class $j$.

##  II Model and assumptions

We focus from now on the two-class setting, the multi-class setting is briefly
discussed in Section V-A. Let ${\mathbf{X}}\in\mathbb{R}^{p\times n}$ be a
collection of $n$ independent data vectors of dimension $p$. The data are
divided into $T$ subsets attached to individual “task”. Specifically, letting
${\mathbf{X}}=[{\mathbf{X}}^{1},\ldots,{\mathbf{X}}^{T}]\in\mathbb{R}^{p\times
n}$, Task $t$ is a semi-supervised binary classification task with training
samples
${\mathbf{X}}^{t}=[{\mathbf{X}}_{\ell}^{t},{\mathbf{X}}_{u}^{t}]\in\mathbb{R}^{p\times
n^{t}}$ which consists of a set of $n_{\ell}^{t}$ labeled data samples
${\mathbf{X}}_{\ell}^{t}=\\{{\mathbf{x}}_{i}^{t}\\}_{i=1}^{n_{\ell}^{t}}$ and
a set of $n_{u}^{t}$ unlabeled data points
${\mathbf{X}}_{u}^{t}=\\{{\mathbf{x}}_{i}^{t}\\}_{i=n_{\ell}^{t}+1}^{n^{t}}$.
To each labeled data ${\mathbf{x}}_{i}^{t}$ from Task $t$ is attached a label
$y_{i}^{t}$ and the goal is to predict the labels for the unlabeled data
${\mathbf{X}}_{u}^{t}$. In this paper, we will divide the $T$ tasks in:

  * •

One “target task” which is the one task we actually want to perform.

  * •

$T-1$ “source tasks” which will help us to perform the “target task”.

In a sense, our setting is close to transfer-learning because we aim to
perform a single classification task. However, as the calculus done in the
following is true for any choice of target task, we can easily perform
sequentially each one of the $T$ tasks with the help of the other, and
therefore perform multi-task learning.

######  Assumption 0 (On the data distribution).

The columns of the data matrix ${\mathbf{X}}$ are independent Gaussian random
variables. Specifically, the data samples
$\left({\mathbf{x}}_{1}^{t},\dots,{\mathbf{x}}^{t}_{n^{t}}\right)$ from Task
$t$ are i.i.d. observations such that
${\mathbf{x}}_{i}^{t}\in\mathcal{C}_{j}^{t}\Leftrightarrow{\mathbf{x}}_{i}^{t}\sim\mathcal{N}({\boldsymbol{\mu}}_{j}^{t},{\mathbf{I}}_{p})$
where $\mathcal{C}_{j}^{t}$ denotes the Class $j$ of Task $t$.

Even though this assumption is intuitive and straightforward, one could argue
that it is unrealistic. Indeed, natural data is not Gaussian, and most
importantly, requiring independent entries for each observation is very
constraining. Concentrated vectors, described for the first time in [12] and
integrated in RMT by [13], allow us to relax the previous assumption, while
preserving its core idea.

######  Assumption 1 (On the data distribution).

The columns of the data matrix ${\mathbf{X}}$ are independent concentrated
vectors with isotropic covariance. Specifically, the data samples
$\left({\mathbf{x}}_{1}^{t},\dots,{\mathbf{x}}^{t}_{n^{t}}\right)$ from Task
$t$ are i.i.d. observations such that:
There exists $C,c>0$ such that for any $1$-Lipschitz function
$\Phi:\mathbb{R}^{p}\to\mathbb{R}$, we have:

$\forall
u>0,\quad{\mathbf{x}}_{i}^{t}\in\mathcal{C}_{j}^{t}\Rightarrow\mathbb{P}(|\Phi({\mathbf{x}}_{i}^{t})-m_{j}^{t}(\Phi)|\geq
u)\leq Ce^{-(\frac{u}{c})^{2}}$

where $\mathcal{C}_{j}^{t}$ denotes the Class $j$ of Task $t$, and
$m_{j}^{t}(\Phi)=\mathbb{E}\left[\Phi({\mathbf{x}})|{\mathbf{x}}\in\mathcal{C}_{j}^{t}\right]$.
Under these assumtions, we can define

$\displaystyle{\boldsymbol{\mu}}_{j}^{t}$
$\displaystyle=\mathbb{E}[{\mathbf{x}}|{\mathbf{x}}\in\mathcal{C}_{j}^{t}]$
$\displaystyle{\mathbf{\Sigma}}_{j}^{t}$
$\displaystyle=\mathrm{Cov}[{\mathbf{x}}|{\mathbf{x}}\in\mathcal{C}_{j}^{t}]$

and we further impose that $\forall
j,t,{\mathbf{\Sigma}}_{j}^{t}={\mathbf{I}}_{p}$.

This second assumption encompasses the first one, and applies to a broader
class of distributions. In particular, images produced by Generative
Adversarial Networks (GANs) are concentrated vectors [14]. As GANs are known
to produce very convincing fake images and text, this assumption allows to
consider more realistic datasets. All the theoretical results discussed in the
remainder of the article are obtained using Assumption 1. The assumption
${\mathbf{\Sigma}}_{j}^{t}={\mathbf{I}}_{p}$ is still restrictive, and should
not be seen as an imperious condition for our algorithm to work, but rather as
a convenient assumption to perform our statistical analysis. As such, the
experiments of Section VI-D shows that the algorithm performs well on
concentrated vectors for which the covariance is not necessarily isotropic.

As discussed earlier, we consider a large dimensional setting, where the
dimension of the data and the number of data have the same order of magnitude.
Moreover, to take into account the potential consequences of class unbalances,
our statistical analysis will make use of the proportion of data in each
class. To this end, we make the following assumption.

######  Assumption 2 (Growth Rate).

As $n\to\infty$,

  * •

$p/n\to c>0$.

  * •

$n_{j}^{t}/n\to\rho_{j}^{t}>0$ ($n_{j}^{t}$ the number of data in
$\mathcal{C}_{j}^{t}$).

  * •

$n^{t}/n\to\rho^{t}>0$.

  * •

$n_{\ell j}^{t}/n_{j}^{t}\to\eta_{j}^{t}>0$ ($n_{\ell j}^{t}$ the number of
labeled data in $\mathcal{C}_{j}^{t}$).

  * •

$n_{\ell}^{t}/n^{t}\to\eta^{t}>0$.

Furthermore, we also consider the $2T$-dimensional vector
${\boldsymbol{\rho}}=\left(\rho_{1}^{1},\rho_{2}^{1},\rho_{1}^{2},\dots,\rho_{2}^{T}\right)^{\sf
T}$, the $T$-dimensional vector
$\bar{{\boldsymbol{\rho}}}=\left(\rho^{1},\dots,\rho^{T}\right)^{\sf T}$, and
similarly the vectors ${\boldsymbol{\eta}}$ and $\bar{{\boldsymbol{\eta}}}$.

Graph-based approaches, such as the Laplacian regularization method, are
widely use to perform semi-supervised learning (in a single-task setting) [15,
4, 16]. The idea consists in propagating the effective information of labeled
data to unlabeled data, following the natural assumption that similar data
points should have similar labels. This similarity between data points
${\mathbf{x}}_{i}$ and ${\mathbf{x}}_{i^{\prime}}$ is measured by the quantity
$\omega_{ii^{\prime}}=h\left(\frac{1}{p}\langle{\mathbf{x}}_{i},{\mathbf{x}}_{i^{\prime}}\rangle\right)$
with $h$ an increasing function ($h(x)=x$ in our case), so that similar data
vectors ${\mathbf{x}}_{i}$ and ${\mathbf{x}}_{i^{\prime}}$ are connected with
a large weight. From there, graph-based learning algorithms estimate the class
of each node ${\mathbf{x}}_{i}$ through a class attachment “score” $f_{i}$, by
solving the following optimization problem:

$\displaystyle\min\limits_{{\mathbf{f}}}\sum\limits_{i,i^{\prime}=1}^{n}\omega_{ii^{\prime}}\left(f_{i}-f_{i^{\prime}}\right)^{2}$
(1) $\displaystyle\textit{such that}~{}f_{i}=y_{i}~{}\forall~{}1\leq i\leq
n_{\ell}.$

The term $f_{i}=y_{i}$ is the fitting constraint, which imposes that the score
of labeled data should match the initial label assignment. This constraint is
sometimes relaxed by adding a term
$2\alpha\|{\mathbf{f}}_{\ell}-{\mathbf{y}}_{\ell}\|^{2}$ to the minimization
problem, with $\alpha>0$ [5], where ${\mathbf{f}}_{\ell}$ and
${\mathbf{y}}_{\ell}$ respectively denotes the vectors ${\mathbf{f}}$ and
${\mathbf{y}}$ restricted to labeled data.

Our multi-task semi-supervised algorithm follows the same idea, yet with the
addition of a hyperparameter matrix
${\mathbf{\Lambda}}=\\{\Lambda^{tt^{\prime}}\\}_{t,t^{\prime}=1}^{T}$ which
filters how much each task should be related to each other. The optimisation
becomes:

$\displaystyle\min\limits_{{\mathbf{f}}^{1},\ldots,{\mathbf{f}}^{T}}\sum\limits_{t,t^{\prime}=1}^{T}\Lambda^{tt^{\prime}}\sum\limits_{i=1}^{n^{t}}\sum\limits_{i^{\prime}=1}^{n^{t^{\prime}}}\omega_{ii^{\prime}}^{tt^{\prime}}\left(f_{i}^{t}-f_{i^{\prime}}^{t^{\prime}}\right)^{2}$
(2) $\displaystyle\textit{such that}~{}f_{i}^{t}=y_{i}^{t}~{}\forall~{}1\leq
i\leq n_{\ell}^{t}~{}\textit{and}~{}1\leq t\leq T.$

and the weights $\omega_{ii^{\prime}}^{tt^{\prime}}$ are now

$\omega_{ii^{\prime}}^{tt^{\prime}}=\frac{1}{Tp}\langle{\mathbf{x}}_{i}^{t},{\mathbf{x}}_{i^{\prime}}^{t^{\prime}}\rangle$

The classical Laplacian regularization algorithm associated to (1) has been
studied in depth in [17] in the single-task setting. There, the authors showed
the fundamental importance to “center” the weight matrix
${\mathbf{W}}=\\{\omega_{ii^{\prime}}\\}_{i,i^{\prime}=1}^{n}$. This centering
approach corrects an important bias in the regularized Laplacian which
completely annihilates the use of unlabeled data in a large dimensional
setting. A significant performance increase was reported, both in theory and
in practice in [3] when this basic, yet counter-intuitive, correction is
accounted for. The same phenomenon evidently arises in the multi-task
extension and we propose consequently the same task-wise pre-centering in the
context of multi-task learning, that is we update the weight matrices
$({\mathbf{W}}^{tt^{\prime}})_{t,t^{\prime}}$ as:

$\hat{{\mathbf{W}}}^{tt^{\prime}}={\mathbf{P}}^{t}{\mathbf{W}}^{tt^{\prime}}{\mathbf{P}}^{t^{\prime}}$
(3)

with
${\mathbf{P}}^{t}=\left({\mathbf{I}}_{n^{t}}-\frac{1}{n^{t}}\mathbb{1}_{n^{t}}\mathbb{1}_{n^{t}}^{\sf
T}\right)$ the centering projector. This is equivalent to replace the data
matrix ${\mathbf{X}}^{t}$ by its centered version
$\mathring{{\mathbf{X}}}^{t}={\mathbf{X}}^{t}{\mathbf{P}}^{t}$. It is worth to
note that the centering is performed undifferently on labeled and unlabeled
data, as the whole task is concerned and both classes are centered at once.
For a matter of readability, ${\mathbf{X}}^{t}$ will denote the centered
matrix in the remainder of the article. Similarly,
${\boldsymbol{\mu}}_{j}^{t}$ will denote the centered mean of
${\mathbf{x}}\in\mathcal{C}_{j}^{t}$.

However, the optimization problem described in (2) is non convex since the
entries of the weight matrix $\hat{{\mathbf{W}}}$ may take negative values
(this must actually be the case as the mean value of the entries of
$\hat{{\mathbf{W}}}$ is zero). To deal with this problem, we further propose
(as in [3]) to constrain the norm of the unlabeled data score vector
${\mathbf{f}}_{u}$ (that is, the score vector ${\mathbf{f}}$ restricted to
unlabeled data) by appending a regularization term
$2\alpha\|{\mathbf{f}}_{u}\|^{2}$ to the previous minimization problem, with
$\alpha>0$. We also relax the labeling constraint with the regularization term
$2\alpha\|{\mathbf{f}}_{\ell}-{\mathbf{y}}_{\ell}\|^{2}$ mentionned above. The
equation (2) becomes:

$\displaystyle\min\limits_{\mathbf{f}^{1},\ldots,\mathbf{f}^{T}}\sum\limits_{t,t^{\prime}=1}^{T}\Lambda^{tt^{\prime}}\sum\limits_{i=1}^{n^{t}}\sum\limits_{i^{\prime}=1}^{n^{t^{\prime}}}\hat{\omega}_{ii^{\prime}}^{tt^{\prime}}\left(f_{i}^{t}-f_{i^{\prime}}^{t^{\prime}}\right)^{2}$
(4)
$\displaystyle+2\alpha\sum\limits_{t=1}^{T}\left(\sum\limits_{i=1}^{n_{\ell}^{t}}(f_{i}^{t}-y_{i}^{t})^{2}+\sum\limits_{i=n_{\ell}^{t}+1}^{n^{t}}(f_{i}^{t})^{2}\right)$

This leads, under a more convenient matrix formulation (see detail in Section
A of the appendix), to

$\min\limits_{{\mathbf{f}}\in\mathbb{R}^{n}}-{{\mathbf{f}}}^{{\sf
T}}\tilde{{\mathbf{W}}}{\mathbf{f}}+\alpha\|{\mathbf{f}}_{\ell}-{\mathbf{y}}_{\ell}\|^{2}+\alpha\|{\mathbf{f}}_{u}\|^{2}$
(5)

with $\tilde{{\mathbf{W}}}$ the block matrix for which each block is
$\tilde{{\mathbf{W}}}^{tt^{\prime}}=\Lambda^{tt^{\prime}}\hat{{\mathbf{W}}}^{tt^{\prime}},\forall(t,t^{\prime})\in\\{1,\dots,T\\}^{2}$.
If we further use the convention ${\mathbf{y}}_{u}=0$, the problem has an even
simpler formulation:

$\min\limits_{{\mathbf{f}}\in\mathbb{R}^{n}}\alpha\|{\mathbf{f}}-{\mathbf{y}}\|^{2}-{{\mathbf{f}}}^{{\sf
T}}\tilde{{\mathbf{W}}}{\mathbf{f}}$ (6)

This problem is now convex for all $\alpha>\|\tilde{{\mathbf{W}}}\|$. In
addition, ${\mathbf{f}}$ is the solution to a quadratic optimization problem
with linear equality constraints, and can be obtained explicitly (see detail
in Section A of the appendix).

${\mathbf{f}}=\left({\mathbf{I}}_{n}-\frac{{\mathbf{Z}}^{\sf
T}{\mathbf{A}}{\mathbf{Z}}}{Tp}\right)^{-1}{\mathbf{y}}$ (7)

where

$\displaystyle{\mathbf{A}}$
$\displaystyle=\tilde{{\mathbf{\Lambda}}}\otimes{\mathbf{I}}_{p},~{}\textit{with}~{}\tilde{{\mathbf{\Lambda}}}=\frac{{\mathbf{\Lambda}}}{\alpha}~{}\textit{the
hyperparameter matrix}$ $\displaystyle{\mathbf{Z}}$
$\displaystyle=\sum\limits_{t=1}^{T}{\mathbf{E}}_{tt}^{[T]}\otimes{\mathbf{X}}^{t}~{}\textit{the
data matrix}$

If we further use Woodbury matrix identity, we have

${\mathbf{f}}={\mathbf{y}}+\frac{1}{Tp}{\mathbf{Z}}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}\underbrace{\left({\mathbf{I}}_{Tp}-\frac{{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Z}}{\mathbf{Z}}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}}{Tp}\right)^{-1}}_{={\mathbf{Q}}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Z}}{\mathbf{y}}$
(8)

This last solution has the benefit of being explicit and therefore easily
tractable. It can be interpreted as being an a priori on the scores (the first
term), corrected by the data (the second term). As for unlabeled data, there
should not be any a priori, which justifies the previous choice of
${\mathbf{y}}_{u}=0$. Focusing on the scores of unlabeled data then leads to:

${\mathbf{f}}_{u}=\frac{1}{Tp}{\mathbf{Z}}_{u}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Q}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Z}}_{\ell}{\mathbf{y}}_{\ell}$
(9)

To reduce the number of parameters and simplify the model, we choose to set as
of now the values of ${\mathbf{\Lambda}}$ as follows:

$\Lambda^{tt^{\prime}}=\frac{|\langle\boldsymbol{\mu}_{1}^{t}-\boldsymbol{\mu}_{2}^{t},\boldsymbol{\mu}_{1}^{t^{\prime}}-\boldsymbol{\mu}_{2}^{t^{\prime}}\rangle|}{\|\boldsymbol{\mu}_{1}^{t}-\boldsymbol{\mu}_{2}^{t}\|\|\boldsymbol{\mu}_{1}^{t^{\prime}}-\boldsymbol{\mu}_{2}^{t^{\prime}}\|}.$
(10)

As expected $\Lambda^{tt^{\prime}}$ increases if the tasks are more
correlated. This quantity is intuitively associated to the alignement between
tasks and can be consistently estimated. Most importantly, simulations
comparing this choice to an optimization of ${\mathbf{\Lambda}}$ on
$[0,1]^{T\times T}$ suggests that this choice is close to optimal.

##  III Main results

We have an explicit formulation of the score vector ${\mathbf{f}}_{u}$ of
unlabeled data. This vector sums up all the information we have to perform the
classification. In a classical machine learning setting, the score $f$ of a
sample ${\mathbf{x}}$ belonging to $\mathcal{C}_{1}^{t}$ (resp.
$\mathcal{C}_{2}^{t}$) is expected to be close to $-1$ (resp. $+1$).
Therefore, the classification rule is:

$\displaystyle f<\zeta^{t}$
$\displaystyle\implies{\mathbf{x}}\to\mathcal{C}_{1}^{t}$ (11) $\displaystyle
f\geq\zeta^{t}$ $\displaystyle\implies{\mathbf{x}}\to\mathcal{C}_{2}^{t}$

with $\zeta^{t}=0$, where ${\mathbf{x}}\to\mathcal{C}$ means that
${\mathbf{x}}$ is classified in $\mathcal{C}$. However, as we will show later,
choosing $\zeta^{t}=0$ is not guaranteed to be optimal, even though it seems
rather intuitive. Similarly, as discussed in the introduction, the arbitrary
choice $y=\pm 1$ is not necessarily the best. To visualize that, one is
interested in understanding the asymptotic behavior of the score function $f$.
Before stating the theorem giving these asymptotics, one must introduce two
fundamental small-dimensional quantities that will be of particular interest.

  * •

The data matrix ${\boldsymbol{\mathcal{M}}}={\mathbf{M}}^{\sf T}{\mathbf{M}}$,
with
${\mathbf{M}}=\left[\boldsymbol{\mu}_{1}^{1},\boldsymbol{\mu}_{2}^{1},\dots,\boldsymbol{\mu}_{2}^{T}\right]$.
It is worth to note that even though ${\mathbf{M}}$ is not accessible in
practice, the data matrix ${\boldsymbol{\mathcal{M}}}\in\mathbb{R}^{2T\times
2T}$ can be estimated consistently (see Section D of the appendix).

  * •

The parameter matrix ${\boldsymbol{\mathcal{A}}}$, which is the solution of
the following system of equations:

$\left\\{\begin{array}[]{lr}\forall
t,~{}\delta^{t}=\frac{1}{T}{\boldsymbol{\mathcal{A}}}_{tt},\\\
{\boldsymbol{\mathcal{A}}}=\tilde{\mathbf{\Lambda}}+\tilde{\mathbf{\Lambda}}\left({\mathcal{D}}_{\bar{\boldsymbol{\delta}}}^{-1}-\tilde{\mathbf{\Lambda}}\right)^{-1}\tilde{\mathbf{\Lambda}}\end{array}\right.$

with $\tilde{\delta}_{j}^{t}=\frac{\rho_{j}^{t}}{Tc(1-\delta^{t})}$ and
$\bar{\delta}^{t}=\tilde{\delta}_{1}^{t}+\tilde{\delta}_{2}^{t}$.
The equations leading to ${\boldsymbol{\mathcal{A}}}$ translates how the
parameters and hyperparameters of each task interact with each other in the
optimization problem.

These two quantities are mixed up in the following matrix:

${\mathbf{\Theta}}_{0}=\left({\boldsymbol{\mathcal{A}}}\otimes\mathbb{1}_{2}\mathbb{1}_{2}^{\sf
T}\right)\odot{\boldsymbol{\mathcal{M}}}$

As long as uncertain labeling is not taken into account, it is natural to
consider that labels are equals for datapoints in the same class, _i.e.,_
$\forall{\mathbf{x}}_{i}^{t}\in\mathcal{C}_{j}^{t},y_{i}^{t}=\tilde{y}_{j}^{t}\in\mathbb{R}$.
Therefore we define
$\tilde{{\mathbf{y}}}=[\tilde{y}_{1}^{1},\tilde{y}_{2}^{1},\tilde{y}_{1}^{2},\dots,\tilde{y}_{2}^{T}]\in\mathbb{R}^{2T}$,
which sums up the label values. Precisely, we have
${\mathbf{y}}_{\ell}={\mathbf{D}}\tilde{{\mathbf{y}}}$, with

${\mathbf{D}}=\sum\limits_{t=1}^{T}{\mathbf{E}}_{tt}^{[T]}\otimes\begin{pmatrix}\mathbb{1}_{n_{\ell
1}^{t}}&\mathbb{0}_{n_{\ell 1}^{t}}\\\ \mathbb{0}_{n_{\ell
2}^{t}}&\mathbb{1}_{n_{\ell 2}^{t}}\end{pmatrix}$ (12)

In this specific case, the statistics of the score function are given by the
following theorem:

######  Theorem 3.

Under Assumptions 1 and 2, and if labels are given by (16), for any unlabeled
sample ${\mathbf{x}}\in\mathcal{C}_{j}^{t}$, and $f$ being its associated
score,

$f\rightarrow\mathcal{N}\left(m_{j}^{t},{\sigma^{t}}^{2}\right)$

with $m_{j}^{t}=(1-\delta^{t}){{\mathbf{a}}_{j}^{t}}^{\sf
T}\tilde{{\mathbf{y}}}$ and
$\sigma^{t}=(1-\delta^{t})\sqrt{\tilde{{\mathbf{y}}}^{\sf
T}{\mathbf{B}}^{t}\tilde{{\mathbf{y}}}}$

$\displaystyle{\mathbf{a}}_{j}^{t}$
$\displaystyle=\left({{\mathbf{e}}_{t,j}^{[2T]}}^{\sf
T}\left({\mathbf{\Theta}}-\frac{Tc\delta^{t}}{\rho^{t}}{\mathbf{\Gamma}}\right){\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}{\mathcal{D}}_{{\boldsymbol{\eta}}}\right)^{\sf
T}$ $\displaystyle{\mathbf{B}}^{t}$
$\displaystyle={\mathcal{D}}_{{\boldsymbol{\eta}}}\left[2{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}\left({\mathbf{\Theta}}-\frac{Tc\delta^{t}}{\rho^{t}}{\mathbf{\Gamma}}\right)-{\mathbf{\Gamma}}^{t}\right]{\mathcal{D}}_{{\mathbf{r}}^{t}}{\mathcal{D}}_{{\boldsymbol{\eta}}}$
$\displaystyle+{\mathcal{D}}_{{\boldsymbol{\eta}}}{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}\left({\mathbf{\Theta}}{\mathcal{D}}_{{\mathbf{r}}^{t}}{\mathbf{\Theta}}+\bar{{\mathbf{\Omega}}}^{t}-\left(\frac{Tc\delta^{t}}{\rho^{t}}\right)^{2}{\mathbf{\Gamma}}^{t}\right){\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}{\mathcal{D}}_{{\boldsymbol{\eta}}}$
$\displaystyle+{\mathbf{T}}^{t}\odot{\mathcal{D}}_{{\boldsymbol{\rho}}\odot{\boldsymbol{\eta}}}{\mathcal{D}}_{(\bar{{\boldsymbol{\rho}}}\odot\bar{{\boldsymbol{\eta}}})\otimes\mathbb{1}_{2}}^{-1}$

and where

  * •

${\mathbf{\Theta}}=\left({\mathbf{I}}_{2T}-{\mathbf{\Theta}}_{0}{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}\right)^{-1}{\mathbf{\Theta}}_{0}\in\mathbb{R}^{T\times
T}$

  * •

${\mathbf{\Gamma}}={\mathbf{I}}_{T}\otimes\mathbb{1}_{2}\mathbb{1}_{2}^{\sf
T}\in\mathbb{R}^{T\times T}$ and
${\mathbf{\Gamma}}^{t}={\mathbf{E}}_{tt}\otimes\mathbb{1}_{2}\mathbb{1}_{2}^{\sf
T}\in\mathbb{R}^{T\times T}$

  * •

$\bar{{\mathbf{\Omega}}}^{t}=\left({\mathbf{I}}_{2T}-{\mathbf{\Theta}}_{0}{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}\right)^{-1}\bar{{\mathbf{\Omega}}}_{0}^{t}\left({\mathbf{I}}_{2T}-{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}{\mathbf{\Theta}}_{0}\right)^{-1}\in\mathbb{R}^{2T\times
2T}$

  * •

$\bar{{\mathbf{\Omega}}}_{0}^{t}=\left[\left({\boldsymbol{\mathcal{A}}}{\mathcal{D}}_{{\mathbf{e}}_{t}^{[T]}+\bar{{\mathbf{r}}}^{t}}{\boldsymbol{\mathcal{A}}}\right)\otimes\mathbb{1}_{2}\mathbb{1}_{2}^{\sf
T}\right]\odot{\boldsymbol{\mathcal{M}}}\in\mathbb{R}^{2T\times 2T}$

  * •

${\mathbf{T}}^{t}={\mathcal{D}}_{\bar{{\mathbf{r}}}^{t}\odot\bar{{\boldsymbol{\eta}}}}\otimes\mathbb{1}_{2}\mathbb{1}_{2}^{\sf
T}\in\mathbb{R}^{2T\times 2T}$

  * •

${\mathbf{r}}^{t}={\boldsymbol{\rho}}\odot\left({\mathbf{S}}_{t.}\otimes\mathbb{1}_{2}\right)\in\mathbb{R}^{2T}$
and
$\bar{{\mathbf{r}}}^{t}=\bar{{\boldsymbol{\rho}}}\odot{\mathbf{S}}_{t.}\in\mathbb{R}^{T}$

  * •

${\mathbf{S}}=\bar{{\mathbf{S}}}\left({\mathbf{I}}_{T}-{\mathcal{D}}_{\bar{{\boldsymbol{\rho}}}}\bar{{\mathbf{S}}}\right)^{-1}\in\mathbb{R}^{T\times
T}$ with
$\bar{{\mathbf{S}}}_{tt^{\prime}}=\frac{{\boldsymbol{\mathcal{A}}}_{tt^{\prime}}^{2}}{T^{2}c(1-\delta^{t^{\prime}})^{2}}$

Beyond the cumbersome formulas, one can notice that the vector
${\mathbf{a}}_{j}^{t}$ and the matrix ${\mathbf{B}}^{t}$ are small dimensional
deterministic quantities that only depend on estimates, known parameters and
hyperparameters. Interestingly, even without analysing how
${\mathbf{a}}_{j}^{t}$ and ${\mathbf{B}}^{t}$ relate to the parameters of the
problem, one can take a look at the implication of the Theorem 3 on our
classification problem. The key information here is that the decision score
$f$ is asymptotically Gaussian with known parameters. These parameters are
mere functionals of the label vector $\tilde{{\mathbf{y}}}$. Therefore, a good
choice of $\tilde{{\mathbf{y}}}$ as well as $\zeta^{t}$ could lead to a lower
classification error. First of all, we need to precise which quantity we want
to minimize.

######  Definition 4.

For a given target task $t$, the classification error of any unlabeled sample
${\mathbf{x}}\in\mathcal{C}_{1}^{t}$ is

$\varepsilon_{1}^{t}=\mathbb{P}({\mathbf{x}}\to\mathcal{C}_{2}^{t}|{\mathbf{x}}\in\mathcal{C}_{1}^{t})$

Similarly, the classification error of any unlabeled sample
${\mathbf{x}}\in\mathcal{C}_{2}^{t}$ is

$\varepsilon_{2}^{t}=\mathbb{P}({\mathbf{x}}\to\mathcal{C}_{1}^{t}|{\mathbf{x}}\in\mathcal{C}_{2}^{t})$

######  Remark 5.

According to Theorem 3, and using the classification rule (11), the
classification errors of Definition 4 rewrite as:

$\varepsilon_{1}^{t}=\mathcal{Q}\left(\frac{\zeta^{t}-m_{1}^{t}}{\sigma^{t}}\right)\quad\text{and}\quad\varepsilon_{2}^{t}=\mathcal{Q}\left(\frac{m_{2}^{t}-\zeta^{t}}{\sigma^{t}}\right)$
(13)

with
$\mathcal{Q}(x)=\frac{1}{\sqrt{2\pi}}\int_{x}^{\infty}e^{-\frac{u^{2}}{2}}\,\mathrm{d}u$.
Thus, $\zeta^{t}\mapsto\varepsilon_{1}^{t}$ is a decreasing function, while
$\zeta^{t}\mapsto\varepsilon_{2}^{t}$ is an increasing function.

With this remark, we understand that the choice of the threshold $\zeta^{t}$
is a trade-off between the minimization of $\varepsilon_{1}^{t}$ and
$\varepsilon_{2}^{t}$, as displayed in Figure 1.

$f$ for ${\mathbf{x}}\in\mathcal{C}_{1}^{t}$$f$ for
${\mathbf{x}}\in\mathcal{C}_{2}^{t}$$\varepsilon_{2}^{t}$$\varepsilon_{1}^{t}$$\sigma^{t}$$\sigma^{t}$$m_{1}^{t}$$\zeta^{t}$$m_{2}^{t}$
Figure 1: Asymptotic probability distribution of the score function $f$ for
samples of both classes. The classification errors expressed in Remark 5 can
be interpreted as the area delimited by the density curve of $f$ and the
threshold $\zeta^{t}$.

$\zeta^{t}=m_{1}^{t}$ and $\zeta^{t}=m_{2}^{t}$ are extreme choices, where we
have respectively $\varepsilon_{1}^{t}=\frac{1}{2}$ and
$\varepsilon_{2}^{t}=\frac{1}{2}$. If $\zeta^{t}\notin[m_{1}^{t},m_{2}^{t}]$,
we have either $\varepsilon_{1}^{t}>\frac{1}{2}$ or
$\varepsilon_{2}^{t}>\frac{1}{2}$, which is not a desirable situation. So we
will assume starting from now that $\zeta^{t}\in[m_{1}^{t},m_{2}^{t}]$.
Interestingly, for any such choice of $\zeta^{t}$, the optimal label vector is
the same.

######  Proposition 6.

For a given target task $t$ and a given threshold
$\zeta^{t}\in[m_{1}^{t},m_{2}^{t}]$, there exists a unique (up to a
multiplicative constant) score vector $\tilde{{\mathbf{y}}}^{\star}$
minimizing $\varepsilon_{1}^{t}$ and $\varepsilon_{2}^{t}$, given as:

$\tilde{{\mathbf{y}}}^{\star}=({\mathbf{B}}^{t})^{-1}({\mathbf{a}}_{2}^{t}-{\mathbf{a}}_{1}^{t})$
(14)

This property provides the possibility, depending on the use of the algorithm,
to choose the threshold accordingly. Indeed, the choice of $\zeta^{t}$ can be
made in several different ways, allowing the user to tackle a wide variety of
classification problems. For example :

  * •

In a medical context, one could be interested to minimize the number of false
positive $\varepsilon_{1}^{t}$ while ensuring that the number of false
negative $\varepsilon_{2}^{t}$ is lower than a given threshold $p$ (for
example $p=1\%$). Then the optimal $\zeta^{t}$ is given by:

$\zeta^{t}=m_{2}^{t}-\sigma^{t}\mathcal{Q}^{-1}(p)$

  * •

One could also be interested in minimizing the overall classification error of
the dataset
$\frac{n_{u1}^{t}}{n_{u}^{t}}\varepsilon_{1}^{t}+\frac{n_{u2}^{t}}{n_{u}^{t}}\varepsilon_{2}^{t}$
(and therefore prioritize the classification of the most numerous class). Then
the optimal $\zeta^{t}$ is given by:

$\zeta^{t}=\frac{m_{1}^{t}+m_{2}^{t}}{2}+\frac{{\sigma^{t}}^{2}}{m_{2}^{t}-m_{1}^{t}}\log\left(\frac{n_{u1}^{t}}{n_{u2}^{t}}\right)$

  * •

If one wants to minimize undifferently $\varepsilon_{1}^{t}$ and
$\varepsilon_{2}^{t}$ (so that $\varepsilon_{1}^{t}=\varepsilon_{2}^{t}$),
then the optimal $\zeta^{t}$ is straightforwardly given by:

$\zeta^{t}=\frac{m_{1}^{t}+m_{2}^{t}}{2}$

This situation is a specific case of the previous one with
$n_{u1}^{t}=n_{u2}^{t}$. It can also be interpreted as minimizing the overall
classification error without any a priori on the genuine class of unlabeled
samples. We will focus on this last simple example to provide a lower bound of
the classification error.

######  Proposition 7.

For a given target task $t$, the minimal value of the classification error
$\varepsilon^{t}=\frac{\varepsilon_{1}^{t}+\varepsilon_{2}^{t}}{2}$ is
achieved with the optimal label $\tilde{{\mathbf{y}}}^{\star}$, and is
asymptotically given by:

$\varepsilon_{\star}^{t}=\mathcal{Q}\left(\frac{1}{2}\sqrt{({\mathbf{a}}_{2}^{t}-{\mathbf{a}}_{1}^{t})^{\sf
T}({\mathbf{B}}^{t})^{-1}({\mathbf{a}}_{2}^{t}-{\mathbf{a}}_{1}^{t})}\right),$
(15)

The proof of Propositions 6 and 7 are obtained from classical convex
optimization tools and provided for simplicity of exposition in the Sections B
and C of the appendix. We now see that the Theorem 3 provides us:

  * •

An optimal choice $\tilde{{\mathbf{y}}}^{\star}$ of the label vector
$\tilde{{\mathbf{y}}}$

  * •

The information we need to choose wisely the threshold $\zeta^{t}$

  * •

The optimal classification error $\varepsilon_{\star}^{t}$ for a specific
choice of $\zeta^{t}$

This leads to Algorithm 1, which summarizes the previous results and remarks.

Algorithm 1 Optimal algorithm

Input: labeled data
${\mathbf{X}}_{\ell}=[{\mathbf{X}}_{\ell}^{1},\dots,{\mathbf{X}}_{\ell}^{T}]$
and unlabeled data
${\mathbf{X}}_{u}=[{\mathbf{X}}_{u}^{1},\dots,{\mathbf{X}}_{u}^{T}]$

Output: Estimated class $\hat{j}\in\\{1,2\\}$ for unlabeled data of a given
target task $t$

Center data per task

Compute data matrices ${\mathbf{Z}}_{\ell}$ and ${\mathbf{Z}}_{u}$ from
${\mathbf{X}}_{\ell}$ and ${\mathbf{X}}_{u}$

Estimate matrix $\mathcal{M}$ (cf. Section D)

Create scores $\tilde{{\mathbf{y}}}^{\star}$ from (14) and $\Lambda$ from
(10).

Estimate the classification error $\varepsilon_{\star}^{t}$ according to (15)
and optimize with respect to $\alpha$ using a grid search approach.

Compute classification scores ${\mathbf{f}}_{u}$ according to (7).

Output:  $\hat{j}$ such that
$f_{i}\underset{\hat{j}=1}{\overset{\hat{j}=2}{\gtrless}}\frac{m_{1}^{t}+m_{2}^{t}}{2}$.

##  IV Uncertain labeling

In this section, we aim to extend the previous results to the case of
erroneous or uncertain data. Until now, the value of the label $y_{i}^{t}$ of
a given sample was either $\tilde{y}_{1}^{t}$ or $\tilde{y}_{2}^{t}$,
depending wether the sample was belonging to the class $\mathcal{C}_{1}^{t}$
or $\mathcal{C}_{2}^{t}$. Let us consider now that instead of knowing which
class the labeled sample belongs to, we have a couple
$(d_{i1}^{t},d_{i2}^{t})$ of pre-estimated probabilities that the sample
belongs to a class or to the other. The previous case is met if the couple is
either $(1,0)$ or $(0,1)$, the associated label value being
$\tilde{y}_{1}^{t}$ or $\tilde{y}_{2}^{t}$. For any other case, the value of
$y_{i}^{t}$ should be in the interval $]\tilde{y}_{1}^{t},\tilde{y}_{2}^{t}[$.
A natural choice is to set
$y_{i}^{t}=d_{i1}^{t}\tilde{y}_{1}^{t}+d_{i2}^{t}\tilde{y}_{2}^{t}$.
Therefore, we have ${\mathbf{y}}_{\ell}={\mathbf{D}}\tilde{{\mathbf{y}}}$,
with

${\mathbf{D}}=\sum\limits_{t=1}^{T}{\mathbf{E}}_{tt}^{[T]}\otimes\begin{pmatrix}d_{11}^{t}&d_{12}^{t}\\\
d_{21}^{t}&d_{22}^{t}\\\ \vdots&\vdots\\\
d_{n_{\ell}^{t}1}&d_{n_{\ell}^{t}2}\end{pmatrix}$ (16)

The results of Theorem 3 have to be adapted. In particular, we have to
introduce some statistics related to the couples of probabilities :

  * •

$\bar{d}_{j_{1},j_{2}}^{t}=\frac{1}{n_{\ell
j_{1}}^{t}}\sum_{i^{\prime}|x_{i^{\prime}}\in\mathcal{C}_{j_{1}}^{t}}d_{i^{\prime}j_{2}}^{t}$
the average probability for a genuine sample of class
$\mathcal{C}_{j_{1}}^{t}$ to be labeled in class $\mathcal{C}_{j_{1}}^{t}$. In
the ideal case, $\bar{d}_{j_{1},j_{2}}^{t}=\mathbb{1}_{j_{1}=j_{2}}$.

  * •

$\tilde{d}_{j_{1}j_{2}}^{t}=\frac{1}{n_{\ell}^{t}}\sum_{i|{\mathbf{x}}_{i}\in\mathcal{C}^{t}}d_{ij_{1}}^{t}d_{ij_{2}}^{t}$
which is a measure of the labeling uncertainty. If $j_{1}\neq j_{2}$ (resp.
$j_{1}=j_{2}$), a high value of $\tilde{d}_{j_{1}j_{2}}^{t}$ means a high
(resp. low) uncertainty.

This leads to the following small-dimensional quantities, related to the
matrix ${\mathbf{D}}$ :

$\displaystyle\bar{{\mathbf{D}}}$
$\displaystyle=\sum_{t=1}^{T}{\mathbf{E}}_{tt}\otimes\begin{pmatrix}\bar{d}_{11}^{t}&\bar{d}_{12}^{t}\\\
\bar{d}_{21}^{t}&\bar{d}_{22}^{t}\end{pmatrix},$
$\displaystyle\tilde{{\mathbf{D}}}$
$\displaystyle=\sum_{t=1}^{T}{\mathbf{E}}_{tt}\otimes\begin{pmatrix}\tilde{d}_{11}^{t}&\tilde{d}_{12}^{t}\\\
\tilde{d}_{21}^{t}&\tilde{d}_{22}^{t}\end{pmatrix}.$

######  Theorem 8.

Under Assumptions 1 and 2, and if labels are given by (16), for any unlabeled
sample ${\mathbf{x}}\in\mathcal{C}_{j}^{t}$, and $f$ being its associated
score,

$f\rightarrow\mathcal{N}\left(m_{j}^{t},{\sigma^{t}}^{2}\right)$

with $m_{j}^{t}=(1-\delta^{t}){{\mathbf{a}}_{j}^{t}}^{\sf
T}\tilde{{\mathbf{y}}}$ and
$\sigma^{t}=(1-\delta^{t})\sqrt{\tilde{{\mathbf{y}}}^{\sf
T}{\mathbf{B}}^{t}\tilde{{\mathbf{y}}}}$

$\displaystyle{\mathbf{a}}_{j}^{t}$
$\displaystyle=\left({{\mathbf{e}}_{t,j}^{[2T]}}^{\sf
T}\left({\mathbf{\Theta}}-\frac{Tc\delta^{t}}{\rho^{t}}{\mathbf{\Gamma}}\right){\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}{\mathcal{D}}_{{\boldsymbol{\eta}}}\bar{{\mathbf{D}}}\right)^{\sf
T}$ $\displaystyle{\mathbf{B}}^{t}$ $\displaystyle=\bar{{\mathbf{D}}}^{\sf
T}{\mathcal{D}}_{{\boldsymbol{\eta}}}\left[2{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}\left({\mathbf{\Theta}}-\frac{Tc\delta^{t}}{\rho^{t}}{\mathbf{\Gamma}}\right)-{\mathbf{\Gamma}}^{t}\right]{\mathcal{D}}_{{\mathbf{r}}^{t}}{\mathcal{D}}_{{\boldsymbol{\eta}}}\bar{{\mathbf{D}}}$
$\displaystyle+\bar{{\mathbf{D}}}^{\sf
T}{\mathcal{D}}_{{\boldsymbol{\eta}}}{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}\left({\mathbf{\Theta}}{\mathcal{D}}_{{\mathbf{r}}^{t}}{\mathbf{\Theta}}+\bar{{\mathbf{\Omega}}}^{t}-\left(\frac{Tc\delta^{t}}{\rho^{t}}\right)^{2}{\mathbf{\Gamma}}^{t}\right){\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}{\mathcal{D}}_{{\boldsymbol{\eta}}}\bar{{\mathbf{D}}}$
$\displaystyle+{\mathbf{T}}^{t}\odot\tilde{{\mathbf{D}}}$

The Theorem 3 is a particular case of the Theorem 8, with
$\bar{{\mathbf{D}}}={\mathbf{I}}_{2T}$ and
$\tilde{{\mathbf{D}}}={\mathcal{D}}_{{\boldsymbol{\rho}}\odot{\boldsymbol{\eta}}}{\mathcal{D}}_{(\bar{{\boldsymbol{\rho}}}\odot\bar{{\boldsymbol{\eta}}})\otimes\mathbb{1}_{2}}^{-1}$.

##  V Limitations

###  V-A Multiclass setting

The paper focuses on a binary setting. There are some known methods to deal
with a higher number of classes, such as _one-vs-all_ and _one-vs-one_ [18,
19]. These methods can be roughly implemented in our case, but each one has
some limitations. In this paragraph, $m>2$ will denote the number of classes.

  * •

One-vs-all : $m$ binary classifiers are trained, each one separating one class
$\mathcal{C}_{j}$ from the other $m-1$ classes. Each new sample is then
classified into the class with the highest score among the $m$ classifiers.
The computations of Theorem 3 can be easily adapted to these classifiers, but
this approach has several issues :

    * –

Each classifier has its own bias, making impossible a fair comparison between
the output scores. To work well, this method implicitly makes the assumption
that for all $1\leq j\leq m$, the output distribution of the classifier
$\mathcal{C}_{j}$-vs-all on samples from class $\mathcal{C}_{j}$ is the same.
One way to tackle this problem is to normalize the distribution (_i.e.,_
consider $\frac{f_{i}^{t}-m_{j}^{t}}{\sigma^{t}}$ instead of $f_{i}^{t}$), but
the algorithm then depends too heavily on the estimations of $m_{j}^{t}$ and
$\sigma^{t}$, affecting its robustness.

    * –

The optimal score vector $\tilde{{\mathbf{y}}}^{\star}$ does not have an
explicit formula, as the quantity to maximize is not a quadratic form of
$\tilde{{\mathbf{y}}}$ anymore (see Section B of the appendix). As such, one
needs to approximate the quantity to maximize, therefore losing the
optimality.

  * •

One-vs-one : $\frac{1}{2}m(m-1)$ binary classifiers are trained, each one
separating one class $\mathcal{C}_{j}$ from an other class
$\mathcal{C}_{j^{\prime}}$. For every sample of unlabeled data, each one of
these classifiers ”votes” for the class the most relevant among the two that
it compares. Then, the sample is attributed to the class collecting the most
votes. This approach also comes with several issues :

    * –

To train a binary classifier $\mathcal{C}_{j}$-vs-$\mathcal{C}_{j^{\prime}}$,
one can get rid of labeled data from other classes, but not unlabeled data. As
such, the unsupervised part of the algorithm will still make use of the
unlabeled data of other classes and change the outcome of the score function,
necessarily introducing a new bias. However, results of Theorem 3 can be
adapted to this situation.

    * –

The number of one-vs-one classifiers to train is a quadratic function of the
number of classes, while the number of one-vs-all classifiers was a linear
function of the number of classes. With a high number of classes, the one-vs-
one method is therefore much slower.

To our knowledge, one-vs-one is the only method able to keep the optimality we
have in the binary case. The major issue is that a high number of classes
makes the method heavy to use.

###  V-B Lack of labeled data

Even if the model is designed to work for any number of labeled and unlabeled
data, in practice it cannot do without a minimum number of labeled data. First
of all, if there is no labeled data at all (as it would be the case in a
purely unsupervised setting), the score vector ${\mathbf{f}}$ would be zero as
the label vector ${\mathbf{y}}$ would be zero itself. Most importantly,
labeled data is needed to perform the estimation of
${\boldsymbol{\mathcal{M}}}$ and ${\mathbf{\Lambda}}$. If labeled data is too
scarce, the algorithm could be misleaded by the estimated values of
${\boldsymbol{\mathcal{M}}}$ and ${\mathbf{\Lambda}}$, implying poor
performances.

##  VI Experiments

The experiments displayed in this section are done on both synthetic and real-
world datasets. With Gaussian synthetic data, we simulate different learning
settings, in order to convey some intuition on the different aspects of our
model : multi-task learning, semi-supervised learning, uncertain labeling,
floating labels… Meanwhile, the purpose of real-data experiments is to show
that our algorithm is robust enough to keep its properties on dataset that are
not isotropic Gaussian vectors anymore. The code used to genereate the
following experiments is available at https://gricad-gitlab.univ-grenoble-
alpes.fr/legervi/tsp

###  VI-A Multitask experiments

This section investigates the influence of task correlation on the
performances of our algorithm. To do so, we consider a case of transfer
learning between a source task and a target task. The source and target tasks
are mixtures of two Gaussians:
$\mathcal{N}(\pm{\boldsymbol{\mu}},{\mathbf{I}}_{p})$ for the source and
$\mathcal{N}(\pm(\beta{\boldsymbol{\mu}}+\sqrt{1-\beta^{2}}{\boldsymbol{\mu}}^{\perp}),{\mathbf{I}}_{p})$
for the target, where ${\boldsymbol{\mu}}^{\perp}$ is a vector orthogonal to
the vector ${\boldsymbol{\mu}}$. This setting allows through $\beta$ to
control the similarity between both tasks. Specifically, for $\beta=0$ the
tasks are unrelated while for $\beta=1$ they are identical. Note that
$\beta=-1$ corresponds to a scenario where the classes of target and source
tasks are reversed.

Figure 2 displays the empirical versus theoretical classification error of our
algorithm as a function of $\beta$ for the optimized method (which integrates
the label and hyperparameter optimization) against the naive method which
leaves the labels ($\pm 1$) untouched. The values of the optimal labels are
displayed jointly in the top figure.

We also provide an optimal bound of performance established by information
theory in [20]. This bound corresponds to the best performance achievable by
any algorithm given the setting of our experiment. The figure clearly shows
that our proposed optimized algorithm is extremely close to the information-
theoretic optimum under our Assumptions 1 and 2. The close fit between
theoretical and empirical performances confirms Proposition 7 even for finite-
dimensional data.

We also observe a strong robustness of our method to negative transfer.
Indeed, when $\beta$ becomes negative, the error increases for the naive
algorithm, while our proposed method is insensitive to the sign of $\beta$ by
a dynamic adaptation of the labels. The top figure shows the sign inversion of
$\tilde{y}_{1}^{2}$ and $\tilde{y}_{2}^{2}$ when $\beta$ becomes negative. In
the specific case where $\beta=-1$, our algorithm has the same performance as
with $\beta=1$, while the naive “conventional” approach gets worse than random
guess. Besides, when $\beta$ is close to $0$, the labels of the source task
have low magnitude, because there is no much information to get from source
task.

$-1$$-0.8$$-0.6$$-0.4$$-0.2$$0$$0.2$$0.4$$0.6$$0.8$$1$$0.35$$0.4$$0.45$$0.5$$0.55$$0.6$$0.65$$\beta$
(correlation between tasks)Classification errorNaive (Emp)Naive
(Th)Optimal(Emp)Optimal(Th)Best achievable
performance$-1$$-0.8$$-0.6$$-0.4$$-0.2$$0$$0.2$$0.4$$0.6$$0.8$$1$$-1.5$$-1$$-0.5$$0$$0.5$$1$$1.5$Optimal
labels
$\tilde{y}$$\tilde{y}_{1}^{1}$$\tilde{y}_{2}^{1}$$\tilde{y}_{1}^{2}$$\tilde{y}_{2}^{2}$$-1$$+1$
Figure 2: Joint evolution of optimal labeling and classification error as a
function of correlation between tasks ($p=200$, $n_{\ell}^{1}=100$,
$n_{\ell}^{2}=1000$, $n_{u}^{1}=n_{u}^{2}=250$). (Top) Optimal labels with
normalization $\|\tilde{{\mathbf{y}}}\|=1$. Optimal labels adapt themselves to
avoid negative transfer (Bottom) Classification error for both naive and
optimal algorithms. Our algorithm is close to optimal, while naive labels
induce a negative transfer when tasks are not related enough.

###  VI-B Class imbalances

In the previous experiment, the number of data in each class was the same.
However, our adaptive labeling is also useful to deal with class imbalances.
Indeed, labels can be interpreted as weights, which should naturally be higher
for underrepresented classes. We will consider a single-task learning scenario
with a fixed amount of data. While the number of unlabeled data is equal for
both classes, the number of labeled data is unbalanced.

As such, Figure 3 displays the classification error as a function of the
number of labeled data in class $\mathcal{C}_{1}$, jointly with the values of
the optimal labels (top figure). We also display the value of the optimal
threshold $\zeta=\frac{m_{1}+m_{2}}{2}$, which ensures that the probability of
misclassifying each sample is the same whether this sample is in a class or in
the other. As expected, the label value of the least represented class is
higher, as each labeled sample belonging to this class carries more
information. Because of the imbalance, the means of the two classes are not
symetrical about zero anymore, and the threshold value must be changed.

In the naive setting, without our choice of threshold, the classification
error for samples from the most represented class is much higher. As a
consequence, the average classification error is higher overall.

$100$$200$$300$$400$$500$$600$$700$$800$$900$$-1.5$$-1$$-0.5$$0$$0.5$$1$$1.5$Optimal
labels
$\tilde{y}$$\tilde{y}_{1}$$\tilde{y}_{2}$$\zeta$$-1$$+1$$0$$0$$100$$200$$300$$400$$500$$600$$700$$800$$900$$1{,}000$$5\cdot
10^{-2}$$0.1$$0.15$$0.2$$0.25$$0.3$$0.35$$0.4$$n_{\ell_{1}}$ (labeled data in
class $\mathcal{C}_{1}$)Classification errorNaive $\mathcal{C}_{1}$Naive
$\mathcal{C}_{2}$Naive avgOptimal $\mathcal{C}_{1}$ Optimal $\mathcal{C}_{2}$
Figure 3: Joint evolution of optimal labeling and classification error as a
function of the number of labeled data in class $\mathcal{C}_{1}$. The total
number of labeled data is constant ($n_{\ell}=n_{\ell 1}+n_{\ell 2}=1000$,
$p=200$, $n_{u1}=n_{u2}=200$). (Top) Optimal labels with normalization
$\|\tilde{{\mathbf{y}}}\|=1$, and optimal threshold $\zeta$ (also normalized).
Optimal labels adapt themselves to compensate the class imbalances (Bottom)
Theoretical and empirical classification error for both naive and optimal
labels and threshold. The overall error is better with our algorithm, while
naive labels and threshold induce a high error for the most represented class.

###  VI-C Uncertain labeling

As for now, the labeled data used in the experiments was assumed to be labeled
without any mistake or imprecision. To simulate a case where labeled data
suffers such imprecision, we will separate the labeled data in two categories
:

  * •

reliable data, labeled in a class with absolute certainty.

  * •

imprecise data, for which there is a probability $r<1$ that the data genuinely
belongs to the class it has been labeled in (and therefore a probability $1-r$
that it belongs in fact to the other class).

To simplify the setting, we assume that all the imprecise data has the same
value $r$ of reliability. $n_{i}$ will denote the number of imprecise data,
while $n_{r}$ will denote the number of reliable data. In order to measure how
useful imprecise data is to solve our problem, one could ask the following
question : for a given value of $n_{r}$, if imprecise data is used instead of
reliable data, how many samples $n_{i}$ are needed to reach the same
performance ? The first thing we notice, through Figure 4, is that the number
of imprecise data needed to reach that performance is a linear function of the
number of reliable data used in the first place.

Therefore, the ratio $\frac{n_{r}}{n_{i}}$ seems to be a relevant quantity to
compute. It can be interpreted as a measure of the strength of imprecise data
compared to reliable data. The higher this ratio is, the more information is
brought by imprecise samples. $\frac{n_{r}}{n_{i}}=0$ means that imprecise
samples are not useful at all, while $\frac{n_{r}}{n_{i}}=1$ means that
imprecise samples are as useful as reliable samples. Figure 5 displays this
ratio for different values of reliability $r$ and difficulty of the task
(expressed through the quantity
$D=\frac{1}{\|{\boldsymbol{\mu}}_{1}-{\boldsymbol{\mu}}_{2}\|}$).

$0$$50$$100$$150$$200$$250$$300$$350$$400$$0$$200$$400$$600$$800$$n_{r}$
(reliable data)$n_{i}$ (imprecise data)$r=0.5$$r=0.6$$r=0.75$$r=0.9$$r=1$
Figure 4: Number of imprecise data $n_{i}$ needed to reach the same
performance one had using $n_{r}$ samples of reliable data, for different
values of $r$ ($1$-task, $p=200$, $n_{u1}=n_{u2}=200$). For each point,
$n_{r}$ is a random number between $20$ and $400$. The figure strongly
suggests that $n_{i}$ is a linear function of $n_{r}$.
$0.45$$0.5$$0.55$$0.6$$0.65$$0.7$$0.75$$0.8$$0.85$$0.9$$0.95$$1$$1.05$$0.3$$0.4$$0.5$$0.6$$0.7$$0.8$$0.9$$1$$r$
(reliability of imprecise data)Ratio
$n_{r}$/$n_{i}$$D=0.25$$D=0.50$$D=0.75$$0.25$$0.5$$0.75$$1$$1.25$$1.5$$0.2$$0.4$$0.6$$0.8$$1$$D$
(difficulty of the task)Ratio $n_{r}$/$n_{i}$$r=0.5$$r=0.7$$r=0.9$ Figure 5:
Ratio $\frac{n_{r}}{n_{i}}$ for different values of reliability ($r$) and
difficulty of the task
($D=1/\|{\boldsymbol{\mu}}_{1}-{\boldsymbol{\mu}}_{2}\|$). The higher the
ratio is, the more effective is the contribution of imprecise samples to the
task. Both figures show that the harder the task is, the least useful
imprecise samples are. However, an increasing of $r$ leads to significantely
better results. (Top) Ratio $\frac{n_{r}}{n_{i}}$ as a function of the
reliability of imprecise data, for different values of difficulty. (Bottom)
Ratio $\frac{n_{r}}{n_{i}}$ as a function of the difficulty of the task, for
different values of reliability.

###  VI-D Real data experiments

The purpose of this section is to check that our algorithm still performs well
on real data, which does not necessarily follow Assumption 1. The data is
generated with normalized VGG-features [21] of randomly BigGAN-generated
images [22]. If GANs are known to produce concentrated vectors [14], the
covariance is unlikely to be isotropic. However, thanks to the robustness of
our method, we still have some reasonably good performances. In the following
figures, only the empirical classification error is displayed, as the
theoretical values are not relevant for this real data setting.

In the Figure 7, we consider a transfer-learning setting with $2$ similar
tasks (`doberman` vs `entlebucher` and `appenzeler` vs `rottweiler`, for which
examples are displayed in Figure 6) and with classes purposely inverted
between the tasks (similarly to the case $\beta=-1$ of Section VI-A).
Naturally, the naive algorithm suffers from a huge negative transfer, while
optimal labeling ensures a low error. The same tasks are used in Figure 8 to
compare $1$-task and $2$-task learning (with our optimal algorithm). While the
number of labeled data in the source task is constant, we add labeled data in
the target task. The error of the single-task algorithm decreases, but remains
higher than the multi-task algorithm, which benefits from the numerous data of
the second task. To simplify the interpretation, the fully-supervised
algorithm is considered.

A third experiment is made with a semi-supervised setting, to which we compare
the purely supervised method. Figure 9 shows the performances for the task
`boxer` vs `greater swiss mountain dog` as a function of the number of
unlabeled data. The error of the supervised method is logically constant,
while the semi-supervised algorithm benefits from the new unlabeled samples.

|  |  |
---|---|---|---
|  |  |
|  |  |
Figure 6: Examples of BigGAN-generated images used for the experiment. From
left to right : doberman (Class $\mathcal{C}_{1}^{1}$), entlebucher (Class
$\mathcal{C}_{2}^{1}$), appenzeler (Class $\mathcal{C}_{1}^{2}$) and
rottweiler (Class $\mathcal{C}_{2}^{2}$). entlebucher and appenzeler are
close, as well as doberman and rottweiler.
$8$$10$$12$$14$$16$$18$$20$$22$$24$$26$$28$$30$$32$$34$$36$$38$$40$$42$$0$$0.2$$0.4$$0.6$$0.8$$n_{\ell}^{2}$Classification
errorNaive (Emp)Optimal (Emp) Figure 7: Empirical classification error, for
both naive and optimal labels, as a function of the number of labeled data in
source task, for BigGAN-generated images. (doberman vs entlebucher and
appenzeler vs rottweiler, $p=4096$, $n_{\ell}^{1}=20$, $n_{u}^{1}=200$ and
$n_{u}^{2}=0$). The naive labels induce a huge negative transfer, while
optimal labels keep the error at low level.
$5$$10$$15$$20$$25$$30$$35$$40$$0.05$$0.10$$0.15$$n_{\ell}^{1}$Classification
errorSingle-task (Emp)Multi-task (Emp) Figure 8: Empirical classification
error, for $1$-task and $2$-task learning, as a function of the number of
labeled data in target task, for BigGAN-generated images. (doberman vs
entlebucher and appenzeler vs rottweiler, $p=4096$, $n_{\ell}^{2}=100$,
$n_{u}^{1}=200$ and $n_{u}^{2}=0$). The multi-task setting takes advantage of
the labeled data from source task.
$0$$200$$400$$600$$800$$1{,}000$$1{,}200$$1{,}400$$1{,}600$$1{,}800$$2{,}000$$2{,}200$$2{,}400$$2{,}600$$2{,}800$$3{,}000$$3{,}200$$1.5$$2$$2.5$$\cdot
10^{-2}$$n_{u}$Classification errorSupervised (Emp)Semi-supervised (Emp)
Figure 9: Empirical classification error for fully-supervised and semi-
supervised algorithms, as a function of the number of unlabeled data. (BigGAN-
generated images boxer vs great swiss mountain dog, $p=4096$, $n_{\ell}=10$).
As expected, the error is constant with the fully-supervised algorithm, while
the semi-supervised version benefits from additional unlabeled data.

##  VII Concluding remarks

Thanks to its simplicity, the algorithm presented in this article allows an
extensive mathematical analysis, which makes it at once robust, powerful and
interpretable. Indeed, the comparison of the empirical error with the optimum-
theoretic bound indicates that the algorithm reaches satisfying performances,
and the basic assumptions made still allow it to perform well on real data.

Our algorithm is therefore accessible to its users and is even able to bring
them further knowledge. More precisely :

  * •

the label vector $\tilde{{\mathbf{y}}}$ informs the users on potential biases
in the dataset, and helps them quantify how useful an additional task would be
to solve the initial problem;

  * •

the combined knowledge of the performance and the information-theoretic bound
helps understand how difficult a problem is, and how far from optimal the
associated performance lies;

  * •

the experiments enlighten the users about the expected improvements of
performance with additional labeled or unlabeled data, or when controversial
data is used.

As such, our method does not intend to compete with state-of-the-art
algorithms, but rather guarantees sufficient performances. In accordance with
the base “convivality” principles enunciated in the introduction, our future
investigations will not aim at any further complexification and improvement of
the present method; rather, we will seek for further simplification and
accessibility: the random matrix framework remains indeed quite opaque to
most, which still constitutes an accessibility hurdle we should seek to
overtake. Options lie in exploiting alternative tools from the mathematical,
and even preferrably from the statistical physics, litterature in order to
retrieve our technical results from a more direct and more intuitive path
(which for instance the non-rigorous but much simpler replica methods may
offer).

##  Appendix A Solution of the optimization problem

First of all, we need to clarify why (4) is equivalent to (5).

$\displaystyle\sum\limits_{t,t^{\prime}=1}^{T}\Lambda^{tt^{\prime}}\sum\limits_{i=1}^{n^{t}}\sum\limits_{i^{\prime}=1}^{n^{t^{\prime}}}\hat{\omega}_{ii^{\prime}}^{tt^{\prime}}\left(f_{i}^{t}-f_{i^{\prime}}^{t^{\prime}}\right)^{2}$
$\displaystyle=$
$\displaystyle\sum\limits_{t,t^{\prime}=1}^{T}\Lambda^{tt^{\prime}}\sum\limits_{i=1}^{n^{t}}\sum\limits_{i^{\prime}=1}^{n^{t^{\prime}}}\left[\hat{\omega}_{ii^{\prime}}^{tt^{\prime}}\left((f_{i}^{t})^{2}-(f_{i^{\prime}}^{t^{\prime}})^{2}\right)-2f_{i}^{t}\hat{\omega}_{ii^{\prime}}^{tt^{\prime}}f_{i^{\prime}}^{t^{\prime}}\right]$
$\displaystyle=$
$\displaystyle\sum\limits_{t,t^{\prime}=1}^{T}\Lambda^{tt^{\prime}}\left(\sum\limits_{i=1}^{n^{t}}(f_{i}^{t})^{2}\underbrace{\sum\limits_{i^{\prime}=1}^{n^{t^{\prime}}}\hat{\omega}_{ii^{\prime}}^{tt^{\prime}}}_{=0}+\sum\limits_{i^{\prime}=1}^{n^{t^{\prime}}}(f_{i^{\prime}}^{t^{\prime}})^{2}\underbrace{\sum\limits_{i=1}^{n^{t}}\hat{\omega}_{ii^{\prime}}^{tt^{\prime}}}_{=0}\right)$
$\displaystyle-2\sum\limits_{t,t^{\prime}=1}^{T}\Lambda^{tt^{\prime}}\sum\limits_{i=1}^{n^{t}}\sum\limits_{i^{\prime}=1}^{n^{t^{\prime}}}f_{i}^{t}\hat{\omega}_{ii^{\prime}}^{tt^{\prime}}f_{i^{\prime}}^{t^{\prime}}$
$\displaystyle=$
$\displaystyle-2\sum\limits_{t,t^{\prime}=1}^{T}\Lambda^{tt^{\prime}}{{\mathbf{f}}^{t}}^{\sf
T}\hat{{\mathbf{W}}}^{tt^{\prime}}{\mathbf{f}}^{t^{\prime}}=-2{\mathbf{f}}^{\sf
T}\hat{{\mathbf{W}}}{\mathbf{f}}$

Therefore

$\eqref{eq:opti_pb_2}\Leftrightarrow\min\limits_{\mathbf{f}^{1},\ldots,\mathbf{f}^{T}}-2{\mathbf{f}}^{\sf
T}\hat{{\mathbf{W}}}{\mathbf{f}}+2\alpha\left(\|{\mathbf{f}}_{\ell}-{\mathbf{y}}_{\ell}\|^{2}+\|{\mathbf{f}}_{u}\|^{2}\right)\Leftrightarrow\eqref{eq:opti_pb_3}$

The optimization problem we need to solve is

$\min\limits_{{\mathbf{f}}\in\mathbb{R}^{n}}\alpha\|{\mathbf{f}}-{\mathbf{y}}\|^{2}-{{\mathbf{f}}}^{{\sf
T}}\tilde{{\mathbf{W}}}{\mathbf{f}}\Leftrightarrow\min\limits_{{\mathbf{f}}\in\mathbb{R}^{n}}{{\mathbf{f}}}^{{\sf
T}}\left(\alpha{\mathbf{I}}_{n}-\tilde{{\mathbf{W}}}\right){\mathbf{f}}-2\alpha{\mathbf{f}}^{{\sf
T}}{\mathbf{y}}\\\ $

The problem is convex as long as $\alpha>\|\tilde{{\mathbf{W}}}\|$, ensuring
$\alpha{\mathbf{I}}_{n}-\tilde{{\mathbf{W}}}$ to be positive definite. We
assume that this condition is satisfied. The quantity to minimize is a
quadratic form of ${\mathbf{f}}$, so the solution of the optimization problem
satisfies:

$\displaystyle\min\limits_{{\mathbf{f}}\in\mathbb{R}^{n}}\alpha\|{\mathbf{f}}-{\mathbf{y}}\|^{2}-{{\mathbf{f}}}^{{\sf
T}}\tilde{{\mathbf{W}}}{\mathbf{f}}\Leftrightarrow\left(\alpha{\mathbf{I}}_{n}-\tilde{{\mathbf{W}}}\right){\mathbf{f}}-\alpha{\mathbf{y}}=0$
$\displaystyle\Leftrightarrow{\mathbf{f}}=\left({\mathbf{I}}_{n}-\frac{\tilde{{\mathbf{W}}}}{\alpha}\right)^{-1}{\mathbf{y}}\Leftrightarrow{\mathbf{f}}=\left({\mathbf{I}}_{n}-\frac{{{\mathbf{Z}}}^{{\sf
T}}{\mathbf{A}}{\mathbf{Z}}}{Tp}\right)^{-1}{\mathbf{y}}$

Indeed,

$\displaystyle\frac{\tilde{{\mathbf{W}}}}{\alpha}$
$\displaystyle=\sum_{t,t^{\prime}=1}^{T}\tilde{\Lambda}^{tt^{\prime}}{\mathbf{E}}_{tt^{\prime}}\otimes\hat{{\mathbf{W}}}^{tt^{\prime}}=\frac{1}{Tp}\sum_{t,t^{\prime}=1}^{T}\tilde{\Lambda}^{tt^{\prime}}{\mathbf{E}}_{tt^{\prime}}\otimes({{\mathbf{X}}^{t}}^{\sf
T}{\mathbf{X}}^{t^{\prime}})$
$\displaystyle=\frac{1}{Tp}\sum_{t,t^{\prime}=1}^{T}({\mathbf{E}}_{tt}\otimes{{\mathbf{X}}^{t}})^{\sf
T}(\tilde{{\mathbf{\Lambda}}}\otimes{\mathbf{I}}_{p})({\mathbf{E}}_{t^{\prime}t^{\prime}}\otimes{\mathbf{X}}^{t^{\prime}})=\frac{{{\mathbf{Z}}}^{{\sf
T}}{\mathbf{A}}{\mathbf{Z}}}{Tp}$

##  Appendix B Proof of Proposition 6

$\zeta^{t}\in[m_{1}^{t},m_{2}^{t}]$ so there exists $\lambda\in[0,1]$ such
that:

$\zeta^{t}=\lambda m_{1}^{t}+(1-\lambda)m_{2}^{t}$
$\displaystyle\varepsilon_{1}^{t}$
$\displaystyle=\mathcal{Q}\left(\frac{\zeta^{t}-m_{1}^{t}}{\sigma^{t}}\right)=\mathcal{Q}\left((1-\lambda)\frac{m_{2}^{t}-m_{1}^{t}}{\sigma^{t}}\right)$
$\displaystyle\varepsilon_{2}^{t}$
$\displaystyle=\mathcal{Q}\left(\frac{m_{2}^{t}-\zeta^{t}}{\sigma^{t}}\right)=\mathcal{Q}\left(\lambda\frac{m_{2}^{t}-m_{1}^{t}}{\sigma^{t}}\right)$

$\mathcal{Q}$ is a decreasing function, so in order to minimize
$\varepsilon_{1}^{t}$ and $\varepsilon_{2}^{t}$, one needs to maximize
$\frac{m_{2}^{t}-m_{1}^{t}}{\sigma^{t}}$, or equivalently the following
quantity:

$\left(\frac{m_{2}^{t}-m_{1}^{t}}{\sigma^{t}}\right)^{2}=\frac{(\tilde{{\mathbf{y}}}^{\sf
T}({\mathbf{a}}_{2}^{t}-{\mathbf{a}}_{1}^{t}))^{2}}{\tilde{{\mathbf{y}}}^{\sf
T}{\mathbf{B}}^{t}\tilde{{\mathbf{y}}}}$ (17)

Then the optimal scores rewrite (up to a multiplicative constant) as

$\operatorname*{arg\,max}_{\tilde{{\mathbf{y}}}}\frac{(\tilde{{\mathbf{y}}}^{\sf
T}({\mathbf{a}}_{2}^{t}-{\mathbf{a}}_{1}^{t}))^{2}}{\tilde{{\mathbf{y}}}^{\sf
T}{\mathbf{B}}^{t}\tilde{{\mathbf{y}}}}=({\mathbf{B}}^{t})^{-1}({\mathbf{a}}_{2}^{t}-{\mathbf{a}}_{1}^{t})$

##  Appendix C Proof of Proposition 7

To minimize
$\varepsilon^{t}=\frac{\varepsilon_{1}^{t}+\varepsilon_{2}^{t}}{2}$, the
optimal threshold is $\zeta^{t}=\frac{m_{1}^{t}+m_{2}^{t}}{2}$.

$\varepsilon^{t}=\frac{1}{2}\mathcal{Q}\left(\frac{\zeta^{t}-m_{1}^{t}}{\sigma^{t}}\right)+\frac{1}{2}\mathcal{Q}\left(\frac{m_{2}^{t}-\zeta^{t}}{\sigma^{t}}\right)=\mathcal{Q}\left(\frac{m_{2}^{t}-m_{1}^{t}}{2\sigma^{t}}\right)$

As stated in Proposition 6, the minimum value of $\varepsilon^{t}$ is achieved
with
$\tilde{{\mathbf{y}}}^{\star}=({\mathbf{B}}^{t})^{-1}(a_{2}^{t}-a_{1}^{t})$,
which leads to

$\displaystyle m_{2}^{t}-$ $\displaystyle m_{1}^{t}=(a_{2}^{t}-a_{1}^{t})^{\sf
T}{\mathbf{B}}^{t})^{-1}(a_{2}^{t}-a_{1}^{t})$ $\displaystyle\sigma^{t}$
$\displaystyle=\sqrt{(a_{2}^{t}-a_{1}^{t})^{\sf
T}({\mathbf{B}}^{t})^{-1}(a_{2}^{t}-a_{1}^{t})}$

Finally, we have

$\varepsilon_{\star}^{t}=\mathcal{Q}\left(\frac{1}{2}\sqrt{(a_{2}^{t}-a_{1}^{t})^{\sf
T}({\mathbf{B}}^{t})^{-1}(a_{2}^{t}-a_{1}^{t})}\right)$

##  Appendix D Estimation of ${\mathbf{M}}^{\sf T}{\mathbf{M}}$

To estimate the matrix ${\boldsymbol{\mathcal{M}}}={\mathbf{M}}^{\sf
T}{\mathbf{M}}$, one only needs to estimate quantities such as
$\theta={\boldsymbol{\mu}}_{1}^{\sf T}{\boldsymbol{\mu}}_{2}$. To estimate
these quantities, we use the following unbiaised estimator :

$\hat{\theta}=\frac{1}{n_{1}n_{2}}\mathbb{1}_{n_{1}}^{\sf
T}{\mathbf{X}}_{1}^{\sf T}{\mathbf{X}}_{2}\mathbb{1}_{n_{2}}$

where
$({\mathbf{X}}_{j})_{.,i}\sim\mathcal{N}({\boldsymbol{\mu}}_{j},{\mathbf{I}}_{p})$

$\hat{\theta}=\frac{1}{n_{1}n_{2}}\mathbb{1}_{n_{1}}^{\sf
T}\left(\mathbb{1}_{n_{1}}{\boldsymbol{\mu}}_{1}^{\sf T}+{\mathbf{V}}_{1}^{\sf
T}\right)\left({\boldsymbol{\mu}}_{2}\mathbb{1}_{n_{2}}^{\sf
T}+{\mathbf{V}}_{2}\right)\mathbb{1}_{n_{2}}$

where $({\mathbf{V}}_{j})_{.,i}\sim\mathcal{N}(0,{\mathbf{I}}_{p})$
To compute the law of $\hat{\theta}$, we will use the two following facts:

######  Lemma 9.

$\frac{1}{\sqrt{n_{j}}}{\mathbf{V}}_{j}\mathbb{1}_{n_{j}}\sim\mathcal{N}(0,{\mathbf{I}}_{p})$

######  Lemma 10.

If ${\mathbf{u}},{\mathbf{v}}\sim\mathcal{N}(0,{\mathbf{I}}_{p})$ and are
independant, then

$\frac{1}{\sqrt{p}}{\mathbf{u}}^{\sf T}{\mathbf{v}}\sim\mathcal{N}(0,1)$

$\displaystyle\hat{\theta}$
$\displaystyle=\frac{1}{n_{1}n_{2}}\mathbb{1}_{n_{1}}^{\sf
T}\left(\mathbb{1}_{n_{1}}{\boldsymbol{\mu}}_{1}^{\sf T}+{\mathbf{V}}_{1}^{\sf
T}\right)\left({\boldsymbol{\mu}}_{2}\mathbb{1}_{n_{2}}^{\sf
T}+{\mathbf{V}}_{2}\right)\mathbb{1}_{n_{2}}$
$\displaystyle=\left({\boldsymbol{\mu}}_{1}+\frac{1}{n_{1}}{\mathbf{V}}_{1}\mathbb{1}_{n_{1}}\right)^{\sf
T}\left({\boldsymbol{\mu}}_{2}+\frac{1}{n_{2}}{\mathbf{V}}_{2}\mathbb{1}_{n_{2}}\right)$
$\displaystyle=\left({\boldsymbol{\mu}}_{1}+\frac{1}{\sqrt{n_{1}}}{\mathbf{u}}_{1}\right)^{\sf
T}\left({\boldsymbol{\mu}}_{2}+\frac{1}{\sqrt{n_{2}}}{\mathbf{u}}_{2}\right)$
$\displaystyle\text{with}\quad{\mathbf{u}}_{1},{\mathbf{u}}_{2}\sim\mathcal{N}(0,{\mathbf{I}}_{p})$
$\displaystyle={\boldsymbol{\mu}}_{1}^{\sf
T}{\boldsymbol{\mu}}_{2}+\frac{1}{\sqrt{n_{2}}}{\boldsymbol{\mu}}_{1}^{\sf
T}{\mathbf{u}}_{2}+\frac{1}{\sqrt{n_{1}}}{\mathbf{u}}_{1}^{\sf
T}{\boldsymbol{\mu}}_{2}+\frac{1}{\sqrt{n_{1}n_{2}}}{\mathbf{u}}_{1}^{\sf
T}{\mathbf{u}}_{2}$ $\displaystyle={\boldsymbol{\mu}}_{1}^{\sf
T}{\boldsymbol{\mu}}_{2}+\frac{\|{\boldsymbol{\mu}}_{1}\|}{\sqrt{n_{2}}}z_{1}+\frac{\|{\boldsymbol{\mu}}_{2}\|}{\sqrt{n_{1}}}z_{2}+\sqrt{\frac{p}{n_{1}n_{2}}}z_{3}$
$\displaystyle\text{with}\quad z_{1},z_{2},z_{3}\sim\mathcal{N}(0,1).$

Therefore the estimator is consistent, and converges with an
$\mathcal{O}\left(\frac{1}{\sqrt{n}}\right)$ speed, under Assumption 2. For
the specific case of $\theta={\boldsymbol{\mu}}_{1}^{\sf
T}{\boldsymbol{\mu}}_{1}$, one can use the previous results, but needs to
divide the samples in two separate subsets, in order to keep the property of
independance between the samples.

##  Appendix E Proof of Theorem 8

The proof is organized as follows:

  * •

A first order deterministic equivalent (Section E-A) is needed to compute the
mean of $f_{i}$ (Section E-B)

  * •

A second order deterministic equivalent (Section E-C) is needed to compute the
variance of $f_{i}$ (Section E-D)

A more detailed version of the proof is available at https://gricad-
gitlab.univ-grenoble-alpes.fr/legervi/tsp.

In the following proof, we will need to distinguish the data matrix
${\mathbf{Z}}$ and its centered version $\mathring{{\mathbf{Z}}}$, as the
centering breaks the independance between samples. This effect of centering is
sumed up in the following lemma.

######  Lemma 11.

For a data matrix ${\mathbf{X}}$ defined as in Assumption 1, and centered as
in equation (3), we have asymtotically:

$\mathbb{E}\left[\mathring{{\mathbf{X}}}\mathring{{\mathbf{X}}}^{\sf
T}\right]=(1-\frac{1}{n})\mathbb{E}\left[{\mathbf{X}}{\mathbf{X}}^{\sf
T}\right]-\frac{1}{n}\mathbb{E}[{\mathbf{X}}]\mathbb{E}[{\mathbf{X}}]^{\sf T}$
(18) $\left\\{\begin{array}[]{lr}\mathbb{E}\left[{\mathbf{X}}^{\sf
T}{\mathbf{X}}\right]=\mathbb{E}[{\mathbf{X}}]^{\sf
T}\mathbb{E}[{\mathbf{X}}]+\rm tr({\mathbf{\Sigma}}){\mathbf{I}}_{n},\\\
\mathbb{E}\left[\mathring{{\mathbf{X}}}^{\sf
T}\mathring{{\mathbf{X}}}\right]=\mathbb{E}[\mathring{{\mathbf{X}}}]^{\sf
T}\mathbb{E}[\mathring{{\mathbf{X}}}]+\rm
tr({\mathbf{\Sigma}}){\mathbf{I}}_{n}-\frac{1}{n}\rm
tr({\mathbf{\Sigma}})\mathbb{1}_{n}\mathbb{1}_{n}^{\sf T}\end{array}\right.$
(19)

While the matrix ${\mathbf{X}}{\mathbf{X}}^{\sf T}$ is practically unaffected
by the centering, the matrix ${\mathbf{X}}^{\sf T}{\mathbf{X}}$ is changed,
not only by the centering of the mean matrix $\mathbb{E}[{\mathbf{X}}]^{\sf
T}\mathbb{E}[{\mathbf{X}}]$, but also with the appearance of the bias term
$-\frac{1}{n}\rm tr({\mathbf{\Sigma}})\mathbb{1}\mathbb{1}^{\sf T}$. With
these results in mind,
${\mathbf{X}}^{t},{\boldsymbol{\mu}}_{j}^{t},{\mathbf{Z}}$ will still denote
their centered versions, as it was the case until now.

###  E-A First order deterministic equivalent

We introduce the notation ${\mathbf{F}}\leftrightarrow\bar{{\mathbf{F}}}$
which denote that $\bar{{\mathbf{F}}}$ is a deterministic equivalent of
${\mathbf{F}}$.
A deterministic equivalent, say $\bar{{\mathbf{F}}}\in\mathbb{R}^{n\times p}$,
of a given random matrix ${\mathbf{F}}\in\mathbb{R}^{n\times p}$, is defined
by the fact that under assumption 2, for any deterministic linear functional
$f:\mathbb{R}^{n\times p}\to\mathbb{R}$,
$f({\mathbf{F}}-\bar{{\mathbf{F}}})\to 0$ almost surely (for instance, for
${\mathbf{u}},{\mathbf{v}}$ of unit norm, ${\mathbf{u}}^{\sf
T}({\mathbf{F}}-\bar{{\mathbf{F}}}){\mathbf{v}}\overset{\rm
a.s.}{\longrightarrow}0$ and, for ${\mathbf{A}}\in\mathbb{R}^{p\times n}$
deterministic of bounded operator norm, $\frac{1}{n}\rm
tr{\mathbf{A}}({\mathbf{F}}-\bar{{\mathbf{F}}})\overset{\rm
a.s.}{\longrightarrow}0$).

Theorem $2.8$ of [23] provides us a deterministic equivalent for
${\mathbf{Q}}$. To express it, we need to define

${\mathbf{C}}_{j}^{t}={\mathbf{A}}^{\frac{1}{2}}\left({\mathbf{E}}_{tt}\otimes\left(\mathbf{\Sigma}_{j}^{t}+\boldsymbol{\mu}_{j}^{t}{\boldsymbol{\mu}_{j}^{t}}^{{\sf
T}}\right)\right){\mathbf{A}}^{\frac{1}{2}}$ (20)

Then, we have
${\mathbf{Q}}\leftrightarrow\bar{{\mathbf{Q}}}=\left({\mathbf{I}}_{Tp}-\sum_{t,j}\tilde{\delta}_{j}^{t}{\mathbf{C}}_{j}^{t}\right)^{-1}$,
with $\tilde{\delta}_{j}^{t}$ satisfying the following system of equations:

$\tilde{\delta}_{j}^{t}=\frac{\rho_{j}^{t}}{Tc}\frac{1}{1-\delta_{j}^{t}}\quad\text{and}\quad\delta_{j}^{t}=\frac{1}{Tp}\rm
tr\left({\mathbf{C}}_{j}^{t}\bar{{\mathbf{Q}}}\right)$

Let’s compute more explicitly the quantity $\delta_{j}^{t}$. If the
covariances of the data for all class $j$ and all tasks $t$ are isotropic of
same magnitude, i.e $\mathbf{\Sigma}_{j}^{t}={\mathbf{I}}_{p}$, then, as
$\boldsymbol{\mu}_{j}^{t}{\boldsymbol{\mu}_{j}^{t}}^{{\sf T}}$ is a small rank
perturbation of $\mathbf{\Sigma}_{j}^{t}$, we have asymptotically:

$\rm tr\left({\mathbf{C}}_{j}^{t}\bar{{\mathbf{Q}}}\right)=\rm
tr\left({\mathbf{A}}^{\frac{1}{2}}\left({\mathbf{E}}_{tt}\otimes{\mathbf{I}}_{p}\right){\mathbf{A}}^{\frac{1}{2}}\bar{{\mathbf{Q}}}\right)$

Therefore, $\delta_{1}^{t}=\delta_{2}^{t}$, and we will use the same notation
$\delta^{t}$ for both in the following. Let’s define
$\bar{\delta}^{t}=\tilde{\delta}_{1}^{t}+\tilde{\delta}_{2}^{t}$, and
$\bar{{\mathbf{M}}}=[{\mathbf{e}}_{1}^{[T]}\otimes\boldsymbol{\mu}_{1}^{1},{\mathbf{e}}_{1}^{[T]}\otimes\boldsymbol{\mu}_{2}^{1},\ldots,{\mathbf{e}}_{T}^{[T]}\otimes\boldsymbol{\mu}_{2}^{T}]$.
Then

$\displaystyle\sum_{t,j}\tilde{\delta}_{j}^{t}{\mathbf{C}}_{j}^{t}=\sum_{t,j}\tilde{\delta}_{j}^{t}{\mathbf{A}}^{\frac{1}{2}}\left({\mathbf{E}}_{tt}\otimes\left({\mathbf{I}}_{p}+\boldsymbol{\mu}_{j}^{t}{\boldsymbol{\mu}_{j}^{t}}^{{\sf
T}}\right)\right){\mathbf{A}}^{\frac{1}{2}}$ $\displaystyle=$
$\displaystyle\left(\tilde{\mathbf{\Lambda}}^{\frac{1}{2}}\mathcal{D}_{\bar{\boldsymbol{\delta}}}\tilde{\mathbf{\Lambda}}^{\frac{1}{2}}\right)\otimes{\mathbf{I}}_{p}+{\mathbf{A}}^{\frac{1}{2}}\bar{{\mathbf{M}}}\mathcal{D}_{\tilde{\boldsymbol{\delta}}}\bar{{\mathbf{M}}}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}$

If
$\bar{{\mathbf{Q}}}_{0}=\left({\mathbf{I}}_{T}-\tilde{\mathbf{\Lambda}}^{\frac{1}{2}}\mathcal{D}_{\bar{\boldsymbol{\delta}}}\tilde{\mathbf{\Lambda}}^{\frac{1}{2}}\right)^{-1}\otimes{\mathbf{I}}_{p}$,
using Woodbury identity,

$\displaystyle\bar{{\mathbf{Q}}}$
$\displaystyle=\bar{{\mathbf{Q}}}_{0}+\bar{{\mathbf{Q}}}_{0}{\mathbf{U}}\left({\mathbf{I}}_{2T}-{\mathbf{U}}^{\sf
T}\bar{{\mathbf{Q}}}_{0}{\mathbf{U}}\right)^{-1}{\mathbf{U}}^{\sf
T}\bar{{\mathbf{Q}}}_{0}$

The second term is a matrix of rank $2T<<Tp$ and can be neglected in the
trace. Then

$\displaystyle{\mathbf{A}}^{\frac{1}{2}}\bar{{\mathbf{Q}}}_{0}{\mathbf{A}}^{\frac{1}{2}}$
$\displaystyle=\underbrace{\left[\tilde{\mathbf{\Lambda}}+\tilde{\mathbf{\Lambda}}\left(\mathcal{D}_{\bar{\boldsymbol{\delta}}}^{-1}-\tilde{\mathbf{\Lambda}}\right)^{-1}\tilde{\mathbf{\Lambda}}\right]}_{={\boldsymbol{\mathcal{A}}}}\otimes{\mathbf{I}}_{p}.$

Finally,

$\delta^{t}=\frac{1}{Tp}\rm
tr\left({\mathbf{E}}_{tt}{\boldsymbol{\mathcal{A}}}\right)\rm
tr({\mathbf{I}}_{p})=\frac{1}{T}{\boldsymbol{\mathcal{A}}}_{tt}.$

We can then conclude that the $\\{\delta^{t}\\}_{t}$ are the solution of the
following system of equations:

$\left\\{\begin{array}[]{lr}\forall
t,~{}\delta^{t}=\frac{1}{T}{\boldsymbol{\mathcal{A}}}_{tt},\\\
{\boldsymbol{\mathcal{A}}}=\tilde{\mathbf{\Lambda}}+\tilde{\mathbf{\Lambda}}\left({\mathcal{D}}_{\bar{\boldsymbol{\delta}}}^{-1}-\tilde{\mathbf{\Lambda}}\right)^{-1}\tilde{\mathbf{\Lambda}}\end{array}\right.$

###  E-B Computation of the mean

$\mathbb{E}[f_{i}]=\frac{1}{Tp}\sum_{i^{\prime}}\mathbb{E}\left[{\mathbf{z}}_{i}^{{\sf
T}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Q}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{z}}_{i^{\prime}}\right]y_{i^{\prime}}.$

Using Sherman-Morrison formula, it can be proved that:

${\mathbf{Q}}={\mathbf{Q}}_{-i}+\frac{1}{Tp}\frac{{\mathbf{Q}}_{-i}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{z}}_{i}{\mathbf{z}}_{i}^{{\sf
T}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Q}}_{-i}}{1-\frac{1}{Tp}{\mathbf{z}}_{i}^{{\sf
T}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Q}}_{-i}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{z}}_{i}}$
(21)

with
${\mathbf{Q}}_{-i}=\left({\mathbf{I}}_{Tp}-\frac{{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Z}}_{-i}{\mathbf{Z}}_{-i}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}}{Tp}\right)^{-1}$, the notation
${\mathbf{Z}}_{-i}$ standing for the matrix ${\mathbf{Z}}$ with the $i$-th
column removed.

In particular:

$\displaystyle\mathbb{E}\left[{\mathbf{z}}_{i}^{{\sf
T}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Q}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{z}}_{i^{\prime}}\right]=\frac{\mathbb{E}\left[{\mathbf{z}}_{i}^{{\sf
T}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Q}}_{-i}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{z}}_{i^{\prime}}\right]}{1-\delta^{t}}.$

And thanks to equation (19)

$\displaystyle\mathbb{E}\left[{\mathbf{z}}_{i}^{{\sf
T}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Q}}_{-i,-i^{\prime}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{z}}_{i^{\prime}}\right]$
$\displaystyle=\mathbb{E}\left[{\mathbf{z}}_{i}\right]^{{\sf
T}}{\mathbf{A}}^{\frac{1}{2}}\bar{{\mathbf{Q}}}{\mathbf{A}}^{\frac{1}{2}}\mathbb{E}\left[{\mathbf{z}}_{i^{\prime}}\right]-\frac{1}{n^{t}}\mathbb{E}\left[\rm
tr({\mathbf{C}}^{t}{\mathbf{Q}})\right]\mathbb{1}_{t=t^{\prime}}$
$\displaystyle={{\mathbf{e}}_{t,j}^{[2T]}}^{\sf T}\bar{{\mathbf{M}}}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}\bar{{\mathbf{Q}}}{\mathbf{A}}^{\frac{1}{2}}\bar{{\mathbf{M}}}{\mathbf{e}}_{t^{\prime},j^{\prime}}^{[2T]}-\frac{Tp}{n^{t}}\delta^{t}{{\mathbf{e}}_{t,j}^{[2T]}}^{\sf
T}({\mathbf{I}}_{T}\otimes\mathbb{1}_{2}\mathbb{1}_{2}^{\sf
T}){\mathbf{e}}_{t^{\prime},j^{\prime}}^{[2T]},$

with

${\mathbf{C}}^{t}:={\mathbf{A}}^{\frac{1}{2}}\left({\mathbf{E}}_{tt}\otimes{\mathbf{I}}_{p}\right){\mathbf{A}}^{\frac{1}{2}}.$

So finally

$\displaystyle\mathbb{E}\left[{\mathbf{z}}_{i}^{{\sf
T}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Q}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{z}}_{i^{\prime}}\right]\simeq\frac{\mathbb{E}\left[{\mathbf{z}}_{i}^{{\sf
T}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Q}}_{-i,-i^{\prime}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{z}}_{i^{\prime}}\right]}{(1-\delta^{t})(1-\delta^{t^{\prime}})}$
$\displaystyle=\frac{{{\mathbf{e}}_{t,j}^{[2T]}}^{\sf
T}}{1-\delta^{t}}\left(\bar{{\mathbf{M}}}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}\bar{{\mathbf{Q}}}{\mathbf{A}}^{\frac{1}{2}}\bar{{\mathbf{M}}}-\frac{Tc}{\rho^{t}}\delta^{t}{\mathbf{I}}_{T}\otimes\mathbb{1}_{2}\mathbb{1}_{2}^{\sf
T}\right)\frac{{\mathbf{e}}_{t^{\prime},j^{\prime}}^{[2T]}}{1-\delta^{t^{\prime}}}.$

Going back to the quantity we want to estimate,

$\displaystyle\sum_{i^{\prime}}\frac{y_{i^{\prime}}}{Tp}\frac{{\mathbf{e}}_{t^{\prime},j^{\prime}}^{[2T]}}{1-\delta^{t^{\prime}}}={\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}{\mathcal{D}}_{{\boldsymbol{\eta}}}\bar{{\mathbf{D}}}\tilde{{\mathbf{y}}}$

with $\bar{d}_{j_{1},j_{2}}^{t}=\frac{1}{n_{\ell
j_{1}}^{t}}\sum_{i^{\prime}|x_{i}\in\mathcal{C}_{j_{1}}^{t}}d_{i^{\prime}j_{2}}^{t}$
and

$\bar{{\mathbf{D}}}=\sum_{t=1}^{T}{\mathbf{E}}_{tt}\otimes\begin{pmatrix}\bar{d}_{11}^{t}&\bar{d}_{12}^{t}\\\
\bar{d}_{21}^{t}&\bar{d}_{22}^{t}\end{pmatrix},$

so we have

$\mathbb{E}[f_{i}]=\frac{{{\mathbf{e}}_{t,j}^{[2T]}}^{\sf
T}}{1-\delta^{t}}\left(\bar{{\mathbf{M}}}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}\bar{{\mathbf{Q}}}{\mathbf{A}}^{\frac{1}{2}}\bar{{\mathbf{M}}}-\frac{Tc}{\rho^{t}}\delta^{t}{\mathbf{I}}_{T}\otimes\mathbb{1}_{2}\mathbb{1}_{2}^{\sf
T}\right){\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}{\mathcal{D}}_{{\boldsymbol{\eta}}}\bar{{\mathbf{D}}}\tilde{{\mathbf{y}}}.$

Let us define

${\mathbf{\Theta}}:=\bar{{\mathbf{M}}}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}\bar{{\mathbf{Q}}}{\mathbf{A}}^{\frac{1}{2}}\bar{{\mathbf{M}}}={\mathbf{\Theta}}_{0}\left({\mathbf{I}}_{2T}-{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}{\mathbf{\Theta}}_{0}\right)^{-1}$
$\mathbb{E}[f_{i}]=\frac{{{\mathbf{e}}_{t,j}^{[2T]}}^{\sf
T}}{1-\delta^{t}}\left({\mathbf{\Theta}}-\frac{Tc}{\rho^{t}}\delta^{t}{\mathbf{I}}_{T}\otimes\mathbb{1}_{2}\mathbb{1}_{2}^{\sf
T}\right){\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}{\mathcal{D}}_{{\boldsymbol{\eta}}}\bar{{\mathbf{D}}}\tilde{{\mathbf{y}}}$

As ${\mathbf{\Gamma}}={\mathbf{I}}_{T}\otimes\mathbb{1}_{2}\mathbb{1}_{2}^{\sf
T}$ and $\gamma^{t}=\frac{Tc\delta^{t}}{\rho^{t}}$, we can conclude that:

$m_{j}^{t}=\mathbb{E}[f_{i}]=\frac{{{\mathbf{e}}_{t,j}^{[2T]}}^{\sf
T}}{1-\delta^{t}}\left({\mathbf{\Theta}}-\gamma^{t}{\mathbf{\Gamma}}\right){\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}{\mathcal{D}}_{{\boldsymbol{\eta}}}\bar{{\mathbf{D}}}\tilde{{\mathbf{y}}}$
(22)

###  E-C Second order deterministic equivalent

In the following, we will need a deterministic equivalent for
${\mathbf{Q}}{\mathbf{C}}_{j}^{t}{\mathbf{Q}}$ (which is not
$\bar{{\mathbf{Q}}}{\mathbf{C}}_{j}^{t}\bar{{\mathbf{Q}}}$). An analysis
similar to the one performed in E-A, allows to show that :

$\displaystyle\mathbb{E}\left[{\mathbf{u}}^{\sf
T}{\mathbf{Q}}{\mathbf{C}}_{j}^{t}{\mathbf{Q}}{\mathbf{v}}\right]-{\mathbf{u}}^{\sf
T}\bar{{\mathbf{Q}}}{\mathbf{C}}_{j}^{t}\bar{{\mathbf{Q}}}{\mathbf{v}}$
$\displaystyle=\sum_{t^{\prime},j^{\prime}}\frac{n_{j^{\prime}}^{t^{\prime}}}{(Tp)^{2}(1-\delta^{t^{\prime}})^{2}}\rm
tr\left(\bar{{\mathbf{Q}}}{\mathbf{C}}_{j}^{t}\bar{{\mathbf{Q}}}{\mathbf{C}}_{j^{\prime}}^{t^{\prime}}\right)\mathbb{E}\left[{\mathbf{u}}^{\sf
T}{\mathbf{Q}}{\mathbf{C}}_{j^{\prime}}^{t^{\prime}}{\mathbf{Q}}{\mathbf{v}}\right]$

Until now we have the following (not deterministic) equivalent:

${\mathbf{Q}}{\mathbf{C}}_{j}^{t}{\mathbf{Q}}\leftrightarrow\bar{{\mathbf{Q}}}{\mathbf{C}}_{j}^{t}\bar{{\mathbf{Q}}}+\sum_{t^{\prime},j^{\prime}}\frac{n_{j^{\prime}}^{t^{\prime}}}{(Tp)^{2}(1-\delta^{t^{\prime}})^{2}}\rm
tr\left(\bar{{\mathbf{Q}}}{\mathbf{C}}_{j}^{t}\bar{{\mathbf{Q}}}{\mathbf{C}}_{j^{\prime}}^{t^{\prime}}\right){\mathbf{Q}}{\mathbf{C}}_{j^{\prime}}^{t^{\prime}}{\mathbf{Q}}$
(23)

First of all, as ${\mathbf{C}}_{j}^{t}$ is a small-rank perturbation of
${\mathbf{C}}^{t}$ and $\bar{{\mathbf{Q}}}$ is a small-rank perturbation of
$\bar{{\mathbf{Q}}}_{0}$:

$\displaystyle\frac{1}{Tp}\rm
tr\left(\bar{{\mathbf{Q}}}{\mathbf{C}}_{j}^{t}\bar{{\mathbf{Q}}}{\mathbf{C}}_{j^{\prime}}^{t^{\prime}}\right)=\frac{1}{Tp}\rm
tr\left(\bar{{\mathbf{Q}}}_{0}{\mathbf{C}}^{t}\bar{{\mathbf{Q}}}_{0}{\mathbf{C}}^{t^{\prime}}\right)$
$\displaystyle=\frac{1}{T}\rm
tr\left({\mathbf{E}}_{tt}{\boldsymbol{\mathcal{A}}}{\mathbf{E}}_{t^{\prime}t^{\prime}}{\boldsymbol{\mathcal{A}}}\right)=\frac{{\boldsymbol{\mathcal{A}}}_{tt^{\prime}}^{2}}{T}$

Let’s define

$\displaystyle\bar{{\mathbf{S}}}^{tt^{\prime}}$
$\displaystyle=\frac{1}{Tc(1-\delta^{t^{\prime}})^{2}}\frac{1}{Tp}\rm
tr\left(\bar{{\mathbf{Q}}}{\mathbf{C}}^{t}\bar{{\mathbf{Q}}}{\mathbf{C}}^{t^{\prime}}\right)=\frac{{\boldsymbol{\mathcal{A}}}_{tt^{\prime}}^{2}}{T^{2}c(1-\delta^{t^{\prime}})^{2}}$
$\displaystyle{\mathbf{S}}^{tt^{\prime}}$
$\displaystyle=\frac{1}{Tc(1-\delta^{t^{\prime}})^{2}}\frac{1}{Tp}\mathbb{E}\left[\rm
tr\left({\mathbf{Q}}{\mathbf{C}}^{t}{\mathbf{Q}}{\mathbf{C}}^{t^{\prime}}\right)\right]$

One can deduce from (23) that
${\mathbf{S}}=\bar{{\mathbf{S}}}+\bar{{\mathbf{S}}}{\mathcal{D}}_{\bar{{\boldsymbol{\rho}}}}{\mathbf{S}}$,
so
${\mathbf{S}}=\bar{{\mathbf{S}}}\left({\mathbf{I}}_{T}-{\mathcal{D}}_{\bar{{\boldsymbol{\rho}}}}\bar{{\mathbf{S}}}\right)^{-1}$.
Similarly, it follows that:

${\mathbf{Q}}{\mathbf{C}}_{j}^{t}{\mathbf{Q}}\leftrightarrow\bar{{\mathbf{Q}}}{\mathbf{C}}_{j}^{t}\bar{{\mathbf{Q}}}+\sum_{t^{\prime},j^{\prime}}\rho_{j^{\prime}}^{t^{\prime}}{\mathbf{S}}^{tt^{\prime}}\bar{{\mathbf{Q}}}{\mathbf{C}}_{j^{\prime}}^{t^{\prime}}\bar{{\mathbf{Q}}}$
(24)

###  E-D Computation of the variance

Under assumption 2, the second order moment can be computed as:

$\displaystyle\mathbf{E}[f_{i}^{2}]=\underbrace{\frac{1}{(Tp)^{2}}\sum_{i^{\prime}}\mathbb{E}\left[{\mathbf{z}}_{i^{\prime}}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Q}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{z}}_{i}{\mathbf{z}}_{i}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Q}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{z}}_{i^{\prime}}\right]y_{i^{\prime}}^{2}}_{:=C_{1}}$
$\displaystyle+\underbrace{\frac{1}{(Tp)^{2}}\sum_{i^{\prime}\neq
i^{\prime\prime}}\mathbb{E}\left[{\mathbf{z}}_{i^{\prime}}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Q}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{z}}_{i}{\mathbf{z}}_{i}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Q}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{z}}_{i^{\prime\prime}}\right]y_{i^{\prime}}y_{i^{\prime\prime}}}_{:=C_{2}}$

  * •

Computation of $C_{1}$

$\displaystyle
C_{1}=\frac{1}{(Tp)^{2}}\sum_{i^{\prime}}\frac{\mathbb{E}\left[\rm
tr\left({\mathbf{Q}}{\mathbf{C}}^{t}{\mathbf{Q}}{\mathbf{C}}^{t^{\prime}}\right)\right]}{(1-\delta^{t})^{2}(1-\delta^{t^{\prime}})^{2}}y_{i^{\prime}}^{2}$
$\displaystyle=\sum_{t^{\prime}}\frac{\rho^{t^{\prime}}{\mathbf{S}}^{tt^{\prime}}}{(1-\delta^{t})^{2}}\eta^{t^{\prime}}\begin{pmatrix}\tilde{y}_{1}^{t^{\prime}}&\tilde{y}_{2}^{t^{\prime}}\end{pmatrix}\begin{pmatrix}\tilde{d}_{11}^{t^{\prime}}&\tilde{d}_{12}^{t^{\prime}}\\\
\tilde{d}_{21}^{t^{\prime}}&\tilde{d}_{22}^{t^{\prime}}\end{pmatrix}\begin{pmatrix}\tilde{y}_{1}^{t^{\prime}}\\\
\tilde{y}_{2}^{t^{\prime}}\end{pmatrix}$
$\displaystyle=\tilde{{\mathbf{y}}}^{\sf
T}\left({\mathbf{T}}^{t}\odot\tilde{{\mathbf{D}}}\right)\tilde{{\mathbf{y}}},$

with
$\tilde{d}_{j_{1}j_{2}}^{t}=\frac{1}{n_{\ell}^{t}}\sum_{i|{\mathbf{x}}_{i}\in\mathcal{C}^{t}}d_{ij_{1}}^{t}d_{ij_{2}}^{t}$,
if we further define

$\displaystyle\tilde{{\mathbf{D}}}$
$\displaystyle=\sum_{t=1}^{T}{\mathbf{E}}_{tt}\otimes\begin{pmatrix}\tilde{d}_{11}^{t}&\tilde{d}_{12}^{t}\\\
\tilde{d}_{21}^{t}&\tilde{d}_{22}^{t}\end{pmatrix}$
$\displaystyle{\mathbf{T}}^{t}$
$\displaystyle=\frac{1}{(1-\delta^{t})^{2}}{\mathcal{D}}_{\bar{{\boldsymbol{\rho}}}\odot\bar{{\boldsymbol{\eta}}}\odot{\mathbf{S}}^{t.}}\otimes\mathbb{1}_{2}\mathbb{1}_{2}^{\sf
T}.$

  * •

Computation of $C_{2}$
Using 21 and 19, we have

$\displaystyle\mathbb{E}\left[{\mathbf{z}}_{i^{\prime}}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Q}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{z}}_{i}{\mathbf{z}}_{i}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{Q}}{\mathbf{A}}^{\frac{1}{2}}{\mathbf{z}}_{i^{\prime\prime}}\right]$
$\displaystyle=\frac{{{\mathbf{e}}_{t^{\prime},j^{\prime}}^{[2T]}}^{\sf
T}}{1-\delta^{t^{\prime}}}\underbrace{\frac{\bar{{\mathbf{M}}}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}\mathbb{E}\left[{\mathbf{Q}}{\mathbf{C}}_{j}^{t}{\mathbf{Q}}\right]{\mathbf{A}}^{\frac{1}{2}}\bar{{\mathbf{M}}}}{(1-\delta^{t})^{2}}}_{:=\mathbf{{\boldsymbol{\mathcal{U}}}}_{1}^{t}}\frac{{\mathbf{e}}_{t^{\prime\prime},j^{\prime\prime}}^{[2T]}}{1-\delta^{t^{\prime\prime}}}$
$\displaystyle-
Tc{\mathbf{S}}^{tt^{\prime}}{{\mathbf{e}}_{t^{\prime},j^{\prime}}^{[2T]}}^{\sf
T}\underbrace{\frac{{\mathbf{\Gamma}}}{(1-\delta^{t})^{2}}}_{:=\mathbf{{\boldsymbol{\mathcal{U}}}}_{2}^{t}}\frac{Tc}{\rho^{t^{\prime}}}{\mathbf{e}}_{t^{\prime\prime},j^{\prime\prime}}^{[2T]}$
$\displaystyle+Tc{{\mathbf{e}}_{t^{\prime},j^{\prime}}^{[2T]}}^{\sf
T}\left(\underbrace{\frac{({\mathbf{\Theta}}-\gamma^{t}{\mathbf{\Gamma}})}{(1-\delta^{t})^{2}}}_{:=\mathbf{{\boldsymbol{\mathcal{U}}}}_{3}^{t}}\frac{{\mathbf{S}}^{tt^{\prime}}}{1-\delta^{t^{\prime\prime}}}+\frac{{\mathbf{S}}^{tt^{\prime\prime}}}{1-\delta^{t^{\prime}}}\mathbf{{\boldsymbol{\mathcal{U}}}}_{3}^{t}\right){\mathbf{e}}_{t^{\prime\prime},j^{\prime\prime}}^{[2T]}.$

Let us decompose

$\displaystyle\bar{{\mathbf{M}}}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}\bar{{\mathbf{Q}}}_{0}\left({\mathbf{C}}_{j}^{t}+\sum_{t^{\prime},j^{\prime}}\rho_{j^{\prime}}^{t^{\prime}}{\mathbf{S}}^{tt^{\prime}}{\mathbf{C}}_{j^{\prime}}^{t^{\prime}}\right)\bar{{\mathbf{Q}}}_{0}{\mathbf{A}}^{\frac{1}{2}}\bar{{\mathbf{M}}}$
$\displaystyle={\mathbf{\Theta}}_{0}\left({\mathbf{e}}_{t,j}^{[2T]}{{\mathbf{e}}_{t,j}^{[2T]}}^{\sf
T}+{\mathcal{D}}_{{\mathbf{r}}^{t}}\right){\mathbf{\Theta}}_{0}+\underbrace{\left(\bar{{\boldsymbol{\mathcal{V}}}}^{t}\otimes\mathbb{1}_{2}\mathbb{1}_{2}^{\sf
T}\right)\odot{\mathbf{M}}^{\sf
T}{\mathbf{M}}}_{:=\bar{{\mathbf{\Omega}}}_{0}^{t}},$

with
${\mathbf{r}}^{t}={\boldsymbol{\rho}}\odot\left({\mathbf{S}}^{t}\otimes\mathbb{1}_{2}\mathbb{1}_{2}^{\sf
T}\right)$ and
$\bar{{\boldsymbol{\mathcal{V}}}}^{t}={\boldsymbol{\mathcal{V}}}^{t}+\sum_{t^{\prime}}\rho^{t^{\prime}}{\mathbf{S}}^{tt^{\prime}}{\boldsymbol{\mathcal{V}}}^{t^{\prime}}$.
We thus have:

$\displaystyle\bar{{\mathbf{M}}}^{\sf
T}{\mathbf{A}}^{\frac{1}{2}}\mathbb{E}[{\mathbf{Q}}{\mathbf{C}}_{j}^{t}{\mathbf{Q}}]{\mathbf{A}}^{\frac{1}{2}}\bar{{\mathbf{M}}}$
$\displaystyle={\mathbf{\Theta}}\left({\mathbf{e}}_{t,j}^{[2T]}{{\mathbf{e}}_{t,j}^{[2T]}}^{\sf
T}+{\mathcal{D}}_{{\mathbf{r}}^{t}}\right){\mathbf{\Theta}}$
$\displaystyle+\underbrace{\left({\mathbf{I}}_{2T}-{\mathbf{\Theta}}_{0}{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}\right)^{-1}\bar{{\mathbf{\Omega}}}_{0}^{t}\left({\mathbf{I}}_{2T}-{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}{\mathbf{\Theta}}_{0}\right)^{-1}}_{:=\bar{{\mathbf{\Omega}}}^{t}}.$
$\displaystyle C_{2}$
$\displaystyle=\frac{1}{(1-\delta^{t})^{2}}\tilde{{\mathbf{y}}}^{\sf
T}\bar{{\mathbf{D}}}^{\sf
T}{\mathcal{D}}_{{\boldsymbol{\eta}}}\left[{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}{\mathbf{\Theta}}\left({\mathbf{e}}_{t,j}^{[2T]}{{\mathbf{e}}_{t,j}^{[2T]}}^{\sf
T}+{\mathcal{D}}_{{\mathbf{r}}^{t}}\right){\mathbf{\Theta}}{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}\right.$
$\displaystyle+{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}\bar{{\mathbf{\Omega}}}^{t}{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}-{\mathbf{\Gamma}}^{t}{\mathcal{D}}_{{\mathbf{r}}^{t}}+2{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}({\mathbf{\Theta}}-\gamma^{t}{\mathbf{\Gamma}}){\mathcal{D}}_{{\mathbf{r}}^{t}}\left.\right]{\mathcal{D}}_{{\boldsymbol{\eta}}}\bar{{\mathbf{D}}}\tilde{{\mathbf{y}}}$

As $Var(q_{i})=C_{1}+C_{2}-{m_{j}^{t}}^{2}$, we finally have:

$\displaystyle{\sigma^{t}}^{2}=\frac{1}{(1-\delta^{t})^{2}}\tilde{{\mathbf{y}}}^{\sf
T}\left({\mathbf{T}}^{t}\odot\tilde{{\mathbf{D}}}\right)\tilde{{\mathbf{y}}}$
$\displaystyle+\frac{1}{(1-\delta^{t})^{2}}\tilde{{\mathbf{y}}}^{\sf
T}\bar{{\mathbf{D}}}^{\sf
T}{\mathcal{D}}_{{\boldsymbol{\eta}}}{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}\left({\mathbf{\Theta}}{\mathcal{D}}_{{\mathbf{r}}^{t}}{\mathbf{\Theta}}+\bar{{\mathbf{\Omega}}}^{t}-{\gamma^{t}}^{2}{\mathbf{\Gamma}}^{t}\right){\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}{\mathcal{D}}_{{\boldsymbol{\eta}}}\bar{{\mathbf{D}}}\tilde{{\mathbf{y}}}$
$\displaystyle+\frac{1}{(1-\delta^{t})^{2}}\tilde{{\mathbf{y}}}^{\sf
T}\bar{{\mathbf{D}}}^{\sf
T}{\mathcal{D}}_{{\boldsymbol{\eta}}}\left[2{\mathcal{D}}_{\tilde{{\boldsymbol{\delta}}}}({\mathbf{\Theta}}-\gamma^{t}{\mathbf{\Gamma}})-{\mathbf{\Gamma}}^{t}\right]{\mathcal{D}}_{{\mathbf{r}}^{t}}{\mathcal{D}}_{{\boldsymbol{\eta}}}\bar{{\mathbf{D}}}\tilde{{\mathbf{y}}},$

with

$\mathbf{{\boldsymbol{\mathcal{U}}}}={\mathbf{\Theta}}{\mathbf{e}}_{t,j}^{[2T]}{{\mathbf{e}}_{t,j}^{[2T]}}^{\sf
T}{\mathbf{\Theta}}-{\gamma^{t}}^{2}\underbrace{{\mathbf{E}}^{tt}\otimes(\mathbb{1}_{2}\mathbb{1}_{2}^{\sf
T})}_{:={\mathbf{\Gamma}}^{t}}.$

## References

  * [1] N. C. Thompson, K. Greenewald, K. Lee, and G. F. Manso, “The Computational Limits of Deep Learning,” arXiv, Tech. Rep. arXiv:2007.05558, Jul. 2022, arXiv:2007.05558 [cs, stat] type: article. [Online]. Available: http://arxiv.org/abs/2007.05558
  * [2] I. Illich, _Tools for Conviviality_. Harper $\&$ Row, 1973.
  * [3] X. Mai and R. Couillet, “Consistent semi-supervised graph regularization for high dimensional data,” _Journal of Machine Learning Research_ , vol. 22, no. 94, pp. 1–48, 2021. [Online]. Available: http://jmlr.org/papers/v22/19-081.html
  * [4] D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Schölkopf, “Learning with local and global consistency,” in _Advances in Neural Information Processing Systems 16 (NIPS 2003)_ , 2003.
  * [5] K. Avrachenkov, A. Mishenin, P. Gonçalves, and M. Sokol, “Generalized Optimization Framework for Graph-based Semi-supervised Learning,” in _Proceedings of the 2012 SIAM International Conference on Data Mining_. Society for Industrial and Applied Mathematics, Apr. 2012, pp. 966–974.
  * [6] B. Shahshahani and D. Landgrebe, “The effect of unlabeled samples in reducing the small sample size problem and mitigating the hughes phenomenon,” _IEEE Transactions on Geoscience and Remote Sensing_ , vol. 32, no. 5, pp. 1087–1095, 1994.
  * [7] F. G. Cozman and I. Cohen, “Risks of semi-supervised learning: How unlabeled data can degrade performance of generative classifiers,” in _Semi-Supervised Learning_ , 2006. [Online]. Available: https://api.semanticscholar.org/CorpusID:63547716
  * [8] O. Chapelle, B. Schölkopf, and A. Zien, _Semi-Supervised Learning_. The MIT Press, 09 2006. [Online]. Available: https://doi.org/10.7551/mitpress/9780262033589.001.0001
  * [9] S. Ben-David, T. Lu, and D. Pál, “Does unlabeled data provably help? worst-case analysis of the sample complexity of semi-supervised learning,” in _Annual Conference Computational Learning Theory_ , 2008. [Online]. Available: https://api.semanticscholar.org/CorpusID:7670149
  * [10] M. Tiomoko, R. Couillet, and H. Tiomoko, “Large dimensional analysis and improvement of multi task learning,” _arXiv preprint arXiv:2009.01591_ , 2020\.
  * [11] T. Evgeniou and M. Pontil, “Regularized multi–task learning,” in _Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , ser. KDD ’04. New York, NY, USA: Association for Computing Machinery, 2004, p. 109–117. [Online]. Available: https://doi.org/10.1145/1014052.1014067
  * [12] M. Ledoux, _The concentration of measure phenomenon_. American Mathematical Society, 2001.
  * [13] N. El Karoui, “Concentration of measure and spectra of random matrices: Applications to correlation matrices, elliptical distributions and beyond,” _The Annals of Applied Probability_ , vol. 19, no. 6, Dec. 2009. [Online]. Available: http://dx.doi.org/10.1214/08-AAP548
  * [14] M. E. A. Seddik, C. Louart, M. Tamaazousti, and R. Couillet, “Random matrix theory proves that deep learning representations of gan-data behave as gaussian mixtures,” in _International Conference on Machine Learning_ , 2020\. [Online]. Available: https://api.semanticscholar.org/CorpusID:210868271
  * [15] T. Joachims, “Transductive Learning via Spectral Graph Partitioning,” 2003.
  * [16] X. Zhu, Z. Ghahramani, and J. Lafferty, “Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions,” 2003.
  * [17] X. Mai and R. Couillet, “A random matrix analysis and improvement of semi-supervised learning for large dimensional data,” _The Journal of Machine Learning Research_ , vol. 19, no. 1, pp. 3074–3100, 2018.
  * [18] C. Bishop, _Pattern Recognition and Machine Learning_. Springer New York, NY, 2006.
  * [19] A. Rocha and S. K. Goldenstein, “Multiclass from binary: Expanding one-versus-all, one-versus-one and ecoc-based approaches,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 25, no. 2, pp. 289–302, 2014.
  * [20] M.-T. Nguyen and R. Couillet, “Asymptotic bayes risk of semi-supervised multitask learning on gaussian mixture,” 2023.
  * [21] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” 2015.
  * [22] A. Brock, J. Donahue, and K. Simonyan, “Large scale gan training for high fidelity natural image synthesis,” 2019.
  * [23] R. Couillet and Z. Liao, _Random Matrix Methods for Machine Learning_. Cambridge University Press, 2022\.