License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.31
URN: urn:nbn:de:0030-drops-75808
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7580/
Bhattiprolu, Vijay ;
Guruswami, Venkatesan ;
Lee, Euiwoong
Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere
Abstract
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.
BibTeX - Entry
@InProceedings{bhattiprolu_et_al:LIPIcs:2017:7580,
author = {Vijay Bhattiprolu and Venkatesan Guruswami and Euiwoong Lee},
title = {{Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {31:1--31:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-044-6},
ISSN = {1868-8969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7580},
URN = {urn:nbn:de:0030-drops-75808},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.31},
annote = {Keywords: Sum-of-Squares, Optimization over Sphere, Random Polynomials}
}
Keywords: |
|
Sum-of-Squares, Optimization over Sphere, Random Polynomials |
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) |
Issue Date: |
|
2017 |
Date of publication: |
|
11.08.2017 |