summaries: 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. The 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. 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.
abstractText: 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 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.
references.authors: Arvind Agarwal Samuel Gerber Hal Daume
references.title: Learning multiple tasks using manifold regularization
references.venue: In Advances in neural information processing systems,
references.authors: Murray Aitkin Nicholas Longford
references.title: Statistical modelling issues in school effectiveness studies
references.venue: Journal of the Royal Statistical Society: Series A (General),
references.authors: Greg M Allenby Peter E Rossi
references.title: Marketing models of consumer heterogeneity
references.venue: Journal of econometrics,
references.authors: Andreas Argyriou Theodoros Evgeniou Massimiliano Pontil
references.title: Multi-task feature learning
references.venue: In Advances in neural information processing systems,
references.authors: Jonathan Baxter
references.title: A bayesian/information theoretic model of learning to learn via multiple task sampling
references.venue: Machine learning,
references.authors: Jonathan Baxter
references.title: A model of inductive bias learning
references.venue: Journal of artificial intelligence research,
references.authors: Shai Ben-David Reba Schuller
references.title: Exploiting task relatedness for multiple task learning
references.venue: In Learning Theory and Kernel Machines,
references.authors: Hal Daumé III
references.title: Bayesian multitask learning with latent hierarchies
references.venue: arXiv preprint arXiv:0907.0783,
references.authors: Zeyu Deng Abla Kammoun Christos Thrampoulidis
references.title: A model of double descent for highdimensional binary linear classification
references.venue: arXiv preprint arXiv:1911.05822,
references.authors: Noureddine El Karoui
references.title: On information plus noise kernel random matrices
references.venue: The Annals of Statistics,
references.authors: Theodoros Evgeniou Massimiliano Pontil
references.title: Regularized multi–task learning
references.venue: In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining,
references.authors: Pinghua Gong Jieping Ye Chang-shui Zhang
references.title: Multi-stage multi-task feature learning. In Advances in neural information processing
references.authors: Ian Goodfellow Jean Pouget-Abadie Mehdi Mirza Bing Xu David Warde-Farley Sherjil Ozair Aaron Courville Yoshua Bengio
references.title: Generative adversarial nets
references.venue: In Advances in neural information processing systems,
references.authors: Gregory Griffin Alex Holub Pietro Perona
references.title: Caltech-256 object category
references.venue: dataset. technical report,
references.authors: Samitha Herath Mehrtash Harandi Fatih Porikli
references.title: Learning an invariant hilbert space for domain adaptation
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Judy Hoffman Erik Rodner Jeff Donahue Trevor Darrell Kate Saenko
references.title: Efficient learning of domain-invariant image representations
references.venue: arXiv preprint arXiv:1301.3224,
references.authors: Yao-Hung Hubert Tsai Yi-Ren Yeh Yu-Chiang Frank Wang
references.title: Learning cross-domain landmarks for heterogeneous domain adaptation
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Zhenyu Liao Romain Couillet
references.title: A large dimensional analysis of least squares support vector machines
references.venue: IEEE Transactions on Signal Processing,
references.authors: Xiaoyi Mai Romain Couillet
references.title: A random matrix analysis and improvement of semi-supervised learning for large dimensional data
references.venue: The Journal of Machine Learning Research,
references.authors: Xiaoyi Mai Zhenyu Liao Romain Couillet
references.title: A large scale analysis of logistic regression: Asymptotic performance and new insights
references.venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),
references.authors: Andreas Maurer Massi Pontil Bernardino Romera-Paredes
references.title: Sparse coding for multitask and transfer learning
references.venue: In International conference on machine learning,
references.authors: Guillaume Obozinski Ben Taskar Michael Jordan
references.title: Multi-task feature selection
references.venue: Statistics Department, UC Berkeley, Tech. Rep,
references.authors: Sinno Jialin Pan Ivor W Tsang James T Kwok Qiang Yang
references.title: Domain adaptation via transfer component analysis
references.venue: IEEE Transactions on Neural Networks,
references.authors: Shibin Parameswaran Kilian Q Weinberger
references.title: Large margin multi-task metric learning
references.venue: In Advances in neural information processing systems,
references.authors: Kate Saenko Brian Kulis Mario Fritz Trevor Darrell
references.title: Adapting visual category models to new domains
references.venue: In European conference on computer vision,
references.authors: Jie Wang Jieping Ye
references.title: Safe screening for multi-task feature learning with multiple data matrices
references.venue: arXiv preprint arXiv:1505.04073,
references.authors: Shuo Xu Xin An Xiaodong Qiao Lijun Zhu Lin Li
references.title: Multi-output least-squares support vector regression machines
references.venue: Pattern Recognition Letters, 34:1078–1084,
references.authors: Wenlu Zhang Rongjian Li Tao Zeng Qian Sun Sudhir Kumar Jieping Ye Shuiwang Ji
references.title: Deep model based transfer and multi-task learning for biological image analysis
references.venue: IEEE transactions on Big Data,
sections.text: 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 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.
sections.heading: 1 INTRODUCTION
sections.text: 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 a machine learn other related tasks, is one of them. The particularly interesting aspects of multi-task learning lie in the possibility (i) to exploit the resemblance between the datasets associated to each task so the tasks “help each other” and (ii) to train a machine on a 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, 1986), 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 a 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 one another and in identifying which features are “transferred”. The article aims to decipher these fundamental aspects for sufficiently general data models.
  Several data models may be accounted for to enforce relatedness between tasks. A common assumption is that the data lie close to each other in a geometrical sense (Evgeniou & Pontil, 2004), live in a low dimensional manifold (Agarwal et al., 2010), or share a common prior (Daumé III, 2009). We follow here the latter assumption in assuming that, for each task, the data arise from a 2-class Gaussian mixture.1
  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 ω) best separating the two classes of a unique dataset, (Evgeniou & Pontil, 2004) proposes to produce best separating hyperplanes (or normal vectors) ω1, . . . , ωk for each pair of data classes of k tasks, with the additional constraint that the normal vectors take the form ωi = ω0 + vi for some common vector w0 and dedicated vectors vi. The amplitude of the vectors vi 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 a 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 (leastsquare) 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 a Gaussian mixture model, assuming the total number n and dimension p of the data are both large, i.e., as n, p → ∞ with p/n→ c ∈ (0,∞). As such, our work follows after the recent wave of interest into the asymptotics of machine learning algorithms, such as studied lately in e.g., (Liao & Couillet, 2019; Deng et al., 2019; Mai & Couillet, 2018; El Karoui et al., 2010). Our analysis reveals the following major conclusions:
  • we exhibit the sufficient statistics, 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 {−1, 1},
  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 cross-validation 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, a bias is naturally induced that makes ζ = 0 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 performance-maximizing 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 are available in the supplementary materials.
  Notation. e[n]m ∈ Rn is the canonical vector of Rn with [e[n]m ]i = δmi. Moreover, e[2k]ij = e [2k] 2(i−1)+j . Similarly, E[n]ij ∈ Rn×n is the matrix with [E [n] ij ]ab = δiaδjb. The notations A ⊗ B and A B
  1In the supplementary material, we extend this setting to a much broader and more realistic scope, and justify in passing the relevance of a Gaussian mixture modelling to address multi-task learning with real data.
  for matrices or vectors A,B are respectively the Kronecker and Hadamard products. Dx is the diagonal matrix containing on its diagonal the elements of the vector x and Ai· is the i-th row of A. The notation Å is used when a centering operation is performed on the matrix or vector A. Uppercase calligraphic letters (A,K,Γ,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 to Class j in Task i.
sections.heading: 2 RELATED WORKS
sections.text: 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, we mainly focus on the MTL literature, which is divided into parameter-based versus feature-based MTL.
  In the parameter-based MTL approach, the tasks are 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 et 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 of 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; Zhang et al., 2016; Pan et al., 2010); other works simply use a 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 to study and improve “data-generic” MTL mechanisms under no structural assumption on the data; this approach is quite unlike recent works exploiting convolutive techniques in deep neural nets or low dimensional feature-based methods to perform transfer or multi-task learning mostly for computer vision.
  From a 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 in the MTL research.
