# 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](https://proceedings.mlr.press/v336/arvanitakis26a.html)
2. D. Arvanitakis, V. Srinivas and A. Vijayaraghavan, Guarantees for alternating least squares in overparameterized tensor decompositions, *NeurIPS* (2025). [OpenReview](https://openreview.net/forum?id=9FDErIfoVE)
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](https://arxiv.org/abs/2010.11356)
4. A. Bhaskara, M. Charikar, A. Moitra and A. Vijayaraghavan, Smoothed analysis of tensor decompositions, *STOC* (2014). [arXiv:1311.3651](https://arxiv.org/abs/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](https://doi.org/10.1137/07070111X)

## Source

Imported from [COLT open problems, COLT 2026](https://proceedings.mlr.press/v336/arvanitakis26a.html), 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.