mlsanityData to 7 Oct 2026

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

arXiv 2206.08756 ↗First posted 17 Jun 2022math.ST cs.LG math.OCcited by 15

Not on the map. Why?

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.

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

Builds on

64 of 119 references.

References · 64

  1. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
  2. 2019Benign Overfitting in Linear Regressioncited by 544
  3. 2017Implicit Regularization in Matrix Factorizationcited by 318
  4. 2021Deep learning: a statistical viewpointcited by 239
  5. 2020Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learningcited by 148
  6. 2021Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolationcited by 130
  7. 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
  8. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 82
  9. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  10. 2014A statistical model for tensor PCAcited by 72
  11. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  12. 2017Tensor SVD: Statistical and Computational Limitscited by 52
38 more
  1. 2020Reducibility and Statistical-Computational Gaps from Secret Leakagecited by 50
  2. 2016Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statisticscited by 45
  3. 2021Implicit Regularization in Tensor Factorizationcited by 43
  4. 2019Subexponential-Time Algorithms for Sparse PCAcited by 41
  5. 2020An Optimal Statistical and Computational Framework for Generalized Tensor Estimationcited by 39
  6. 2020Computational Barriers to Estimation from Low-Degree Polynomialscited by 38
  7. 2013Square Deal: Lower Bounds and Improved Relaxations for Tensor Recoverycited by 37
  8. 2015A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurementscited by 34
  9. 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
  10. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  11. 2019Computational Hardness of Certifying Bounds on Constrained PCA Problemscited by 30
  12. 2020Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limitscited by 29
  13. 2014Multilinear tensor regression for longitudinal relational datacited by 28
  14. 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
  15. 2017On Polynomial Time Methods for Exact Low Rank Tensor Completioncited by 27
  16. 2021Generalized Low-rank plus Sparse Tensor Estimation by Fast Riemannian Optimizationcited by 24
  17. 2016Non-Convex Projected Gradient Descent for Generalized Low-Rank Tensor Regressioncited by 23
  18. 2020Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limitcited by 23
  19. 2017Tensor-on-tensor regressioncited by 22
  20. 2015Bayesian Tensor Regressioncited by 21
  21. 2021Optimal Spectral Recovery of a Planted Vector in a Subspacecited by 21
  22. 2021Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recoverycited by 21
  23. 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
  24. 2015Parsimonious Tensor Response Regressioncited by 20
  25. 2021Understanding Deflation Process in Over-parametrized Tensor Decompositioncited by 20
  26. 2016Low-rank tensor completion: a Riemannian manifold preconditioning approachcited by 19
  27. 2021Provable Tensor-Train Format Tensor Completion by Riemannian Optimizationcited by 17
  28. 2017Multilayer tensor factorization with applications to recommender systemscited by 16
  29. 2019ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketchingcited by 14
  30. 2021The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomialscited by 14
  31. 2021Clustering a Mixture of Gaussians with Unknown Covariancecited by 14
  32. 2018A novel approach for fusion of heterogeneous sources of datacited by 13
  33. 2021Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergencecited by 13
  34. 2020Computationally efficient sparse clusteringcited by 12
  35. 2020Understanding Implicit Regularization in Over-Parameterized Single Index Modelcited by 12
  36. 2020Inference for Low-rank Tensors -- No Need to Debiascited by 12
  37. 2016Learning from Multiway Data: Simple and Efficient Tensor Regressioncited by 11
  38. 2016STORE: Sparse Tensor Response Regression and Neuroimaging Analysiscited by 11

50 most cited of 64 All 64 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 3; 2024: 7; 2025: 3; 2026: 1.

15 papers.

Sort:

  1. 2024Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descentcited by 7
  2. 2024Factor Augmented Tensor-on-Tensor Neural Networkscited by 7
  3. 2023Computational Lower Bounds for Graphon Estimation via Low-degree Polynomialscited by 6
  4. 2023Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regressioncited by 4
  5. 2024Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decompositioncited by 4
  6. 2025A Scalable Factorization Approach for High-Order Structured Tensor Recoverycited by 4
  7. 2023Online Tensor Learning: Computational and Statistical Trade-offs, Adaptivity and Optimal Regretcited by 3
  8. 2024Robust Low-rank Tensor Train Recoverycited by 2
  9. 2024Efficient Decision Trees for Tensor Regressionscited by 1
  10. 2025Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descentcited by 1
  11. 2022Elliptically-Contoured Tensor-variate Distributions with Application to Improved Image Learningcited by 0
  12. 2024Near-Optimal differentially private low-rank trace regression with guaranteed private initializationcited by 0
3 more
  1. 2024Statistical Inference in Tensor Completion: Optimal Uncertainty Quantification and Statistical-to-Computational Gapscited by 0
  2. 2025Guaranteed Noisy CP Tensor Recovery via Riemannian Optimization on the Segre Manifoldcited by 0
  3. 2026Structured Adaptive Tensor Prediction for Streaming Datacited by 0