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.
@cite_16: We consider the computational complexity of optimizing various classes of continuous functions over a simplex, hypercube or sphere.These relatively simple optimization problems have many applications.We review known approximation results as well as negative (inapproximability) results from the recent literature.
* Results for worst-case tensors. It is proved in @cite_16 that the @math -level SoS gives an @math approximation to @math in the case of arbitrary @math -tensors and an @math approximation to @math in the case of @math -tensors with non-negative entries (for technical reasons one can only approximate @math in the former case).