search

jolars / sgdnet

Fast Sparse Linear Models for Big Data with SAGA
https://jolars.github.io/sgdnet/
GNU General Public License v3.0
5 stars 2 forks source link

Redesigned algorithm based on DeFazio 2014 #11

Closed jolars closed 6 years ago

jolars commented 6 years ago

This pull request is the result of several attempts to optimize the implementation of the algorithm. Most of this has been cleaned up now but originally involved benchmarking both the lighting-based implementation and the original from DeFazio. In the end, the latter turned out to perform best, although it has been augmented with bits and pieces from both the lighting and scikit-learn based implementation.

I have switched from Armadillo to Eigen, which lead to significant speed boosts and slight improvements in memory footprint. Here is a benchmark run similar to the one that I included with the proposal:

image

I believe that this is close enough for most comparisons that additional optimizations in the future along with going parallel should put us ahead. One reason for why we might not reach the same speeds as in the cython-based implementations is that they use more aggressive optimization (-O3 compared to -O2, which seems to be default for R).

As you can see, however, there is still some way to go, and for computing the full path glmnet is still much faster in the L1-regularized case, probably due to the use of restricted sets via the strong rules. For L2-regression we are now very close performance-wise, however.

I have also included a brief vignette with these benchmarks. The data itself is produced from a script in data-raw. I am not sure that this is a good idea by the way, so if you have advice for a better way to store the data for the vignette I am all ears.

There is still only support for the binomial and gaussian families. I'll deal with that in the next pull request.

Edit 6/7 I should also note that the domain for binomial responses has been switched to {-1, 1}.

michaelweylandt commented 6 years ago

Looks good - I didn't check the algorithmic details though.

Which algorithm exactly is DeFazio 2014? The original SAGA paper or the finito paper?

jolars commented 6 years ago

I actually looked mostly at https://github.com/adefazio/point-saga/blob/master/optimization/saga.pyx but this is basically a carbon copy of the SAGA paper.

michaelweylandt commented 6 years ago

Ok - sounds good. (The logger at the end of the link prints "point-saga" instead of SAGA, but I think that's a typo)

jolars commented 6 years ago

I'll merge this one in now. Thanks for the review!