△ Mechanism confirmed, baseline not beaten 2026

Extreme-Marginal Conditioning Certificate

Implementation & benchmark of arXiv:2607.12286 — Structured Preconditioning in Affine-Invariant Geometry: Projection, Certificates, and Kronecker Separation

Usefulness7/10

Difficulty7/10

Novelty8/10

Optimization Stability Accuracy Speedup Optimizer Training Mlp Transformer Spectral theory Linear algebra Optimization Geometry

Source paper: Structured Preconditioning in Affine-Invariant Geometry: Projection, Certificates, and Kronecker Separation arXiv:2607.12286 ⓘ · analyzed Aug 30, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Use the extreme-eigenvector marginal test to decide whether a Kronecker preconditioner is condition-optimal, rather than blindly running expensive factor refinement. If the certificate fails, construct a low-cost factor correction from the mismatch between tensor marginals of the worst-conditioned spectral states and accept it only with a condition-number line search.

Formulas

$$\kappa(G^{-1}H)=\kappa(H^{-1/2}GH^{-1/2})=\frac{\lambda_{\max}(C)}{\lambda_{\min}(C)},\qquad C=H^{-1/2}GH^{-1/2}.$$

$$u\in\mathbb R^{pq},\quad U=\operatorname{reshape}(u,p,q),\quad M_p(u)=UU^T,\quad M_q(u)=U^TU.$$

$$\Delta(G)=\left\|M_p(u_{\max})-M_p(u_{\min})\right\|_F+\left\|M_q(u_{\max})-M_q(u_{\min})\right\|_F.$$

$$D_A=M_p(u_{\min})-M_p(u_{\max}),\quad D_B=M_q(u_{\min})-M_q(u_{\max}),\quad A'=A^{1/2}e^{\pm\alpha D_A}A^{1/2},\quad B'=B^{1/2}e^{\pm\alpha D_B}B^{1/2}.$$

Mathematical statement

For SPD curvature H and structured preconditioner G = A tensor B, define C = H^(-1/2) G H^(-1/2), whose eigenvalues satisfy 0 < lambda_min <= lambda_max. The relative condition number is kappa(G^(-1)H) = kappa(C) = lambda_max divided by lambda_min. Let u_min and u_max be normalized eigenvectors of C associated with lambda_min and lambda_max. Reshape each vector u in R^(pq) into U in R^(p by q), and define tensor marginals M_p(u) = U U^T and M_q(u) = U^T U. The paper's condition-optimality criterion states that a Kronecker projection is condition-optimal when the extreme spectral states have identical tensor marginals: M_p(u_min) = M_p(u_max) and M_q(u_min) = M_q(u_max). Use the mismatch Delta = ||M_p(u_max) - M_p(u_min)||_F + ||M_q(u_max) - M_q(u_min)||_F as a stopping certificate. When Delta is nonzero, use D_A = M_p(u_min) - M_p(u_max) and D_B = M_q(u_min) - M_q(u_max) as theorem-guided candidate directions; test both signs because the practical sign depends on whether the implementation optimizes C or its inverse.

Implementation notes

Attach this monitor to the affine-invariant Kronecker preconditioner or to an existing Kronecker optimizer. At a refresh interval K, form the whitened relative operator C = H^(-1/2) G H^(-1/2) implicitly and use Lanczos or randomized power iteration to estimate its largest and smallest eigenpairs. For the largest eigenpair, run Lanczos on C. For the smallest, run Lanczos on C^(-1), applying C^(-1) through conjugate-gradient solves rather than explicitly inverting matrices. Normalize both eigenvectors, reshape each pq-vector into a p by q matrix, compute M_p = U U^T and M_q = U^T U, and then compute Delta. If Delta is below a tolerance tau, skip factor refinement because the extreme-state certificate predicts that the projection is already condition-optimal. If Delta is at least tau, build D_A and D_B from the marginal differences, try both signs and several small alpha values using SPD exponential maps, and retain the candidate that decreases the estimated ratio lambda_max divided by lambda_min. The exact mathematical quantities are the relative spectrum, extreme eigenvectors, tensor marginals, and zero-mismatch certificate; Lanczos accuracy and candidate line search are empirical approximations. Start with a p = q = 32 MLP layer on CIFAR-10 or one Transformer feed-forward block, comparing unconditional projection refinement against certificate-gated refinement. Log Delta, estimated condition number, training loss per step, eigensolver time, and wall-clock time. The desired signal is that many refinements are skipped when Delta is small, while large-mismatch cases show lower estimated condition number and faster loss descent. A negative result is increased eigensolver overhead without improved optimization at equal wall-clock time.

