Algorithm

#  Computational-Statistical Gaps for Improper Learning in Sparse Linear
Regression

Rares-Darius Buhai ETH Zürich. Jingqiu Ding11footnotemark: 1 Stefan
Tiegel11footnotemark: 1

###### Abstract

We study computational-statistical gaps for improper learning in sparse linear
regression. More specifically, given $n$ samples from a $k$-sparse linear
model in dimension $d$, we ask what is the minimum sample complexity to
efficiently (in time polynomial in $d$, $k$, and $n$) find a potentially dense
estimate for the regression vector that achieves non-trivial prediction error
on the $n$ samples. Information-theoretically this can be achieved using
$\Theta(k\log(d/k))$ samples. Yet, despite its prominence in the literature,
there is no polynomial-time algorithm known to achieve the same guarantees
using less than $\Theta(d)$ samples without additional restrictions on the
model. Similarly, existing hardness results are either restricted to the
proper setting, in which the estimate must be sparse as well, or only apply to
specific algorithms.

We give evidence that efficient algorithms for this task require at least
(roughly) $\Omega(k^{2})$ samples. In particular, we show that an improper
learning algorithm for sparse linear regression can be used to solve sparse
PCA problems (with a negative spike) in their Wishart form, in regimes in
which efficient algorithms are widely believed to require at least
$\Omega(k^{2})$ samples. We complement our reduction with low-degree and
statistical query lower bounds for the sparse PCA problems from which we
reduce.

Our hardness results apply to the (correlated) random design setting in which
the covariates are drawn i.i.d. from a mean-zero Gaussian distribution with
unknown covariance.

###### Contents

  1. 1 Introduction
    1. 1.1 Relation to known algorithms and other hardness results
  2. 2 Technical overview
  3. 3 Sparse linear regression reduction
  4. 4 Distinguishing paired distributions reduction
  5. Acknowledgements
  6. A Concentration bounds
  7. B Low-degree lower bound for negative-spike sparse Wishart model
    1. B.1 Low-degree framework
    2. B.2 LD lower bound for negative-spike sparse Wishart model
  8. C Statistical query lower bound for negative-spike sparse Wishart model
    1. C.1 SQ framework
    2. C.2 SQ lower bound for sparse negative-spike Wishart model

##  1 Introduction

We study computational-statistical gaps in sparse linear regression models
with (correlated) random designs. In particular, on receiving $n$ samples
$(\bm{a}_{i},\bm{y}_{i})$ for
$\bm{y}_{i}=\langle\bm{a}_{i},x^{*}\rangle+\bm{w}_{i}$ where $\bm{w}_{i}$ is
Gaussian noise and $x^{*}$ is an unknown sparse vector, we wish to find an
estimate $\hat{\bm{x}}$ for $x^{*}$ that produces predictions
$\langle\bm{a}_{i},\hat{\bm{x}}\rangle$ close to
$\langle\bm{a}_{i},x^{*}\rangle$ for the given samples. We consider the
setting in which the covariates $\bm{a}_{i}$ are drawn i.i.d. from a
(correlated) Gaussian distribution (cf. Model 1.1) – this is referred to as
the _random design_ setting.

Despite its prominence, the computational complexity of sparse linear
regression with respect to general estimators remains poorly understood.
Without further restrictions on the model, no efficient algorithms are known
that use $o(d)$ samples. Similarly, there is a dearth of hardness results:
Known lower bounds apply only against specific algorithms or rule out so-
called _proper_ learners, in which the output of the estimator needs to be
sparse as well. In particular, to the best of our knowledge, there is no
evidence ruling out efficient algorithms producing potentially dense estimates
that use only the information-theoretically minimal number of samples. We call
such estimators _improper_. The distinction between proper and improper
learners can be substantial: There are learning tasks that are
$\mathrm{NP}$-hard in the proper setting but polynomial-time solvable using an
improper learner [Val84, PV88].111The learning tasks are 3-Term DNFs that are
known to be efficiently learnable via 3-CNFs yet are $\mathrm{NP}$-hard to
learn properly. Thus, hardness against proper learners only gives limited
evidence for the hardness of a learning task.

Similarly, many of the known lower bounds only apply to the more stringent
setting in which the covariates are allowed to be worst-case (worst-case
designs) [ZWJ14, ZWJ15]. A priori the random design setting may seem much more
benign than the worst-case setting. Computational hardness results for worst-
case designs, albeit restricted to proper learners, have been known for nearly
a decade [ZWJ14], yet obtaining any computational lower bounds for random
Gaussian designs is a major open question explored in [KKMR22b, KKMR22a]. In
this work, we show hardness results for improper learners that hold even in
the restrictive random design setting.

More specifically, we consider the following model:

######  Model 1.1 (Sparse linear regression with Gaussian design).

Let $d,k,n\in\mathbb N$ and $\sigma\in\mathbb R_{\geqslant 0}$ be known. Let
$\Sigma$ be an unknown positive semi-definite matrix and $x^{*}\in\mathbb
R^{d}$ be some unknown $k$-sparse vector, i.e., that has at most $k$ non-zero
entries. We draw $n$ i.i.d. samples
$(\bm{a}_{1},\bm{y}_{1}),\ldots,(\bm{a}_{n},\bm{y}_{n})\in\mathbb
R^{d}\times\mathbb R$ from the following linear model: Independently draw
$\bm{a}_{i}\sim N(0,\Sigma)$ and $\bm{w}_{i}\sim N(0,\sigma^{2})$. Output the
$(\bm{a}_{i},\bm{y}_{i})$, where
$\bm{y}_{i}=\langle\bm{a}_{i},x^{*}\rangle+\bm{w}_{i}$.

Let $\bm{A}\in\mathbb R^{n\times d}$ be the matrix that has the $\bm{a}_{i}$
as rows and let $\bm{y}\in\mathbb R^{n}$ be the vector that has entries
$\bm{y}_{i}$. We say an algorithm achieves _prediction error_ $\rho$ if it
outputs a (potentially dense) vector $\hat{\bm{x}}\in\mathbb R^{d}$ such that
$\tfrac{1}{n}\lVert\bm{A}x^{*}-\bm{A}\hat{\bm{x}}\rVert^{2}\leqslant\rho$.

We refer to the matrix $\bm{A}$ as the design matrix. In what follows, we will
focus on algorithms achieving prediction error $\rho=0.01$.

Information-theoretically, this problem is well-understood:
$\Theta(k\log(d/k))$ samples are both necessary and sufficient to achieve
prediction error $0.01$ with, say, probability 0.99 [RWY11]. Unfortunately,
the algorithm achieving the upper bound – known as the best-subset-selection
estimator – relies on an exhaustive search over $k$-sparse vectors and
requires time $d^{\Omega(k)}$. This exponential-in-$k$ running time is
prohibitively large as soon as $k$ is only slightly larger than constant.
Instead, we would like algorithms running in time
$\operatorname{poly}(d,n,k)$. We call such algorithms efficient. All efficient
algorithms for this task use $\Omega(d)$ samples, yet there is no hardness
result giving evidence that even $\omega(k\log(d/k))$ samples are necessary.
This leads us to the main question of this work:

######  Question 1.2.

What is the best-possible sample complexity for computationally efficient
algorithms in Model 1.1 achieving prediction error 0.01?

We make progress on this question by presenting evidence that efficient
algorithms need $\Omega(k^{2})$ samples, even in the improper setting. This
leads to an intriguing state of affairs: Many problems involving sparsity
exhibit a $k$-vs-$k^{2}$ statistical-computational gap. That is, information-
theoretically the problem can be solved with (roughly) $k$ samples, yet
computationally efficient algorithms likely require $k^{2}$ samples (we refer
to [BB20] and the references therein for a more detailed treatment). Our
results provide evidence that this might also be the case for sparse linear
regression.222However, we remark that for sparse linear regression there is no
known algorithm using $O(k^{2})$ or even $o(d)$ samples. Our hardness results
come in the form of reductions from problems that are believed to be
computationally intractable.

#### Known lower bounds and our approach

Known lower bounds have focused on showing impossibility results for the
harder task of (semi-)proper learning in which the algorithm has to output a
$k^{\prime}$-sparse estimate for $k\leqslant k^{\prime}\leqslant k\cdot
d^{o(1)}$. Based on worst-case complexity assumptions, [ZWJ14, FKT15] show
that for worst-case design matrices polynomial-time algorithms require
$\omega(k\log d)$ samples. While this settles 1.2 for (semi-)proper learners,
this does not say anything about the improper and/or random design case. To
the best of our knowledge, the only known lower bounds for this more general
setting apply to (very) restricted families of algorithms [ZWJ15, KKMR22b,
KKMR22a]. While these include popular sparse regression algorithms such as
LASSO and variations thereof, this only provides weak evidence of hardness: It
remains unclear if an algorithm from a different family can circumvent the
results. In particular, in recent years algorithms based on spectral methods
and the sum-of-squares hierarchy have seen an immense success in the design of
computationally efficient algorithms for statistical estimation problems. Such
a general class of algorithms is not ruled out.

This calls for hardness evidence against more general classes of algorithms.
Unfortunately, and in contrast to the proper learning setting, there seem to
be inherent barriers to basing hardness of improper learning (in average-case
problems) on classical worst-case assumptions such as
$\mathrm{P}\neq\mathrm{NP}$ [ABX08]. By now, the two most prevalent techniques
for showing average-case hardness are the following: First, show unconditional
lower bounds in a restricted model of computation (that captures most known
algorithms for the problem), such as statistical query (SQ) [Kea98, FGR+17] or
low-degree algorithms [HS17, HKP+17, Hop18]. These algorithms capture most
known algorithms for statistical inference problems (with the notable
exception of Gaussian elimination and the LLL Algorithm [ZSWB22, DK22]). For
many average-case problems (such as graph recovery problems [BHK+19, HS17],
mean estimation and learning Gaussian Mixture Models [DKS17] and spiked matrix
models [HKP+17, DKWB22]), these frameworks have been successfully used to
trace out a computational phase transition for a broad class of computational
problems: the statistical error rate achieved by existing polynomial-time
algorithms can be matched by algorithms in the class, while obtaining better
error rate is impossible for these algorithms. The second approach is to show
a reduction from a problem believed to be computationally hard [BB20, BRST21,
GVV22]. We remark that the latter can also be interpreted in a positive way as
understanding the connections between different computational problems: If,
say, we find a better sparse linear regression algorithm, we also find a
better algorithm for another problem that we did not know before.

