Simple, robust and fast algorithm for stochastic gradient descent

Question

I'm trying to solve an optimisation problem with stochastic gradient descent with the following properties:

• It has a very large (1,000,000+ element) parameter vector.
• Empirically, there seems to be a single maximum (though I can't prove this) so hill climbing is fine, however the problem is definitely not convex
• I can get gradient samples at any point, but the samples have quite a bit of noise and getting a large number of samples is expensive.
• It needs to be an online algorithm

Currently, I'm using a simple online gradient descent with momentum. It works, but has two problems:

• It seems quite slow to converge
• It requires quite careful hand-tuning of the learning rate

Is there a better algorithm that I could use for this situation?

Answer 1

Check out Leon Bouttou's averaged stochastic gradient. It's all on his site. There is also a good video lecture on it.

What he is saying is that in your setting SGD is the best you can do. If you are uncertain about the hyperparameters, run several different configurations on a small (a few thousand examples) subset of your data and check which work best.

Having said that, I want to point out that there is a form of Online LBFGS and LBFGS even works if you don't use all the data every step (just 1000 examples for example). Maybe this is 'online enough'. Then there is resilient propagation (which, as opposed to common belief, not only works with neural networks but is an ordinary optimizer).

From my experience, you should try out everything. You can never reliably say which method works best a priori.

Answer 2

The latest version of Vowpal Wabbit (the AllReduce option) supports a hybrid SGD / LBFGS approach: SGD is run first to quickly find a good solution (after a single pass pretty much) and then LBFGS is used to converge to the (near) optimal solution.