b

DiscoverSearch
About
A Safe Screening Rule for Sparse Logistic Regression
2013·arXiv
Abstract
Abstract

The  ℓ1-regularized logistic regression (or sparse logistic regression) is a widely used method for simultaneous classification and feature selection. Although many recent efforts have been devoted to its efficient implementation, its application to high dimensional data still poses significant challenges. In this paper, we present a fast and effective sparse logistic regression screening rule (Slores) to identify the “0” components in the solution vector, which may lead to a substantial reduction in the number of features to be entered to the optimization. An appealing feature of Slores is that the data set needs to be scanned only once to run the screening and its computational cost is negligible compared to that of solving the sparse logistic regression problem. Moreover, Slores is independent of solvers for sparse logistic regression, thus Slores can be integrated with any existing solver to improve the efficiency. We have evaluated Slores using high-dimensional data sets from different applications. Extensive experimental results demonstrate that Slores outperforms the existing state-of-the-art screening rules and the efficiency of solving sparse logistic regression is improved by one magnitude in general.

Logistic regression (LR) is a popular and well established classification method that has been widely used in many domains such as machine learning [5, 8], text mining [4, 9], image processing [10, 17], bioinformatics [1, 15, 22, 30, 31], medical and social sciences [2, 19] etc. When the number of feature variables is large compared to the number of training samples, logistic regression is prone to over-fitting. To reduce over-fitting, regularization has been shown to be a promising approach. Typical examples include  ℓ2and  ℓ1regularization. Although  ℓ1regularized LR is more challenging to solve compared to  ℓ2regularized LR, it has received much attention in the last few years and the interest in it is growing [23, 27, 31] due to the increasing prevalence of high-dimensional data. The most appealing property of  ℓ1regularized LR is the sparsity of the resulting models, which is equivalent to feature selection.

In the past few years, many algorithms have been proposed to efficiently solve the  ℓ1regularized LR [6, 14, 13, 20]. However, for large-scale problems, solving the  ℓ1regularized LR with higher accuracy remains challenging. One promising solution is by “screening”, that is, we first identify the “inactive” features, which have 0 coefficients in the solution and then discard them from the optimization. This would result in a reduced feature matrix and substantial savings in computational cost and memory size. In [7], El Ghaoui et al. proposed novel screening rules, called “SAFE”, to accelerate the optimization for a class of  ℓ1regularized problems, including LASSO [25],  ℓ1regularized LR and  ℓ1regularized support vector machines. Inspired by SAFE, Tibshirani et al. [24] proposed “strong rules” for a large class of  ℓ1regularized problems, including LASSO, elastic net,  ℓ1regularized LR and more general convex problems. In [29, 28], Xiang et al. proposed “DOME” rules to further improve SAFE rules for LASSO based on the observation that SAFE rules can be understood as a special case of the general “sphere test”. Although both strong rules and the sphere tests are more effective in discarding features than SAFE for solving LASSO, it is worthwhile to mention that strong rules may mistakenly discard features that have non-zero coefficients in the solution and the sphere tests are not easy to be generalized to handle the  ℓ1regularized LR. To the best of our knowledge, the SAFE rule is the only screening test for the  ℓ1regularized LR that is “safe”, that is, it only discards features that are guaranteed to be absent from the resulting models.

image

Figure 1: Comparison of Slores, strong rule and SAFE on the prostate cancer data set.

In this paper, we develop novel screening rules, called “Slores”, for the  ℓ1regularized LR. The proposed screening tests detect inactive features by estimating an upper bound of the inner product between each feature vector and the “dual optimal solution” of the  ℓ1regularized LR, which is unknown. The more accurate the estimation is, the more inactive features can be detected. An accurate estimation of such an upper bound turns out to be quite challenging. Indeed most of the key ideas/insights behind existing “safe” screening rules for LASSO heavily rely on the least square loss, which are not applicable for the  ℓ1regularized LR case due to the presence of the logistic loss. To this end, we propose a novel framework to accurately estimate an upper bound. Our key technical contribution is to formulate the estimation of an upper bound of the inner product as a constrained convex optimization problem and show that it admits a closed form solution. Therefore, the

estimation of the inner product can be computed efficiently. Our extensive experiments have shown that Slores discards far more features than SAFE yet requires much less computational efforts. In contrast with strong rules, Slores is “safe”, i.e., it never discards features which have non-zero coefficients in the solution. To illustrate the effectiveness of Slores, we compare Slores, strong rule and SAFE on a data set of prostate cancer along a sequence of 86 parameters equally spaced on the  λ/λmaxscale from 0.1 to 0.95, where  λis the parameter for the  ℓ1penalty and  λmaxis the smallest tuning parameter [12] such that the solution of the ℓ1regularized LR is 0 [please refer to Eq. (1)]. The data matrix contains 132 patients with 15154 features. To measure the performance of different screening rules, we compute the rejection ratio which is the ratio between the number of features discarded by screening rules and the number of features with 0 coefficients in the solution. Therefore, the larger the rejection ratio is, the more effective the screening rule is. The results are shown in Fig. 1. Clearly, Slores discards far more features than SAFE especially when  λ/λmaxis large while the strong rule is not applicable when  λ/λmax ≤ 0.5. We present more experimental results and discussions to demonstrate the effectiveness of Slores in Section 6.

In this section, we briefly review the basics of the  ℓ1regularized LR and then motivate the general screening rules via the KKT conditions. Suppose we are given a set of training samples  {xi}mi=1and the associate labels  b ∈ ℜm, where  xi ∈ ℜpand  bi ∈ {1, −1}for all  i ∈ {1, . . . , m}. The  ℓ1regularized logistic regression is:

