✗ Failed on benchmark 2026

Spectral-Certified Block-Diagonal Preconditioning

Implementation & benchmark of arXiv:2608.29009 — A Sharp Unitarily Invariant Norm Bound for the Off-Diagonal Block Perturbation of a Hermitian Matrix

Usefulness7/10

Difficulty6/10

Novelty5/10

Optimization Memory Speedup Stability Optimizer Memory Training dynamics Spectral theory Linear algebra Approximation theory Optimization

Source paper: A Sharp Unitarily Invariant Norm Bound for the Off-Diagonal Block Perturbation of a Hermitian Matrix arXiv:2608.29009 ⓘ · analyzed Sep 1, 2026

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

Idea description

Replace a full Hermitian curvature matrix, such as a Hessian or empirical Fisher matrix, by its block-diagonal version only when the paper's perturbation certificate predicts a small eigenvalue change. Use the certificate online to merge poorly separated blocks and retain independent preconditioners for well-separated blocks, yielding a controllable accuracy-memory tradeoff rather than a fixed block-diagonal approximation.

Formulas

$$A=\begin{bmatrix}H_{1}&E^{*}\\E&H_{2}\end{bmatrix},\qquad \widetilde{A}=\begin{bmatrix}H_{1}&0\\0&H_{2}\end{bmatrix},\qquad V=A-\widetilde{A}.$$

$$\phi(\delta,\epsilon)=\frac{2\epsilon}{\delta+\sqrt{\delta^{2}+4\epsilon^{2}}},\qquad \eta=\min_{\lambda\in\eig(H_1),\,\mu\in\eig(H_2)}|\lambda-\mu|,\qquad \epsilon_2=\|E\|_2.$$

$$\left\|\operatorname{diag}\!\left(\boldsymbol{\lambda}(A)-\boldsymbol{\lambda}(\widetilde{A})\right)\right\|_{\mathrm{UI}}\leq \phi(\eta,\epsilon_2)\,\|A-\widetilde{A}\|_{\mathrm{UI}}.$$

$$\widehat{\Delta}_{\mathrm{curv}}=\phi(\widehat\eta,\widehat\epsilon_2)\,\|\widehat V\|_{F},\qquad \text{accept block deletion only if }\widehat{\Delta}_{\mathrm{curv}}\leq\tau.$$

Mathematical statement

Let $A=\begin{bmatrix}H_1&E^*\\E&H_2\end{bmatrix}$ be a Hermitian curvature matrix, where $H_1$ and $H_2$ are within-block curvature matrices and $E$ contains cross-block curvature. Let $\widetilde A=\begin{bmatrix}H_1&0\\0&H_2\end{bmatrix}$, $V=A-\widetilde A$, and $\epsilon_2=\|E\|_2=\|V\|_2$. Define the spectral gap $\eta=\min_{\lambda\in\eig(H_1),\,\mu\in\eig(H_2)}|\lambda-\mu|$. The paper defines $\phi(\delta,\epsilon)=\frac{2\epsilon}{\delta+\sqrt{\delta^2+4\epsilon^2}}$ for $(\delta,\epsilon)\neq(0,0)$, and $\phi(0,0)=1$. For every Q-norm, including Schatten $p$-norms for $2\leq p\leq\infty$, the sharp bound is $\|\operatorname{diag}(\boldsymbol\lambda(A)-\boldsymbol\lambda(\widetilde A))\|_{\mathrm{UI}}\leq\phi(\eta,\epsilon_2)\|A-\widetilde A\|_{\mathrm{UI}}$; it also holds for every unitarily invariant norm when $\operatorname{rank}(E)\leq1$. Here $\boldsymbol\lambda(\cdot)$ is the descending eigenvalue vector and $\operatorname{diag}(x)$ is the diagonal matrix with entries $x$. Use the Frobenius or spectral norm to obtain a computable upper bound on curvature-spectrum distortion.

Implementation notes

Integrate this into a second-order optimizer or curvature-aware Adam variant at the preconditioner-construction step. Partition parameters into blocks, such as one block per layer or groups of 1–10 million parameters, and maintain a block-diagonal approximation to a damped empirical Fisher matrix $A=G+\lambda I$, where $G$ is estimated from minibatch gradients and $\lambda>0$ ensures positive definiteness. For each candidate pair of blocks, estimate the within-block matrices $H_1,H_2$ and cross-block matrix $E$ using gradient-covariance sketches instead of materializing the full matrix. Estimate $\widehat\epsilon_2=\|E\|_2$ by randomized power iteration: initialize a random unit vector $v$, repeatedly compute $v\leftarrow E^*Ev/\|E^*Ev\|_2$, and return $\widehat\epsilon_2=\|Ev\|_2$. Estimate extremal eigenvalues of each $H_i$ with a few Lanczos iterations; set $\widehat\eta$ to the smallest pairwise distance between these estimates, or conservatively set it to zero if spectral intervals overlap. Compute $\phi(\widehat\eta,\widehat\epsilon_2)$ and $\widehat\Delta_{\mathrm{curv}}=\phi(\widehat\eta,\widehat\epsilon_2)\|\widehat V\|_F$. Pseudocode: collect gradient sketches; estimate $H_i$, $E$, $\widehat\eta$, and $\widehat\epsilon_2$; if the certificate is below threshold $\tau$, retain independent block inverses or Kronecker factors; otherwise merge the pair and construct a joint factor; apply the resulting preconditioner to the gradient. The theorem supplies the perturbation bound, while all spectral quantities are estimated empirically. First test on a six-layer MLP or small ViT on CIFAR-10, comparing full-matrix, fixed layerwise block-diagonal, and adaptive certified preconditioning at equal optimizer memory. Measure loss versus optimizer FLOPs, final accuracy, estimated curvature-eigenvalue distortion, and peak memory. A successful result is at least 2x lower preconditioner memory with no more than 1% relative loss in final accuracy, while the certificate correctly predicts block merges preceding optimization instability.

