Linear Solver Stop Criteria

LinSysStopCriterion

Abstract supertype for specifying stopping criteria for randomized linear solver.

LSStopMaxIterations <: LinSysStopCriterion

A structure that specifies a maximum iteration stopping criterion. That is, once a method achieves a certain number of iterations, it stops.

Fields

• max_iter::Int64, the maximum number of iterations.

LSStopThreshold <: LinSysStopCriterion

A structure that specifies a threshold for sufficient progress as a stopping critertion. That is, once a progress estimator achieves a certain quality of solution, it stops.

Fields

• max_iter::Int64, the maximum number of iterations.
• threshold::Float64, the value threshold for when sufficient progress has been achieved.

LSStopMA <: LinSysStopCriterion

A structure that specifies a stopping criterion that incoroporates the randomness of the moving average estimator. That is, once a method achieves a certain number of iterations, it stops.

Fields

• max_iter::Int64, the maximum number of iterations.
• threshold::Float64, the value of the estimator that is sufficient progress.
• delta1::Float64, the percent below the threshold does the true value of the progress estimator need to be for not stopping to be a mistake. This is equivalent to stopping too late.
• delta2::Float64, the percent above the threshold does the true value of the progress estimator need to be for stopping to be a mistake. This is equivalent to stopping too early.
• chi1::Float64, the probability that the stopping too late action occurs.
• chi2::Float64, the probability that the stopping too early action occurs.

Constructors

• Calling LSStopMA(iter) will specify the users desired maximum number of iterations, threshold = 1e-10, delta1 = .9, delta2 = 1.1, chi1 = 0.01, and chi2 = 0.01.

check_stop_criterion(
    log::LinSysSolverLog,
    stop::LinSysStopCriterion
    )

A common interface for specifying different strategies for stopping log with supertype LinSysSolverLog. A stop of supertype LinSysStopCriterion can be used to provide specific multiple implementations of stopping conditions for the same log type.

iota_threshold(hist::LSLogMA, stop::LSStopMA)

Function that computes the stopping criterion using the sub-Exponential distribution from the LSLogMA, and the stopping criterion information in LSSopMA. This function is not exported and thus not directly callable by the user.

Inputs

• hist::LSLogMA, the log information for the moving average tracking.
• stop::LSStopMA, the stopping information for the stopping criterion.

Ouputs

Returns the stoppping criterion value.

Pritchard, Nathaniel, and Vivak Patel. "Solving, Tracking and Stopping Streaming Linear Inverse Problems." arXiv preprint arXiv:2201.05741 (2024).