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.ITCS.2020.78
URN: urn:nbn:de:0030-drops-117633
URL: https://drops.dagstuhl.de/opus/volltexte/2020/11763/
Bandeira, Afonso S. ;
Kunisky, Dmitriy ;
Wein, Alexander S.
Computational Hardness of Certifying Bounds on Constrained PCA Problems
Abstract
Given a random n × n symmetric matrix 𝑾 drawn from the Gaussian orthogonal ensemble (GOE), we consider the problem of certifying an upper bound on the maximum value of the quadratic form 𝒙^⊤ 𝑾 𝒙 over all vectors 𝒙 in a constraint set 𝒮 ⊂ ℝⁿ. For a certain class of normalized constraint sets we show that, conditional on a certain complexity-theoretic conjecture, no polynomial-time algorithm can certify a better upper bound than the largest eigenvalue of 𝑾. A notable special case included in our results is the hypercube 𝒮 = {±1/√n}ⁿ, which corresponds to the problem of certifying bounds on the Hamiltonian of the Sherrington-Kirkpatrick spin glass model from statistical physics. Our results suggest a striking gap between optimization and certification for this problem.
Our proof proceeds in two steps. First, we give a reduction from the detection problem in the negatively-spiked Wishart model to the above certification problem. We then give evidence that this Wishart detection problem is computationally hard below the classical spectral threshold, by showing that no low-degree polynomial can (in expectation) distinguish the spiked and unspiked models. This method for predicting computational thresholds was proposed in a sequence of recent works on the sum-of-squares hierarchy, and is conjectured to be correct for a large class of problems. Our proof can be seen as constructing a distribution over symmetric matrices that appears computationally indistinguishable from the GOE, yet is supported on matrices whose maximum quadratic form over 𝒙 ∈ 𝒮 is much larger than that of a GOE matrix.
BibTeX - Entry
@InProceedings{bandeira_et_al:LIPIcs:2020:11763,
author = {Afonso S. Bandeira and Dmitriy Kunisky and Alexander S. Wein},
title = {{Computational Hardness of Certifying Bounds on Constrained PCA Problems}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {78:1--78:29},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-134-4},
ISSN = {1868-8969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11763},
URN = {urn:nbn:de:0030-drops-117633},
doi = {10.4230/LIPIcs.ITCS.2020.78},
annote = {Keywords: Certification, Sherrington-Kirkpatrick model, spiked Wishart model, low-degree likelihood ratio}
}
|
Keywords: |
|
Certification, Sherrington-Kirkpatrick model, spiked Wishart model, low-degree likelihood ratio |
|
Collection: |
|
11th Innovations in Theoretical Computer Science Conference (ITCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
06.01.2020 |