Verification

Failed on benchmark

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not reproduced ✗

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 spectral certificate module and adaptive block-merging quadratic optimizer prototype. The mechanism manifested: in the 2x2 equality case, weak coupling produced distortion/epsilon² of 2.0000, 1.0000, 0.5000, and 0.2500 for gaps 0.5, 1, 2, and 4, matching 1/eta; strong coupling approached distortion/epsilon = 0.995 at epsilon=100, and zero-gap distortion equaled epsilon exactly. The rank-one Frobenius check had 0/100 violations, while adaptive merging retained blocks at coupling 0.03, merged one pair at 0.3, and merged all blocks at 0.8; this is promising evidence for certificate-controlled merging, not a demonstrated large-scale optimizer win.

Agent confidence: 8/10

Baseline: Fixed 2x2 block-diagonal preconditioner: 16 stored matrix entries; residual quadratic loss after 8 steps was 0.0, 1.03e-10, and 2.03e-5 at couplings 0.03, 0.3, and 0.8.
Idea: Adaptive certificate: 16, 24, and 64 stored entries at couplings 0.03, 0.3, and 0.8; residual loss was 0.0, 2.22e-14, and 0.0 respectively. Certificate predictions matched the exact 2x2 shifts to numerical precision and had no rank-one violations.

Limitations: Only tiny synthetic Hermitian quadratics were tested; no MLP, CIFAR-10, empirical-Fisher sketch estimation, randomized power iteration error analysis, CUDA benchmark, wall-clock/FLOP measurement, noisy online certificates, or meaningful large-scale memory comparison was performed. The adaptive method does not preserve memory savings when the certificate merges all blocks.

How to run: python3 experiment.py && /home/maxwelhelp/main/bin/python3 mini_optimizer.py

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

No significant difference vs. the tuned baseline (+111.4%, p=0.9404, wins 6 / 8 paired seeds).

Benchmark: Tabular regression (Friedman)
Model: mlp_tiny
Paired seeds: 8
Baseline mean: 231.5268
Idea mean: 489.4526
Effect (Δ): 257.9258 (+111.4%; negative = idea better)
Wins: 6 / 8 paired seeds
p-value: 0.9404 (permutation test, 20 000 shuffles)
Smallest detectable effect: n/a
Mechanism: Not confirmed ✗
Practical effect: Inconclusive
Baseline tuning: swept over 6 configs

Limitations:

This was a deliberately small MVP due to repeated autograd and dense block-factor costs: 100 training samples, 50 test samples, one epoch, three per-example gradients, 64-parameter blocks, and no wall-clock or peak-memory measurement. The certificate used conservative eta=0 rather than reliable within-block spectral interval estimates. The projected trained-model signature returned zero observed shift and should be debugged before drawing conclusions about the theorem itself; the negative result applies to this implementation and budget, not a general impossibility claim.

How to run: python3 bench_experiment.py

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

Stage 2 — Benchmark Sep 2, 2026 latest Failed ✗

Agent confidence: 9/10

Implemented spectral-certified adaptive block preconditioning with a small per-example empirical-Fisher sketch, conservative certificate-based adjacent block merging, and matched Adam baseline training on identical mlp_tiny systems. Across 8 paired seeds, the idea had much worse mean test MSE (489.45 vs 231.53), with paired delta +257.93 and permutation p=0.9404; the mechanism signature was also not confirmed because observed projected distortion was zero in this implementation. The proposed effect therefore did not transfer to this neural-network benchmark.

Baseline: Best sweep config lr=0.01, epochs=1, weight_decay=0.0001; full 8-seed test MSE mean 231.5268, std 21.3007; per-seed [256.4728, 229.3470, 246.0605, 182.8064, 247.0722, 224.0730, 240.7747, 225.6076].
Idea: Best idea config lr=0.01, epochs=1, block=64, tau=0.02, damp=0.01, sketch=3; full 8-seed test MSE mean 489.4526, std 991.4184; per-seed [29.4809, 76.0353, 67.2008, 22.4972, 3082.7842, 505.4777, 78.8188, 53.3257]. Paired delta +257.9258, p=0.9404, verdict no significant win.

Benchmark result