On the Optimization Landscape of Tensor Decompositions
Non-convex optimization with local search heuristics has been widely used in machine learning, achieving many state-of-art results. It becomes increasingly important to understand why they can work for these NP-hard problems on typical data. The landscape of many objective functions in learning has been conjectured to have the geometric property that "all local optima are (approximately) global optima", and thus they can be solved efficiently by local search algorithms. However, establishing such property can be very difficult.
In this paper, we analyze the optimization landscape of the random over-complete tensor decomposition problem, which has many applications in unsupervised leaning, especially in learning latent variable models. In practice, it can be efficiently solved by gradient ascent on a non-convex objective. We show that for any small constant ε > 0, among the set of points with function values (1 + ε)-factor larger than the expectation of the function, all the local maxima are approximate global maxima. Previously, the best-known result only characterizes the geometry in small neighborhoods around the true components. Our result implies that even with an initialization that is barely better than the random guess, the gradient ascent algorithm is guaranteed to solve this problem. Our main technique uses Kac-Rice formula and random matrix theory. To our best knowledge, this is the first time when Kac-Rice formula is successfully applied to counting the number of local optima of a highly-structured random polynomial with dependent coefficients.
### Summary
The paper analyzes the landscape of tensor decomposition problem. Specifically, it studies random over-complete tensors. The associated objective function is nonconvex, yet in practice simple methods based on gradient ascent are observed to solve this problem. This paper proves why we should expect such outcome by showing that there is almost no local maxima other than the global maxima of the problem when the optimization is initialized by any solution that is slightly better than random guess. Importantly, it is shown that these initial points do not have to be close to the true components of the tensor. This is an interesting result and well written paper. The analysis involves two steps: local (points close to true components) and global (point far from true components). The number of local maxima in each case is analyzed and shown to be exactly 2n for the former and almost nonexistent for the latter. 
### Questions
1. Authors mention that in practice gradient ascent type algorithms succeed. Do these algorithms use any specific initialization that meets your criterion? More precisely, do they use a scheme to produce initialization which is slightly better than chance and thus the objective value is slightly greater than 3*n?
IF YES: Please elaborate briefly how this is done or provide a reference.
IF NO: Any idea how such initial points could be generated easily? Could it be a very hard problem on its own?
2. The analysis is performed on random tensors, where each true component is assumed to be drawn iid from Gaussian distribution N (0, I). It seems to be a strong assumption and not true for real world problems. While I am not disputing the importance of the result provided in this paper, I was wondering if the authors had thoughts about analysis scenarios that could potentially explain the success of local schemes in a broader setup? For example, performing a worst-case analysis (i.e. choosing the worst tensors) and then showing that these worst tensors form a negligible fraction of the space of tensors? This would go beyond the Gaussian setting and may be more pertinent to explaining why local search succeeds on real world problems.
### Minor Comments
1. Lemma 2.2. Eq. 2.1, the first E is missing a | at the begining right after [.
2. Lines 80, 84, 123 local minima should be local maxima?
3. You refer to hard optimization as nonconvex, but since your task in 1.1. is defined as a maximization, concave functions are actually ideal for that. To avoid confusion around minimization/maximization/nonconvexity, you might want to replace 1.1 from Max f(x) with Min -f(x) so that everything remains a minimization, and thus nonconvexity implies hardness. In that case, you can also ignore my comment 2.