Theano/Theano — pull request #1091 by aboSamoor (2012-11-23 17:00:25+00:00)
Title: Speed up the gradient of AdvancedSubtensor1 WIP

This is a PR to address the issues explained in [theano-users] (https://groups.google.com/forum/?fromgroups=#!topic/theano-users/z2YJFo6ciXo) and touches on https://github.com/Theano/Theano/issues/930

The solution that I propose is that `AdvancedSubtensor1` gradient return a sparse matrix instead of dense one or make that an option.

The first solution I tried was to convert
`W = W - 0.1 * grad(J, W)`
to
`AdvancedIncSubtensor1(W, 0.1 *gz, inplace=True)`

This proved to be hard to implement. Optimizing the whole graph with global optimization for the `AdvancedIncSubtensor1` is a hard to implement, as the graph get more complicated with various clones and several apply nodes separating the target from the sources of its inputs, detecting patterns becomes so brittle. I think similar issues appeared with `Subtensor` gradient optimizations.

Returning a sparse matrix will allow us to avoid any global graph optimizations needed as the operations that require dense operations will be replaced with their corresponding sparse ones. Therefore, complexity goes down from theta(W) to theta(non-zero elements in grad(J, W)). Now, sparse formats have different performance characteristics. For now, I am returning csc matrix as it works best for me.

I added a new operation that converts gx, idx to a sparse matrix. It is called ConstructSparse.

One issue that appeared and was not expected, that AddSD does not have an inpalce version. Which forces us to create a whole new copy of the dense matrix. Therefore, I added an inplace version to the python implementation. Moreover, to boost performance I implemented both inplace no-in-inplace in C. To enable inplace optimization, I added local optimization to the theano/sparse/opt.py.

I understand that my PR is quite not-quality. This is a hackish solution that fixes my problem by making my code run in constant speed regardless of the size of W. Moreover, I achieve 4x speedup on small matrices. Therefore, it is a win-win fix.

However, I would like to hear your concerns and requests to improve the patch so it is easy to merge back to theano.

Finally, I would like to thank Pascal Lamblin, John Salvatier, Ian Goodfellow and Frédéric Bastien for their help and continuous support.