# Support-Identified Newton Optimizer for Sparse Orthogonal Layers

- ID: 831
- Canonical URL: https://synthcore.org/idea/831/support-identified-newton-optimizer-for-sparse-orthogonal-la
- API JSON: https://synthcore.org/api/idea/831.json
- API Markdown: https://synthcore.org/api/idea/831.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.12877](https://arxiv.org/abs/2607.12877)
- Category: optimization
- Solves: speedup, stability, memory
- ML areas: optimizer, attention, ssm, pruning
- Math tags: optimization, differential-geometry, linear-algebra, dynamical-systems
- Ratings: usefulness 7/10; difficulty 6/10; novelty 7/10

## Idea description

Train a matrix-valued neural layer under an exact or near-exact Stiefel constraint while using an l1 or row-group sparsity penalty. During early training, use manifold proximal-gradient steps to identify a stable nonzero support; once the support stops changing, switch to Newton-CG steps restricted to the smooth intersection of the Stiefel tangent space and the fixed-support subspace. This can reduce the number of optimizer iterations needed to obtain sparse, well-conditioned projections.

## Mathematical statement

The paper studies min_X F(X)=f(X)+g(X) subject to X in St(n,r), where St(n,r)={X in R^{n times r}: X^T X=I_r}, f is smooth with Lipschitz Euclidean gradient, and g is convex and Lipschitz, including g(X)=lambda||X||_1 and g(X)=lambda||X||_{2,1}. Let S be the currently identified support and E_S={Z: Z_{ij}=0 whenever (i,j) is not in S} for entry sparsity, or E_S={Z: Z_{i,:}=0 whenever row i is not in S} for row sparsity. The Stiefel tangent space is T_X St(n,r)={Z: X^T Z+Z^T X=0}, so the identified tangent model is T_X St(n,r) intersect E_S. After support identification, Newton-CG approximately solves H_k[Z]=-grad_{M_S} f(X_k) on this restricted tangent model, where H_k is the Hessian of the smooth restriction and grad_{M_S} is the projected gradient. The safeguard uses proximal manifold-gradient steps when projection or Newton fails. The extracted acceptance logic is: an accepted superlinear Newton step keeps t_k unchanged and decreases lambda_k; an accepted linear full step increases t_k and decreases lambda_k; an accepted backtracked step decreases t_k and increases lambda_k. Under regularity and a second-order sufficient condition, the active manifold is identified finitely and the local Newton sequence has Q-superlinear convergence.

## Key formulas

- $$\min_X F(X):=f(X)+g(X),\qquad \mathrm{s.t.}\qquad X\in\mathrm{St}(n,r),$$
- $$\mathrm{St}(n,r):=\{X\in\mathbb{R}^{n\times r}\mid X^\top X=I_r\},\qquad g(X)=\lambda\|X\|_1=\lambda\sum_{i=1}^n\sum_{j=1}^r|X_{ij}|,$$
- $$T_X\mathrm{St}(n,r)=\{Z\in\mathbb{R}^{n\times r}:X^\top Z+Z^\top X=0\},\qquad T_X\mathcal{M}_S=T_X\mathrm{St}(n,r)\cap E_S,$$
- $$\texttt{accepted/superlinear}:\ t_{k+1}=t_k,\ \lambda_{k+1}=\lambda_k^+;\qquad \texttt{accepted/linear/full}:\ t_{k+1}=t_k^+,\ \lambda_{k+1}=\lambda_k^-;\qquad \texttt{accepted/backtracked}:\ t_{k+1}=t_k^-,\ \lambda_{k+1}=\lambda_k^+.$$

## Implementation notes

