# Extreme-Marginal Conditioning Certificate

- ID: 798
- Canonical URL: https://synthcore.org/idea/798/extreme-marginal-conditioning-certificate
- API JSON: https://synthcore.org/api/idea/798.json
- API Markdown: https://synthcore.org/api/idea/798.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.12286](https://arxiv.org/abs/2607.12286)
- Category: optimization
- Solves: stability, accuracy, speedup
- ML areas: optimizer, training, mlp, transformer
- Math tags: spectral-theory, linear-algebra, optimization, geometry
- Ratings: usefulness 7/10; difficulty 7/10; novelty 8/10

## 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.

## 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.

## Key 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}.$$

## 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

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: 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.

### Mechanism check

- Verdict: 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.
- Confidence: 8/10
- 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.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.2374
- Paired wins: 5/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_report.json](https://synthcore.org/code/326/bench_report.json)
- [experiment.py](https://synthcore.org/code/326/experiment.py)
- [report.md](https://synthcore.org/code/326/report.md)
- [report_bench_2026-08-31T011535.md](https://synthcore.org/code/326/report_bench_2026-08-31T011535.md)
- [results.json](https://synthcore.org/code/326/results.json)
- [stage2_bench.py](https://synthcore.org/code/326/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/326)

## Disclaimer

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