Overview

This PR refactors cd_fast.pyx module (linear_module) which implements coordinate-descent, and make it more transparent and extensible.

The resulting implementation, is a single function which can solve general penalized / constrained multi-task least-squares. regression problems. Out-of-the-box, it supports

• Gram mode (crucial when p << n) and non-Gram mode (crucial when p >> n)
• a variety of penalties and constraints, including:
  • L11 penalty (sum of L1 norms), as in multi-task Lasso;
  • L21 penalty (sum of L2 norms), as in G-Lasso;
  • L2INF constraint (L2 constraint on each block), as in vanilla dictionary-learning;
  • L1INF constraint (L1 constraint on each block), e.g as in sparse PCA

The API remains consistent with the legacy implementation via cd_fast2.

Ping @agramfort

Other benefits

• Things like screening rules for LASSO-type problems (inexact Stanford, GapSafe, etc.) and be implemented in a global way (by just modifying the single central cd solver), reducing maintenance complexity
• The use of cBLAS has been factored out into a transparent API which is easier to understand, modify or replace (say, with the modern scipy's cython_blas way)
• Factored the implementation of the dual gap computation into a single transparent function.

Also

• It also supports user-defined penalties (via their prox operators). For example, with this technology, it is straightforward to implement otherwise non-trivial models like:

• BCD dictionary update in online structured dictionary-learning with general (e.g see Dohmatob el al. "Learning brain regions via large-scale online structured sparse dictionary-learning", In NIPS 2016")

• The same code can be used in implement dictionary updates (once again with both standard and exotic penalties / constraints), via a single appropriate call (another upcoming PR)

Some very preliminary benchmarks

• Script: https://github.com/dohmatob/scikit-learn/blob/refactor-cd/benchmarks/bench_lasso_cd_fast2.py