On Regularized Sparse Logistic Regression

Logistic regression has been applied widely in many areas as a method of classification. The goal of logistic regression is to maximize the likelihood based on the observation of training samples, with its objective function formulated as follows with a natural and meaningful probabilistic interpretation:

where $\mathbf{x}_{i}$ and $y_{i}$ denote the $i$-th sample and its label.

Though logistic regression is straightforward and effective, its performance can be diminished due to over-fitting [10], especially when the dimensionality of features is very high compared to the number of available training samples. Therefore, regularization term is usually introduced to alleviate over-fitting issue [23]. Also, in applications with high-dimensional data, it’s desirable to obtain sparse solutions, since in this way we are conducting classification and feature selection at the same time. Therefore, $\ell_{1}$-regularized logistic regression has received more attention with the sparsity-inducing property and its superior empirical performance [1].

More recent studies show that $\ell_{1}$-norm regularization may suffer from implicit bias problem that would cause significantly biased estimates, and such bias problem can be mitigated by a nonconvex penalty [9]. Therefore, nonconvex regularization has also been studied to induce sparsity in logistic regression [29]. Solving sparse logistic regression with convex $\ell_{1}$-norm regularizer or with nonconvex term using a unified algorithm has been studied in [19]. However, it imposes strong regularity condition on the nonconvex term and it transfers the nonconvex problem into an $\ell_{1}$-norm regularized surrogate convex function, which limits its generality. As a contribution, we extend the scope of nonconvex penalties to a much weaker assumption and compare the performance of different regularization terms with a unified optimization framework.

In this paper, we solve $\ell_{1}$-regularized (sparse) logistic regression by proposing a novel framework, which can be applied to non-convex regularization term as well. The idea of our proposed method stems from the well know Iterative Shrinkage Thresholding Algorithm (ISTA) and its accelerated version Fast Iterative Shrinkage Thresholding Algorithm (FISTA) [3], upon which we modify the step-size setting and line search criteria to make the algorithm applicable for both convex and nonconvex regularization terms with empirical faster convergence rate. To be clear, we call any logistic regression with regularization term that can produce sparse solutions as sparse logistic regression, therefore, the term is not only limited to $\ell_{1}$-norm regularization.

Due to the NP-hardness of $\ell_{0}$-norm constraint problem, being its tightest convex envelope, $\ell_{1}$-norm is widely taken as an alternative to induce sparsity [17, 18, 32]. The main drawback of $\ell_{1}$-norm is it’s non-differentiable, which makes the computation challenging compared to squared $\ell_{2}$-norm. Sub-gradient is an option but can be very slow even if we disregard the fact that it is non-monotone. Besides, there has been active research on numerical algorithms to solve $\ell_{1}$-regularized logistic regression. Among these, an intuitive idea is as the challenge originates from the non-smoothness of $\ell_{1}$-norm, we can make it ‘smoothable’. For example, in [24], the $\ell_{1}$-norm is approximated by a smooth function that is readily solvable by any applicable optimization method. The iteratively reweighted least squares least angle regression (IRLS-LARS) method converts the original problem into a smooth function by the equivalent $\ell_{1}$-norm constrained ball [14]. In addition, coordinate descent method has been utilized to solve the $\ell_{1}$-regularized logistic regression as well: in  [7] and  [20], cyclic coordinate descent is used for optimizing Bayesian logistic regression. Besides, the interior-point method is another option with truncated Newton step and conjugated gradient iterations [12]. We refer readers to the papers and references therein.

The bias of $\ell_{1}$-norm is implicitly introduced as it penalizes the parameters with larger coefficients more than the smaller ones. Recently, nonconvex regularization terms have drawn considerable interest in sparse logistic regression since it is able to ameliorate the bias problem of $\ell_{1}$-norm, and it acts as one main driver of recent progress in nonconvex and nonsmooth optimization [28].