image

where  β ∈ ℜpand  c ∈ ℜare the model parameters to be estimated, ¯xi = bixi, and  λ >0 is the tuning parameter. Let the data matrix be  X ∈ ℜm×pwith the  ithrow being ¯xiand the  jthcolumn being ¯xj.

Let  C = {θ ∈ ℜm:  θi ∈(0, 1), i = 1, . . . , m} and f(y) = y log(y) + (1  − y) log(1  − y) for  y ∈(0, 1). The dual problem of (LRPλ) (please refer to the supplement) is given by

image

To simplify notations, we denote the feasible set of problem (LRDλ) as  Fλ, and let (β∗λ, c∗λ) and  θ∗λbe the optimal solutions of problems (LRPλ) and (LRDλ) respectively. In [12], the authors have shown that for some special choice of the tuning parameter  λ, both of (LRPλ) and (LRDλ) have closed form solutions. In fact, let  P = {i : bi= 1}, N = {i : bi = −1}, and  m+and  m−be the cardinalities of P and N respectively. We define

image

where

image

([·]idenotes the  ithcomponent of a vector.) Then, it is known [12] that  β∗λ= 0 and  θ∗λ=  θ∗λmaxwhenever λ ≥ λmax. When  λ ∈(0, λmax], it is known that (LRDλ) has a unique optimal solution. (For completeness, we include the proof in the supplement.) We can now write the KKT conditions of problems (LRPλ) and (LRDλ) as

image

In view of Eq. (3), we can see that

image

In other words, if  |⟨θ∗λ, ¯xj⟩ < mλ, then the KKT conditions imply that the coefficient of ¯xjin the solution β∗λis 0 and thus the  jthfeature can be safely removed from the optimization of (LRPλ). However, for the general case in which  λ < λmax, (R1) is not applicable since it assumes the knowledge of  θ∗λ. Although it is unknown, we can still estimate a region  Aλwhich contains  θ∗λ. As a result, if maxθ∈A |⟨θ, ¯xj⟩| < mλ, we can also conclude that [β∗λ]j= 0 by (R1). In other words, (R1) can be relaxed as

image

In this paper, (R1′) serves as the foundation for constructing our screening rules, Slores. From (R1′), it is easy to see that screening rules with smaller  T(θ∗λ, ¯xj) are more aggressive in discarding features. To give a tight estimation of  T(θ∗λ, ¯xj), we need to restrict the region  Aλwhich includes  θ∗λas small as possible. In Section 3, we show that the estimation of the upper bound  T(θ∗λ, ¯xj) can be obtained via solving a convex optimization problem. We show in Section 4 that the convex optimization problem admits a closed form solution and derive Slores in Section 5 based on (R1′).

image

In this section, we present a novel framework to estimate an upper bound  T(θ∗λ, ¯xj) of  |⟨θ∗λ, ¯xj⟩|. In the subsequent development, we assume a parameter  λ0and the corresponding dual optimal  θ∗λ0are given. In our Slores rule to be presented in Section 5, we set  λ0and  θ∗λ0to be  λmaxand  θ∗λmaxgiven in Eqs. (1) and (2). We formulate the estimation of  T(θ∗λ, ¯xj) as a constrained convex optimization problem in this section, which will be shown to admit a closed form solution in Section 4.

For the dual function  g(θ), it follows that [∇g(θ)]i = 1mlog( θi1−θi), [∇2g(θ)]i,i = 1m 1θi(1−θi) ≥ 4m.Since ∇2g(θ) is a diagonal matrix, it follows that  ∇2g(θ) ⪰ 4mI, where I is the identity matrix. Thus,  g(θ) is strongly convex with modulus  µ= 4m[18]. Rigorously, we have the following lemma.

Lemma 1. Let  λ >0 and  θ1, θ2 ∈ Fλ, then

image

Given  λ ∈(0, λ0], it is easy to see that both of  θ∗λand  θ∗λ0belong to  Fλ0. Therefore, Lemma 1 can be a useful tool to bound  θ∗λwith the knowledge of  θ∗λ0. In fact, we have the following theorem.

Theorem 2. Let  λmax ≥ λ0 > λ >0, then the following holds:

image

Proof. a). It is easy to see that  Fλ ⊆ Fλ0, θ∗λ ∈ Fλand  θ∗λ0 ∈ Fλ0. Therefore, both of  θ∗λ0and  θ∗λbelong to the set  Fλ0. By Lemma 1, we have

image

Therefore, we can see that  θλ ∈ Fλand thus

image

Then the inequality in (6) becomes

image

On the other hand, by noting that (LRDλ) is feasible, we can see that the Slater’s conditions holds and thus the KKT conditions [21] lead to:

image

where  η+, η− ∈ ℜp+, γ ∈ ℜand  NC(θ∗λ) is the normal cone of C at  θ∗λ[21]. Because  θ∗λ ∈ Cand C is an open set,  θ∗λis an interior point of C and thus  NC(θ∗λ) =  ∅[21]. Therefore, Eq. (8) becomes:

image

Let  I+λ0=  {j : ⟨θ∗λ0, ¯xj⟩ = mλ0, j= 1, . . . , p}, I−λ0=  {j′ : ⟨θ∗λ0, ¯xj′⟩ = −mλ0, j= 1, . . . , p} and  Iλ0= I+λ0 ∪ I−λ0. We can see that  I+λ0 ∩ I−λ0=  ∅. By the complementary slackness condition, if  k /∈ Iλ0, we have η+k=  η−k= 0. Therefore,

