Document Open Access Logo

Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere

Authors Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.31.pdf
  • Filesize: 0.65 MB
  • 20 pages

Document Identifiers

Author Details

Vijay Bhattiprolu
Venkatesan Guruswami
Euiwoong Lee

Cite As Get BibTex

Vijay Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee. Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.31

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.

Subject Classification

Keywords
  • Sum-of-Squares
  • Optimization over Sphere
  • Random Polynomials

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Boaz Barak, Fernando G. S. L. Brandao, Aram W. Harrow, Jonathan Kelner, David Steurer, and Yuan Zhou. Hypercontractivity, sum-of-squares proofs, and their applications. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 307-326. ACM, 2012. Google Scholar
  2. Boaz Barak, Jonathan A. Kelner, and David Steurer. Rounding sum-of-squares relaxations. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 31-40. ACM, 2014. Google Scholar
  3. Boaz Barak, Jonathan A. Kelner, and David Steurer. Dictionary learning and tensor decomposition via the sum-of-squares method. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 143-151. ACM, 2015. Google Scholar
  4. Boaz Barak and David Steurer. Sum-of-squares proofs and the quest toward optimal algorithms. arXiv preprint arXiv:1404.5236, 2014. Google Scholar
  5. Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, and Madhur Tulsiani. Weak decoupling, polynomial folds, and approximate optimization over the sphere. Electronic Colloquium on Computational Complexity (ECCC), 23:185, 2016. URL: https://eccc.weizmann.ac.il/report/2016/185/.
  6. Vijay Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee. Certifying random polynomials over the unit sphere via sum of squares hierarchy. arXiv preprint arXiv:1605.00903, 2016. Google Scholar
  7. Fernando G. S. L. Brandao and Aram W. Harrow. Quantum de finetti theorems under local measurements with applications. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 861-870. ACM, 2013. Google Scholar
  8. S. Charles Brubaker and Santosh S. Vempala. Random tensors and planted cliques. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 406-419. Springer, 2009. Google Scholar
  9. Alan Frieze and Ravi Kannan. A new approach to the planted clique problem. In LIPIcs-Leibniz International Proceedings in Informatics, volume 2. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2008. Google Scholar
  10. Rong Ge and Tengyu Ma. Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, page 829, 2015. Google Scholar
  11. Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer. Personal communication, 2017. Google Scholar
  12. Samuel B. Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via sum-of-square proofs. In Proceedings of The 28th Conference on Learning Theory, pages 956-1006, 2015. Google Scholar
  13. Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP. In Proceedings of the 49th ACM Symposium on Theory of Computing, 2017. To appear. Google Scholar
  14. Monique Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of algebraic geometry, pages 157-270. Springer, 2009. Google Scholar
  15. Andrea Montanari and Emile Richard. A statistical model for tensor PCA. In Advances in Neural Information Processing Systems, pages 2897-2905, 2014. Google Scholar
  16. Prasad Raghavendra, Satish Rao, and Tselil Schramm. Strongly refuting random CSPs below the spectral threshold. In Proceedings of the 49th ACM Symposium on Theory of Computing, 2017. To appear. Google Scholar
  17. Barry Simon. The classical moment problem as a self-adjoint finite difference operator. Advances in Mathematics, 137(1):82-203, 1998. Google Scholar
  18. R. Tomioka and T. Suzuki. Spectral norm of random tensors. ArXiv e-prints, July 2014. URL: http://arxiv.org/abs/1407.1870.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact