✓✓ Beats tuned baseline 2026

Projected Randomized Gauss–Newton Updates

Implementation & benchmark of arXiv:2607.06917 — RPLSS: A randomized projected linear systems solver

Usefulness7/10

Difficulty6/10

Novelty7/10

Optimization Speedup Stability Sample efficiency Optimizer Fine tuning Training dynamics Optimization Linear algebra Numerical analysis

Source paper: RPLSS: A randomized projected linear systems solver arXiv:2607.06917 ⓘ · analyzed Aug 30, 2026

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

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.

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}$$

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.

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

Beats tuned baseline

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not reproduced ✗

Stage 2 · Practical benchmark result: Significant win ✓

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

How to read this: The implementation beat the baseline, but the claimed mechanism did not reproduce at benchmark scale. The gain may come from another effect; treat the cause as unresolved.

Stage 1 — Mechanism check agent confidence 9/10

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.

Agent confidence: 9/10

Baseline: Randomized coordinate descent, 12 sampled coordinates: final loss 3.836, 4.243, 3.546, 0.528 for rho=0.00, 0.50, 0.90, 0.99 respectively.
Idea: Projected RPLSS, 12 sampled coordinates: final loss 2.108, 1.211, 0.254, 0.0256 for rho=0.00, 0.50, 0.90, 0.99 respectively; 5.25 independent directions accepted on average.

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.

How to run: python3 experiment.py

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

Beats the tuned baseline by 64.4% (p=0.0081, wins 8 / 8 paired seeds; metric: lower is better).

Benchmark: Tabular regression (Friedman)
Model: mlp_tiny_frozen_head
Paired seeds: 8
Baseline mean: 95.2806
Idea mean: 33.9243
Effect (Δ): -61.3564 (−64.4%; negative = idea better)
Wins: 8 / 8 paired seeds
p-value: 0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±20.5%
Mechanism: Not confirmed ✗
Practical effect: Helps
Baseline tuning: swept over 3 configs

Limitations:

Only the registered tabular track was tested. The implementation trains a frozen-MLP linear head rather than all neural-network weights or a LoRA adapter; wall-clock/FLOP speedup was not measured; the mechanism signature was not quantitatively confirmed; CUDA fallback was implemented but device-specific timing was not isolated.

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 Aug 30, 2026 latest Worked ✓

Agent confidence: 7/10

Implemented Projected Randomized Gauss–Newton/RPLSS as an optimizer intervention on the registered tabular Friedman#1 track. Using the same frozen mlp_tiny representation and trainable linear head, it significantly beat tuned Adam across 8 paired seeds: MSE 33.924 versus 95.281, paired delta -61.356, permutation p=0.0081, and 8/8 paired wins. The trained-model mechanism signature was not quantitatively confirmed, because the observed projection residual ratio 0.0561 differed from the predicted 0.2221.

Baseline: Adam baseline, lr sweep {0.003, 0.01, 0.03}, 10 epochs; best lr=0.03; full 8-seed MSE mean 95.2806477549.
Idea: Projected randomized Gauss–Newton, same lr grid with damping; best lr=0.03; full 8-seed MSE mean 33.9242689610; paired delta -61.3563787937; p=0.0081; 8/8 wins.

Benchmark result