scikit-learn/scikit-learn — pull request #3719 by MechCoder (2014-09-29 13:12:28+00:00)
Title: ENH: Faster stopping criteria based on glmnet for coordinate descent

The current cd algorithm breaks when the dual gap if the biggest coordinate update is less than tolerance. Glmnet however checks if the max change in the objective is less than tol and then breaks. This surprisingly leads to huge changes in speedup with almost no noticeable regression in prediction.

It states that, Each inner coordinate-descent loop continues until the maximum change in the objective after any coefficient update is less than thresh times the null deviance.

It should be noted that the default tolerance in this case is 1e-7

Some initial benchmarks using `LassoCV` and `precompute=False`.

For the newsgroup dataset (using two categories), 5 random splits. (1174 X 130107), test_size = 2/3 of total size.

In this branch (using tol=1e-7)
mean_time = 16.6982872009
mean_accuracy_score = 0.89587628866
In master (using tol=1e-4)
mean_time = 236.406961584
mean_accuracy_score = 0.889175257732

For the haxby dataset, using 5 random splits, (216 X 577)

In this branch (using tol=1e-7)
mean_time = 0.495861053467
mean_accuracy_score = 0.958333333333
In master (using tol=1e-4)
mean_time = 3.05996584892
mean_accuracy_score = 0.930555555556

For the arcene dataset, (100 * 10000)
In this branch (using tol=1e-7)
mean_time = 4.69407510757
accuracy_score on test data = 0.68

In master (using tol=1e-7)
mean_time = 57.34074401860.68
accuracy_score on test data = 0.68

For the duke dataset, 5 random splits
In master
mean_accuracy_score = 0.84000000000000008
mean_time = 3.316893196105957

In this branch
mean_accuracy_score = 0.82666666666666655
mean_time = 1.2530781269073485

Since the default tolerances are different, how do we accomodate this change in terms of API. Do we need a new stopping criteria called "glmnet?".