Deciphering and Optimizing Multi-Task Learning: a Random Matrix Approach
Authors: Malik Tiomoko
Hafiz Tiomoko Ali
Romain Couillet
Venue: ICLR 2021 Spotlight (2021)
Keywords: Transfer Learning
Multi Task Learning
Random Matrix Theory

Abstract: This article provides theoretical insights into the inner workings of multi-task and transfer learning methods, by studying the tractable least-square support vector machine multi-task learning (LS-SVM MTL) method, in the limit of large ($p$) and numerous ($n$) data. By a random matrix analysis applied to a Gaussian mixture data model, the performance of MTL LS-SVM is shown to converge, as $n,p\to\infty$, to a deterministic limit involving simple (small-dimensional) statistics of the data.

We prove (i) that the standard MTL LS-SVM algorithm is in general strongly biased and may dramatically fail (to the point that individual single-task LS-SVMs may outperform the MTL approach, even for quite resembling tasks): our analysis provides a simple method to correct these biases, and that we reveal (ii) the sufficient statistics at play in the method, which can be efficiently estimated, even for quite small datasets. The latter result is exploited to automatically optimize the hyperparameters without resorting to any cross-validation procedure. 

Experiments on popular datasets demonstrate that our improved MTL LS-SVM method is computationally-efficient and outperforms sometimes much more elaborate state-of-the-art multi-task and transfer learning techniques.