We follow the second approach. In particular, we show a reduction from a
slight variant of a widely studied PCA problem:

######  Model 1.3 (Sparse spiked Wishart model).

Let $d,k,n\in\mathbb N$ with $d\geqslant k$ and $\theta\in(0,1)$. We define
the $\mathrm{NegSPCA}_{\theta}$ problem as the following distinguishing
problem: We are given $n$ i.i.d. samples from either $\mathcal{P}$ or
$\mathcal{Q}$ defined as follows and want to decide whether they came from
$\mathcal{P}$ or $\mathcal{Q}$.

  * •

Planted distribution $\mathcal{P}$: Sample a unit vector $\bm{x}\in\mathbb
R^{d+1}$ with $\bm{x}_{1}=-\tfrac{1}{\sqrt{k+1}}$ and $\bm{x}_{\setminus 1}$
sampled uniformly from $k$-sparse
$\mathopen{}\mathclose{{}\left\\{\pm\tfrac{1}{\sqrt{k+1}},0}\right\\}^{d}$
vectors and fix it for the rest of the sampling procedure. Produce samples by
sampling from $N(0,\mathrm{Id}_{d+1}-\theta\cdot\bm{x}\bm{x}^{\top})$.

  * •

Null distribution $\mathcal{Q}$: $N(0,\mathrm{Id}_{d+1})$.

We remark that, except for the condition that the first coordinate of $\bm{x}$
under $\mathcal{P}$ is non-zero, this coincides with the classical problem of
sparse PCA in the Wishart model with a negative spike that has a sparse prior.
Several variants of this problem are known to be hard using (roughly) less
than $k^{2}$ samples: in the low-degree model, inside the sum-of-squares
framework, and under a reduction from a variant of the planted clique
assumption [HKP+17, DKWB21, BB20]. We make the following hardness assumption
about Model 1.3, which we formally verify in the low-degree and statistical
query model in Appendices B and C (our proof follows closely the proof of
[DKWB21]).

######  Assumption 1.4.

Let $d,n,k\in\mathbb N$ with $d\geqslant k$ and let $0<\delta\leqslant 0.1$ be
an arbitrary absolute constant. Suppose that $n=o(\min(d,k^{2-\delta}))$.
Then, for any $\theta\in(0,1)$, any algorithm that solves
$\mathrm{NegSPCA}_{\theta}$ in dimension $d$ using $n$ samples and has success
probability at least $1-o(1)$ requires running time $d^{k^{\Omega(1)}}$.

#### Results

We show that a polynomial-time algorithm for improper learning in sparse
linear regression that uses $n$ samples can be turned into a polynomial-time
algorithm for Model 1.3 using the same number of samples. In particular, our
main result is the following:

######  Theorem 1.5 (Main result, see reduction in Theorem 3.1).

Let $d,n,k\in\mathbb N$ with $d\geqslant k$ and let $0<\delta\leqslant 0.1$ be
an arbitrary absolute constant. Suppose that $n=o(\min(d,k^{2-\delta}))$. If
there is an improper learner for the Sparse Linear Regression Model with
Gaussian Design (cf. Model 1.1) that uses $n$ samples and runs in time
$d^{k^{o(1)}}$ and achieves prediction error better than 0.01 with probability
at least $1-o(1)$, then 1.4 is false.

Note that this result implies that efficient algorithms for improperly
learning sparse linear regression models likely need (roughly)
$\Omega(\min(k^{2},d))$ samples, whereas information-theoretically, only
$O(k\log(d/k))$ samples are necessary. Without additional assumptions on the
model (cf. Section 1.1) no efficient algorithm is known that uses $o(d)$
samples for this task. We remark that when we only want to rule out algorithms
that achieve prediction error 0.01 with probability at least
$1-\Omega(\tfrac{1}{d})$, we can reduce from a version of Model 1.3 in which
$\bm{x}$ is sampled uniformly from all $(k+1)$-sparse vectors in
$\mathopen{}\mathclose{{}\left\\{\pm\tfrac{1}{\sqrt{k+1}},0}\right\\}$
(without the first coordinate being known).333We remark that we cannot combine
this last reduction with the reductions in [BB20] to obtain a reduction from
(secret-leakage) planted clique. The reason is that the parameters in the
reduction from the latter to Model 1.3 are not sufficiently strong.
Specifically, [BB20] requires $\theta=o(1)$, while we need $\theta$ to be an
absolute constant close to $1$.

It turns out that LASSO can solve our hard instance with $O(k^{2}\log d)$
samples, so our lower bound is tight up to logarithmic factors. Therefore a
different construction would be needed to obtain even stronger lower bounds.

###  1.1 Relation to known algorithms and other hardness results

We outline here how our result compares to other algorithmic and hardness
results that have been obtained in prior works.

As stated before, known algorithms achieve prediction error 0.01 using $o(d)$
samples only with additional assumptions on the model. In particular, under
the assumption that the columns are normalized to have squared norm $n$, the
LASSO estimator is known to achieve prediction error 0.01 using $O(\lVert
x^{*}\rVert_{1}^{2}\log d)$ samples [Wai19, Theorem 7.20]. This gives a good
sample complexity if the $\ell_{1}$-norm of the secret is bounded. Second, if
the design matrix is known to satisfy the so-called _restricted eigenvalue
condition_ (with the same normalization of the columns), LASSO is known to
succeed with few samples. In particular, let $A$ be the design matrix.
Assuming that (roughly) for all $k$-sparse unit vectors $u$ it holds that
$\tfrac{1}{n}\lVert Au\rVert^{2}\geqslant\gamma$, LASSO achieves prediction
error 0.01 using $O(\tfrac{k\log d}{\gamma})$ samples. $\gamma$ is referred to
as the RE constant.

Further, [KKMR22b] showed that in the Gaussian design setting that we consider
in this paper, the LASSO estimator combined with a preconditioning step
achieves nearly optimal sample complexity whenever the dependency structure of
the covariates satisfies a specific regularity condition.

For lower bounds, the results closest to us are the following: [ZWJ14] showed
that, assuming $\mathrm{NP}\not\subseteq\mathrm{P}_{/\operatorname{poly}}$,
the dependence of the RE constant achieved by the LASSO is tight for all
polynomial-time proper learners. In particular, they construct instance in
which the RE constant can be exponentially small and obtain a corresponding
lower bound on the sample complexity of proper learners achieving prediction
error $0.01$. Under other complexity theoretic assumptions [FKT15] showed that
there is no polynomial-time estimator for this task, even if the output vector
is allowed to be $O(k\cdot 2^{\log^{1-\delta}(d)})$-sparse for any constant
$\delta>0$. Note that this notion is still significantly more restrictive than
ours, as it does note rule out outputting even a $d^{0.001}$-sparse vector.
The design matrices in both the above works are worst-case.

Concurrent work to ours [GVV24] shows hardness for proper learning under
random designs based on worst-case problems in lattices. In particular, they
give evidence that in this setting, improving the prediction error bound of
LASSO, when expressing the error as a function of the RE constant of the
design matrix, would give stronger lattice algorithms. As the information-
theoretic prediction error has no dependence on the RE constant and the RE
constant can be exponentially small, this gives evidence of a possibly large
computational-statistical separation.

[ZWJ15] showed that a restricted class of convex M-estimators (including the
LASSO estimator) cannot achieve optimal prediction error (under worst-case
designs). While the algorithms they rule out are improper, their result does
not make any claims beyond the specific algorithms they consider. To the best
of our knowledge, the only hardness results for (a restricted class of)
improper learners in the random design setting are [KKMR22b, KKMR22a]. They
ruled out that the LASSO can achieve optimal sample complexity even when
combined with a pre-processing step (called pre-conditioning).

##  2 Technical overview

#### Notation

We use asymptotic notations $O(\cdot),o(\cdot),\Omega(\cdot),\omega(\cdot)$
for $n\to\infty$. We use $\tilde{O}(\cdot)$ to hide
$\frac{1}{\operatorname{polylog}(n)}$ factors. We use $\|\cdot\|$ for the
Euclidean norm of vectors. We use boldface for random variables. For a vector
$x\in\mathbb R^{d}$, we use $x_{\setminus 1}\in\mathbb R^{d-1}$ for the vector
obtained by removing the first coordinate. For a matrix $A\in\mathbb
R^{n\times d}$, we use $A_{j}$ for the $j$-th column and $A_{j:k}$ for the
submatrix containing columns $j$ through $k$. For two vectors $x\in\mathbb
R^{d_{1}}$ and $y\in\mathbb R^{d_{2}}$, we denote by
$\operatorname{concat}(x,y)$ the vector $(x,y)\in\mathbb R^{d_{1}+d_{2}}$.

In this section, we present our reduction from PCA with a negative spike (cf.
1.4) to improperly learning sparse linear regression models. Our reduction is
similar to the one of [BPP18]. However, a crucial difference is that we start
from sparse PCA with a _negative_ spike. Indeed, since the design matrices in
the resulting SLR instance in [BPP18] satisfy the restricted eigenvalue
property with appropriate parameters, they can be solved with error 0.01 using
only $O(k\log d)\ll k^{2}$ samples. Further, the reduction of [BPP18] only
works assuming access to a _proper_ sparse linear regression algorithm, i.e.,
one that outputs a sparse solution. By giving a slightly different reduction,
we show that it is enough to assume access to an improper learner. As a warm-
up, we will show that improperly learning sparse linear regression models is
hard when the variance of the noise is unknown (but known to be in [0,1]).
Second, we show that even when the variance is known and equal to 1 (i.e.
Model 1.1) the problem remains hard. For the remainder of the paper, unless
explicitly specified, when referring to "solving sparse linear regression" or
similar expressions, we always mean improper learners.

#### Hardness of certifying RIP and a first lower bound

We first recall that achieving prediction error $0.01$ is possible in
polynomial time using $O(k\log d)$ samples under additional assumptions on the
design matrix. In particular, if the design matrix satisfies the restricted
eigenvalue condition (with a constant), the LASSO algorithm achieves this
guarantee. In order to construct a lower bound instance, it is thus necessary
that this property does not hold (or only with weaker parameters than
necessary for known algorithms). We focus here on the related _restricted
isometry property_ (RIP). In particular, a matrix $X\in\mathbb R^{n\times d}$
is said to satisfy $(k,\delta)$-RIP if for all $k$-sparse unit vectors $v$ it
holds that $\lVert Xv\rVert^{2}\in[1-\delta,1+\delta]$.

