Abstract
This paper introduces ScaledGD, the first algorithm for low-rank tensor completion (using the Tucker decomposition) that is both statistically near-optimal and computationally efficient. By utilizing iteration-varying preconditioners, ScaledGD achieves a linear convergence rate that is independent of the tensor's condition number, effectively overcoming a major bottleneck in high-dimensional data recovery.
Introduction
Tensors are multi-dimensional generalizations of matrices, essential for modeling complex interactions in recommendation systems or hyperspectral imaging. However, tensor completion—recovering a full tensor from a sparse set of observations—is significantly more challenging than matrix completion. Convex approaches like nuclear norm minimization are NP-hard for tensors, while standard nonconvex methods like Gradient Descent (GD) often struggle with "ill-conditioned" data, where varying signal strengths lead to slow convergence.
The primary challenge is finding an algorithm that achieves near-optimal sample complexity while remaining computationally scalable. As shown in the comparison below, ScaledGD provides a superior balance of sample and iteration complexity compared to existing methods.
Methods: The ScaledGD Algorithm
ScaledGD is a nonconvex optimization algorithm characterized by the use of iteration-varying preconditioners. Instead of following the steepest descent path of standard GD, ScaledGD scales the gradient by the inverse of the diagonal blocks of the Hessian. This transformation effectively turns the algorithm into a quasi-Newton method.
The algorithm relies on three key technical components:
- Tucker Decomposition: Modeling the tensor as a small core tensor multiplied by factor matrices for each dimension.
- Spectral Initialization: A tailored starting point derived from observed entries to ensure the algorithm begins within the "region of attraction."
- Scaled Projection: A specialized trimming step that maintains the "incoherence" of factor matrices without disrupting the mathematical symmetries of the Tucker model.
Key Insights
- Condition Number Independence: By scaling the gradient, the convergence rate becomes independent of the condition number ($\kappa$). While standard GD requires significantly more iterations as $\kappa$ increases, ScaledGD maintains a near-constant iteration count.
- Invariance to Parameterization: ScaledGD is "basis-invariant." It naturally accounts for the non-uniqueness of the Tucker decomposition (rotational symmetry), following a trajectory that is invariant to the specific representation of factors.
- The $n^{3/2}$ Barrier: ScaledGD hits the near-optimal sample complexity of $O(n^{3/2})$, which is the conjectured computational barrier for polynomial-time tensor completion algorithms.
Results
Numerical experiments validate the theoretical claims. ScaledGD demonstrates remarkable efficiency, reaching target accuracy in approximately 17 iterations regardless of the condition number. In contrast, the iteration count for standard GD increases quadratically with $\kappa$, exceeding 5,000 iterations for moderately ill-conditioned cases.
The paper proves that ScaledGD succeeds with high probability given a sample complexity of roughly $O(n^{3/2} r^{5/2} \kappa^3 \log^3 n)$. Furthermore, it exhibits linear convergence, meaning the error decreases geometrically, allowing for high-precision recovery in very few steps.
Discussion and Future Work
While ScaledGD represents a significant advancement for Tucker-based tensor completion, several avenues for future research remain:
- CP Decomposition: Extending preconditioning techniques to the Canonical Polyadic (CP) decomposition model.
- Robustness: Adapting the algorithm to handle noisy observations or outliers, as the current theory assumes clean Bernoulli sampling.
- Entrywise Guarantees: Moving beyond total Frobenius norm error to provide entrywise error guarantees for more sensitive applications.
Summary updated