How to define the termination condition for gradient descent?

Actually, I wanted to ask you how can I define the terminating condition for gradient descent.

Can I stop it based upon the number of iterations, i.e. considering parameter values for, say, 100 iterations?

Or should I wait such that the different in the two parameters values 'new' and 'old' is very small to the order of lets say $10^{-6}$? This will definitely take much time.

What is the best way? In my case even one iteration takes significant time. In this situation if I wait for the 2nd condition it might even take weeks I guess.

So which approach should I use. How to tackle this scenario?

• It isn't explicitly stated, but I assume that you are trying to find an MLE. Your result really depends entirely on your parameter space, your likelihood function and your needs (aka, best isn't well defined). If you are just looking for theoretical justification such as asymptotic efficiency; under Le'Cam conditions you can just use the one-step MLE (Under the further assumption is that you are using Newton's Method and the score function for your gradient descent). This requires that your initial value is such that $n^{1/2}\hat{\theta}_0 \rightarrow \theta$ in probability. – Jonathan Lisic Aug 2 '12 at 18:40
• so wait, when you said "new" - "old" is suffitiently small, is that an incorrect termination condition for gradient descent? (if fixed point like theorems apply, that condition should be ok?) – Charlie Parker Aug 24 '15 at 5:03
• One could stop when any one of: function values $f_i$, or gradients $\nabla f_i$, or parameters $x_i$, seem to stop moving, either relative or absolute. But in practice $3 \times 2$ parameters ftolabs ftolrel .. xtolabs is way too many so they're folded, but every program does that differently. See Mathworks tolerances and stopping criteria for a picture. – denis Jun 12 '18 at 9:54

Nice question. I've seen lots of stopping rules in the literature, and there are advantages and disadvantages to each, depending on context. The optim function in R, for example, has at least three different stopping rules:

• maxit, i.e. a predetermined maximum number of iterations. Another similar alternative I've seen in the literature is a maximum number of seconds before timing out. If all you need is an approximate solution, this can be a very reasonable. In fact, there are classes of models (especially linear models) for which early stopping is similar to putting a Gaussian prior on your parameter values. A frequentist would say you have an "L2 norm" rather than a prior, but they would also think of it as a reasonable thing to do. I've only skimmed this paper, but it talks about the relationship between early stopping and regularization and might help point you toward more information. But the short version is, yes, early stopping can be a perfectly respectable thing to do, depending on what you're interested in.

• abstol, i.e., stop when the function gets "close enough" to zero. This may not be relevant for you (it doesn't sound like you're expecting a zero), so I'll skip it.

• reltol, which is like your second suggestion--stop when the improvement drops below a threshold. I don't actually know how much theory there is on this, but you'll probably tend to get lower minima this way than with a small maximum number of iterations. If that's important to you, then it might be worth running the code for more iterations.

Another family of stopping rules has to do with optimizing a cost function on a validation data set (or with cross-validation) rather than on the training data. Depending on what you want to use your model for, you might want to stop well before you get to the local minimum on your training data, since that could involve overfitting. I'm pretty sure Trevor Hastie has written about good ways of doing this, but I can't remember the citation.

Other possible options for finding lower minima in a reasonable amount of time could include:

• Stochastic gradient descent, which only requires estimating the gradients for a small portion of your data at a time (e.g. one data point for "pure" SGD, or small mini-batches).

• More advanced optimization functions (e.g. Newton-type methods or Conjugate Gradient), which use information about the curvature of your objective function to help you point in better directions and take better step sizes as you move downhill.

• A "momentum" term in your update rule, so that your optimizer does a better job of rolling downhill rather than bounding off canyon walls in your objective function.

These approaches are all discussed in these lecture notes I found online.

Hope this helps!

Edit oh, and you can also try to get better starting values (e.g. by solving a simpler version of the problem) so that it takes fewer iterations to get close to the optimum from your "warm start".

• the issue with choosing a fixed number of iterations, is that unless you can clearly plot your cost curve (and it has small noise), then its hard to know how many iterations is too many, specially if the optimization function is complicated and who knows how many local minimums it has and if you have randomized initialization, this further worsen the issue, since it makes it even harder to guess what is a good "small" number of iterations. How do you address this issues in reality if you want to actually use early stopping? How do you make sure you dont over shoot nor undershoot too much? – Charlie Parker Aug 24 '15 at 4:53
• I'd like to clarify what reltol (i.e. when there stops being an "improvement") means. First improvement means decreasing cost function. So I will assume that what you mean is that, when the cost function stops decreasing enough (or starts increasing) one halts, right? One does not actually do "|old - new|" type of update rule, right? – Charlie Parker Aug 24 '15 at 5:37
• The abstol parameter only makes sense if you're taking the tolerance of the gradient of the cost function, not the cost function itself. In a local optimizer, the value of the gradient is zero; but not the value of the function. – Mario Becerra Jan 3 '18 at 15:54