2026-07-24T00:01:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7580 2024-03-06T10:40:40Z ddc:004 open_access

Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere Bhattiprolu, Vijay Guruswami, Venkatesan Lee, Euiwoong Sum-of-Squares Optimization over Sphere Random Polynomials For an n-variate order-d tensor A, define A_{max} := sup_{||x||_2 = 1} <A,x^(otimes d)>, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vijay Bhattiprolu and Venkatesan Guruswami and Euiwoong Lee 2017 Is Part Of LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2017.31 urn:nbn:de:0030-drops-75808 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.31 eng https://creativecommons.org/licenses/by/3.0/legalcode