Clinch

Clinch (Certified Local Interval-Newton Convergence for Hierarchies) proves that a fitted optimum of a hierarchical statistical model is a strict local optimum, or names the test that failed. The input is the fitted parameter vector and an evaluator for the model's gradient and Hessian written in ball arithmeticevery number is stored as a midpoint and a radius that provably contains the true value, so all rounding error is tracked. The proof is the interval Newton test of R. Krawczyk and R. E. Moore, run block by block by Baller.

Where it comes from

L. Mizrahi, S. Nandan and S. Wiemer wrote the etas package, which fits the ETAS model of Y. Ogata (a self-exciting point process). One part of Clinch, the ETAS adapter in adapters/certpass/, certifies optima fitted by that package. The adapter follows the code of the etas package at commit 097f08b6 and was written with that code open.

Part of ClinchSourceAuthors
Copied unchanged: upper_gamma_ext and the parameter boundsetas/inversion.pyL. Mizrahi, S. Nandan and S. Wiemer
Copied unchanged: round_half_upetas/mc_b_est.pyThe same authors
Follows their code: the pair table, the check of the expectation step and the source integral, rewritten in vectorized formetas/inversion.pyThe same authors
Imported for reference values, by etas_dump.pyThe installed etas packageThe same authors
New code: the ball-arithmetic evaluator of the ETAS likelihood, its derivatives, the identity checks and the certificatesThe likelihood as the etas package implements itCode by Claude
New code: the engine, the tests and the other evaluatorsThe papers under Source and referencesCode by Claude

The copied and followed parts are in twin_etas.py, assemble_etas_np.py, run_etas.py and recertify_taupinned.py. Please cite the authors' paper when you use the ETAS adapter. Clinch is not affiliated with or endorsed by them.

What it does

An optimizer reports convergence when the gradient is small. Everything computed afterward (standard errors, likelihood-ratio tests, model comparison) assumes that the optimizer stopped at a true strict local minimum. Clinch proves that assumption or reports why it cannot.

Clinch works in ball arithmetic (Arb, through python-flint) and applies the Krawczyk test, an interval form of Newton's method. Let $F$ be the gradient, $H(X)$ the Hessian enclosed over a box $X$ around the candidate $\tilde x$, and $C$ an approximate inverse of the midpoint Hessian. If

$$K(X) \;=\; \tilde x - C\,F(\tilde x) + \bigl(I - C\,H(X)\bigr)(X - \tilde x)$$

lies strictly inside $X$, then a zero of $F$ exists in $X$ and is unique there. A second test proves every symmetric matrix in $H(X)$ positive definite, so that zero is a strict local minimum.

Hierarchical (mixed, random-effects) models have a block-arrow Hessian: independent diagonal blocks, one per group of latent parameters, coupled only through a dense border of global parameters. The kernel Clinch calls, baller.certify.block_krawczyk in Baller, runs both tests block by block with an interval Schur complement on the border. A fit with about 5,600 coordinates in 582 blocks certifies at the default 192-bit precision. Clinch adds the model evaluators, the choice of box, the handling of bounds and the certificate files.

Clinch returns one of four verdicts:

The code chooses the box. Radii are scaled per coordinate by the local curvature and start at twice the candidate's own Newton step. Boxes 1, 2, 4 and 8 times that size are tried, and no radius may exceed one curvature standard deviation. A wide box around a poorly converged point would be a true statement of little value, so Clinch refuses and reports how far from stationary the candidate is.

Clinch has these limits:

Examples

Run the self-test. With the package set up (see Requirements), run from the package directory tools/clinch/, in a checkout that also contains tools/baller/:

python3 selftest.py

The script runs the tests L1 through L8 from a fresh scratch directory and prints a PASS or FAIL line per test, then an OVERALL line. L3, L6 and one part of L4 read stored results of BootLoops' reference fits, which are not distributed. On a public checkout the script reports the missing files and still ends with a line beginning clinch selftest PASS and exit status 0.

Certify a known optimum from Python. Test L1 reduced to its core, on the synthetic test problem (two latent blocks of sizes 3 and 2, three global parameters, exact optimum known):

import sys
sys.path.insert(0, "tools/baller"); sys.path.insert(0, "tools/clinch")
sys.path.insert(0, "tools/clinch/battery")
import clinch
clinch.verify(quiet=True)
from synthetic import SynthOracle, exact_optimum
from clinch import engine, cert
zs_ex, g_ex = exact_optimum()
theta = [float(v) for v in zs_ex[0] + zs_ex[1] + g_ex]
res = engine.certify(SynthOracle(), theta, prec=128)
assert res["verdict"] == "CERTIFIED-INTERIOR", res["verdict"]
cert.write_cert(res, out_dir, "synthetic")

