For the purpose of model fitting in a large time series dataset, I am using stochastic gradient descent of the negative log likelihood. The model is nonlinear and non-convex. Is there a thumb rule for choosing a good step size? I could choose a very small step size for stable but painfully slow convergence, but I would like to be able to choose a big enough step size for faster convergence and anneal it.
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Depending on your specific system and the size, you could try a line search method as suggested in the other answer such as Conjugate Gradients to determine step size.
However, if your data size is really large, this might become very inefficient and time consuming. For large datasets people often choose a fixed step size and stop after a certain number of iterations and/or decrease the step size by a certain percentage after each pass through the data so that you can effectively take big "jumps" when you are first starting out and slow down once you are getting closer to your solution. You can determine the step size by using a validation method such as cross-validation and choose a step-size which minimizes your cross-validation error. If your training set is huge and your model (number of free parameters) is not terribly complicated, then a step size which works well for the in-sample will likely work well for out-of-sample (test data set) as well. Even so, regularization may be important for achieving a good generalization.
The Netflix competition is a great example of a huge dataset (480,189 users and 17,770 movies, and several million ratings for the training set) where stochastic gradient descent was used as the workhorse optimization algorithm for training most of the prediction models used. A good paper to read regarding an algorithm used in the Netflix competition is Factorization Meets the Neighborhood by one of the winners of the competition, Y. Koren. For training their models, they typically used a fixed learning rate, and empirically a learning rate $\eta = 0.001$ seemed to work well for the Netflix problem. This is highly application specific, however!
$\begingroup$
$\endgroup$
Another suggestion via a blog post I just read that refers to a talk at NIPS 2007 tutorial:
Do a line search once for a subset of samples, and then fix the learning rate to be the effective step size within the line search.
$\begingroup$
$\endgroup$
0
Have you considered a line search? Typically, convergence proofs and anecdotes of convergence for optimization problems both rely heavily on having an appropriate line search in place.