image

Similarly, we have

image

Recall that to make our screening rules more aggressive in discarding features, we need to get a tight upper bound  T(θ∗λ, ¯xj) of  |⟨θ∗λ, ¯xj⟩|[please see (R1′)]. Thus, it is desirable to further restrict the possible region Aλof  θ∗λ. Clearly, we can see that

image

since  θ∗λis feasible for problem (LRDλ). On the other hand, we call the set  Iλ0defined in the proof of Theorem 2 the “active set” of  θ∗λ0. In fact, we have the following lemma for the active set.

Lemma 3. Given the optimal solution  θ∗λof problem (LRDλ), the active set  Iλ = {j : |⟨θ∗λ, ¯xj⟩| = mλ, j= 1, . . . , p} is not empty if  λ ∈(0, λmax].

Since  λ0 ∈(0, λmax], we can see that  Iλ0is not empty by Lemma 3. We pick  j0 ∈ Iλ0and set

image

As a result, Theorem 2, Eq. (11) and (13) imply that  θ∗λis contained in the following set:

image

is smaller than  mλ, we can conclude that [β∗λ]j= 0 and ¯xjcan be discarded from the optimization of (LRPλ). Notice that, we replace the notations  Aλand  T(θ∗λ, ¯xj) with  T(θ∗λ, ¯xj; θ∗λ0) and  Aλλ0to emphasize their dependence on  θ∗λ0. Clearly, as long as we can solve for  T(θ∗λ, ¯xj; θ∗λ0), (R1′) would be an applicable screening rule to discard features which have 0 coefficients in  β∗λ. We give a closed form solution of problem (42) in the next section.

In this section, we show how to solve the convex optimization problem (42) based on the standard Lagrangian multiplier method. We first transform problem (42) into a pair of convex minimization problem (UBP′) via Eq. (15) and then show that the strong duality holds for (UBP′) in Lemma 6. The strong duality guarantees the applicability of the Lagrangian multiplier method. We then give the closed form solution of (UBP′) in Theorem 8. After we solve problem (UBP′), it is straightforward to compute the solution of problem (42) via Eq. (15).

image

of the space spanned by b. In fact, we have the following theorem.

Theorem 4. Let  λmax ≥ λ0 > λ >0, and assume  θ∗λ0is known. For  j ∈ {1, . . . , p}, if  P¯xj= 0, then T(θ∗λ, ¯xj; θ∗λ0) = 0.

Because of (R1′), we immediately have the following corollary.

Corollary 5. Let  λ ∈(0, λmax) and  j ∈ {1, . . . , p}. If  P¯xj= 0, then [β∗λ]j= 0.

For the general case in which  P¯xj ̸= 0, let

image

Clearly, we have

image

To make use of the standard Lagrangian multiplier method, we transform problem (UBPs) to the following minimization problem:

image

by noting that maxθ∈Aλλ0 ⟨θ, ξ¯xj⟩ = −minθ∈Aλλ0 ⟨θ, −ξ¯xj⟩.

Lemma 6. Let  λmax ≥ λ0 > λ >0 and assume  θ∗λ0is known. The strong duality holds for problem (UBP′). Moreover, problem (UBP′) admits an optimal solution in  Aλλ0.

Because the strong duality holds for problem (UBP′) by Lemma 6, the Lagrangian multiplier method is applicable for (UBP′). In general, we need to first solve the dual problem and then recover the optimal solution of the primal problem via KKT conditions. Recall that r and ¯x∗are defined by Eq. (10) and (12) respectively. Lemma 7 derives the dual problems of (UBP′) for different cases.

Lemma 7. Let  λmax ≥ λ0 > λ >0 and assume  θ∗λ0is known. For  j ∈ {1, . . . , p}and  P¯xj ̸= 0, let ¯x = −ξ¯xj. Denote

image

image

We can now solve problem (UBP′) in the following theorem.

Theorem 8. Let  λmax ≥ λ0 > λ >0, d = m(λ0−λ)r∥P¯x∗∥2and assume  θ∗λ0is known. For  j ∈ {1, . . . , p}and P¯xj ̸= 0, let ¯x = −ξ¯xj.

image

Notice that, although the dual problems of (UBP′) in Lemma 7 are different, the resulting upper bound Tξ(θ∗λ, ¯xj; θ∗λ0) can be given by Theorem 8 in a uniform way. The tricky part is how to deal with the extremal cases in which ⟨P¯x,P¯x∗⟩∥P¯x∥2∥P¯x∗∥2 ∈ {−1,+1}. To avoid the lengthy discussion of Theorem 8, we omit the proof in the main text and include the details in the supplement.

Using (R1′), we are now ready to construct the screening rules for the  ℓ1Regularized Logistic Regression. By Corollary 5, we can see that the orthogonality between the  jthfeature and the response vector b implies the absence of ¯xjfrom the resulting model. For the general case in which  P¯xj ̸= 0, (R1′) implies that if T(θ∗λ, ¯xj; θ∗λ0) = max{T+(θ∗λ, ¯xj; θ∗λ0), T−(θ∗λ, ¯xj; θ∗λ0)} < mλ,then the  jthfeature can be discarded from the optimization of (LRPλ). Notice that, letting  ξ = ±1, T+(θ∗λ, ¯xj; θ∗λ0) and  T−(θ∗λ, ¯xj; θ∗λ0) have been solved by Theorem 8. Rigorously, we have the following theorem.

