# Alternating Direction Multiplier Method for Matrixl2,1-Norm Optimization in Multitask Feature Learning Problems

Authors: Yaping Hu; Liying Liu; Yujie Wang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The joint feature selection problem can be resolved by solving a matrixl2,1-norm minimization problem. For l2,1-norm regularization, one of the most fascinating features is that some similar sparsity structures can be employed by multiple predictors. However, the nonsmooth nature of the problem brings great challenges to the problem. In this paper, an alternating direction multiplier method combined with the spectral gradient method is proposed for solving the matrix l2,1-norm optimization problem involved with multitask feature learning. Numerical experiments show the effectiveness of the proposed algorithm.


---

## Body

## 1. Introduction

Because of its widespread application in high-dimensional sparse learning, the feature selection problem has been concerned widely by the machine learning community in multitask feature learning and become a hot research field in recent years. The purpose of multitask feature learning is to learn the shared information between related tasks, so as to promote the learning effect. Learning multiple related tasks simultaneously is much more efficient compared to single-task learning particularly [1, 2]. For feature selection tasks in multitask learning, using mixed l2,1-norm can produce joint sparsity in the feature layer and task layer. In particular, l2,1-norm is sometimes more advantageous because it often leads to more sparse solutions. In multitask learning by Obosinski et al. [3] and Argyriou et al. [4], the regularization of l2,1-norm is introduced for the first time. In recent years, a lot of research studies have been carried out on it. Multiple predictors are encouraged to share similar parameter sparse patterns from different tasks [3–5], which is a very attractive feature of the l2,1-norm regularized problem. When the objective function is convex, the l2,1-norm regularized problem is convex and has a global optimal solution. However, the optimization problem is difficult to solve because of the nonsmoothness of l2,1-norm regularization. The method in Liu et al. [6] transforms the minimization problem of l2,1-norm into two equivalent convex smooth optimization problems and then minimizes them by Nesterov’s accelerated gradient method [7]. For the l2,1-norm regularized problem, a proximal alternating direction method was presented recently by Xiao et al. [8]. Hu et al. [9] proposed inexact accelerated proximal gradient algorithms to solve the l2,1-norm regularization.The training set ofk tasks is given by aij,biji=1mjj=1,2,…,t, where for the jth task, aij∈ℜn denotes the ith sample, mj denotes the number of training samples, bij denotes the corresponding response, and the total number of training samples is m=∑j=1tmj. The matrix Aj=a1j,…,amjjT∈ℜmj×n is the data for the jth task, and bj=b1j,…,bmjjT∈ℜmj, X:,j∈ℜn is the sparse feature for the jth task. A=A1,…,At∈ℜm×n, b=b1,…,btT∈ℜm, and X=X:,1,…,X:,t∈ℜn×t are the joint learning features for the task in multitask learning. It is encouraged to set elements of several rows in X to be zero to select features globally. According to Argyriou et al. [4], the problem of l2,1-norm minimization can be described as(1)minX∈ℜn×t12∑j=1tAjX:,j−bj22+μX2,1,in which matrix X2,1 is defined as(2)X2,1=∑i=1n∑j=1tXi,j2=∑i=1nXi,:2,where Xi,: denotes the ith row element of matrix X and X:,j denotes the jth column element of matrix X. The first term measures the loss caused by matrix X which is based on the training data samples of A and b, and the second term is the regularization term in (1), where μ>0 is the regularization parameter which can be used to keep a balance between the two terms to minimize.As described in [10], the alternate direction multiplier method (ADMM) is a natural method in the field of large-scale data distribution machine learning and big data-related optimization because it can process the objective function separately and synchronously, and it has aroused widespread attention in the past few years. ADMM method is widely used in a lot of fields, such as image restoration [11], machine learning [12], and compressed sensing [13]. This widespread application has sparked a strong interest in further understanding the theoretical nature of the ADMM (see [14–17]).Barzilai and Borwein in [18] first proposed the spectral gradient method to solve the strict convex quadratic minimization problems. Due to efficiency and computational cheapness, BB method has caused wide attention in the area of optimization. Raydan [19] developed this method to solve general unconstrained optimization problems. Recently, the BB method has been successfully extended for solving the nonsmooth convex optimization problem [20].In this paper, an ADMM with the spectral gradient method is proposed to solve thel2,1-norm regularization problem in the area of multitask learning. We first add a new auxiliary variable to the augmented Lagrangian form of (1), then iteratively minimize the augmented Lagrangian function in which an exact method is used to solve one subproblem, and the spectral gradient method is employed to solve the other subproblems. Experimental results show that the proposed ADMM-BB method is competitive, fast, and efficient.The rest of the paper is arranged as follows. Section2 introduces the ADMM method for solving (1). Section 3 explains how to find the solution to the subproblems generated by each iteration and gives a practical ADMM using the spectral gradient algorithm. Section 4 gives the numerical results of the simulation data set and the real data set and compares them with other methods. Finally, Section 5 summarizes and concludes this article.


## 2. ADMM forl2,1-Norm Minimization

Thel2,1-norm matrix minimization problem has the following standard form:(3)minX∈ℜn×t12AX−b22+μX2,1,where A:ℜn×t⟶ℜm is a mapping defined based on matrix vector multiplication for each learning task, i.e., AX=A1X:,1,…,AtX:,t∈ℜm. By introducing auxiliary variable Y, problem (3) is equivalently transformed into a linearly constrained convex programming problem:(4)minX∈ℜn×t12AY−b22+μX2,1s.t.X−Y=0.The augmented Lagrangian function of problem (4) is defined as(5)ℒcX,Y,Z=12AY−b22+μX2,1−Z,X−Y+c2X−Y2,where c>0 is the penalty parameter, ⋅ means the standard trace inner product, X,Y:=TrXTY for X and Y in ℜn×t, symbol “Tr” represents the trace, i.e., the sum of the diagonal elements of a squared matrix which is also equal to the sum of the eigenvalues. For any matrix X∈ℜn×t, ⋅ is defined as the Frobenius norm:(6)X=XFr=∑i=1n∑j=1txi,j2,where xi,j is the i,jth element of matrix X so that X=X,X. For solving (5), the iterative scheme of the alternating direction method of multipliers is(7)Xk+1=argminX∈ℜn×tμX2,1−Zk,X+c2X−Yk2,(8)Yk+1=argminY∈ℜn×tAY−b22+Zk,Y+c2Xk+1−Y2,(9)Zk+1=Zk−cXk+1−Yk+1,where Zk∈ℜn×t is the Lagrange multiplier.The alternating direction multiplier method for solving problem (4) can be expressed as follows.Algorithm 1.
ADMM forl2,1-norm minimization problem.Step 1: findXk+1 via(10)0∈∂μXk+12,1−Zk−cXk+1−Yk,where∂⋅ represents the subgradient operator of the convex function ⋅2,1.Step 2: solveYk+1 via(11)Y−Yk+1,A∗AYk+1−b+Zk−cXk+1−Yk+1≥0,∀Y∈ℜn×t.Step 3: compute the multiplierZk+1 by (9).
The following result shows that the optimal solution set ofl2,1-norm matrix minimization problem (3) is bounded (see [9]).Lemma 1.
For eachμ>0, the optimal solution set X∗ of (3) is bounded, and for any X∗∈X, we have(12)X≤χ.(13)χ=minb222μ,A∗AA∗−1b2,1,Aissurjective,b222μ,otherwise.The global convergence property of Algorithm1 holds directly based on the results developed by Bertsekas and Tsitsiklis [21], Chapter 3, p. 256 for general convex programming problems.Theorem 1.
LetXk,Yk,Zk be the sequence generated by Algorithm 1 with limk⟶∞ck=c∞≤∞. Then, Xk,Yk,Zk is bounded, and every limit of Xk,Yk is an optimal solution of equivalent problem (4).


## 3. ADMM-BB Method forl2,1-Norm Minimization