Suppose that we could _certify_ that a matrix satisfies RIP. This would give
us a way to convince ourselves that our learning algorithm succeeded in some
cases: Check if the design matrix satisfies RIP, and if yes run LASSO. Else,
we do not guarantee anything. It is thus natural to wonder whether there is a
formal connection between RIP certification and sparse linear regression.
Unfortunately, it is believed that certifying RIP is computationally difficult
[DKWB21].444Interestingly, the results in [DKWB21] are tight, in the sense
that there is a certification algorithm matching their lower bound [KZ14]. On
the other hand, our work shows that we can exploit this connection to show
_hardness results_ in the following way: Lower bounds for RIP certification
are proved by showing that an associated distinguishing problem between two
distributions is hard. One hypothesis corresponds to matrices with good RIP,
the other does not. If we can certify RIP, we can distinguish the two. Our
main observation is that sparse linear regression solvers can be used to solve
this distinguishing problem.

In particular, consider the following (degenerate) instance of the negative
sparse PCA problem. This instance will already give us a lower bound for
sparse regression if we ask that the algorithm works in the case when the
variance of the noise is unknown between $0$ and $1$. Given samples
$\bm{z}_{1},\ldots,\bm{z}_{n}$ from either $\mathcal{Q}=N(0,I_{d})$ or
$\mathcal{P}=N(0,I_{d}-\bm{x}\bm{x}^{\top})$, where $\bm{x}$ is a uniformly
random $(k+1)$-sparse unit vector with $\bm{x}_{1}=-\tfrac{1}{\sqrt{k+1}}$,
decide which is the case. Note that this instance being hard implies that RIP
certification is hard: Consider the matrix $\bm{Z}\in\mathbb R^{n\times d}$
with rows $\bm{z}_{i}$. Under $\mathcal{Q}$ this has good RIP and under
$\mathcal{P}$ it does not. Our key observation is that the absence of RIP
implies a dependence between the columns of $\bm{Z}$ that is not present under
$\mathcal{Q}$. Luckily for us, in our setting this dependence is linear and
only concerns $k$ columns. We can thus hope to detect it with our sparse
regression oracle.

Indeed, consider the matrix $\bm{Z}$ under $\mathcal{P}$: It holds that
$\bm{Z}_{1}\bm{x}_{1}+\bm{Z}_{\setminus 1}\bm{x}_{\setminus 1}=\bm{Z}\bm{x}=0$
and hence $\bm{Z}_{1}=\bm{Z}_{\setminus
1}(-\tfrac{1}{\bm{x}_{1}}\bm{x}_{\setminus 1})$. Under $\mathcal{Q}$ on the
other hand the columns are independent and $\bm{Z}_{1}=\bm{Z}_{\setminus
1}\cdot 0+\bm{w}$, where $\bm{w}\sim N(0,\mathrm{Id}_{n})$. In either case,
let $\bm{A}=\bm{Z}_{\setminus 1}$ and $\bm{y}=\bm{Z}_{1}$. We have shown that
in both cases $(\bm{A},\bm{y})$ forms a valid input for our regression
algorithm since $\bm{y}=\bm{A}\bm{x^{*}}+\bm{w}$, where $\bm{x}^{*}$ is $0$ or
$-\tfrac{1}{\bm{x}_{1}}\bm{x}_{\setminus 1}$ under $\mathcal{Q}$ and
$\mathcal{P}$ respectively and $\bm{w}$ is independent of $\bm{A}$ and either
$N(0,\mathrm{Id}_{n})$ or $0$.555Note that the $0$ vector is also $k$-sparse.
Our regression oracle allows us to estimate $\bm{A}\bm{x}^{*}$. In particular,
under $\mathcal{Q}$, $\bm{A}\bm{x^{*}}=\bm{Z}_{\setminus 1}\bm{x}^{*}=0$ and
hence if $\bm{\hat{\bm{x}}}$ is our estimator then $\bm{A}\bm{\hat{\bm{x}}}$
should have small norm. On the other hand, under $\mathcal{P}$,
$\bm{A}\bm{x^{*}}=\bm{Z}_{\setminus 1}\bm{x}^{*}=\bm{Z}_{1}\sim
N(0,(1-\tfrac{1}{k+1})\cdot\mathrm{Id}_{n})$ and we expect our estimate to
have large norm. Indeed, suppose our regression oracle outputs $\hat{\bm{x}}$
achieving prediction error 0.01 with at least constant probability. Then,
under $\mathcal{Q}$,
$\tfrac{1}{\sqrt{n}}\lVert\bm{A}\hat{\bm{x}}\rVert=\tfrac{1}{\sqrt{n}}\lVert\bm{A}\hat{\bm{x}}-\bm{A}\bm{x^{*}}\rVert\leqslant
0.1$. However, under $\mathcal{P}$ it holds that

$\tfrac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{A}\hat{\bm{x}}}\right\rVert\geqslant\mathopen{}\mathclose{{}\left\lvert\tfrac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{A}\hat{\bm{x}}-\bm{A}\bm{x^{*}}}\right\rVert-\tfrac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{A}\bm{x^{*}}}\right\rVert}\right\rvert\,.$

By standard concentration bounds it follows that
$\tfrac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{A}\bm{x^{*}}}\right\rVert=\tfrac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{Z}_{1}}\right\rVert$
is at least, say, $0.6$ with high probability and thus
$\tfrac{1}{\sqrt{n}}\lVert\bm{A}_{\setminus 1}\hat{\bm{x}}\rVert\geqslant
0.5$. It follows that thresholding $\tfrac{1}{\sqrt{n}}\lVert\bm{A}_{\setminus
1}\hat{\bm{x}}\rVert$ faithfully distinguishes $\mathcal{Q}$ and $\mathcal{P}$
with at least constant probability.

Note that if we assume that our sparse linear regression algorithm has success
probability at least $1-O(\tfrac{1}{d})$, we do not need to assume that the
first coordinate of the sparse PCA prior in Model 1.3 is known to be
$-\tfrac{1}{\sqrt{k+1}}$. Indeed, instead of the above reduction, we can set
$\bm{y}=\bm{Z}_{i}$ and $\bm{A}=\bm{Z}_{\setminus i}$ for all $i\in[d]$ and
run our regression solver on $(\bm{A},\bm{y})$. Under $\mathcal{Q}$, with
probability at least, say, 0.99, it holds that in all of these runs we have
that $\tfrac{1}{\sqrt{n}}\lVert\bm{A}\hat{\bm{x}}\rVert\leqslant 0.01$.
Similarly, under $\mathcal{P}$, with probability at least 0.99, there exists
at least one $i$ such that
$\tfrac{1}{\sqrt{n}}\lVert\bm{A}\hat{\bm{x}}\rVert\geqslant 0.5$. Thus, we can
distinguish $\mathcal{Q}$ and $\mathcal{P}$ with at least constant
probability, based on whether
$\tfrac{1}{\sqrt{n}}\lVert\bm{A}\hat{\bm{x}}\rVert$ is large in at least one
iteration.

Note that in both cases the $\ell_{1}$-norm of the secret is at most $O(k)$
and thus LASSO would achieve prediction error $0.01$ using $O(k^{2}\log d)$
samples, under the slow-rate analysis.

#### Extension to non-degenerate negative sparse PCA

So far our reduction used a degenerate planted hypothesis
$\mathcal{P}=N(0,I_{d}-\bm{x}\bm{x}^{\top})$. In what follows, we argue that
the same reduction can also produce valid instances from non-degenerate
hypotheses. The sparse linear regression instances produced will now have
unknown variance of the noise between $0.5$ and $1$.

In particular, let $\theta=\tfrac{k+1}{k+2}\approx 1-\tfrac{1}{k}$. We start
with the negative sparse PCA problem in which
$\mathcal{Q}=N(0,\mathrm{Id}_{d})$ and
$\mathcal{P}=N(0,\mathrm{Id}_{d}-\theta\cdot\bm{x}\bm{x}^{\top})$, where
$\bm{x}$ is again a uniformly random $(k+1)$-sparse unit vector with
$\bm{x}_{1}=-\tfrac{1}{\sqrt{k+1}}$. The null case does not change (and the
variance of the noise in this case is 1), so it suffices to analyze
$\mathcal{P}$. Then, for the planted case, we use the following fact proved in
[BPP18]:666Formally, [BPP18] only shows this fact for sparse PCA instances
with _positive_ spikes. The proof they give also works for the setting with
negative spikes.

######  Fact 2.1 (Appendix B.2 in [BPP18]).

Let $\bm{y},\bm{A}$ be as above (under $\mathcal{P}$) and
$\gamma=\tfrac{\theta}{1-\theta\cdot\tfrac{k}{k+1}}=\tfrac{k+1}{2}$. Then
$\bm{y}=\bm{A}{\bm{x^{*}}}+\bm{w}$, where $\bm{A}{\bm{x^{*}}}$ and $\bm{w}$
are independent with $\bm{w}\sim N(0,\sigma^{2}\mathrm{Id}_{n})$, and

$\displaystyle{\bm{x^{*}}}=\frac{\gamma}{\sqrt{k+1}}\cdot\bm{x}_{\setminus
1}=\frac{\sqrt{k+1}}{2}\cdot\bm{x}_{\setminus 1}\,,$
$\displaystyle\sigma^{2}=1-\frac{\gamma}{{k+1}}=\frac{1}{2}\,.$

This establishes that the variance of the noise is always either 0.5 or 1. It
follows using the same techniques that under $\mathcal{P}$ it still holds that
$\tfrac{1}{\sqrt{n}}\lVert\bm{A}_{\setminus 1}\hat{\bm{x}}\rVert\geqslant
0.5$.

#### Known variance of the noise

Our goal is to reduce $\mathrm{NegSPCA}_{\theta}$ to sparse linear regression
instances that have known variance of the noise.

In the discussions so far our strategy has been to set $\bm{y}=\bm{Z}_{1}$.
Then under $\mathcal{Q}$ we have $\bm{y}\sim N(0,\mathrm{Id}_{n})$, but under
$\mathcal{P}$ we have $\bm{y}=\bm{A}{\bm{x^{*}}}+\bm{w}$ where $\bm{w}$ is
Gaussian with variance less than $1$. Indeed, if $\bm{w}$ had variance exactly
$1$, we could distinguish $\mathcal{Q}$ and $\mathcal{P}$ by thresholding the
norm of $\bm{y}$. Therefore, in this strategy the variance of the noise cannot
be the same under $\mathcal{Q}$ and $\mathcal{P}$. More generally, in
$\mathrm{NegSPCA}_{\theta}$ the null case and the planted case are asymmetric,
so it seems difficult to obtain some $\bm{y}$ for which the variance of the
noise is the same.

