Given a random $n$-variate degree-$d$ homogeneous polynomial $f$, we study the following problem: \[ \max_{\| x \| = 1} f(x). \] Besides being a fundamental problem in its own right, this random model has received attention recently due to its connection to tensor PCA. We study how the degree-$q$ Sum of Squares (SoS) hierarchy performs on this problem. Our results include: #R##N#- When $f$ is a degree-$q$ polynomial with independent random coefficients, we prove that there is a constant $c$ such that with high probability, degree-$q$ SoS satisfies \[ #R##N#(\frac{n}{q^{\,\,c+o(1)}})^{q/4} \leq \text{ SoS-Value } \leq (\frac{n}{q^{\,\,c-o(1)}})^{q/4}. \] Our upper bound improves a result of Montanari and Richard~\cite{MR14} when $q$ is large. (It is known that $\max_{\|x\|=1} f(x) \lesssim \sqrt{n\,q\,\log q}$ w.h.p.) #R##N#- When $f$ is a random degree-$3$ or $4$ polynomial, we prove that with high probability, the degree-$q$ SoS-Value is at most $\tilde{O}(\frac{n^{3/4}}{q^{1/4}})$, $\tilde{O}(\frac{n}{\sqrt{q}})$ respectively. This improves on a result of Hopkins, Shi, and Steurer~\cite{HSS15} when $q$ is growing. #R##N#- Lower bounds on the degree-$q$ SoS-Value of the $2$-norm of the $q$-parity-tensor of a random graph. #R##N#In providing these results, we develop tools that we believe to be useful in analysing the SoS hierarchy on other optimization problems over the sphere.
['Vijay V. S. P. Bhattiprolu', 'Venkatesan Guruswami', 'Euiwoong Lee']
Certifying Random Polynomials over the Unit Sphere via Sum of Squares Hierarchy