res holds the verdict, the per-coordinate radius range (radius_min, radius), the precision and the box sizes tried. Under krawczyk it lists the contraction margin of each named block and of the border (each provably below 1), and under pd the positive-definiteness margins (each provably above 0). write_cert writes CERT.json with those fields and STATEMENT.txt, one plain paragraph stating what was proven, into out_dir (any writable directory).

The same test then certifies a candidate held exactly at a declared lower bound with engine.certify(base, list(th), bounds=(lo, None), prec=128). That call returns CERTIFIED-CORNER with the certified multiplier signs under kkt. Without bounds the same candidate is REFUSED with failed == "fat-ball".

Polish, then certify. Expect a refusal for a point taken straight from a general-purpose optimizer: the candidate is too far from stationary. The remedy is newton_polish, a few structured Newton steps, followed by a certificate at the polished point, as in the manual's quick start:

thp, prcpt = engine.newton_polish(o, theta)     # labeled second product
resp = engine.certify(o, thp)                   # polished-center cert

prcpt["distance_inf"] is the largest coordinate change the polish made. Report it beside the certificate so that a reader knows which point was certified.

Routines

The Python package is clinch.

FunctionWhat it returns
clinch.verify(quiet=False)A dictionary whose key pinned_ok lists the modules that match the checksums in _pins.py; raises ClinchTamperError on a mismatch
engine.certify(o, theta, bounds=(lo, hi))The verdict dictionary for candidate theta and evaluator o; bounds, prec (bits) and budget_s are optional
engine.certify_guarded(make_oracle, theta)As certify, from a function that builds the evaluator; a parameter-layout refusal during construction becomes OUT-OF-SCOPE
engine.newton_polish(o, theta)(theta_polished, record) from a structured Newton polish in floating point; the record holds distance_inf
cert.write_cert(res, out_dir, model_tag)The certificate, after writing CERT.json and STATEMENT.txt; cert.human_statement returns the paragraph alone
jets.Jet, jconst, jvarValue, gradient and Hessian over arb balls in up to three variables
oracle_v31.ModelV31Oracle, oracle_v36.ModelV36OracleEvaluators for the hierarchical ecological model and its mean-centered variant
EtienneSSOracle, EtienneEqIOracle, EtienneCornerOracle, EtienneDiffIOracleEvaluators for the negative log-likelihood of Etienne's sampling formula, in the four cases below
oracle_coded.CodedOracle, oracle_cond.CondOracle, oracle_etas.EtasOracleEvaluators in adapters/certpass/ for a capped-count Poisson regression, a conditional multinomial fit and the ETAS likelihood

The mean-centered evaluator carries equality constraints, so its extended Jacobian is indefinite by construction. For it engine.certify pairs the Krawczyk test with kkt_pd.pd_reduced_congruence, which proves the Hessian positive definite on the constraint surface.

The four Etienne evaluators, in adapters/etienne/, cover in order: one sample; several samples sharing one immigration parameter; fits on the boundary $q = 1/I = 0$; and a 65-sample fit. The boundary is treated as a declared lower bound. The 65-sample fit has one immigration parameter per sample (66 parameters, one dense block).

The census in census/repertoire_g1/ covers the equilibria of a clone-competition model family at 128-bit precision. Its driver is g1_run, with the subcommands bench, batch and assemble, and its output goes to the directory named by G1_OUT (default ./g1_out). Every case is disposed by exactly one certificate class, and undecided cases are recorded as undecided, never forced.

MANUAL.md describes the modules of the clinch package and the tests L1 through L8.

Requirements

Source and references

The code is tools/clinch/ in the BootLoops repository, with GUIDE.md (summary) and MANUAL.md (full detail) beside it. adapters/certpass/PROVENANCE.md holds the third-party notice for the two copied functions.

ReferenceWhat it supplies
R. Krawczyk, Computing 4 (1969) 187The Krawczyk operator
R. E. Moore, SIAM J. Numer. Anal. 14 (1977) 611The interior test
S. M. Rump, Acta Numerica 19 (2010) 287The rules of verified computation that the certificate follows
F. Johansson, IEEE Trans. Comput. 66 (2017) 1281, arXiv:1611.02831Arb, the ball arithmetic, used through python-flint
L. Mizrahi, S. Nandan and S. Wiemer, Seismol. Res. Lett. 92 (2021) 2333, doi:10.1785/0220200231; code: etasThe package whose fits the ETAS adapter certifies, and the code listed under Where it comes from
Y. Ogata, JASA 83 (1988) 9The ETAS model
Veen and Schoenberg, JASA 103 (2008) 614The expectation-maximization (EM) fit that the etas package follows
Etienne, Ecol. Lett. 8 (2005) 253; 10 (2007) 608The sampling formula of the Etienne adapter
Etienne, J. Theor. Biol. 257 (2009) 510The likelihood with one immigration parameter per sample

← back to the tools index