sections.heading: 3 THE MULTI-TASK LEARNING SETTING
sections.text: Let X ∈ Rp×n be a collection of n independent data vectors of dimension p. The data are divided into k subsets attached to individual “tasks”. Specifically, letting X = [X1, . . . , Xk], Task i is a binary classification problem from the training samples Xi = [X (1) i , X (2) i ] ∈ Rp×ni with X (j) i = [x (j) i1 , . . . , x (j) inij ] ∈ Rp×nij the nij vectors of class j ∈ {1, 2} for Task i. In particular, n = ∑k i=1 ni and ni = ni1 + ni2 for each i ∈ {1, . . . , k}. To each xil ∈ Rp of the training set is attached a corresponding “label” (or score) yil ∈ R. We denote yi = [yi1, . . . , yini ]
  T ∈ Rni the vector of all labels for Task i, and y = [yT1 , . . . , yTk ]T ∈ Rn 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, a preliminary task-wise centering operation is performed on the data, i.e., we consider in the following the datasets
  X̊i = Xi ( Ini − 1
  ni 1ni1 T ni
  ) , ∀i ∈ {1, . . . , k}.
  As such, we systematically work on the labeled datasets (X̊1, y1), . . . , (X̊k, yk). Remark 1 in the supplementary material motivates this choice, which avoids extra biases produced by the algorithm.
