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.
Our analysis asymptotically improves the aforementioned bound when @math is growing with @math , and we prove an essentially matching lower bound (but only for the case @math ). Secondly, we consider the case when @math is fixed, and give improved results for the performance of degree- @math SoS (for large @math ), thus answering in part, a question posed by Hopkins, Shi and Steurer @cite_11 .
@cite_11
1897704527
We give a lower bound of @math for the degree-4 Sum-of-Squares SDP relaxation for the planted clique problem. Specifically, we show that on an Erd "os-R 'enyi graph @math , with high probability there is a feasible point for the degree-4 SOS relaxation of the clique problem with an objective value of @math , so that the program cannot distinguish between a random graph and a random graph with a planted clique of size @math . This bound is tight. We build on the works of Deshpande and Montanari and , who give lower bounds of @math and @math respectively. We improve on their results by making a perturbation to the SDP solution proposed in their work, then showing that this perturbation remains PSD as the objective value approaches @math . In an independent work, Hopkins, Kothari and Potechin [HKP15] have obtained a similar lower bound for the degree- @math SOS relaxation.