Stopping criteria

Continuing the square‑root story from the Interface page, we now decide when the iteration should halt. A stopping criterion encapsulates halting logic separately from the algorithm update rule.

Why separate stopping logic?

Decoupling halting from stepping lets us:

Reuse generic stopping (iteration caps, time limits) across algorithms.
Compose multiple conditions (stop after 1 second OR 100 iterations, etc.).
Query convergence indication vs. mere forced termination, see querying the verdict.
Store structured reasons and state (e.g. at which iteration a threshold was met).

Built-in criteria: Heron's method

The package ships several concrete StoppingCriterions:

StopAfterIteration: stop after a maximum number of iterations.
StopAfter: stop after a wall‑clock time Period (e.g. Second(2), Minute(1)).
Combinations StopWhenAll (logical AND) and StopWhenAny (logical OR) built via & and | operators.

Each criterion has an associated StoppingCriterionState storing dynamic data (iteration when met, elapsed time, etc.).

Recall our example implementation for Heron's method, where we added a stopping_criterion to the Algorithm, as well as a stopping_criterion_state to the State.

using AlgorithmsInterface

struct SqrtProblem <: Problem
    S::Float64                # number whose square root we seek
end

struct HeronAlgorithm <: Algorithm
    stopping_criterion        # any StoppingCriterion
end

mutable struct HeronState <: State
    iterate::Float64          # current iterate
    iteration::Int            # current iteration count
    stopping_criterion_state  # any StoppingCriterionState
end

Here, we delve a bit deeper into the core components of what made our algorithm stop, even though we had to add very little additional functionality.

The first core component to enable working with stopping criteria is to extend the initialization step to include initializing a StoppingCriterionState as well. This can conveniently be done through the same initialization functions we used for initializing the state:

initialize_state constructs an entirely new stopping state for the algorithm
initialize_state! (in-place) reset of an existing stopping state.

function AlgorithmsInterface.initialize_state(problem::SqrtProblem, algorithm::HeronAlgorithm; kwargs...)
    x0 = rand() # random initial guess
    stopping_criterion_state = initialize_state(problem, algorithm, algorithm.stopping_criterion)
    return HeronState(x0, 0, stopping_criterion_state)
end

function AlgorithmsInterface.initialize_state!(problem::SqrtProblem, algorithm::HeronAlgorithm, state::HeronState; kwargs...)
    # reset the state for the algorithm
    state.iterate = rand()
    state.iteration = 0

    # reset the state for the stopping criterion
    state = AlgorithmsInterface.initialize_state!(
        problem, algorithm, algorithm.stopping_criterion, state.stopping_criterion_state
    )
    return state
end

Iteration

During the iteration procedure, as set out by our design principles, we do not have to modify any of the code, and the stopping criteria do not show up:

function AlgorithmsInterface.step!(problem::SqrtProblem, algorithm::HeronAlgorithm, state::HeronState)
    S = problem.S
    x = state.iterate
    state.iterate = 0.5 * (x + S / x)
    return state
end

What is really going on is that behind the scenes, the loop of the iterative solver expands to code that is equivalent to:

while !is_finished!(problem, algorithm,  state)
    increment!(state)
    step!(problem, algorithm, state)
end

In other words, all of the logic is handled by the is_finished! function. The generic stopping criteria provided by this package have default implementations for this function that work out-of-the-box. This is partially because we used conventional names for the fields in the structs. There, Algorithm assumes the existence of stopping_criterion, while State assumes iterate and iteration and stopping_criterion_state to exist.

Running the algorithm

We can again combine everything into a single function, but now make the stopping criterion accessible:

function heron_sqrt(x; stopping_criterion)
    prob = SqrtProblem(x)
    alg  = HeronAlgorithm(stopping_criterion)
    return solve(prob, alg)  # allocates & runs
end

heron_sqrt(2; stopping_criterion = StopAfterIteration(10))

1.414213562373095

With this function, we are now ready to explore different ways of telling the algorithm to stop. For example, using the basic criteria provided by this package, we can alternatively do:

using Dates
criterion = StopAfter(Millisecond(50))
heron_sqrt(2; stopping_criterion = criterion)

1.414213562373095

We can tighten the condition by combining criteria. Suppose we want to stop after either 25 iterations or 50 milliseconds, whichever comes first:

