For an @math -variate order- @math tensor @math , define @math to be the maximum value taken by the tensor on the unit sphere. It is known that for a random tensor with i.i.d @math entries, @math w.h.p. We study the problem of efficiently certifying upper bounds on @math via the natural relaxation from the Sum of Squares (SoS) hierarchy. Our results include: - When @math is a random order- @math tensor, we prove that @math levels of SoS certifies an upper bound @math on @math that satisfies [ B A_ ( n q^ ,1-o(1) )^ q 4-1 2 w.h.p. ] Our upper bound improves a result of Montanari and Richard (NIPS 2014) when @math is large. - We show the above bound is the best possible up to lower order terms, namely the optimum of the level- @math SoS relaxation is at least [ A_ ( n q^ ,1+o(1) )^ q 4-1 2 . ] - When @math is a random order- @math tensor, we prove that @math levels of SoS certifies an upper bound @math on @math that satisfies [ B A_ ( O (n) q )^ d 4 - 1 2 w.h.p. ] For growing @math , this improves upon the bound certified by constant levels of SoS. This answers in part, a question posed by Hopkins, Shi, and Steurer (COLT 2015), who established the tight characterization for constant levels of SoS.
Montanari and Richard @cite_8 presented a @math -time algorithm that can certify that the optimal value of @math for a random @math -tensor is at most @math with high probability. Hopkins, Shi, and Steurer @cite_11 improved it to @math with the same running time. They also asked how many levels of SoS are required to certify a bound of @math for @math .
@cite_11 @cite_8
1521197246 2952621790
We study a statistical model for the tensor principal component analysis problem introduced by Montanari and Richard: Given a order- @math tensor @math of the form @math , where @math is a signal-to-noise ratio, @math is a unit vector, and @math is a random noise tensor, the goal is to recover the planted vector @math . For the case that @math has iid standard Gaussian entries, we give an efficient algorithm to recover @math whenever @math , and certify that the recovered vector is close to a maximum likelihood estimator, all with high probability over the random choice of @math . The previous best algorithms with provable guarantees required @math . In the regime @math , natural tensor-unfolding-based spectral relaxations for the underlying optimization problem break down (in the sense that their integrality gap is large). To go beyond this barrier, we use convex relaxations based on the sum-of-squares method. Our recovery algorithm proceeds by rounding a degree- @math sum-of-squares relaxations of the maximum-likelihood-estimation problem for the statistical model. To complement our algorithmic results, we show that degree- @math sum-of-squares relaxations break down for @math , which demonstrates that improving our current guarantees (by more than logarithmic factors) would require new techniques or might even be intractable. Finally, we show how to exploit additional problem structure in order to solve our sum-of-squares relaxations, up to some approximation, very efficiently. Our fastest algorithm runs in nearly-linear time using shifted (matrix) power iteration and has similar guarantees as above. The analysis of this algorithm also confirms a variant of a conjecture of Montanari and Richard about singular vectors of tensor unfoldings. Let @math be a nontrivial @math -ary predicate. Consider a random instance of the constraint satisfaction problem @math on @math variables with @math constraints, each being @math applied to @math randomly chosen literals. Provided the constraint density satisfies @math , such an instance is unsatisfiable with high probability. The problem is to efficiently find a proof of unsatisfiability. We show that whenever the predicate @math supports a @math - probability distribution on its satisfying assignments, the sum of squares (SOS) algorithm of degree @math (which runs in time @math ) refute a random instance of @math . In particular, the polynomial-time SOS algorithm requires @math constraints to refute random instances of CSP @math when @math supports a @math -wise uniform distribution on its satisfying assignments. Together with recent work of [LRS15], our result also implies that polynomial-size semidefinite programming relaxation for refutation requires at least @math constraints. Our results (which also extend with no change to CSPs over larger alphabets) subsume all previously known lower bounds for semialgebraic refutation of random CSPs. For every constraint predicate @math , they give a three-way hardness tradeoff between the density of constraints, the SOS degree (hence running time), and the strength of the refutation. By recent algorithmic results of [AOW15] and [RRS16], this full three-way tradeoff is , up to lower-order factors.