How much overparameterization does ALS need for tensor decomposition?

Alternating least squares (ALS) is a workhorse method for splitting a tensor into rank-one pieces. From a random start, a variant of ALS that is allowed about $r^2$ pieces for a rank-$r$ tensor provably reaches a global optimum. Do far fewer pieces, closer to $r$, suffice, or is $r^2$ a genuine barrier for simple iterative methods?

Problem

Let $T = \sum_{j=1}^{r} a_j \otimes b_j \otimes c_j \in \mathbb{R}^{n \times n \times n}$ with $r \ll n$. Take the instance to be smoothed: each factor is an arbitrary well-conditioned vector plus independent Gaussian noise, $a_j = \bar a_j + g_j$ with $g_j \sim N(0, (\rho^2/n) I_n)$, and likewise for $b_j, c_j$, where $\rho = 1/\mathrm{poly}(r)$. Iterative methods fit $k \ge r$ components by minimizing

$$\Big\| T - \sum_{i=1}^{k} x_i \otimes y_i \otimes z_i \Big\|_F^2 \quad \text{over } x_i, y_i, z_i \in \mathbb{R}^n .$$

ALS fixes two of the three families $\{x_i\}, \{y_i\}, \{z_i\}$, solves the resulting linear least-squares problem for the third, and cycles through the three.

Question (upper bound). Does overparameterization $k = o(r^2)$ suffice for ALS or gradient descent (or another simple iterative method) from random initialization to find, with high probability over the instance and in time $\mathrm{poly}(n, r, \log(1/\epsilon))$, a decomposition with $\big\| T - \sum_{i=1}^{k} x_i \otimes y_i \otimes z_i \big\|_F \le \epsilon \|T\|_F$? Success with constant probability over the initialization, for a fixed instance, is enough.

Question (lower bound). Or is there an absolute constant $c > 0$ such that with $k \le r^{1+c}$ these methods end, with constant probability, at a point of positive objective value?

Background

Tensor decompositions underlie algorithms for latent variable models, mixtures, topic models and independent component analysis [5]. In the worst case they are intractable, but for generic or smoothed tensors there are polynomial-time algebraic algorithms [4]. In practice, however, people run simple iterative heuristics such as ALS and gradient descent, whose behavior is poorly understood. The question is also a clean model of feature learning: the $r$ hidden components are the features, and $k$ measures how much extra capacity an iterative method needs to find them. Arvanitakis, Srinivas and Vijayaraghavan posed it at COLT 2026 [1], pledging a donation of up to $300 to research on amyotrophic lateral sclerosis as the upper and lower bounds meet.

What is known

• Quadratic overparameterization works. A parallel variant of ALS with random initialization and $k = O(r^2)$ converges with high probability to a global optimum, for mildly conditioned rank-$r$ tensors with $n$ large enough compared with $r$ (Arvanitakis, Srinivas and Vijayaraghavan, 2025) [2]. The proof shows that the Khatri–Rao products $x_i \odot y_i$ formed by the algorithm span all $r^2$ pairwise products of the true factors, an argument that needs $k = \Omega(r^2)$.
• Earlier bound. A variant of gradient descent was shown to converge with $k = O(r^{7.5} \log n)$ (Wang, Wu, Lee, Ma and Ge, 2020) [3].
• Evidence for a barrier. Experiments in [2] suggest that ALS needs superlinear overparameterization on random tensors.
• A threshold at $r^2$. Decompositions with about $r^2$ components are easy because they reduce to a matrix problem. The posers know of no algorithm that uses fewer than $r^2$ components without also recovering the unique rank-$r$ decomposition.

What would count as progress

• A proof that ALS or gradient descent with $k = O(r^{2-c})$, for some $c > 0$, converges to a global optimum on smoothed instances.
• A proof that ALS fails with constant probability for $k \le r^{1+c}$ on random or smoothed rank-$r$ tensors. An explicit well-conditioned tensor on which ALS fails unless $k = \Theta(r^2)$ would also be of interest.
• Reproducible experiments that measure, for random tensors, the smallest $k$ at which ALS succeeds as $r$ grows. These would be supporting evidence, not proof.

References

1. D. Arvanitakis, V. Srinivas and A. Vijayaraghavan, Open problem: How much overparametrization is needed for ALS in tensor decomposition?, COLT 2026, PMLR 336 (2026), 7105–7110. PMLR
2. D. Arvanitakis, V. Srinivas and A. Vijayaraghavan, Guarantees for alternating least squares in overparameterized tensor decompositions, NeurIPS (2025). OpenReview
3. X. Wang, C. Wu, J. D. Lee, T. Ma and R. Ge, Beyond lazy training for over-parameterized tensor decomposition, NeurIPS (2020). arXiv:2010.11356
4. A. Bhaskara, M. Charikar, A. Moitra and A. Vijayaraghavan, Smoothed analysis of tensor decompositions, STOC (2014). arXiv:1311.3651
5. T. G. Kolda and B. W. Bader, Tensor decompositions and applications, SIAM Review 51(3) (2009), 455–500. doi:10.1137/07070111X

Source

Imported from COLT open problems, COLT 2026, curated by the Conference on Learning Theory (COLT). Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.