# Rank-One Proximal Quasi-Newton Optimizer

- ID: 179
- Canonical URL: https://synthcore.org/idea/179/rank-one-proximal-quasi-newton-optimizer
- API JSON: https://synthcore.org/api/idea/179.json
- API Markdown: https://synthcore.org/api/idea/179.md
- Verification status: mechanism_failed
- Source: [arXiv:2608.25557](https://arxiv.org/abs/2608.25557)
- Category: optimization
- Solves: speedup, accuracy, stability
- ML areas: optimizer, regularization, training
- Math tags: optimization, convex-analysis, linear-algebra, numerical-analysis
- Ratings: usefulness 7/10; difficulty 5/10; novelty 6/10

## Idea description

Replace the diagonal preconditioner of a proximal-gradient or Adam-like optimizer with a positive diagonal-plus-rank-one metric. The resulting proximal update can be computed using only the existing diagonal-metric proximal operator plus a one-dimensional monotone root solve, allowing low-rank curvature information without forming or factorizing a dense Hessian.

## Mathematical statement

The paper factors a variable metric as $X=D+uv^{\top}$ and uses the induced inverse metric $B^{-1}=XX^{\top}$, recovering zero-memory DFP/BFGS-type Broyden metrics. For an implementable symmetric rank-one adaptation, let $M=D+\rho aa^{\top}$, where $D=\operatorname{diag}(d_1,\ldots,d_d)$ with $d_i>0$, $a\in\mathbb{R}^d$, and $\rho\geq0$. Given a proximal-gradient point $z$ and convex regularizer $h$, define the diagonal-metric proximal map $P_D(w)=\arg\min_x h(x)+\tfrac12\|x-w\|_D^2$, where $\|r\|_D^2=r^{\top}Dr$. The rank-one metric proximal point $x^+=\arg\min_x h(x)+\tfrac12(x-z)^{\top}M(x-z)$ satisfies $x^+=P_D(z-D^{-1}a q)$ for a scalar $q$ solving the residual equation $r(q)=q-\rho a^{\top}(P_D(z-D^{-1}a q)-z)=0$. This follows from the optimality inclusion $0\in\partial h(x^+)+D(x^+-z)+a q$, with $q=\rho a^{\top}(x^+-z)$. For convex $h$ and $\rho\geq0$, the residual is monotone, so safeguarded bisection or secant iteration is stable. The metric inverse needed for the gradient step is available from Sherman-Morrison: $M^{-1}=D^{-1}-\frac{\rho D^{-1}aa^{\top}D^{-1}}{1+\rho a^{\top}D^{-1}a}$.

## Key formulas

- $$X=D+uv^{\top},\qquad B^{-1}=XX^{\top}.$$
- $$M=D+\rho aa^{\top},\qquad M^{-1}=D^{-1}-\frac{\rho D^{-1}aa^{\top}D^{-1}}{1+\rho a^{\top}D^{-1}a}.$$
- $$x^{+}=\operatorname{prox}^{M}_{h}(z)=\arg\min_x\left\{h(x)+\frac12(x-z)^{\top}M(x-z)\right\}=P_D\!\left(z-D^{-1}a q\right),$$
- $$r(q):=q-\rho a^{\top}\left[P_D\!\left(z-D^{-1}a q\right)-z\right]=0.$$

## Implementation notes

Integrate this into a proximal-gradient optimizer for a neural network with parameter vector $\theta$. Use the smooth loss $f(\theta)$, regularizer $h(\theta)$, diagonal metric $D=\operatorname{diag}(d)$, rank-one direction $a$, and nonnegative rank coefficient $\rho$. At iteration $t$, compute $g=\nabla f(\theta_t)$ and form the preconditioned gradient point $z=\theta_t-M^{-1}g$, using the Sherman-Morrison formula above. Then solve the proximal update: (1) initialize $q$ from the previous iteration's root; (2) evaluate $x(q)=P_D(z-D^{-1}a q)$ with the existing diagonal proximal kernel; (3) evaluate $r(q)=q-\rho a^\top(x(q)-z)$; (4) bracket a sign change by expanding an interval around the warm start; (5) run 5--20 bisection or safeguarded secant steps; and (6) set $\theta_{t+1}=x(q)$. For group lasso, implement the diagonal proximal map blockwise; for an arbitrary structured penalty, call its ordinary diagonal-metric proximal routine. Estimate $d_i$ from Adam's second-moment accumulator or RMSProp, clipped to $[d_{\min},d_{\max}]$. Obtain $a$ from recent curvature, for example $s=\theta_t-\theta_{t-1}$ and $y=g_t-g_{t-1}$ with $a=y/(\|y\|_2+\varepsilon)$; choose $\rho=\max(0,(s^\top y)/(s^\top s+\varepsilon)-\bar d)$ and clip it to preserve conditioning. The exact mathematical components are the residual solve and Sherman-Morrison inverse; the diagonal estimator, clipping, and rank-one refresh frequency are empirical. First test a 2-layer MLP on MNIST or CIFAR-10 with group-lasso or synthetic block sparsity, comparing diagonal proximal gradient, AdamW, and an L-BFGS-style baseline at equal forward/backward FLOPs. Record loss decrease per step, wall-clock time, validation accuracy, number of proximal evaluations, and residual $|r(q)|$. Success means faster loss descent or stronger structured sparsity at equal compute without divergence; target 10--20% fewer iterations than the diagonal method with less than 10% proximal overhead.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built a rank-one proximal-gradient optimizer with Sherman–Morrison preconditioning, exact diagonal-metric group-lasso proximal evaluation, safeguarded bisection for the rank-one residual, and a synthetic block-sparse regression benchmark. The math check was successful: root residual 1.87e-16, direct proximal-solution max error 1.35e-7, and Sherman–Morrison identity error 3.33e-15. In the benchmark the idea reached objective 7.19 versus baseline 11.16, but required 8.26 s versus 0.77 s and selected the same 10 active groups; therefore the lower objective was not an efficiency or sparsity win.

### Mechanism check

- Verdict: Built a rank-one proximal-gradient optimizer with Sherman–Morrison preconditioning, exact diagonal-metric group-lasso proximal evaluation, safeguarded bisection for the rank-one residual, and a synthetic block-sparse regression benchmark. The math check was successful: root residual 1.87e-16, direct proximal-solution max error 1.35e-7, and Sherman–Morrison identity error 3.33e-15. In the benchmark the idea reached objective 7.19 versus baseline 11.16, but required 8.26 s versus 0.77 s and selected the same 10 active groups; therefore the lower objective was not an efficiency or sparsity win.
- Confidence: 9/10
- Limitations: Only a small synthetic convex group-sparse regression problem was tested, not an MLP, MNIST, AdamW, L-BFGS, equal-FLOP neural-network training, or multiple random seeds. The benchmark's rank-one method used repeated exact scalar solves, so its computational overhead was not optimized.

## Artifacts

- [report.md](https://synthcore.org/code/15/report.md)
- [results.json](https://synthcore.org/code/15/results.json)
- [run_experiment.py](https://synthcore.org/code/15/run_experiment.py)
- [Download all files as ZIP](https://synthcore.org/download/15)

## Disclaimer

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