Theorem 9 (Slores). Let  λ0 > λ >0 and assume  θ∗λ0is known.

1. If  λ ≥ λmax, then  β∗λ= 0;

2. If  λmax ≥ λ0 > λ >0 and either of the following holds:

image

Notice that, the output R of Slores is the indices of the features that need to be entered to the optimization. As a result, suppose the output of Algorithm 1 is  R = {j1, . . . , jk}, we can substitute the full matrix X in problem (LRPλ) with the submatrix  XR= (¯xj1, . . . , ¯xjk) and just solve for [β∗λ]Rand  c∗λ.

On the other hand, Algorithm 1 implies that Slores needs five inputs. Since X and b come with the data and  λis chosen by the user, we only need to specify  θ∗λ0and  λ0. In other words, we need to provide Slores with an dual optimal solution of problem (LRDλ) for an arbitrary parameter. A natural choice is by setting  λ0 = λmaxand  θ∗λ0=  θ∗λmaxgiven in Eq. (1) and Eq. (2).

We evaluate our screening rules using the newgroup data set [12] and Yahoo web pages data sets [26]. The newgroup data set is cultured from the data by Koh et al. [12]. The Yahoo data sets include 11 top-level categories, each of which is further divided into a set of subcategories. In our experiment we construct five balanced binary classification datasets from the topics of Computers, Education, Health, Recreation, and Science. For each topic, we choose samples from one subcategory as the positive class and randomly sample an equal number of samples from the rest of subcategories as the negative class. The statistics of the data sets are given in Table 1.

image

Table 2: Running time (in seconds) of Slores, strong

We compare the performance of Slores and the strong rule which achieves state-of-the-art performance for  ℓ1regularized LR. We do not include SAFE because it is less effective in discarding features than strong rules and requires much higher computational time [24]. Fig. 1 has shown the performance of Slores, strong rule and SAFE. We compare the efficiency of the three screening rules on the same prostate cancer data set in Table 2. All of the screening rules are tested along a sequence of 86 parameter values equally spaced on the  λ/λmaxscale from 0.1 to 0.95. We repeat the procedure 100 times and during each time we undersample 80% of the data. We report the total running time of the three screening rules over the 86 values of  λ/λmaxin Table 2. For reference, we also report the total

running time of the solver1. We observe that the running time of Slores and strong rule is negligible compared to that of the solver. However, SAFE takes much longer time even than the solver.

In Section 6.1, we evaluate the performance of Slores and strong rule. Recall that we use the rejection ratio, i.e., the ratio between the number of features discarded by the screening rules and the number of features with 0 coefficients in the solution, to measure the performance of screening rules. Note that, because no features with non-zero coefficients in the solution would be mistakenly discarded by Slores, its rejection ratio is no larger than one. We then compare the efficiency of Slores and strong rule in Section 6.2.

The experiment settings are as follows. For each data set, we undersample 80% of the date and run Slores and strong rules along a sequence of 86 parameter values equally spaced on the  λ/λmaxscale from 0.1 to 0.95. We repeat the procedure 100 times and report the average performance and running time at each of the 86 values of  λ/λmax. Slores, strong rules and SAFE are all implemented in Matlab. All of the experiments are carried out on a Intel(R) (i7-2600) 3.4Ghz processor.

6.1 Comparison of Performance

In this experiment, we evaluate the performance of the Slores and the strong rule via the rejection ratio. Fig. 2 shows the rejection ratio of Slores and strong rule on six real data sets. When  λ/λmax > 0.5, we can see that both Slores and strong rule are able to identify almost 100% of the inactive features, i.e., features with 0 coefficients in the solution vector. However, when  λ/λmax ≤ 0.5, strong rule can not detect the inactive features. In contrast, we observe that Slores exhibits much stronger capability in discarding inactive features for small  λ, even when  λ/λmaxis close to 0.1. Taking the data point at which  λ/λmax= 0.1 for example, Slores discards about 99% inactive features for the newsgroup data set. For the other data sets, more than 80% inactive features are identified by Slores. Therefore, in terms of rejection ratio, Slores significantly outperforms the strong rule. It is also worthwhile to mention that the discarded features by Slores are guaranteed to have 0 coefficients in the solution. But strong rule may mistakenly discard features which have non-zero coefficients in the solution.

image

Figure 2: Comparison of the performance of Slores and strong rules on six real data sets.

image

Figure 3: Comparison of the efficiency of Slores and strong rule on six real data sets.

6.2 Comparison of Efficiency

We compare efficiency of Slores and the strong rule in this experiment. The data sets for evaluating the rules are the same as Section 6.1. The running time of the screening rules reported in Fig. 3 includes the computational cost of the rules themselves and that of the solver after screening. We plot the running time of the screening rules against that of the solver without screening. As indicated by Fig. 2, when  λ/λmax > 0.5, Slores and strong rule discards almost 100% of the inactive features. As a result, the size of the feature matrix involved in the optimization of problem (LRPλ) is greatly reduced. From Fig. 3, we can observe that the efficiency is improved by about one magnitude on average compared to that of the solver without screening. However, when  λ/λmax < 0.5, strong rule can not identify any inactive features and thus the running time is almost the same as that of the solver without screening. In contrast, Slores is still able to identify more than 80% of the inactive features for the data sets cultured from the Yahoo web pages data sets and thus the efficiency is improved by roughly 5 times. For the newgroup data set, about 99% inactive features are identified by Slores which leads to about 10 times savings in running time. These results demonstrate the power of the proposed Slores rule in improving the efficiency of solving the  ℓ1regularized LR.

