A Safe Screening Rule for Sparse Logistic Regression

2013·arXiv

Abstract

1 Introduction

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 and regularization. Although regularized LR is more challenging to solve compared to regularized 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 regularized 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 regularized LR [6, 14, 13, 20]. However, for large-scale problems, solving the regularized 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 regularized problems, including LASSO [25], regularized LR and regularized support vector machines. Inspired by SAFE, Tibshirani et al. [24] proposed “strong rules” for a large class of regularized problems, including LASSO, elastic net, regularized 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 regularized LR. To the best of our knowledge, the SAFE rule is the only screening test for the regularized LR that is “safe”, that is, it only discards features that are guaranteed to be absent from the resulting models.

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 regularized 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 regularized 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 regularized 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 scale from 0.1 to 0.95, where is the parameter for the penalty and is the smallest tuning parameter [12] such that the solution of the regularized 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 is large while the strong rule is not applicable when 5. We present more experimental results and discussions to demonstrate the effectiveness of Slores in Section 6.

2 Basics and Motivations

In this section, we briefly review the basics of the regularized LR and then motivate the general screening rules via the KKT conditions. Suppose we are given a set of training samples and the associate labels , where and for all . The regularized logistic regression is:

where and are the model parameters to be estimated, ¯, and 0 is the tuning parameter. Let the data matrix be with the row being ¯and the column being ¯.

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

To simplify notations, we denote the feasible set of problem (LRD) as , and let () 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 = 1, and and be the cardinalities of P and N respectively. We define

where

([denotes the component of a vector.) Then, it is known [12] that = 0 and = whenever . When (0], 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

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

In other words, if , then the KKT conditions imply that the coefficient of ¯in the solution is 0 and thus the feature can be safely removed from the optimization of (LRP). However, for the general case in which , (R1) is not applicable since it assumes the knowledge of . Although it is unknown, we can still estimate a region which contains . As a result, if max, we can also conclude that [= 0 by (R1). In other words, (R1) can be relaxed as

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 ) are more aggressive in discarding features. To give a tight estimation of ), we need to restrict the region which includes as small as possible. In Section 3, we show that the estimation of the upper bound ) 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).

3 Estimating the Upper Bound via Solving a Convex Optimiza-

In this section, we present a novel framework to estimate an upper bound ) of . In the subsequent development, we assume a parameter and the corresponding dual optimal are given. In our Slores rule to be presented in Section 5, we set and to be and given in Eqs. (1) and (2). We formulate the estimation of ) 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 ), it follows that [log( )Since ) is a diagonal matrix, it follows that , where I is the identity matrix. Thus, ) is strongly convex with modulus = [18]. Rigorously, we have the following lemma.

Lemma 1. Let 0 and , then

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

Theorem 2. Let 0, then the following holds:

Proof. a). It is easy to see that and . Therefore, both of and belong to the set . By Lemma 1, we have

Therefore, we can see that and thus

Then the inequality in (6) becomes

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:

where and ) is the normal cone of C at [21]. Because and C is an open set, is an interior point of C and thus ) = [21]. Therefore, Eq. (8) becomes:

Let = = 1= = 1, . . . , p} and = . We can see that = . By the complementary slackness condition, if , we have = = 0. Therefore,

Similarly, we have

Recall that to make our screening rules more aggressive in discarding features, we need to get a tight upper bound ) of [please see (R1)]. Thus, it is desirable to further restrict the possible region of . Clearly, we can see that

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

Lemma 3. Given the optimal solution of problem (LRD), the active set = 1, . . . , p} is not empty if (0].

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

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

is smaller than , we can conclude that [= 0 and ¯can be discarded from the optimization of (LRP). Notice that, we replace the notations and ) with ) and to emphasize their dependence on . Clearly, as long as we can solve for ), (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.

4 Solving the Convex Optimization Problem (UBP)

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).

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

