Efficient k-Support-Norm Regularized Minimization via Fully Corrective Frank-Wolfe Method

1 Introduction

In many sparsity inducing machine learning problems, a common practice is to use the `1 norm as a convex relaxation of the model parameter cardinality constraint. The `1 norm, however, tends to shrink excessive number of variables to zeros, regardless the potential correlation among the variables. In order to alleviate such an over-shrinkage issue of `1-norm, numerous methods including elastic net [Zou and Hastie, 2005] and trace Lasso [Grave et al., 2011] have been proposed in literature. All of these methods tend to smooth the output parameters by averaging similar features rather than selecting out a single one. More recently, k-support-norm k · ksp k is proposed as a new alternative that provides the tightest convex relaxation of cardinality on the Euclidean norm unit ball [Argyriou et al., 2012]. Formally, the k-supportnorm of a vector w 2 Rp is defined as where Gk denotes the set of all subsets of ¶1↪ 2↪ ▷▷▷↪ p♦ of cardinality at most k. More properties of k-support-norm are analyzed in [Argyriou et al., 2012].

⇤These match the formatting instructions of IJCAI-07. The support of IJCAI, Inc. is acknowledged.

As a regularizer, the k-support-norm is characterized by simultaneously selecting a few relevant groups and penalizing the `2-norm of the selected individual groups. The following k-support-norm regularized model was considered in [Argyriou et al., 2012] for sparse prediction tasks:

where f(w) is a convex and differentiable objective function. The parameter k is regarded as an upper bound estimation of the number of non-zero elements in w. It has been shown that this model leads to improved learning guarantees as well as better algorithmic stability [Argyriou et al., 2012].

Motivation One issue that hinders the applicability of the ksupport-norm regularized model (1) is its high computational complexity in large scale settings. Indeed, proximal gradient methods are conventionally used for optimizing the composite minimization problem in (1) [Argyriou et al., 2012; Lai et al., 2014; Eriksson et al., 2015]. Given the gradient vector, the per-iteration computational cost of proximal gradient methods is dominated by an proximity operator of the following form:

In the work of [Argyriou et al., 2012], a closed form solution of (2) was derived based on an exhaustive search strategy. However, the complexity of such a strategy is O(p(k+log p)) which is computationally expensive when p is large. Despite significant speed-ups have been reported in [Lai et al., 2014; Eriksson et al., 2015] by using binary search, those methods are still expensive for large scale problems.

It has been known that the k-support-norm ball Bk↪sp $ := ¶w 2 Rp : kwksp k  $♦ is equivalent to the convex hull of C (2) k↪$ = ¶w 2 Rp : kwk0  k↪ kwk2  $♦. In this sense, k-support-norm ball Bk↪sp $ provides a convex envelope of the nonconvex set C (2) k↪$ . Recently, Frank-Wolfe-type methods for minimizing a convex objective over a convex hull have received wide interests in optimization and machine learning [Zhang, 2003; Shalev-Shwartz et al., 2010; Yuan and Yan, 2013]. These algorithms have been shown to achieve satisfying trade-off between convergence rate and iteration complexity. In this paper, inspired by the success of these algorithms, we consider applying the Frank-Wolfe method to solve the composite optimization problem (1).

Challenge and Contribution In this paper we propose to convert the k-support-norm regularized formulation into an identical constrained formulation by introducing an augmented variable as the bound of the regularizer (kwksp k )2 . We then develop a fully corrective variant of the Frank-Wolfe algorithm to optimize the augmented model. The proposed algorithm is called k-FCFW in the following context. The convergence rate of the proposed algorithm is analyzed. Particularly, we prove that the proposed algorithm converges linearly under proper conditions. Our this result is stronger than the sublinear rate of convergence obtained in [Harchaoui et al., 2015] for norm regularized minimization with Frank-Wolfe methods. The advantage of the proposed algorithm over prior algorithms is demonstrated by empirical results in various learning tasks.

2 RelatedWork

2.1 k-Support-NormRegularized Learning