In this paper, we propose novel screening rules to effectively discard features for  ℓ1regularized LR. Extensive numerical experiments on real data demonstrate that Slores outperforms the existing state-of-the-art screening rules. We plan to extend the framework of Slores to more general sparse formulations, including convex ones, like group Lasso, fused Lasso,  ℓ1regularized SVM, and non-convex ones, like  ℓpregularized problems where 0 < p < 1.

[1] M. Asgary, S. Jahandideh, P. Abdolmaleki, and A. Kazemnejad. Analysis and identification of  β-turn types using multinomial logistic regression and artificial neural network. Bioinformatics, 23(23):3125– 3130, 2007. URL http://dblp.uni-trier.de/db/journals/bioinformatics/bioinformatics23. html#AsgaryJAK07.

[2] C. Boyd, M. Tolson, and W. Copes. Evaluating trauma care: The TRISS method, trauma score and the injury severity score. Journal of Trauma, 27:370–378, 1987.

[3] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

[4] Jack R. Brzezinski and George J. Knafl. Logistic regression modeling for context-based classification. In DEXA Workshop, pages 755–759, 1999. URL http://dblp.uni-trier.de/db/conf/dexaw/dexaw99. html#BrzezinskiK99.

[5] K. Chaudhuri and C. Monteleoni. Privacy-preserving logistic regression. In NIPS, 2008.

[6] B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani. Least angle regression. Ann. Statist., 32:407–499, 2004.

[7] L. El Ghaoui, V. Viallon, and T. Rabbani. Safe feature elimination for the lasso and sparse supervised learning problems. arXiv:1009.4219v2.

[8] J. Friedman, T. Hastie, and R. Tibshirani. Additive logistic regression: a statistical view of boosting. The Annals of Statistics, 38(2), 2000.

[9] A. Genkin, D. Lewis, and D. Madigan. Large-scale bayesian logistic regression for text categorization. Technometrics, 49:291–304(14), 2007. doi: doi:10.1198/004017007000000245. URL http: //www.ingentaconnect.com/content/asa/tech/2007/00000049/00000003/art00007.

[10] S. Gould, J. Rodgers, D. Cohen, G. Elidan, and D. Koller. Multi-class segmentation with relative location prior. International Journal of Computer Vision, 80(3):300–316, 2008. URL http://dblp. uni-trier.de/db/journals/ijcv/ijcv80.html#GouldRCEK08.

[11] O. G¨uler. Foundations of Optimization. Springer, 2010.

[12] K. Koh, S. J. Kim, and S. Boyd. An interior-point method for large scale l1-regularized logistic regression. J. Mach. Learn. Res., 8:1519–1555, 2007.

[13] B. Krishnapuram, L. Carin, M. Figueiredo, and A. Hartemink. Sparse multinomial logistic regression: Fast algorithms and generalization bounds. IEEE Trans. Pattern Anal. Mach. Intell., 27:957–968, 2005.

[14] S. Lee, H. Lee, P. Abbeel, and A. Ng. Efficient l1 regularized logistic regression. In In AAAI-06, 2006.

[15] J. Liao and K. Chin. Logistic regression for disease classification using microarray data: model selection in a large p and small n case. Bioinformatics, 23(15):1945–1951, 2007. URL http://dblp.uni-trier. de/db/journals/bioinformatics/bioinformatics23.html#LiaoC07.

[16] J. Liu, S. Ji, and J. Ye. SLEP: Sparse Learning with Efficient Projections. Arizona State University, 2009. URL http://www.public.asu.edu/~jye02/Software/SLEP.

[17] S. Martins, L. Sousa, and J. Martins. Additive logistic regression applied to retina modelling. In ICIP (3), pages 309–312. IEEE, 2007. URL http://dblp.uni-trier.de/db/conf/icip/icip2007-3.html# MartinsSM07.

[18] Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Springer, 2004.

[19] S. Palei and S. Das. Logistic regression model for prediction of roof fall risks in bord and pillar workings in coal mines: An approach. Safety Science, 47:88–96, 2009.

[20] M. Park and T. Hastie.  ℓ1regularized path algorithm for generalized linear models. J. R. Statist. Soc. B, 69:659–677, 2007.

[21] A. Ruszczy´nski. Nonlinear Optimization. Princeton university Press, 2006.

[22] M. Sartor, G. Leikauf, and M. Medvedovic. LRpath: a logistic regression approach for identifying enriched biological groups in gene expression data. Bioinformatics, 25(2):211–217, 2009. URL http: //dblp.uni-trier.de/db/journals/bioinformatics/bioinformatics25.html#SartorLM09.

[23] D. Sun, T. Erp, P. Thompson, C. Bearden, M. Daley, L. Kushan, M. Hardt, K. Nuechterlein, A. Toga, and T. Cannon. Elucidating a magnetic resonance imaging-based neuroanatomic biomarker for psychosis: classification analysis using probabilistic brain atlas and machine learning algorithms. Biological Psychiatry, 66:1055–1–60, 2009.

[24] R. Tibshirani, J. Bien, J. Friedman, T. Hastie, N. Simon, J. Taylor, and R. Tibshirani. Strong rules for discarding predictors in lasso-type problems. J. R. Statist. Soc. B, 74:245–266, 2012.

[25] Robert Tibshirani. Regression shringkage and selection via the lasso. J. R. Statist. Soc. B, 58:267–288, 1996.