criterion = StopAfterIteration(25) | StopAfter(Millisecond(50))  # logical OR
heron_sqrt(2; stopping_criterion = criterion)

1.414213562373095

Conversely, to demand both a minimum iteration count and a time cap, use & (logical AND).

criterion = StopAfterIteration(25) & StopAfter(Millisecond(50))  # logical AND
heron_sqrt(2; stopping_criterion = criterion)

1.414213562373095

Implementing a new criterion

It is of course possible that we are not satisfied by the stopping criteria that are provided by default. Suppose we want to stop when successive iterates change by less than ϵ, we could achieve this by implementing our own stopping criterion. In order to do so, we need to define our own structs and implement the required interface. Again, we split up the data into a static part, the StoppingCriterion, and a dynamic part, the StoppingCriterionState.

struct StopWhenStable <: StoppingCriterion
    tol::Float64    # when do we consider things converged
end

mutable struct StopWhenStableState <: StoppingCriterionState
    previous_iterate::Float64       # previous value to compare to
    at_iteration::Int               # iteration at which stability was reached
    delta::Float64                  # difference between the values
end

Note that our mutable state holds both the previous_iterate, which we need to compare to, as well as the iteration at which the condition was satisfied. This is not strictly necessary, but can be convenient to have a persistent indication that convergence was reached.

Initialization

In order to support these stateful criteria, again an initialization phase is needed. This could be implemented as follows:

function AlgorithmsInterface.initialize_state(::Problem, ::Algorithm, c::StopWhenStable; kwargs...)
    return StopWhenStableState(NaN, -1, NaN)
end

function AlgorithmsInterface.initialize_state!(
        ::Problem, ::Algorithm, stop_when::StopWhenStable, st::StopWhenStableState;
        kwargs...
)
    st.previous_iterate = NaN
    st.at_iteration = -1
    st.delta = NaN
    return st
end

Checking for convergence

Then, we need to implement the logic that checks whether an algorithm has finished, which is achieved through is_finished and is_finished!. Here, the mutating version alters the stopping_criterion_state, and should therefore be called exactly once per iteration, while the non-mutating version is simply used to inspect the current status.

function AlgorithmsInterface.is_finished!(
        ::Problem, ::Algorithm, state::State, c::StopWhenStable, st::StopWhenStableState
)
    k = state.iteration
    if k == 0
        st.previous_iterate = state.iterate
        st.at_iteration = -1
        return false
    end

    st.delta = abs(state.iterate - st.previous_iterate)
    st.previous_iterate = state.iterate
    if st.delta < c.tol
        st.at_iteration = k
        return true
    end
    return false
end

function AlgorithmsInterface.is_finished(
        ::Problem, ::Algorithm, state::State, c::StopWhenStable, st::StopWhenStableState
)
    k = state.iteration
    k == 0 && return false

    Δ = abs(state.iterate - st.previous_iterate)
    return Δ < c.tol
end

Reason and convergence reporting

Finally, we need to say what our criterion reports once it has triggered. There are two separate questions here, and keeping them apart is what makes the generic reporting work:

Did this criterion indicate to stop? This is answered by is_active, and it is what all the generic machinery is built on.
Why, in words? This is answered by get_reason, and it is for human consumption only.

We get the first one for free. The default implementation of is_active reads the at_iteration property of the state, and our StopWhenStableState has one, following the convention that a negative value means "has not (yet) indicated to stop". Only a state that records its status some other way has to implement is_active itself.

That leaves the message, plus the static statement that meeting this criterion does mean convergence:

function AlgorithmsInterface.get_reason(c::StopWhenStable, st::StopWhenStableState)
    is_active(c, st) || return nothing
    return "The algorithm reached an approximate stable point after $(st.at_iteration) iterations; the change $(st.delta) is less than $(c.tol).\n"
end

AlgorithmsInterface.indicates_convergence(::Type{StopWhenStable}) = true

Note that get_reason gates on the recorded status rather than re-checking st.delta < c.tol. Re-checking the predicate would make the message disappear again as soon as the state moves on, whereas at_iteration is a permanent record of what happened.

Only the type-domain indicates_convergence needs to be defined. It answers "would meeting this criterion mean the algorithm converged?", which is a static property of the criterion type alone. The variant taking a criterion simply forwards to the type, and the two-argument variant, which additionally answers "did it happen?", is derived from it and is_active:

