Statistical-Computational Trade-offs in Tensor PCA and Related Problems
  via Communication Complexity
  Tensor PCA is a stylized statistical inference problem introduced by
Montanari and Richard to study the computational difficulty of estimating an
unknown parameter from higher-order moment tensors. Unlike its matrix
counterpart, Tensor PCA exhibits a statistical-computational gap, i.e., a
sample size regime where the problem is information-theoretically solvable but
conjectured to be computationally hard. This paper derives computational lower
bounds on the run-time of memory bounded algorithms for Tensor PCA using
communication complexity. These lower bounds specify a trade-off among the
number of passes through the data sample, the sample size, and the memory
required by any algorithm that successfully solves Tensor PCA. While the lower
bounds do not rule out polynomial-time algorithms, they do imply that many
commonly-used algorithms, such as gradient descent and power method, must have
a higher iteration count when the sample size is not large enough. Similar
lower bounds are obtained for Non-Gaussian Component Analysis, a family of
statistical estimation problems in which low-order moment tensors carry no
information about the unknown parameter. Finally, stronger lower bounds are
obtained for an asymmetric variant of Tensor PCA and related statistical
estimation problems. These results explain why many estimators for these
problems use a memory state that is significantly larger than the effective
dimensionality of the parameter of interest.
