[WIP] Strong rules for coordinate descent

Fixes https://github.com/scikit-learn/scikit-learn/issues/229

This implements strong rules for discarding non active features in coordinate descent. I believe this works. However it is really slow. 

TODO:

- [ ] Decide whether to migrate the strong_active_set and check_kkt_conditions to Cython
- [ ] Fix the lazy centering of sparse matrices that gives slightly different results.
I'm taking a look at the paper and giving the code a more technical review.
Will get back to you.


On 2 September 2014 01:20, Manoj Kumar <notifications@github.com> wrote:

>  In sklearn/linear_model/coordinate_descent.py:
>
> > +    #    This is the strong active set, corresponding to the present alpha.
> > +    # 2. Compute coefficients using the active_set corresponding to the
> > +    #    previous alpha. If it is the first alpha, then the active set
> > +    #    is the set of n_features
> > +    # 3. Check if the KKT conditions are satisfied for the strong_active_set.
> > +    #    If they are violated, then add those features to the active_set,
> > +    #    if they are not already present.
> > +    # 4. If the KKT conditions are violated, then compute the coefficients
> > +    #    again. If they are not, then the non zero features become the active
> > +    #    features.
> > +    # 5. Check again for all n_features. If the KKT conditions are violated.
> > +    #    add those features to the active_set and compute the coefficients
> > +    #    again. If they are not, then the non zero features become the active
> > +    #    features.
> > +
> > +    active_set = np.arange(n_features, dtype=np.int32)
>
> A small experiment
>
> In [1]: alpha = 1.0 * 1000 * 0.5
> In [2]: beta = 1.0 * 1000 * 0.5
> In [3]: from sklearn.linear_model.cd_fast import enet_coordinate_descent
> In [4]: import numpy as np
> In [5]: w = np.zeros(10000)
> In [6]: X = np.random.rand(1000, 10000)
> In [7]: y = np.random.rand(1000)
> In [8]: active_features = np.arange(10000)
> In [9]: rng = np.random.RandomState(0)
> In [11]: max_iter = 1000
> In [12]: tol = 0.01
> In [15]: %timeit enet_coordinate_descent(w, alpha, beta, X, y, active_features, max_iter, tol, rng)
> 10 loops, best of 3: 131 ms per loop
>  In [16]: rng.shuffle(active_features)
>  In [19]: %timeit enet_coordinate_descent(w, alpha, beta, X, y, active_features[:10], max_iter, tol, rng)
> 10 loops, best of 3: 120 ms per loop
>
> Is there anything wrong with my hypothesis, that limiting the number of
> features to update, does not really decrease the runtime.
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/scikit-learn/scikit-learn/pull/3579/files#r16958594>.
>