Base on the intuition of convex clustering, CCMTL solves the following problem

where $\lambda$ is a regularization parameter and $G$ is the $k$-nearest neighbor graph on the prediction models learned independently for each task.

Fig.1 shows graphically the key intuitions of CCMTL for solving problem with massive number of tasks and high accuracy.

First we introduce an auxiliary variable $L=\{l_{i,j}\}$ for each connection between node $i$ and $j$ in graph $G$, $l_{i,j}\ge 0$, and we form the following new problem:

Intuitively, Problem (2) learns the weights $l_{i,j}$ for the squared ${\mathrm{\ell }}_2$ norm regularizer ${||W_i-W_j||}_2^2$ as in Graph regularized Multi-task Learning (SRMTL) [12]. With noisy edges, squared ${\mathrm{\ell }}_2$ norm forces uncorrelated tasks to be close, while ${\mathrm{\ell }}_2$ norm is more robust which is confirmed for MTL in the experimental section.

In order to solve Problem (2), let us define $X\in {ℝ}^{TP\times N}$ as a block diagonal matrix $X=\text{diag}(X_1,\mathrm{\dots },X_T)$

define $Y\in {ℝ}^{1\times N}$ as a row vector $Y=[y_1,\mathrm{\dots },y_T],$

and define $V\in {ℝ}^{TP\times 1}$ as a column vector $V={[W_1^T,\mathrm{\dots },W_T^T]}^T$, $e_i\in {ℝ}^T$ is an indicator vector with the $i$th element set to $1$ and others $0$ and $I_P$ is an identity matrix of size $P$. Setting the derivative of Problem (2) with respect to $V$ to zero, the optimal solution of $V$ can be obtained by solving the following linear system:

where $A=(\lambda {\sum }_{i,j\in G}{l}_{i,j}(e_i-e_j){(e_i-e_j)}^T)\otimes I_P$, $B=X{X}^T$, $C=X{Y}^T$, and $W$ is derived by reshaping $V$.

Would Alg.1 converge to the optimal solution of the orginal problem? The following theorem answer the question.

CCMTL is summarized in Algorithm 1. Firstly, it initializes the weight vector $W_t$ by performing Linear Regression on each task $t$ separately. Then, it constructs the $k$-nearest neighbor graph $G$ on $W$ based on the Euclidean distance. Finally, the optimization problem is solved by iteratively updating $L$ and $W$ until convergence.

Solving the linear system in Eq. (4) involves inverting a matrix of size $PT\times PT$, where $P$ is the number of features and $T$ is the number of tasks. Direct inversion will lead to cubic computational complexity, which will not scale to a large number of tasks. However, there are certain properties of $A$ and $B$ in Eq. (4) that can be used to derive efficient implementation.

Based on Theorem 3, Eq. (4) can be solved efficiently.

The runtime of CCMTL consists of threefold: 1) Initialization of $W$, 2) $k$-nearest neighbor graph construction, and 3) optimization of Problem (2). Clearly, initialization of $W$ by linear regression is efficient and scales linearly on the number of tasks $T$. $k$-nearest neighbor graph construction naively scales quadratically to $T$, but approximate solver has complexity of $T\log T$. Solving the linear system in Eq. (4) exhibit linear complexity in $T$.

We compare our method CCMTL with several SoA methods. As baselines, we compare with Single-task learning (STL), which learns a single model by pooling together the data from all the tasks and Independent task learning (ITL), which learns each task independently. We further compare to multi-task feature learning method: Joint Feature Learning (L21) [1] and low-rank methods: Trace-norm Regularized Learning (Trace) [8] and Robust Multi-task Learning (RMTL) [2]. We also compare to the other five clustering approaches: CMTL[7], FuseMTL[13], SRMTL[12] and two recently proposed models BiFactorMTL and TriFactorMTL[10].

We employ both synthetic and real-world datasets. Table 1 shows their statistics.

Table 2 depicts the results on two retail datasets: Sales and Ta-Feng; it also depicts the time required (in seconds) for the training using the best found parametrization for each method. Here $50\%$ of samples are used for training. The best runtime for MTL methods is shown in boldface. Tasks in these two datasets are, again, rather homogeneous, therefore, the baseline STL has a competitive performance and outperforms many MTL methods. STL outperforms ITL, L21, Trace²²2 The hyperparameters searching range for L21 and Trace are shifted to $[{10}^0,{10}^{10}]$ for Ta-Feng dataset to get reasonable results., RMTL, CMTL, FuseMTL, SRMTL, BiFactor, and TriFactor on the Sales dataset, and outperforms ITL, L21, Trace and RMTL on the Ta-Feng data³³3 We set a timeout at $24h$. CMTL, SRMTL, BiFactor, and TriFactor did not return the result on this timeout for the Ta-Feng dataset.. CCMTL is the only method that performs better (also statistically better) than STL on both data sets; it also outperforms all MTL methods (with statistical significance) on both data sets, except for FuseMTL which performs slightly better than CCMTL only on the Ta-Feng data. CCMTL requires the smallest runtime in comparison with the competitor MTL algorithms. On Ta-Feng dataset, CCMTL requires only around $30$ seconds, while the SoA methods need up to hours or even days.

Table 3 depicts the results on the Transportation datasets, using two different target attributes (alighting and boarding); again, the runtime is presented for the best-found parametrization, and the best runtime achieved by the MTL methods are shown in boldface.

Figure 2 shows the recorded runtime in seconds while presenting the number of tasks in the log-scale. As can be seen, CMTL, MTFactor, and TriFactor were not capable to process 40k tasks in less than 24 hours, therefore, they were stopped (the extrapolation for the minimum needed runtime can be seen as a dashed line). FuseMTL, SRMTL, L21, and Trace tend to show a super-linear growth of the needed runtime in the log-scale. Both CCMTL and RMTL show constant behavior in the number of tasks, where only around $500$ and $800$ seconds are needed for the dataset with $160k$ tasks respectively. CCMTL is the fastest method among all the MTL competitors.