sections.heading: 3.1 THE OPTIMIZATION FRAMEWORK
sections.text: The multitask learning least square support vector machine (MTL LS-SVM) aims to predict, for input vectors x ∈ Rp not belonging to the training set, their associated score y upon which a decision on the class allocation of x is taken, for a given target task. To this end, based on the labeled sets (X̊1, y1), . . . , (X̊k, yk), MTL LS-SVM determines the normal vectorsW = [ω1, ω2, . . . , ωk] ∈ Rp×k and intercepts b = [b1, b2, . . . , bk]T ∈ Rk defining k separating hyperplanes for the corresponding k binary classification tasks. In order to account for task relatedness, each ωi assumes the form ωi = ω0 + vi for some common ω0 ∈ Rp and task-dedicated vi ∈ Rp. Formally, writing V = [v1, . . . , vk] ∈ Rp×k (so that W = ω01>k + V ) and following the work of (Evgeniou & Pontil, 2004; Xu et al., 2013), the optimization function is given by
  min (ω0,V,b)∈
  Rp×Rp×k×Rk
  1
  2λ ‖ω0‖2 +
  1
  2 k∑ i=1 ‖vi‖2 γi + 1 2 k∑ i=1 ‖ξi‖2, ξi = yi − (X̊Ti ωi + bi1ni), 1 ≤ i ≤ k.
  In this expression, the parameter λ enforces more task relatedness while the parameters γ1, . . . , γk enforce better classification of the data in their respective classes.
  Being a quadratic optimization problem under linear equality constraints, ω0, V, b are obtained explicitly (see details in Section 1 of the supplementary material). The solution is best described through the expression of the hyperplanes ω1, . . . , ωk ∈ Rp which take the form:
  ωi = ( e [k]T i ⊗ Ip ) AZα,
  and b = (PTQP )−1PTQy, where α = Q(y−Pb) = Q 12 (In−Q 1 2P (PTQP )−1PTQ 1 2 )Q 1 2 y ∈ Rn is the Lagrangian dual and
  Q =
  ( 1
  kp ZTAZ + In
  )−1 ∈ Rn×n, Z = k∑ i=1 E [k] ii ⊗ X̊i ∈ R pk×n
  A = ( Dγ + λ11T ) ⊗ Ip ∈ Rkp×kp, P = k∑ i=1 E [k] ii ⊗ 1ni ∈ R n×k
  with γ = [γ1, . . . , γk]T and Dγ = diag(γ).
  MTL LS-SVM differs from a single-task joint LS-SVM for all data in that the data X̊1, . . . , X̊k are not treated simultaneously but through k distinct filters: this explains why Z ∈ Rkp×n is not the mere concatenation [X̊1, . . . , X̊k] but a block-diagonal structure isolating each X̊i. As such, the X̊i’s-relating matrix A plays an important role in the MTL learning process.
  With this formulation for the solution (W, b), the prediction of the class of any new data point x ∈ Rp for the target Task i is then obtained from the classification score
  gi(x) = 1
  kp
  ( e
  [k] i ⊗ x̊ )T AZα+ bi (1)
  where x̊ = x− 1niXi1ni is a centered version of x with respect to the training dataset for Task i.