It is worth noting that there have been many studies trying to solve the $\ell_{0}$-regularized problems directly. The most common method is to conduct coordinate descent for nonconvex regularized logistic regression [5, 22]. The alternating direction method of multipliers (ADMM) inspires the development of incremental aggregated proximal ADMM to solve nonconvex optimization problems, and it achieves good results in sparse logistic regression [11]. In [21], the momentumized iterative shrinkage thresholding (MIST) algorithm is proposed to minimize the nonconvex criterion for linear regression problems, and similar ideas can be applied to logistic regression as well. Besides the $\ell_{0}$-norm, other nonconvex penalties are also explored. The minimax concave penalty (MCP) is studied in [31] together with a penalized linear unbiased selection (PLUS) algorithm, and it shows the MCP is unbiased with superior selection accuracy. The smoothly clipped absolute deviation (SCAD) penalty is proposed in [6], which corresponds to a quadratic spline function, and the study shows SCAD penalty outperforms the $\ell_{1}$-norm regularizer significantly, and it has the best performance in selecting significant variables without introducing excessive biases.

The empirical studies are conducted on the following 5 benchmark classification datasets, which can be found in UCI machine learning repository [2]: Wine, Specheart, Ionosphere, Madelon, and Dorothea. For the logistic regression with convex $\ell_{1}$-norm penalty, we compare our proposed methods with the following counterparts: OMFISTA [34], Interior-Point method [12], GSLR [15], SPA  [26], Lassplore [16], HIS [25], and proximal Newton [13]. For the logistic regression with nonconvex penalties, we compare our proposed methods with GPGN [27] and HONOR  [8], and the nonconvex penalty we utilize in the experiment is SCAD. In this benchmark result, the classification performance is measured by the average testing accuracy obtained with $k$-fold cross-validation, in our experiment, we set $k=5$. It’s known there exists a valid upper threshold for $\lambda_{max}$ in logistic regression [12], when the regularization parameter is larger than that, the cardinality of the solution will be zero. Therefore $\lambda$ is usually selected as a fraction proportion of $\lambda_{max}$. We choose a 10-length path for $\lambda$, where the fraction is $0.01,0.02,0.05,0.07,0.1,0.2,0.3,0.5,0.7,0.8$ respectively. All the other parameters are set as suggested in the original papers. In Table III and Table IV, we show the testing accuracy with various $\lambda$ for $\ell_{1}$-norm and SCAD regularizer item, respectively.

We compare the efficiency of our proposed methods with other methods. We show the computation time for the training with 1000 and 500 features. The number of samples is fixed at 1000 and with $\lambda/\lambda_{max}$ = 0.1. From Figure 4 we can see that in the $\ell_{1}$-norm regularized logistic regression problem, our proposed methods (ISTA-BB, ISTA-reverse, and FISTA-Lip) require less computation time to converge. The proximal Newton method is not included in the figure because its running time is way higher than the others, making it hard to visualize the time in the same figure. The nonconvex regularized logistic regression follows a similar path, ISTA-BB and ISTA-reverse have better performance than GPGN and HONOR in terms of less time consumption.

We also conduct numerical experiments to show the scalability of our methods. We varied the number of features and the number of samples to show how our algorithms perform with the size of samples increase. The results are illustrated in Figure 5. For our proposed methods, the computation time is quite low even with a large number of features and samples, the trends of increasing computation time with increased features/samples are quite stable, there is no explosive increase in the computation time with the rapid growth in features/samples.

We present the convergence of our proposed methods along the regularization path, using a Ionosphere data from the UCI repository, which is shown in Figure 7. Similarly, we also include the original ISTA and FISTA methods to show the superiority of our proposed. The figure shows that our methods have similar performance in terms of convergence, but require less iterations to converge han that of vanilla ISTA and FISTA. We also explore the sparsity of the solutions, which is shown in Figure 7. The numbers of nonzero entries obtained by our methods are pretty similar to each other, and the solutions are more sparse than the counterparts. In general, we can see that the regularization parameter $\lambda$ has effects on the number of iterations to converge and the sparsity of optimal solutions. Also, we note that the proximal Newton method is not able to induce sparsity even with large $\lambda$.

In this paper, we propose new optimization frameworks to solve sparse logistic regression problem which work for both convex and nonconvex regularization terms. Experimental results on benchmark datasets with both types of regularizers demonstrate the advantages of our proposed algorithms compared to others in terms of both accuracy and efficiency.