Instead, we introduce a new, symmetric, distinguishing problem
$\mathrm{PairNegSPCA}_{\theta}$ which requires distinguishing between a sample
from $\mathcal{P}\times\mathcal{Q}$ and a sample from
$\mathcal{Q}\times\mathcal{P}$, where $\mathcal{P}$ and $\mathcal{Q}$ are the
planted and null distributions in $\mathrm{NegSPCA}_{\theta}$:

######  Definition 2.2 (Paired spiked Wishart model).

Let $d,k,n\in\mathbb N$ with $d\geqslant k$ and $\theta\in(0,1)$. Let
$\mathcal{P}$ and $\mathcal{Q}$ be the planted and null distributions in a
$\mathrm{NegSPCA}_{\theta}$ problem, respectively. We define the
$\mathrm{PairNegSPCA}_{\theta}$ problem as the following distinguishing
problem: We are given $n$ i.i.d. samples from either
$\mathcal{P}\times\mathcal{Q}$ or $\mathcal{Q}\times\mathcal{P}$ defined as
follows and we want to decide whether they came from
$\mathcal{P}\times\mathcal{Q}$ or $\mathcal{Q}\times\mathcal{P}$.

  * •

$\mathcal{P}\times\mathcal{Q}$: Sample independently $z\sim\mathcal{P}$ and
$z^{\prime}\sim\mathcal{Q}$ and return $(z,z^{\prime})$.

  * •

$\mathcal{Q}\times\mathcal{P}$: Sample independently $z\sim\mathcal{Q}$ and
$z^{\prime}\sim\mathcal{P}$ and return $(z,z^{\prime})$.

Then we reduce $\mathrm{PairNegSPCA}_{\theta}$ to sparse linear regression by
setting $\bm{y}$ to be the sum of a column as in $\mathcal{P}$ and a column as
in $\mathcal{Q}$ – without knowing which is which. This ensures that the
variance of the noise is identical under $\mathcal{P}\times\mathcal{Q}$ and
$\mathcal{Q}\times\mathcal{P}$. In addition, we reduce
$\mathrm{NegSPCA}_{\theta}$ to $\mathrm{PairNegSPCA}_{\theta}$, so by
composition we obtain the desired reduction from $\mathrm{NegSPCA}_{\theta}$
to sparse linear regression with known variance of the noise.

##  3 Sparse linear regression reduction

Theorem 3.1 gives our main result.

######  Theorem 3.1.

Let $d,k,n\in\mathbb N$ with $d\geqslant k$ and $\theta\in(0,1)$. Assume there
exists an efficient algorithm that, given $n$ samples from the sparse linear
regression model with variance of the noise $\sigma^{2}=1$, achieves
prediction error
$\frac{1}{n}\mathopen{}\mathclose{{}\left\lVert\bm{A}\hat{\bm{x}}-\bm{A}\bm{x^{*}}}\right\rVert^{2}$
at most $0.01$ with probability $1-\delta$. Then there exists an efficient
algorithm that solves $\mathrm{NegSPCA}_{\theta}$ for $\theta=\frac{k+1}{k+2}$
with probability $1-\sqrt{2\delta}-\exp(-\Omega(n))$.

We first state a reduction from $\mathrm{NegSPCA}_{\theta}$ to
$\mathrm{PairNegSPCA}_{\theta}$. Informally, this says that if it is hard to
decide whether a sample comes from $\mathcal{P}$ or $\mathcal{Q}$, then it is
also hard, given a sample from $\mathcal{P}$ and one from $\mathcal{Q}$, to
decide which is which. The result follows from a more general reduction from
distinguishing distributions to distinguishing paired distributions that we
give in Lemma 4.1.

######  Lemma 3.2.

Let $d,k,n\in\mathbb N$ with $d\geqslant k$ and $\theta\in(0,1)$. Assume there
exists an efficient algorithm that solves $\mathrm{PairNegSPCA}_{\theta}$ with
probability at least $1-\delta$. Then there exists an efficient algorithm that
solves $\mathrm{NegSPCA}_{\theta}$ with probability at least
$1-\sqrt{2\delta}$.

The remaining step is to reduce $\mathrm{PairNegSPCA}_{\theta}$ to sparse
linear regression.

#### The reduction

Let $\theta=\tfrac{k+1}{k+2}$. Given $n$ samples
$(\bm{z}_{1},\bm{z}_{1}^{\prime}),\ldots,(\bm{z}_{n},\bm{z}_{n}^{\prime})$
from $\mathrm{PairNegSPCA}_{\theta}$, let $\bm{Z}\in\mathbb R^{n\times 2d}$ be
the matrix with rows
$\operatorname{concat}(\bm{z}_{1},\bm{z}_{1}^{\prime}),\ldots,\operatorname{concat}(\bm{z}_{n},\bm{z}_{n}^{\prime})$.
We do the following:

  1. 1.

Set $\bm{y}={\bm{Z}}_{1}+{\bm{Z}}_{d+1}$ and
$\bm{A}={\bm{Z}}_{\setminus\\{1,d+1\\}}$. That is, $\bm{A}$ is the
$n\times(2d-2)$ matrix that is obtained by removing columns $\bm{Z}_{1}$ and
$\bm{Z}_{d+1}$ from $\bm{Z}$.

  2. 2.

Invoke the sparse linear regression solver on $(\bm{A},\bm{y})$ to obtain an
estimator $\hat{\bm{x}}$.

  3. 3.

If
$\tfrac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{A}\hat{\bm{x}}-{\bm{Z}}_{1}}\right\rVert\leqslant\tfrac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{A}\hat{\bm{x}}-{\bm{Z}}_{d+1}}\right\rVert$
output $\mathcal{P}\times\mathcal{Q}$. Else output
$\mathcal{Q}\times\mathcal{P}$.

Consider the case $\mathcal{P}\times\mathcal{Q}$. As in Fact 2.1, let
$\gamma=\tfrac{\theta}{1-\theta\cdot k/(k+1)}=\frac{k+1}{2}$. Then, by the
same argument as in Fact 2.1, we can write
${\bm{Z}}_{1}=\bm{A}{\bm{x^{*}}}+\bm{w}^{\prime}$, where $\bm{A}{\bm{x^{*}}}$
and $\bm{w}^{\prime}$ are independent with $\bm{w}^{\prime}\sim
N(0,\sigma^{2}\mathrm{Id}_{n})$, and

$\displaystyle{\bm{x^{*}}}=\tfrac{\sqrt{k+1}}{2}\cdot\operatorname{concat}(\bm{x}_{\setminus
1},\bm{0}^{d-1})\,,$ $\displaystyle\sigma^{2}=\frac{1}{2}\,.$

Also, ${\bm{Z}}_{d+1}\sim N(0,\mathrm{Id}_{n})$ is independent of
$\bm{A}{\bm{x^{*}}}$ and $\bm{w}^{\prime}$, so we can write
$\bm{y}=\bm{A}{\bm{x^{*}}}+\bm{w}$, where $\bm{A}{\bm{x^{*}}}$ and $\bm{w}$
are independent with $\bm{w}\sim N(0,(\sigma^{2}+1)\mathrm{Id}_{n})$. Note
that by symmetry the variance of the noise is $\sigma^{2}+1$ also in the case
$\mathcal{Q}\times\mathcal{P}$.

We now prove Theorem 3.1.

###### Proof of Theorem 3.1.

Consider the case $\mathcal{P}\times\mathcal{Q}$. We have
${\bm{Z}}_{1}=\bm{A}{\bm{x^{*}}}+\bm{w}$, where $\bm{w}\sim
N(0,1.5\mathrm{Id}_{n})$. By the assumption on our sparse linear regression
estimator, by scaling up the guarantees such that the known variance of the
noise is $1.5$, we have with probability $1-\delta$ that
$\frac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{A}\hat{\bm{x}}-\bm{A}{\bm{x^{*}}}}\right\rVert\leqslant
0.01\cdot\sqrt{1.5}\leqslant 0.13$. By the triangle inequality, we get

$\displaystyle\frac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{A}\hat{\bm{x}}-{\bm{Z}}_{1}}\right\rVert$
$\displaystyle\leqslant\frac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{A}\hat{\bm{x}}-\bm{A}{\bm{x^{*}}}}\right\rVert+\frac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{w}^{\prime}}\right\rVert\,.$

Recall that $\bm{w}^{\prime}$ has covariance matrix $0.5\cdot\mathrm{Id}_{n}$.
Then we have by Fact A.1 with probability $1-\exp(-\Omega(n))$ that
$\tfrac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{w}^{\prime}}\right\rVert\leqslant\sqrt{0.5}+0.001\leqslant
0.71$. Then

$\frac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{A}\hat{\bm{x}}-{\bm{Z}}_{1}}\right\rVert\leqslant
0.71+0.13=0.84\,.$

On the other hand

$\displaystyle\frac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{A}\hat{\bm{x}}-{\bm{Z}}_{d+1}}\right\rVert$
$\displaystyle\geqslant\mathopen{}\mathclose{{}\left\lvert\frac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{A}\hat{\bm{x}}-\bm{A}{\bm{x^{*}}}}\right\rVert-\frac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{A}{\bm{x^{*}}}-{\bm{Z}}_{d+1}}\right\rVert}\right\rvert\,.$

The entries of ${\bm{Z}}_{d+1}$ are i.i.d. Gaussian with mean zero and
variance $1$, independent of the multivariate Gaussian $\bm{A}{\bm{x^{*}}}$.
Then we have by Fact A.1 with probability $1-\exp(-\Omega(n))$ that
$\frac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{A}{\bm{x^{*}}}-{\bm{Z}}_{d+1}}\right\rVert$
is at least $0.99$. Then

$\frac{1}{\sqrt{n}}\mathopen{}\mathclose{{}\left\lVert\bm{A}\hat{\bm{x}}-{\bm{Z}}_{d+1}}\right\rVert\geqslant
0.99-0.13=0.86\,,$

and overall we output $\mathcal{P}\times\mathcal{Q}$ with probability at least
$1-\delta-\exp(-\Omega(n))$.

