knitr::opts_chunk$set(echo = TRUE, collapse = TRUE, comment = "#>") library(mize)
There are a variety of ways that the optimization can terminate, running the gamut from good (you have reached the minimum and further work is pointless) to bad (the solution diverged and an infinity or NaN turned up in a calculation).
We'll use the 2D Rosenbrock function for the examples, which has a minimum at
c(1, 1)
, where the function equals 0
.
rb_fg <- list( fn = function(x) { 100 * (x[2] - x[1] * x[1]) ^ 2 + (1 - x[1]) ^ 2 }, gr = function(x) { c( -400 * x[1] * (x[2] - x[1] * x[1]) - 2 * (1 - x[1]), 200 * (x[2] - x[1] * x[1])) }) rb0 <- c(-1.2, 1)
An obvious way for the optimization to terminate is if you run out of iterations:
res <- mize(rb0, rb_fg, max_iter = 10) res$terminate res$f res$par
When comparing different methods, the number of iterations is obviously less important than the amount of actual CPU time you spent. Comparing results with a fixed number of iterations is not a very good idea, because different methods may do a lot more work within an iteration than others. See the section on function and gradient tolerance below.
There are two ways to specify a function tolerance, based on comparing the
difference between consecutive function values. abs_tol
measures absolute
tolerance.
res <- mize(rb0, rb_fg, max_iter = 100, abs_tol = 1e-8) res$terminate res$f res$par
However, relative tolerance is often preferred, because it measures the change in value relative to the size of the values themselves.
res <- mize(rb0, rb_fg, max_iter = 100, rel_tol = 1e-3) # hit relative tolerance res$terminate # but stopped too early! res$iter res$f res$par
In this example we stopped way too early. Even efficient methods like L-BFGS may make little progress on some iterations, so don't be too aggressive with relative tolerance.
Gradient tolerances measure the difference between the size of the gradient on
consecutive step. grad_tol
uses the 2-norm (sometimes referred to as the
Euclidean norm) of the gradient to measure convergence.
res <- mize(rb0, rb_fg, abs_tol = 0, grad_tol = 1e-3) res$terminate res$f res$par
This seems like a good stopping criterion because it is always zero at a minimum, even if the function isn't. It is also used to compare different methods in Nocedal and Wright's book. However, it has also been recognized that it is not always reliable, see for instance this paper by Nocedal and co-workers.
Other workers suggest using the infinity norm (the maximum absolute component)
of the gradient vector, particularly for larger problems. For example, see this
conjugate gradient paper by Hager and Zhang.
To use the infinity norm, set the ginf_norm
parameter.
res <- mize(rb0, rb_fg, rel_tol = NULL, abs_tol = NULL, ginf_tol = 1e-3) res$terminate res$f res$par
While the gradient norms aren't as reliable for checking convergence, they almost never incur any overhead for checking, because the gradient that's calculated at the end of the iteration for this purpose can nearly always be re-used for the gradient descent calculation at the beginning of the next iteration, whereas the function-based convergence requires the function to be calculated at the end of the iteration and this is not always reused, although for many line search methods it is.
You can also look out for the change in par
itself getting too small:
# set abs_tol to zero to stop it from triggering instead of step_tol res <- mize(rb0, rb_fg, abs_tol = 0, step_tol = .Machine$double.eps) res$terminate res$iter res$f res$par
In most cases, the step tolerance should be a reasonable way to spot
convergence. Some optimization methods may allow for a step size of zero for
some iterations, preferring to commence the next iteration using the same
initial value of par
, but with different optimization settings. The step
tolerance criterion knows when this sort of "restart" is being attempted, and
does not triggered under these conditions.
For most problems, the time spent calculating the function and gradient values will drown out any of the house-keeping that individual methods do, so the number of function and gradient evaluations is the usual determinant of how long an optimization takes. You can therefore decide to terminate based on the number of function evaluations:
res <- mize(rb0, rb_fg, max_fn = 10) res$terminate res$nf res$f res$par
Number of gradient evaluations:
res <- mize(rb0, rb_fg, max_gr = 10) res$terminate res$ng res$f res$par
or both:
res <- mize(rb0, rb_fg, max_fg = 10) res$terminate res$nf res$ng res$f res$par
The function and gradient termination criteria are checked both between
iterations and during line search. On the assumption that if you specify
a maximum number of evaluations, that means these calculations are expensive,
mize
errs on the side of caution and will sometimes calculate fewer
evaluations than you ask for, because it thinks that attempting another
iteration will exceed the limit.
By default, convergence is checked at every iteration. For abs_tol
and
rel_tol
, this means that the function needs to have been evaluated at the
current value of par
. A lot of optimization methods do this as part of their
normal working, so it doesn't cost very much to do the convergence check.
However, not all optimization methods do. If you specify a non-NULL
value for
rel_tol
and abs_tol
and the function value isn't available, it will be
calculated. This could, for some methods, add a lot of overhead.
If this is important, then using a gradient-based tolerance will be a better choice.
mize
internally uses the function value as a way to keep track of the best
par
found during optimization. If this isn't available, it will use a gradient
norm if that is being calculated. This is less reliable than using function
values, but better than nothing. If you turn off all function and gradient
tolerances then mize
will be unable to return the best set of parameters found
over the course of the optimization. Instead, you'll get the last set of
parameters it used.
If convergence checking at every iteration is too much of a burden, you can
reduce the frequency with which it is carried out with the check_conv_every
parameter:
res <- mize(rb0, rb_fg, grad_tol = 1e-3, check_conv_every = 5, verbose = TRUE)
This also has the side effect of producing less output to the console when
verbose = TRUE
, because log_every
is set to the same value of
check_conv_every
by default. If you set them to different values, log_every
must be an integer multiple of check_conv_every
. If it's not, it will be
silently set to be equal to check_conv_every
.
In many cases, however, convergence checking every iteration imposes no
overhead, so this is a non-issue. The vignette that runs through the methods
available in mize
mentions where it might be an issue.
Any scripts or data that you put into this service are public.
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.