Problem classes

AbstractProblem

Root of the problem-class hierarchy. A concrete problem declares its regime by subtyping DeterministicProblem, ExpectationProblem or FiniteSumProblem, and the solver, the model Hessian and the sampling rule are all checked against that declaration at construction.

Ordinary JSO models (ADNLPModel, CUTEstModel, …) are not subtypes: they are deterministic by default and need no wrapper. underlying_problem returns nothing for them, which is what the compatibility checks test.

DeterministicProblem <: AbstractProblem

f(x) is evaluated exactly. No batch, no sampling rule, no variance estimate.

Solved by DeterministicTRSolver. Most users never subtype this — a plain AbstractNLPModel is treated as deterministic. It exists for the full-batch view of a sampled problem, FullBatchNLP, which is deterministic while still carrying the finite-sum problem underneath so that BHHHModel remains legal.

SampledProblem <: AbstractProblem

f(x) is estimated from a sample drawn afresh at each iteration. The common supertype of ExpectationProblem and FiniteSumProblem; dispatch on it for anything that applies to both, on the two children for anything that does not.

ExpectationProblem <: SampledProblem

f(x) = E_ξ[F(x,ξ)] with an unbounded population: realisations are drawn i.i.d. from a distribution, never from a finite list.

Consequences the type carries:

• population(p) == typemax(Int); N_k is capped only by the user's budget.
• There is no full-batch iteration and no exact evaluation, so the accuracy hypotheses of the stochastic convergence theory can never be discharged.
• has_truth(p) is false unless the construction happens to supply the exact mean — PerturbedExpectation does, a general one does not.

Solved by ExpectationTRSolver.

FiniteSumProblem <: SampledProblem

f(x) = (1/M) Σ_{i=1}^{M} f_i(x) with M finite and known: sampling means subsetting 1:M.

Consequences the type carries:

• population(p) == M, so N_k ≤ M is imposed by the problem. A sampling rule used here must not carry a user-supplied N_max; pass budget to FiniteSumTRSolver if a sub-population cap is genuinely wanted.
• N_k = M is an exact iteration. FullBatch reaches it deliberately, and :full_batch_trajectory records when it happened.
• true_objective and true_gradient are always available, at one full pass, so has_truth is true for the whole class.

Solved by FiniteSumTRSolver.

ScoredProblem <: FiniteSumProblem

A finite-sum problem that reports the gradient of each term separately:

scores(p, x, batch)     -> n × |batch| Matrix, column i = ∇f_i(x)
loss_terms(p, x, batch) -> |batch| Vector, entry i = f_i(x)

The column mean is the gradient, so this is strictly more information than a gradient evaluation and usually costs no more to produce. It is what the inner-product sampling rules and the outer-product model Hessians consume.

Scores sit under FiniteSumProblem because every scored construction here is a dataset. An expectation with per-realisation scores is coherent and would need a parallel branch; has_scores is the trait to dispatch on if you add one.

LikelihoodProblem <: ScoredProblem

f(x) = −(1/M) Σ ln p_i(x), an average negative log-likelihood.

This is the class in which BHHH is justified, and the reason it is a type rather than a docstring: required_problem(::BHHHModel) === LikelihoodProblem, so BHHHModel over anything else is an ArgumentError at solver construction rather than a silently meaningless matrix.

The justification is the information identity V = −H, which holds for a correctly specified model at the true parameters. Belonging to this type asserts the first half only — that f is a negative log-likelihood and the scores are its per-observation gradients. Whether the model is correctly specified is a statement about the data that no type can carry, which is what information_identity_error is for.

NLSProblem <: LikelihoodProblem

f(x) = (1/2M) Σ r_i(x)², nonlinear least squares, additionally supplying

residuals(p, x, batch) -> Vector
jacobian(p, x, batch)  -> |batch| × n Matrix

Placed under LikelihoodProblem because it is one: least squares is maximum likelihood under i.i.d. Gaussian errors of known variance, and the score r_i ∇r_i is the log-likelihood score up to σ². So BHHH applies here as well as Gauss-Newton, and the two can be compared on one problem — which is worth having, since they discard different terms and fail for different reasons.

