() is a curated collection of retinal fundus images and their associated
pathology labels, which is derived from ten publicly available datasets. In
the following subsections, we describe the steps involved in the selection,
curation and construction of the final unified dataset. The dataset sources,
also referred to as s, are summarized in tbl:dcohortz.

Ethics statement: Identified datasets are in the public space and links to
their websites or download pages are accordingly referenced. We leave it to
the researcher to access and directly download the datasets.

Public data sources In this version of a total of publicly accessible data
sources are considered. The s are selected based on ease of access as well as
for their potential to represent diversity in retinal fundus images. Together,
the selected data sources represent multiple collection centers, several
ethnicities and various age groups. Additionally, they include some of the
common retinal pathologies like Diabetic Retinopathy (DR), Diabetic Macular
Edema (DME), Age-related Macular Degeneration (AMD), Glaucoma, Cataracts, and
Pathologic Myopia (PM), encompassing a variety of lesions or pathologies.

Specifically, the public sources are

  * •

EyePACS (on Kaggle)[noauthor_data_nodate, noauthor_diabetic_nodate]: This is a
large multi-center and multi-ethnicity dataset collected in the USA that
focuses on DR. We retrieve a total of images of which are originally labeled
as not pathological for DR. We manually cover images during curation. This
particularly adds diversity with respect to ethnicity, types of cameras and
center-specific variations.

  * •

ODIR [noauthor_odir-2019_nodate, noauthor_ocular_nodate]: This is a relatively
large multi-center dataset from Peking University (PKU) International
Competition on Ocular Disease Intelligent Recognition (ODIR), China. It covers
various retinal conditions including DR, Glaucoma, Cataracts, AMD,
Hypertension, PM and some rare conditions. We curate the entire set of images
in this dataset. This cohort adds diversity with respect to retinal
conditions, cameras and center-specific variations.

  * •

Kaggle1000 [cen_automatic_2021]: This dataset entails 39 retinal conditions,
including healthy or normal eyes. It is derived from a larger dataset that was
used to train an ensemble model for classifying 39 retinal conditions
[cen_automatic_2021], and avails 1000 fundus images from the Joint Shantou
International Eye Center (JSIEC) in China. This brings a diverse set of
retinal conditions and lesions to . We curate the entire set of images.

  * •

PAPILA [kovalyk_papila:_2022]: This is a glaucoma-focused dataset from a
single center in Spain. Additionally, it includes images from subjects between
the ages of 14 and 90. We curate the entire set of images.

  * •

IDRiD [porwal_indian_2018]: The Indian Diabetic Retinopathy Image Dataset
(IDRiD) is a single-center dataset from India that looks into DR and DME. This
dataset has three task-related subsets - a grading or classification dataset,
a segmentation dataset and a dataset for the localization of the optic disc.
We focus on the grading dataset where disease labels are included and curate
the entire set of those images. It further contributes to the ethnic diversity
in .

  * •

CHASEDB1 [fraz_ensemble_2012, fraz_chase_db1_2012]: This a dataset of school-
going children that is also multi-ethnic. It was collected in the UK for
research on cardiovascular conditions and is a relatively small dataset. This
dataset represents young patients and avails retinal fundus images focused on
the optic disc.

  * •

HRF (high-resolution fundus) [odstrcilik_retinal_2013, budai_robust_2013]:
This data source avails a set of high-resolution images collected from a
center in Europe for DR and glaucoma conditions. We curate the entire set of
images.

  * •

FIVE [jin_fives:_2022]: This a single-center high-resolution dataset that was
built for vessel segmentation under healthy and diseased conditions. The
retinal diseases covered include DR, AMD and Glaucoma. We curate the entire
set of images.

  * •

STARE [hoover_locating_2000]: This is one of the long-standing fundus
datasets. It covers 14 conditions including healthy eyes. Being one of the
older datasets, we hope that it adds diversity to the types of equipment and
protocols used. We curate the entire set of images.

  * •

Retina Cataracts [noauthor_cataract_nodate]: This is a bit of a wild-card in
that, while publicly available, it is not well documented. We curate the
entire set of images.

[c]

Table : Data sources or cohorts considered in this version of .

Consolidating the cohorts provides a set of Python modules that parse the
various directory structures and files to generate a unified catalog of the
cohorts. The Python modules contain cohort-specific parsers that map out their
directory structures, and extract and collate relevant metadata and condition
labels. This is because some datasets do not provide a metadata file or a CSV
file of disease labels, instead uniquely encapsulating such information within
the directory structure of the dataset. Relatedly, a unique image identifier
is created from the relative file path of an image since some datasets employ
identical filenames for images belonging to the same subject, relying on the
directory structure for context. The result is a unified catalog that
seamlessly maps back to the original directory structures, and to which we
append additional metadata and the newly curated _is_normal_ label. Curating
the normal label Extensive literature delves into reviewing retinal fundus
images and the phenotypic characteristics of various retinal diseases,
offering descriptive notes, classification frameworks, image atlases and
comprehensive insights into their manifestation [quinn_clinical_2019,
yannuzzi_retinal_2010-1, grossniklaus_introduction_2015-1, mishra_fundus_2023,
shukla_diabetic_2023, yuen_telehealth_2022, muller_ophthalmic_2019,
fang_progression_2018, noauthor_pathologic_nodate, kolb_facts_1995,
das_recently_2021, masland_neuronal_2012, pm1c, pm22, pm73]. Additionally,
these resources also illustrate what healthy eyes look like for different
ethnicities, age groups, and equipment in some cases. Furthermore, the
guideline [noauthor_annotation_2021] specifically aims to standardize the use
of for machine learning purposes. We employ the definitions and guidelines in
these works and consider the pathological labels provided by the cohorts to be
compliant. We conduct three rounds of curation with the goal of incrementally
refining the quality of the curated labels as we gain more experience through
interaction with a large number of images over time. For each curation round,
we commence by exploring literature and visual atlases, paying attention to
also clarify any concerns we might have from the previous iteration. Secondly,
we manually review and curate the _is_normal_ label for each image identified
as healthy by the source dataset, eliminating images with conclusive and
suspect pathologies. Lastly, we do a final review of only the images that have
been identified as healthy in the previous step. The first two steps happen
iteratively over consecutive days where they are the primary tasks, while the
last step happens after a break of a day or two. The three rounds of data
curation happened at least a month apart. To determine the _is_normal_ label
for a given image, we employ the workflow depicted in fig:flow-normz-curate. A
primary inclusion requirement is that an image be an original color fundus
image for which there is an associated condition label provided by the source
dataset. As per the workflow, any image with a source condition label that
indicates some pathology gets the label not normal. On the other hand, images
with a source condition label that suggests a non-pathological eye are
subjected to the other steps in the workflow and may not receive the value
normal. Only images confidently identified as representing healthy eyes are
assigned the value . Moreover, images that are suspected to be pathological
but not conclusive are left unlabeled. The unified catalog is accordingly
updated with the curated _is_normal_ label. Additional metadata is also
assigned, including labels indicating whether the image is of a left or right
eye, and whether the image is centered around the macular or the optic nerve
head.

[width=0.65]/flow-chart-curate-normaz.drawio.pdf

Figure : Flow chart depicting the process for curating _is_normal_ label

Harmonizing the pixel data Additionally, includes a set of Python modules that
automate the harmonization of the images themselves and provide optional
capabilities to statistically standardize the pixel data, thereby aiding in
mitigating batch effects. In this step, the images can be updated to have the
same image size and file format. Furthermore, statistical harmonization first
conducts a within-cohort normalization and then updates the larger unified
dataset. Two statistical harmonization methods are included; 1. A standard
method that makes use of the mean and standard deviation, and 2. A robust
method, which employs the median and inter-quartile range.


Asymptotic Bayes risk of semi-supervised multitask learning
on Gaussian mixture

Minh-Toan Nguyen Romain Couillet

GIPSA-lab, Université Grenoble Alpes LIG-lab, Université Grenoble Alpes

###### Abstract

The article considers semi-supervised multitask learning on a Gaussian mixture
model (GMM). Using methods from statistical physics, we compute the asymptotic
Bayes risk of each task in the regime of large datasets in high dimension,
from which we analyze the role of task similarity in learning and evaluate the
performance gain when tasks are learned together rather than separately. In
the supervised case, we derive a simple algorithm that attains the Bayes
optimal performance.

##  1 INTRODUCTION

Multitask learning (MTL) is a machine learning method in which multiple tasks
are learned simultaneously. It can facilitate knowledge transfer between tasks
and can lead to more informative data representation (Ruder, 2017). Although
learning from related tasks can help disseminate useful information learned
from one task to other tasks, the presence of unrelated tasks can also be
beneficial. With the prior knowledge that two given tasks are unrelated, the
algorithm can learn to ignore irrelevant features of the data distribution,
resulting in better data representation (Paredes et al., 2012).

In this work, we propose a simple model of MTL based on Gaussian mixtures that
focuses on capturing the transfer of knowledge between tasks, leaving out the
data representation aspect. Our paper extends the semi-supervised learning
model studied in Lelarge and Miolane (2019a), which examines the added value
of unlabeled data in a one-task classification. We consider here instead
multiple classification tasks, for which the data in each task are partially
labeled and come from two classes. Thanks to the simplicity of our model, we
can define the correlation between two tasks as a number in $[-1,1]$. We are
interested in the performance gain when correlated tasks are learned together
versus when they are learned separately, assuming the best algorithm is used.
This leads to the concept of _Bayes risk_ , defined as the minimal feasible
probability of misclassifying a new data point not from the training dataset.
Despite the randomness of data, in the limit where both the quantity and the
dimensionality of the data are large with a fixed ratio, the Bayes risk
converges towards a deterministic value.

Although the main objective of this study is to compute the minimum
classification error, it is important to emphasize that the posterior
distribution of a signal given the observed data is a more fundamental object,
as it serves as a basis for deriving optimal estimators with respect to
certain criteria. In the high-dimensional regime, the posterior law of a
signal is a high-dimensional integral, and despite its complexity, it behaves
like a simpler law. This property enables the exact calculations obtained in
this work.

Contributions and related works.

As a first contribution, we derive an exact formula for the asymptotic
Bayesian risk, based on a simple argument that is similar to the cavity method
from statistical physics (Mezard and Montanari, 2009). Although not fully
rigorous, the paper aims to provide a clear intuition of the asymptotic
equivalence that occurs in high dimensions. This concept underlies most of the
equations presented in the paper. The paper is designed to be accessible, and
no prior knowledge of physics is required to understand its contents. Our work
aligns with a body of research that studies the fundamental limit of various
high-dimensional statistical models, including tensor models (Barbier et al.,
2017; Lesieur et al., 2017; Lelarge and Miolane, 2019b), generalized linear
model (Barbier et al., 2019) and Gaussian mixture model (Lesieur et al., 2016;
Lelarge and Miolane, 2019a).

Secondly, we analyze the role of task correlations and how they interact with
other elements of the model, such as the proportion of labeled data in each
task. It is well known that unsupervised learning on a single task with
Gaussian mixture data leads to a phase transition that separates the high and
low noise regimes. We demonstrate that phase transition persists to the case
of multitask and study how it is affected by task correlations. In the context
of source task - target task, we identify the conditions in which the source
task is most beneficial to the target task.

Finally, we derive a simple algorithm that achieves the optimal performance in
the case of supervised learning. Although an optimal performance on a
synthetic data set does not necessarily have a good performance on real data,
this algorithm shows how the optimal algorithms on separate tasks should be
modified when correlations are taken into account. This could offer useful
insights for designing MTL methods in practice.

Although our focus is different, there is some connection between our work and
theoretical studies that investigate optimization-based inference on simple
data models. These studies compute the exact asymptotic performance of
algorithms, and examine how this performance is influenced by factors such as
choice of loss function, regularization, and number of model parameters. On
the other hand, our work focuses on investigating the fundamental limit of
statistical problems regardless of any specific algorithm. It is interesting,
however, that in some cases, the optimization-based methods can nearly reach
or achieve the optimal performance (Mai and Couillet, 2021; Thrampoulidis et
al., 2020; Mignacco et al., 2020; Loureiro et al., 2021; Aubin et al., 2020).
For multitask learning on Gaussian mixtures, Tiomoko et al. (2021b) obtain
exact asymptotic results for least-square support vector machine using random
matrix theory.

There are several reasons to study the GMM. Besides being amenable to
theoretical analysis, it is the simplest model that captures the elements of
MTL that we are interested in: task correlation and transferring of
information. On the application aspect, it is remarked in Lesieur et al.
(2016) that the Bayesian statistics under GMM as a prior can rediscover
several key methods in machine learning such as the K-means or spectral
clustering algorithms. There exists a close relationship between Bayesian
statistics and algorithms. On one hand, Bayesian interpretations can be
established for well-known algorithms such as PCA and SVM (Tipping and Bishop,
1999; Polson and Scott, 2011), which turn out to be standard estimators on
fairly simple data models. On the other hand, by starting with a simple data
model and devising an optimal algorithm based on specific criteria, one can
enhance existing methods or create new ones. (Bishop, 1998; Krzakala et al.,
2012).

Notation: We use the symbol $\langle\cdot,\cdot\rangle$ to denote the scalar
(or inner) product of vectors. If $\boldsymbol{X}=(X_{ij})$, then
$\boldsymbol{X}_{i\cdot}=(X_{ij})_{j}$ and $\boldsymbol{X}_{\cdot
j}=(X_{ij})_{i}$. For $n\in\mathbb{N}$, we use $[n]$ to denote the set
$\mathopen{}\mathclose{{}\left\\{1,2,\dots,n}\right\\}$. The notation
$\boldsymbol{D}_{\boldsymbol{x}}$ represents the diagonal matrix with diagonal
elements given by the vector $\boldsymbol{x}$. If indexed objects such as
$\boldsymbol{X}_{i}$ are given, then $\boldsymbol{X}$ simply means
$(\boldsymbol{X}_{i})_{i}$.

The source code for the simulations in this paper is available at:
https://github.com/Minh-Toan/Bayes-risk

##  2 MODEL

We consider $T$ classification tasks, where task $t$ consists of $N_{t}$ data
points in $\mathbb{R}^{D}$. The $i$-th data point in task $t$, denoted by
$\boldsymbol{Y}_{ti}$, is given by

$\displaystyle\boldsymbol{Y}_{ti}=V_{ti}\boldsymbol{U}_{t}+\sigma_{t}\boldsymbol{Z}_{ti}$
(1)

where $\sigma_{t}>0$. The random variables
$\boldsymbol{V},\boldsymbol{U},\boldsymbol{Z}$ are independent, with

$\displaystyle V_{ti}$ $\displaystyle\stackrel{{\scriptstyle
i.i.d}}{{\sim}}\mathcal{U}(\mathopen{}\mathclose{{}\left\\{-1,1}\right\\}),$
$\displaystyle Z_{ti}$ $\displaystyle\stackrel{{\scriptstyle
i.i.d}}{{\sim}}\mathcal{N}(0,I_{D}),$

and $\boldsymbol{U}_{1},\dots,\boldsymbol{U}_{T}$ are chosen uniformly
randomly on the unit sphere
$S^{D-1}=\mathopen{}\mathclose{{}\left\\{\boldsymbol{x}\in\mathbb{R}^{D},\mathopen{}\mathclose{{}\left\|\boldsymbol{x}}\right\|=1}\right\\}$,
conditioned on the event

$\displaystyle\langle\boldsymbol{U}_{t},\boldsymbol{U}_{t^{\prime}}\rangle=C_{tt^{\prime}},t\neq
t^{\prime}.$

The matrix
$\boldsymbol{C}=(\langle\boldsymbol{U}_{t},\boldsymbol{U}_{t^{\prime}}\rangle)_{t,t^{\prime}=1}^{T}$
is called the _task-correlation matrix_. It follows from the definition that
$\boldsymbol{C}$ is a positive definite matrix with diagonal entries all equal
to $1$. The tasks are said to be _connected_ if for any two tasks $t$ and
$t^{\prime}$, there is a sequence of tasks $t_{1},\dots,t_{k}$ such that
$C_{tt_{1}},C_{t_{1}t_{2}}\dots$ $C_{t_{k}t^{\prime}}\neq 0$.

In other words, the data in task $t$ comes from two classes corresponding to
two Gaussian distributions centered at $\pm\boldsymbol{U}_{t}$ with the same
covariance $\sigma_{t}^{2}I_{D}$. The positions of the centers are not known
and can only be estimated from the data. The class of a data point
$\boldsymbol{Y}_{ti}$ is indicated by $V_{ti}$, so each data point has
probability $1/2$ of belonging to each class. A data point is said to be
_labeled_ if we know which class it belongs to, otherwise it is _unlabeled_.
Independently of all other random variables, each data point in task $t$ is
labeled with probability $\eta_{t}$. The cases $\eta_{t}=1$ and $\eta_{t}=0$
correspond to supervised and unsupervised learning. $C_{tt^{\prime}}$ measures
the correlation between tasks $t$ and $t^{\prime}$. The parameters
$\lambda_{t}=1/\sigma_{t}^{2}$ are called the _signal to noise ratio_ (SNR).
As the SNR increases, the two classes separate and classification is easier.
We study the model in the setting where the dimension and the amount of data
in each task tends to infinity at a fixed rate
$\alpha_{t}=\lim_{D\rightarrow\infty}N_{t}/D$, called the _sampling ratio_.
Note that the model for semi-supervised learning studied in Lelarge and
Miolane (2019a) corresponds to the case $T=1$.

We have access to the dataset $\boldsymbol{Y}=(\boldsymbol{Y}_{ti})$, the
labels as well as model parameters $(\sigma_{t}),(\eta_{t}),(\alpha_{t})$ and
$\boldsymbol{C}$. 111 $\boldsymbol{\sigma}$ and $\boldsymbol{C}$ can indeed be
estimated with vanishing errors as $D\rightarrow\infty$, given that a positive
fraction of labeled data is available in each task, i.e. $\eta_{t}>0$ for all
$t$ (Appendix D). Our job is to use that available information to classify a
new data point $\boldsymbol{Y}_{\text{new}}$ in any given task $t$

$\displaystyle\boldsymbol{Y}_{\text{new}}=V_{\text{new}}\boldsymbol{U}_{t}+\sigma_{t}\boldsymbol{Z}_{\text{new}}$
(2)

We are interested in the minimal classification error, i.e. the Bayes risk

$\displaystyle\inf_{\hat{V}}\mathbb{P}(\hat{V}\neq V_{\text{new}})$ (3)

where the infimum is taken over all estimators of $V_{\text{new}}$.

##  3 RESULTS

Before presenting the results, we need some definitions that will aid in
formulating our findings in a clear and concise manner.

######  Definition 3.1.

The inference of $\boldsymbol{X}\in\mathbb{R}^{D}$ from the data
$\boldsymbol{Y}$ satisfies the _replica symmetric_ (RS) property with
_overlap_ $q$ if in the limit $D\rightarrow\infty$,

$\displaystyle\langle\boldsymbol{X},\boldsymbol{X}^{1}\rangle,\,\langle\boldsymbol{X}^{1},\boldsymbol{X}^{2}\rangle,\,\langle\boldsymbol{X},\hat{\boldsymbol{X}}\rangle,\,\|\hat{\boldsymbol{X}}\|^{2}$
(4)

all converge to the same limit $q$, where
$\boldsymbol{X}^{1},\boldsymbol{X}^{2}$ are sampled independently from the
posterior of $\boldsymbol{X}$ given $\boldsymbol{Y}$, and
$\hat{\boldsymbol{X}}=\mathbb{E}[\boldsymbol{X}|\boldsymbol{Y}]$, called the
_MMSE estimator_ of $\boldsymbol{X}$ given $\boldsymbol{Y}$. 222MMSE stands
for minimum mean-squared error. In some contexts, we use
$\hat{\boldsymbol{X}}$ to refer to a general estimator of $\boldsymbol{X}$,
while the MMSE estimator of $\boldsymbol{X}$ is denoted as
$\hat{\boldsymbol{X}}_{\text{MMSE}}$.

This property holds for a wide range of inference problems in the setting
where the signal is generated from a known distribution. We assume that this
property holds true for our model:

######  Assumption.

$\sigma_{t}^{-1}\boldsymbol{U}_{t}|\boldsymbol{Y}$ and
$N_{t}^{-1/2}\boldsymbol{V}_{t}|\boldsymbol{Y}$ satisfies the RS property for
all $t\in[T]$ with the overlaps denoted by $q_{ut}$ and $q_{vt}$ respectively.

The inclusion of the normalizing factor $\sigma_{t}$ in the definition of
$q_{ut}$ is for the purpose of convenience.

Later in the paper, we will require the following definition in order to prove
the results:

######  Definition 3.2.

Consider the following Gaussian channels

$\displaystyle Y_{i}=\sqrt{\lambda_{i}}X_{i}+Z_{i},\quad i=1,\dots,n$ (5)

with inputs $X_{i}$, outputs $Y_{i}$ and SNRs $\lambda_{i}$. Let
$\hat{\boldsymbol{X}}=\mathbb{E}[\boldsymbol{X}|\boldsymbol{Y}]$. The _overlap
functions_ $F_{\boldsymbol{X},i}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ are
defined as

$\displaystyle
F_{\boldsymbol{X},i}(\boldsymbol{\lambda})=\mathbb{E}[\hat{X}_{i}X_{i}]=\mathbb{E}[\hat{X}_{i}^{2}]$
(6)

$F_{\boldsymbol{X},i}$ is also referred to as the _overlap_ of the signal
$X_{i}$.

The main result of the article unfolds as follows.

######  Result.

i) Under the setting of the model, as $D\rightarrow\infty$, the Bayes risk
converges to

$\displaystyle 1-\Phi\mathopen{}\mathclose{{}\left(\sqrt{q_{ut}}}\right),$

where $\Phi(t)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{t}e^{-x^{2}}dx$

ii) The overlaps $q_{ut},q_{vt}$ satisfies the following equations

$\displaystyle q_{ut}$
$\displaystyle=[\boldsymbol{M}-\boldsymbol{M}(\boldsymbol{I}+\boldsymbol{D}\boldsymbol{M})^{-1}]_{tt}$
(7a) $\displaystyle q_{vt}$ $\displaystyle=\eta_{t}+(1-\eta_{t})F(q_{ut})$
(7b)

with

$\displaystyle\boldsymbol{M}$
$\displaystyle=\mathopen{}\mathclose{{}\left\\{C_{tt^{\prime}}/\sigma_{t}\sigma_{t^{\prime}}}\right\\}_{t,t^{\prime}=1}^{T}$
$\displaystyle\boldsymbol{D}$
$\displaystyle=\operatorname{diag}\\{\alpha_{t}q_{vt}\\}_{t=1}^{T}$
$\displaystyle F(q)$ $\displaystyle=\mathbb{E}[\tanh(\sqrt{q}Z+q)],\quad
Z\sim\mathcal{N}(0,1).$

