文章基本信息

标题：Computational Hardness of Certifying Bounds on Constrained PCA Problems
本地全文：下载
作者：Afonso S. Bandeira ; Dmitriy Kunisky ; Alexander S. Wein 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：151
页码：1-29
DOI：10.4230/LIPIcs.ITCS.2020.78
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 ?^âS¤ ? ? over all vectors ? in a constraint set ? âS, â"â¿. 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/â^Sn}â¿, 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.
关键词：Certification; Sherrington-Kirkpatrick model; spiked Wishart model; low-degree likelihood ratio