Analogously, by symmetry, in the case $\mathcal{Q}\times\mathcal{P}$ we also
output $\mathcal{Q}\times\mathcal{P}$ with probability
$1-(\delta+\exp(-\Omega(n)))$. Then, by the reduction in Lemma 3.2, we also
solve $\mathrm{NegSPCA}_{\theta}$ with probability at least
$1-\sqrt{2(\delta+\exp(-\Omega(n)))}\geqslant
1-\sqrt{2\delta}-\exp(-\Omega(n))$.

∎

##  4 Distinguishing paired distributions reduction

In this section we show that an algorithm that distinguishes a sample from the
paired distributions $\mathcal{P}\times\mathcal{Q}$ and
$\mathcal{Q}\times\mathcal{P}$ also distinguishes a sample from the
distributions $\mathcal{P}$ and $\mathcal{Q}$, assuming that $\mathcal{Q}$ is
known.

######  Lemma 4.1.

Let $\mathcal{P}$ and $\mathcal{Q}$ be probability distributions over a domain
$\mathcal{D}$, and suppose that $\mathcal{Q}$ is known that it is possible to
sample independently from $\mathcal{Q}$ in time $T_{\mathrm{sample}}$. Suppose
that there exists a (randomized) algorithm $\mathcal{A}$ that takes as input a
pair $(x,x^{\prime})\in\mathcal{D}\times\mathcal{D}^{\prime}$ and runs in time
$T_{\mathrm{dist}}$ with the following guarantees:

  * •

$\operatorname*{\mathbb{P}}_{\bm{x}\sim\mathcal{P},\bm{x}^{\prime}\sim\mathcal{Q}}(\mathcal{A}(\bm{x},\bm{x}^{\prime})=0)\geqslant
1-\delta$, where $\bm{x}$ and $\bm{x}^{\prime}$ are sampled independently and
where the probability is also over any internal randomness of $\mathcal{A}$.

  * •

$\operatorname*{\mathbb{P}}_{\bm{x}\sim\mathcal{Q},\bm{x}^{\prime}\sim\mathcal{P}}(\mathcal{A}(\bm{x},\bm{x}^{\prime})=1)\geqslant
1-\delta$, where $\bm{x}$ and $\bm{x}^{\prime}$ are sampled independently and
where the probability is also over any internal randomness of $\mathcal{A}$.

Then there also exists a randomized algorithm $\mathcal{B}$ that takes as
input $x\in\mathcal{D}$ and runs in time
$O((T_{\mathrm{sample}}+T_{\mathrm{dist}})/\sqrt{\delta})$ with the following
guarantees:

  * •

$\operatorname*{\mathbb{P}}_{\bm{x}\sim\mathcal{P}}(\mathcal{B}(\bm{x})=0)\geqslant
1-\sqrt{2\delta}$, where the probability is also over any internal randomness
of $\mathcal{B}$.

  * •

$\operatorname*{\mathbb{P}}_{\bm{x}\sim\mathcal{Q}}(\mathcal{B}(\bm{x})=1)\geqslant
1-\sqrt{2\delta}$, where the probability is also over any internal randomness
of $\mathcal{B}$.

###### Proof.

Let $\bm{x}\in\mathcal{D}$ such that either $\bm{x}\sim\mathcal{P}$ or
$\bm{x}\sim\mathcal{Q}$. Let $M$ be a positive integer that we will fix later.
The randomized algorithm $\mathcal{B}$ is the following:

  1. 1.

Initialize $\Delta=0$.

  2. 2.

Repeat $M$ times:

    1. (a)

Sample $\bm{x}^{\prime}\sim\mathcal{Q}$.

    2. (b)

If $\mathcal{A}(x,\bm{x}^{\prime})$ returns $0$ and
$\mathcal{A}(\bm{x}^{\prime},\bm{x})$ returns $1$, increment $\Delta$.

  3. 3.

If $\Delta=M$, return $0$. Else, return $1$.

We now analyze the algorithm.

If $\bm{x}\sim\mathcal{P}$, then
$\operatorname*{\mathbb{P}}_{\bm{x}\sim\mathcal{P}}(\mathcal{B}(\bm{x})=1)=\operatorname*{\mathbb{P}}(\Delta<M)\leqslant
2M\delta$. This is because the probability that $\mathcal{A}$ is wrong in an
iteration is at most $\delta$, so the probability that $\mathcal{A}$ is wrong
in any of the $2M$ iterations is at most $2M\delta$.

On the other hand, if $\bm{x}\sim\mathcal{Q}$, we show that
$\operatorname*{\mathbb{P}}_{\bm{x}\sim\mathcal{Q}}(\mathcal{B}(\bm{x})=0)=\operatorname*{\mathbb{P}}(\Delta=M)\leqslant\frac{1}{M+1}$.
From now on, we condition on the internal randomness of $\mathcal{A}$, which
makes $\mathcal{A}$ deterministic, and show that the same probability upper
bound holds irrespective of this internal randomness. This implies that the
upper bound also holds unconditionally. To begin, let
$\bm{x}_{1},...,\bm{x}_{M}$ be the $M$ random variables corresponding to the
$x^{\prime}$ that are generated in the $M$ iterations. Then we are interested
in the event $E(\bm{x},(\bm{x}_{1},...,\bm{x}_{M}))$ that $\Delta$ is
incremented in each iteration. First, note that
$E(\bm{x},(\bm{x}_{1},...,\bm{x}_{M}))$ has the same probability as
$E(\bm{x}_{i},(\bm{x},\bm{x}_{1},...,\bm{x}_{i-1},\bm{x}_{i+1},...,\bm{x}_{M}))$
for all $i\in[M]$, because $\bm{x},\bm{x}_{1},...,\bm{x}_{M}$ are
independently and identically distributed according to $\mathcal{Q}$. Second,
note that all the events $E(\bm{x},(\bm{x}_{1},...,\bm{x}_{M}))$ and
$E(\bm{x}_{i},(\bm{x},\bm{x}_{1},...,\bm{x}_{i-1},\bm{x}_{i+1},...,\bm{x}_{M}))$
for all $i\in[M]$ are mutually exclusive (e.g., for $i\neq j$,
$E(\bm{x}_{i},(\bm{x},\bm{x}_{1},...,\bm{x}_{i-1},\bm{x}_{i+1},...,\bm{x}_{M}))$
implies that $\mathcal{A}(\bm{x}_{i},\bm{x}_{j})$ returns $0$, but
$E(\bm{x}_{j},(\bm{x},\bm{x}_{1},...,\bm{x}_{j-1},\bm{x}_{j+1},...,\bm{x}_{M}))$
implies that $\mathcal{A}(\bm{x}_{i},\bm{x}_{j})$ returns $1$, which is a
contradiction). Hence, the probability that $\Delta$ is incremented in every
iteration is at most $\frac{1}{M+1}$. Note that this argument did not use the
value of the internal randomness of $\mathcal{A}$, so the same probability
upper bound also holds unconditionally.

Taking $M=1/\sqrt{2\delta}$ gives the desired probability bounds. Finally, the
time complexity of algorithm $\mathcal{B}$ is
$O((T_{\mathrm{sample}}+T_{\mathrm{dist}})M)=O((T_{\mathrm{sample}}+T_{\mathrm{dist}})/\sqrt{\delta})$.
∎

## Acknowledgements

The authors thank David Steurer for helpful discussions. This project has
received funding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (grant agreement No
815464).

## References

  * [ABX08] Benny Applebaum, Boaz Barak, and David Xiao, _On basing lower-bounds for learning on worst-case assumptions_ , 2008 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2008, pp. 211–220.
  * [Ahl22] Thomas D Ahle, _Sharp and simple bounds for the raw moments of the binomial and poisson distributions_ , Statistics & Probability Letters 182 (2022), 109306.
  * [BB20] Matthew Brennan and Guy Bresler, _Reducibility and statistical-computational gaps from secret leakage_ , 2020.
  * [BBH+20] Matthew Brennan, Guy Bresler, Samuel B Hopkins, Jerry Li, and Tselil Schramm, _Statistical query algorithms and low-degree tests are almost equivalent_ , arXiv preprint arXiv:2009.06107 (2020).
  * [BHK+19] Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin, _A nearly tight sum-of-squares lower bound for the planted clique problem_ , SIAM Journal on Computing 48 (2019), no. 2, 687–735.
  * [BPP18] Guy Bresler, Sung Min Park, and Madalina Persu, _Sparse pca from sparse linear regression_ , Advances in Neural Information Processing Systems 31 (2018).
  * [BRST21] Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang, _Continuous lwe_ , Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (New York, NY, USA), STOC 2021, Association for Computing Machinery, 2021, p. 694–707.
  * [DK22] Ilias Diakonikolas and Daniel Kane, _Non-gaussian component analysis via lattice basis reduction_ , Conference on Learning Theory, PMLR, 2022, pp. 4535–4547.
  * [DKS17] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart, _Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures_ , 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, pp. 73–84.
  * [DKWB21] Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, and Afonso S. Bandeira, _The average-case time complexity of certifying the restricted isometry property_ , IEEE Transactions on Information Theory 67 (2021), no. 11, 7355–7361.
  * [DKWB22] Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, and Afonso S. Bandeira, _Subexponential-time algorithms for sparse pca_ , 2022.
  * [FGR+17] Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, and Ying Xiao, _Statistical algorithms and a lower bound for detecting planted cliques_ , vol. 64, Association for Computing Machinery, apr 2017.
  * [FKT15] Dean Foster, Howard Karloff, and Justin Thaler, _Variable selection is hard_ , Conference on Learning Theory, PMLR, 2015, pp. 696–709.
  * [GVV22] Aparna Gupte, Neekon Vafa, and Vinod Vaikuntanathan, _Continuous lwe is as hard as lwe & applications to learning gaussian mixtures_, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2022, pp. 1162–1173.
  * [GVV24] , _Sparse linear regression and lattice problems_ , arXiv submission (2024).
  * [HKP+17] Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer, _The power of sum-of-squares for detecting hidden structures_ , 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, pp. 720–731.
  * [Hop18] Samuel Hopkins, _Statistical inference and the sum of squares method_ , Ph.D. thesis, 2018, p. 430.
  * [HS17] Samuel B Hopkins and David Steurer, _Efficient bayesian estimation from few samples: community detection and related problems_ , 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, pp. 379–390.
  * [Kea98] Michael Kearns, _Efficient noise-tolerant learning from statistical queries_ , Journal of the ACM (JACM) 45 (1998), no. 6, 983–1006.
  * [KKMR22a] Jonathan Kelner, Frederic Koehler, Raghu Meka, and Dhruv Rohatgi, _Lower bounds on randomly preconditioned lasso via robust sparse designs_ , Advances in Neural Information Processing Systems 35 (2022), 24419–24431.
  * [KKMR22b] Jonathan A Kelner, Frederic Koehler, Raghu Meka, and Dhruv Rohatgi, _On the power of preconditioning in sparse linear regression_ , 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2022, pp. 550–561.
  * [KWB19] Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira, _Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio_ , arXiv preprint arXiv:1907.11636 (2019).
  * [KZ14] Pascal Koiran and Anastasios Zouzias, _Hidden cliques and the certification of the restricted isometry property_ , IEEE transactions on information theory 60 (2014), no. 8, 4999–5006.
  * [PV88] Leonard Pitt and Leslie G Valiant, _Computational limitations on learning from examples_ , Journal of the ACM (JACM) 35 (1988), no. 4, 965–984.
  * [Reg24] Oded Regev, _On lattices, learning with errors, random linear codes, and cryptography_ , 2024.
  * [RWY11] Garvesh Raskutti, Martin J Wainwright, and Bin Yu, _Minimax rates of estimation for high-dimensional linear regression over $\ell_{q}$-balls_, IEEE transactions on information theory 57 (2011), no. 10, 6976–6994.
  * [Val84] Leslie G Valiant, _A theory of the learnable_ , Communications of the ACM 27 (1984), no. 11, 1134–1142.
  * [Wai19] Martin J. Wainwright, _Graphical models for high-dimensional data_ , Cambridge Series in Statistical and Probabilistic Mathematics, p. 347–382, Cambridge University Press, 2019.
  * [ZSWB22] Ilias Zadik, Min Jae Song, Alexander S Wein, and Joan Bruna, _Lattice-based methods surpass sum-of-squares in clustering_ , Conference on Learning Theory, PMLR, 2022, pp. 1247–1248.
  * [ZWJ14] Yuchen Zhang, Martin J. Wainwright, and Michael I. Jordan, _Lower bounds on the performance of polynomial-time algorithms for sparse linear regression_ , Proceedings of The 27th Conference on Learning Theory (Barcelona, Spain) (Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, eds.), Proceedings of Machine Learning Research, vol. 35, PMLR, 13–15 Jun 2014, pp. 921–948.
  * [ZWJ15] Yuchen Zhang, Martin J. Wainwright, and Michael I. Jordan, _Optimal prediction for sparse linear models? lower bounds for coordinate-separable m-estimators_ , 2015.