Published as a conference paper at ICLR 2021
DECIPHERING AND OPTIMIZING MULTI-TASK LEARNING: A RANDOM MATRIX APPROACH
Malik Tiomoko
Hafiz Tiomoko Ali
Laboratoire des Signaux et Systèmes Université Paris-Sud
Huawei Technologies Research and Development (UK) London, UK hafis z, tioooo.. al @@hhawwee....... com
Orsay, France
ma Liki t tiomokolu latrokkk@u-psud....
Romain Couillet
Gipsa Lab
Université Grenoble-Alpes Saint Martin d d'Hères, France
romain. coui 1esseggpsstaaaeeeeee lab. waab.ggreobbeiing.... fr
ABSTRACT
This article provides theoretical insights into the inner workings of multi-task and transfer learning methods, by studying the tractable least-square support vector machine multi-task learning (LS-SVN MTL) method, in the limit of large (p) and numerous (n) data. By a random matrix analysis applied to a Gaussian mixture data model, the performance of MTL LS-SVM is shown to converge, as + co, a deterministic limit involving simple ssmall-dimensional)) statistics of the data.
We prove (i) that the standard MTL LS-SVM algorithm in general strongly biased and may dramatically fail (to the point that individual single-task LS-SVMs may outperform the MTL approach, even for quite resembling tasks): our analysis provides simple method to correct these biases, and that we reveal (ii) the sufficient statistics at play in the method, which can be efficiently estimated, even for quite small datasets. The latter result is exploited to automatically optimize the hyperparameters without resorting to any cross cross- validation procedure.
Experiments on popular datasets demonstrate that our improved MTL LS-SVM method is computationally-etii rate state-of state-of-the-art multi-task and transfer learning techniques.
and outperforms sometimes much more elabo-
INTRODUCTION
The advent of elaborate learning machines capable to surpass human performances on dedicated tasks has reopened past challenges in machine learning. Transfer learning, and multitask learning (MTL) in general, by which known tasks are used to help machine learn other related tasks, is one of them. The particularly interesting aspects of multi-task learning lie in the possibility (i) exploit the resemblance between the datasets associated to each task so the tasks "help each other" and (ii) to train a machine on specific target dataset comprised of few labelled data by exploiting much larger labelled datasets, however composed of different data. Practical applications are numerous, ranging from the prediction of student test results for a collection of schools (Aitkin Longford (9866. to survival of patients in different clinics, to the value of many possibly related financial indicators (Allenby & Rossi 1998), to the preference modelling of individuals in a marketing context, etc.
Since MTL seeks to improve the performance of task with the help of related tasks, a central issue to (i) understand the functioning of MTL, (ii) adequately adapt its hyperparameters and eventually (iii) improve its performances consists in characterizing how MTL relates tasks to another and in identifying which features are "transferred"". The article aims to decipher these fundamental aspects for sufficiently general data models.

---

Published as a conference paper at ICLR 2021
Several data models may be accounted for to enforce relatedness between tasks. A common assump- tion is that the data lie close to each other in a geometrical sense (Evgeniou & Pontil 2004), live in low dimensional manifold (Agarwal et al. 2010), or share common prior (Daumé Mi 2009). We follow here the latter assumption in assuming that, for each task, the data arise from a 2-class Gaussian mixture
Methodologically, in its simplest approach, MTL algorithms can be obtained from a mere extension of support vector machines (SVM), accounting for more than one task. That is, instead of finding the hyperplane (through its normal vector w) best separating the two classes of a unique dataset, (Evgeniou & Pontil| 2004) proposes to produce best separating hyperplanes (or normal vectors) wi....,Wk for each pair of data classes of k tasks, with the additional constraint that the normal vectors take the form wi = wp + U/ for some common vector wy and dedicated vectors et-- The amplitude of the vectors B; is controlled (through an additional hyperparameter) to enforce or relax task relatedness. We study this approach here. Yet, to obtain explicit and thus more insightful results, we specifically resort to least-square SVM (as proposed e.g., in (Xu et al. 2013 rather than a margin- based SVM. This only marginally alters the overall behavior of the MTL algorithm and has no impact on the main insights drawn in the article. Moreover, by a now well-established universality argument in large dimensional statistics, (Mai et al., 2019) show that quadratic (least- square) cost functions are asymptotically optimal and uniformly outperform alternative costs (such as margin-based methods or logistic approaches), even in a classification setting. This argument further motivates the choice of considering first and foremost the LS-SVM version of MTL-SVM.
Technically, the article exploits the powerful random matrix theory to study the performance of the MTL least-square SVM algorithm (MTL LS-SVM) for data arising from Gaussian mixture model, assuming the total number n and dimension p of the data are both large, i.e., as n, - oo with p/n + E (0, oo). As such, our work follows after the recent wave of interest into the asymptotics of machine learning algorithms, such as studied lately in c.g. (Liao & Couillet [011 Deng et al. 2019)] Mai & Couillet 2018 El Karoui et al. 2010). Our analysis sis reveals the following major conclusions:
we exhibit the sufficient statisties, which concretely enable task comparison in the MTL LS-SVM algorithm; we show that, even when data are of large dimensions (p >> 1), these statistics remain small dimensional (they only scale with the number k of tasks);
while it is conventional to manually set labels associated to each dataset within 11,, we prove that this choice is largely suboptimal and may even cause MTL to severely fail (causing "negative transfer"); we instead provide the optimal values for the labels of each dataset, which depend on the sought-for objective: these optimal values are furthermore easily estimated from very few training data (i.e., no vross-vvlidation is needed);
for unknown new data x, the MTL LS-SVM algorithm allocates a class based on the comparison of a score g(x) to a threshold Ç, usually set to zero. We prove that, depending on the statistics and number of elements of the training dataset, bias is naturally induced that makes ( = a largely suboptimal choice in general. We provide a correction for this bias, which again can be estimated from the training data alone;
we demonstrate on popular real datasets that our proposed optimized MTL LS-SVM is both resilient to real data and also manages, despite its not being a best-in-class MTL algorithm, to rival and sometimes largely outperform competing state-of-the-art algorithms.
These conclusions thus allow for an optimal use of MTL LS-SVM with ieformmncc-maxiiiize hyperparameters and strong theoretical guarantees. As such, the present article offers through MTL LS-SVM a viable fully-controlled (even better performing) alternative to state-of-the-art MTL.
Reproducibility. Matlab and Julia codes for reproducing the results of the article available in the supplementary materials.
[2M] = e [2k] Notation. em E Rd is the canonical vector of RD with [e 8mi- Moreover, e
2(1 +)+
Similarly, P. Raxx is the matrix with [F|g] Jab 5.b The notations A B and A ④ B
In the supplementary material, we extend this setting much broader and more realistic scope, and justify in passing the relevance of Gaussian mixture modelling address multi-task leaming with real data.
2

---

Published as a conference paper at ICLR 2021
for matrices or vectors A, B respectively the Kronecker and Hadamard products. Dr is the diagonal matrix containing on its diagonal the elements of the vector 2 and A, is the i-th row of A. The notation Å is used when a centering operation is performed on the matrix or vector A. Uppercase calligraphic letters (A, T,, M, V.... are used for deterministic small dimensional matrices. Finally, 1m and Im are respectively the vector of all one's of dimension m and the identity matrix of dimension m m. The index pair i,j generally refers Class j in Task
2 RELATED WORKS
Let us first point out the difference between MTL and transfer learning: while MTL makes no distinction between tasks and aims to improve the performance of all tasks, transfer learning aims to maximize the performance of a target task with the help of all source tasks. Yet. both methods mostly sharing the same learning process, in this section, mainly focus the MTL literature, which is divided into parameter-based versus feature-based MTL.
In the parameter-based MTL approach, the tasks assumed to share some parameters (e.g., the hyperplanes best separating each class) or their hyperparameters have a common prior distribution. Existing learning methods (SVM, logistic regression, etc.) can then be appropriately modified to incorporate these relatedness assumptions. In this context, (Evgeniou & Pontil 2004) Xu et al. 2013 Parameswaran & Weinberger 2010) respectively adapt the SVM, LS-SVM, and Large Margin
Nearest Neighbor (LMNN) algorithms to the MTL paradigm. The present article borrows ideas from
Evgeniou & Pontil (2004); Xu al. (2013).
In the feature-based MTL approach, the tasks data are instead assumed to share a low-dimensional common representation. In this context, most the works aim to determine a mapping of the ambient data space into a low-dimensional subspace (through sparse coding, deep neural networks, principal component analysis, etc.) in which the tasks have high similarity (Argyriou et al. 2007 Maurer et al. 2013; Z et al.) 2016 Pan et al. 2010); other works simply use feature selection method by merely extracting a subset of the original feature space (Obozinski et al. 2006 Wang & Ye 2015 Gong et al. 2012). We must insist that, in the present work, our ultimate objective is study and improve gentari"""""" MTL mechanisms under no structural assumption on the data; this approach quite unlike recent works exploiting convolutive techniques in deep neural nets low dimensional feature-based methods to perform transfer or multi-task learning mostly for computer vision.
From theoretical standpoint though, few works have provided a proper understanding of the various MTL algorithms. To our knowledge, the only such results arise from elementary learning theory (Rademacher complexity, VC dimension, covering number, stability) and only provide loose
performance bounds (Baxter 2000, Ben-David & Schuller 2003 Baxter 1997). As such, the present work fills a long-standing gap the MTL research.
THE MULTI-TASK LEARNING SETTING
Let X E RPX" be a collection of n independent data vectors dimension p. The data are divided
into i subsets attached to individual "tasks". Specifically, letting X = [X1...., Xx]. Task is
binary classification problem from the training samples X; = [x(") "('"x(()) x Rexms with x(1) [x.11) x 1 E RRxxn the nij vectors of class j E 21 for Task i. In particular, Σk Di=n n4 and n; = n11 + n22 for each E (1,...,k:) k:).
(i)
To each za E R2 of the training set is attached a corresponding "label" (or score) E R. We denote V: = "ym
RT, the vector of all labels for Task and y = [vT ...., 0g T E RD the vector of all labels. These labels are generally chosen to be +1 but, for reasons that will become clear in the course of the article, we voluntarily do not enforce binary labels here.
Before detailing the multitask classification scheme, preliminary task-wise centering operation is performed on the data, i.c., we consider in the following the datasets
x; X; Tns
T 1 11,1111,17 1T.1TT))
1
Vi E (1....,k).
3

---

Published as a conference paper at ICLR 2021
As such, systematically work the labeled datasets (X1, 311 ,1)..... (Xx: We). Remark I in the supplementary material motivates this choice, which avoids extra biases produced by the algorithm.
3.1 THE OPTIMIZATION FRAMEWORK
The multitask learning least square support vector machine (MTL LS-SVM) aims predict, for input vectors x & R not belonging to the training set, their associated score upon which decision on the class allocation of x is taken, for a given larget lask. To this end, based on the labeled sets (X1. vi)...., (Xx, 3k.. MTL LS- SVM determines the normal vectors W [w] .2....,, wa] Ro*k and intercepts = [b,, b2.... bu] E IR defining k separating hyperplanes for the corresponding k binary classification tasks. In order to account for task relatedness, each wi assumes the form w = wp + for some common wp E Rº and task-dedicated 222 E R"
Formally, writing
Uu...... 2k
E
Raxk (so that W wolk + V) and following the work of 2013). the optimization function is given by
(Evgeniou & Pontil 2004
Xu et al.
min (wo. (wa.V,b) V.b)e 2A IP x X
2
1
|0: 2
K&l, 2 Σ
& = (XT wi b,ln,)) Isisk k.
2
%
In this expression, the parameter À enforces more task relatedness while the parameters 7/1, "/,,.... 7k enforce better classification of the data in their respective classes.
Being a quadratic optimization problem under linear equality constraints, wo, V, b are obtained explicitly (see details in Section of the supplementary material). The solution is best described through the expression of the hyperplanes WI,..., w E Re which take the form:
1p) AZa,
and 6 = (PTQP)-1PT Qy, where a QQ Q+ (1, 1000:=pp0000011111000000 R" the Lagrangian dual and
nT 2T AZ + +T,) {1
k
Q =
E Raxx
Z
Σ
F!!! @ X, E Rpkxn
kp
i=1
A (D, + X117) 2 Ip Rhpxkp
P
1n, E Rux
with = In,..., ] and D. = diag(n).
MTL LS-SVM differs from single-task joint LS-SVM for all data in that the data X & are not treated simultaneously but through distinct filters: this explains why Z R is not the mere concatenation [Xi,...,XX, but block-diagonal structure isolating each X, As such, the X, 's-relaaiing matrix plays an important role in the MTI. learning process.
With this formulation for the solution (W, b), the prediction of the class of any new data point E RP for the target Task is then obtained from the classification score
gx(x)
=
[k] c
x
AZa + b;
(1)
kp
where x = 1X1,,, is centered version of x with respect to the training dataset for Task i.
3.2
LARGE DIMENSIONAL STATISTICAL MODELLING
The first objective of the article is to quantify the MTL performance, and thus of the (a priori intricate) statistics of g (x), under a sufficiently simple but telling Gaussian mixture model for training and test data.
Assumption (Distribution of X and x). The columns of [X, x] are independent Gaussian random (5)
(() variables. Specifically, the nij samples x. ..... Finyy of class j for Task i are independent N M(Hjj Ip)
vectors, and we let Ap4 = paa /422- As for x, it follows independent A M(xx; Ip) vector.
4

---

Published as a conference paper at ICLR 2021
In the supplementary material, Assumption i relaxed [X,x] arising from generative model of the type = = his (2 (2 for 2 ~ NV 1p) and he : IR + IP a 1-Lipschitz function. This model encompasses extremely realistic data models, including data arising from generative networks (e.g., GANs (Goodfellow et al. 2014)) and shown in the supplementary material to be universal in the sense that, n. + oo, the asymptotic performances of MTL LS- SVM only depend on the
statistical means and covariances the : the performances under complex mixtures are thus proved to coincide with those under elementary Gaussian mixture. This generalized study however comes at the expense of more complex definitions and formulas, which impedes readability; hence the simpler isotropic Gaussian mixture model here.
Our central technical approach for the performance evaluation of the MTL. LS-SVM algorithm consists in placing ourselves under the large p, n regime of random matrix theory.
Assumption 2 (Growth Rate). As
00, n/p
Co 0 and, for S < k,
Ry
Cij > 0. We let = G11 + 42 C = [c,,...
E R
With these notations and assumptions, are in position present main theoretical results.
4
THE MULTI-TASK LEARNING ANALYSIS
4.1 TECHNICAL STRATEGY AND NOTATIONS
To evaluate the statistics of gi (x) (equation D. we resort to finding so-called deterministic equivalents for the matrices Q. AZQ. etc., which appear at the core of the formulation of g: (x). Those are provided in Lemma of the supplementary material. Our strategy then consists in "decoupling"
the effect of the data statistics from those of the MTL hyperparameters' X, 7...... . 7h- Specifically, we extract two fundamental quantities for our analysis: a data-related matrix M E x22x2 and a hyperparameter matrix A E R
M Σ 1-=1
AuT Apj (E! @ (coo))
A
1x + +D (D, + A1x17) D
where Â = ( Ax]" are the unique positive solutions to the implicit system A, Ass
(this is implicit because A is function of the Áý's). In passing, it will appear convenient to use the shortcut notation A =
E IR2h where Á.G St An
We will see that M plays the role, in the limit of large p, n, of a sufficient statistic for the performance of the MTL LS-VVM algorithm only involving (i) the data statistics f11..... .kz and (ii) the (limiting) relative number C11 cu//c....,, Ck2/Cs Cs of elements per class in each task. As for A, it captures the information about the impact of the hyperparameters X, 7i, 7hh and of the dimension ratios CI,..., Ck and co. These two matrices will be combined in the core matrix T E R2 of the upcoming MTL LS-SVM performance analysis, defined as I' (12x + ((1111)) o M) where we recall that 'O" is the Hadamard (element-win wise) matrix product.
We raised in the introduction of Section 3 that we purposely relax the binary "labels" Yij associated to each datum rij in each task to become "scores" yie E This will have fundamental consequences to the MTL performance. Yet, since T.1,..., Tin; are i.i.d. data vectors, we impose equal scores ya = = Vin, within each class. As such, we may reduce the complete score vector y E IR" under the form y = [wn1] 1 6k2 Dx21 1 for ÿ [V1,.... 0k2)1 R2h From Remark of the supplementary material, the performances of MTI are insensitive to a constant shift in the scores yar and y/2 of every given Task i: as such, the recentered version ÿ = [ [i2] of y. where [ Tu + 112
m; (12) will be central in the upcoming results.
4.2 MAIN RESULTS
Theorem 1 (Asymptotics of gi (x)). Under Assumptions 2 for x ~ N N( Ip) with px = pig.
g: (x) Gij + 0, Gi ((mig,
5

---

Published as a conference paper at ICLR 2021
in distribution where, letting [m11..... m42 T
- D D 150012 + +V:) rDj
A TDA of
= -ー
A.
with V: = (AD of. A 2 121
O M and K. = [A Al - Deo D Al)
As anticipated, the statistics of the classification scores gi(x) mainly depend on the data statistics j&,' and on the hyperparameters À and ",,....; "/k through the matrix I (and more marginally through V; and IC for the variances).
Since gi (x) has a Gaussian limit centered about maj, the (asymptotic) standard decision for x to be
allocated to Class (x + Ci) or Class 2 (x - C2) for Task is obtained by the "averaged-meant test
C1
(x)
(ma1 + m22)
(2)
the classification error rate c21 = P(x + C2 x E C1) of which then
G = (i(x)= 2 Mà; + m2,
maa m22
x E Ci
=
+ o1)
(3)
2
20;
with mij. of in Theorem and ((t) Je du.
Further comment on is due before moving to practical consequences of Theorem [ From the expression (A @ 121!)-1 @ M, we observe that: (i) if X < 1, then A is diagonal dominant and thus "filters out" in the Hadamard product all off-diagonal entries of M, i.e., all cross-terms Aμ₃ Au, for i * j, therefore refusing exploit the correlation between tasks; (ii) if instead À is not small, A may be developed (using the Sherman -orriiooo matrix inverse formulas) as the sum of a diagonal matrix, which again filters out the Au! AHy for * j. and of rank-one matrix which instead performs a weighted sum (through the 7 's and the Á/'s) of the entries of M. Specifically, letting Y
As such, disregarding the regularization effect of the Â,'s, the off-diagonal Aud Auu entry of M is weighted with coefficient (7:r)) the impact of the 7/'s is thus strongly associated to the relevance of the correlation between tasks.
b 7/ (xi".....777) in the expression of A. we have (D,, + x1x = =D, 1- El 7
fundamental aspect of Theorem D is that it concludes that the performances of the large dimensional (n.p >> 1) classification problem at hand merely boils down to 2k-dimension statistics, as all objects defined in the theorem statement are at most of size 2k. More importantly from a practical perspective, these "sufficient statistics" are easily amenable to fast and efficient estimation: it only requires a few training samples to estimate all quantities involved in the theorem. This, as a corollary, lets one envision the possibility of efficient transfer learning methods based on very scarce data samples as discussed in Remark !
Estimating maj and o; not only allows one anticipate theoretical performances but also enables the actual estimation of the decision threshold 1 (ma + m222) in equation 2 and opens the possibility to largely optimize MTL LS-SVM through an (asymptotically) optimal choice of the training scores ÿ. Indeed, the asymptoties in Theorem [ depend in elegant manner on the training data labels (scores) ÿ. Since the variance of is independent of the classes, we easily determine the vector ÿ = "* minimizing the misclassification probability for Task i
-2
11 TLZx - D DI (e
12
12k )1 $2
V' arg max
arg JER2K
JERA
of
TTD 01, V.)IDDA
the solution of which explicit
ÿ = with corresponding (asymptotically) optimal classification error ej (equation 3 given by
@ MD ( |2|] - -2 ) H. = (D Φ1, + +1)
(4)
c - e - - Tc(
[2
[2N]
) g = - MDT @ MI
6

---

Published as a conference paper at ICLR 2021
The only non-diagonal matrices in equation 4 are I and V; in which M plays the role of "variance profile" matrix. In particular, assuming Áμu Ape = 0 for all * (i.e., the statistical means of all tasks are orthogonal to those of Task i), then the two Task i are all zero but on the 2 x 2 diagonal block. Therefore, ÿ' must be filled with zero entries but on its Task i two elements. All other values at the zero entry locations of ÿ' (such the usual ÿ = [1.-l,.... 1, - ! would be suboptimal and possibly severely detrimental to the classification performance of Task (not by altering the means ma1, m42 but by increasing the variance of). This extreme example strongly suggests that, in order to maximize the MTL performance on Task i, one must impose low scores y to all Tasks j strongly different from Task i.
and columns of M associated to
The choice y [I.-1...., 1, -1] can also be very detrimental when Aμ₃ Ap,, < 0 for some i. that is, when the mapping of the two classes within each task is reversed (e.g., if Class 1 in Task 1 is closer to Class than Class 1 in Task 2). In this setting. it easily seen that ý = 11. 1,- works against the classification and performs much worse than single-task LS-SVM.
Another interesting conclusion arises from the simplified setting of equal number of samples per task
72.2- In this case, 3 -1" ((A @ 121!) @ MM) (c. - in which all matrices are organized in 2 x 2 blocks of equal entries. This immediately implies that Új ー for all j. So in particular the detection threshold (ma, + m22) of the averaged-mean
and per class, i.c., A11
test (equation 2 is zero, as conventionally assumed. In all other settings for the nza 's, it is very unlikely that Vii - and the optimal decision threshold must also be estimated.
These various conclusions give rise to an improved MTL LS-SVM algorithm. A pseudo-code (Algo- rithm [ along with discussions on (i) the estimation of the statistics met in Theorem [] (Remark and on (ii) its multi-class extension (Remark 2) are covered next. Matlab and Julia implementations of Algorithm I and its extensions are proposed in the supplementary material.
5 EXPERIMENTS
Our theoretical results (the data-driven optimal tuning of MTL LS-SVM, as well as the anticipation of classification performance) find various practical applications and consequences. We exploit them here in the context of transfer learning, first on a binary decision on synthetic data, and then on a multiclass classification on real data.
To this end, and before proceeding to our experimental setup, a few key remarks to practically exploit Theorem are in order.
Remark (On the estimation of maj and o,). All quantities defined in Theorem ! are a priori known, apart from the k2 inner products Auy Au, for S i,j S k. For these, define Sn C {1, (1,.... na} (l 1,2) and the corresponding indicator vector ja E R": with lissla = dues.g. For i = j. further let S C {l...., naJ with S/ n S. = @ and the corresponding indicator vector Ka E R"i Then, the following estimates hold:
De1
Di2
111
= -0 -0(10 min 18;11) (E(1.)
AUTAR,
x,x,
[Sai]
S112
[Sya|
APTAN Ap=
ja
x,x,
M1
M2
0
(p
min (ISal. (al)) (E(1.2)
[Sal
[S,z]
[8]]]
[
Observe in particular that a single sample (two when i = 1) per task and per class (Sytl = 1) is sufficient to obtain a consistent estimate for all quantities, long that p is large.
Remark (From binary to multiclass MTL). Accessing the vector m in Theorem D allows for the extension of the MTL framework to a multicluss-per-tusk MTL by discarding the well known inherent biases of multiclass SVM. In the context of L,; classes for Task i, using a one-versus- all approach (for each E e (l....,,iy Li}. one MTL LS-SVM algorithmss with Class "I" being the target class E and Class "2" all other classes at once), one needs to access Li pairs of values (f), and, for new x, decide on the genuine class of based on the largest value among gx(x; 1)-
L,) - ma1 (L)) with gi(x; E) the output score for "Class E versus all".
For simplicity, from Remark I in the supplementary material, one may choose smart shift vectors (()) E R² for the scores ū()) E R2h (i.e. replace (({) by :({)= + g(E) @ 12) so that ma(() = 0 for each f. Under this shift, the selected class is the one for which gi (x E) is maximum.
7

---

Published as a conference paper at ICLR 2021
8
0.5
3 =1
92(x), y E [=1]a2
2
91.3%
1.5
34.4%
5.2%
1.5
0.3%
1.5
1
1
0.5
0.5
0.5
0.5
0
0
-
0
2
92 optimal y = i
0.6
0.4%
0.8
6.4%
1.5
3.2%
1.5
0.3%
0.6
0.4
1
0.4
0.2
0.5
0.5
0.2
0
0
2
0
2
4
2
2
Figure 1: Scores 92 (x() lempirical histogram vs. theory in solid lines] for x of Class C1 (red) or Class
C2 (blue) for Task 2 in 2-task (A: 2) setting of isotropic Gaussian mixtures for: (top) classical MTLLL-SSVM with y E {+1) and threshold (= 0; (bottom) proposed optimized MTL--LSSVM with ÿ* and estimated threshold Ç: decision thresholds Ç represented in dashed vertical lines; red numbers are misclassification rates; task relatedness with / = 0 for orthogonal tasks, 3 > 0 for positively correlated tasks. 3 for negatively correlated tasks; p 100, [c11, C12, C21, Cral [0.3, 0.4, 0.2, 12, À = 10. Histograms drawn from 1 000 test samples of each class.
5.1 EFFECT OF INPUT SCORE (LABEL) AND THRESHOLD DECISION CHOICES
In order to support the theoretical insights drawn in the article, our first experiment illustrates the effects of the bias in the decision threshold for (x) (in general not centered on zero) and of the input score (label) optimization 3² synthetic data.
Specifically, MTL-LSSVM first applied to the following two-task (k 2) setting: for Task 1, (() .N((-1) p1 Ip) and for Task 2, Tzy
[,5 ((((1))p,, Ip), where fl2 Bp1 + 1 gr
and jr| is any vector orthogonal to μl and [ E [0, 1]. This setting allows us to tune, through 3, the similarity between tasks. For four different values of 3, Figure depiccss the distribution of the binary output scores (x) both for the classical MTLLL-SVM (top displays) and for our proposed random matrix improved scheme, with optimized input labels (bottom displays).
As first remark, note that both theoretical prediction and empirical outputs closely fit for all values of B, thereby corroborating our theoretical findings. In practical terms, the figure supports (i) the importance to estimate the threshold decision which is non-trivial (not always close to zero) and (ii) the relevance of an appropriate choice of the input labels to improve the discrimination performance between both classes, especially when the two tasks not quite related as shown by the classification error presented in red in the figure.
5.2 MULTICLASS TRANSFER LEARNING
We next turn to the classical Office+Caltec2256 (Saenko et al. 2010 Griffin et al. 2007) real data (images) benchmark for transfer learning, consisting of the 10 categories shared by both datasets. For fair comparison with previous works, we compare images using p = 4096 VGG features. Half of the samples of the target is randomly selected for the test data and the accuracy is evaluated over 20 trials. We use here Algorithm|] [ the results of which (Proposed) are reported in Table [ against the non-optimized LS-SVM (Xu al. 2013) and alternative state-of-the-art algorithms: MMDT, CDL.S and IIS
"MDDT: Max Margin Domain Transform, proposed in Hoffiman et al. 2013). applies a weighted SVM on a learnt transformation of the source and target. CDLS: Poos-DDoaiin Landmark Selection, proposed in (Hubert T Tsai et al. (2166), derives domain invariant feature space. IIS: Invariant Latent Space, proposed in Herath et al. 2017) learns invariant latent space reduce the discrepancy between source and target.
8

---

Published as a conference paper at ICLR 2021
Algorithm Proposed Multi Task Learning algorithm.
Input: Training samples = [X1,.... Xx) with x, = (x ,...,, x! X E Rexai and test
data x.
Output: Estimated class i E {L...., ,,..,,,,)) Le} of x for target Task for j = 1 to L; do
Center and normalize data per task: for all (1.....kk]
X₂. t- Xy [In, n In T RV
N,+t t Xv/ Dop
p xTx
Estimate: Matrix M from Remark and A. using x()) ...., x data of class and
X X (x(x) ..... x as data of class 2.
Create scores
--)= - " O MDD (el 12
(2k)
Estimate and center m(j) from Theorem 1 as per Remark [ (Optional) Estimate the theoretical classification error q (A, 7) minimize over (A, 7 Compute classification scores go j) according equation end for Output: i = arg ).) (x(x
Table 1: Classification accuracy over Office+Caltech256 database. c(Caltech), w(Webcam), a( u(Amazon), d(dslr), for different "Source target" task pairs T) based on VGG features. Best score in boldface, second-to to-bett in italic.
S/T
d
d
Mean
w
c
a
a
d
a
d
c
w
w
score
LSSVM
96.69
89.90
92.90
90,00
93.80
78.70
93.50
95.00
85.00
90.20
94.70
100
91.70
MMDT
93.90
87.05
90.83
84.40
94.17
86.25
94.58
97.50
86.25
87.23
92.05
97.35
90.96
ILS
77.89
73.55
86.85
76.22
86.22
71.34
74.53
82.80
68.15
63.49
78.98
92.88
77.74
CDLS
97.60
88.30
93.54
88.30
93.54
92.50
93.54
93.75
93.75
88.30
97.35
96.70
93. 10
Ours
98.68
89.90
94.40
90.60
94.40
93.80
94.20
100
92.50
89.90
98.70
99.30
94.70
Table I
demonstrates that proposed improved MTL LS-SVM, despite its simplicity and unlike the competing methods used for comparison, has stable performances and is quite competitive. We further recall that, in additions these high levels of performance, the method comes along with theoretical guarantees, which none of the competing works are able to provide.
CONCLUSION: BEYOND MTL
Through the example of transfer learning (and more generally multitask learning), we have demon- strated the capability of random matrix theory to (i) predict and improve the performance of machine learning algorithms and, most importantly, to (ii) turn simplistic (and in theory largely suboptimal) methods, such as here LS-SVM, into competitive state-of-the-ar algorithms. As Gaussian mixtures quite "universal" and thus already appropriate to handle real data (as shown in supplementary material), one may surmise the optimality of the least square approach, thereby opening the possibility prove that MTL LS-SVM is likely close-to-optimal even real data settings.
This is yet merely a first step into a generalized use of random matrix theory and large dimensional statisties to devise much-needed low computational cost and explainable, yet highly competitive, machine learning methods from elementary optimization schemes.
ACKNOWLEDGMENT
Couillet's 's work is partially supported by MIAI at University Grenoble-Alpes (ANR- LANR-19--311 ---P3A--000) and the HUAWEI LarDist project.

---

Published as a conference paper at ICLR 2021
REFERENCES
Arvind Agarwal, Samuel Gerber, and Hal Daume. Learning multiple tasks using manifold regulariza- tion. In Advances neural information processing systems, pp. 46 46-54, 2010.
Murray Aitkin and Nicholas Longford. Statistical modelling issues in school effectiveness studies.
Journal of the Royal Statistical Society: Series (General), (4911):1-266 1986.
Greg M Allenby and Peter E Rossi. Marketing models of consumer heterogeneity. Journal of econometrics, 89(1-)):57-78, 1998.
Andreas Argyriou, Theodoros Evgeniou, and Massimiliano Pontil. Multi-task feature learning. In Advances in neural information processing systems, pp. 41-48, 2007.
Jonathan Baxter. A hayesian/inforrmtionn theoretic model of learning to learn via multiple task sampling. Machine learning, 28(1):7-39, 1997.
Jonathan Baxter. A model of inductive bias learning. Journal of artificial intelligence research, 12: 149-198, 2000.
Shai Ben- Den-Davvi and Reba Schuller. Exploiting task relatedness for multiple task learning. In Learning Theory and Kernel Machines, pp. 567-580. Springer, 2003.
Hal Daumé III. Bayesian multitask learning with latent hierarchies. arXiv preprint arXiv:0907.0788, 2009.
Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high- dimensional binary linear classification. arXiv preprint
2019.
Noureddine Karoui al. On information plus noise kernel random matrices. The Annals of Statistics, 38(5):3191 (155):319-3333 -2266,, 2010.
Theodoros Evgeniou and Massimiliano Pontil. Regularized multi-task learning. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 109-117. ACM, 2004.
Pinghua Gong, Jieping Ye, and Chang-shui Zhang, Multi-stage multi-task feature learning. In Advances neural information processing systems, pp. 1988-1996, 2012.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural informa- tion processing systems, pp. 2672-2680, 2014.
Gregory Griffin, Alex Holub, and Pietro Perona. Caltech-256 object category dataset. technical report, 2007.
Samitha Herath, Mehrtash Harandi, and Fatih Porikli. Learning invariant hilbert space for domain adaptation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3845-3854, 2017.
Judy Hoffman, Erik Rodner, Jeff Donahue, Trevor Darrell, and Kate Saenko. Efficient learning of domain-invariant image representations. arXiv preprint 1301vv1301.3222 2013.
Hoog Hubert Tsai, Yi-Ren Yeh, and Yu- Yu-Chiang Frank Wang. Learning cross- cross-domain landmarks for heterogeneous domain adaptation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5081- 2016.
Zhenyu Liao and Romain Couillet. A large dimensional analysis of least squares support vector machines. IEEE Transactions on Signal Processing,
2019.
Xiaoyi Mai and Romain Couillet. A random matrix analysis and improvement of semi-supervised learning for large dimensional data. The Journal of Machine Learning Research, 19(1):30743110) 2018.
10

---

Published as a conference paper at ICLR 2021
Xiaoyi Mai, Zhenyu Liao, and Romain Couillet. A large scale analysis of logistic regression: Asymptotic performance and new insights. In ICASSP 2019-2019 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 3357-3361. IEEE, 2019.
Andreas Maurer, Massi Pontil, and Bernardino Romera-Paredes. Sparse coding for multitask and transfer learning. In International conference on machine learning, pp. 343-351, 2013.
Guillaume Obozinski, Ben Taskar, and Michael Jordan. Multi-task feature selection. Statistics Department, UC Berkeley, Tech. Rep. 2(2.2):2, 2006.
Sinno Jialin Pan, Ivor W Tsang, James T Kwok, and Qiang Yang. Domain adaptation via transfer component analysis. IEEE Transactions Neural Networks, 22(2):199-216 2010.
Shibin Parameswaran and Kilian Q Weinberger. Large margin multi-task metric learning. In Advances in neural information processing systems, pp. 1867-1875, 2010.
Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell. Adapting visual category models to new domains. In European conference on computer vision, pp. 213-226. Springer, 2010.
Jie Wang and Jieping Ye. Safe screening for multi-task feature learning with multiple data matrices. arXiv preprint arXiv: 1Xix:1555.00073 2015.
Shuo Xu, Xin An, Xiaodong Qiao, Lijun Zhu, and Lin Li. Multi-output least-squares support vector regression machines. Pattern Recognition Letters, 14:1078-1084, 07 2013. doi: 10.1016/j. 2013.01.015.
Wenlu Zhang, Rongjian Li, Tao Zeng. Qian Sun, Sudhir Kumar, Jieping Ye, and Shuiwang Ji. Deep model based transfer and multi-task learning for biological image analysis. IEEE transactions on Big Data, 2016.


Reviews:
[{"review_id": "o0lVA93DxoS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides a theoretical analysis of the inner workings of multi-task learning methods, based on a random matrix analysis applied to Gaussian mixture data model. The analysis is based on MTL LS-SVM with data from a Gaussian mixture model, where the bias of MTL LS-SVM is shown and a simple method is proposed to correct it. Experiments are conducted on a synthetic dataset and image classification task, where superior performance is shown in addition to the theoretical guarantees.\n\nThe main contribution of the paper is to introduce the random matrix theory to study the performance of MTL LS-SVM theoretically, which is novel and facilitates the understanding of MTL. The theoretical work seems valid. \n\nConcerns:\n1)\tThe theoretical analysis is based on MTL LS-SVM with data from a Gaussian mixture model, which limits the generality of the work. Specifically, as the authors state in the paper, the quadratic optimization problem with linear constraints produces explicit solutions, which makes the analysis easier. It would be helpful if the authors provide some insights of generalizing the analysis to other settings. \n\n2)\tIn the experiments, it would be necessary to explain the choice of the baselines to justify the results of the comparison. Specifically, why didn’t the authors compare to some multi-task learning representatives? Also, only one dataset is employed for multi-class experiments, which is less than sufficient. \n\n3)\tIs the “low computational cost” claimed in the conclusion more due to the quadratic optimization problem itself?\n\nMinor comments:\nAlgorithm 1 is suggested to be included in the main content of the paper. \n\nAfter rebuttal:\nThe authors' response addressed some of my concerns and I'd like to adjust my rating to marginally above.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "djwlPbXQcEQ", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe paper provides interesting theoretical insights in multi-task learning using common and specific parameters modeling framework and based on least-squares SVM. Especially, it is theoretically established that the standard MTL LS-SVM is biased. Thereon a method derived from the analysis is proposed to correct the bias and allows to achieve enhanced performances. Empirical evaluations highlight the effectiveness of the method.\n\nReasons for score: \nOverall, I vote for accepting. The theoretical analysis highlight the intrinsic  relation between task statistics/relatedness and the classification performances. The analysis helps to design an adequate MT models with improved performances. My major concern is about the clarity of the paper notations. Hopefully the authors can address my concern in the rebuttal period. \n \nPros:\n- The paper provides a asymptotical analysis of the decision function $g_i$ related to each task $i$ (learned using a linear MTL LS-SVM) by leveraging on random matrix theory and by assuming large scale $n$ and high dimension $p$ with limiting growth rate. The main result highlights the influence of the task data statistics and the MTL hyper-parameters on the decision function. Essentially the paper shows that the score provided by a task decision function $g_i(\\mathbf{x})$ has a Gaussian distribution in the limit case, hence one can estimate its classification error. For me, the proposed derivation is of great interest in real applications. \n-  The derived statistical modeling of $g_i(\\mathbf{x})$ allows to control the intercept of $g_i$ in order to minimize the classification error. The key to this error control is to appropriately assign the labels of each task samples according to the tasks relatedness and their data statistics which can be easily computed based on available training data. This leads to a practical and comprehensive MTL algorithm (that should be moved in the main paper). \n- Experimental evaluations on synthetic and classical MTL datasets illustrate that the proposed method systematically ranks in the top two methods out of 5 compared algorithms. This makes the provided analysis convincing.  \n\nCons: \n- The mathematical notations are dense and render the overall mathematical derivation hard to read.  It might be valuable to expose the main concepts of the paper starting from a two-tasks MTL problem and then generalize to an arbitrary number of tasks. \n-  It might be useful to report the standard deviation along with the average empirical accuracies (Table 1 for instance)\n- The analyzed framework relies on a binary MT classification problems. How the presented results transfer to the multi-class classification setting?\n- Does the analysis change if instead of the LS-SVM one uses a logistic regression as a model? Also how the proposed approach lifts to non-linear models? \n \n\nOther comments:\n- Table 1 overpasses the page format. \n\nAfter rebuttal\n- I read the response of the authors. The response addresses most of the concerns raised in the reviews.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Rfy-fDHZwEj", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overall, I vote for accepting this paper. I list the strong and weak points in the following.\n### Strong points\n- The theoretical result is sound and significant. It not only matches the simulation well, but also provides a way to optimally choose the decision threshold and training labels. The proposed method is simple but beats some of the more complicated algorithms as demonstrated in the experiments. This is quite a success of applying random matrix theory to study machine learning. It is a stepping stone to utilizing random matrix theory to study more sophisticated problems and design more efficient algorithms.\n- The paper is well written and organized. It clearly states the contributions and limitations and put itself in the literature appropriately.\n\n### Weak points\n- The studied problem is restricted. It is a binary classification problem under a Gaussian mixture model. The LS-SVM algorithm is also not as common as margin-based SVM. I would like at least some discussions on how to generalize the framework and techniques in this paper to other problems. \n- The asymptotic regime also require the number of samples in each task and in each class to be proportional to each other. What can be said about the unbalanced case?\n- The paper does not talk about how to choose the hyperparameters $\\lambda$ and $\\gamma$. Can the theory provide a way of choosing the hyperparameters optimally?\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NelfGYSuQ01", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the multitask least-square SVM problem. Such a problem consists of k SVM tasks, each being a binary classification problem. The normal vector of the separating hyperplane in each task is “close” to each other, reflecting the commonality of the tasks. For an input data point, the problem asks to predict the classification of the input data point for a given task. This problem has a standard optimization formulation.\n\nThe main contribution of the paper is a theoretical analysis for the setting where the training data and the test data are all Gaussian random vectors. It shows that under such setting, the classification score in each task converges, when the number of training data goes to infinity, in distribution to Gaussian variables whose mean and variance can be computed from some statistics of the data and the parameters of the optimization formulation. Therefore, one can use this limiting distribution to set the threshold for assigning the class, given the classification score, by minimizing the misclassification probability.\n\nStrengths:\n- Sophistical analysis, very theoretical\n- Good experiment result\n\nWeaknesses:\n- Analysis may only be possible for special distributions (perhaps Gaussians is a relatively easy case) and it is not fully convincing that it can be widely used. SVM itself is a relatively simple problem, too.\n- Experiment does not completely beat the best existing method. Is there an advantage in some other aspect, such as runtime?\n- ICLR seems to mainly about representation learning while the problem this paper does not rightly concern processing the input data.\n\nThe main body of the paper is very well-written, although I think Algorithm 1 should be presented in the main body instead of being left in the supplementary material. \n\nMinor comment:\n- Second paragraph of Section 1, add “is” to the end of the first line\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers and I all agree that this analysis of multi-task and transfer learning from the random matrix perspective is novel and theoretically sound. While some reviewers expressed concern about the restriction to Gaussian mixtures, the strength of the explicit results undoubtedly justifies this assumption, and the generalization to concentrated random vectors significantly mitigates any concerns. I recommend acceptance.
Decision: Accept (Spotlight)