Subexponential hardness of certifying non-negative PCA

Let $\bW \in \mathbb{R}^{n \times n}_{\mathrm{sym}}$ be drawn from the Gaussian orthogonal ensemble, and let $\lambda^+(\bW)$ denote the non-negative principal component analysis objective. A certification algorithm is an algorithm that outputs $c(\bW) \geq \lambda^+(\bW)$ for every input $\bW$ and, with high probability for $\bW \sim \operatorname{GOE}(n)$, outputs $c(\bW) \leq K$. Certification hardness conjecture. For any fixed $\varepsilon > 0$ and $\eta > 0$, there is no algorithm of runtime $\exp(O(n^{1-\eta}))$ that certifies the bound $\lambda^+(\bW) \leq 2 - \varepsilon$. The conjecture formalizes the claim that the simple certificate $\lambda_{\max}(\bW) \leq 2+o(1)$ cannot be improved in subexponential time, except by a fully exponential-time brute-force search.