##  Appendix A Concentration bounds

The following fact is taken from [Wai19, Example 2.11].

######  Fact A.1.

Let $\bm{X}\sim N(0,\mathrm{Id}_{n})$. Then

$\operatorname*{\mathbb{P}}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\frac{1}{n}\mathopen{}\mathclose{{}\left\lVert\bm{X}}\right\rVert^{2}-1}\right\rvert\geqslant
t}\right)\leqslant
2\exp\mathopen{}\mathclose{{}\left(-\frac{nt^{2}}{8}}\right)\,.$

##  Appendix B Low-degree lower bound for negative-spike sparse Wishart model

###  B.1 Low-degree framework

One significant barrier for proving computational lower bounds in high
dimension statistics is that we need to show average-case hardness: we want to
show that no efficient algorithms can succeed with high probability over
random inputs. It is notoriously difficult to show average-case hardness based
on worst-case hardness assumptions such as $\mathrm{P}\neq\mathrm{NP}$, except
in a few notable examples [Reg24, BRST21, BB20].

The low-degree method, which is developed in [HS17, Hop18, HKP+17], provides a
way to give evidence for average-case hardness by showing that no efficient
algorithms based on low-degree polynomials can succeed with high probability
over random inputs. In the context of hypothesis testing problems, it has been
applied to a wide range of fundamental problems, such as community detection
[HS17], spiked matrix models [KWB19], sparse principal component analysis
[HKP+17, DKWB22], and certifying restricted isometry property [DKWB21].

The crux of the techniques is to bound the projection of the likelihood ratio
function onto the space of low-degree polynomials:

######  Definition B.1 (Definition 1.14 in [KWB19]).

Let $\mathsf{V}^{\leqslant D}_{n}\subset L^{2}(\mathcal{Q}_{n})$ denote the
linear subspace of polynomials $\mathsf{S}_{n}\to\mathbb R$ of degree at most
$D$. Let $\mathsf{P}^{\leqslant
D}:L^{2}(\mathcal{Q}_{n})\to\mathsf{V}^{\leqslant D}_{n}$ denote the
orthogonal projection onto this linear subspace.777To clarify, the orthogonal
projection is with respect to the inner product induced by $\mathcal{Q}_{n}$
operator on this subspace. Finally, define the _$D$ -low-degree likelihood
ratio ($D$-LDLR)_ as $L_{n}^{\leqslant D}\coloneqq\mathsf{P}^{\leqslant
D}L_{n}$.

Then in hypothesis testing a low-degree lower bound shows that efficient
algorithms based on thresholding low-degree polynomials are inherently
obstructed from distinguishing the two distributions. Particularly, we have
the following proposition connecting the low-degree likelihood ratio and the
distribution separation by low-degree polynomials:

######  Proposition B.2 ([HS17, Hop18, KWB19]).

Let $\mathcal{P}$ and $\mathcal{Q}$ be two sequences of probability measures,
and $L_{n}=\frac{dP}{dQ}$ be their likelihood ratio. Then there exists
$\varepsilon>0$ and $D=D(n)\geqslant(\log n)^{1+\varepsilon}$ for which
$\|L_{n}^{\leqslant D}\|$ remains bounded as $n\to\infty$ if and only if for
any degree $\leqslant D$ polynomials $f(\cdot)$ we have

$\frac{\operatorname*{\mathbb{E}}_{\mathcal{P}}f}{\sqrt{\operatorname*{\mathbb{E}}_{\mathcal{Q}}f^{2}}}\leqslant
O(1)\,.$

The low-degree conjecture states that, for "sufficiently nice" distributions,
low-degree lower bounds rule out all polynomial-time algorithms that strongly
distinguish the distributions:

######  Conjecture B.3 (Informal, [Hop18, KWB19]).

For "sufficiently nice" sequences of probability measures $\mathcal{P}$ and
$\mathcal{Q}$, let $L_{n}=\frac{dP}{dQ}$ be their likelihood ratio. If there
exists $\varepsilon>0$ and $D=D(n)\geqslant(\log n)^{1+\varepsilon}$ for which
$\|L_{n}^{\leqslant D}\|$ remains bounded as $n\to\infty$, then there is no
polynomial-time algorithm that _strongly distinguishes_ $\mathcal{P}$ and
$\mathcal{Q}$, i.e., distinguishes the two distributions with $1-o(1)$
probability.

###  B.2 LD lower bound for negative-spike sparse Wishart model

In this section, we provide evidence of hardness for the sparse negative-spike
Wishart model, based on the low-degree likelihood ratio (LDLR) method.

We show that the low-degree likelihood ratio is bounded for the sparse
negative-spike Wishart model in the hard regime conjectured in 1.4.

Our proof follows closely the proof of [DKWB21]. The main differences are that
in our planted distribution the prior of $\bm{x^{*}}$ is the uniform
distribution over $k$-sparse vectors (instead of a sparse Rademacher
distribution, in which the exact sparsity can vary) and that the first
coordinate of $\bm{x^{*}}$ is non-zero.

######  Theorem B.4 (Low-degree lower bound for $\mathrm{NegSPCA}_{\theta}$).

Fix $\delta\in(0,0.1]$. Suppose that $n=o(\min(d,k^{2-\delta}))$. Consider the
planted distribution $\mathcal{P}_{n}$ formed from $n$ samples from
$\mathcal{P}$ and null distribution $\mathcal{Q}_{n}$ formed from $n$ samples
from $\mathcal{Q}$ in $\mathrm{NegSPCA}_{\theta}$ defined in Model 1.3. Then
for any degree-$k^{\delta}$ polynomial $f(z_{1},z_{2},\ldots,z_{n}):\mathbb
R^{n\times d}\to\mathbb R$ such that
$\operatorname*{\mathbb{E}}_{\mathcal{Q}}f=0$, we have

$\frac{\operatorname*{\mathbb{E}}_{\mathcal{P}_{n}}f}{\sqrt{\operatorname*{\mathbb{E}}_{\mathcal{Q}_{n}}f^{2}}}\leqslant
1+o(1)\,.$

###### Proof.

For degree-$D$ polynomials, the maximum value of
$\frac{\operatorname*{\mathbb{E}}_{\mathcal{P}_{n}}f}{\sqrt{\operatorname*{\mathbb{E}}_{\mathcal{Q}_{n}}f^{2}}}$
is given by (see [Hop18])

$\mathopen{}\mathclose{{}\left\lVert
L_{n,\gamma,\theta,\chi}}\right\rVert^{2}\coloneqq\operatorname*{\mathbb{E}}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left(\frac{d{\mathcal{P}_{n}}}{d{\mathcal{Q}_{n}}}}\right)^{\leqslant
D}}\right)^{2}\,.$

Equations (8) and (10) in [DKWB21] provide the bound

$\displaystyle\mathopen{}\mathclose{{}\left\lVert
L_{n,\gamma,\theta,\chi}}\right\rVert^{2}$
$\displaystyle\leqslant\sum_{\ell=0}^{\lfloor
D/2\rfloor}\frac{(2n+4D)^{\ell}}{\ell!}\cdot\frac{\theta^{2\ell}}{4^{\ell}}\cdot\operatorname*{\mathbb{E}}\langle\bm{x}^{(1)},\bm{x}^{(2)}\rangle^{2\ell}$
$\displaystyle\leqslant 1+\sum_{\ell=1}^{\lfloor
D/2\rfloor}\mathopen{}\mathclose{{}\left(\frac{4\theta^{2}\max(n,D)}{\ell}}\right)^{\ell}\operatorname*{\mathbb{E}}\langle\bm{x}^{(1)},\bm{x}^{(2)}\rangle^{2\ell}$
$\displaystyle\leqslant 1+\sum_{\ell=1}^{\lfloor
D/2\rfloor}\mathopen{}\mathclose{{}\left(\frac{4\max(n,D)}{\ell}}\right)^{\ell}\operatorname*{\mathbb{E}}\langle\bm{x}^{(1)},\bm{x}^{(2)}\rangle^{2\ell}\,,$

