# Projected Randomized Gauss–Newton Updates

- ID: 502
- Canonical URL: https://synthcore.org/idea/502/projected-randomized-gauss-newton-updates
- API JSON: https://synthcore.org/api/idea/502.json
- API Markdown: https://synthcore.org/api/idea/502.md
- Verification status: beats_baseline
- Source: [arXiv:2607.06917](https://arxiv.org/abs/2607.06917)
- Category: optimization
- Solves: speedup, stability, sample-efficiency
- ML areas: optimizer, fine-tuning, training-dynamics
- Math tags: optimization, linear-algebra, numerical-analysis
- Ratings: usefulness 7/10; difficulty 6/10; novelty 7/10

## Idea description

Replace ordinary randomized coordinate descent inside a least-squares neural subproblem with RPLSS's projected direction update. Each sampled parameter coordinate generates a Jacobian column, while the stored matrix P removes components already covered by previous updates; this should reduce redundant coordinate steps and improve convergence for linear heads, LoRA modules, and locally linearized fine-tuning.

## Mathematical statement

For a linear system A x = b with A in R^{m x n}, x in R^n, choose a positive diagonal or symmetric positive-definite preconditioner W in R^{n x n}. At iteration k, select coordinate i and form the sampled column s_k = A e_i, where e_i is the i-th standard basis vector. Let P_{k-1} in R^{n x (k-1)} contain the previously accepted projected search directions, and define Theta_{k-1} = P_{k-1}^T W^{-1} P_{k-1}. The RPLSS correction is p_k = gamma_{k-1}(W A^T s_k - P_{k-1} Theta_{k-1}^{-1} P_{k-1}^T A^T s_k), with d_{k-1} = Theta_{k-1}^{-1/2} P_{k-1}^T A^T s_k and gamma_{k-1} = [s_k^T(b-Ax_{k-1})]/[s_k^T A W A^T s_k - ||d_{k-1}||_2^2]. Then x_k = x_{k-1}+p_k. The second term subtracts the W^{-1}-metric projection onto span(P_{k-1}); the denominator is the resulting squared norm of the new direction in measurement space. For neural least squares, A is a minibatch Jacobian or feature matrix, b is the desired target/residual, x is the vector of trainable head or adapter parameters, and P stores earlier accepted parameter-space directions. The finite-termination intuition applies when sampled Jacobian columns generate independent directions; the paper additionally claims exponential convergence for its randomized variants.

## Key formulas

- $$\mathbf{s}_{k}=\mathbf{A}\mathbf{e}_{i}$$
- $$\mathbf{p}_{k}=\gamma_{k-1}\left(\mathbf{W}\mathbf{A}^{T}\mathbf{s}_{k}-\mathbf{P}_{k-1}\mathbf{\Theta}_{k-1}^{-1}\mathbf{P}_{k-1}^{T}\mathbf{A}^{T}\mathbf{s}_{k}\right),\qquad \mathbf{\Theta}_{k-1}=\mathbf{P}_{k-1}^{T}\mathbf{W}^{-1}\mathbf{P}_{k-1}$$
- $$\gamma_{k-1}=\frac{\mathbf{s}_{k}^{T}(\mathbf{b}-\mathbf{A}\mathbf{x}_{k-1})}{\mathbf{s}_{k}^{T}\mathbf{A}\mathbf{W}\mathbf{A}^{T}\mathbf{s}_{k}-\|\mathbf{d}_{k-1}\|_{2}^{2}},\qquad \mathbf{d}_{k-1}=\mathbf{\Theta}_{k-1}^{-1/2}\mathbf{P}_{k-1}^{T}\mathbf{A}^{T}\mathbf{s}_{k}$$
- $$\mathbf{x}_{k}=\mathbf{x}_{k-1}+\mathbf{p}_{k}$$

## Implementation notes

1. Integration point: implement this as an inner optimizer for a small least-squares neural subproblem, starting with a frozen transformer and a trainable linear classification head or LoRA adapter. On a minibatch, define A = J(theta) or A = H, where J is the minibatch Jacobian of model outputs with respect to the selected adapter parameters and H is the feature matrix for a linear head. Define b as the target vector for a head fit, or as the negative current residual for a Gauss–Newton linearization. Do not apply it directly to all transformer weights initially; the stored projection matrix is O(nk).

2. Pseudocode: initialize x=x0 and P as an empty matrix. Repeatedly sample coordinate i, compute s=A[:,i], residual r=b-Ax, and q=A^T s. For the first step set u=Wq. Otherwise compute Theta=P^T W^{-1}P, c=Theta^{-1}(P^Tq), u=Wq-Pc, and denom=s^T A u, equivalently s^T A W A^T s minus ||Theta^{-1/2}P^Tq||^2. Set gamma=(s^T r)/(denom+epsilon), p=gamma*u, and x=x+p. If the new direction is numerically independent, append p to P; otherwise skip the append or resample i. Use W=diag(1/(column_norm_i^2+epsilon)) or W=I.

3. The exact quantities imported from the paper are the projected direction, Theta Gram matrix, and gamma denominator. In a neural implementation, estimate J columns with forward-mode automatic differentiation or finite differences, estimate A^T s with a Jacobian-vector product or vector-Jacobian product, and use QR or Cholesky solves rather than explicitly forming Theta^{-1/2}. Recompute A and P every minibatch or maintain P only within one local Gauss–Newton solve; reset P when the minibatch changes substantially.

4. First experiment: use a frozen small MLP or ViT backbone with a 1,000–10,000 parameter LoRA adapter on MNIST or CIFAR-10. Compare projected randomized Gauss–Newton against Adam, ordinary randomized coordinate descent, and unprojected minibatch Gauss–Newton at equal Jacobian evaluations. Measure training loss versus wall-clock time and number of sampled coordinates, final validation accuracy, and the number of repeated directions detected by |P^Tq|. The expected signal is faster loss reduction and fewer effective coordinate updates, especially when adapter Jacobian columns are highly correlated; a negative result would be no improvement over randomized coordinate descent after accounting for the O(k^2) projection cost.

## Verification

- Status: beats_baseline
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: helps
- Verdict: Built a NumPy MVP of the W=I projected randomized Gauss–Newton/RPLSS update and a matched randomized coordinate-descent baseline. The mechanism manifested quantitatively: denominator identity error was 3.7e-14, projected norm matched the predicted sqrt(1-rho^2) law across rho=0..0.99, and exact rank-6 systems terminated after six accepted directions with final loss 5.3e-26. In the toy comparison, RPLSS also had lower 12-sample final loss than coordinate descent at every tested correlation, but this is not yet a neural or wall-clock result.

### Mechanism check

- Verdict: Built a NumPy MVP of the W=I projected randomized Gauss–Newton/RPLSS update and a matched randomized coordinate-descent baseline. The mechanism manifested quantitatively: denominator identity error was 3.7e-14, projected norm matched the predicted sqrt(1-rho^2) law across rho=0..0.99, and exact rank-6 systems terminated after six accepted directions with final loss 5.3e-26. In the toy comparison, RPLSS also had lower 12-sample final loss than coordinate descent at every tested correlation, but this is not yet a neural or wall-clock result.
- Confidence: 9/10
- Limitations: Only the W=I linear least-squares case was tested. No CUDA implementation, neural network or LoRA adapter, minibatch Jacobian recomputation, timing/FLOP accounting, validation accuracy, or non-identity preconditioner was evaluated.

### Practical benchmark

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

## Artifacts

- [README.md](https://synthcore.org/code/240/README.md)
- [bench_experiment.py](https://synthcore.org/code/240/bench_experiment.py)
- [bench_report.json](https://synthcore.org/code/240/bench_report.json)
- [experiment.py](https://synthcore.org/code/240/experiment.py)
- [report.md](https://synthcore.org/code/240/report.md)
- [report_bench_2026-08-30T212806.md](https://synthcore.org/code/240/report_bench_2026-08-30T212806.md)
- [Download all files as ZIP](https://synthcore.org/download/240)

## Disclaimer

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