The k-support-norm regularized learning models have been extensively studied in machine learning and computer vision. Multiple k-support-norm regularized convex models were investigated in [Blaschko, 2013]. The applications of ksupport-norm to various computer vision problems have been explored in [Lai et al., 2014]. The k-support-norm was applied to generalized dantzig selector for linear models [Chatterjee et al., 2014]. In this paper the proposed algorithm applies to first-order k-support-norm regularized minimization problem, which is different from the squared k-support-norm that we consider in this work and [Argyriou et al., 2012; Lai et al., 2014; Eriksson et al., 2015]. The authors of [Belilovsky et al., 2015b] showed that it is helpful to use k-supportnorm regularization in fMRI data analysis including classification, regression and data visualization. In [Belilovsky et al., 2015a], total variation penalty is incorporated in the ksupport framework and applied in image and neuroscience data analysis.

2.2 Frank-Wolfe Method

The history of Frank-Wolfe method dates back to [Frank and Wolfe, 1956] for constrained optimization problem

where D is a polytope convex set. It is also known as conditional gradient method. Due to the potential of efficiency improvement when applied in solving minimization problem with some forms of constraint, recently there is an increasing Algorithm 1: k-FCFW Algorithm for k-support-norm regularized problem.

trend to revisit and restudy this method. The detail of original Frank-Wolfe method, its variants and algorithm analysis can be found in [Jaggi, 2013; Garber and Hazan, 2014]. FrankWolfe-type methods have been developed to solve numerous optimization problems including structural SVM [LacosteJulien et al., 2013], trace norm regularization problem [Dudik et al., 2012] and atomic norm constrained problem [Rao et al., 2015]. In sparse learning, a number of Frank-Wolfe-type methods, e.g., forward greedy selection [Shalev-Shwartz et al., 2010] and gradient Lasso [Kim and Kim, 2004], have been developed to solve sparsity constrained problems. In the context of boosting classification, the restricted gradient projection algorithms stated in [Grubb and Bagnell, 2011] is essentially a forward greedy selection method over `2functional space.

3 The k-FCFWmethod for k-Support Norm Regularized Minimization

To apply the Frank-Wolfe method, we reformulate (1) into a constrained optimization problem:

Here ✓ is an augmented variable bounding the term (kwksp k )2 . We introduce in ∗3.1 the k-FCFW algorithm for solving the above constrained formulation. The convergence rate of kFCFWwill be analyzed in ∗3.2.

3.1 AlgorithmDescription

The k-FCFW algorithm for k-support-norm regularized minimization is outlined in Algorithm 1. As is known that the k-support-norm ball Bk↪sp $ := ¶w 2 Rp : kwksp k  $♦ is equivalent to the convex hull of C (2) k↪$ = ¶w 2 Rp : kwk0  k↪ kwk2 $♦. That is, Therefore, given v > 0, the optimal u of (3) admits the following close-form solution:

where rkf(w(t-1) ) denotes a truncated version of rf(w(t-1) ) with its top k (in magnitude) entries preserved. By substituting this back to (3) we get v(t) through the following quadratic program:

Obviously v(t) = ⇣ krkf(w(t-1) )k 2λ ⌘2 ↪ and thus,

At each time instance t, we record all previous updates in U (t) = ¶w(0) ↪ u(1) ↪ ▷▷▷↪ u(t) ♦ and V (t) = ¶✓(0) ↪ v(1) ↪ v(2) ↪ ▷▷▷↪ v(t) ♦. At the t-th iteration, the optimal value of w(t) and ✓(t) are jointly searched on the convex hull define by U (t) and V (t) . The subproblem (4) of estimating ↵(t) is a simplex constrained smooth minimization problem. The scale of such a problem is dominated by the value of t. This subproblem can be solved via off-the-shelf algorithms such as the projected quasi-Newton (PQN) method [Schmidt et al., 2009] as used in our implementation.

It is noteworthy that the subproblem (3) is equivalent to the following k-support-norm regularized linear program:

This is in contrast to the proximal gradient method which solves the quadratic proximity operator (2) at each iteration. Apparently the former is less expensive to solve than the latter which involves exhaustive search. In addition, when t is of moderate value and warm start is adopted to initialize the parameters, the subproblem (4) can often be accurately solved with very few iterations. In sparse learning problem the k value is often much smaller than model parameter dimension hence the overall computational cost of k-FCFW is expected to be lower than the proximal gradient algorithms.

Given a constant radius $c > 0, the k-support-norm constrained minimization problem

is essentially a special case of the regularized form by directly assigning ✓ = $2 c . The proposed algorithm can be easily modified to solve the constrained model (6).

3.2 Convergence Analysis

To analyze the model convergence, we need the following key technical conditions imposed on the curvature of the objective function f restricted on sparse subspaces.

Definition 1 (Smoothness and restricted strong convexity). We say f is L-smooth if there exists a positive constant L such that for any w and w0 ,

We say f is ⇢(s)-strongly convex at sparsity level s, if there exists positive constants ⇢(s) such that for any kw -w0 k0  s,

In the analysis to follow, we define

and

Let ¯ s = k ¯wk0 and ¯ ✓ = (k ¯wksp k )2 . Consider the radius r given by

We now analyze the convergence of Algorithm 1. Before presenting the main result, we need some preliminaries.

Lemma 1. There exist ¯U = [¯u1↪ ▷▷▷↪ ¯u¯l] 2 Rp⇥¯l with k¯uik0  k, k¯uik2 = p¯ ✓, and ¯↵ 2 4¯l such that

Please refer to Appendix A.1 for the proof of Lemma 1. In the following analysis, we will consider such a decomposition ¯w = ¯U ¯↵ as guaranteed by Lemma 1. Given a matrix M, we write its mathcal versionMas a vector set consisting of the columns of M. Similarly, given a set M of vectors of the same size, we denote M be a matrix whose columns are the elements of M. Let σmin(M) be the smallest singular value of matrix M. We establish in the following theorem a linear rate of convergence for Algorithm 1.

Theorem 1. Let s = maxt kw(t) k0. Let M(t) = ¯ U [ U (t) . Assume that there exists a ¯ β > 0 such that σmin(M (t) ) ≥ ¯ β for all t. Assume that f is L-smooth and ⇢(s + ¯ s)- strongly convex. Given ✏ > 0, let us run Algorithm 1 with t ≥ 1 ⇣ ln h F(w(0) ;λ)-F( ¯w;λ) ✏ i where ⇣ := min n ⇢(s+¯ s) ¯ β 4¯lLr2 ↪ 12 o ▷ Then Algorithm 1 will output w(t) satisfying

The proof of Theorem 1 is given in Appendix A.2.

Remark 1. In general constrained minimization problems, the Frank-Wolfe method is known to have O( 1t ) convergence rate [Jaggi, 2013] and O( 1 t2 ) if the constraint set is strongly-convex [Garber and Hazan, 2014]. Several linear convergence guarantees are established by adding various specific assumptions to either constraint set or loss function in literatures such as [Beck and Teboulle, 2004; ˜Nanculef et al., 2014], but they are not directly applicable to our problem. In a recent work of [Lacoste-Julien and Jaggi, 2015], a global linear convergence rate is proved for the constrained optimization on polytope. Their analysis, however, does not fit for our algorithm as the constraint (kwksp k )2  v is a k-support-norm cone, rather than a polytope. This imposes extra challenges in analysis. Another related work is [Harchaoui et al., 2015] which also applies Frank-Wolfe method to regularized minimization problems. However it is restrictive as it requires an estimation of the bound of the regularizer which is hard to know in practice. Also, the sublinear convergence rate established in that paper is weaker than the linear rate proved in Theorem 1.

Remark 2. In Algorithm 1 we have required the subproblem (4) in Step (S4) to be solved exactly. This could be be computationally demanding if the objective function f is highly nonlinear and t is relatively large. Instead of solving the subproblem (4) exactly, a more realistic option in practice is to find a suboptimal solution up to a precision " > 0 w.r.t. the first-order optimality condition. That is, ¶w(t) ↪ ✓(t) ♦ satisfy for any w = U (t)↵ and ✓ = V (t)↵,

Following the similar arguments in the proof of Theorem 1 we can be prove that F (w(t) ; λ)  F ( ¯w; λ) + ✏ + O(") after t = O (ln( 1✏ )) steps of iteration. In other words, the optimization error of the subproblem (4) does not accumulate during iteration.

4 Experiments

This section is devoted to showing the empirical performance of k-FCFW and comparing it to the state-of-the-art algorithms for k-support-norm regularized minimization. All the considered algorithms are implemented in Matlab and tested on a computer equipped with 3.0GHz CPU and 32GB RAM.

4.1 k-Support-NormL2-Logistic Regression

Given a binary training set ¶xm↪ ym♦Mm=1 ↪ xm 2 Rp ↪ ym 2 ¶-1↪ 1♦, the k-support-norm regularized logistic regression problem is formulated as

where `(w; xm↪ ym) = log (1 + exp(-ymw>xm)) is the logistic loss on a training pair (xm↪ ym). The parameter ⌧ controls the strong convexity of the loss function.