Section2 gives the theoretical alternating direction multiplier method of the l2,1-norm minimization problem. However, a key issue has not yet been resolved: how to solve subproblems (7) and (8) efficiently? This problem is fundamentally important because if it is difficult to solve each subproblem, this method will not be useful anyway. In this paper, an exact method is used to solve (7), and the spectral gradient method is employed to solve (8).Givenc>0 and Yk,Zk∈ℜn×t,ℜn×t, we have(14)Xk+1=argminX∈ℜn×tℒcX,Yk,Zk=argminX∈ℜn×tμX2,1−Zk,X−Yk+c2X−Yk2=argminX∈ℜn×tμX2,1+c2X−Yk+1cZk2.LetN=Yk+1/cZk. Equation (14) has the solution of the form(15)Xk+1=argminX1,:,…,Xn,:∑i=1nμXi,:2,1+c2Xi,:−Ni,:2,which indicates that involved problem (15) can be broken down into n independent t-dimensional subproblems:(16)minXi,:∈ℜtμXi,:2,1+c2Xi,:−Ni,:2,i=1,2,…,n.Clearly, the optimal solutionXi,:∗ can be obtained in the direction Ni,:, and it has the form of the formula Xi,:∗=aNi,: in which a≥0 is a parameter. Based on developing a Lagrangian dual form, subproblem (16) has a closed-form solution (see, e.g., [22, 23]) which can be explicitly expressed as(17)Xi,:∗=1−μcNi,:2+Ni,:,i=1,…,n,where ⋅+=max⋅,0. Therefore, the closed-form solution of (10) is given as follows:(18)Xk+1=1−μcYk+1/cZk1,:2+Yk+1cZk1,:1−μcYk+1/cZk2,:2+Yk+1cZk2,:⋯1−μcYk+1/cZkn,:2+Yk+1cZkn,:.Next, we analyze another subproblem (8). For fixed c>0, let(19)θY≔ℒcXk+1,Y,Zk.Now, we investigate how to use the spectral gradient method to solve the corresponding problem:(20)minY∈ℜn×tθY.The functionθY is convex and everywhere differentiable with(21)∇θY=A∗AY−b+Zk−cXk+1−Y.In order to distinguish the superscript in Algorithm1, we apply the subscripts in the iteration of this subproblem. Spectral gradient method is defined by(22)Yj+1=Yj−αj∇θYj,where αj is given by(23)αj=sj−1Tuj−1uj−1Tuj−1,where sj−1=Yj−Yj−1 and uj−1=∇θYj−∇θYj−1.Now, the spectral gradient method for (20) can be described as given in Algorithm 2.Algorithm 2.
The spectral gradient method.Step 0: givenY0=Yk, ϵ∈0,1, α0=1, and j:=0.Step 1: termination criterion: stop ifYj satisfies termination condition ∇θYj<ϵ. Otherwise, go to the next step.Step 2: computeαj by (23) if j>0. Let Yj+1=Yj−αj∇θYj.Step 3: letj:=j+1 and go to Step 1.
Finally, by adopting a relaxation factorγ, the multiplier update formula in Algorithm 1 is replaced by(24)Zk+1=Zk−γcXk+1−Yk+1,0<γ<5+12.
Glowinski in [24] first suggested the instruction of γ, and it has shown better performance in numerical experiments [25].
Now, a practical ready-to-implement version of the ADMM (7)–(9) can be described as follows.Algorithm 3.
ADMM-BB for thel2,1-norm minimization problem.Step 0: letc0 and κ>1 be given. Let Y0 be arbitrary. Let Z0 be the initial estimated Lagrange multipliers. Let k:=0.Step 1: when the stopping criterion holds, then stop; otherwise, continue.Step 2: computeXk+1 by (18).Step 3: computeYk+1 by solving the following problem with the spectral gradient method:(25)minY∈ℜm×nθY.Step 4: computeZk+1 by (24).Step 5: letk≔k+1 and go to Step 1.
Based on the conclusions of Bertsekas and Tsitsiklis ([21], Chapter 3, Proposition 4.2) and Glowinski ([24], Chapter VI, Theorem 5.1), for Algorithm 3, the following convergence conclusion holds.Theorem 2.
Suppose thatℒc has a saddle point X¯,Y¯,Z¯. Let Xk,Yk,Zk be the sequence generated by Algorithm 3 with c>0 and γ∈0,5+1/2. Then,(26)limk⟶∞Xk,Yk=X¯,Y¯,limk⟶∞Zk+1−Zk=0,Zkisbounded.Moreover, ifZ∗ is a weak cluster point of Zk, then X¯,Y¯,Z∗ is a saddle point of ℒc.


## 4. Experiments

