How is `tol` used in scikit-learn's `Lasso` and `ElasticNet`?

Question

As a followup to this question, how does scikit-learn implementation of Lasso (and coordinate_descent algorithm) uses the tol parameter in practice?

More precisely, in the documentation, we can see:

tol: float, optional

The tolerance for the optimization: if the updates are smaller than tol, the optimization code checks the dual gap for optimality and continues until it is smaller than tol.

Additionally, when the model does not converge, we can get:

ConvergenceWarning: Objective did not converge. You might want to increase the number of iterations. Duality gap: 8.058438499079784, tolerance: 5.712111291830755 positive)

So:

1. How is the duality gap defined in the case of Lasso (/ElasticNet)?
2. Why the displayed tolerance in the example above is 5.712111291830755 whereas it was set as 0.0001 (default value) in the model?
3. In pratice, what does the optimization code checks the dual gap for optimality and continues until it is smaller than tol. mean?

Answer 1

I am going to explain the case of Lasso, you can apply the same logic to ElasticNet.

1. How is the duality gap defined in the case of Lasso (/ElasticNet)?

The duality gap is the difference between a solution of the primal problem and a solution of the dual problem as said here. The primal problem is the following: $$ \min_{w \in \mathbb{R}^{n}} \frac{1}{2} ||Xw - y||_{2}^{2} + \alpha ||w||_{1}$$

Where $n$ is the number of features that your dataset has. $X$ is your samples, $w$ is the weights and $\alpha$ is the tradeoff between accuracy and sparsity of the weights. I don't think there is a real interest in looking at the dual formulation but if you want, you can have a look here.

However, it is more interesting to know that the dual gap is always positive. In case of strong duality, the dual gap is equal to zero. The lasso problem is convex (and has an interior point) so there is strong duality. This is why reducing the dual gap tells us that we are getting closer to an optimal solution.

2. Why the displayed tolerance in the example above is 5.712111291830755 whereas it was set as 0.0001 (default value) in the model?

The reason is that the algorithm has not converged yet after max_iter updates of weight coordinate. That is why they ask you to increase the number of iterations. The last update of a weight coordinate changed the value of this coordinate by 5.71, which is greater than 0.0001. In the meantime, with the weights that you have, the primal problem minus the dual problem is equal to 8.058.

3. In pratice, what does the optimization code checks the dual gap for optimality and continues until it is smaller than tol. mean?

In order for your algorithm to converge, there has to be an update of a weight coordinate lower than tol. Then, sklearn will check the dual gap and it will stop only if the value is lower than tol.