We ask how much overparameterization is needed for simple iterative methods such as alternating least squares (ALS) and gradient descent to decompose a third-order tensor. This question can be viewed as a basic setting to study feature learning: when a rank-$r$ tensor in ambient dimension $n$ has $r\ll n$, the latent rank-one components are the features, and $k$ is the amount of overparameterization used by the algorithm. For rank $r$ tensors, recent work shows that overparametrized rank $k=O(r^2)$ suffices for the popular ALS heuristic (with random initialization) to converge to a global optima. Is the quadratic dependence on $r$ an inherent barrier for ALS-like methods? We pose the open problem of proving convergence to the global optimum for $k=o(r^2)$, or proving that a lower bound on the overparametrized rank of $k=\Omega(r^{1+c})$ for some absolute constant $c>0$ is necessary.

Tensor decomposition is a canonical non-convex optimization problem that is computationally challenging, and yet important due to applications in factor analysis and parameter estimation of latent variable models. In practice, scalable iterative methods, particularly Alternating Least Squares (ALS), remain the workhorse for tensor decomposition despite the lack of global convergence guarantees. A popular approach to tackle challenging non-convex optimization problems is overparameterization--- on input an $n \times n \times n$ tensor of rank $r$, the algorithm can output a decomposition of potentially rank $k$ (potentially larger than $r$). On the theoretical side, overparameterization for iterative methods is challenging to reason about and requires new techniques. The work of Wang et al., (NeurIPS 2020) makes progress by showing that a variant of gradient descent globally converges when overparameterized to $k=O(r^{7.5} \log n)$. Our main result shows that overparameterization provably enables global convergence of ALS: on input a third order $n \times n \times n$ tensor with a decomposition of rank $r \ll n$, ALS overparameterized with rank $k=O(r^2)$ achieves global convergence with high probability under random initialization. Moreover our analysis also gives guarantees for the more general low-rank approximation problem. The analysis introduces new techniques for understanding iterative methods in the overparameterized regime based on new matrix anticoncentration arguments.