# Beyond Lazy Training for Over-parameterized Tensor Decomposition

arXiv: https://arxiv.org/abs/2010.11356 · HTML: https://mlsanity.com/paper/2010.11356/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2020.

## Built on by (most cited first, 15 of 15)

- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021)
- [Implicit Regularization in Tensor Factorization](https://mlsanity.com/paper/2102.09972/) (2021)
- [Understanding Deflation Process in Over-parametrized Tensor Decomposition](https://mlsanity.com/paper/2106.06573/) (2021)
- [Understanding Augmentation-based Self-Supervised Representation Learning via RKHS Approximation and Regression](https://mlsanity.com/paper/2306.00788/) (2023)
- [Optimal Gradient-based Algorithms for Non-concave Bandit Optimization](https://mlsanity.com/paper/2107.04518/) (2021)
- [Going Beyond Linear RL: Sample Efficient Neural Function Approximation](https://mlsanity.com/paper/2107.06466/) (2021)
- [Depth Separation with Multilayer Mean-Field Networks](https://mlsanity.com/paper/2304.01063/) (2023)
- [Implicit Regularization for Group Sparsity](https://mlsanity.com/paper/2301.12540/) (2023)
- [Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion](https://mlsanity.com/paper/2402.06756/) (2024)
- [Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decomposition](https://mlsanity.com/paper/2210.00346/) (2022)
- [What Makes Data Suitable for a Locally Connected Neural Network? A Necessary and Sufficient Condition Based on Quantum Entanglement](https://mlsanity.com/paper/2303.11249/) (2023)
- [Guided by the Experts: Provable Feature Learning Dynamic of Soft-Routed Mixture-of-Experts](https://mlsanity.com/paper/2510.07205/) (2025)
- [Feature learning is decoupled from generalization in high capacity neural networks](https://mlsanity.com/paper/2507.19680/) (2025)
- [Nonlinear Matrix Approximation with Radial Basis Function Components](https://mlsanity.com/paper/2106.02018/) (2021)

## Abstract (arXiv)

Over-parametrization is an important technique in training neural networks. In both theory and practice, training a larger network allows the optimization algorithm to avoid bad local optimal solutions. In this paper we study a closely related tensor decomposition problem: given an l-th order tensor in (Rd)otimes l of rank r (where rll d), can variants of gradient descent find a rank m decomposition where m > r? We show that in a lazy training regime (similar to the NTK regime for neural networks) one needs at least m = Omega(dl-1), while a variant of gradient descent can find an approximate tensor when m = O^*(r2.5llog d). Our results show that gradient descent on over-parametrized objective could go beyond the lazy training regime and utilize certain low-rank structure in the data.