We test the algorithm efficiency on a synthetic dataset. The model parameter ground truth wgt is designed to be a p-dimension vector as follows:

Within the supporting set we partition the feature dimension into g groups. Each group of ¶xm↪1↪ xm↪2↪ ▷▷▷↪ xm↪p0 ◁g♦, ..., ¶xm↪(g-1)p0 ◁g+1↪ ▷▷▷↪ xm↪p0♦ follows normal distribution that the mean value of each group is drawn from N(0↪ 1). Other dimensions are drawn from N(0↪ 1) as noise. Finally xm is normalized by xm = xm◁kxmk. The data label ¶ym♦Mm=1 follows Bernoulli distribution with probability P(ym = 1♣xm) = exp(w> gt xm) 1+exp(w> gt xm) . The task is designed as selecting the top k most discriminative features for classification using logistic regression model through solving (9).

We produce the training data by setting M = 500, p = 106 , g = 20, p0 = 10000, k = 2000↪ 4000↪ 6000↪ 8000 and 10000, respectively. λ is selected by grid search according to the testing result on a validation set of size 100. We set the termination criterion as ♣F(w(t) )-F(w(t-1) )♣ F(w(t-1) )  10-4 . We replicate the experiment 10 times and report the mean of the numerical results.

We compare the efficiency of k-FCFWwith three state-ofthe-art proximal gradient methods: (1) the Box Norm solver (denoted by BN) proposed in [McDonald et al., 2014]; (2) the binary search based solver proposed in [Lai et al., 2014] (denoted by BS); and (3) the solver proposed in [Eriksson et al., 2015] which tries to find the active set (AS) by a twostep binary searching strategy. All of these proximal gradient solvers are implemented in the framework of FISTA [Beck and Teboulle, 2009].

