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 Clinch | Source | Authors |
|---|---|---|
Copied unchanged: upper_gamma_ext and the parameter bounds | etas/inversion.py | L. Mizrahi, S. Nandan and S. Wiemer |
Copied unchanged: round_half_up | etas/mc_b_est.py | The same authors |
| Follows their code: the pair table, the check of the expectation step and the source integral, rewritten in vectorized form | etas/inversion.py | The same authors |
Imported for reference values, by etas_dump.py | The installed etas package | The same authors |
| New code: the ball-arithmetic evaluator of the ETAS likelihood, its derivatives, the identity checks and the certificates | The likelihood as the etas package implements it | Code by Claude |
| New code: the engine, the tests and the other evaluators | The papers under Source and references | Code 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:
CERTIFIED-INTERIOR. The box contains exactly one stationary point, with a positive-definite Hessian throughout, and no bound is active.CERTIFIED-CORNER. Some coordinates sit exactly on bounds you declared. The free coordinates certify and the sign of each active bound's multiplier is proven over the box, which gives a strict local minimum of the bounded problem.REFUSED. Clinch names what failed and by what margin. The causes are a block or the border that did not contract, a block that is not positive definite, a candidate too far from stationary, and the 30-minute time budget.OUT-OF-SCOPE. The evaluator does not cover the model's parameter layout.
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:
- Every statement from
engine.certifyis local. It claims nothing about global optimality. - The objective must be smooth over the box.
- The certified target is the unclipped objective. An evaluator for a model that clips probabilities must check each clip over the box and report any it cannot prove inactive.
- The evaluator must use ball arithmetic end to end (the
jetsmodule helps). A quantity whose enclosure leaves its domain becomes a refusal. - The evaluators included cover the large hierarchical ecological model the package was first written for (species-, genus- and family-level effects under shared global parameters) and Etienne's sampling formula from neutral community ecology. The others are listed under Routines.
- For another model you write an object with the same small interface (
dims,part,F(x),H(x)). The synthetic test problemSynthOracleinbattery/synthetic.pyis a complete short example.
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.
| Function | What 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, jvar | Value, gradient and Hessian over arb balls in up to three variables |
oracle_v31.ModelV31Oracle, oracle_v36.ModelV36Oracle | Evaluators for the hierarchical ecological model and its mean-centered variant |
EtienneSSOracle, EtienneEqIOracle, EtienneCornerOracle, EtienneDiffIOracle | Evaluators for the negative log-likelihood of Etienne's sampling formula, in the four cases below |
oracle_coded.CodedOracle, oracle_cond.CondOracle, oracle_etas.EtasOracle | Evaluators 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
- Runs on: Python 3 with
python-flint(Arb ball arithmetic), NumPy andmpmath. Files ofadapters/certpass/also import SciPy and pandas, andetas_dump.pyimports the installedetaspackage. - Install: keep Baller beside Clinch as in the repository (
tools/baller/next totools/clinch/), or setCLINCH_BALLER_DIR. - Self-test:
python3 selftest.pyfrom the package directory ends with a line beginningclinch selftest PASSand exit status 0. - Etienne adapter:
python3 -m etienne.battery_etienne [--fast]runs its tests E1 through E7. It imports the ecology study's code and data from the directory named byCLINCH_ETIENNE_DIRand writes underCLINCH_RECEIPTS_DIR. The study's data are not distributed. The four kernel files that it checks by checksum also come with Mixalot, intools/mixalot/mixalot/vendor/eco/pilot/. - Reference data: the reference fits, the studies' data and their stored results are not distributed. The reference loaders find a local copy through
CLINCH_REFERENCE_DIRandCLINCH_CODE_DIR, thecertpassdrivers throughCERTPASS_REFERENCE_DIR. They stop with a message when the variable is unset.
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.
| Reference | What it supplies |
|---|---|
| R. Krawczyk, Computing 4 (1969) 187 | The Krawczyk operator |
| R. E. Moore, SIAM J. Numer. Anal. 14 (1977) 611 | The interior test |
| S. M. Rump, Acta Numerica 19 (2010) 287 | The rules of verified computation that the certificate follows |
| F. Johansson, IEEE Trans. Comput. 66 (2017) 1281, arXiv:1611.02831 | Arb, 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: etas | The package whose fits the ETAS adapter certifies, and the code listed under Where it comes from |
| Y. Ogata, JASA 83 (1988) 9 | The ETAS model |
| Veen and Schoenberg, JASA 103 (2008) 614 | The expectation-maximization (EM) fit that the etas package follows |
| Etienne, Ecol. Lett. 8 (2005) 253; 10 (2007) 608 | The sampling formula of the Etienne adapter |
| Etienne, J. Theor. Biol. 257 (2009) 510 | The likelihood with one immigration parameter per sample |