Computational and Statistical Guarantees for Tensor-on-Tensor Regression With Tensor Train Decomposition.

Area of Science:

• Machine Learning
• Numerical Analysis
• Tensor Computations

Background:

• Tensor-on-tensor (ToT) regression generalizes tensor recovery but faces storage and computational challenges.
• Tensor decomposition, specifically the tensor train (TT) format, offers efficiency improvements for ToT regression.
• A gap exists between the theoretical analysis and practical performance of TT-based ToT models.

Purpose of the Study:

• To theoretically analyze the TT-based ToT regression model, focusing on error bounds under the restricted isometry property (RIP).
• To develop and evaluate efficient optimization algorithms for solving the constrained least-squares problem in TT-based ToT regression.
• To compare the performance and complexity of proposed algorithms, namely iterative hard thresholding (IHT) and Riemannian gradient descent (RGD).

Main Methods:

• Error analysis for a constrained least-squares optimization problem assuming the regression operator satisfies RIP.
• Development of two optimization algorithms: iterative hard thresholding (IHT) using TT-singular value decomposition (TT-SVD) and Riemannian gradient descent (RGD).
• Analysis of spectral initialization and linear convergence rates for both IHT and RGD algorithms under RIP conditions.

Main Results:

• Theoretical upper error bounds and minimax lower bounds were derived, showing polynomial dependence on the order $N+M$.
• Both IHT and RGD algorithms achieve linear convergence rates with spectral initialization when RIP is satisfied.
• RGD offers reduced storage complexity compared to IHT by optimizing factors on the Stiefel manifold, but with slightly worse recovery performance.

Conclusions:

• The TT-based ToT regression model's theoretical properties and algorithmic solutions are elucidated.
• IHT and RGD provide efficient methods for solving TT-based ToT regression, with distinct trade-offs in storage and recovery.
• Experimental results validate the theoretical findings and algorithmic effectiveness.