######  Remark 3.1.

When $q_{ut}=0$, the Bayes risk of task $t$ is equal to $0.5$, which
corresponds to the level of classification error of a random guess. In this
case, we say that the classification of task $t$ is _impossible_. On the other
hand, if $q_{ut}$ is positive, the classification of task $t$ is said to be
_feasible_.

######  Remark 3.2.

The fixed point equations (7a) and (7b) may not uniquely determine the
overlaps. Specifically, for unsupervised learning with high SNR, two solutions
exist: the zero solution is unstable while the non-zero solution is stable,
and the stable solution is naturally chosen as overlaps. In other cases, there
is only one solution.

We can perform a sanity check of the result by considering the following
special cases: if the similarity between any two tasks is zero, the result
implies that MTL has the same asymptotic Bayes risks as learning task
separately, which is obvious since the data from different tasks are
independent, while if $\sigma_{t}=\sigma$ and $C_{tt^{\prime}}=1$ for all
$t,t^{\prime}$, i.e. the data distributions are identical for all tasks, the
asymptotic Bayes risks of all tasks are equal to that of a single task with
parameters $\alpha=\sum_{t}\alpha_{t}$ and
$\alpha\eta=\sum_{t}\alpha_{t}\eta_{t}$ (Appendix B).

##  4 CONSEQUENCES

We present in this section some implications of the main result.

###  4.1 Supervised learning.

For supervised learning with only one task, the minimal classification error
of a new data point $\boldsymbol{Y}_{\text{new}}$ is achieved by the estimator
$\hat{V}_{\text{new}}=\operatorname{sgn}(\langle\boldsymbol{Y}_{\text{new}},\bar{\boldsymbol{Y}}\rangle)$,
where $\bar{\boldsymbol{Y}}=N^{-1}\sum_{i}V_{i}\boldsymbol{Y}_{i}$ (Lelarge
and Miolane, 2019a). In the multitask case, if $\boldsymbol{Y}_{\text{new}}$
is a new data point in task $t$, the following algorithm achieves the optimal
performance:

  1. 1.

Compute

$\displaystyle\bar{\boldsymbol{Y}}_{t}=\frac{1}{N_{t}}\sum_{i=1}^{N_{t}}V_{ti}\boldsymbol{Y}_{ti}$

  2. 2.

Compute

$\displaystyle\tilde{\boldsymbol{Y}}_{t}=\sum_{s=1}^{T}a_{ts}\bar{\boldsymbol{Y}}_{s}$

where
$\boldsymbol{A}=(a_{ts})_{t,s=1}^{T}=\boldsymbol{M}\boldsymbol{D}_{\boldsymbol{\alpha}}(\boldsymbol{I}+\boldsymbol{M}\boldsymbol{D}_{\boldsymbol{\alpha}})^{-1}$.

  3. 3.

The asymptotic Bayes risk is achieved by

$\displaystyle\hat{V}_{\text{new}}=\operatorname{sgn}(\langle\boldsymbol{Y},\tilde{\boldsymbol{Y}}_{t}\rangle).$
(8)

We can see that the optimal estimator for multiple tasks modifies the optimal
estimators for separated tasks $\bar{\boldsymbol{Y}}_{t}$ by taking into
account the correlations between tasks as well as their levels of difficulty
and the relative sizes, measured by $\boldsymbol{C},(\sigma_{t})$ and
$(\alpha_{t})$ respectively. Interestingly, this optimal algorithm coincides
with the method proposed in Tiomoko et al. (2021a) using a different approach.

Figure 1: Bayes risk vs performance of the asymptotic optimal algorithm.
$\alpha_{1}=\alpha_{2}=1$, $\sigma_{1}=1$, $\sigma_{2}=0.5$, $D=1000$.

###  4.2 Unsupervised learning and phase transition.

A particularly interesting behavior that only occurs in the case of
unsupervised learning is phase transition. One of the most well-known example
of this phenomenon is _BBP phase transition_ (Baik et al., 2005) which
concerns a single learning task with $\lim_{D\rightarrow\infty}N/D=1$. When
$\lambda=1/\sigma^{2}\leq 1$, no estimator can achieve a smaller
classification error than $0.5$. In other words, the classification is
objectively impossible since the two classes are statistically identical. On
the other hand, we say that a task is _feasible_ if one can obtain a
classification error smaller than $0.5$. It turns out that phase transition
persists to the case of multitask. Fig. 2 shows the performance of task 1 in
terms of SNRs in the case of two tasks with $N_{1}=N_{2}=D$ and correlation
$c=0.7$. The classification is impossible in the region delimited by the black
curve.

Figure 2: Bayes risk of Task 1 in terms of SNR of each task. Two tasks are
unsupervised, with $N_{1}=N_{2}=D$ and correlation $c=0.7$. The classification
is impossible in the region delimited by the black curve. The impossible
region is identical for two tasks.

The simulation also shows that the impossible regions are identical for both
tasks. In other words, two correlated tasks are either feasible or impossible.
In the general case with any number of tasks, tasks are feasible or impossible
together, given that they are connected.

Note that phase transition disappears as soon as a positive proportion of
labeled data is available, since supervised learning restricted on labeled
data already produces a non-trivial performance.

In the case of two tasks with $N_{1}=N_{2}=D$, the region of impossible
classification is given by

$\displaystyle\Big{\\{}(\lambda_{1},\lambda_{2})\in[0,1]^{2}:(1-\lambda_{1}^{2})(1-\lambda_{2}^{2})\geq
c^{4}\lambda_{1}^{2}\lambda_{2}^{2}\Big{\\}}$ (9)

as shown in Figure 3. As the task correlation $c$ increases from $0$ to $1$,
this region shrinks from the unit square $[0,1]^{2}$ to a quarter of a disk.

Figure 3: The region of impossible classification shrinks as the task
correlation increases. When two tasks are uncorrelated ($c=0$), the region of
impossible classification is the whole square $[0,1]^{2}$. As $c$ increases
from $0$ to $1$, the impossible region shrinks from the unit square
$[0,1]^{2}$ to a quarter of a disk.

Another special case where an explicit formula for the impossible region can
be obtained is when there are $T$ tasks with $N_{1}=\dots=N_{T}=D$, with
correlation $c>0$ between any two of them, and $\lambda_{t}=\lambda$ for all
$t$. It can be shown that the classification is impossible whenever

$\displaystyle\lambda\leq\frac{1}{\sqrt{1+(T-1)c^{2}}}.$ (10)

###  4.3 Semi-supervised learning.

To reduce the number of model parameters in the simulation, we here focus on a
specific setting consisting of one _source task_ and one _target task_. The
source task is comparatively easy: it can be fully labeled, have a high SNR,
or have a larger dataset. We want to see how the target task benefits from the
source task.

Figure 4 illustrates the effect of task correlation. The task correlation $c$
ranges from $0$ to $1$. Note that the correlations $c$ and $-c$ are
essentially the same, since one can be transformed to another by switching
labels in one task. The first task (target task) is composed of a small
dataset ($\alpha_{1}=0.1$) without label ($\eta_{1}=0$), while the second task
(source task) consists of a fully labeled dataset ($\eta_{2}=1$) with twice as
much data ($\alpha_{2}=0.2$). If two tasks are highly correlated ($c\gtrsim
0.5$), the performance of the target task can be significantly improved. When
$c$ is near zero, the decrease in Bayes risk is slow, in order of $O(c^{2})$.
Note that two tasks have the same SNR ($\lambda_{1}=\lambda_{2}=4$), so when
$c=1$ they have the same data distribution and can be combined into a single
task, yielding a identical performance.

Figure 4: Two-task setting: Bayes risks as a function of the task correlation
$c$, with proportions of labeled data $\eta_{1}=0$, $\eta_{2}=1$, oversampling
ratios $\alpha_{1}=0.1$, $\alpha_{2}=0.2$ and SNRs
$\lambda_{1}=\lambda_{2}=4$. When two tasks are highly correlated ($c\gtrsim
0.5$), the performance of task 1 is significantly improved.

In Figure 5, we compute the rate of error reduction in the target task as a
result of transferring information from the source task. We found that MTL is
most effective when the SNR of the target task is near the phase transition
and is smaller than that of the source task, while the proportion of labeled
data is low.

Figure 5: Percentage of reduction of Bayes risk in term of SNR and proportion
of labeled data of the target task, with parameters $c=0.8$, $N_{1}=N_{2}=D$,
$\lambda_{1}=2$, $0\leq\lambda_{2}\leq 3$, $\eta_{1}=1$, $0\leq\eta_{2}\leq
1$.

Intuitively, there are three reasons for this. Firstly, the labeled data from
the target task is more valuable than that of source task, even in this case
where two tasks are highly correlated ($c=0.8$). This leads to lower gain when
the proportion of labeled data in the target task is high. Secondly, if the
source task is more difficult than the target task, i.e. the SNR is higher in
the target task, then the source task is not very useful. Finally, near the
phase transition where the target task struggles, labeled data from the source
task can offer valuable help.

##  5 CAVITY ARGUMENT

The various equations obtained in the paper are underpinned by the phenomenon
of asymptotic equivalence that occurs in the high-dimensional limit. In this
limit, a fairly complicated statistical model decouples into independent
components, and the inference can be performed separately in each component.
This decoupling phenomenon is proven using the so-called _cavity method_. The
following lemma plays a crucial role in the cavity argument presented in this
paper:

######  Lemma 5.1.

Suppose we want to estimate the signal $X\in\mathbb{R}$ with prior $P_{X}$
from the data $\boldsymbol{Y}$ that can be split into two parts as follows.
The first part, denoted by $\boldsymbol{Y}^{x}$, consists of the following
observation on $X$,

$\displaystyle\boldsymbol{Y}^{x}=X\boldsymbol{U}+\boldsymbol{Z},$ (11)

where

  * $\cdot$

$\boldsymbol{U}\in R^{D}$ is unknown with prior $P_{U}$,

  * $\cdot$

$\boldsymbol{Z}\sim\mathcal{N}(0,I_{D})$,

  * $\cdot$

$X$, $\boldsymbol{U}$ and $\boldsymbol{Z}$ are independent.

The second dataset, denoted by $\boldsymbol{Y}^{u}$, is independent of
$\boldsymbol{X}$. Suppose that the law $\boldsymbol{U}|\boldsymbol{Y}^{u}$ has
the RS property with overlap $q$. Then in the limit $D\rightarrow\infty$,

i) The posterior of $\boldsymbol{X}$ given $\boldsymbol{Y}$ is asymptotically
equivalent to the law $\bar{P}$ defined as

$\displaystyle\frac{d\bar{P}(x|\boldsymbol{Y})}{dP_{X}(x)}\propto\exp\Big{(}x\langle\boldsymbol{Y}^{x},\hat{\boldsymbol{U}}\rangle-\frac{1}{2}qx^{2}\Big{)}$
(12)

where $\hat{\boldsymbol{U}}=\mathbb{E}[\boldsymbol{U}|\boldsymbol{Y}]$. As a
consequence, the statistics
$S=\langle\boldsymbol{Y}^{x},\hat{\boldsymbol{U}}\rangle$ is asymptotically
sufficient for estimating $\boldsymbol{X}$ from $\boldsymbol{Y}$.

ii) $S/\sqrt{q}$ converges in law to $\sqrt{q}X+\xi$, where $\xi$ follows
standard normal distribution and is independent of $X$. As a result,
estimating $X$ from $\boldsymbol{Y}$ is asymptotically equivalent to
estimating $X$ from the output of a Gaussian channel with SNR $q$.

###### Proof.

Since $X$ is independent of $\boldsymbol{U}$ and $\boldsymbol{Y}^{u}$, we have

$\displaystyle\frac{dP(x|\boldsymbol{Y})}{dP_{X}(x)}$ $\displaystyle=\int
dP(\boldsymbol{u}|\boldsymbol{Y}^{u})P(x|\boldsymbol{u},\boldsymbol{Y}^{x})$
$\displaystyle\propto\int
dP(\boldsymbol{u}|\boldsymbol{Y}^{u})\exp\Big{(}x\langle\boldsymbol{Y}^{x},\boldsymbol{u}\rangle-\frac{1}{2}x^{2}\|\boldsymbol{u}\|^{2}\Big{)}$
$\displaystyle:=\mathcal{A}$

Define

$\displaystyle\mathcal{B}=\exp\Big{(}x\langle\boldsymbol{Y}^{x},\hat{\boldsymbol{U}}\rangle-\frac{1}{2}qx^{2}\Big{)}$
(13)

To prove (i), we will show that
$\mathbb{E}[(\mathcal{A}-\mathcal{B})^{2}]\rightarrow 0$ in the high-
dimensional limit $D\rightarrow\infty$ for any value of $x$. To do this, it is
sufficient to show that $\mathbb{E}[\mathcal{A}^{2}]$,
$\mathbb{E}[\mathcal{B}^{2}]$ and $\mathbb{E}[\mathcal{A}\mathcal{B}]$
converge to the same limit, using the RS property of
$\boldsymbol{U}|\boldsymbol{Y}^{u}$. Indeed, $\mathbb{E}[\mathcal{A}^{2}]$ can
be written as

$\displaystyle\mathbb{E}\exp\Big{(}\sum_{a=1}^{2}x\langle\boldsymbol{Y}^{x},\boldsymbol{U}^{a}\rangle-\frac{1}{2}x^{2}\|\boldsymbol{U}^{a}\|^{2}\Big{)}$

where $\boldsymbol{U}^{1},\boldsymbol{U}^{2}$ are sampled independently from
$\boldsymbol{U}|\boldsymbol{Y}^{u}$. Substituting
$\boldsymbol{Y}^{x}=X\boldsymbol{U}+\boldsymbol{Z}$ into the previous
expression, we obtain

$\displaystyle\mathbb{E}\exp\Big{(}\sum_{a=1}^{2}xX\langle\boldsymbol{U},\boldsymbol{U}^{a}\rangle+x\langle\boldsymbol{Z},\boldsymbol{U}^{a}\rangle-\frac{1}{2}x^{2}\|\boldsymbol{U}^{a}\|^{2}\Big{)}$

Taking the expectation over $\boldsymbol{Z}$ and using the fact that
$\mathbb{E}[e^{\langle\boldsymbol{a},\boldsymbol{Z}\rangle}]=e^{\frac{1}{2}\|\boldsymbol{a}\|^{2}}$,
we have

$\displaystyle\mathbb{E}[\mathcal{A}^{2}]=\mathbb{E}\exp\Big{(}\sum_{a=1}^{2}xX\langle\boldsymbol{U},\boldsymbol{U}^{a}\rangle+x^{2}\langle\boldsymbol{U}^{1},\boldsymbol{U}^{2}\rangle\Big{)}$

It follows from RS property of $\boldsymbol{U}|\boldsymbol{Y}^{u}$ that

$\displaystyle\lim_{D\rightarrow\infty}\mathbb{E}[\mathcal{A}^{2}]=\mathbb{E}\exp\mathopen{}\mathclose{{}\left(2qXx+qx^{2}}\right)$
(14)

To calculate the limits of $\mathbb{E}[\mathcal{AB}]$ and
$\mathbb{E}[\mathcal{B}^{2}]$, we follow exactly the same procedure, which
involves substituting the definition of $\boldsymbol{Y}^{x}$, taking the
expectation over $\boldsymbol{Z}$, and using the RS property. This leads us to
the same limit as (14), thereby proving (i).

It follows immediately from the asymptotic equivalence between
$P(x|\boldsymbol{Y})$ and $\bar{P}(x|\boldsymbol{Y})$ that the statistics
$\langle\boldsymbol{Y}^{x},\hat{\boldsymbol{U}}\rangle$ is asymptotically
sufficient for estimating $X$ from $\boldsymbol{Y}$. This means that all of
the relevant information about $X$ can be extracted from
$\langle\boldsymbol{Y}^{x},\hat{\boldsymbol{U}}\rangle$ instead of from
$\boldsymbol{Y}$, without any loss of information in high dimensional limit.

Now we have

$\displaystyle\langle\boldsymbol{Y}^{x},\hat{\boldsymbol{U}}\rangle=\langle
X\boldsymbol{U}+\boldsymbol{Z},\hat{\boldsymbol{U}}\rangle=X\langle\boldsymbol{U},\hat{\boldsymbol{U}}\rangle+\langle\boldsymbol{Z},\hat{\boldsymbol{U}}\rangle.$

Given that
$\langle\boldsymbol{Z},\hat{\boldsymbol{U}}\rangle\sim\mathcal{N}(0,\|\hat{\boldsymbol{U}}\|^{2})$
and $\boldsymbol{Z}$ is independent of $X$, in the limit $D\rightarrow\infty$,
this inner product converges in distribution to $\sqrt{q}\xi$, where $\xi$ is
a standard normal random variable independent of $\boldsymbol{X}$. Therefore

$\displaystyle\frac{\langle\boldsymbol{Y}^{x},\hat{\boldsymbol{U}}\rangle}{\sqrt{q}}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}\sqrt{q}X+\xi,\quad D\rightarrow\infty,$

which proves (ii) since the left hand side of the last expression is also a
sufficient statistics of $X$ given $\boldsymbol{Y}$. ∎

To give an application of Lemma 5.1 and to familiarize readers with the cavity
argument before delving into the proof of the main results in the paper, we
will analyze the following tensor model studied in Miolane (2017). Our goal is
to estimate the signals $\boldsymbol{U}$ and $\boldsymbol{V}$ from the
following observations:

$\displaystyle
Y_{ij}=\sqrt{\frac{\lambda}{N}}U_{i}V_{j}+Z_{ij},i\in[N_{u}],j\in[N_{v}]$ (15)

Here, we assume that $U_{i}\stackrel{{\scriptstyle
i.i.d}}{{\sim}}P_{U},V_{j}\stackrel{{\scriptstyle i.i.d}}{{\sim}}P_{V}$ and
the noises $Z_{ij}$ follow independent standard Gaussian distributions for all
$i,j$. We study the model in the limit as $N,N_{u},N_{v}$ tend to infinity
with fixed ratios $N_{u}/N\rightarrow\alpha_{u}$ and
$N_{v}/N\rightarrow\alpha_{v}$. Furthermore, we assume that
$\boldsymbol{U},\boldsymbol{V}$ and $\boldsymbol{Z}=(Z_{ij})$ are independent.
It can be shown that both $N_{u}^{-1/2}\boldsymbol{U}|\boldsymbol{Y}$ and
$N_{v}^{-1/2}\boldsymbol{V}|\boldsymbol{Y}$ satisfies the replica symmetry
property, with overlaps $q_{u}$ and $q_{v}$ respectively. We will use Lemma
5.1 to derive the fixed point equations that satisfied by $q_{u},q_{v}$.

Let $i\in[N_{u}]$ be fixed. The cavity method involves dividing the data
$\boldsymbol{Y}$ into two parts. The first part, denoted as
$\boldsymbol{Y}^{1}$, includes the observations related to $U_{i}$, given by

$\displaystyle\boldsymbol{Y}_{i\cdot}=\sqrt{\frac{\lambda}{N}}U_{i}\boldsymbol{V}+\boldsymbol{Z}_{i\cdot}$
(16)

while the remaining data is denoted as $\boldsymbol{Y}^{2}$. Since the dataset
$\boldsymbol{Y}^{1}$ only contains an insignificant amount of information
relevant to $\boldsymbol{V}$ (one can see that by comparing the sizes of
$\boldsymbol{Y}^{1}$ and $\boldsymbol{Y}^{2}$), estimating $\boldsymbol{V}$
from $\boldsymbol{Y}$ is essentially the same as estimating $\boldsymbol{V}$
from $\boldsymbol{Y}^{2}$. Therefore, $N_{v}^{-1/2}\boldsymbol{V}|Y^{2}$ also
satisfies the RS property with overlap $q_{v}$. It is easy to check that the
Lemma 5.1 is applicable for this model, with $U_{i}$ and
$\sqrt{\lambda/N}\boldsymbol{V}$ respectively playing the role of $X$ and
$\boldsymbol{U}$ in the lemma. As a result, estimating $U_{i}$ from
$\boldsymbol{Y}$ is asymptotically equivalent to estimating the signal $U_{i}$
from the output of a Gaussian channel with SNR $\lambda\alpha_{v}q_{v}$.

For distinct $i,k\in N_{u}$, since $\boldsymbol{Z}_{i\cdot}$ and
$\boldsymbol{Z}_{k\cdot}$ are independent, it can be seen from the proof of
Lemma 5.1-ii that the noises $\xi_{i}$ and $\xi_{k}$ of the equivalent
Gaussian channels associated with $U_{i},U_{k}$ are independent. Therefore
$\hat{\boldsymbol{U}}_{i}$, which depends on $\xi_{i}$ and $U_{i}$, are
asymptotically independent for all $i$. By the law of large number

$\displaystyle
q_{u}=\lim_{N_{u}\rightarrow\infty}\frac{1}{N_{u}}\sum_{i=1}^{N_{u}}\hat{U}_{i}^{2}=F_{U}(\lambda
q_{v})$ (17)

where $F_{U}$ is the overlap function of the Gaussian channel with signal $U$.
Repeating the same argument for $V_{j}$ with $j\in N_{v}$, we obtain the fixed
point equations for $q_{u},q_{v}$:

$\displaystyle q_{u}=F_{U}(\lambda\alpha_{v}q_{v})$ $\displaystyle
q_{v}=F_{V}(\lambda\alpha_{u}q_{u})$

Note that fixed point equations may not uniquely determine overlaps, as they
can have multiple solutions. However, rigorous methods (Barbier and Macris
(2019)) demonstrate that overlaps can be uniquely determined as the minimax
point of a certain function.

##  6 PROOFS

###  6.1 Fixed point equations

Reformulation as a tensor model. Let
$\tilde{\boldsymbol{U}}_{t}=\sqrt{D}\boldsymbol{U}_{t}$, it is shown in
Appendix F that in the limit $D\rightarrow\infty$, $\tilde{U}_{tj}$ are
asymptotically Gaussian with covariance

$\displaystyle\mathbb{E}[\tilde{U}_{tj}\tilde{U}_{t^{\prime}j^{\prime}}]=C_{tt^{\prime}}\delta_{jj^{\prime}}$
(18)

Let $\boldsymbol{W}_{t}=\sqrt{D}\boldsymbol{U}_{t}/\sigma_{t}$, the original
model can be written as a collection of one-dimensional Gaussian channels

$\displaystyle Y_{ijt}=\frac{1}{\sqrt{D}}V_{ti}W_{tj}+Z_{tij}$ (19)

for $1\leq t\leq T,1\leq i\leq N_{t},1\leq j\leq D$. As $D\rightarrow\infty$,
the random variables $W_{tj}$ are asymptotically Gaussian with covariance

$\displaystyle\mathbb{E}[W_{tj}W_{t^{\prime}j^{\prime}}]=M_{tt^{\prime}}\delta_{jj^{\prime}}$
(20)

where $M_{tt^{\prime}}=C_{tt^{\prime}}/(\sigma_{t}\sigma_{t^{\prime}})$.

Next, the information conveyed by the labels can be absorbed into the prior
distribution of $\boldsymbol{V}$. Specifically, if the value of $V_{ti}$ is
unknown, then its prior remains uniform over
$\mathopen{}\mathclose{{}\left\\{-1,1}\right\\}$. Otherwise, if it is known
that $V_{ti}=1$, then the prior of $V_{ti}$ is $\delta(v-1)$. Note that in
this case, the posterior coincides with the prior.

The RS property of $\sigma_{t}^{-2}\boldsymbol{U}_{t}|\boldsymbol{Y}$ implies
that $D^{-1/2}\boldsymbol{W}_{t}|\boldsymbol{Y}$ also has the RS property with
overlap $\boldsymbol{q}_{ut}$.

In summary, the problem can be cast as a tensor model, whereby the objective
is to estimate the signals $\boldsymbol{V}_{t}$ and $\boldsymbol{W}_{t}$ based
on prior information regarding these vectors and noisy observations of the
tensor products $\boldsymbol{V}_{t}\otimes\boldsymbol{W}_{t}$.

Cavity argument. A crucial step in the analysis is to show that in the high-
dimensional limit, estimating $\boldsymbol{V}_{t}$ and $\boldsymbol{W}_{t}$
given $\boldsymbol{Y}$ is asymptotically equivalent to estimating the
coordinates of these vectors from Gaussian channels with independent noises.
The original model is thus equivalent to a much more decoupled model and the
inference can be done separately on each channel.

To obtain the fixed point equations, we follow the same approach as the
example presented in Section 5. We assume that the proportion of unlabeled
data is positive in any task. By taking the limit of these proportions to
zero, we can derive the result for the supervised case. Fix $t\in[T]$ and
$i\in[N_{t}]$ such that $V_{ti}$ is unknown. We divide the data
$\boldsymbol{Y}$ into two parts: $\boldsymbol{Y}^{1}$ consisting of the
observations concerning $V_{ti}$, namely

$\displaystyle\boldsymbol{Y}_{ti}=\frac{1}{\sqrt{D}}V_{ti}\boldsymbol{W}_{t}+\boldsymbol{Z}_{ti}$

and the remaining data $\boldsymbol{Y}^{2}$. Since the dataset
$\boldsymbol{Y}^{1}$ only contains an insignificant amount of information
relevant to $\boldsymbol{W}_{t}$, estimating $\boldsymbol{W}_{t}$ from
$\boldsymbol{Y}$ is essentially the same as estimating $\boldsymbol{W}_{t}$
from $\boldsymbol{Y}^{2}$. Therefore,
$D^{-1/2}\boldsymbol{W}_{t}|\boldsymbol{Y}^{2}$ also satisfies the RS property
with overlap $q_{u}$. It is easy to check that the Lemma 5.1 is applicable,
with $V_{ti}$ and $D^{-1/2}\boldsymbol{W}_{t}$ respectively playing the role
of $X$ and $\boldsymbol{U}$ in the lemma. As a result, estimating $V_{ti}$
from $\boldsymbol{Y}$ is asymptotically equivalent to estimating the signal
$V_{ti}$ from the output of the Gaussian channel with SNR $q_{ut}$. For
distinct $i,k\in[N_{t}]$, since $\boldsymbol{Z}_{ti}$ and
$\boldsymbol{Z}_{tk}$ are independent, it can be seen from the proof of Lemma
5.1-ii that the noises $\xi_{i}$ and $\xi_{k}$ of the equivalent Gaussian
channels associated with $V_{ti},V_{tk}$ are also independent. Therefore
$V_{ti}$, which depends on $\xi_{i}$ and $V_{ti}$, are asymptotically
independent for all $i$ such that $V_{ti}$ is unlabeled. By the law of large
number,

$\displaystyle r_{vt}$
$\displaystyle:=\lim_{N_{t}\rightarrow\infty}\frac{1}{(1-\eta_{t})N_{t}}\sum_{i}\hat{V}_{ti}^{2}$
$\displaystyle=F_{v}(q_{ut})$ (21)

where the sum is over all $i\in[N_{t}]$ such that $V_{ti}$ is unlabeled and
$F_{v}$ is the overlap function of the Gaussian channel with Rademacher
signal. From Appendix E.1,

$\displaystyle F_{v}(q)$ $\displaystyle=\mathbb{E}[\tanh(\sqrt{q}Z+q)],\quad
Z\sim\mathcal{N}(0,1).$ (22)

On the other hand, from the definition of $r_{vt}$, we have

$\displaystyle q_{vt}=\eta_{t}+(1-\eta_{t})r_{vt}$ (23)

The fixed point equation (7b) follows from (6.1), (22) and (23).

Following exactly the same cavity argument, the estimation of $W_{tj}$ given
$\boldsymbol{Y}$ is asymptotically equivalent the the estimation of the signal
$W_{tj}$ from the output of the Gaussian channel with SNR $\alpha_{t}q_{vt}$.
Moreover, the noises corresponding to the signals $W_{tj}$ and
$W_{t^{\prime}j^{\prime}}$ are asymptotically independent for
$(t,j)\neq(t^{\prime},j^{\prime})$. When $j\neq j^{\prime}$, the signals
$W_{tj}$ and $W_{t^{\prime}j^{\prime}}$ are independent. As a result, the
inference on the equivalent Gaussian channels can be performed independently
on groups of $T$ scalar Gaussian channels $(W_{tj})_{t=1}^{T}$. By the law of
large number,

$\displaystyle
q_{ut}=\lim_{D\rightarrow\infty}\frac{1}{D}\sum_{j=1}^{D}\hat{W}_{tj}^{2}=F_{w,t}(\mathopen{}\mathclose{{}\left\\{\alpha_{t}q_{vt}}\right\\}_{t=1}^{T})$
(24)

where $F_{w,t}$ are overlap functions of the Gaussian channel with signal
$\mathcal{N}(0,\boldsymbol{M})$. The explicit formula for $F_{w,t}$ are
computed in Appendix E.2, which gives the fixed point equation (7a).

###  6.2 Bayes risk and optimal algorithm

Suppose we want to classify a new data point $\boldsymbol{Y}_{\text{new}}$ in
task $t$

$\displaystyle\boldsymbol{Y}_{\text{new}}$
$\displaystyle=V_{\text{new}}\boldsymbol{U}_{t}+\sigma_{t}\boldsymbol{Z}_{\text{new}}$
(25)

It is easy to check that Lemma 5.1 can be applied to this problem, with
$V_{\text{new}},\boldsymbol{U}_{t}$ playing the role of $X,\boldsymbol{U}$ in
the lemma, as the posterior $\sigma_{t}^{-1}\boldsymbol{U}_{t}|\boldsymbol{Y}$
satisfies the RS property with overlap $q_{ut}$. As a result, in high
dimensional limit, estimating $V_{\text{new}}$ given
$\boldsymbol{Y},\boldsymbol{Y}_{\text{new}}$ is essentially the same as
estimating the signal $V_{\text{new}}$ from the output of the Gaussian channel
with SNR $q_{ut}$. This implies that the minimal classification error of
$V_{\text{new}}$ is given by that of the Gaussian channel with Rademacher
signal and SNR $q_{ut}$, which is (Appendix E.1)

$\displaystyle 1-\Phi\mathopen{}\mathclose{{}\left(\sqrt{q_{ut}}}\right),$

According to Lemma 5.1,
$S=\langle\boldsymbol{Y}_{\text{new}},\hat{\boldsymbol{U}}_{t}\rangle/\sqrt{q_{ut}}$
is sufficient for estimating $V_{\text{new}}$. Moreover, $S$ converges in law
to the output of the Gaussian channel with signal $V_{\text{new}}$ and SNR
$q_{ut}$. The estimator that minimizes the Bayes risk for this channel is
simply $\operatorname{sgn}(S)$, which leads to the optimal estimator of
$V_{\text{new}}$ as
$\operatorname{sgn}(\langle\boldsymbol{Y}_{\text{new}},\hat{\boldsymbol{U}}_{t}\rangle)$.
The next step is to determine the value of $\hat{\boldsymbol{U}}_{t}$. We will
take advantage of the fact that the vectors $\boldsymbol{U}_{t}$ are
asymptotically Gaussian, so our subsequent argument will rely on the
reformulation (18) of the model. We will need the following result

######  Lemma 6.1.

The following collection of Gaussian channels

$\displaystyle Y_{i}=c_{i}X_{i}+Z_{i},\quad i=1,\dots,n$ (26)

with inputs $X_{i}$, outputs $Y_{i}$, SNR $c_{i}^{2}$ and independent standard
Gaussian noises $Z_{i}$, is equivalent to a single Gaussian channel with
signal $X$, output
$\langle\boldsymbol{c},\boldsymbol{Y}\rangle/\|\boldsymbol{c}\|$ and SNR
$\sum_{i=1}^{n}c_{i}^{2}$. Moreover,

###### Proof.

It is straightforward to verify that the statistics
$S:=\langle\boldsymbol{c},\boldsymbol{Y}\rangle/\|\boldsymbol{c}\|$ is
sufficient for estimating $X$ from $\boldsymbol{Y}$. Moreover,
$S=\mathopen{}\mathclose{{}\left\|\boldsymbol{c}}\right\|X+\xi$ where
$\xi=\mathopen{}\mathclose{{}\left\|\boldsymbol{c}}\right\|^{-1}\langle\boldsymbol{c},\boldsymbol{Z}\rangle$
is standard Gaussian and independent of $X$. This proves the claim of the
lemma. ∎

######  Remark 6.1.

From the proof of Lemma 6.1 we can also see that the noise $\xi$ of the
simplified channel comes from the noises of the original channels.

The Lemma 6.1 implies that, for each $(t,j)$ fixed, the following Gaussian
channels

$\displaystyle Y_{tij}=\frac{1}{\sqrt{D}}V_{ti}W_{tj}+Z_{tij},\quad
i=1,\dots,N_{t}$

which share the same signal $W_{tj}$, can be simplified into a single Gaussian
channel with output $\sqrt{N_{t}}\bar{Y}_{tj}$ and SNR
$N_{t}/D\simeq\alpha_{t}$, where $\bar{Y}_{tj}$ is the $j$-th coordinate of
the vector $\bar{\boldsymbol{Y}}_{t}$ in the algorithm.

For $(t,j)\neq(t^{\prime},j^{\prime})$, the noises of the simplified Gaussian
channels associated with $W_{tj}$ and $W_{t^{\prime}j^{\prime}}$ are
independent, as a consequence of Remark 6.1. Additionally, the signals
$W_{tj}$ and $W_{t^{\prime}j^{\prime}}$ are independent if $j\neq j^{\prime}$.
Therefore, the inference on the simplified Gaussian channels can be carried
out independently on each group of $T$ channels with signals
$(W_{tj})_{t=1}^{T}$. The MMSE estimator on each of these groups can be
computed explicitly as

