文章基本信息

标题：Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere
本地全文：下载
作者：Vijay Bhattiprolu ; Venkatesan Guruswami ; Euiwoong Lee 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：81
页码：31:1-31:20
DOI：10.4230/LIPIcs.APPROX-RANDOM.2017.31
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：For an n-variate order-d tensor A, define A_{max} := sup_{||x||_2 = 1} , 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. +1/-1 entries, A_{max} <= sqrt(n.d.log(d)) w.h.p. We study the problem of efficiently certifying upper bounds on A_{max} via the natural relaxation from the Sum of Squares (SoS) hierarchy. Our results include: * When A is a random order-q tensor, we prove that q levels of SoS certifies an upper bound B on A_{max} that satisfies B <= A_{max} * (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 q is large. * We show the above bound is the best possible up to lower order terms, namely the optimum of the level-q SoS relaxation is at least A_{max} * (n/q^(1+o(1)))^(q/4-1/2). * When A is a random order-d tensor, we prove that q levels of SoS certifies an upper bound B on A_{max} that satisfies B <= A_{max} * (n*polylog/q)^(d/4 - 1/2) w.h.p. For growing q, 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 tightly characterized constant levels of SoS.
关键词：Sum-of-Squares; Optimization over Sphere; Random Polynomials