required_problem(::GaussNewtonModel) === NLSProblem: the Jacobian is what it needs and nothing above this type has one.

problem_class(p) -> Symbol

:deterministic, :expectation or :finite_sum. Used in error messages and in the benchmark tables, where a run's regime must be reported alongside its cost.

population(p) -> Int

The number of terms available. M for a finite sum, typemax(Int) for an expectation — not an error, because "unbounded" is exactly what the sampling layer needs to know: it is the value N_k is capped against, and capping against typemax(Int) is a no-op.

n_terms(p) -> Int

Alias of population, kept because it appears in the default argument of information_identity_error and gauss_newton_error.

has_scores(p) -> Bool

Whether per-observation gradients are available. true for the whole of ScoredProblem and its descendants.

Checked once, at oracle construction, against needs_scores on the sampling rule — the inner-product family needs Var(∇F_iᵀĝ) and cannot estimate it from a batch gradient alone.

has_truth(p) -> Bool

Whether f and ∇f can be evaluated exactly, so a run can be scored on the truth rather than on its own estimates.

true for every FiniteSumProblem — one full pass. For an ExpectationProblem it is false unless the construction supplies the exact mean, which PerturbedExpectation does by design.

This gates TRParams(true_stop = true) and the :true_grad_trajectory entry: requesting either on a problem without truth is an ArgumentError, not a silent fallback to the batch estimate.

full_batch(p::FiniteSumProblem) -> Vector{Int}

The whole index set 1:M. A finite-sum iteration on this batch is exactly deterministic, which is the limit an expectation does not have.

underlying_problem(nlp) -> AbstractProblem or nothing

The AbstractProblem an NLP oracle presents, or nothing for a plain JSO model. This is what the model-Hessian compatibility check dispatches on: a raw ADNLPModel returns nothing, so a model requiring LikelihoodProblem is rejected against it.

required_problem(model) -> Type

The narrowest problem class a ModelHessian is defined for. AbstractProblem — "anything, including a plain NLP" — by default.

The three outer-product models narrow it, which is the point of the hierarchy:

Checked by check_model_problem at solver construction, so the failure is a constructor error naming both types rather than a matrix that means nothing.

check_model_problem(model, nlp) -> nothing

Throw an ArgumentError if model requires a narrower problem class than nlp provides. Called by all three solver constructors.

check_rule_problem(rule, prob) -> nothing

Throw an ArgumentError if a sampling rule needs per-observation scores and the problem does not supply them. Called by the two sampled oracle constructors.

check_population_cap(rule, prob) -> nothing

Throw an ArgumentError if a rule used on a FiniteSumProblem carries a user-supplied N_max.

For a finite sum the cap is M, imposed by the problem. A user N_max there is either redundant (≥ M) or a deliberate sub-population budget (< M), and those are different intentions that should not share a keyword — the first hides a misunderstanding, the second is a legitimate experiment. Pass budget to FiniteSumTRSolver for the second.

On an ExpectationProblem nothing is checked: there the population is unbounded and the cap is the user's budget.

user_cap(rule) -> Int or nothing

The N_max the user supplied, or nothing when they supplied none.

Distinct from sample_cap, which resolves to typemax(Int) so it can be used in arithmetic. This one preserves the difference between "unset" and "set to a large number", which is what check_population_cap needs.

DeterministicTRSolver(nlp; rule, model, subsolver, params, x_ref,
                      true_curvature, hessian_norm)

Trust-region solver for a problem evaluated exactly: any AbstractNLPModel, or the full-batch view FullBatchNLP of a finite sum.

Accepts no sampling rule. It has no resample!, no variance estimate and no sample counters, and any TRParams(true_stop = …) other than :none is rejected — the batch test is the true test here, so confirming it against the truth is meaningless rather than merely redundant.

stats = tr_solve(nlp; rule = RGrad(), model = SR1Model(mem = 5),
                 subsolver = SteihaugCG(), params = TRParams(tol = 1e-8))