$\displaystyle(\hat{W}_{tj})_{t=1}^{T}=\boldsymbol{B}(\sqrt{N_{t}}\bar{Y}_{tj})_{t=1}^{T}$

where

$\displaystyle\boldsymbol{B}=\boldsymbol{M}\boldsymbol{D}_{\boldsymbol{\alpha}}^{1/2}(\boldsymbol{I}+\boldsymbol{D}_{\boldsymbol{\alpha}}^{1/2}\boldsymbol{M}\boldsymbol{D}_{\boldsymbol{\alpha}}^{1/2})^{-1}$

(Appendix E.2). Equivalently,

$\displaystyle\hat{\boldsymbol{W}}_{t}=\sum_{s}B_{ts}\sqrt{N_{s}}\bar{\boldsymbol{Y}}_{s}$

Dividing both sides by $\sqrt{D}$ and using $N_{t}/D\simeq\alpha_{t}$, we have

$\displaystyle\tilde{\boldsymbol{Y}}_{t}:=\sigma_{t}^{-1}\hat{\boldsymbol{U}}_{t}\simeq\sum_{s}A_{ts}\bar{\boldsymbol{Y}}_{s}$
(27)

where $A_{ts}=B_{ts}\sqrt{\alpha_{s}}$. Therefore,

$\displaystyle\boldsymbol{A}=\boldsymbol{M}\boldsymbol{D}_{\boldsymbol{\alpha}}(\boldsymbol{I}+\boldsymbol{M}\boldsymbol{D}_{\boldsymbol{\alpha}})^{-1}$

as given in the optimal algorithm. The optimal estimator for $V_{\text{new}}$
is
$\operatorname{sgn}(\langle\boldsymbol{Y}_{\text{new}},\hat{\boldsymbol{U}}_{t}\rangle)=\operatorname{sgn}(\langle\boldsymbol{Y}_{\text{new}},\tilde{\boldsymbol{Y}}_{t}\rangle)$.

##  7 CONCLUSION

This paper proposed a Gaussian mixture model of multitasking learning, in
which each task is a semi-supervised classification problem. We derived an
explicit formula for the Bayes risk, from which the behaviors of the model is
studied through various numerical simulations.

The model in this paper concerns with Gaussian and Rademacher random
variables. However, our method also works for more general tensor models with
random variables of finite second moments.

Acknowledgement. We would like to thank the reviewers for their valuable
feedback and insightful comments, which have significantly contributed to the
improvement of this paper. We would also like to express our appreciation to
Malik Tiomoko for insightful discussions on the algorithmic aspects of the
model and to Hugues Souchard de Lavoreille for his internship report, which
the first author consulted numerous times while working on this paper. Our
research is supported by MIAI.

## Bibliography

  * Aubin et al. (2020) B. Aubin, F. Krzakala, Y. Lu, and L. Zdeborová.  Generalization error in high-dimensional perceptrons: Approaching bayes error with convex optimization.  _Advances in Neural Information Processing Systems_ , 33:12199–12210, 2020.
  * Baik et al. (2005) J. Baik, G. B. Arous, and S. Péché.  Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices.  _The Annals of Probability_ , 33(5):1643–1697, 2005.
  * Barbier and Macris (2019) J. Barbier and N. Macris.  The adaptive interpolation method: a simple scheme to prove replica formulas in bayesian inference.  _Probability theory and related fields_ , 174:1133–1185, 2019.
  * Barbier et al. (2017) J. Barbier, N. Macris, and L. Miolane.  The layered structure of tensor estimation and its mutual information.  In _2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pages 1056–1063. IEEE, 2017.
  * Barbier et al. (2019) J. Barbier, F. Krzakala, N. Macris, L. Miolane, and L. Zdeborová.  Optimal errors and phase transitions in high-dimensional generalized linear models.  _Proceedings of the National Academy of Sciences_ , 116(12):5451–5460, 2019.
  * Bishop (1998) C. Bishop.  Bayesian pca.  _Advances in neural information processing systems_ , 11, 1998.
  * Krzakala et al. (2012) F. Krzakala, M. Mézard, F. Sausset, Y. Sun, and L. Zdeborová.  Statistical-physics-based reconstruction in compressed sensing.  _Physical Review X_ , 2(2):021005, 2012.
  * Lelarge and Miolane (2019a) M. Lelarge and L. Miolane.  Asymptotic bayes risk for gaussian mixture in a semi-supervised setting.  In _2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)_ , pages 639–643. IEEE, 2019a.
  * Lelarge and Miolane (2019b) M. Lelarge and L. Miolane.  Fundamental limits of symmetric low-rank matrix estimation.  _Probability Theory and Related Fields_ , 173(3):859–929, 2019b.
  * Lesieur et al. (2016) T. Lesieur, C. De Bacco, J. Banks, F. Krzakala, C. Moore, and L. Zdeborová.  Phase transitions and optimal algorithms in high-dimensional gaussian mixture clustering.  In _2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pages 601–608. IEEE, 2016.
  * Lesieur et al. (2017) T. Lesieur, L. Miolane, M. Lelarge, F. Krzakala, and L. Zdeborová.  Statistical and computational phase transitions in spiked tensor estimation.  In _2017 IEEE International Symposium on Information Theory (ISIT)_ , pages 511–515. IEEE, 2017.
  * Loureiro et al. (2021) B. Loureiro, G. Sicuro, C. Gerbelot, A. Pacco, F. Krzakala, and L. Zdeborová.  Learning gaussian mixtures with generalized linear models: Precise asymptotics in high-dimensions.  _Advances in Neural Information Processing Systems_ , 34:10144–10157, 2021.
  * Mai and Couillet (2021) X. Mai and R. Couillet.  Consistent semi-supervised graph regularization for high dimensional data.  _J. Mach. Learn. Res._ , 22:94–1, 2021.
  * Mezard and Montanari (2009) M. Mezard and A. Montanari.  _Information, physics, and computation_.  Oxford University Press, 2009.
  * Mignacco et al. (2020) F. Mignacco, F. Krzakala, Y. Lu, P. Urbani, and L. Zdeborova.  The role of regularization in classification of high-dimensional noisy gaussian mixture.  In _International Conference on Machine Learning_ , pages 6874–6883. PMLR, 2020.
  * Miolane (2017) L. Miolane.  Fundamental limits of low-rank matrix estimation: the non-symmetric case.  _arXiv preprint arXiv:1702.00473_ , 2017.
  * Paredes et al. (2012) B. R. Paredes, A. Argyriou, N. Berthouze, and M. Pontil.  Exploiting unrelated tasks in multi-task learning.  In _Artificial intelligence and statistics_ , pages 951–959. PMLR, 2012.
  * Polson and Scott (2011) N. G. Polson and S. L. Scott.  Data augmentation for support vector machines.  _Bayesian Analysis_ , 6(1):1–23, 2011.
  * Ruder (2017) S. Ruder.  An overview of multi-task learning in deep neural networks.  _arXiv preprint arXiv:1706.05098_ , 2017.
  * Thrampoulidis et al. (2020) C. Thrampoulidis, S. Oymak, and M. Soltanolkotabi.  Theoretical insights into multiclass classification: A high-dimensional asymptotic view.  _Advances in Neural Information Processing Systems_ , 33:8907–8920, 2020.
  * Tiomoko et al. (2021a) M. Tiomoko, R. Couillet, and F. Pascal.  Pca-based multi task learning: a random matrix approach.  _arXiv preprint arXiv:2111.00924_ , 2021a.
  * Tiomoko et al. (2021b) M. Tiomoko, H. Tiomoko, and R. Couillet.  Deciphering and optimizing multi-task learning: a random matrix approach.  In _ICLR 2021-9th International Conference on Learning Representations_ , 2021b.
  * Tipping and Bishop (1999) M. E. Tipping and C. M. Bishop.  Probabilistic principal component analysis.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 61(3):611–622, 1999.

##  Appendix A Setting and main result

We summarize here the general setting and main results of the paper. We
consider $T$ tasks, where task $t$ consists in classifying $N_{t}$ data points
in $\mathbb{R}^{D}$ that belong to two different Gaussian clusters with the
same covariance $\sigma_{t}^{2}I_{D}$. The dataset of each task is partially
labeled. The model is studied in the high dimensional setting
$D\rightarrow\infty$ with the following parameters supposed to be known:

  * $\cdot$

$\boldsymbol{C}=(C_{tt^{\prime}})_{t,t^{\prime}=1}^{T}$: task correlations,
with $C_{tt}=1$ for all $t$.

  * $\cdot$

$\alpha_{t}=\lim_{D\rightarrow\infty}N_{t}/D$: oversampling ratios

  * $\cdot$

$\lambda_{t}=1/\sigma_{t}^{2}$: signal-to-noise ratios (SNRs)

  * $\cdot$

$\eta_{t}$: proportion of labeled data in task $t$

We are interested in the minimal probability of misclassifying a new data
point in task $t$, i.e. the Bayes risk of task $t$.

######  Result.

Under the setting of the model, as $D\rightarrow\infty$, the Bayes risk of
task $t$ converges to

$\displaystyle 1-\Phi\mathopen{}\mathclose{{}\left(\sqrt{q_{ut}}}\right),$

where $\Phi(t)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{t}e^{-x^{2}}dx$ and
$(q_{ut},q_{vt})_{t=1}^{T}$ is the stable solution of the system of equations

$\displaystyle q_{ut}$
$\displaystyle=[\boldsymbol{M}-\boldsymbol{M}(\boldsymbol{I}+\boldsymbol{D}\boldsymbol{M})^{-1}]_{tt}$
(28a) $\displaystyle q_{vt}$ $\displaystyle=\eta_{t}+(1-\eta_{t})F(q_{ut})$
(28b)

with

$\displaystyle\boldsymbol{M}$
$\displaystyle=\mathopen{}\mathclose{{}\left\\{C_{tt^{\prime}}/\sigma_{t}\sigma_{t^{\prime}}}\right\\}_{t,t^{\prime}=1}^{T}$
$\displaystyle\boldsymbol{D}$
$\displaystyle=\operatorname{diag}\\{\alpha_{t}q_{vt}\\}_{t=1}^{T}$
$\displaystyle F(q)$ $\displaystyle=\mathbb{E}[\tanh(\sqrt{q}Z+q)],\quad
Z\sim\mathcal{N}(0,1).$

##  Appendix B Special cases

We check the main result with the following special cases.

###  B.1 Uncorrelated tasks

We consider here the case in which $C_{tt^{\prime}}=0$ for all $t\neq
t^{\prime}$, the matrix $\boldsymbol{M}$ is diagonal and we obtain the
following equations for each $t$

$\displaystyle q_{ut}$
$\displaystyle=\frac{1}{\sigma_{1}^{2}}\frac{\alpha_{t}q_{vt}}{\sigma_{t}^{2}+\alpha
q_{vt}}$ $\displaystyle q_{vt}$ $\displaystyle=\eta_{t}+(1-\eta_{t})F(q_{ut})$

which is the same as the fixed point equations when the tasks are learned
separately.

###  B.2 The data for each task follows the same distribution

We consider here the case in which $C_{tt^{\prime}}=1$ and $\sigma_{t}=\sigma$
for all $t,t^{\prime}=1,\dots,T$. We have

$\displaystyle\boldsymbol{M}=\frac{1}{\sigma^{2}}\mathds{1}\mathds{1}^{T},\quad\boldsymbol{D}\boldsymbol{M}=\frac{\boldsymbol{u}\mathds{1}^{T}}{\sigma^{2}}$