[26] Naonori Ueda and Kazumi Saito. Parametric mixture models for multi-labeled text. Advances in neural information processing systems, 15:721–728, 2002.

[27] T. T. Wu, Y. F. Chen, T. Hastie, E. Sobel, and K. Lange. Genome-wide association analysis by lasso penalized logistic regression. Bioinformatics, 25:714–721, 2009.

[28] Z. J. Xiang and P. J. Ramadge. Fast lasso screening tests based on correlations. In IEEE ICASSP, 2012.

[29] Z. J. Xiang, H. Xu, and P. J. Ramadge. Learning sparse representation of high dimensional data on large scale dictionaries. In NIPS, 2011.

[30] J. Zhu and T. Hastie. Kernel logistic regression and the import vector machine. In Thomas G. Dietterich, Suzanna Becker, and Zoubin Ghahramani, editors, NIPS, pages 1081–1088. MIT Press, 2001. URL http://dblp.uni-trier.de/db/conf/nips/nips2001.html#ZhuH01.

[31] J. Zhu and T. Hastie. Classification of gene microarrays by penalized logistic regression. Biostatistics, 5:427–443, 2004.

In this appendix, we will provide detailed proofs of the theorems, lemmas and corollaries in the main text.

Suppose we are given a set of training samples  {xi}mi=1and the associate labels  b ∈ ℜm, where  xi ∈ ℜpand bi ∈ {1, −1}for all  i ∈ {1, . . . , m}. The logistic regression problem takes the form as follows:

image

where  β ∈ ℜpand  c ∈ ℜare the model parameters to be estimated, ¯xi = bixiand  λ >0. Let ¯X denote the data matrix whose rows consist of ¯xi. Denote the columns of ¯X as ¯xj, j ∈ {1, . . . , p}.

A.1 Dual Formulation

By introducing the slack variables  qi = 1m(−⟨β, ¯xi⟩ − bic) for all  i ∈ {1, . . . , m}, problem (LRPλ) can be formulated as:

image

The Lagrangian is

image

In order to find the dual function, we need to solve the following subproblems:

image

Consider  f1(q). It is easy to see

image

By setting [∇f1(q)]i= 0, we get

image

Clearly, we can see that  θi ∈(0, 1) for all  i ∈ {1, . . . , m}. Therefore,

image

Consider  f2(β) and let  β′= argminβ f2(β). The optimality condition is

image

It is easy to see that

image

and thus

image

Moreover, it follows that

image

For  f3(c), we can see that

image

Therefore, we have

image

since otherwise infc f3(c) =  −∞and the dual problem is infeasible. Clearly, minc f3(c) = 0. All together, the dual problem is

image

where  C = {θ ∈ ℜm:  θi ∈(0, 1), i = 1, . . . , m}.

In this section, we prove that problem (LRDλ) has a unique optimal solution for all  λ >0. Therefore, in Lemma A, we first show that problem (LRDλ) is feasible for all  λ >0. Then Lemma B confirms the existence of the dual optimal solution  θ∗λ.

image

Proof. 1. When  λ ≥ λmax, the feasibility of (LRDλ) is trivial because of the existence of  θ∗λmax. We focus on the case in which  λ ∈(0, λmax] below.

Recall that [12]  λmaxis the smallest tuning parameter such that  β∗λ= 0 and  θ∗λ=  θ∗λmaxwhenever λ ≥ λmax. For convenience, we rewrite the definition of  λmaxand  θ∗λmaxas follows.

image

Clearly, we have  θ∗λmax ∈ Fλmax, i.e.,  θ∗λmax ∈ C, ∥ ¯XT θ∗λmax∥∞ ≤ mλmaxand  ⟨θ∗λmax, b⟩= 0. Let us define:

image

2. The constraints of (LRDλ) are all affine. Therefore, the Slater’s condition reduces to the feasibility of (LRDλ) [3]. When  λ ≥ λmax, θ∗λmaxis clearly a feasible solution of (LRDλ). When  λ ∈(0, λmax], we have shown the feasibility of (LRDλ) in part 1. Therefore, the Slater’s condition always holds for (LRDλ) in which  λ >0.

image

Lemma 11. B Given  λ ∈(0, λmax], problem (LRDλ) has a unique optimal solution, i.e., there exists a unique  θ∗λ ∈ Fλsuch that  g(θ) achieves its minimum over  Fλat  θ∗λ.

Proof. Let �C:=  {θ ∈ ℜm:  θi ∈[0, 1], i = 1, . . . , m} and

image

By L′Hˆopital′s rule, it is easy to see that limy↓0 f(y) = limy↑1 f(y) = 0. Therefore, let

image

and

image

image

Because of Lemma A, we know that  Fλ ̸= ∅and thus �Fλ ̸= ∅either. Therefore, problem (LRD′λ) is feasible. By noting that the constraints of problem (LRD′λ) are all linear, the Slater’s condition is satisfied. Hence, there exists a set of Lagrangian multipliers  η+, η− ∈ ℜp+, ξ+, ξ− ∈ ℜm+and  γ ∈ ℜsuch that

image

We can see that if there is an  i0such that [θ∗λ]i0 ∈ {0, 1}, i.e.,  θ∗λ /∈ Fλ, Eq. (24) does not hold since |[∇�g(θ∗λ)]i0| = ∞. Therefore, we can conclude that  θ∗λ ∈ Fλ. Moreover, it is easy to see that  θ∗λ= argminθ∈ �Fλ �g(θ) = argminθ∈Fλ g(θ), i.e.  θ∗λis a minimum of  g(θ) over  Fλ. The uniqueness of  θ∗λis due to the strict convexity of  g(θ) (strong convexity implies strict convexity), which completes the proof.