criterion = StopWhenStable(1e-8)
state = AlgorithmsInterface.initialize_state(SqrtProblem(16.0), HeronAlgorithm(criterion), criterion)
indicates_convergence(criterion), indicates_convergence(criterion, state)

(true, false)

The criterion always could indicate convergence, but its fresh state has not yet seen it happen.

This distinction matters most for composed criteria. A StopWhenStable(1e-8) | StopAfterIteration(5) can stop for either reason, so indicates_convergence of the group without a state is false since the group offers no guarantee. Given a state, it reports whether one of the children that actually triggered indicates convergence, which is what lets a caller tell "converged" apart from "ran out of iterations".

Both get_reason and the type-domain indicates_convergence have conservative defaults, nothing and false, so a criterion that has nothing to add does not have to implement them.

Querying the verdict

After a run, these same functions are how a caller finds out what happened. Since solve returns only the iterate, we use solve! with a state we hold on to:

function heron_verdict(x, criterion)
    problem = SqrtProblem(x)
    algorithm = HeronAlgorithm(criterion)
    state = AlgorithmsInterface.initialize_state(problem, algorithm)

    solve!(problem, algorithm, state)

    converged = indicates_convergence(algorithm, state)
    reason = get_reason(algorithm, state)
    active = [typeof(c) for (c, cs) in get_active_stopping_criteria(algorithm, state)]

    return converged, reason, active
end

heron_verdict(16.0, StopWhenStable(1e-8) | StopAfterIteration(50))

(true, "The algorithm reached an approximate stable point after 9 iterations; the change 1.5987211554602254e-14 is less than 1.0e-8.\n", DataType[Main.StopWhenStable])

These two-argument forms extract the criterion and its state for us, so there is no need to reach into algorithm.stopping_criterion and state.stopping_criterion_state by hand.

The very same criterion reports a different verdict when the budget is what runs out first:

heron_verdict(16.0, StopWhenStable(1e-8) | StopAfterIteration(5))

(false, "At iteration 5 the algorithm reached its maximal number of iterations (5).\n", DataType[StopAfterIteration])

This is the distinction the whole two-argument machinery exists for. Note also that convergence is a coarse verdict: an iteration cap and a collapsed step size both fail to indicate convergence while calling for quite different responses. That is what get_active_stopping_criteria is for — it reports exactly which criteria became active, recursing through any StopWhenAll and StopWhenAny so that the groups themselves never show up.

The logging system offers StopReasonAction to report the reason at the :Stop context, without having to hold on to the state at all.

Convergence in action

Then we are finally ready to test out our new stopping criterion.

criterion = StopWhenStable(1e-8)
heron_sqrt(16.0; stopping_criterion = criterion)

4.0

Note that our work paid off, as we can still compose this stopping criterion with other criteria as well:

criterion = StopWhenStable(1e-8) | StopAfterIteration(5)
heron_sqrt(16.0; stopping_criterion = criterion)

4.0000989506882485

Summary

Implementing a criterion usually means defining:

A subtype of StoppingCriterion.
A state subtype of StoppingCriterionState capturing dynamic fields, including an at_iteration recording when the criterion triggered.
initialize_state and initialize_state! for setup/reset.
is_finished! (mutating) and optionally is_finished (non‑mutating) variants.
get_reason (return nothing or a string) for user feedback, gated on is_active.
indicates_convergence(::Type{YourCriterion}) to mark if meeting it implies convergence. The (criterion,) and the (criterion, criterion_state) variant are derived from this one and do not need to be defined.

You may also implement Base.summary(io, criterion, criterion_state) for compact status reports, and is_active(criterion, criterion_state) if your state does not record its status in an at_iteration property.

Reference API

Below are the auto‑generated docs for all stopping criterion infrastructure.

AlgorithmsInterface.DefaultStoppingCriterionState — Type

DefaultStoppingCriterionState <: StoppingCriterionState

A StoppingCriterionState that does not require any information besides storing the iteration number at which it (last) indicated to stop.

Fields

at_iteration::Int stores the iteration number at which this state indicated to stop.
- 0 means it already indicated to stop at the start.
- any negative number means that it has not yet indicated to stop.