The running time of the considered algorithms is shown in Figure 1(a). It can be observed that our method is significantly faster than all the three comparing solvers.

We also compare the efficiency of k-FCFW with ADMM [Parikh and Boyd, 2013] which is another popular framework for regularized minimization problems. Since AS has been observed to be superior to the other considered proximity operator solvers, we equip ADMM with AS as its proximity operator solver. The running time curves of ADMMAS are drawn in Figure 1(a). Clearly, ADMM-AS is inferior to k-FCFW and the proximal gradient algorithms as well. Actually, we observe that ADMM-AS fails to converge to the desired accuracy given maximum number of iterations. In Figure 1(b), we plot the convergence curves of the considered algorithms under k = 2000 and 10000. It can be observed that our method needs significant less number of iterations to reach comparable optimization accuracy.

4.2 k-Support-NormMatrix Pursuit

In this group of experiments, we apply the proposed method to the k-support-norm regularized matrix pursuit problem. In many graph based machine learning algorithms such as semisupervised classification and subspace segmentation, a key step is learning the sample affinity matrix [Liu et al., 2010; Yuan and Li, 2014]. Matrix pursuit has been proved to be an effective approach. The results of [Lai et al., 2014] indicate that the k-support-norm regularized matrix pursuit method achieves superior performance in various applications. The k-support-norm regularized matrix pursuit is formulated as:

where X 2 Rd⇥n is the data matrix with n samples in ddimension space and vec(W) denotes the vectorization of W .

The MNIST [LeCun et al., 1998] and USPS [Hull, 1994] datasets are adopted for testing. For MNIST dataset, we resize each image into 14 ⇥ 14 then normalize the gray value into [0↪ 1]. The pixel values are then vectorized as image feature. The USPS dataset is preprocessed by [Cai et al., 2011]. Each image is represented by a 256-dimension feature vector and the feature values are normalized into [-1↪ 1]. Each image of both datasets are further normalized to be a unit vector. We select 100 images per digit fromMNIST and 200 images per digit from USPS hence the size of datasets are 1000 and 2000, respectively. We use the same optimization termination criterion as in the previous experiment. The algorithms are tested under k = 4000↪ 6000↪ 8000↪ 10000 and 12000 in the k-support-norm. The regularization parameter is set to be λ = 20.

We first compare k-FCFW with three FISTA algorithms that respectively employ proximity operator solver BN, BS and AS. The comparison of average time cost over 10 replications is illustrated in Figure 2. The time cost curves of ADMM-AS are also shown in Figure 2. The convergence curves of the considered methods evaluated by F(W) when k = 4000 and 12000 are shown in Figure 3. From the results we can see that in these cases, k-FCFW is the most efficient one for optimization. As the value of k increases, the efficiency advantage of k-FCFW gets more significant.

