How Much Overparameterization Is Needed for ALS in Tensor Decomposition?

Let

$$T=\sum_{j=1}^{r} a_j\otimes b_j\otimes c_j,$$

where $A=[a_1\ \cdots\ a_r]$, $B=[b_1\ \cdots\ b_r]$, and $C=[c_1\ \cdots\ c_r]$ are $n\times r$ factor matrices and $r\ll n$. Consider the following smoothed-analysis setting. Start from arbitrary well-conditioned matrices $\bar A,\bar B,\bar C$. Independently perturb every factor by Gaussian noise:

$$a_i-\bar a_i,\ b_i-\bar b_i,\ c_i-\bar c_i \sim \mathcal{N}\!\left(0,\frac{\rho^2}{n}I_n\right), \qquad \rho\approx\frac{1}{\operatorname{poly}(r)}.$$

Given $T$, run ALS, gradient descent, or another iterative algorithm from random initialization on

$$\min_{x_i,y_i,z_i\in\mathbb{R}^n,\ i\in[k]} \left\|T-\sum_{i=1}^{k}x_i\otimes y_i\otimes z_i\right\|_F^2.$$

1. What is the smallest value $k=k(r)$ for which ALS, or another iterative algorithm such as gradient descent, converges to the global optimum with high probability over the smoothed instance?

2. Does subquadratic overparameterization $k=o(r^2)$ suffice to find, with high probability over the smoothed instance and in time $\operatorname{poly}(n,r,\log(1/\epsilon))$, a rank-$k$ decomposition satisfying

$$\left\|T-\sum_{i=1}^{k}x_i\otimes y_i\otimes z_i\right\|_F \leq \epsilon\|T\|_F?$$

1. Conversely, can one prove that there is a universal constant $c>0$ such that ALS, gradient descent, and related iterative methods require $k=r^{1+c}$? More precisely, for $k\leq r^{1+c}$, does the algorithm converge to a solution of positive objective value with constant probability on a smoothed instance?

A particularly compelling lower bound would hold for random or smoothed rank-$r$ tensors rather than only for a worst-case pathological tensor. It is also of interest to determine whether the lower bound can approach $k=r^{2-c}$ for a small constant $c>0$.