Maximum Likelihood Stopping Tolerance I have a large scale problem that I am training with MLE. It is taking quite a long time. I would like to set a stopping condition.
How does one set a tolerance level in MLE optimization?


*

*absolute change in logL < tolerance

*absolute change in logL/number_of_samples < tolerance

*%change in LogL < tolerance


Obviously one can always go with any of them, but which one actually indicates that the change in model is small (at least under some well founded interpretation)?
For example (1) ignores sample size hence a fixed tolerance will not make much sense. (2) has some interpretation from KL sense, as average number of bits.
 A: Rather than looking at the log likelihood alone, the most "rigorous" stopping criteria should be the gradient norm being small enough. Note that the gradient being zero is literally what we want mathematically (consider solving the maximisation problem by hand), while the change in the log likelihood between steps being small is just a heuristic for algorithmic purpose.
If the log-likelihood surface is very flat then in some neighbourhood of the MLE the change of function value between optimisation steps can be rather small. Any of your criteria may stop too early when the likelihood surface is almost flat, but an algorithm that insists on using only the gradient norm may make a lot of small improvement until it has found the location where the gradient norm is near zero; and sometimes these small steps accumulatively move the parameter quite a lot.
This also makes intuitive sense: the gradient approximates the change in $\log L$ when $\theta$ is moved by an unit amount. If moving $\theta$ by an unit amount will move $\log L$ a lot, then it is a bad idea to stop even if the next step will only give you a slight improvement. On the other hand, stopping when the change in log likelihood is small is equivalent to saying that "I will be happy if the log-likelihood is close enough to the maximum" while not caring where the true $\theta_{MLE}$ actually is. Note that the former is motivated by finding the exact location of the MLE while the latter is more similar to the cases, say, in finance: "if doing more computation will give me only $0.1\%$ improvement in my ~$100 investment return then it is fine; I really don't care about that one cent."
But log-likelihood is not dollars, and $0.1\%$ can be a lot. To see how important a 0.1% is, consider this: let an early-stopping algorithm stops at point $\theta_1$ with $\log L_1=-3001$ and another algorithm stops at $\theta_2$ with $\log L_2=-3000$. Note that $1/3000*100\% = 0.033\%$ only, but $L_2/L_1 = 2.718$. If we interpret the likelihood as the probability that the data occurs then the chance that the data occur if $\theta_2$ were true is more than twice if $\theta_1$ were true. Here one-third of a $0.1\%$ of improvement has led to the likelihood being double!
