# Affine-Invariant Kronecker Preconditioner

- ID: 797
- Canonical URL: https://synthcore.org/idea/797/affine-invariant-kronecker-preconditioner
- API JSON: https://synthcore.org/api/idea/797.json
- API Markdown: https://synthcore.org/api/idea/797.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.12286](https://arxiv.org/abs/2607.12286)
- Category: optimization
- Solves: speedup, stability, memory
- ML areas: optimizer, mlp, transformer
- Math tags: geometry, optimization, linear-algebra
- Ratings: usefulness 8/10; difficulty 6/10; novelty 6/10

## Idea description

Replace Euclidean or entrywise Kronecker fitting of a layer curvature matrix with its affine-invariant projection onto G = A tensor B. Use the resulting factors as a compact SPD preconditioner in the optimizer, while solving the projection through logarithmic residual partial traces and Armijo line search.

## Mathematical statement

For an SPD target H in S++^(pq) and candidate SPD geometry G in S++^(pq), the paper measures mismatch by d_AI(G0,G1) = ||log(G0^(-1/2) G1 G0^(-1/2))||_F. The structured family is K = {A tensor B : A in S++^p, B in S++^q}. Its affine-invariant projection is G* = argmin over G in K of d_AI(G,H)^2, and geodesic convexity gives uniqueness. Define the normalized logarithmic residual R = log(G^(-1/2) H G^(-1/2)). In tensor coordinates, projection stationarity is expressed by vanishing partial traces, Tr_q(R) = 0 and Tr_p(R) = 0, modulo the scalar gauge A tensor B = (cA) tensor (B/c). Here Tr_q sums the q by q diagonal blocks and returns a p by p matrix, while Tr_p returns a q by q matrix. The structured inverse can be applied without materializing G: (A tensor B)^(-1) vec(X) = vec(B^(-1) X A^(-T)).

## Key formulas

- $$d_{\mathrm{AI}}(G_{0},G_{1})=\left\lVert\log(G_{0}^{-1/2}G_{1}G_{0}^{-1/2})\right\rVert_{F}.$$
- $$G^*=\arg\min_{A\succ0,\,B\succ0}\left\|\log\!\left((A\otimes B)^{-1/2}H(A\otimes B)^{-1/2}\right)\right\|_F^2.$$
- $$R=\log\!\left(G^{-1/2}HG^{-1/2}\right),\qquad \operatorname{Tr}_{q}(R)=0,\quad \operatorname{Tr}_{p}(R)=0.$$
- $$(A\otimes B)^{-1}\operatorname{vec}(X)=\operatorname{vec}(B^{-1}XA^{-T}).$$

## Implementation notes

Integrate this into Adam or a K-FAC-like optimizer for a linear or attention projection layer W in R^(p by q). Every K optimizer steps, estimate an SPD curvature target H from a damped gradient covariance, a block Hessian-vector approximation, or a Fisher matrix: H = (1/m) sum_i g_i g_i^T + lambda I, with lambda greater than zero. Maintain SPD factors A and B, initialize them from the previous iteration or identity, and impose the gauge log det A = 0 after every update. Form G = A tensor B, compute R = log(G^(-1/2) H G^(-1/2)) using an eigendecomposition for small MVPs or a matrix-log routine, then compute both partial traces. Update the factors in SPD-preserving coordinates, for example A <- A^(1/2) exp(alpha D_A) A^(1/2) and B <- B^(1/2) exp(alpha D_B) B^(1/2), where D_A and D_B are whitened versions of the partial-trace residuals. Choose alpha by Armijo backtracking on ||R||_F^2 and stop when both partial-trace norms are small. The exact paper-derived quantities are the affine-invariant residual and partial-trace stationarity test; damping, stochastic curvature estimation, and the factor update are engineering choices. During training, replace the raw matrix gradient by G^(-1)g, implemented as B^(-1) X A^(-T) after reshaping the vector gradient into X. First test on a two-layer MLP on CIFAR-10 with p and q in {64, 128}, comparing SGD, AdamW, Euclidean Kronecker fitting, and affine-invariant projection at equal wall-clock and memory budgets. Measure training loss versus optimizer steps, loss versus FLOPs, final accuracy, factor-update overhead, and the condition number of the preconditioned empirical Hessian. Success means faster loss descent or a smaller preconditioned condition number at comparable memory; failure is no improvement over Euclidean fitting after accounting for projection cost.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: harms
- Verdict: Built an affine-invariant Kronecker projection MVP with SPD log/exp factors, logarithmic residual partial traces, Euclidean Kronecker fitting, structured inverse application, and quadratic preconditioning tests. The mechanism manifested: transverse perturbation distance tracked epsilon with observed/predicted ratios from 0.990 to 0.991, partial-trace residuals stayed below 3.2e-8, scale-invariant targets had residuals below 3.2e-8, and the inverse identity error was 4.4e-15. Across 8 random 2x2 trials, affine projection reduced mean relative condition number from 44.31 for Euclidean fitting to 19.02 and had lower step-20 loss in 7/8 trials, although projection required roughly 10-14 numerical iterations.

### Mechanism check

- Verdict: Built an affine-invariant Kronecker projection MVP with SPD log/exp factors, logarithmic residual partial traces, Euclidean Kronecker fitting, structured inverse application, and quadratic preconditioning tests. The mechanism manifested: transverse perturbation distance tracked epsilon with observed/predicted ratios from 0.990 to 0.991, partial-trace residuals stayed below 3.2e-8, scale-invariant targets had residuals below 3.2e-8, and the inverse identity error was 4.4e-15. Across 8 random 2x2 trials, affine projection reduced mean relative condition number from 44.31 for Euclidean fitting to 19.02 and had lower step-20 loss in 7/8 trials, although projection required roughly 10-14 numerical iterations.
- Confidence: 8/10
- Limitations: This is a small NumPy/SciPy quadratic experiment only with p=q=2, dense eigendecompositions, and BFGS factor fitting. It does not test CIFAR-10, MLP training, Adam/K-FAC integration, wall-clock or FLOP parity, stochastic curvature estimation, larger dimensions, or a full Armijo factor-update implementation.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 0/8
- Benchmark verdict: idea worse (significant)

## Artifacts

- [affine_kron_mvp.py](https://synthcore.org/code/150/affine_kron_mvp.py)
- [bench_report.json](https://synthcore.org/code/150/bench_report.json)
- [extended_check.py](https://synthcore.org/code/150/extended_check.py)
- [extended_results.json](https://synthcore.org/code/150/extended_results.json)
- [report.md](https://synthcore.org/code/150/report.md)
- [report_bench_2026-08-30T174713.md](https://synthcore.org/code/150/report_bench_2026-08-30T174713.md)
- [results.json](https://synthcore.org/code/150/results.json)
- [stage2_bench.py](https://synthcore.org/code/150/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/150)

## Disclaimer

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