# Gram-multilevel Gauss–Newton optimizer

- ID: 519
- Canonical URL: https://synthcore.org/idea/519/gram-multilevel-gauss-newton-optimizer
- API JSON: https://synthcore.org/api/idea/519.json
- API Markdown: https://synthcore.org/api/idea/519.md
- Verification status: mechanism_failed
- Source: [arXiv:2607.07485](https://arxiv.org/abs/2607.07485)
- Category: optimization
- Solves: speedup, stability, scalability
- ML areas: optimizer, training, mlp
- Math tags: linear-algebra, optimization, spectral-theory, numerical-analysis
- Ratings: usefulness 6/10; difficulty 6/10; novelty 6/10

## Idea description

Replace an unpreconditioned conjugate-gradient solve for a damped Gauss–Newton step with a two-level algebraic preconditioner derived from local Jacobian-row supports. Use overlapping local parameter blocks as Schwarz subdomains and a coarse basis containing low-energy local modes, so the optimizer can correct both localized and globally coupled parameter errors.

## Mathematical statement

The paper represents an SPD matrix as A = G^T G = sum_{j=1}^m g_j g_j^T, where G has m rows, g_j in R^n is row j transposed, n is the number of unknowns, and each rank-one term g_j g_j^T is an SPSD local energy. For a neural least-squares problem with residual vector r(theta) in R^m and Jacobian J(theta) in R^{m x n}, use G = J and A_lambda = J^T J + lambda I, where theta in R^n is the parameter vector and lambda > 0 is damping. The paper's two-level error propagator is E_TG = (I - M^{-T} A)(I - P A_c^{-1} P^T A)(I - M^{-1} A), with P in R^{n x n_c} the interpolation/coarse basis, A_c = P^T A P = (G P)^T(G P), n_c the coarse dimension, and M^{-1} a block-Schwarz smoother. The exact identity A_c = (G P)^T(G P) means the coarse operator can be formed by applying J to coarse basis vectors, without assembling a new dense Hessian. Define the row-touching set R_omega = {j : supp(g_j) intersects omega} for parameter block omega, and the G-row closure Omega_omega^G = union_{j in R_omega} supp(g_j); this supplies an algebraic overlap rule. In the adaptation, local operators are A_i = J_i^T J_i + lambda I on overlapping closures Omega_i^G, local eigenvectors with smallest generalized energy are retained in P, and the preconditioner is evaluated through local solves plus a coarse solve.

## Key formulas

- $$A=G^{\top}G=\sum_{j=1}^{m}\bm{g}_{j}\bm{g}_{j}^{\top}$$
- $$E_{\rm TG}=\bigl(I-M^{-\top}A\bigr)\bigl(I-PA_{c}^{-1}P^{\top}A\bigr)\bigl(I-M^{-1}A\bigr),\qquad A_{c}:=P^{\top}AP=(GP)^{\top}(GP)$$
- $$\Omega_{i}^{G}:=\bigcup_{j\in\mathfrak{R}_{\omega_i}}\operatorname{supp}(\bm{g}_{j}),\qquad \mathfrak{R}_{\omega_i}:=\{j:\operatorname{supp}(\bm{g}_{j})\cap\omega_i\neq\varnothing\}$$
- $$\left(J^{\top}J+\lambda I\right)\Delta\theta=-J^{\top}r,\qquad A_c=P^{\top}(J^{\top}J+\lambda I)P=(JP)^{\top}(JP)+\lambda P^{\top}P$$

## Implementation notes

Integrate this at the optimizer step for a least-squares model, immediately after computing a minibatch residual r and Jacobian J. Do not form J^T J explicitly. Use parameter blocks omega_i, initially one block per layer or per group of neurons. First compute approximate row supports: for each residual/Jacobian row j, record parameter blocks whose Jacobian norm exceeds a threshold tau; define each block's overlap Omega_i as the union of blocks touched by those rows. Pseudocode: (1) compute r and J or Jacobian-vector products; (2) set A_lambda = J^T J + lambda I conceptually; (3) for every overlapping Omega_i, form the restricted Jacobian J_i and solve (J_i^T J_i + lambda I) z_i = R_i v using a small dense Cholesky or a few CG iterations; combine z = sum_i R_i^T z_i with diagonal overlap normalization to obtain M^{-1}v; (4) build P by taking k low-energy eigenvectors from each local generalized problem (J_i^T J_i + lambda I)u = mu (D_i + lambda I)u, where D_i is the local diagonal or block-diagonal preconditioner; discard duplicate vectors and orthonormalize; (5) apply the coarse correction by solving A_c y = P^T b with A_c represented as (JP)^T(JP) + lambda P^T P; (6) run preconditioned CG on A_lambda Delta_theta = -J^T r, then update theta <- theta + Delta_theta. The paper supplies the Gram preservation, row-closure rule, and multiplicative error-correction structure; the eigenvalue cutoff k, overlap threshold tau, damping lambda, and CG tolerance are empirical. Start with a two-level method and k=2 to 8 modes per layer. The first experiment should use a width-256 MLP on a 20-dimensional nonlinear regression dataset, comparing Adam, ordinary damped Gauss–Newton CG, block-Jacobi-preconditioned CG, and this method at equal Jacobian evaluations. Measure residual decrease per CG iteration, wall-clock time to a fixed training loss, number of CG iterations, and damping sensitivity. Success is a 2x reduction in CG iterations or a lower loss at equal Jacobian/FLOP budget without worsening final residual; a useful negative result is no improvement over block Jacobi when supports are dense.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built a self-contained row-closure Gram preconditioner experiment with multiplicity-weighted local SPSD splitting, local generalized modes, and Galerkin coarse correction. The exact splitting error was 8.7e-17 and the coarse Gram identity error was 1.2e-15, confirming the algebra. However, on the 1D Gram test, unpreconditioned CG converged in 120 iterations, block Jacobi in 166, while the two-level method reached the 500-iteration cap with relative residual 8.46e-5; damping checks also gave 500 iterations for the idea versus 310, 166, and 52 for block Jacobi at lambda 1e-6, 1e-4, and 1e-2. This MVP therefore shows no promised optimization win and possibly an unsuitable coarse/smoother composition.

### Mechanism check

- Verdict: Built a self-contained row-closure Gram preconditioner experiment with multiplicity-weighted local SPSD splitting, local generalized modes, and Galerkin coarse correction. The exact splitting error was 8.7e-17 and the coarse Gram identity error was 1.2e-15, confirming the algebra. However, on the 1D Gram test, unpreconditioned CG converged in 120 iterations, block Jacobi in 166, while the two-level method reached the 500-iteration cap with relative residual 8.46e-5; damping checks also gave 500 iterations for the idea versus 310, 166, and 52 for block Jacobi at lambda 1e-6, 1e-4, and 1e-2. This MVP therefore shows no promised optimization win and possibly an unsuitable coarse/smoother composition.
- Confidence: 9/10
- Limitations: This was a small structured linear Gram-system sanity test, not the requested width-256 nonlinear MLP/minibatch Jacobian experiment. No wall-clock/FLOP accounting, Adam comparison, GPU execution, or genuinely multiplicative symmetric Schwarz cycle was tested. The implementation follows the idea’s smallest-local-mode wording, while the paper section describes retaining modes above a cutoff, so mode-selection conventions remain a significant unresolved limitation.

## Artifacts

- [gram_multilevel_experiment.py](https://synthcore.org/code/1367/gram_multilevel_experiment.py)
- [report.md](https://synthcore.org/code/1367/report.md)
- [run.json](https://synthcore.org/code/1367/run.json)
- [Download all files as ZIP](https://synthcore.org/download/1367)

## Disclaimer

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