Proof. Recall that the domain of g is  C = {θ ∈ ℜm: [θ]i ∈(0, 1), i = 1, . . . , m}.

a. It is easy to see that

image

Therefore, g is a strong convex function with convexity parameter  µ= 4m[18]. The claim then follows directly from the definition of strong convex functions.

b. If  θ1 ̸= θ2, then there exists at least one  i′ ∈ {1, . . . , m}such that [θ1]i′ ̸= [θ2]i′. Moreover, at most one of [θ1]i′and [θ2]i′can be 12. Without loss of generality, assume [θ1]i′ ̸= 12.

For  t ∈(0, 1), let  θ(t) =  tθ2+ (1  − t)θ1. Since [θ1]i′ ̸= 12, we can find  t′ ∈(0, 1) such that [θ(t′)]i′ ̸= 12. Therefore, we can see that

image

image

image

Proof. According to the definition of  λmaxin Eq. (1), there must be  j0 ∈ {1, . . . , p}such that  λmax=

image

For  λ ∈(0, λmax), we prove the statement by contradiction. Suppose  Iλis empty, then the KKT condition for (LRDλ) at  θ∗λcan be written as:

image

where  η+, η− ∈ ℜp+, γ ∈ ℜand  NC(θ∗λ) is the normal cone of C at  θ∗λ. Because  θ∗λ ∈ Cand C is an open set, θ∗λis an interior point of C and thus  NC(θ∗λ) =  ∅. Therefore, the above equation becomes:

image

Moreover, by the complementary slackness condition [3], we have  η+j=  η−j= 0 for j = 1, . . . , p since  Iλis empty. Then, Eq. (39) becomes:

image

By the similar argument, the KKT condition for (LRDλmax) at  θ∗λmaxis:

image

where ¯η+, ¯η− ∈ ℜp+and  γ′ ∈ ℜ.

Since  Iλ = ∅, we can see that  |⟨θ∗λ, ¯xj⟩| < mλ < mλmaxfor all  j ∈ {1, . . . , m}. Therefore,  θ∗λalso satisfies Eq. (41) by setting  η+= ¯η+, η−= ¯η−and  γ = γ′without violating the complementary slackness conditions. As a result,  θ∗λis an optimal solution of problem (LRDλmax) as well.

Moreover, it is easy to see that  θ∗λ ̸= θ∗λmaxbecause  |⟨θ∗λ, ¯xj0⟩| < mλ < mλmax = |⟨θ∗λmax, ¯xj0⟩|. Conse- quently, (LRDλmax) has at least two distinct optimal solutions, which contradicts with Lemma B. Therefore, Iλmust be an nonempty set. Because  λis arbitrary in (0, λmax), the proof is complete.

image

Proof. Recall that we need to solve the following optimization proble:

image

i.e.,  θbelongs to the orthogonal complement of the space spanned by b. As a result,  θ = Pθand

image

image

image

To show that the Slater’s condition holds, we need to seek a point  θ′such that

image

empty. Let  j0 ∈ Iλ0, we can see that

image

However, because  θ∗λ ∈ Fλ, we have | ¯XT θ∗λ|∞ ≤ mλ,

image

As a result, the Slater’s condition holds for (UBP′) which implies the strong duality of (UBP′). Moreover, it is easy to see that problem (UBP′) admits optimal solution in  Aλλ0because the objective function of (UBP′) is continuous and  Aλλ0is compact.

image

Proof. The Lagrangian of (UBP′) is

L(θ; u1, u2, v) =  ⟨θ, ¯x⟩+ u12�∥θ − θ∗λ0∥22 − r2�+ u2(⟨θ, ¯x∗⟩ −2) + v⟨θ, b⟩(43) =  ⟨θ, ¯x + u2¯x∗+ vb⟩+ u12�∥θ − θ∗λ0∥22 − r2�− u2mλ2.

where  u1, u2 ≥0 and  v ∈ ℜare the Lagrangian multipliers. To derive the dual function ˆg(u1, u2, v) = minθ L(θ; u1, u2, v), we can simply set  ∇θL(θ; u1, u2, v) = 0, i.e.,

image

When  u1 ̸= 0, we set

image

to minimize  L(θ; u, v) with (u, v) fixed. By plugging Eq. (44) to Eq. (43), we can see that the dual function ˆg(u1, u2, v) is:

image

Clearly, Eq. (46) implies that  P¯xand  P¯x∗are collinear, i.e., ⟨P¯x,P¯x∗⟩∥P¯x∥2∥P¯x∗∥2 ∈ {−1, 1}. Moreover, by Eq. (47), we know that  ⟨P¯x, P¯x∗⟩ ≤0. Therefore, it is easy to see that ⟨P¯x,P¯x∗⟩∥P¯x∥2∥P¯x∗∥2=  −1, which contradicts the assumption. Hence, ¯x + u2¯x∗+  vb ̸= 0 for all  u2 ≥0 and v.

image

image

Moreover, it is easy to see that problem (52) is an unconstrained optimization problem with respect to v. Therefore, we set

image

By plugging (53) into ˆg(u1, u2, v) and noting that  U1 = {(u1, u2) :  u1 > 0, u2 ≥ 0}, problem (52) is equivalent to

image

