Tensor Ring Decomposition: Optimization Landscape and One-loop Convergence of Alternating Least Squares

Ziang Chen, Yingzhou Li, Jianfeng LuSIAM J. Matrix Anal. Appl 2020 · DOI

TL;DR

This paper investigates the optimization landscape of tensor ring decomposition, a method for compressing high-dimensional data. The authors reveal a surprising "sharp transition" where algorithms can either get stuck in spurious local minima or converge rapidly, depending on how over-parameterized the problem is. This work sheds light on the inherent difficulties of tensor ring decomposition and provides theoretical guarantees for specific algorithmic behaviors.

What Problem Does This Paper Address?

High-dimensional data, common in fields like quantum physics and machine learning, poses a significant challenge due to the "curse of dimensionality." Tensor decomposition methods, such as tensor ring (TR) decomposition, offer a way to represent these high-dimensional tensors more compactly. However, finding the optimal TR representation is notoriously difficult. Existing algorithms, like Alternating Least Squares (ALS), can struggle with spurious local minima, meaning they might converge to a suboptimal solution. This paper aims to understand the optimization landscape of TR decomposition, specifically investigating why it's harder than related methods like tensor train (TT) decomposition, and to establish conditions under which ALS can reliably converge.

Methods

The authors tackle the problem by analyzing the optimization landscape of TR decomposition. They employ a combination of theoretical analysis and numerical experiments.

  • Spurious Local Minima: They construct a specific target tensor and demonstrate the existence of spurious local minima in the TR decomposition problem, even when the model is significantly over-parameterized (i.e., the chosen TR format has a much larger bond dimension than necessary). This is achieved by carefully designing a target tensor and analyzing the objective function.
  • One-Loop Convergence: They prove that under certain conditions, specifically when the TR space is sufficiently over-parameterized (with a bond dimension significantly larger than the target tensor's bond dimension), the ALS algorithm exhibits "one-loop convergence." This means the algorithm converges to the correct solution within a single pass through all the tensor components.
  • Numerical Validation: The theoretical findings are complemented by numerical experiments. They test the stability of the spurious local minima by perturbing the initial guess and observe how often the ALS algorithm gets trapped. They also numerically verify the one-loop convergence by testing it with various parameters and comparing the results for different bond dimensions.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and synthetic data generation for numerical experiments.

Key Insights and Ideas

  • Sharp Transition in Algorithmic Difficulty: The most striking finding is the existence of a sharp transition in the optimization landscape. As the bond dimension of the TR space increases, the problem shifts from being prone to spurious local minima to exhibiting guaranteed fast convergence (one-loop). This is a crucial insight into why TR decomposition can be challenging.
  • Over-parameterization is Key: The paper highlights that while over-parameterization can lead to spurious local minima (as shown in Theorem 3.3), sufficient over-parameterization is what guarantees one-loop convergence (Theorem 4.2). This suggests a delicate balance is needed for efficient TR decomposition.
  • TR vs. TT Differences: The authors note that the difficulties in TR decomposition, particularly the existence of spurious local minima even in over-parameterized settings, are more pronounced than in TT decomposition. This is attributed to the underlying ring structure of TR, which makes the set of TRs of a fixed bond dimension not a closed set, unlike TT.

Key Results

  • Existence of Spurious Local Minima: The paper proves the existence of spurious local minima for TR decomposition, even when the chosen TR format is significantly over-parameterized (bond dimension $r^{d-1}$ for a target tensor with bond dimension $r+1$).
  • One-Loop Convergence: Under mild assumptions and with a sufficiently large bond dimension ($m = r^{d-1}$), the ALS algorithm is proven to converge in one loop (d microsteps) for target tensors with bond dimension $r$.
  • Numerical Evidence for Spurious Minima Stability: Numerical experiments show that ALS can get "trapped" in the vicinity of the constructed spurious local minimum, especially when the initial guess is close to it. The probability of escaping the spurious minimum decreases as the perturbation size decreases.
  • Numerical Verification of One-Loop Convergence Tightness: Numerical results demonstrate that one-loop convergence fails when the bond dimension is just one less than the theoretically guaranteed value ($m = r^{d-1} - 1$), supporting the tightness of the theorem.

Limitations and Future Work

  • Non-Strict Local Minima: The paper focuses on non-strict local minima, meaning the objective function value at the minimum is not necessarily greater than at nearby points. The numerical results suggest these minima can still be "sticky" for ALS.
  • Open Questions on General Convergence: While one-loop convergence is proven for a specific over-parameterized case, the general convergence of ALS for TR decomposition to a stationary point remains an open problem. The authors mention difficulties in ensuring boundedness of the iterates and the accumulation point's rank.
  • Assumptions for One-Loop Convergence: The one-loop convergence proof relies on certain assumptions about the target tensor and the initial guess, which are characterized by zero-measure sets. Future work could explore relaxing these assumptions.
  • Broader Applicability: The theoretical insights gained for TR decomposition might offer guidance for understanding other tensor network formats.

Summary updated

BibTeX
@article{chen2020tensor,
  author = {Ziang Chen and Yingzhou Li and Jianfeng Lu},
  title = {{Tensor Ring Decomposition: Optimization Landscape and One-loop Convergence of Alternating Least Squares}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2020},
  doi = {10.1137/19m1270689},
}
Figure