Breaking the Frozen Subspace: Importance Sampling for Low-Rank Optimization in LLM Pretraining

Lin Yang (UCLA) · Zirui Liu (University of Minnesota - Twin Cities) · Haochen Zhang (Rice University) · Tianyi Zhang (Rice University) · Junze Yin (Rice University) · Guanchu Wang (University of North Carolina at Charlotte) · Anshumali Shrivastava (Meta / Rice University) · Vladimir Braverman (Johns Hopkins University; Google)

approximation quality convergence guaranteedominant subspaceempirical evaluation gradient projection importance sampling low-rank optimization memory cost memory-efficient training optimization trajectory optimizer statespretraining taskssubspace selectionweight updates

Low-rank optimization has emerged as a promising approach to enabling memory-efficient training of large language models (LLMs). Existing low-rank optimization methods typically project gradients onto a low-rank subspace, reducing the memory cost of storing optimizer states. A key challenge in these methods is selecting suitable subspaces to ensure an effective optimization trajectory. Most existing approaches select the dominant subspace to preserve gradient information, as this intuitively provides the best approximation. However, we find that in practice, the dominant subspace stops changing during pretraining, thereby constraining weight updates to similar subspaces. In this paper, we propose importance sampling for low-rank optimization in LLM pretraining with a provable convergence guarantee, which the dominant subspace approach does not have. Empirically, we demonstrate that our method significantly outperforms previous methods in LLM pretraining tasks.