sections.heading: 3.2 LARGE DIMENSIONAL STATISTICAL MODELLING
sections.text: The first objective of the article is to quantify the MTL performance, and thus of the (a priori intricate) statistics of gi(x), under a sufficiently simple but telling Gaussian mixture model for training and test data. Assumption 1 (Distribution of X and x). The columns of [X,x] are independent Gaussian random variables. Specifically, the nij samples x (j) i1 , . . . , x (j) inij
  of class j for Task i are independentN (µij , Ip) vectors, and we let ∆µi ≡ µi1 − µi2. As for x, it follows an independent N (µx, Ip) vector.
  In the supplementary material, Assumption 1 is relaxed to [X,x] arising from a generative model of the type x(j)il = hij(z (j) il ) for z (j) il ∼ N (0, Ip) and hij : Rp → Rp 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 is shown in the supplementary material to be universal in the sense that, as n, p→∞, the asymptotic performances of MTL LS-SVM only depend on the statistical means and covariances of the x(j)il : the performances under complex mixtures are thus proved to coincide with those under an 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 n → ∞, n/p → c0 > 0 and, for 1 ≤ i ≤ k, 1 ≤ j ≤ 2, nij n → cij > 0. We let ci = ci1 + ci2, c = [c1, . . . , ck] T ∈ Rk.
  With these notations and assumptions, we are in position to present our main theoretical results.
sections.heading: 4 THE MULTI-TASK LEARNING ANALYSIS
sections.heading: 4.1 TECHNICAL STRATEGY AND NOTATIONS
sections.text: To evaluate the statistics of gi(x) (equation 1), we resort to finding so-called deterministic equivalents for the matrices Q, AZQ, etc., which appear at the core of the formulation of gi(x). Those are provided in Lemma 1 of the supplementary material. Our strategy then consists in “decoupling” the effect of the data statistics from those of the MTL hyperparameters λ, γ1, . . . , γk. Specifically, we extract two fundamental quantities for our analysis: a data-related matrixM ∈ R2k×2k and a hyperparameter matrix A ∈ Rk×k: M = k∑
  i,j=1
  ∆µTi ∆µj
  ( E
  [k] ij ⊗ cic T j ) , ci =  ci2ci √ ci1ci − ci1ci √ ci2 ci  , A = (Ik +D− 12∆̃ (Dγ + λ1k1Tk)−1D− 12∆̃ )−1 where ∆̃ = [∆̃1, . . . , ∆̃k]T are the unique positive solutions to the implicit system ∆̃i = cic0 −Aii (this is implicit because A is a function of the ∆̃j’s). In passing, it will appear convenient to use the shortcut notation ∆̄ = [∆̄11, . . . , ∆̄k2]T ∈ R2k where ∆̄ij = cijci c0∆̃i.
  We will see thatM plays the role, in the limit of large p, n, of a sufficient statistic for the performance of the MTL LS-SVM algorithm only involving (i) the data statistics µ11, . . . , µk2 and (ii) the (limiting) relative number c11/c1, . . . , ck2/ck of elements per class in each task. As for A, it captures the information about the impact of the hyperparameters λ, γ1, . . . , γk and of the dimension ratios c1, . . . , ck and c0. These two matrices will be combined in the core matrix Γ ∈ R2k×2k of the upcoming MTL LS-SVM performance analysis, defined as Γ = ( I2k + ( A⊗ 121T2 ) M
  )−1 where we recall that ‘ ’ is the Hadamard (element-wise) matrix product.
  We raised in the introduction of Section 3 that we purposely relax the binary “labels” yij associated to each datum xij in each task to become “scores” yij ∈ R. This will have fundamental consequences to the MTL performance. Yet, since xi1, . . . , xini are i.i.d. data vectors, we impose equal scores yi1 = . . . = yini within each class. As such, we may reduce the complete score vector y ∈ Rn
  under the form y = [ ỹ111Tn11 , . . . , ỹk21 T nk2 ]T for ỹ = [ỹ11, . . . , ỹk2]T ∈ R2k. From Remark 1 of the supplementary material, the performances of MTL are insensitive to a constant shift in the scores yi1 and yi2 of every given Task i: as such, the recentered version ˚̃y = [̊ỹ11, . . . ,˚̃yk2]T of ỹ, where ˚̃yij = ỹij − (ni1ni ỹi1 + ni2 ni ỹi2) will be central in the upcoming results.
sections.heading: 4.2 MAIN RESULTS
sections.text: Theorem 1 (Asymptotics of gi(x)). Under Assumptions 1–2, for x ∼ N (µx, Ip) with µx = µij , gi(x)−Gij → 0, Gij ∼ N (mij , σ2i )
  in distribution where, letting m = [m11, . . . ,mk2]T,
  m = ỹ −D− 1 2
  ∆̄ ΓD
  1 2
  ∆̄ ˚̃y, σ2i =
  1
  ∆̃i ˚̃yTD
  1 2 ∆̄ Γ ( DKi. c ⊗12 + Vi ) ΓD 1 2 ∆̄ ˚̃y
  with Vi = 1c0 (AD c0Ki·c +e[k]i A⊗ 121 T 2 ) M and K = [A A](Ik −D c0kc [A A]) −1.
  As anticipated, the statistics of the classification scores gi(x) mainly depend on the data statistics µi′j′ and on the hyperparameters λ and γ1, . . . , γk through the matrix Γ (and more marginally through Vi and K for the variances). Since gi(x) has a Gaussian limit centered about mij , the (asymptotic) standard decision for x to be allocated to Class 1 (x→ C1) or Class 2 (x→ C2) for Task i is obtained by the “averaged-mean” test
  gi(x) C1 ≷ C2 1 2 (mi1 +mi2) (2)
  the classification error rate i1 ≡ P (x→ C2|x ∈ C1) of which is then i1 ≡ P ( gi(x) ≥
  mi1 +mi2 2 ∣∣∣x ∈ C1) = Q(mi1 −mi2 2σi ) + o(1) (3)
  with mij , σi as in Theorem 1 and Q(t) = ∫∞ t e− u2 2 du.
  Further comment on Γ is due before moving to practical consequences of Theorem 1. From the expression (A⊗ 121T2 )−1 M, we observe that: (i) if λ 1, then A is diagonal dominant and thus “filters out” in the Hadamard product all off-diagonal entries ofM, i.e., all cross-terms ∆µTi ∆µj for i 6= j, therefore refusing to exploit the correlation between tasks; (ii) if instead λ is not small, A may be developed (using the Sherman-Morrison matrix inverse formulas) as the sum of a diagonal matrix, which again filters out the ∆µTi ∆µj for i 6= j, and of a rank-one matrix which instead performs a weighted sum (through the γi’s and the ∆̃i’s) of the entries ofM. Specifically, letting γ−1 = (γ−11 , . . . , γ −1 k ) T in the expression of A, we have ( Dγ + λ1k1Tk )−1 = D−1γ − λγ−1γ−1T 1+λ 1k ∑k i=1 γ −1 i . As such, disregarding the regularization effect of the ∆̃i’s, the off-diagonal ∆µTi ∆µj entry ofM is weighted with coefficient (γiγj)−1: the impact of the γi’s is thus strongly associated to the relevance of the correlation between tasks.
  A fundamental aspect of Theorem 1 is that it concludes that the performances of the large dimensional (n, p 1) classification problem at hand merely boils down to 2k-dimensional 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 1.
  Estimating mij and σi not only allows one to anticipate theoretical performances but also enables the actual estimation of the decision threshold 12 (mi1 +mi2) in equation 2 and opens the possibility to largely optimize MTL LS-SVM through an (asymptotically) optimal choice of the training scores ỹ. Indeed, the asymptotics in Theorem 1 depend in an elegant manner on the training data labels (scores) ỹ. Since the variance σ2i is independent of the classes, we easily determine the vector ỹ = ỹ ? minimizing the misclassification probability for Task i as
  ỹ? = arg max ỹ∈R2k
  (mi1 −mi2)2
  σ2i = arg max ỹ∈R2k
  ‖ỹT(I2k −D 1 2 ∆̄ ΓD− 1 2 ∆̄ )(e [2k] i1 − e [2k] i2 )‖2
  ỹTD 1 2
  ∆̄ Γ(DKi. c ⊗12 + Vi)ΓD
  1 2 ∆̄ ỹ
  the solution of which is explicit
  ỹ? = D− 1 2 ∆̄ Γ−1H[(A⊗121T2 ) M]D − 12 ∆̄ (e [2k] i1 − e [2k] i2 ), H ≡ (DKi. c ⊗12 + Vi)−1 (4)
  with corresponding (asymptotically) optimal classification error i1 (equation 3) given by ?i1 = Q ( 1
  2
  √ (e
  [2k] i1 − e [2k] i2 ) TG(e[2k]i1 − e [2k] i2 )
  ) , G = D 1 2
  ∆̄ [(A⊗121T2 ) M ]V−1i [(A⊗121 T 2 ) M ]D
  1 2 ∆̄ .
  The only non-diagonal matrices in equation 4 are Γ and Vi in whichM plays the role of a “variance profile” matrix. In particular, assuming ∆µTi ∆µ` = 0 for all ` 6= i (i.e., the statistical means of all tasks are orthogonal to those of Task i), then the two rows and columns of M associated to Task i are all zero but on the 2 × 2 diagonal block. Therefore, ỹ? must be filled with zero entries but on its Task i two elements. All other values at the zero entry locations of ỹ? (such as the usual ỹ = [1,−1, . . . , 1,−1]T) would be suboptimal and possibly severely detrimental to the classification performance of Task i (not by altering the means mi1,mi2 but by increasing the variance σ2i ). This extreme example strongly suggests that, in order to maximize the MTL performance on Task i, one must impose low scores ỹjl to all Tasks j strongly different from Task i.
  The choice ỹ = [1,−1, . . . , 1,−1]T can also be very detrimental when ∆µTi ∆µj < 0 for some i, j: 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 2 than Class 1 in Task 2). In this setting, it is easily seen that ỹ = [1,−1, . . . , 1,−1]T works against the classification and performs much worse than a single-task LS-SVM.
  Another interesting conclusion arises from the simplified setting of equal number of samples per task and per class, i.e., n11 = . . . = nk2. In this case, ỹ? = Γ−1H ( (A⊗ 121T2 ) M ) (e [2k] i1 − e [2k] i2 ) in which all matrices are organized in 2× 2 blocks of equal entries. This immediately implies that ỹ?j1 = −ỹ?j2 for all j. So in particular the detection threshold 12 (mi1 +mi2) of the averaged-mean test (equation 2) is zero, as conventionally assumed. In all other settings for the njl’s, it is very unlikely that ỹ?i1 = −ỹ?i2 and the optimal decision threshold must also be estimated. These various conclusions give rise to an improved MTL LS-SVM algorithm. A pseudo-code (Algorithm 1) along with discussions on (i) the estimation of the statistics met in Theorem 1 (Remark 1) and on (ii) its multi-class extension (Remark 2) are covered next. Matlab and Julia implementations of Algorithm 1 and its extensions are proposed in the supplementary material.