where $\boldsymbol{u}=(\alpha_{t}q_{vt})_{t=1}^{\top}$ and
$\mathds{1}=\underbrace{(1,\dots,1)^{\top}}_{T\text{ }1s}$. Applying the
formula

$\displaystyle(\boldsymbol{I}+\boldsymbol{u}\boldsymbol{v}^{T})^{-1}=\boldsymbol{I}-\frac{\boldsymbol{u}\boldsymbol{v}^{T}}{1+\boldsymbol{u}^{T}\boldsymbol{v}}$

for $\boldsymbol{v}=\mathds{1}/\sigma^{2}$, we obtain

$\displaystyle(\boldsymbol{I}+\boldsymbol{D}\boldsymbol{M})^{-1}=\boldsymbol{I}-\frac{\boldsymbol{u}\mathds{1}^{T}}{\sigma^{2}+\boldsymbol{u}^{T}\mathds{1}}$

so

$\displaystyle\boldsymbol{M}-\boldsymbol{M}(\boldsymbol{I}+\boldsymbol{D}\boldsymbol{M})^{-1}=\frac{1}{\sigma^{2}}\frac{\boldsymbol{u}^{T}\mathds{1}}{\sigma^{2}+\boldsymbol{u}^{T}\mathds{1}}\mathds{1}\mathds{1}^{T}$
(29)

It follows from the equation (28a) that for all $t$,

$\displaystyle
q_{ut}=\frac{1}{\sigma^{2}}\frac{\boldsymbol{u}^{T}\mathds{1}}{\sigma^{2}+\boldsymbol{u}^{T}\mathds{1}}:=q_{u}$
(30)

Define $\alpha,\eta$ as

$\displaystyle\alpha=\sum_{t}\alpha_{t},\quad\alpha\eta=\sum_{t}\alpha_{t}\eta_{t}$
(31)

We have

$\displaystyle\boldsymbol{u}^{T}\mathds{1}$
$\displaystyle=\sum_{t}\alpha_{t}q_{ut}$
$\displaystyle=\sum_{t}\alpha_{t}(\eta_{t}+(1-\eta_{t})F(q_{u}))$
$\displaystyle=\alpha\eta+\alpha(1-\eta)F(q_{u})$ $\displaystyle=\alpha q_{v}$
(32)

where $q_{v}$ is defined as

$\displaystyle q_{v}=\eta+(1-\eta)F(q_{u})$ (33)

then from (30) and (B.2), we have

$\displaystyle q_{u}$ $\displaystyle=\frac{1}{\sigma^{2}}\frac{\alpha
q_{v}}{\sigma^{2}+\alpha q_{v}}$ (34)

Since (33) and (34) are exactly the equations for the case of single task
learning with parameters $\alpha$ and $\eta$, the multitask learning problem
is reduced to one single task with parameters $\alpha,\eta$ given by (31).

##  Appendix C Unsupervised learning and phase transition

###  C.1 Region of impossible recovery

In the unsupervised case, the fixed point equations are

$\displaystyle q_{ut}$
$\displaystyle=[\boldsymbol{M}-\boldsymbol{M}(\boldsymbol{I}+\boldsymbol{D}\boldsymbol{M})^{-1}]_{tt}$
(35a) $\displaystyle q_{vt}$ $\displaystyle=F(q_{ut})$ (35b)

which always admits
$(\boldsymbol{q}_{u},\boldsymbol{q}_{v})=(\boldsymbol{0},\boldsymbol{0})$ as
solution. The classification is impossible if and only if this solution is
stable. To analyze the stability of (35) around zero, let $q_{ut},q_{vt}=O(h)$
where $h\rightarrow 0$. For vectors $A$ and $B$ of the same dimension, we
denote $A\simeq B$ if $|A-B|\simeq O(h^{2})$, where $|\,.\,|$ denotes the
Euclidean norm. From

$\displaystyle F(q)=\mathbb{E}[\tanh(\sqrt{q}Z+q)],$ (36)

(Appendix E.1), using the Taylor expansion $\tanh(x)=x-x^{3}/3+o(x^{3})$, we
get

$\displaystyle q_{vt}=F(q_{ut})\simeq q_{ut}$

On the other hand,

$\displaystyle q_{ut}$
$\displaystyle=[\boldsymbol{M}-\boldsymbol{M}(\boldsymbol{I}+\boldsymbol{D}\boldsymbol{M})^{-1}]_{tt}$
$\displaystyle\simeq[\boldsymbol{M}-\boldsymbol{M}(\boldsymbol{I}-\boldsymbol{D}\boldsymbol{M})]_{tt}$
$\displaystyle=[\boldsymbol{M}\boldsymbol{D}\boldsymbol{M}]_{tt}$
$\displaystyle=\sum_{s=1}^{T}M_{ts}^{2}\alpha_{s}q_{vs}$

Let

$\displaystyle\boldsymbol{P}=(M_{ts}^{2}\alpha_{s})_{s,t=1}^{T}=\Big{(}\frac{C_{ts}^{2}}{\sigma_{t}^{2}\sigma_{s}^{2}}\alpha_{s}\Big{)}_{s,t=1}^{T}=(\lambda_{s}\lambda_{t}C_{st}^{2}\alpha_{s})_{s,t=1}^{T}$
(37)

In a small neighborhood of $(\boldsymbol{0},\boldsymbol{0})$, the system of
equations can be approximated up to an error of $O(h^{2})$ by

$\displaystyle\boldsymbol{q}_{v}$ $\displaystyle=\boldsymbol{q}_{u}$ (38)
$\displaystyle\boldsymbol{q}_{u}$
$\displaystyle=\boldsymbol{P}\boldsymbol{q}_{v}$ (39)

Therefore the fixed point $(\boldsymbol{0},\boldsymbol{0})$ is stable if and
only if the module of each eigenvalue of $\boldsymbol{P}$ is not larger than
$1$. Using the property that $AB$ and $BA$ has the same eigenvalues for
general square matrices $A,B$, the matrix $\boldsymbol{P}$ has the same
eigenvalues as the following symmetric matrix

$\displaystyle\boldsymbol{R}=(\sqrt{\alpha_{s}\alpha_{t}}\lambda_{s}\lambda_{t}C_{st}^{2})_{s,t=1}^{T}$
(40)

Note that $\boldsymbol{R}$ is a positive semidefinite (p.s.d) matrix, since it
can be written as Hadamard product of p.s.d. matrices. Therefore, the
classification is impossible if and only if all eigenvalues of
$\boldsymbol{R}$ are not greater than $1$.

When $C_{tt^{\prime}}=c$ for all $t\neq t^{\prime}$ and
$\lambda_{t}=\lambda,\alpha_{t}=1$ for all $t$, we have

$\displaystyle\boldsymbol{R}=\lambda^{2}(c^{2}\mathds{1}\mathds{1}^{T}+(1-c^{2})I)$
(41)

Note that the matrix $\mathds{1}\mathds{1}^{T}$ has eigenvalues $0,\dots,0,T$,
so the largest eigenvalue of $\boldsymbol{R}$ is $\lambda^{2}(1+(T-1)c^{2})$,
from with we obtain the condition for impossible classification

$\displaystyle\lambda^{2}(1+(T-1)c^{2})\leq 1$ (42)

which becomes $\lambda\leq 1$ for the special case $T=1$.

When $T=2$ with task correlation $c$ and $\alpha_{1}=\alpha_{2}=1$, we have

$\displaystyle\boldsymbol{R}=\begin{pmatrix}\lambda_{1}^{2}&c^{2}\lambda_{1}\lambda_{2}\\\
c^{2}\lambda_{1}\lambda_{2}&\lambda_{2}^{2}\end{pmatrix}$ (43)

It is clear that the $(\lambda_{1},\lambda_{2})$-domain of impossible
classification is a subset of $[0,1]^{2}$, otherwise at least one task is
achievable. All eigenvalues of $\boldsymbol{R}$ are less than 1 if and only if
$\operatorname{Tr}(\boldsymbol{I}-\boldsymbol{R})\geq 0$ and
$\det(\boldsymbol{I}-\boldsymbol{R})\geq 0$. The first condition is already
satisfied for $(\lambda_{1},\lambda_{2})\in[0,1]^{2}$ while the second
condition is equivalent to

$\displaystyle(1-\lambda_{1}^{2})(1-\lambda_{2}^{2})\leq
c^{4}\lambda_{1}^{2}\lambda_{2}^{2}$ (44)

###  C.2 Connected tasks are either all feasible or impossible

In the unsupervised case, tasks are considered connected if any two tasks are
directly or indirectly correlated through other tasks. We will prove that if
tasks are connected, then either all tasks are feasible or all tasks are
impossible. As a reminder, for any task $t$, the value of $q_{ut}$ is always
non-negative. If $q_{ut}=0$, then the task $t$ is impossible; otherwise, it is
feasible.

Consider $T$ Gaussian channels with outputs $(Y_{t})_{t=1}^{T}$, signals
$(X_{t})_{t=1}^{T}$ having joint distribution $\mathcal{N}(0,\boldsymbol{M})$
and independent standard Gaussian noises. The SNRs for each channel are
$(\alpha_{t}q_{vt})_{t=1}^{T}$. Then the right-hand side of (35a) corresponds
to the overlap between the signal $X_{t}$ and its MMSE estimator (Appendix
E.2).

Suppose by contradiction that the tasks can be split into non-empty sets such
$S$ and $S^{\prime}$ such that $q_{ut}=0$ for all $t\in S$ while $q_{ut}>0$
for all $t\in S^{\prime}$. Since the tasks are connected, there exists
correlated tasks $t,t^{\prime}$ such that $t\in S,t^{\prime}\in S^{\prime}$.
Therefore, there exists $t,t^{\prime}$ such that $q_{ut}=0,q_{ut^{\prime}}>0$
and $C_{tt^{\prime}}\neq 0$.

Since
$\mathbb{E}[X_{t}X_{t^{\prime}}]=M_{tt^{\prime}}=C_{tt^{\prime}}/(\sigma_{t}\sigma_{t^{\prime}})\neq
0$, $X_{t}$ is correlated with $X_{t^{\prime}}$. Moreover, as
$q_{vt^{\prime}}=F(q_{ut^{\prime}})$ and $q_{ut^{\prime}}>0$, we have
$q_{vt^{\prime}}>0$. Therefore $X_{t}$ is not independent of
$\boldsymbol{Y}=\mathopen{}\mathclose{{}\left\\{\sqrt{\alpha_{s}q_{vs}}X_{s}+Z_{s}}\right\\}_{s=1}^{T}$,
leading to $q_{ut}=\mathbb{E}[X_{t}\mathbb{E}[X_{t}|\boldsymbol{Y}]]>0$, a
contradiction.

##  Appendix D Estimating model parameters from data

Although it is assumed that the model parameters $\boldsymbol{C}$ and
$(\sigma_{t})$ are available for the analysis, we show here that they can
indeed be estimated with vanishing errors as $D\rightarrow\infty$, given that
a positive fraction of labeled data is available in each task, i.e.
$\eta_{t}>0$ for all $t$. First consider the supervised learning case. Let

$\displaystyle\bar{\boldsymbol{Y}}_{t}=\frac{1}{N_{t}}\sum_{i=1}^{N_{t}}V_{ti}\boldsymbol{Y}_{ti}$
(45)

Then we have

$\displaystyle\bar{\boldsymbol{Y}}_{t}=\boldsymbol{U}_{t}+\sqrt{\frac{\sigma_{t}^{2}}{N_{t}}}\bar{\boldsymbol{Z}}_{t}$
(46)

