# Simple, robust and fast algorithm for stochastic gradient descent

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?