  Convex sparsity-inducing regularizations are ubiquitous in high-dimensional
machine learning, but solving the resulting optimization problems can be slow.
To accelerate solvers, state-of-the-art approaches consist in reducing the size
of the optimization problem at hand. In the context of regression, this can be
achieved either by discarding irrelevant features (screening techniques) or by
prioritizing features likely to be included in the support of the solution
(working set techniques). Duality comes into play at several steps in these
techniques. Here, we propose an extrapolation technique starting from a
sequence of iterates in the dual that leads to the construction of improved
dual points. This enables a tighter control of optimality as used in stopping
criterion, as well as better screening performance of Gap Safe rules. Finally,
we propose a working set strategy based on an aggressive use of Gap Safe
screening rules. Thanks to our new dual point construction, we show significant
computational speedups on multiple real-world problems.