where $\bm{x}^{(1)},\bm{x}^{(2)}$ are independently sampled from the prior of
the spike vector in the planted distribution, i.e., the first coordinates
$\bm{x}_{1}^{(1)},\bm{x}_{1}^{(2)}$ are sampled uniformly from
$\mathopen{}\mathclose{{}\left\\{\pm\sqrt{\frac{1}{k+1}}}\right\\}$ and the
rest of the coordinates $\bm{x}_{\setminus 1}^{(1)},\bm{x}_{\setminus
1}^{(2)}$ are sampled uniformly from $k$-sparse
$\mathopen{}\mathclose{{}\left\\{\pm\sqrt{\frac{1}{k+1}},0}\right\\}^{d}$
vectors.

Now we note that

$\displaystyle\operatorname*{\mathbb{E}}\langle\bm{x}^{(1)},\bm{x}^{(2)}\rangle^{2\ell}$
$\displaystyle=\operatorname*{\mathbb{E}}\mathopen{}\mathclose{{}\left(\langle\bm{x}_{\setminus
1}^{(1)},\bm{x}_{\setminus
1}^{(2)}\rangle+\bm{x}_{1}^{(1)}\bm{x}_{1}^{(2)}}\right)^{2\ell}$
$\displaystyle\leqslant
2^{2\ell}\cdot\mathopen{}\mathclose{{}\left(\operatorname*{\mathbb{E}}\langle\bm{x}_{\setminus
1}^{(1)},\bm{x}_{\setminus
1}^{(2)}\rangle^{2\ell}+\operatorname*{\mathbb{E}}\mathopen{}\mathclose{{}\left(\bm{x}_{1}^{(1)}\bm{x}_{1}^{(2)}}\right)^{2\ell}}\right)$
$\displaystyle=2^{2\ell}\cdot\operatorname*{\mathbb{E}}\langle\bm{x}_{\setminus
1}^{(1)},\bm{x}_{\setminus
1}^{(2)}\rangle^{2\ell}+\mathopen{}\mathclose{{}\left(\frac{4}{(k+1)^{2}}}\right)^{\ell}\,,$

so

$\displaystyle\mathopen{}\mathclose{{}\left\lVert
L_{n,\gamma,\theta,\chi}}\right\rVert^{2}$ $\displaystyle\leqslant
1+\sum_{\ell=1}^{\lfloor
D/2\rfloor}\mathopen{}\mathclose{{}\left(\frac{16\max(n,D)}{\ell}}\right)^{\ell}\cdot\operatorname*{\mathbb{E}}\langle\bm{x}_{\setminus
1}^{(1)},\bm{x}_{\setminus 1}^{(2)}\rangle^{2\ell}+\sum_{\ell=1}^{\lfloor
D/2\rfloor}\mathopen{}\mathclose{{}\left(\frac{16\max(n,D)}{(k+1)^{2}\ell}}\right)^{\ell}\,.$

Using that $n=o(k^{2})$ and $D=o(k^{2})$, we have

$\sum_{\ell=1}^{\lfloor
D/2\rfloor}\mathopen{}\mathclose{{}\left(\frac{16\theta^{2}\max(n,D)}{(k+1)^{2}\ell}}\right)^{\ell}\leqslant
o(1)\,.$

For the remaining term, we have by Lemma B.5 that there is an absolute
constant $C>0$ such that

$\displaystyle\sum_{\ell=1}^{\lfloor
D/2\rfloor}\mathopen{}\mathclose{{}\left(\frac{16\max(n,D)}{\ell}}\right)^{\ell}\cdot\operatorname*{\mathbb{E}}\langle\bm{x}_{\setminus
1}^{(1)},\bm{x}_{\setminus 1}^{(2)}\rangle^{2\ell}$
$\displaystyle\leqslant\sum_{\ell=1}^{\lfloor
D/2\rfloor}\mathopen{}\mathclose{{}\left(C\cdot\max(n,D)\cdot\mathopen{}\mathclose{{}\left(\frac{1}{d}+\frac{\ell}{k^{2}}}\right)}\right)^{\ell}\,.$

For this sum to be bounded by $o(1)$, we want both $\max(n,D)=o(d)$ and
$\max(n,D)=o(k^{2}/D)$. This is achieved if $n=o(d)$ and $nD=o(k^{2})$ and
$D=o(k)$, so it is achieved under the conditions of the theorem with
$D\leqslant k^{\delta}$. Then

$\mathopen{}\mathclose{{}\left\lVert
L_{n,\gamma,\theta,\chi}}\right\rVert^{2}\leqslant 1+o(1)\,.$

∎

######  Lemma B.5 (Expectation bound).

In the setting of Theorem B.4, there exists an absolute constant $C>0$ such
that

$\operatorname*{\mathbb{E}}\langle{\bm{x}}_{\setminus
1}^{(1)},\bm{x}_{\setminus
1}^{(2)}\rangle^{2\ell}\leqslant(C\ell)^{\ell}\mathopen{}\mathclose{{}\left(\frac{1}{d}+\frac{\ell}{k^{2}}}\right)^{\ell}\,.$
(B.1)

###### Proof.

Let $\bm{S}_{1},\bm{S}_{2}\subset[d]$ be the sets of non-zero indices of
$\bm{x}_{\setminus 1}^{(1)}$ and $\bm{x}_{\setminus 1}^{(2)}$ respectively. We
have

$\displaystyle\operatorname*{\mathbb{E}}\langle{\bm{x}}_{\setminus
1}^{(1)},\bm{x}_{\setminus 1}^{(2)}\rangle^{2\ell}$
$\displaystyle=\frac{1}{(k+1)^{2\ell}}\operatorname*{\mathbb{E}}_{\bm{S}_{1},\bm{S}_{2}}\operatorname*{\mathbb{E}}\mathopen{}\mathclose{{}\left[\mathopen{}\mathclose{{}\left(\sum_{i\in\bm{S}_{1}\cap\bm{S}_{2}}\bm{\rho}_{i}}\right)^{2\ell}\Biggr{|}\bm{S}_{1},\bm{S}_{2}}\right]\,,$

where $\bm{\rho}_{i}$ are i.i.d. Rademacher variables. Then
$\sum_{i\in\bm{S}_{1}\cap\bm{S}_{2}}\bm{\rho}_{i}$ is a sub-Gaussian random
variable with variance proxy $|\bm{S}_{1}\cap\bm{S}_{2}|$, so for an absolute
constant $C>0$,

$\displaystyle\operatorname*{\mathbb{E}}\langle{\bm{x}}_{\setminus
1}^{(1)},\bm{x}_{\setminus 1}^{(2)}\rangle^{2\ell}$
$\displaystyle\leqslant\frac{(C\ell)^{\ell}}{(k+1)^{2\ell}}\operatorname*{\mathbb{E}}\mathopen{}\mathclose{{}\left\lvert\bm{S}_{1}\cap\bm{S}_{2}}\right\rvert^{\ell}\,.$

Let $\bm{a}_{i}\in\\{0,1\\}$ for $i\in[k]$ be the indicator that the $i$-th
element of $\bm{S}_{1}$ is also in $\bm{S}_{2}$. Then
$\mathopen{}\mathclose{{}\left\lvert\bm{S}_{1}\cap\bm{S}_{2}}\right\rvert=\bm{a}_{1}+\ldots+\bm{a}_{k}$.
Also let $\bm{b}_{i}$ for $i\in[k]$ be i.i.d. $\mathrm{Ber}(\tfrac{k}{d})$
variables. Then for any $S\subseteq[k]$ we have

$\operatorname*{\mathbb{E}}\prod_{i\in
S}\bm{a}_{i}=\frac{k}{d}\frac{k-1}{d-1}\ldots\frac{k-|S|+1}{d-|S|+1}\leqslant\mathopen{}\mathclose{{}\left(\frac{k}{d}}\right)^{|S|}=\operatorname*{\mathbb{E}}\prod_{i\in
S}\bm{b}_{i}\,.$

Then also
$\operatorname*{\mathbb{E}}(\bm{a}_{1}+\ldots+\bm{a}_{k})^{\ell}\leqslant\operatorname*{\mathbb{E}}\bm{B}^{\ell}$
where $\bm{B}$ is a $\mathrm{Bin}(k,\tfrac{k}{d})$ variable. [Ahl22, Corollary
1] gives that
$\operatorname*{\mathbb{E}}\bm{B}^{\ell}\leqslant\mathopen{}\mathclose{{}\left(\tfrac{k^{2}}{d}+\tfrac{\ell}{2}}\right)^{\ell}$.
Therefore, overall

$\operatorname*{\mathbb{E}}\langle{\bm{x}}_{\setminus
1}^{(1)},\bm{x}_{\setminus
1}^{(2)}\rangle^{\ell}\leqslant\frac{(C\ell)^{\ell}}{(k+1)^{2\ell}}\mathopen{}\mathclose{{}\left(\frac{k^{2}}{d}+\frac{\ell}{2}}\right)^{\ell}\leqslant(C\ell)^{\ell}\mathopen{}\mathclose{{}\left(\frac{1}{d}+\frac{\ell}{k^{2}}}\right)^{\ell}\,.$

∎

##  Appendix C Statistical query lower bound for negative-spike sparse Wishart
model

In this section, we prove a statistical query (SQ) lower bound for negative
spike sparse Wishart model. Our proof heavily relies on an almost equivalence
established between LDLR lower bounds and SQ lower bounds [BBH+20], and
resembles the proof in section 8.3 of their paper.

###  C.1 SQ framework

The SQ framework is a restricted computational model where a learning
algorithm can make certain types of queries to an oracle and get answers that
are subject to a certain degree of noise [Kea98]. We will focus on the SQ
model with VSTAT queries which is used in [BBH+20], where the learning
algorithm has access to the VSTAT oracle as defined below:

######  Definition C.1 (VSTAT oracle).

Given a query $\phi:\mathbb R^{d}\rightarrow[0,1]$ and a distribution $D$ over
$\mathbb R^{d}$, the VSTAT(n) oracle returns
$\operatorname*{\mathbb{E}}_{x\sim D}[\phi(x)]+\zeta$ for an adversarially
chosen $\zeta\in\mathbb R$ such that
$|\zeta|\leqslant\max\Big{(}\frac{1}{n},\sqrt{\frac{\operatorname*{\mathbb{E}}[\phi](1-\operatorname*{\mathbb{E}}[\phi])}{n}}\Big{)}$.

