# Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 64 of its 119 references that are in the map.
- First posted on arXiv 17 Jun 2022.

## Builds on (most cited first, 30 of 64)

- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning](https://mlsanity.com/paper/2012.09839/) (2020)
- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [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)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics](https://mlsanity.com/paper/1605.00353/) (2016)
- [Implicit Regularization in Tensor Factorization](https://mlsanity.com/paper/2102.09972/) (2021)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [An Optimal Statistical and Computational Framework for Generalized Tensor Estimation](https://mlsanity.com/paper/2002.11255/) (2020)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery](https://mlsanity.com/paper/1307.5870/) (2013)
- [A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements](https://mlsanity.com/paper/1506.06081/) (2015)
- [Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization](https://mlsanity.com/paper/2203.02839/) (2022)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [Computational Hardness of Certifying Bounds on Constrained PCA Problems](https://mlsanity.com/paper/1902.07324/) (2019)
- [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020)
- [Multilinear tensor regression for longitudinal relational data](https://mlsanity.com/paper/1412.0048/) (2014)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [On Polynomial Time Methods for Exact Low Rank Tensor Completion](https://mlsanity.com/paper/1702.06980/) (2017)
- [Generalized Low-rank plus Sparse Tensor Estimation by Fast Riemannian Optimization](https://mlsanity.com/paper/2103.08895/) (2021)
- [Non-Convex Projected Gradient Descent for Generalized Low-Rank Tensor Regression](https://mlsanity.com/paper/1611.10349/) (2016)
- [Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit](https://mlsanity.com/paper/2012.09996/) (2020)

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

- [Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent](https://mlsanity.com/paper/2401.11940/) (2024)
- [Factor Augmented Tensor-on-Tensor Neural Networks](https://mlsanity.com/paper/2405.19610/) (2024)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression](https://mlsanity.com/paper/2305.06199/) (2023)
- [Online Tensor Learning: Computational and Statistical Trade-offs, Adaptivity and Optimal Regret](https://mlsanity.com/paper/2306.03372/) (2023)
- [Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decomposition](https://mlsanity.com/paper/2406.06002/) (2024)
- [A Scalable Factorization Approach for High-Order Structured Tensor Recovery](https://mlsanity.com/paper/2506.16032/) (2025)
- [Robust Low-rank Tensor Train Recovery](https://mlsanity.com/paper/2410.15224/) (2024)
- [Efficient Decision Trees for Tensor Regressions](https://mlsanity.com/paper/2408.01926/) (2024)
- [Statistical Inference in Tensor Completion: Optimal Uncertainty Quantification and Statistical-to-Computational Gaps](https://mlsanity.com/paper/2410.11225/) (2024)
- [Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2512.07490/) (2025)
- [Elliptically-Contoured Tensor-variate Distributions with Application to Improved Image Learning](https://mlsanity.com/paper/2211.06940/) (2022)
- [Near-Optimal differentially private low-rank trace regression with guaranteed private initialization](https://mlsanity.com/paper/2403.15999/) (2024)
- [Guaranteed Noisy CP Tensor Recovery via Riemannian Optimization on the Segre Manifold](https://mlsanity.com/paper/2510.00569/) (2025)
- [Structured Adaptive Tensor Prediction for Streaming Data](https://mlsanity.com/paper/2606.10085/) (2026)

## Abstract (arXiv)

We study the tensor-on-tensor regression, where the goal is to connect tensor responses to tensor covariates with a low Tucker rank parameter tensor/matrix without the prior knowledge of its intrinsic rank. We propose the Riemannian gradient descent (RGD) and Riemannian Gauss-Newton (RGN) methods and cope with the challenge of unknown rank by studying the effect of rank over-parameterization. We provide the first convergence guarantee for the general tensor-on-tensor regression by showing that RGD and RGN respectively converge linearly and quadratically to a statistically optimal estimate in both rank correctly-parameterized and over-parameterized settings. Our theory reveals an intriguing phenomenon: Riemannian optimization methods naturally adapt to over-parameterization without modifications to their implementation. We also prove the statistical-computational gap in scalar-on-tensor regression by a direct low-degree polynomial argument. Our theory demonstrates a "blessing of statistical-computational gap" phenomenon: in a wide range of scenarios in tensor-on-tensor regression for tensors of order three or higher, the computationally required sample size matches what is needed by moderate rank over-parameterization when considering computationally feasible estimators, while there are no such benefits in the matrix settings. This shows moderate rank over-parameterization is essentially "cost-free" in terms of sample size in tensor-on-tensor regression of order three or higher. Finally, we conduct simulation studies to show the advantages of our proposed methods and to corroborate our theoretical findings.