sections.heading: 5 EXPERIMENTS
sections.text: 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 1 are in order. Remark 1 (On the estimation of mij and σi). All quantities defined in Theorem 1 are a priori known, apart from the k2 inner products ∆µTi ∆µj for 1 ≤ i, j ≤ k. For these, define Sil ⊂ {1, . . . , nil} (l = 1, 2) and the corresponding indicator vector jil ∈ Rni with [jij ]a = δa∈Sij . For i = j, further let S ′il ⊂ {1, . . . , nil} with S ′il ∩ Sil = ∅ and the corresponding indicator vector j′il ∈ Rni . Then, the following estimates hold:
  ∆µTi ∆µj − (
  ji1 |Si1| − ji2 |Si2|
  )T XTi Xj ( jj1 |Sj1| − jj2 |Sj2| ) = O ( (p min l∈{1,2} {|Sil|, |Sjl|})− 1 2 ) ∆µTi ∆µi − ( ji1 |Si1| − ji2 |Si2| )T XTi Xi ( j′i1 |S ′i1| − j ′ i2 |S ′i2| ) = O ( (p min l∈{1,2} {|Sil|, |S ′il|})− 1 2 ) .
  Observe in particular that a single sample (two when i = j) per task and per class (|Sil| = 1) is sufficient to obtain a consistent estimate for all quantities, so long that p is large. Remark 2 (From binary to multiclass MTL). Accessing the vector m in Theorem 1 allows for the extension of the MTL framework to a multiclass-per-task MTL by discarding the well known inherent biases of multiclass SVM. In the context of Li classes for Task i, using a one-versusall approach (for each ` ∈ {1, . . . , Li}, one MTL LS-SVM algorithms with Class “1” being the target class ` and Class “2” all other classes at once), one needs to access Li pairs of values (mi1(`),mi2(`)) and, for a new x, decide on the genuine class of x based on the largest value among gi(x; 1)−mi1(1), . . . , gi(x;Li)−mi1(Li) with gi(x; `) the output score for “Class ` versus all”. For simplicity, from Remark 1 in the supplementary material, one may choose smart shift vectors ȳ(`) ∈ Rk for the scores ỹ(`) ∈ R2k (i.e., replace ỹ(`) by ỹ(`) + ȳ(`)⊗ 12) so that mi1(`) = 0 for each `. Under this shift, the selected class is the one for which gi(x; `) is maximum.
  β = −1
  β = 0
  β = 0.5
  β = 1
sections.heading: 5.1 EFFECT OF INPUT SCORE (LABEL) AND THRESHOLD DECISION CHOICES
sections.text: 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 gi(x) (in general not centered on zero) and of the input score (label) optimization ỹ? on synthetic data.
  Specifically, MTL-LSSVM is first applied to the following two-task (k = 2) setting: for Task 1, x
  (j) 1l ∼ N ((−1)jµ1, Ip) and for Task 2, x (j) 2l ∼ N ((−1)jµ2, Ip), where µ2 = βµ1 + √ 1− β2µ⊥1 and µ⊥1 is any vector orthogonal to µ1 and β ∈ [0, 1]. This setting allows us to tune, through β, the similarity between tasks. For four different values of β, Figure 1 depicts the distribution of the binary output scores gi(x) both for the classical MTL-LSSVM (top displays) and for our proposed random matrix improved scheme, with optimized input labels (bottom displays).
  As a first remark, note that both theoretical prediction and empirical outputs closely fit for all values of β, 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 are not quite related as shown by the classification error presented in red in the figure.
sections.heading: 5.2 MULTICLASS TRANSFER LEARNING
sections.text: We next turn to the classical Office+Caltech256 (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 1, the results of which (Proposed) are reported in Table 1 against the non-optimized LS-SVM (Xu et al., 2013) and alternative state-of-the-art algorithms: MMDT, CDLS and ILS.3
  3MMDT: Max Margin Domain Transform, proposed in (Hoffman et al., 2013), applies a weighted SVM on a learnt transformation of the source and target. CDLS: Cross-Domain Landmark Selection, proposed in (Hubert Tsai et al., 2016), derives a domain invariant feature space. ILS: Invariant Latent Space, proposed in (Herath et al., 2017), learns an invariant latent space to reduce the discrepancy between source and target.
  Algorithm 1 Proposed Multi Task Learning algorithm.
  S/T c→ w
  w→ c c→ a
  a→ c
  w→ a a→ d
  d→ a
  w→ d c→ d
  d→ c
  a→ w
  d→ w
  Mean 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 1 demonstrates that our 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 to these high levels of performance, the method comes along with theoretical guarantees, which none of the competing works are able to provide.
sections.heading: 6 CONCLUSION: BEYOND MTL
sections.text: Through the example of transfer learning (and more generally multitask learning), we have demonstrated 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-art algorithms. As Gaussian mixtures are 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 to prove that MTL LS-SVM is likely close-to-optimal even in real data settings.
  This is yet merely a first step into a generalized use of random matrix theory and large dimensional statistics to devise much-needed low computational cost and explainable, yet highly competitive, machine learning methods from elementary optimization schemes.
sections.heading: ACKNOWLEDGMENTS
sections.text: Couillet’s work is partially supported by MIAI at University Grenoble-Alpes (ANR-19-P3IA-0003) and the HUAWEI LarDist project.