Learning Large Scale Sparse Models

Underlying most of these algorithms is a simple yet effective operator termed hard thresholding, which sets all but the largest $k$ absolute values to zero. Hence, it is a good fit to solve the $\ell_{0}$ constrained program. [38, 4] extends this technique to the machine learning setting, where the objective function is a general loss. Yet, they are all based on a batch setting, i.e. their algorithms and theoretical results only hold if all samples are revealed in each iteration. It still remains an open question if a $\ell_{0}$ constrained formulation can be exactly solved in the online setting. The challenge falls into the fact that online optimization introduces variance to the gradient evaluation which is hard to characterize.

We propose to tackle the important but challenging problem of producing sparse solutions for large scale machine learning. Compared to the batch methods, our formulation reduces the memory cost by one order of magnitude. Compared to existing methods, our empirical study demonstrates that our improved Lasso formulation and hard thresholded SGD algorithm will always result in sparse solutions.

Coordinate descent (CD) is one of the most popular methods for solving the Lasso problem. In each iteration, it updates the coordinates of $x$ in a sequential (or random) manner by fixing the remaining coordinates. Let $x^{t-1}$ be the iterate at the $t$-th iteration. Denote

where we write the $j$th column of $A$ as $A_{j}$. In this way, solving the $i$th coordinate of $x^{t}$ amounts to minimizing

where the closed-form solution is given by

Here, $\mathcal{S}_{\lambda}(v)$ is the soft-thresholding operator:

We summarize the coordinate descent algorithm in Algorithm 1.

Parallel to coordinate descent, gradient descent is another prominent algorithm in mathematical optimization [5, 23]. That is, for a differentiable convex function $h(x)$, one computes its gradient evaluated at $x=x^{\textrm{old}}$ and update the solution as

for some pre-defined learning rate $\eta>0$. However, the $L_{1}$ norm is not differentiable at $x=0$ so we have resort to the sub-gradient method. While for first-order differentiable functions the gradient is uniquely determined at a given point, the sub-gradients of a non-differentiable convex function $h(x)$ at $x=x^{\prime}$ form a set as follows:

In our problem, the $L_{1}$ norm $\left\lVert x\right\rVert_{1}$ is non-differentiable and one may verify that its sub-gradients at $x=0$ is given by

In our implementation, we simply choose the zero vector as the sub-gradient if $x=0$. Hence, if not specified, we use the sub-gradient

for the $L_{1}$ norm.

To begin, let $\Lambda^{t}=\{i^{t}_{1},i^{t}_{2},\dots,i^{t}_{m}\}\subset\{1,2,\dots,n\}$ be an index set which is drawn randomly at the $t$-th iteration with batch size $m$. Let $A_{\Lambda^{t}}$ be the submatrix of $A$ consisting of the rows of $A$ indexed by $\Lambda^{t}$. Likewise, we define $Y_{\Lambda^{t}}$. With the notation on hand, the mini-batch sub-gradient method can be stated as follows:

For the reader’s convenience, we write the algorithm in Algorithm 3.

Fobos [16] is an interesting algorithm for solving the Lasso problem and tackles the shortcoming of sub-gradient methods. Recall that sub-gradient methods always compute the sub-gradient of $L_{1}$ norm and add it. The key idea of Fobos is updating the solution in two phases. First, it computes the gradient for the least-squares loss and performs gradient descent, i.e.,

Note that the least-squares loss is differentiable. Hence, we move forward to a new point $b^{t}$. Second, it takes the $L_{1}$ norm into consideration by minimizing the following problem:

where the closed-form solution is given by

Intuitively, (17) is looking for a new iterate that interpolates between two goals: 1) stay close to the obtained point $b^{t}$ that minimizes the least-squares (in expectation), and 2) exhibit the sparsity pattern. As [16] suggested, the step size $\eta_{t}$ should be inversely proportional to $\sqrt{t}$, which is also the choice in Algorithm 4.

While it is well known that the Lasso formulation (1) is able to effectively encourage sparse solutions, it is actually impossible to characterize how sparse the Lasso solution is for a given $\lambda$. This makes tuning the parameter hard and time-consuming.

Alternatively, the $L_{0}$ norm counts the number of non-zero components and thereby, imposing an $L_{0}$ constraint guarantees sparsity. To this end, we are to solve the following non-convex program:

where $K$ is a tunable parameter that controls the sparsity. Note that at this moment, we are only minimizing the least-squares loss, since the constraint already enforces sparsity. Again, the objective function $G(x)$ is decomposable:

