3
$\begingroup$

I am experimenting with some regularized linear regression methods using sklearn and noticed that Ridge does not accept warm start. I found it odd as many other methods do accept like Lasso, LogisticRegression, etc.

Is there a deeper reason for this? Does Ridge not benefit from warm starting?

$\endgroup$
  • 6
    $\begingroup$ Ridge can be solved as a system of linear equations, so does not need an iterative algorithm. LASSO is not solvable as a linear system, so needs some kind of iterative solver. $\endgroup$ – Matthew Drury Apr 30 '18 at 18:29
5
$\begingroup$

Ridge regression can be solved in one shot as a system of linear equations:

$$ \hat \beta = (X^t X + \lambda I)^{-1} X^t y $$

So ridge regression is usually solved with a linear equation solver, just like linear regression.

For example, sklearn uses the singular value decomposition of the matrix $X$:

$$ X = UDV^{-1} $$

To re-express this system as

$$ \hat \beta = V (D^2 + \lambda I)^{-1} DU^{t}y $$

For a derivation of this equation, see The proof of shrinking coefficients using ridge regression through spectral decomposition.

Notice that this equation is rather nicer than it may seem. The $D^2 + \lambda I$ matrix is diagonal, so inverting it is just taking the reciporical of the entries. Then $(D^2 + \lambda I)^{-1} D$ is also diagonal, and the matrix product is just the product of the diagonal entries.

Here's the source code from sklearn:

def _solve_svd(X, y, alpha):
    U, s, Vt = linalg.svd(X, full_matrices=False)
    idx = s > 1e-15  # same default value as scipy.linalg.pinv
    s_nnz = s[idx][:, np.newaxis]
    UTy = np.dot(U.T, y)
    d = np.zeros((s.size, alpha.size), dtype=X.dtype)
    d[idx] = s_nnz / (s_nnz ** 2 + alpha)
    d_UT_y = d * UTy
    return np.dot(Vt.T, d_UT_y).T

Except for the small amount of gymnastics to deal with the zero singular values, this code lines up exactly with the equation above.

LASSO on the other hand, has no simple expression in terms of linear algebraic operations. For LASSO we need some kind of iterative solver, and so the concept of re-starting the iteration at the previous solutions makes sense.

$\endgroup$
  • $\begingroup$ Sklearn's ridge implementation also allows for stochastic average gradient descent as the solver. Shouldn't it be possible to do a warm start with that? $\endgroup$ – Russell Richie Nov 15 '18 at 19:39
  • 1
    $\begingroup$ Of course, but you would only need to do so if your data was so large that directly solving the system of linear equations is untenable. $\endgroup$ – Matthew Drury Nov 15 '18 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.