# Adaptive Householder Gradient Subspaces

- ID: 2798
- Canonical URL: https://synthcore.org/idea/2798/adaptive-householder-gradient-subspaces
- API JSON: https://synthcore.org/api/idea/2798.json
- API Markdown: https://synthcore.org/api/idea/2798.md
- Verification status: unverified
- Source: [arXiv:2608.28941](https://arxiv.org/abs/2608.28941)
- Category: memory
- Solves: memory, stability, speedup
- ML areas: optimizer, training, memory
- Math tags: linear-algebra, numerical-analysis, random-matrix
- Ratings: usefulness 7/10; difficulty 5/10; novelty 5/10

## Idea description

Replace fixed-rank randomized SVD or unstable block Gram–Schmidt in a GaLore-like optimizer with an adaptive blocked randomized range finder using implicit Householder QR. The basis grows in Gaussian blocks until the residual Frobenius energy is below a layer-specific tolerance, allowing compressible layers to use fewer projected dimensions while preserving orthogonality over repeated refreshes.

## Mathematical statement

The paper seeks an orthonormal basis Q for A in R^{m x n} satisfying A approximately Q Q^T A and Q^T Q = I_k, where A is the matrix being approximated, Q has k columns, and I_k is the k x k identity. Its adaptive algorithm initializes E = ||A||_F^2 and repeatedly samples Omega in R^{n x b} with independent standard Gaussian entries, forms a residual sketch, and adds a block of basis vectors until E <= sigma^2, where b is the block size and sigma is the prescribed absolute residual tolerance. Instead of explicitly materializing Q, the orthogonal basis is represented as a product of block Householder reflectors Q = product_{i=0}^k (I - V_{0:j,i} T_i V_{0:j,i}^T), where V_{0:j,i} contains the Householder vectors for block i and T_i is the compact triangular factor defining that block reflector. Each reflector is orthogonal up to floating-point error, avoiding the loss of orthogonality associated with unreorthogonalized Gram–Schmidt. For a neural-network gradient G, use R_0 = G and, after adding block Q_i, update R_{i+1} = (I - Q_i Q_i^T)R_i. The projected gradient is Q Q^T G, while optimizer moments can be stored in the reduced coordinates Q^T G.

## Key formulas

- $$A\approx QQ^{T}A,\qquad Q^{T}Q=I_k.$$
- $$Q=\prod_{i=0}^{k}\left(I-V_{0:j,i}T_iV_{0:j,i}^{T}\right).$$
- $$E_0=\lVert A\rVert_F^2,\qquad \text{add Gaussian blocks while }E>\sigma^2.$$
- $$R_{i+1}=(I-Q_iQ_i^T)R_i,\qquad E_{i+1}=\lVert R_{i+1}\rVert_F^2,\qquad \widehat G=QQ^TG.$$

## Implementation notes

Integrate this at the gradient-compression and optimizer-state update point for large linear layers, attention projections, or embeddings. Every S optimizer steps, reshape the layer gradient G into a matrix in R^{m x n}. Set R = G, E = ||G||_F^2, and maintain an empty list of Householder blocks. Pseudocode: `while E > sigma^2 and num_columns < k_max: Omega = randn(n,b); Y = R @ Omega; apply all previous reflectors to remove components in the existing span; compute an in-place blocked Householder QR of Y; store V_i and compact T_i; define Q_i(x) = x - V_i @ (T_i @ (V_i.T @ x)); append (V_i,T_i); R = R - Q_i(Q_i.T @ R); E = ||R||_F^2; end`. Apply the stored reflectors to G to obtain reduced coordinates Z = Q^T G. Run AdamW or SGD on Z, storing first and second moments with shape k x n rather than m x n, then reconstruct the parameter update as Q times the reduced update. Store reflector factors in FP32 even when matrix products use BF16 or FP16. Initially compute the residual norm exactly after each block; later test Hutchinson estimates if memory bandwidth dominates. The first experiment should use a small Transformer on WikiText-2, comparing fixed-rank GaLore, randomized QR with one-pass Gram–Schmidt, and adaptive Householder QR at equal optimizer-state memory. Measure validation perplexity, peak memory, wall-clock refresh cost, average retained rank, and ||Q^TQ-I||_F. Success means lower orthogonality error, no loss in perplexity, and lower average rank or refresh time at the same memory budget.

## Disclaimer

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