where

$\displaystyle\bar{\boldsymbol{Z}}_{t}=\frac{1}{\sqrt{N_{t}}}\sum_{i=1}^{N_{t}}V_{ti}\boldsymbol{Z}_{ti}$
(47)

It is clear that $\bar{\boldsymbol{Z}}_{t}\stackrel{{\scriptstyle
i.i.d}}{{\sim}}\mathcal{N}(0,I_{D})$ for $t=1,\dots,T$. We consider the
following estimator of $C_{tt^{\prime}}$ for $t\neq t^{\prime}$:

$\displaystyle\hat{C}_{tt^{\prime}}=\langle\bar{\boldsymbol{Y}}_{t},\bar{\boldsymbol{Y}}_{t^{\prime}}\rangle$
(48)

Insert (46) into the definition of $\hat{C}_{tt^{\prime}}$ and use the fact
that
$\langle\bar{\boldsymbol{Z}}_{t},\bar{\boldsymbol{Z}}_{t^{\prime}}\rangle=O(\sqrt{D})$,
$\langle\bar{\boldsymbol{U}}_{t},\bar{\boldsymbol{Z}}_{t^{\prime}}\rangle=O(1)$,
which are direct consequences of Central Limit Theorem, we obtain
$\hat{C}_{tt^{\prime}}=C_{tt^{\prime}}+O(D^{-1/2})$. Moreover

$\displaystyle\|\bar{\boldsymbol{Y}}_{t}\|^{2}=1+\frac{\sigma_{t}^{2}}{\alpha_{t}}+O(D^{-1/2}),$
(49)

from which $\sigma_{t}$ can also be estimated.

In the case where the proportion of labeled data is positive for all tasks, we
can restrict the above estimators on the labeled data and obtain the
approximate values of $\boldsymbol{C}$ and $(\sigma_{t})$ with errors
converging to zero when $D\rightarrow\infty$.

##  Appendix E Simple Gaussian channels

###  E.1 Rademacher signal.

Consider the Gaussian channel given by

$\displaystyle Y=\sqrt{\lambda}X+Z,$ (50)

where the Rademacher signal $X$ takes values of $1$ and $-1$ with equal
probabilities and the standard Gaussian noise $Z$ is independent of $X$. We
have

$\displaystyle P(x|Y)$ $\displaystyle=\frac{P(x)P(Y|x)}{P(Y)}$
$\displaystyle\propto e^{-(Y-\sqrt{\lambda}x)^{2}/2}$ $\displaystyle\propto
e^{\sqrt{\lambda}Yx},$ (51)

from which we obtain the posterior distribution as

$\displaystyle P(x|Y)=\frac{e^{\sqrt{\lambda}Yx}}{2\cosh(\sqrt{\lambda}Y)}$
(52)

and the MMSE estimator $\hat{X}_{\text{MMSE}}=\mathbb{E}[X|Y]$ as

$\displaystyle\hat{X}=\sum_{x=\pm 1}xP(x|Y)=\tanh(\sqrt{\lambda}Y).$ (53)

The overlap between the MMSE estimator and the signal is therefore

$\displaystyle\mathbb{E}[X\hat{X}_{\text{MMSE}}]$
$\displaystyle=\mathbb{E}[X\tanh(\sqrt{\lambda}(\sqrt{\lambda}X+Z)]$
$\displaystyle=\frac{1}{2}\mathbb{E}[\tanh(\lambda+\sqrt{\lambda}Z)]-\frac{1}{2}\mathbb{E}[\tanh(-\lambda+\sqrt{\lambda}Z)]$
$\displaystyle=\frac{1}{2}\mathbb{E}[\tanh(\lambda+\sqrt{\lambda}Z)]-\frac{1}{2}\mathbb{E}[\tanh(-\lambda-\sqrt{\lambda}Z)]$
$\displaystyle=\mathbb{E}[\tanh(\sqrt{\lambda}Z+\lambda)]$ (54)

Next, the error $\mathbb{P}(\hat{X}\neq X)$ for any estimator $\hat{X}$ of $X$
is minimized by the maximum-likelihood estimator:

$\displaystyle\hat{X}_{\text{ML}}$
$\displaystyle=\operatorname*{argmax}_{x=\pm 1}P(x,Y)$
$\displaystyle=\operatorname*{argmax}_{x=\pm 1}e^{\sqrt{\lambda}Yx}$ (55)

This gives us the maximum-likelihood estimator as:

$\displaystyle\hat{X}_{\text{ML}}=\text{sgn}(Y).$ (56)

The Bayes risk is therefore

$\displaystyle\mathbb{P}(X\neq\hat{X}_{ML})$
$\displaystyle=\frac{1}{2}\mathbb{P}(X=1,\hat{X}_{ML}=-1)+\frac{1}{2}\mathbb{P}(X=-1,\hat{X}_{ML}=1)$
$\displaystyle=\frac{1}{2}\mathbb{P}(X=1,Y<0)+\frac{1}{2}\mathbb{P}(X=-1,Y>0)$
$\displaystyle=\mathbb{P}(X=-1,Y>0)$
$\displaystyle=\mathbb{P}(Z>\sqrt{\lambda})$

###  E.2 Correlated Gaussian signals

Consider $T$ Gaussian channels, where the signals $X_{1},\dots,X_{T}$ have a
joint distribution of $\mathcal{N}(0,\boldsymbol{M})$ and are independent of
Gaussian noises $Z_{1},\dots,Z_{T}$ that are independently distributed as
$\mathcal{N}(0,1)$. Specifically, we have:

$\displaystyle Y_{t}=\sqrt{\lambda_{t}}X_{t}+Z_{t},\quad t=1,\dots,T.$

Let
$\hat{X}_{t}=\mathbb{E}\mathopen{}\mathclose{{}\left[X|\boldsymbol{Y}}\right]$
be the MMSE estimator for $X_{t}$. Since $(X_{t},Y_{1},\dots,Y_{T})$ is a
Gaussian vector, $\hat{X}_{t}$ is a linear combination of $Y_{1},\dots,Y_{T}$.
Therefore

$\displaystyle\text{MMSE}_{t}$
$\displaystyle:=\mathbb{E}[(X_{t}-\hat{X}_{t})^{2}]$
$\displaystyle=\min_{\boldsymbol{\beta}_{t}\in\mathbb{R}^{T}}\mathbb{E}\mathopen{}\mathclose{{}\left[(X_{t}-\langle\boldsymbol{\beta}_{t},\boldsymbol{Y}\rangle)^{2}}\right].$

This can be written as a quadratic optimization problem

$\displaystyle\text{MMSE}_{t}=\min_{\boldsymbol{\beta}_{t}\in\mathbb{R}^{T}}\mathopen{}\mathclose{{}\left\\{M_{tt}-2\boldsymbol{a}_{t}^{T}\boldsymbol{\beta}_{t}+\boldsymbol{\beta}_{t}^{T}\boldsymbol{A}\boldsymbol{\beta}_{t}}\right\\}$

with

$\displaystyle\boldsymbol{a}_{t}$
$\displaystyle=\mathopen{}\mathclose{{}\left(\mathbb{E}\mathopen{}\mathclose{{}\left[X_{t}Y_{s}}\right]}\right)_{s=1}^{T}=\mathopen{}\mathclose{{}\left(\sqrt{\lambda_{t}}M_{ts}}\right)_{s=1}^{T}=\boldsymbol{D}_{\boldsymbol{\lambda}}^{1/2}\boldsymbol{M}\boldsymbol{e}_{t}$
$\displaystyle\boldsymbol{A}$
$\displaystyle=\mathopen{}\mathclose{{}\left(\mathbb{E}\mathopen{}\mathclose{{}\left[Y_{s}Y_{s^{\prime}}}\right]}\right)_{s,s^{\prime}=1}^{T}=\mathopen{}\mathclose{{}\left(\sqrt{\lambda_{s}\lambda_{s^{\prime}}}M_{ss^{\prime}}+\delta_{ss^{\prime}}}\right)_{s,s^{\prime}=1}^{T}=\boldsymbol{I}+\boldsymbol{D}_{\boldsymbol{\lambda}}^{1/2}\boldsymbol{M}\boldsymbol{D}_{\boldsymbol{\lambda}}^{1/2}.$

This optimization problem admits a unique minimizer
$\boldsymbol{\beta}_{t}=\boldsymbol{A}^{-1}\boldsymbol{a}_{t}$, from which we
obtain

$\displaystyle\hat{\boldsymbol{X}}$
$\displaystyle=\boldsymbol{M}\boldsymbol{D}_{\boldsymbol{\lambda}}^{1/2}(\boldsymbol{I}+\boldsymbol{D}_{\boldsymbol{\lambda}}^{1/2}\boldsymbol{M}\boldsymbol{D}_{\boldsymbol{\lambda}}^{1/2})^{-1}\boldsymbol{Y}$
(57) $\displaystyle\text{MMSE}_{t}$
$\displaystyle=[\boldsymbol{M}(\boldsymbol{I}+\boldsymbol{D}_{\boldsymbol{\lambda}}\boldsymbol{M})^{-1}]_{tt}$
(58) $\displaystyle\mathbb{E}[X_{t}\hat{X}_{t}]$
$\displaystyle=[\boldsymbol{M}-\boldsymbol{M}(\boldsymbol{I}+\boldsymbol{D}_{\boldsymbol{\lambda}}\boldsymbol{M})^{-1}]_{tt}.$
(59)

##  Appendix F The uniform prior is asymptotically Gaussian

To generate $(\boldsymbol{U}_{1},\dots,\boldsymbol{U}_{T})$ according to the
prior distribution specified in the model, we follow these steps:

  1. 1.

Generate $\boldsymbol{Z}_{1},\dots,\boldsymbol{Z}_{T}\stackrel{{\scriptstyle
i.i.d}}{{\sim}}\mathcal{N}(\boldsymbol{0},I_{D})$.

  2. 2.

Orthonormalize $\boldsymbol{Z}_{1},\dots,\boldsymbol{Z}_{T}$ using Gram-
Schmidt process, we obtain orthonormal vectors
$\boldsymbol{S}_{1},\dots,\boldsymbol{S}_{T}$

  3. 3.

$(\boldsymbol{U}_{1},\dots,\boldsymbol{U}_{T})=(\boldsymbol{S}_{1},\dots,\boldsymbol{S}_{T})\boldsymbol{C}^{1/2}$,
where $(\boldsymbol{U}_{1},\dots,\boldsymbol{U}_{T})$ denotes the $D\times T$
matrix with columns $\boldsymbol{U}_{1},\dots,\boldsymbol{U}_{T}$.

In the high dimensional limit, the vector
$\boldsymbol{Z}_{1},\dots,\boldsymbol{Z}_{T}$ are asymptotically orthogonal,
so the orthonormalizing step produces approximately
$n^{-1/2}(\boldsymbol{Z}_{1},\dots,\boldsymbol{Z}_{T})$, which implies that if
$\boldsymbol{W}_{t}=\sqrt{D}\boldsymbol{U}_{t}$, then $\boldsymbol{W}_{t}$’s
are asymptotically Gaussian with covariance

$\displaystyle\mathbb{E}[W_{ti}W_{t^{\prime}j}]=\delta_{ij}C_{tt^{\prime}}$
(60)

It is worth noting that this is a direct consequence of the equivalence
between the canonical and microcanonical ensembles in statistical physics.