# Coloring-Probed Curvature Traces

- ID: 422
- Canonical URL: https://synthcore.org/idea/422/coloring-probed-curvature-traces
- API JSON: https://synthcore.org/api/idea/422.json
- API Markdown: https://synthcore.org/api/idea/422.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.05157](https://arxiv.org/abs/2607.05157)
- Category: optimization
- Solves: speedup, stability
- ML areas: optimizer, regularization, training-dynamics
- Math tags: probability, graph-theory, linear-algebra, numerical-analysis
- Ratings: usefulness 7/10; difficulty 5/10; novelty 7/10

## Idea description

Replace independent Hutchinson vectors used to estimate traces of neural-network curvature operators with graph-coloring probing vectors. Coordinates that are far apart in an interaction graph share a color, so one probe simultaneously covers many coordinates while reducing variance from localized off-diagonal matrix entries. Apply this to Hessian-trace regularization, Fisher-trace diagnostics, or layerwise curvature estimates used by adaptive optimizers.

## Mathematical statement

The stochastic trace identity uses a zero-mean probe vector \(\eta\in\mathbb{C}^n\) satisfying \(\mathbb{E}[\eta_j]=0\) and \(\mathbb{E}[\bar\eta_j\eta_k]=\delta_{jk}\), where \(\delta_{jk}\) is the Kronecker delta. For a matrix \(A\), Hutchinson estimation is \(\operatorname{tr}(A)\approx M^{-1}\sum_{m=1}^M\eta_m^*A\eta_m\). Construct a graph \(G=(V,E)\) whose vertices are tensor coordinates or parameter blocks and whose edges connect coordinates with potentially large \(|A_{ij}|\); a distance-\(d\) coloring assigns a color \(c(i)\) so that vertices at graph distance at most \(d\) have different colors. For each color \(r\), construct a probing vector \(z_r\) whose entries on color \(r\) are independent Rademacher signs and whose other entries are zero. Resampling signs preserves unbiasedness, while color separation suppresses contributions from localized off-diagonal entries.

## Key formulas

- $$\mathbb{E}[\eta_j]=0,\qquad \mathbb{E}[\bar{\eta}_j\eta_k]=\delta_{jk},\qquad \operatorname{tr}(A)=\mathbb{E}[\eta^*A\eta].$$
- $$\widehat{\operatorname{tr}}(A)=\frac{1}{M}\sum_{m=1}^{M}\eta_m^*A\eta_m.$$
- $$\widehat{\operatorname{tr}}_{\mathrm{probe}}(A)=\frac{1}{M}\sum_{m=1}^{M}\sum_{r=1}^{C}z_{m,r}^*Az_{m,r},\qquad (z_{m,r})_i=\begin{cases}\epsilon_{m,i},&c(i)=r,\\0,&c(i)\neq r,\end{cases}\quad \epsilon_{m,i}\in\{-1,+1\}.$$
- $$\operatorname{Var}(\eta^*A\eta)=\sum_{i\neq j}|A_{ij}|^2\,\mathbb{E}[|\bar\eta_i\eta_j|^2]\quad\text{for independent Rademacher probes}.$$

## Implementation notes

(1) Integration point: add this to a Hessian-trace regularizer or curvature-aware optimizer for a small Transformer or MLP. Let \(A=H\), the minibatch-loss Hessian, and compute \(Hz\) with Pearlmutter's Hessian-vector product; never materialize \(H\). Build an interaction graph over parameter blocks. Connect blocks that occur in the same layer, share an attention head, or have a large pilot cross-block Hessian interaction. For a simple MVP, use a chain or grid graph over coordinates within each layer. (2) Pseudocode: construct \(G\); form its distance-\(d\) power graph; greedily color it to obtain \(c(i)\in\{1,\ldots,C\}\). For each minibatch and repetition \(m\), set \(s=0\); for every color \(r\), sample Rademacher signs on coordinates with \(c(i)=r\), form \(z_{m,r}\), compute \(u=\operatorname{HVP}(loss,z_{m,r})\), and add \(z_{m,r}^{\top}u\) to \(s\). Return \(s/M\) as the trace estimate. (3) Compute the trace identity, coloring, and quadratic forms exactly; estimate the graph from architecture connectivity or a pilot covariance of gradient blocks. Track empirical variance online. (4) First experiment: train a two-layer MLP and tiny ViT on MNIST or CIFAR-10, comparing dense Hutchinson probes with distance-1 and distance-2 probing at equal HVP count and equal wall-clock time. Measure trace variance, HVPs to target loss, and final accuracy. Success is at least 2x lower variance or equivalent accuracy with fewer HVPs.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: Built and numerically verified colored Rademacher probing on banded curvature matrices with chain distance coloring. The estimator was unbiased, variance followed the predicted 1/M law (log-log slopes -1.002 for dense and -0.969 for colored), and variance became exactly zero when coloring distance covered the matrix bandwidth. At equal HVP budget, distance-1 and distance-2 coloring reduced theoretical variance to 0.573x and 0.432x of Hutchinson, while distance-3 eliminated variance for the bandwidth-3 matrix.

### Mechanism check

- Verdict: Built and numerically verified colored Rademacher probing on banded curvature matrices with chain distance coloring. The estimator was unbiased, variance followed the predicted 1/M law (log-log slopes -1.002 for dense and -0.969 for colored), and variance became exactly zero when coloring distance covered the matrix bandwidth. At equal HVP budget, distance-1 and distance-2 coloring reduced theoretical variance to 0.573x and 0.432x of Hutchinson, while distance-3 eliminated variance for the bandwidth-3 matrix.
- Confidence: 9/10
- Limitations: This was a controlled toy verification using explicitly materialized symmetric banded matrices, not a neural-network Hessian-vector-product implementation. The interaction graph was a known chain rather than estimated from architecture or pilot curvature, and wall-clock speed, training loss, accuracy, Fisher traces, and real optimizer integration were not tested.

### Practical benchmark

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

## Artifacts

- [bench_report.json](https://synthcore.org/code/210/bench_report.json)
- [experiment.py](https://synthcore.org/code/210/experiment.py)
- [nn_benchmark.py](https://synthcore.org/code/210/nn_benchmark.py)
- [report.md](https://synthcore.org/code/210/report.md)
- [report_bench_2026-08-30T205921.md](https://synthcore.org/code/210/report_bench_2026-08-30T205921.md)
- [results.json](https://synthcore.org/code/210/results.json)
- [run_stage2.py](https://synthcore.org/code/210/run_stage2.py)
- [Download all files as ZIP](https://synthcore.org/download/210)

## Disclaimer

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