Search papers, labs, and topics across Lattice.
This paper investigates the implicit biases of gradient descent and Adam optimizers in the context of low-rank matrix recovery, revealing that gradient descent favors low-rank solutions due to its gauge-equivariance, while Adam does not. The authors establish a structure theorem that characterizes memoryless equivariant update rules and demonstrate that the choice of optimizer significantly affects recovery performance in underdetermined matrix sensing tasks. Notably, they show that gradient descent can achieve a 43-44% reduction in held-out error compared to Adam at low sampling densities, underscoring the importance of optimizer selection in matrix recovery tasks.
Gradient descent can slash held-out error by up to 44% compared to Adam in low-rank matrix recovery, revealing the critical role of optimizer choice in performance outcomes.
Gradient descent on a factored model $W = UV^\top$ is implicitly biased toward low-rank solutions, while Adam, starting from the same small initialization, is not. We trace the difference to the gauge symmetry of the loss, its invariance under $(U, V) \mapsto (UQ, VQ)$. Gradient flow's low-rank mechanism is available to an optimizer only if that optimizer is gauge-equivariant, a condition necessary for the transfer but not sufficient for low-rank recovery. Gradient descent, momentum,"shared-scalar"Adam, Muon, and Shampoo satisfy it. Adam, RMSProp, and the other coordinate-wise methods do not. A structure theorem characterizes the memoryless equivariant rules as exactly the Gram-determined left preconditioners, and a transfer theorem carries gradient flow's pathwise properties to common-scalar flows. We then sort nine update rules on underdetermined matrix sensing by recovery error against the planted ground truth. A one-parameter family from coordinate-wise to shared-scalar preconditioning restores the bias monotonically, isolating anisotropy as the cause. A"spectral schedule"reconciles two opposing reports about Muon: equal-rate updates recover exactly low-rank targets but lose their edge as the spectral tail grows. In transformers, Adam separates two gauge-equivalent initializations at the first step, where the equivariant optimizers stay at float precision, and ends with the per-head invariants $W_Q^\top W_K$ 56% apart in relative Frobenius distance, a gap no per-head rotation can close. On two hyperspectral datasets at matched training loss, gradient descent cuts held-out error by 43-44% at the lowest sampling density, and at lower effective rank. Basis choice is therefore not a tuning detail but a decision about which interpolant the optimizer selects.
