Is my Lasagne/Theano neural network running too slow?
Found the answer

I found out why it was going slowly, after doing some profiling and reading this:

It turns out that if you do a convolution with a stride != 1, then it doesn't use the GPU for that operation (or perhaps the gradient of that operation), and makes things run much slower.  I was only using a non-1 stride to save execution time anyway, but turns out I'm better off getting rid of the stride.

Also note that in your convoution layer, you have to completely get rid of stride=X.  Just having stride=1 is not sufficient.