OP1 [open] Open Problem 1 (Broad open question): What is the smallest value of k = k(r) so that ALS (or other iterative algorithms like GD) on smoothed instances (under random initialization) converges to the global optimum with high probability (over the smoothed instance)?
OP2 [open] Open Problem 2 (Subquadratic overparameterization for iterative tensor decomposition): Given as input a smoothed tensor T in R^{n x n x n} (arbitrary base factors perturbed by N(0, rho^2/n) noise) with rho = 1/poly(r), does overparametrization of k = o(r^2) suffice for ALS or gradient descent (or other iterative algorithms) to find with high probability (over the randomness in the instance) a rank
OP3 [open] Open Problem 3 (Polynomial lower bound): Can one prove that there exists a universal constant c > 0 such that ALS and gradient descent (and other iterative methods) require overparametrization of k = r^{1+c}, i.e., given a smoothed instance as described earlier and overparametrized rank k <= r^{1+c}, the algorithm converges to a solution of positive objective value with constant probability? (The