# Non-Convex Projected Gradient Descent for Generalized Low-Rank Tensor Regression

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Nov 2016.

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

- [GaLore: Memory-Efficient LLM Training by Gradient Low-Rank Projection](https://mlsanity.com/paper/2403.03507/) (2024)
- [Fira: Can We Achieve Full-rank Training of LLMs Under Low-rank Constraint?](https://mlsanity.com/paper/2410.01623/) (2024)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Learning by Turning: Neural Architecture Aware Optimisation](https://mlsanity.com/paper/2102.07227/) (2021)
- [VeLoRA: Memory Efficient Training using Rank-1 Sub-Token Projections](https://mlsanity.com/paper/2405.17991/) (2024)
- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [Propulsion: Steering LLM with Tiny Fine-Tuning](https://mlsanity.com/paper/2409.10927/) (2024)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [Gradient Weight-normalized Low-rank Projection for Efficient LLM Training](https://mlsanity.com/paper/2412.19616/) (2024)
- [Parameter-Efficient Fine-Tuning of Large Language Models using Semantic Knowledge Tuning](https://mlsanity.com/paper/2410.08598/) (2024)
- [COAP: Memory-Efficient Training with Correlation-Aware Gradient Projection](https://mlsanity.com/paper/2412.00071/) (2024)
- [A Scalable Factorization Approach for High-Order Structured Tensor Recovery](https://mlsanity.com/paper/2506.16032/) (2025)
- [CeCNN: Copula-enhanced convolutional neural networks in joint prediction of refraction error and axial length based on ultra-widefield fundus images](https://mlsanity.com/paper/2311.03967/) (2023)
- [Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Lifting](https://mlsanity.com/paper/2602.05887/) (2026)
- [Multi-dimensional domain generalization with low-rank structures](https://mlsanity.com/paper/2309.09555/) (2023)
- [Robust Low-rank Tensor Train Recovery](https://mlsanity.com/paper/2410.15224/) (2024)
- [Tensor Methods in High Dimensional Data Analysis: Opportunities and Challenges](https://mlsanity.com/paper/2405.18412/) (2024)
- [GWT: Scalable Optimizer State Compression for Large Language Model Training](https://mlsanity.com/paper/2501.07237/) (2025)
- [Lightweight Auto-bidding based on Traffic Prediction in Live Advertising](https://mlsanity.com/paper/2508.06069/) (2025)
- [Near-Optimal differentially private low-rank trace regression with guaranteed private initialization](https://mlsanity.com/paper/2403.15999/) (2024)
- [An Interdisciplinary and Cross-Task Review on Missing Data Imputation](https://mlsanity.com/paper/2511.01196/) (2025)
- [Tensor Completion using Subspace Information](https://mlsanity.com/paper/2609.24501/) (2026)
- [On-Policy Parameter Update Direction Underlies Generalization in LLM Post-Training](https://mlsanity.com/paper/2609.36659/) (2026)

## Abstract (arXiv)

In this paper, we consider the problem of learning high-dimensional tensor regression problems with low-rank structure. One of the core challenges associated with learning high-dimensional models is computation since the underlying optimization problems are often non-convex. While convex relaxations could lead to polynomial-time algorithms they are often slow in practice. On the other hand, limited theoretical guarantees exist for non-convex methods. In this paper we provide a general framework that provides theoretical guarantees for learning high-dimensional tensor regression models under different low-rank structural assumptions using the projected gradient descent algorithm applied to a potentially non-convex constraint set Theta in terms of its localized Gaussian width. We juxtapose our theoretical results for non-convex projected gradient descent algorithms with previous results on regularized convex approaches. The two main differences between the convex and non-convex approach are: (i) from a computational perspective whether the non-convex projection operator is computable and whether the projection has desirable contraction properties and (ii) from a statistical upper bound perspective, the non-convex approach has a superior rate for a number of examples. We provide three concrete examples of low-dimensional structure which address these issues and explain the pros and cons for the non-convex and convex approaches. We supplement our theoretical results with simulations which show that, under several common settings of generalized low rank tensor regression, the projected gradient descent approach is superior both in terms of statistical error and run-time provided the step-sizes of the projected descent algorithm are suitably chosen.