Scikit-learn's SGDClassifier code 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.

 A: 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.
A: 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!