(1) Integration point: replace the standard optimizer for a matrix W in one orthogonal linear layer, attention projection, or SSM transition matrix. Parameterize the forward weight directly as X and initialize it with X^T X=I_r; use entrywise sparsity or row-group sparsity. Let f(X) be the minibatch loss and g(X)=lambda||X||_1 or lambda||X||_{2,1}. (2) Pseudocode: at iteration k, compute a manifold proximal-gradient candidate Y=Retr_{X_k}(-alpha_k grad f(X_k)), apply soft thresholding, and retract back toward Y^T Y=I. Define S_k={(i,j): |X_{k,ij}|>tau}, or active rows for group sparsity. If S_k is unchanged for q consecutive iterations, form the tangent operator on T_{X_k}St intersect E_{S_k} and solve H_k[Z]=-grad_{M_{S_k}}f(X_k) with truncated CG. Retract X_{k+1}=Retr_{X_k}(eta Z) and test Armijo decrease. If CG detects negative curvature, the residual is too large, or retraction fails, use the proximal-gradient candidate. Increase the trust scale after accepted full linear steps, preserve it after superlinear steps, damp after backtracking, decrease sparsity regularization after successful full Newton steps, and increase it after backtracking. (3) Compute from the mathematics: tangent constraints, support-restricted CG, Stiefel retraction, and acceptance tests. Estimate empirically: support stabilization, local convergence slope, and Hessian-vector products through autodiff. (4) First experiment: train a 2-layer MLP or small Transformer on CIFAR-10 or WikiText-2 with a 256x256 sparse orthogonal projection. Compare AdamW plus soft thresholding, projected Riemannian gradient, and this ManPG/Newton-CG optimizer at matched forward/backward FLOPs. Measure wall-clock time to a fixed validation loss, nonzero count, ||X^T X-I||_F, loss decrease per optimizer step, and whether the final loss curve becomes superlinear-like. A useful success signal is 20–30% fewer optimizer steps at the same sparsity and validation accuracy without orthogonality drift.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: harms
- Verdict: Built and ran a self-contained support-restricted Riemannian Newton experiment for the r=1 Stiefel case (the unit sphere), including retraction, tangent-space restriction, Newton solves, safeguards, and support stabilization. The mechanism manifested: soft-threshold support counts exactly matched the predicted transition rule across all six lambda values, tangent dimensions matched |S|-1 with residuals below 1.8e-16, and Newton errors showed quadratic ratios near 0.51 while gradient errors had linear ratios near 0.965. In the toy comparison, support-identified Newton reached the final-objective target in 45 steps versus 60 for projected gradient, with both maintaining orthogonality below 5e-16; this is a promising toy signal, not evidence of a general neural-network speedup.

### Mechanism check

- Verdict: Built and ran a self-contained support-restricted Riemannian Newton experiment for the r=1 Stiefel case (the unit sphere), including retraction, tangent-space restriction, Newton solves, safeguards, and support stabilization. The mechanism manifested: soft-threshold support counts exactly matched the predicted transition rule across all six lambda values, tangent dimensions matched |S|-1 with residuals below 1.8e-16, and Newton errors showed quadratic ratios near 0.51 while gradient errors had linear ratios near 0.965. In the toy comparison, support-identified Newton reached the final-objective target in 45 steps versus 60 for projected gradient, with both maintaining orthogonality below 5e-16; this is a promising toy signal, not evidence of a general neural-network speedup.
- Confidence: 8/10
- Limitations: Only a synthetic r=1 sphere problem was tested, not a matrix St(n,r) layer with r>1, row-group sparsity, minibatches, autodiff Hessian-vector products, GPU execution, or CIFAR/Transformer training. The sparsity comparison uses a fixed active set rather than a full proximal-manifold implementation with dynamically changing l1 support, and wall-clock speed was not evaluated.

### Practical benchmark

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

## Artifacts

- [bench_report.json](https://synthcore.org/code/339/bench_report.json)
- [report.md](https://synthcore.org/code/339/report.md)
- [report_bench_2026-08-31T014050.md](https://synthcore.org/code/339/report_bench_2026-08-31T014050.md)
- [results.json](https://synthcore.org/code/339/results.json)
- [stage2_bench.py](https://synthcore.org/code/339/stage2_bench.py)
- [support_newton_experiment.py](https://synthcore.org/code/339/support_newton_experiment.py)
- [Download all files as ZIP](https://synthcore.org/download/339)

## Disclaimer

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