Introduction
In the era of big data, multi-way arrays or tensors have become essential for representing complex, high-dimensional information, such as 3D medical images captured over time or multi-channel sensor data. Tensor-on-tensor regression provides a framework for predicting a tensor response from a tensor covariate. The relationship is typically governed by a high-dimensional parameter tensor. To make estimation feasible, researchers often assume this parameter tensor possesses a low-rank structure.
However, two major hurdles impede the practical application of these models. First, the "Rank Headache": the true intrinsic rank ($r^*$) of the data is rarely known a priori, leading to extensive manual tuning or model misspecification. Second, the "Computational Gap": tensors are mathematically more complex than matrices, often resulting in a significant gap between the theoretical statistical limit of samples needed and the higher number required for practical algorithms to converge.
Riemannian Optimization and Robustness to Over-parameterization
To address these challenges, this research proposes two robust algorithms based on Riemannian Optimization: Riemannian Gradient Descent (RGD) and Riemannian Gauss-Newton (RGN). Unlike standard factorized methods that may require careful pre-conditioning, these algorithms operate directly on the manifold of low-rank tensors. RGD offers a first-order approach with guaranteed linear convergence, while RGN utilizes second-order curvature information to achieve quadratic convergence, allowing for extremely high precision in fewer iterations.
A core contribution of this work is the demonstration that these Riemannian methods are robust to rank over-parameterization. In practice, a user can select a conservative rank estimate $r$ that is larger than the true rank $r^*$. While traditional optimization theory suggests that over-parameterization can lead to singularities and convergence issues, the authors develop new technical tools to prove that RGD and RGN adapt naturally to the over-specified rank without any modifications to the underlying code.
The "Blessing" of the Computational-Statistical Gap
The paper reveals a surprising phenomenon termed the "blessing" of over-parameterization, which is unique to high-order tensors. In standard matrix settings (order 2), over-estimating the rank typically incurs a "price" in the form of increased sample size requirements to maintain statistical accuracy.
As shown in Figure 1, for tensors of order $d \ge 3$, the "computational barrier" ($n_{comp} = O(p^{d/2})$) is already so high that the additional samples theoretically needed to handle a larger rank $r$ are effectively "submerged." This creates a "no cost regime" where over-parameterization is essentially free. For a given problem size $p$, as long as the sample size $n$ is sufficient to overcome the computational gap, the algorithm can handle a wide range of over-specified ranks without any loss in performance.
Key Results and Empirical Validation
The authors rigorously test their theoretical bounds using synthetic datasets generated via Gaussian Ensemble designs. These simulations cover various scenarios, including scalar-on-tensor and matrix trace regression, confirming several key findings:
- Convergence Rates: RGD consistently exhibits linear convergence, while RGN achieves quadratic convergence.
- Statistical Optimality: The estimation error achieved by these algorithms matches the minimax risk lower bound, indicating that no other algorithm can significantly outperform them in terms of accuracy for a given sample size.
- Sample Complexity: For an order-$d$ tensor, the established requirement of $n = \Omega(p^{d/2})$ samples for polynomial-time success is empirically validated.
Conclusion and Future Work
This work provides the first comprehensive convergence analysis for general tensor-on-tensor regression using Riemannian optimization. By identifying the "no cost regime," the authors show that the inherent computational hardness of tensors actually provides a practical advantage: it eliminates the need for precise rank tuning.
Future research will look into the "highly" over-parameterized regime where the model has more parameters than data points (the interpolation regime), a common scenario in deep learning. Additionally, while the current work provides spectral initialization methods for several cases, developing a universal initialization strategy for any arbitrary tensor-on-tensor structure remains an open challenge.
Summary updated