Theorem 4. Let 0, and assume is known. For , if = 0, then ) = 0.

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

Corollary 5. Let (0) and . If = 0, then [= 0.

For the general case in which = 0, let

Clearly, we have

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

by noting that maxmin.

Lemma 6. Let 0 and assume is known. The strong duality holds for problem (UBP). Moreover, problem (UBP) admits an optimal solution in .

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 ¯are defined by Eq. (10) and (12) respectively. Lemma 7 derives the dual problems of (UBP) for different cases.

Lemma 7. Let 0 and assume is known. For and = 0, let ¯. Denote

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

Theorem 8. Let 0, d = and assume is known. For and = 0, let ¯.

Notice that, although the dual problems of (UBP) in Lemma 7 are different, the resulting upper bound ) can be given by Theorem 8 in a uniform way. The tricky part is how to deal with the extremal cases in which +1}. To avoid the lengthy discussion of Theorem 8, we omit the proof in the main text and include the details in the supplement.

5 The proposed Slores Rule for ℓ1 Regularized Logistic Regression

Using (R1), we are now ready to construct the screening rules for the Regularized Logistic Regression. By Corollary 5, we can see that the orthogonality between the feature and the response vector b implies the absence of ¯from the resulting model. For the general case in which = 0, (R1) implies that if ) = maxthen the feature can be discarded from the optimization of (LRP). Notice that, letting ) and ) have been solved by Theorem 8. Rigorously, we have the following theorem.

Theorem 9 (Slores). Let 0 and assume is known.

1. If , then = 0;

2. If 0 and either of the following holds:

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 , we can substitute the full matrix X in problem (LRP) with the submatrix = (¯) and just solve for [and .

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 and . 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 and = given in Eq. (1) and Eq. (2).

6 Experiments

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.

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 regularized 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 scale 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 in Table 2. For reference, we also report the total

running time of the solver. 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 scale 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 . 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 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 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 is close to 0.1. Taking the data point at which = 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.

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

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 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 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 regularized LR.

7 Conclusions

In this paper, we propose novel screening rules to effectively discard features for regularized 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, regularized SVM, and non-convex ones, like regularized problems where 0 < p < 1.

References

[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. regularized 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.

Appendix

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

A Deviation of the Dual Problem of the Sparse Logistic Regression

Suppose we are given a set of training samples and the associate labels , where and for all . The logistic regression problem takes the form as follows:

where and are the model parameters to be estimated, ¯and 0. Let ¯X denote the data matrix whose rows consist of ¯. Denote the columns of ¯X as ¯.

A.1 Dual Formulation

By introducing the slack variables ) for all , problem (LRP) can be formulated as:

The Lagrangian is

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

Consider ). It is easy to see

By setting [= 0, we get

Clearly, we can see that (0, 1) for all . Therefore,

Consider ) and let = argmin). The optimality condition is

It is easy to see that

and thus

Moreover, it follows that

For ), we can see that

Therefore, we have

since otherwise inf) = and the dual problem is infeasible. Clearly, min) = 0. All together, the dual problem is

where : (0, 1), i = 1, . . . , m}.

B Proof of the Existence of the Optimal Solution of (LRDλ)

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 .

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

Recall that [12] is the smallest tuning parameter such that = 0 and = whenever . For convenience, we rewrite the definition of and as follows.

Clearly, we have , i.e., and = 0. Let us define:

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

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

Proof. Let := : [0, 1], i = 1, . . . , m} and

By LHˆopitals rule, it is easy to see that lim) = lim) = 0. Therefore, let

and

Because of Lemma A, we know that and thus 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 and such that

We can see that if there is an such that [, i.e., , Eq. (24) does not hold since . Therefore, we can conclude that . Moreover, it is easy to see that = argmin) = argmin), i.e. is a minimum of ) over . The uniqueness of is due to the strict convexity of ) (strong convexity implies strict convexity), which completes the proof.

C Proof of Lemma 1