where

Note that the problem above is non-convex and algorithms such as [6, 21] optimize it in a batch fashion. To be more detailed, these methods basically compute a full gradient followed by a hard thresholding step on the iterate. As mentioned earlier, it is not practical to evaluate a full gradient on a large dataset owing to computational and memory issues.

Henceforth, in this work, we attempt a stochastic gradient descent algorithm to solve (19). The high level idea follows both from the compressed sensing algorithms [6, 21] and the vanilla stochastic gradient method. That is, in each iteration $t$, given the previous iterate $x^{t-1}$, we randomly pick a sample $i_{t}$ to compute an unbiased stochastic gradient, followed by a usual gradient descent update:

Subsequently, to ensure the iterate satisfies the $L_{0}$ constraint, we perform hard thresholding $\mathcal{H}_{K}\left(\cdot\right)$ which sets all but the $K$ largest elements (in magnitude) to zero:

We summarize the algorithm in Algorithm 5.

To close this section, we give a comparison among all the methods in Table 1.

To test our Lasso and $\ell_{0}$ implementations, we selected the Gisette dataset . The examples in this dataset are instances of the numeric characters $4$ and $9$ that must be classified into the appropriate numeric category. All digits were scale normalized and centered in a fixed image window of $28\times 28$ prior to feature extraction.

This dataset consists of $6000$ training examples, $3000$ positive and $3000$ negative. There are $1000$ testing examples, again $50\%$ positive and $50\%$ negative. Each example consists of $5000$ features. Critically though, only $2500$ of these features are real, the other $2500$ were added as dummy (random) features, meaning they have no predictive power. Therefore, any good Lasso solution for this dataset should set at least $50\%$ of the weights to $0$. We want to determine which algorithm (if any) will produce the best tradeoff between memory cost, accuracy and sparsity of the solution.

An important point regarding the $\ell_{0}$ constrained SGD is that the parameter $K$ essentially determines the sparsity of resulting solution since $K$ defines the number of weighting coefficients that will be set to $0$. For example, if we have $K=500$ in a dataset with $5000$ features, the sparsity will be $0.1$ since at most $10\%$ of the features can have non-zero weights.

Since Lasso requires tuning of the soft thresholding parameter $\lambda$, we tested our different Lasso implementations along a range of different $\lambda$ values (and in the case of the $\ell_{0}$ constrained SGD, the parameter $K$) until performance became asymptotic. $\lambda$ values ranged from $1.0\times 10^{-5}$ to $1.0\times 10^{2}$, while the $K$ parameter in the $\ell_{0}$ constrained SGD ranged from $20$ to $500$. For our mini-batch implementations, we used a batch size of $20$ random samples. We then recorded the accuracy and sparsity of each solution. Accuracy is computed as classification accuracy (the percentage of test examples correctly classified as a $4$ or a $9$). Sparsity is given by the percentage of non-zero weight. For example, a sparsity value of $100$ would mean that none of the weights were set to $0$, likewise a sparsity value of $0.75$ would indicate that only $75\%$ of the weights are non-zero and $25\%$ are $0$. Therefore, lower values correspond to more sparse solution. Algorithms that provide solutions preferable in both accuracy and sparsity will be deemed better solutions.

As can be seen in Table 2, all Lasso implementations were able to achieve reasonably high accuracy given proper parameter tuning. Maximal accuracy values ranged from $0.8810$ to $0.9700$ across the different Lasso implementations. However, only Coordinate Descent and the $\ell_{0}$ Constrained SGD were able to produce truly sparse solutions.

If we look at the sparsity of the solutions generated by each Lasso implementation in Figure 1 we notice a clear trend. As we should expect, as $\lambda$ increases, so does the sparsity. The one exception is the Subgradient Minibatch and Stochastic Subgradient (not plotted), which always result in dense solutions. Therefore, the Minibatch and Stochastic Subgradient Descent methods are not able to produce sparse solutions.

Although the various Fobos implementations are able to generate sparse solutions, the accuracy of these sparse solutions is extremely low (e.g. $50\%$). The only Lasso implementation plotted here that can produce both sparse and accurate solutions is Coordinate Descent, which has the significant drawback of being a batch method and therefore requiring extensive memory.

As previously mentioned, the $\ell_{0}$ constrained SGD will always produce a sparse solution since the sparsity is directly related to the parameter $K$. Since the sparsity of the solution for this implementation is always pre-defined, it is not necessary or informative to plot here.