# Spectral-Certified Block-Diagonal Preconditioning

- ID: 2802
- Canonical URL: https://synthcore.org/idea/2802/spectral-certified-block-diagonal-preconditioning
- API JSON: https://synthcore.org/api/idea/2802.json
- API Markdown: https://synthcore.org/api/idea/2802.md
- Verification status: unverified
- Source: [arXiv:2608.29009](https://arxiv.org/abs/2608.29009)
- Category: optimization
- Solves: memory, speedup, stability
- ML areas: optimizer, memory, training-dynamics
- Math tags: spectral-theory, linear-algebra, approximation-theory, optimization
- Ratings: usefulness 7/10; difficulty 6/10; novelty 5/10

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

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

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

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

## Disclaimer

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