Scikit-learn's SGDClassifier code question

Question

I have a question regarding the code of function SGDClassifier, from library scikit-learn, which implements linear classification using the stochastic gradient descent (SGD) algorithm. It concerns its application for the Support Vector Machine (SVM) model - i.e. SVM is parametrized by a hinge loss function and a L2 penalty function. The SVM decision function is:

$$ d(x) = sign\left(f(x)\right) = sign\left(w^Tx\right) $$

The optimal solution $w^*$ is found by solving the following regularized problem ($[x]_+ \equiv \max[0,x]$):

$$ \min_w \left(\sum_{i=1}^{n}{\left[1-y_i\,w^Tx_i\right]_+}+\lambda\|w\|^2\right) $$

From [Bottou, 2012], page 3, I recall the SGD algorithm's main update equation for the SVM:

$$ w \leftarrow w \ - \ \eta_t \left(\lambda w - y_tx_t\mathbf{1}_{\{y_tw^Tx_t<1\}} \right) $$

However, I am having trouble finding this same equation in SGDClassifier. The code of SGDClassifier is based on the function _plain_sgd() written in Cython: for an optimal learning rate (2), a hinge loss $-$ see definition of dloss in the code from line 108 on; dloss for a hinge loss function (SVM) is in line 160 $-$ and a L2 penalty (2), and ignoring class and sample weights, I have the impression the value for the update of $w$ is computed in line 639 and is equal to -eta * dloss:

$$ w \leftarrow w \ - \ \eta_ty_t\mathbf{1}_{\{y_tw^Tx_t<1\}} $$

There is a last computation in line 656:

w.add(x_data_ptr, x_ind_ptr, xnnz, update)

But I do not understand what this does.

Is there anything I have missed on _plain_sgd code? Has anybody a clue on where these differences come from? Especially given that scikit-learn claims that they follow Bottou's approach:

The implementation of SGD is influenced by the Stochastic Gradient SVM of Léon Bottou.

Answer 1

As you said, with $L_2$ regularization, the update is:

\begin{equation} w \leftarrow w - \eta_t\lambda w - \eta_t y_t x_t 1_{\{...\}} \end{equation}

The first two terms corresponds to a simple scaling. It is updated with the line:

w.scale(max(0, 1.0 - ((1.0 - l1_ratio) * eta * alpha)))

where the weight w are not really updated: to be fast, only a scaling coefficients is updated.

The last term of the update is done with the line:

w.add(x_data_ptr, x_ind_ptr, xnnz, update)

The key element is that if the update is sparse, we don't want to update all the weights. The second step only apply the non-zero updates, but the first step would affects all the weights. To avoid that, only a scaling coefficient is updated.

You might want to check the code of the weight vector.

Answer 2

While i can't give you a complete analysis, i'm pretty sure, that these differences are due to the fact, that the implementation is targeting sparsity in the data.

Have a look at the Bottou paper you linked, especially part 5.1! There is a special treatment mentioned for sparse input and the update rule is splitted into several lines.

Further evidence:

• the code-line w.add(x_data_ptr, x_ind_ptr, xnnz, update) you refer to: xnnz means most of the time nonzeros (as in nonzeros of sparse-matrix) like for example here
• sklearns SGDClassifier is sparse-matrix ready (see here)
• personal experience tells me that sparsity-information is used!