Proof. Recall that the domain of g is : [(0, 1), i = 1, . . . , m}.

a. It is easy to see that

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

b. If , then there exists at least one such that [= [. Moreover, at most one of [and [can be . Without loss of generality, assume [.

For (0, 1), let ) = + (1 . Since [= , we can find (0, 1) such that [. Therefore, we can see that

D Proof of Lemma 3

Proof. According to the definition of in Eq. (1), there must be such that =

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

where and ) is the normal cone of C at . Because and C is an open set, is an interior point of C and thus ) = . Therefore, the above equation becomes:

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

By the similar argument, the KKT condition for (LRD) at is:

where ¯and .

Since , we can see that for all . Therefore, also satisfies Eq. (41) by setting = ¯= ¯and without violating the complementary slackness conditions. As a result, is an optimal solution of problem (LRD) as well.

Moreover, it is easy to see that because . Conse- quently, (LRD) has at least two distinct optimal solutions, which contradicts with Lemma B. Therefore, must be an nonempty set. Because is arbitrary in (0), the proof is complete.

E Proof of Theorem 4

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

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

F Proof of Corollary 5

G Proof of Lemma 6

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

empty. Let , we can see that

However, because , we have | ¯

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 because the objective function of (UBP) is continuous and is compact.

H Proof of Lemma 7

Proof. The Lagrangian of (UBP) is

L(θ; u, u, v) = θ, ¯+ u+ uθ, ¯mλ) + v(43) = θ, ¯x + u+ v+ u.

where 0 and are the Lagrangian multipliers. To derive the dual function ˆ) = min), we can simply set ) = 0, i.e.,

When = 0, we set

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

Clearly, Eq. (46) implies that and are collinear, i.e., . Moreover, by Eq. (47), we know that 0. Therefore, it is easy to see that = 1, which contradicts the assumption. Hence, ¯+ = 0 for all 0 and v.

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

By plugging (53) into ˆ) and noting that ) : , problem (52) is equivalent to

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 0, 0 and such that ˆ) = maxˆ). By Eq. (51), it is easy to see that 0. Therefore, ¯) attains its maximum in .

I Proof of Theorem 8

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 1), i.e., and 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

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

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

It is easy to observe that

(0, 1] due to the fact that and Eq. (68) (note 0).

Therefore, we can see that 0 and thus = 0 due to the complementary slackness condition. By plugging = 0 into Eq. (67), we can get = . The result in part a) of Theorem 8 follows by noting that ) = ).

a2) Suppose = d. If 0, then = 0 by the complementary slackness condition. In view of Eq. (68) and m1), we can see that

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

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

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

1, we can see that and are not collinear. Therefore, m1) and Eq. (62) imply that d < 1. Moreover, the assumption leads to d > 0. As a result, we have (1 0 and thus

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 = 1.

Proof. Because = 1, by part a) of Lemma 7, the dual problem of (UBP) is given by (UBD). Therefore, the following KKT conditions hold as well:

where 0 and 0 are the optimal solution of (UBD), and 0 are the slack variables. Since 0, then = 0 and Eq. (64) results in

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

Therefore, we can see that 0 and thus = 0 due to the complementary slackness condition. By plugging = 0 into Eq. (67), we can get = . The result in part a) of Theorem 8 follows by noting that ) = ).

I.3 Proof for the Collinear and Negative Correlated Case

Before we proceed to prove Theorem 8 for the case in which = 1, it is worthwhile to noting the following lemma.

Lemma 12. C Let 0, d = and assume is known. Then (0, 1].

Proof. Let ¯x := ). Clearly, we can see that

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

We prove Theorem 8 for the case in which = 1.

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

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

By noting Eq. (74), we have

Suppose is fixed, it is easy to see that

and

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

Moreover, we observe that

Therefore, Eq. (82) can simplified as:

By Eq. (77), we can see that

where

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

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

Designed for Accessibility and to further Open Science