Robust Tensor Regression with Nonconvexity: Algorithmic and Statistical Theory

Technical Summary: Robust Tensor Regression with Nonconvexity: Algorithmic and Statistical Theory

Problem Statement
Tensor regression is a critical tool for analyzing high-dimensional, multi-dimensional data structures prevalent in fields such as neuroimaging, finance, and computer vision. While existing tensor regression methods effectively capture low-rank structures, they often rely on convex relaxations (such as the tensor tubal nuclear norm, t-TNN) and convex loss functions (e.g., squared loss). These existing approaches face two primary limitations:

1. Sensitivity to Outliers: Convex loss functions, particularly squared loss, are highly sensitive to heavy-tailed noise and outliers, leading to suboptimal estimation.
2. Suboptimal Relaxation: The t-TNN, while a convex surrogate for the tensor tubal rank, provides a loose relaxation. This gap between the rank minimization objective and the convex solution can result in biased estimators and reduced accuracy, a problem exacerbated by the presence of outliers.

Furthermore, while nonconvex regularizers have been successfully applied in sparse learning and matrix completion to reduce bias, their application to tensor regression—specifically for tubal rank—remains unexplored. Additionally, the statistical properties of tensor regression models employing both nonconvex losses and nonconvex regularizers have not been theoretically established.

Methodology
The paper proposes a unified framework for robust tensor regression that incorporates both nonconvex loss functions and nonconvex regularizers within a general optimization setting.

• Model Formulation: The authors consider a regularized M-estimator framework:
  $$\hat{B} \in \arg\min_{B} L_n(B) + \rho_\lambda(B)$$
  where $L_n(B)$ is a differentiable (potentially nonconvex) empirical risk function, and $\rho_\lambda(B)$ is a nonconvex surrogate for the tensor tubal rank.
• Nonconvex Regularization: Instead of the t-TNN, the method employs a nonconvex penalty function applied to the singular values of the tensor in the Fourier domain (derived via t-SVD). The penalty $\rho_\lambda$ is defined as a sum of univariate nonconvex functions (e.g., SCAD, MCP, Geman, Logarithm) applied to the singular values. This approach offers a tighter envelope to the tubal rank function compared to t-TNN, reducing estimation bias.
• General Loss Functions: The framework does not restrict the loss function to be convex. It accommodates a wide range of robust losses, including Huber loss, correntropy-induced loss (C-loss), and minimum distance criterion-induced losses (e.g., for robust logistic regression).
• Algorithmic Framework: To solve the resulting nonconvex optimization problem, the authors develop a unified estimation algorithm based on an iterative reweighting strategy.
  • The algorithm linearizes the nonconvex regularizer and majorizes the loss function quadratically at each iteration.
  • This reduces the subproblem at each step to a weighted tensor singular value thresholding (Wt-SVT) problem.
  • The Barzilai-Borwein rule is utilized for initialization and step-size selection to accelerate convergence.
  • A backtracking strategy ensures the monotonic decrease of the objective function.

Key Contributions

1. Nonconvex Regularization for Tubal Rank: The paper develops a rigorous nonconvex surrogate for the tensor tubal rank. Theoretical analysis demonstrates that this regularizer provides a more accurate approximation to the true tubal rank than the traditional t-TNN, leading to better sparsity and reduced bias.
2. Unified Nonconvex Framework: A general framework is established that allows for simultaneous nonconvexity in both the loss and penalty functions. This flexibility accommodates diverse models, including linear models, generalized linear models (GLMs), and various robust regression variants.
3. Algorithmic Convergence: The authors establish global convergence guarantees for the proposed iterative algorithm. Under mild assumptions (including the Kurdyka-Łojasiewicz (KŁ) property), the sequence generated by the algorithm is proven to converge to a stationary point. The convergence rate is shown to be at least sublinear, with linear convergence or finite-step convergence achievable under specific conditions (e.g., for MCP/SCAD penalties).
4. Statistical Theory: The paper derives general statistical properties for the stationary points of the proposed framework, including bounds on the Frobenius norm error, nuclear norm error, and prediction error. These results are applied to specific models:
   • Linear Tensor Regression: Under sub-Gaussian noise.
   • Generalized Linear Models (GLMs): Covering logistic and log-linear models.
   • Adaptive Huber Regression: Extending adaptive Huber methods to tensors to handle heavy-tailed noise.
   • Correntropy-Induced Loss (C-loss) and Minimum Distance Criterion: Novel robust tensor regression models for handling outliers.
     The theoretical results show that the estimation error scales with $\sqrt{r d d_3 / n}$, where $r$ is the tubal rank, $d$ is the dimension, and $n$ is the sample size.

Results

• Theoretical: The paper proves that under local restricted strong convexity (LRSC) and regularity conditions, the proposed estimators achieve statistical consistency. The bounds indicate that nonconvex penalties (characterized by a constant $C_{\rho'_\lambda}$) can lead to faster statistical rates compared to convex counterparts.
• Numerical Experiments: Extensive simulations on synthetic data and application studies demonstrate the effectiveness of the proposed methods.
  • Robustness: In the presence of heavy-tailed noise (t-distribution, Pareto distribution) and outliers, the proposed nonconvex methods (particularly those using C-loss or Adaptive Huber loss) significantly outperform traditional least squares and t-TNN regularized methods in terms of estimation error and rank recovery.
  • Rank Estimation: Nonconvex penalties consistently yield estimated ranks closer to the true tubal rank compared to t-TNN.
  • Convergence: The objective function value decreases monotonically in all tested scenarios, validating the theoretical convergence results.
  • Classification: In logistic regression tasks with misspecification and corrupted predictors, the proposed robust logistic regression via minimum distance criterion achieves higher prediction accuracy and more stable rank estimation than standard MLE-based approaches.

Significance
The paper claims to fill a critical gap in the literature by being the first to explore the statistical properties of nonconvex tensor regression with tubal rank. By moving beyond convex relaxations and convex losses, the proposed framework offers a more robust and accurate approach for high-dimensional tensor data analysis, particularly in scenarios involving heavy-tailed noise and outliers. The development of a globally convergent algorithm for such nonconvex problems provides a practical and theoretically sound tool for researchers and practitioners in fields dealing with complex multi-dimensional data. The work suggests that nonconvex surrogates can effectively balance rank estimation capability and bias reduction, offering superior performance over existing convex methods.