# Sketch-orthogonal low-rank optimizer updates

- ID: 396
- Canonical URL: https://synthcore.org/idea/396/sketch-orthogonal-low-rank-optimizer-updates
- API JSON: https://synthcore.org/api/idea/396.json
- API Markdown: https://synthcore.org/api/idea/396.md
- Verification status: mechanism_failed
- Source: [arXiv:2607.03402](https://arxiv.org/abs/2607.03402)
- Category: optimization
- Solves: speedup, memory, stability
- ML areas: optimizer, fine-tuning
- Math tags: linear-algebra, random-matrix, optimization
- Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10

## Idea description

Apply the paper's orthogonal-sketch idea to a trainable low-rank weight update or low-rank optimizer state. After every optimizer step, use a row sketch and Cholesky QR to recondition the factor basis, then compute the update with the standard tangent-space projector rather than an oblique sketched projector.

## Mathematical statement

The paper starts from the matrix ODE $\dot{A}(t)=F(t,A(t))$, where $A(t)\in\mathbb{R}^{m\times n}$ is a large matrix and $F$ is its vector field. For a rank-$r$ factorization $W=UV^\top$, with $U\in\mathbb{R}^{m\times r}$ and $V\in\mathbb{R}^{n\times r}$, the standard orthogonal tangent-space projector for an update $G\in\mathbb{R}^{m\times n}$ is $P_{U,V}(G)=UU^\top G+GVV^\top-UU^\top GVV^\top$, assuming $U^\top U=I_r$ and $V^\top V=I_r$. A sketch is a matrix $S\in\mathbb{R}^{s\times m}$, typically with $s\ge r+p$, whose rows are random Gaussian, subsampled orthogonal, or a randomized transform. Sketch-based Cholesky QR computes $C=(SU)^\top(SU)$, $R=\operatorname{chol}(C)$, and $Q=UR^{-1}$; if $S$ is a subspace embedding for $\operatorname{range}(U)$, then $Q^\top Q\approx I_r$. The corresponding update is $U\leftarrow Q$ and $V\leftarrow VR^\top$ so that $UV^\top$ is unchanged. The transferable warning from the paper is that replacing $P_{U,V}$ by a naively sketched or oblique projector can produce a large error when $(I-UU^\top)G(I-VV^\top)$ is large; therefore the implementation must retain the standard orthogonal projector after basis reconditioning.

## Key formulas

- $$\dot{A}(t)=F(t,A(t)),\qquad A(0)=A_0\in\mathbb{R}^{m\times n}.$$
- $$P_{U,V}(G)=UU^\top G+GVV^\top-UU^\top GVV^\top,\qquad U^\top U=I_r,\;V^\top V=I_r.$$
- $$C=(SU)^\top(SU),\qquad R=\operatorname{chol}(C),\qquad Q=UR^{-1},\qquad Q^\top Q\approx I_r.$$
- $$U\leftarrow Q,\qquad V\leftarrow VR^\top,\qquad UV^\top\ \text{unchanged}.$$

## Implementation notes

Integrate this at the low-rank weight or optimizer-state update, not at the dense matrix multiplication itself. Represent a selected linear-layer weight as $W=W_0+UV^\top$, with $U\in\mathbb{R}^{d_{out}\times r}$ and $V\in\mathbb{R}^{d_{in}\times r}$, and obtain the dense gradient $G=\partial L/\partial W$ either explicitly for a small benchmark or through matrix-free products. At each update, first form the tangent-projected gradient $H=P_{U,V}(G)$ using the displayed projector, then update $U,V$ with the chosen factor-gradient rule or with a rank-$r$ factorization of $H$. Every $K$ steps, draw a fixed or refreshed sketch $S\in\mathbb{R}^{s\times d_{out}}$ with $s=r+8$ or $2r$, compute $Y=SU$, $C=Y^\top Y+\epsilon I$, and the Cholesky factor $R=\operatorname{chol}(C)$. Replace $U$ by $UR^{-1}$ and $V$ by $VR^\top$; this preserves the represented low-rank matrix while reconditioning the basis. In distributed training, compute $SU$ using an all-reduce on only the $s\times r$ sketch Gram matrix rather than a full QR synchronization. Measure $\|U^\top U-I\|_F$, projector residual $\|G-H\|_F$, communication volume, wall-clock time, and loss. First test rank-8 and rank-16 LoRA on one Transformer MLP or attention projection using RoBERTa-base on GLUE, comparing ordinary QR, no reorthogonalization, and sketch-Cholesky QR. A successful signal is equal validation accuracy and loss trajectory with lower orthogonalization time or communication, while the no-reorthogonalization baseline develops worse conditioning.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built a NumPy MVP implementing the standard tangent-space projector and sketch-Cholesky factor reconditioning. The math checks confirmed factor-product invariance (2.35e-16 relative error), sketch-orthogonality (7.54e-6 error), and projector normality (9.82e-15), while reducing an intentionally ill-conditioned factor from condition number 8.03e7 to 4.08. In the tiny regression run, sketch and exact QR reached essentially identical loss, but sketch reconditioning was slower than QR (0.308s vs 0.221s) and did not provide Euclidean orthogonality; therefore no optimization win was observed.

### Mechanism check

- Verdict: Built a NumPy MVP implementing the standard tangent-space projector and sketch-Cholesky factor reconditioning. The math checks confirmed factor-product invariance (2.35e-16 relative error), sketch-orthogonality (7.54e-6 error), and projector normality (9.82e-15), while reducing an intentionally ill-conditioned factor from condition number 8.03e7 to 4.08. In the tiny regression run, sketch and exact QR reached essentially identical loss, but sketch reconditioning was slower than QR (0.308s vs 0.221s) and did not provide Euclidean orthogonality; therefore no optimization win was observed.
- Confidence: 8/10
- Limitations: This is a small dense CPU NumPy regression benchmark, not a Transformer or distributed communication test. The sketch uses s=r+8 rows and is not expected to preserve Euclidean orthogonality as well as a full QR; only sketch-orthogonality and conditioning were evaluated. No GPU, memory, multi-seed, wall-clock scaling, or downstream validation-accuracy experiment was tested.

## Artifacts

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

## Disclaimer

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