Stopcriteria

Stop criteria, or stopping criteria, are rules used to terminate an iterative algorithm when a solution is deemed sufficiently accurate or when further iterations are unlikely to improve the result. They balance the need for accuracy with computational cost and are used across numerical optimization, scientific computing, and machine learning.

Common categories include convergence-based criteria and resource-based criteria. Convergence-based criteria monitor the progress of the algorithm, using measures such as changes in the objective value, changes in the parameters, or the size of the gradient. Resource-based criteria impose hard limits on computation, such as a maximum number of iterations or a time limit.

Typical forms of convergence-based stop criteria include absolute tolerances, relative tolerances, and hybrid conditions. Examples are stopping when the norm of the gradient satisfies ||grad f(x_k)|| ≤ tol, when the absolute change in the objective satisfies |f(x_{k+1}) − f(x_k)| ≤ tol, or when the step size satisfies ||x_{k+1} − x_k|| ≤ tol. Hybrid criteria may combine several checks, such as requiring both a small gradient and a small parameter change. In practice, a maximum iteration count or wall-clock time is often used as a safety net.

In machine learning, stop criteria appear as early stopping, where training ends when performance on a validation set stops improving, often with a patience parameter to avoid premature termination.

Considerations include problem conditioning, noise, and the desired accuracy. Poorly chosen stop criteria can lead to premature stopping or unnecessary computation. Hybrid and adaptive criteria are common to address these issues.