Adaptive Householder Gradient Subspaces
Source paper: A GPU-Accelerated Blocked Adaptive Randomized Range Finder Based on an Implicit Householder QR Decomposition arXiv:2608.28941 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
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.
Formulas
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.
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.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.