Research map / Optimization / Implicit bias and generalization
On the Crucial Role of Initialization for Matrix Factorization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Nyström initialization (X0 = AΩ) for ScaledGD in symmetric and asymmetric matrix factorization, proving quadratic/one-step convergence, and extends it to LoRA as NoRA/NoRA+ with gains on LLM and diffusion finetuning.
Problem
Global convergence of nonconvex, nonsmooth Burer-Monteiro matrix factorization is slow under standard small initialization (linear rates, saddle at origin), and LoRA initialization is typically costly or unprincipled.
Approach
Initialize the factors via a Nyström-style sketch X0 = AΩ so that iterates stay in the column space of A and remain full rank; with ScaledGD this yields quadratic (symmetric) or one-step (asymmetric) convergence, and the same initialization is applied to LoRA weights using W0 in place of A.
Key results
- Nyström-initialized ScaledGD converges quadratically in the symmetric exact-parametrized case (O(log log(1/ε)) after linear phase) and in one step for asymmetric exact-parametrized problems.
- NoRA improves OPT-1.3B few-shot average accuracy to 75.0 vs 73.2 for LoRA; NoRA+ reaches 75.1.
- On LLaMA2-7B commonsense reasoning, NoRA+ averages 78.92 vs 77.6 reported for LoRA; on Gemma-7B GSM8K, NoRA reaches 78.62 vs 76.72 for LoRA.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Nyström initialization instead of LoRA initialization | LoRA · OPT-1.3B few-shot learning (avg) | accuracy: 73.2 -> 75.0 | Helped |
| Use Nyström initialization with preconditioning instead of LoRA-P | LoRA-P · OPT-1.3B few-shot learning (avg) | accuracy: 73.2 -> 75.1 | Helped |
| Use Nyström initialization | LoRA · StableDiffusion v1.4 subject-driven generation | training loss: 0.092$\pm 0.012$ -> 0.084$\pm 0.017$ | Helped |
| Use Nyström initialization with preconditioning | LoRA-P · StableDiffusion v1.4 subject-driven generation | training loss: 0.093$\pm 0.012$ -> 0.084$\pm 0.015$ | Helped |
| Use Nyström initialization | LoRA · LLaMA-7B commonsense reasoning (avg) | accuracy: 76.19 -> 76.69 | Helped |
| Use Nyström initialization | LoRA · LLaMA2-7B commonsense reasoning (avg) | accuracy: 77.6 -> 78.76 | Helped |
| Use Nyström initialization with preconditioning | LoRA-P · LLaMA2-7B commonsense reasoning (avg) | accuracy: 78.35 -> 78.92 | Helped |
| Use Nyström initialization | LoRA · GSM8K | accuracy: 76.72 -> 78.62 | Helped |
| Use Nyström initialization with preconditioning | LoRA-P · GSM8K | accuracy: 77.03 -> 78.47 | Helped |
| Use Nyström initialization rather than small initialization | ScaledGD on symmetric exact-parametrized matrix factorization · Symmetric exact-parametrized matrix factorization | convergence rate: linear -> quadratic | Helped |
| Perturb Nyström initialization by adding residual-space noise (ablation) | ScaledGD on symmetric exact-parametrized matrix factorization · Symmetric exact-parametrized matrix factorization | convergence rate: quadratic -> linear | Hurt |
| Use Nyström initialization | Modified ScaledGD · Asymmetric exact-parametrized matrix factorization | iterations to global convergence: one-step convergence | Helped |
Surprising findings
- Setting the adapter Y0 to zero (as in standard LoRA) is justified by the asymmetric Nyström initialization, which achieves one-step convergence rather than being a stability-only choice.
- Singular values with larger magnitude, not only top-r ones, show large change after LoRA finetuning, suggesting that directional alignment with W0 is useful beyond top singular vectors.
Limitations
- Theory covers exact- and over-parametrized cases with a w.h.p. condition on rank of X0; under-parametrized results are only to weak optima and neighborhoods.
- Experiments on LLM and diffusion finetuning are single-setting with modest gains (e.g., 0.5 average on LLaMA-7B) and small test sets; LoRA results on LLaMA2-7B are taken from prior work.
- Nyström sketch is used only for full-rankness; recovery properties of the sketch are not explored.
Experimental setup
Datasets: GLUE SuperGLUE MetaMathQA-100K commonsense reasoning 8-dataset merge (BoolQ, PIQA, SIQA, HellaSwag, WinoGrande, ARC, OBQA)
Benchmarks: SST-2 WSC BoolQ CB RTE ReCoRD MultiRC SQuAD PIQA SIQA HellaSwag WinoGrande
Metrics: test accuracy optimality error ||XX^T - A||_F training loss
Baselines: LoRA LoRA-P PiSSA OLoRA prefix tuning GD AltGD
Builds on: ScaledGD LoRA PiSSA OLoRA
Closest papers by meaning
- Preconditioning Matters: Fast Global Convergence of Non-convex Matrix Factorization via Scaled Gradient Descent (NeurIPS 2023 · similarity 0.92)
- Convergence of Alternating Gradient Descent for Matrix Factorization (NeurIPS 2023 · similarity 0.91)
- Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization (NeurIPS 2021 · similarity 0.91)
- Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks (NeurIPS 2024 · similarity 0.91)
- In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting (AAAI 2025 · similarity 0.90)
- How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization (ICLR 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.