Verification

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Inconclusive

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 8/10

Built a readable exact-eigensolver MVP for the extreme-marginal certificate, marginal-guided SPD exponential corrections, sign/alpha line search, and a small preconditioned quadratic comparison. The mechanism manifested: the 2x2 marginal sweep matched the derived Delta=sqrt(2)sin(theta) prediction to 1.1e-16, while Delta remained constant as the spectral condition number varied. On the synthetic 3x3 Kronecker problem, line search reduced estimated condition number from 79.12 to 38.08 and reduced step-30 quadratic loss from 0.00958 to 0.00276, though this is not evidence of a general ML win.

Agent confidence: 8/10

Baseline: Synthetic quadratic: condition number 79.1206; loss at step 30 = 0.0095786; initial loss = 0.615923.
Idea: Certificate-guided correction: condition number 38.0797 using sign +1, alpha 0.8; loss at step 30 = 0.00275794; initial loss = 0.615923. Marginal prediction maximum absolute error = 1.11e-16; spectral-sweep Delta range = 0.0 while kappa ranged from 1.8333 to 166.667.

Limitations: Only small synthetic SPD/quadratic problems were tested; no CIFAR/MLP training, stochastic gradients, wall-clock training comparison, Lanczos/CG approximation, refresh gating frequency, or GPU implementation was evaluated. The exact certificate uses dense eigendecompositions, so scalability and practical eigensolver overhead remain untested.

How to run: python3 experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2607.12286) Sep 2, 2026

Ahead of the baseline (−10.0%) but not statistically significant (p=0.2374, wins 5 / 8 paired seeds).

Benchmark: Tabular regression (Friedman)
Model: mlp_tiny
Paired seeds: 8
Baseline mean: 14.7501
Idea mean: 13.2807
Effect (Δ): -1.4695 (−10.0%; negative = idea better)
Wins: 5 / 8 paired seeds
p-value: 0.2374 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±16.8%
Mechanism: Confirmed ✓
Practical effect: Inconclusive
Baseline tuning: swept over 3 configs

Limitations:

Only the structurally matched tabular/Friedman#1 track and mlp_tiny model were tested; vision, sequence, and dynamics tracks were not evaluated. The implementation uses minibatch diagonal empirical curvature and a diagonal approximation to the Kronecker correction rather than Lanczos/CG on a dense Hessian, and no wall-clock speedup was established.

How to run: python3 stage2_bench.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Aug 31, 2026 latest Failed ✗

Agent confidence: 9/10

Implemented the extreme-marginal certificate as a certificate-gated Kronecker-style gradient preconditioner on the structurally matched tabular MLP track, with identical 3-configuration sweeps for baseline and idea. The idea improved mean test MSE from 14.7501 to 13.2807 (delta -1.4695, 5/8 wins), but the paired permutation p-value was 0.2374, yielding the harness verdict "no significant win". The trained-model mechanism signature was confirmed: observed corrected relative condition decreased from 47793.0 to 27638.1 with a 34.7% accepted-correction fraction.

Baseline: Best Adam config lr=0.003, weight_decay=0.0001; mean test MSE 14.750141620635986; per-seed [16.789127349853516, 12.572675704956055, 13.758902549743652, 15.026583671569824, 14.131619453430176, 12.001730918884277, 16.066631317138672, 17.65386199951172].
Idea: Best certificate-gated preconditioner config lr=0.003, weight_decay=0.0001; mean test MSE 13.280670881271362; paired delta -1.469470739364624; permutation p=0.2374; per-seed [17.312753677368164, 11.368658065795898, 7.711630821228027, 13.712480545043945, 11.744468688964844, 13.272930145263672, 11.026009559631348, 20.096435546875].
Mechanism signature: Observed from trained models: delta_mean 1.8790707981531405; raw_condition_mean 47793.0335754214; corrected_condition_mean 27638.099197888216; accepted_fraction 0.3472222222222222; confirmed true.

Benchmark result