Supplemental Materials: Fast and Robust Multi-View Multi-Task Learning via
Structured Sparsity
Proofs for Section: The AGILE method
Proof of Lemma 1
Proof. According to the definition of Ut and Wt , we have
Ut Wt =VX

Uvt wtv e>
v =

v=1

VX

kUvt wtv k2

v=1

Uvt wtv >e ,kUvt wtv k2 v

(1)where ev is the vector of canonical basis with its v-th element equal to 1 and 0 otherwise.
Uv w v• Predictions from multiple views are orthogonal. In this case, { kUvtwvtk }Vv=1 are orthonormal to each other. Recall that thet 2t
trace norm actually equal to the `1 -norm on the singular values. According to (1) and singular value decomposition, wehaveVX
kUt Wt k∗ =| kUvt wtv k2 | = kUt Wt k1,2 = kUt wt kG1 .
(2)
v=1

According to Cauchy–Schwarz inequality, the following inequality holds,VX

kUvt wtv k2 ≤v=1VX

kUvt kop kwtv k2 .

(3)

v=1

where k·kop denotes the matrix operator norm, such that given an arbitrary matrix A, kAkop equals to the largest singularvalue of A,
00• Predictions from multiple views are consistent, i.e., Uvt wtv = Uvt wtv , v 6= v 0 . Thus, we have
Ut Wt = U1t wt1 1>
V =√V U1t wt1 2

U1t wt1 1>√V .
kU1t wt1 k2 V

(4)Then the following equality holds,vuVuX√
2
1 1kUvt wtv k2 = kUt Wt kF = kUt wt k2 .
kUt Wt k∗ = | V Ut wt 2 | = t(5)v=1Again, according to Cauchy–Schwarz inequality, we have
kUt wt k2 ≤ kUt kop kwt k2 .

(6)

Proof of Lemma 2
To verify Lemma 2, we need to prove the correctness of the following Lemma.
Lemma 1. For any real matrix A ∈ Rn×m , the following inequality holds;
kAkF ≤ kAk∗ ≤ kAk2,1 .

Proof. For any real matrix A ∈ Rn×m , we have the following definitions for matrix normsq√
kAkF = Tr(AA> ), kAk∗ = Tr( AA> ),andkAk2,1 =nX
i=1qkai· k2 = Tr( Diag(AA> )),

(7)

(8)

(9)

where Diag(AA> ) ∈ Rn×n denotes a diagonal matrix with same diagonal elements of AA> ∈ Rn×n . Let the SVD of A be
A = UΣV> , where U ∈ Rn×r , V ∈ Rm×r and Σ ∈ Rr×r with the i-th diagonal Σii = σi , we havekAkF =r
X

σi2 ,kAk∗ =i=1rX

σi ,(10)i=1

indicating that kAkF and kAk∗ equal to `2 -norm and `1 -norm of singular values of A, respectively. Since for an arbitrary
vector v, the√inequality kvk2 ≤ kvk1 is always satisfied, we then have kAkF ≤ kAk∗ .
Let M = AA> and mi· be the i-th row of M, we haveqs√Xm2ij ≥ mii =(11)Diag(AA> )= kmi· k2 = m2ii +AA> , i ∈ [n],ii

j6=iiiwhere mii is the i-th diagonal element of M. Hence we have kAk∗ ≤ kAk2,1 .
According to Lemma 1 and the fact A> 2,1 = kAk1,2 , we have the following inequality
kUt Wt kF ≤ kUt Wt k∗ ≤ kUt Wt k1,2 .

(12)Given the facts that kUt Wt k1,2 = kUt wt kG1 in (2) and kUt Wt kF = kUt wt k2 in (5), the above inequality becomes
kUt wt k2 ≤ kUt Wt k∗ ≤ kUt wt kG1 .

(13)

Implementation and convergence analysis for Section: Optimization algorithm
In Algorithm 1, we provide the optimization algorithm of AGILE discussed in Sec.4 of the main paper. Note that, we apply
fast-ADMM [Goldstein et al., 2014] and Accelerated Proximal Method (APM) [Nesterov, 2013] in Algorithm 1 to accelerate
the optimization algorithm, leading to a quadratic convergence rate. In Algorithm 1, prox-`2,1 and prox-`G1 denote the proximal
operator for `2,1 -norm regularized problem and `G1 -norm regularized problem, respectively.
Algorithm 1 AGILE: Optimization algorithm
Input: {{Xvt }Vv=1 }Tt=1 , {{Uvt }Vv=1 }Tt=1 , {yt }Tt=1 , α, β, γ.
Output: Θ = W + H.
1: Initialize W, H, P and Q, and set a0 , a1 := 1, k := 1.
2: repeat
−13:Ŵ(k) ← W(k) + ak−1
W(k) − W(k−1) .
ak
−1
4:
Ĥ(k) ← H(k) + ak−1
H(k) − H(k−1) .
akb (k) ← P(k) + ak−1 −1 P(k) − P(k−1) .
5:Pakb (k) ← Q(k) + ak−1 −1 Q(k) − Q(k−1) .
6:
Qak
7:
Determine the learning rate η by line search.

8:
W(k+1) ← prox-`2,1 Ŵ(k) − η∇w f (Ŵ(k) ), αη .
9:H(k+1) ← prox-`G1 Ĥ(k) − η∇h f (Ĥ(k) ), γη .
b (k) .
10:
[M(k) , Σ(k) , N(k) ] ← SVD UW (k) − Q(k)(k)βP(k+1) ← M(k) Σ̃(k) N(k)> , where Σ̃ii ← max{0, Σii − 2ρ}, ∀i.
(k+1)
(k)
(k+1)
(k)
b +P
12:
Q
←Q− UW .
√1+ 4a2k +1.
13:
ak+1 ←214:k ← k + 1.
15: until Convergence

11:

To evaluate the convergence ability of Algorithm 1, we conduct experiment on one synthetic dataset and two real-world
datasets, FOX and NUS-Object. In this experiment, we randomly select 30%, 30%, 20% and 20% of total samples as labeledtraining set, unlabeled training set, validation set and testing set, respectively, and set the parameters of AGILE as α = β = γ =1. We terminate Algorithm 1 once the relative change of its objective is below 10−5 . Figure 1 shows the convergence curves ofthe objective function value by Algorithm 1. Figure 1 shows that the objective function value converges within 400 iterations,demonstrating the efficiency of the proposed algorithm.

(a) Synthetic data(b) FOX(c) NUS-Object(d) Synthetic data(e) FOX(f) NUS-ObjectFigure 1: Convergence analysis of Algorithm 1 (α = β = γ = 1) on one synthetic dataset and two real-world datasets. Thealgorithm converged at the 48th, 115th and 361st iteration on the synthetic data, FOX, and NUS-Object, respectively. The 1strow shows the original objective value, while the 2nd row shows the objective value in the logarithmic scale. In each subfigure, Funval and Loss denote the objective value and value of loss function, respectively, and R1, R2 and R3 denote the valuesof three regularization terms.

(a) AUC(b) Accuracy

Figure 2: CD diagrams (0.05 significance level) of seven comparing methods in two evaluation metrics. The performance oftwo methods is regarded as significantly different if their average ranks differ by at least the Critical Difference (CD).

Data preparation for Section: Experiments
To compare the performances of multi-task multi-view learning methods, we conduct experiments on the following four realworld dual-heterogeneous datasets.
• FOX: The datasetrefers to the FOX web news classification [Qian and Zhai, 2014] with 4 categories (tasks): health, sports,science/technology and travel, where each article (instance) has 2 views: text view and image view. Titles, abstracts andtext body contents in one article (instance) are extracted as the text view, while the associated images are processed as
the image view, consisting of seven groups of color features. The text features are stored in `2 -normalized TFIDF vector
representation, and the image features concatenate 7 groups of color features.
• Mirflickr: The Mirflickr datasetcollects 25,000 Flickr images from Mar. 2007 to Jun. 2008 for image annotation [Huiskesand Lew, 2008]. Here, we treat the 15 relevant class labels as the ground truth categories (tasks) of images, such as
clouds, sea, flower, dog, car and people. Each image (instance) is represented by two types (views) of features: image edge
histogram and image homogeneous texture.
• NUS-Object: This datasetis an object image dataset extracted from the NUS-WIDE dataset [Chua et al., July 8 10 2009] for
web image annotation and retrieval. Images (instances) are annotated by 31 class labels (tasks), like book, car, computer,
flower, horse, train, plane, etc, and each image is represented by 5 types (views) of low-level features, including 64-D color
histogram, 144-D color correlation, 73-D edge direction histogram, 128-D wavelet texture and 225-D block-wise colormoments.
• NUS-Scene: This datasetis a scene image dataset of the NUS-WIDE dataset [Chua et al., July 8 10 2009] for web image annotation and retrieval. Images (instances) can be associated with 33 class labels (tasks), such as beach, building,airport, forest, moon, sky and road. Similar with NUS-Object, each image in the NUS-Scene dataset is represented by 5types (views) of low-level features: 64-D color histogram, 144-D color correlation, 73-D edge direction histogram, 128-D
wavelet texture and 225-D block-wise color moments.
As a preprocessing for the above datasets, we filter out the text features represented by `2 -normalized TFIDF vector representation, whose frequency is less than 1%. In addition, we eliminate the features with constant values, and remove the samples
with no associated categorization. Moreover, we discard the tasks with a relatively small number of positive instances, forexample, in the Mirflickr dataset, 7 tasks are discarded as the percentage of positive instances is less than 5%, leading to aMVMTL problem with 8 tasks.

Statistical test for Section: Experiments
To perform statistical test on experimental results in Table 2 of the main paper, we apply Nemenyi test [Demšar, 2006], whichallows to statistically evaluate the performance between every two methods. In Nemenyi test, the performance of two methods
is regarded as significantly different if their average ranks differ by at least the critical difference (CD). Fig. 2 shows the CD
diagrams for four evaluation metrics at 0.05 significance level. In each subfigure, the CD is given above the axis, where theaveraged rank is marked. In Fig. 2, algorithms which are not significantly different are connected by a thick line. In terms ofAUC, AGILE achieved statistically comparable performances with CSL-MVMT and rMTFL, and statistically superior performances than Elastic-Net, coMVL, MFM and IteM2 . In Accuracy, AGILE ranked 1st among seven comparing methods, andstatistically outperformed IteM2 . On average, the robust multi-task learning method, rMTFL, performed second best. This isprobably because the real-world datasets indeed exhibit tasks/views outliers, and two robust methods, AGILE and rMTFL, cansuccessfully cope with this setting.

References[Chua et al., July 8 10 2009] Tat-Seng Chua, Jinhui Tang, Richang Hong, Haojie Li, Zhiping Luo, and Yan-Tao Zheng. Nuswide: A real-world web image database from national university of singapore. In Proc. of ACM Conf. on Image and Video
Retrieval (CIVR’09), Santorini, Greece., July 8-10, 2009.
[Demšar, 2006] Janez Demšar. Statistical comparisons of classifiers over multiple data sets. Journal of Machine learning
research, 7(Jan):1–30, 2006.
[Goldstein et al., 2014] Tom Goldstein, Brendan O’Donoghue, Simon Setzer, and Richard Baraniuk. Fast alternating direction
optimization methods. SIAM Journal on Imaging Sciences, 7(3):1588–1623, 2014.
[Huiskes and Lew, 2008] Mark J. Huiskes and Michael S. Lew. The mir flickr retrieval evaluation. In MIR ’08: Proceedingsof the 2008 ACM International Conference on Multimedia Information Retrieval, New York, NY, USA, 2008. ACM.
[Nesterov, 2013] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science& Business Media, 2013.
[Qian and Zhai, 2014] Mingjie Qian and Chengxiang Zhai. Unsupervised feature selection for multi-view clustering on textimage web news data. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, pages 1963–1966. ACM, 2014.