In this section, we will give the numerical experimental results of ADMM-BB to solve matrixl2,1-norm minimization problem (3). The experiments are carried out by MATLAB R2018b running on a computer with 2.8 GHz Intel Pentium CPU and 8 GB of low voltage memory.Based on simulated data and real data, we conducted two types of numerical experiments to study the performance of the ADMM-BB method. In the test, we compared the ADMM-BB method with the IADM-MFL method [8] because the IADM-MFL method is well known and gives a feasible way to find a solution to the joint feature selection problem in the area of multitask learning. For each test function, starting with the origin point, when the distance between adjacent iteration points is less than a given constant tol, the algorithm stops, i.e.,(27)RelChg=Xk−Xk−1FXk−1F≤tol.We choosec=0.01/meanb in the following series of experiments.Example 1.
As [4], the simulation data sets are created by using a 5-dimensional zero-mean Gaussian distribution with a covariance matrix that equals to diag {1, 0.64, 0.49, 0.36, 0.25}, which can be denoted by X¯:,j. For all X¯:,j, expand it to 20 irrelevant dimensions by adding zero elements. The training data Aj are a random Gaussian matrix generated by Matlab command randnmj,n. Using Aj and X¯:,j, get the outputs bj as(28)bj=AjX¯:,j+ω,where Gaussian noise ω is described by a mean of 0 and a standard deviation of 1.e − 2. In each performed method, X∗ denotes the optimal solution of matrix l2,1-norm minimization problem (3). To measure the quality of X∗ to original X¯, we set the relative error as follows:(29)RelErr=X∗−X¯FX¯F.
We will analyze the performance of both methods with different number of dimensions and tasks because they will certainly affect the performance of each algorithm as an important factor. The numerical results are shown in Table1, which contains the CPU time required in seconds (TIME), the total number of iterations (ITER), the total number of tasks (t), the dimension of the test data (n), and the dimension of the outputs (m).Table 1
Numerical results for the random problem.
b, XADMM-BBIADM-MFL(m, n, t)ITERTIMERelErrITERTIMERelErr(10000, 10, 100)140.05062.87e − 03320.17193.36e − 03(20000, 10, 200)150.21882.65e − 03310.28132.97e − 03(30000, 10, 300)150.23442.98e − 03310.29693.25e − 03(10000, 15, 100)180.06253.75e − 03420.25003.49e − 03(20000, 15, 200)180.29693.55e − 03410.39063.24e − 03(30000, 15, 300)190.39063.66e − 03440.42193.47e − 03(10000, 20, 100)220.14064.78e − 03510.43754.55e − 03(20000, 20, 200)220.39064.92e − 03520.56134.27e − 03(30000, 20, 300)220.59385.43e − 03541.39064.35e − 03(10000, 25, 100)270.25006.49e − 03660.59384.94e − 03(20000, 25, 200)260.29696.40e − 03640.76564.94e − 03(30000, 25, 300)260.73446.81e − 03651.51565.11e − 03(10000, 30, 100)320.35949.04e − 03800.71887.03e − 03(20000, 30, 200)310.62509.23e − 03810.87506.27e − 03(30000, 30, 300)310.96888.47e − 03811.73445.54e − 03From the results in Table1, it can be seen that although both methods have successfully terminated, the number of iterations and CPU time of the ADMM-BB method are much less than IADM-MFL.Then, the parameters involved in the methods are specified astol=1e−3, t=300, n=20, μ=1e−2, and mj=100j=1,2,…,t. For each solving algorithm, we evaluate the objective function values and test error rate, and the convergence behavior of these algorithms is shown in Figure 1. To visually compare the convergence speed of the algorithms, the four subgraphs in Figure 1 show the change of the function value and relative error with the number of iterations and CPU time for both ADMM-BB and IADM-MFL algorithms. We present the relative error and the objective function values plotted against the number of iterations in the first row in Figure 1 and present the relative error and the objective function values plotted against the computational time in the second row. Figure 1 shows that although both ADMM-BB and IADM-MFL algorithms generate decreasing sequences and converge to the same function value as well as relative error, the performance of ADMM-BB is better than IADM-MFL in terms of iteration numbers and CPU time.Figure 1
Convergence performance of ADMM-BB and IADM-MFL.
(a)(b)(c)(d)Example 2.
In this test, we demonstrate the performance of the proposed algorithms on a real data set.dmoz is a text categorization data set, in which every 10 tasks correspond to subcategories of the arts category. The dmoz data set can be downloaded from http://www.dmoz.org/. In order to learn the joint feature between tasks, we randomly select data from each task for training and sample 20%, 30%, 40%, 50%, 60% and 70%, respectively, of the dmoz data set and then test the two methods at the same time. Except for μ=1e−4, the other parameters are the same as in the proceeding example for both ADMM-BB and IADM-MFL methods. The corresponding numerical results are summarized in Table 2.Table 2
Numerical results for the real problem.
Demob, XADMM-BBIADM-MFL(m, n, t)ITERTIMERelChgITERTIMERelChg20%(80, 500, 10)1781.349.95e − 043652.479.97e − 0430%(120, 500, 10)2822.239.98e − 044122.549.93e − 0440%(160, 500, 10)2662.339.96e − 044152.739.92e − 0450%(200, 500 10)3002.759.95e − 044042.809.73e − 0460%(240, 500, 10)3062.869.99e − 044273.139.95e − 0470%(280, 500, 10)3493.309.99e − 044603.479.97e − 04From Table2, we can see that ADMM-BB is an effective method and works better on these problems.


## 5. Conclusion

The convergence theory for the alternating direction multiplier method for the convex optimization problem has been well established by Bertsekas and Tsitsiklis [21] and Glowinski [24]. The main purpose of this paper is to demonstrate that this method is robust for the matrix l2,1-norm regularized minimization problem. The key element is the practical efficiency of the alternating direction multiplier method by using the spectral gradient method in this paper. The corresponding numerical results verify the encouraging efficiency of the proposed method in solving the joint feature selection problem.



---

*Source: 4864296-2020-08-26.xml*