By Lemma 6, we know that the Slater’s conditions holds for (UBP′). Therefore, the strong duality holds for (UBP′) and (UBD′). By the strong duality theorem [11], there exists  u∗1 ≥0,  u∗2 ≥0 and v∗such that ˆg(u∗1, u∗2, v∗) = maxu1≥0,u2≥0,vˆg(u1, u2, v). By Eq. (51), it is easy to see that  u∗1 >0. Therefore, ¯g(u1, u2) attains its maximum in  U1.

image

image

I.1 Proof for the Non-Collinear Case

In this section, we show that the results in Theorem 8 holds for the case in which ⟨P¯x,P¯x∗⟩∥P¯x∥2∥P¯x∗∥2 ∈ (−1,1), i.e.,  P¯xand  P¯x∗are not collinear.

Proof. As shown by part a) of Lemma 7, the dual problem of (UBP′) is equivalent to (UBD′). Since the strong duality holds by Lemma 6, we have

image

Clearly, problem (UBD′) can be solved via the following minimization problem

image

Let  u∗1and  u∗2be the optimal solution of problem (56). By part a) of Lemma 7, the existence of  u∗1 >0 and u∗2 ≥0 is guaranteed. By introducing the slack variables  s1 ≥0 and  s2 ≥0, the KKT conditions of problem (56) can be written as follows:

image

It is easy to observe that

image

m2). d ∈(0, 1] due to the fact that  λ0 > λand Eq. (68) (note  s2 ≥0).

image

Therefore, we can see that  s2 >0 and thus  u∗2= 0 due to the complementary slackness condition. By plugging  u∗2= 0 into Eq. (67), we can get  u∗1=  ∥P¯x∥2r. The result in part a) of Theorem 8 follows by noting that  Tξ(θ∗λ, ¯xj; θ∗λ0) =  −¯g(u∗1, u∗2).

a2) Suppose ⟨P¯x,P¯x∗⟩∥P¯x∥2∥P¯x∗∥2= d. If  u∗2 >0, then  s2= 0 by the complementary slackness condition. In view of Eq. (68) and m1), we can see that

image

which leads to a contradiction. Therefore  u∗2= 0 and the result in part a) of Theorem 8 follows by a similar argument as in the proof of a1).

image

which implies that  s2 <0, a contradiction. Thus, we have  u∗2 >0 and  s2= 0 by the complementary slackness condition. Eq. (68) becomes:

image

Expanding the terms in Eq. (62) yields the following quadratic equation:

image

⟨P¯x,P¯x∗⟩∥P¯x∥2∥P¯x∗∥2 ̸= −1, we can see that  P¯x∗and  P¯xare not collinear. Therefore, m1) and Eq. (62) imply that d < 1. Moreover, the assumption  λ0 > λleads to d > 0. As a result, we have (1  − d2) >0 and thus

image

Consequently, (63) has only one positive solution which can be computed by the formula in Eq. (86). The result in Eq. (85) follows by a similar argument as in the proof of a1).

I.2 Proof for the Collinear and Positive Correlated Case

We prove for the case in which ⟨P¯x,P¯x∗⟩∥P¯x∥2∥P¯x∗∥2= 1.

Proof. Because ⟨P¯x,P¯x∗⟩∥P¯x∥2∥P¯x∗∥2= 1, by part a) of Lemma 7, the dual problem of (UBP′) is given by (UBD′). Therefore, the following KKT conditions hold as well:

image

where  u∗1 >0 and  u∗2 ≥0 are the optimal solution of (UBD′), and  s1, s2 ≥0 are the slack variables. Since u∗1 >0, then  s1= 0 and Eq. (64) results in

image

By plugging Eq. (70) into Eq. (68), we have

image

Therefore, we can see that  s2 >0 and thus  u∗2= 0 due to the complementary slackness condition. By plugging  u∗2= 0 into Eq. (67), we can get  u∗1=  ∥P¯x∥2r. The result in part a) of Theorem 8 follows by noting that  Tξ(θ∗λ, ¯xj; θ∗λ0) =  −¯g(u∗1, u∗2).

image

I.3 Proof for the Collinear and Negative Correlated Case

Before we proceed to prove Theorem 8 for the case in which ⟨P¯x,P¯x∗⟩∥P¯x∥2∥P¯x∗∥2=  −1, it is worthwhile to noting the following lemma.

Lemma 12. C Let  λmax ≥ λ0 > λ >0, d = m(λ0−λ)r∥P¯x∗∥2and assume  θ∗λ0is known. Then  d ∈(0, 1].

Proof. Let ¯x :=  −ξ(−¯x∗). Clearly, we can see that

image

Moreover, since  λ0 > λ, it is easy to see that d > 0, which completes the proof.

We prove Theorem 8 for the case in which ⟨P¯x,P¯x∗⟩∥P¯x∥2∥P¯x∗∥2=  −1.

image

As shown by part b) of Lemma 7, the dual problem is given by (UBD′′). Therefore, to find

image

Let us consider the problem in (76). From problem (UBD′′), we observe that

image

By noting Eq. (74), we have

image

Suppose  u1is fixed, it is easy to see that

image

and

image

image

Otherwise, if  d ∈(0, 1), it is easy to see that

image

Moreover, we observe that

image

Therefore, Eq. (82) can simplified as:

image

By Eq. (77), we can see that

image

where

image

In fact, if we plugging Eq. (74) into Eq. (86), we have

image

Clearly, Eq. (84) and Eq. (87) give the same result, which completes the proof.


Designed for Accessibility and to further Open Science