5 Conclusion

In this paper, we proposed k-FCFW as a fully corrective Frank-Wolfe algorithm for optimizing the k-support-norm regularized loss minimization problem. We have established a linear rate of convergence for the proposed algorithm, which to our knowledge is new for Frank-Wolfe-type algorithms when applied to composite formulation. Comparing to the conventionally adopted proximal gradient algorithms and ADMM, k-FCFW has superior rate of convergence in theory and practice. Numerical results in logistic regression and matrix pursuit applications confirmed that k-FCFW is significantly more efficient than several state-of-the-art proximal gradient descent methods, especially in large scale settings. To conclude, both theoretical analysis and empirical observations suggest that k-FCFW is a computationally attractive alternative to the proximal gradient algorithms for solving the k-support-norm regularized minimization problems. As a future study in this line, we will investigate the generalization of k-FCFW to generic group-sparsity-norm regularized minimization problems of which the model considered in this paper is a special case.

A Appendix

A.1 Proof of Lemma 1

Proof. Consider

Let ¯l = ♣ ˜ U♣ and ˜ U = ¶˜ui♦¯li=1 . Based on the definition of k-support-norm we have that ¯w = Pi ˜ui and Pi k˜uik2 = k ¯wksp k = p¯ ✓. We construct ¯U = [¯u1↪ ▷▷▷↪ ¯u¯l] with ¯ui defined by ¯ui = p¯ ✓˜ui◁k˜uik. Then we can show that ¯w admits a decomposition of ¯w = ¯U ¯↵ with some ¯↵ lies in a ¯l-dimensional simplex 4¯l. Indeed, since ¯w = Pi ˜ui = Pi ¯ui(k˜uik◁p¯ ✓), we may define ¯↵i = k˜uik◁p¯ ✓ such that Pi ¯↵i = 1. A.2 Proof of Theorem 1

Proof. From the definition of G(w↪ ✓; λ), the step (S4) of Algorithm 1 and the assumption that f (w) is the L-smooth function, we have

where

For simplicity, let us now denote x(t) = [w(t) ; ✓(t) ] 2 Rd+1 as the concatenation of w(t) and ✓(t) . We define ¯ V = [¯ ✓↪ ▷▷▷↪ ¯ ✓] 2 R¯l . Similarly, we denote ¯X = [ ¯U; ¯ V ] 2 R(p+1)⇥¯l and X(t) = [U (t) ; V (t) ] 2 R(p+1)⇥t . By writing G(x(t) ; λ) = G(w(t) ↪ ✓(t) ; λ), the preceding inequality can be equivalently written as

Let X c := ¯ X ∩ X (t-1) . Assume X c 6= ;. From the update rule of ¶✓(t) ↪ v(t) ♦ in (S2) we know the following inequality holds for any x 2 X c :

Since Px2X (t-1) ¯↵x◁(1 - ⇠) = 1, from the optimality of ↵(t-1) (see the step (S4)) we can derive that

Note that ↵(t-1) x = 0 for x ◁2 X (t-1) and ¯↵x = 0 for x ◁2 ¯ X . Therefore

where the inequality follows (12). Combining the preceding inequality with (8) we obtain

where the last inequality follows Pu2¯ U∩U (t-1) ¯↵2u ≥ (Pu2 ¯ U∩U (t-1) ¯↵u)2 ◁¯l. By combining the above with (11) we get

Let us choose ⌘ = ⇠⇣  1 in the above inequality with ⇣ := min n ⇢(s+¯ s) ¯ β 4¯lLr2 ↪ 12 o ▷ Then we have

Let us denote ✏t := G(x(t) ; λ) - G(¯x; λ). Applying this inequality recursively we obtain ✏t  ✏0 (1 - ⇣)t . Using the inequality 1 - x  exp(-x) and rearranging we get that ✏t  ✏0 exp(-⇣t). When t ≥ 1 ⇣ ln ✏0 ✏ , it can be guaranteed that ✏t  ✏. The desired result follows directly from

Acknowledgments

Xiao-Tong Yuan was supported partially by the National Natural Science Foundation of China under Grant 61402232, 61522308, and partially by the Natural Science Foundation of Jiangsu Province of China under Grant BK20141003. Qingshan Liu was supported partially by National Natural Science Foundation of China under Grant 61532009.