One way to show an SQ lower bound is by computing the statistical dimension of
the hypothesis testing problem, which is a measure on the complexity of the
testing problem. In this paper, we use the following definition of statistical
dimension introduced by [FGR+17]:

######  Definition C.2 (Statistical dimension).

Let $\mu_{\emptyset}$ be some distribution with $\mathcal{D}_{\emptyset}$ as
density function. Let
$\mathcal{S}=\mathopen{}\mathclose{{}\left\\{\mu_{u}}\right\\}$ be some family
of distributions indexed by $u$, such that $\mu_{u}$ has density function
given by $\mathcal{D}_{u}$. Consider the hypothesis testing problem between:

  * •

Null hypothesis: sample i.i.d. from $\mathcal{\mu}_{\emptyset}$,

  * •

Alternative hypothesis: sample i.i.d. from $\mathcal{\mu}_{u}$ where $u$ is
sampled from some prior distribution $\mu$.

For $D_{u}\in\mathcal{S}$, define the relative density
$\bar{D}_{u}(x)=\frac{D_{u}(x)}{D_{\emptyset}(x)}$ and the inner product
$\langle f,g\rangle=\operatorname*{\mathbb{E}}_{x\sim
D_{\emptyset}}[f(x)g(x)]$. The statistical dimension $SDA(\mathcal{S},\mu,n)$
measures the tail of $\langle\bar{D}_{u},\bar{D}_{v}\rangle-1$ with $u$, $v$
drawn independently from $\mu$:

$\displaystyle SDA(\mathcal{S},\mu,n)$ $\displaystyle=\max\Big{\\{}q\in\mathbb
N:\operatorname*{\mathbb{E}}_{u,v\sim\mu}\Big{[}|\langle\bar{D}_{u},\bar{D}_{v}\rangle-1|\mid
A\Big{]}\leqslant\frac{1}{n}\text{ for all events A
s.t.}\operatorname*{\mathbb{P}}_{u,v\in\mu}(A)\geqslant\frac{1}{q^{2}}\Big{\\}}\,.$

We will use $SDA(n)$ or $SDA(\mathcal{S},n)$ when $\mathcal{S}$ or $\mu$ are
clear from the context. In [FGR+17], it was shown that the statistical
dimension is a lower bound on the SQ complexity of the hypothesis test using
VSTAT oracles:

######  Theorem C.3 (Theorem 2.7 of [FGR+17], Theorem A.5 of [BBH+20]).

Let $D_{\emptyset}$ be a null distribution and $\mathcal{S}$ be a set of
alternative distributions. Then any (randomized) statistical query algorithm
which solves the hypothesis testing problem between $D_{\emptyset}$ and
$\mathcal{S}$ with probability at least $1-\gamma$ requires at least
$(1-\gamma)SDA(\mathcal{S},n)$ queries to $VSTAT(\frac{n}{3})$.

The almost equivalence between SQ lower bounds and low-degree lower bounds is
established in [BBH+20]:

######  Theorem C.4 (Theorem 3.1 in [BBH+20], LDLR to SDA).

Let $\ell\in\mathbb{N}$ with $\ell$ even and
$\mathcal{S}=\mathopen{}\mathclose{{}\left\\{D_{v}}\right\\}_{v\in S}$ be a
collection of probability distributions with prior $\mu$ over $\mathcal{S}$.
Suppose that $\mathcal{S}$ satisfies:

  * •

The $\ell$-sample high-degree part of the likelihood ratio is bounded by
$\mathopen{}\mathclose{{}\left\|\mathbf{E}_{u\sim\mathcal{S}}\mathopen{}\mathclose{{}\left(\bar{D}_{u}^{>\ell}}\right)^{\otimes\ell}}\right\|\leqslant\gamma$.

  * •

For some $n\in\mathbb{N}$, the degree-$\ell$ likelihood ratio is bounded by
$\mathopen{}\mathclose{{}\left\|\mathbf{E}_{u\sim\mathcal{S}}\mathopen{}\mathclose{{}\left(\bar{D}_{u}^{\otimes
n}}\right)^{\leqslant\ell}-1}\right\|\leqslant\varepsilon$.

Then for any $q\geqslant 1$, it follows that

$\operatorname{SDA}\mathopen{}\mathclose{{}\left(\mathcal{S},\frac{n}{q^{2/\ell}\mathopen{}\mathclose{{}\left(\ell\varepsilon^{2/\ell}+\gamma^{2/\ell}n}\right)}}\right)\geqslant
q\,.$

###  C.2 SQ lower bound for sparse negative-spike Wishart model

The sparse negative-spike Wishart model $\mathrm{NegSPCA}_{\theta}$ under the
statistical query framework has the following form:

######  Model C.5 (Sparse spiked Wishart model in SQ model).

Let $d,k\in\mathbb N$ with $d\geqslant k$ and $\theta\in(0,1)$. We define the
$\mathrm{NegSPCA}_{\theta}$ problem in the statistical query case as the
following distinguishing problem: We want to distinguish between the
distributions $\mathcal{P}$ or $\mathcal{Q}$ defined as follows, using VSTAT
oracle calls to them.

  * •

Planted distribution $\mathcal{P}$: Sample a unit vector $\bm{x}\in\mathbb
R^{d+1}$ with $\bm{x}_{1}=-\tfrac{1}{\sqrt{k+1}}$ and $\bm{x}_{\setminus 1}$
sampled uniformly from $k$-sparse
$\mathopen{}\mathclose{{}\left\\{\pm\tfrac{1}{\sqrt{k+1}},0}\right\\}^{d}$
vectors and fix it for the rest of the sampling procedure. Produce samples by
sampling from $N(0,\mathrm{Id}_{d+1}-\theta\cdot\bm{x}\bm{x}^{\top})$.

  * •

Null distribution $\mathcal{Q}$: $N(0,\mathrm{Id}_{d+1})$.

Corresponding to Theorem C.4, the set of distributions $\mathcal{S}$ is
parameterized by the random unit vector $\bm{x}$, and is given by
$\mathopen{}\mathclose{{}\left\\{N(0,\mathrm{Id}_{d+1}-\theta\cdot\bm{x}\bm{x}^{\top})}\right\\}$
in our setting. The prior distribution $\mu$ is determined by the distribution
of $\bm{x}$.

Under the statistical query framework, we have the following lower bound:

######  Theorem C.6 (SQ lower bound for $\mathrm{NegSPCA}_{\theta}$).

Consider the $\mathrm{NegSPCA}_{\theta}$ model. Let $0<\delta\leqslant 0.1$ be
an arbitrary absolute constant. Then, for
$n=o(\min(d/k^{\delta},k^{2-2\delta}))$, we have the SQ lower bound
$\text{SDA}(\mathcal{S},n)\geqslant 2^{k^{\delta}}$.

To apply the almost equivalence relation between low-degree lower bounds and
statistical query lower bounds, we need to prove the following lemma:

######  Lemma C.7.

Consider the $\mathrm{NegSPCA}_{\theta}$ model. Fix $\delta\in(0,0.1]$. Then
for any $\ell\leqslant k^{\delta}$, we have

$\mathopen{}\mathclose{{}\left\lVert\operatorname*{\mathbb{E}}_{u\sim\mathcal{S}}\mathopen{}\mathclose{{}\left(\bar{D}_{u}^{>\ell}}\right)^{\otimes\ell}}\right\rVert^{2}\leqslant
k^{-\ell^{2}/3}\,.$

###### Proof.

We follow the same proof as Lemma 8.21 in [BBH+20]888Particularly, we set
their $k$ and $d$ to $\ell$, and $n$ to $d$ in our setting., and get

$\mathopen{}\mathclose{{}\left\lVert\operatorname*{\mathbb{E}}_{u\sim\mathcal{S}}(\bar{D}_{x}^{>\ell})^{\otimes\ell}}\right\rVert^{2}\leqslant\ell^{2\ell^{2}}\mathopen{}\mathclose{{}\left(1-4\theta^{2}}\right)^{2\ell^{2}}\operatorname*{\mathbb{E}}\langle\bm{x}^{(1)},\bm{x}^{(2)}\rangle^{2\ell\cdot(\ell+1)}\,,$

where $\bm{x}^{(1)},\bm{x}^{(2)}$ are independently sampled from the prior of
the spike vector in the planted distribution, i.e., the first coordinates
$\bm{x}_{1}^{(1)},\bm{x}_{1}^{(2)}$ are sampled uniformly from
$\mathopen{}\mathclose{{}\left\\{\pm\sqrt{\frac{1}{k+1}}}\right\\}$ and the
rest of the coordinates $\bm{x}_{\setminus 1}^{(1)},\bm{x}_{\setminus
1}^{(2)}$ are sampled uniformly from $k$-sparse
$\mathopen{}\mathclose{{}\left\\{\pm\sqrt{\frac{1-\frac{1}{k+1}}{k}},0}\right\\}^{d}$
vectors.

Following the proof of Theorem B.4, we have

$\operatorname*{\mathbb{E}}\langle\bm{x}^{(1)},\bm{x}^{(2)}\rangle^{2\ell(\ell+1)}\leqslant
2^{2\ell(\ell+1)}\cdot(C\ell(\ell+1))^{\ell(\ell+1)}\cdot\mathopen{}\mathclose{{}\left(\frac{1}{d}+\frac{\ell(\ell+1)}{k^{2}}}\right)^{\ell(\ell+1)}+\mathopen{}\mathclose{{}\left(\frac{4}{(k+1)^{2}}}\right)^{\ell(\ell+1)}\,.$

As a result, when $\ell\leqslant k^{\delta}$, we have

$\ell^{2\ell^{2}}\mathopen{}\mathclose{{}\left(1-4\theta^{2}}\right)^{2\ell^{2}}\operatorname*{\mathbb{E}}\langle\bm{x}^{(1)},\bm{x}^{(2)}\rangle^{2\ell(\ell+1)}\leqslant(1/k^{1/3})^{\ell^{2}}\,,$

which finishes the proof. ∎

###### Proof of Theorem C.6.

We apply Theorem C.4 with $n=o(\min(d,k^{2-\delta}))$, $\ell=k^{\delta}$ and
$q=2^{\ell}$. By Lemma C.7, we can take $\gamma=k^{-\frac{\ell^{2}}{3}}$. By
Theorem B.4, we can take $\varepsilon=o(1)$. As a result, we have
$\text{SDA}(\mathcal{S},\frac{n}{100k^{\delta}})\geqslant 2^{k^{\delta}}$. ∎