ExpectationTRSolver(nlp; rule, model, subsolver, params, x_ref,
                    true_curvature, hessian_norm)

Trust-region solver for an ExpectationNLP.

The sampling rule lives on the oracle, not here — it decides what the oracle returns, so it belongs with the oracle. So does the budget: budget is a keyword of ExpectationNLP, not of this constructor. It is a safety cap on N_k applied on top of the rule's own N_max; the accuracy theory imposes none, so without a cap a criticality-anchored mechanism will ask for Θ(Δ_k^{-4}) objective terms and get it.

TRParams(true_stop = :full) and :both require has_truth(prob). That is true for PerturbedExpectation, which supplies the exact mean by construction, and false for a general expectation — where the request is not conservative but impossible, and is refused rather than silently downgraded to the batch test.

:test is available on every expectation: it consults only σ_g and N_k, both of which the oracle already maintains, and asserts nothing it cannot support.

FiniteSumTRSolver(nlp; rule, model, subsolver, params)

Trust-region solver for a FiniteSumNLP.

Every TRParams(true_stop = …) mode is available here: has_truth holds for the whole class, so :full and :both can confirm exactly, at the cost of one full pass per confirmation. :both pays that cost only when the batch cannot settle the question on its own, and is the mode to prefer.

FullBatchNLP(prob; x0)

The exact view of a FiniteSumProblem: every term evaluated at every call.

Deterministic, so it goes to DeterministicTRSolver — while underlying_problem still reports the finite-sum problem, so required_problem checks pass and BHHHModel over a likelihood remains legal. That combination is the reason this is a separate type rather than a FiniteSumNLP with FullBatch(): the two are numerically identical and structurally different, and the second still carries a sampling rule, a batch, a variance estimate and an RNG that mean nothing.

The dense Hessian is cached per iterate: batch_hess is a pure function of x here, and on MLPClassifier it costs O(n) gradient evaluations, so recomputing it inside every hprod! made ExactHessian unusable on the problems the BHHH comparison needs it for.

The former name LikelihoodNLP remains as an alias.

ExpectationNLP(prob, rule; x0, seed = 0, N_init = 8)

Oracle for an ExpectationProblem: each resample! draws N_k fresh realisations.

There is no population cap of the problem's own, so the budget comes from the rule's N_max and from ExpectationTRSolver's budget. There is no full-batch iteration and, unless has_truth(prob), no exact gradient — so a run here can be scored only against whatever the construction supplies.

FiniteSumNLP(prob, rule; x0, seed = 0, replace = true, N_init = 8, budget = nothing)

Oracle for a FiniteSumProblem: each resample! subsets 1:M.

N_k ≤ M always. A rule carrying a user-supplied N_max is rejected here — see check_population_cap — because on a finite sum the cap is a property of the problem; budget is where a deliberate sub-population limit belongs.

:full_batch_trajectory records the iterations at which N_k = M, which are exactly the iterations that were deterministic.

SampledNLP{T, V} <: AbstractNLPModel{T, V}

Common supertype of ExpectationNLP and FiniteSumNLP. Everything that does not depend on the population — evaluation, the Hessian cache, the counters, the variance estimates, reset_sampling! — is defined once here.

Common random numbers

The batch is redrawn once per iteration, in resample!, and then held fixed. Every evaluation within the iteration — f̂(x_k), f̂(x_k + s_k), and the retrospective f̂ if the rule needs it — uses the same realisations.

That is not an optimisation. With independent draws the variance of f̂(x_k) − f̂(x_k + s_k) does not shrink as ‖s_k‖ → 0, so ρ̂ becomes pure noise at small radii and every mechanism stalls for a reason that has nothing to do with the mechanism.

population_cap(m) -> Int

The largest sample the oracle will ever draw: the solver budget for an expectation, min(budget, M) for a finite sum. N_k is clamped to it after the rule has spoken, and hitting it is counted in m.capped — a run spent at the cap is no longer meeting the accuracy requirement the convergence theory assumes.