# Sparse Linear Regression and Lattice Problems

Aparna Gupte
MIT
<EMAIL_ADDRESS>Research supported by the Ida M. Green MIT Office of Graduate
Education Fellowship. Neekon Vafa
MIT
<EMAIL_ADDRESS>Research supported by NSF fellowship DGE-2141064 and by the
grants of the third author. Vinod Vaikuntanathan
MIT
<EMAIL_ADDRESS>Research supported in part by DARPA under Agreement No.
HR00112020023, NSF CNS-2154149, a grant from the MIT-IBM Watson AI, a grant
from Analog Devices, a Microsoft Trustworthy AI grant, a Thornton Family
Faculty Research Innovation Fellowship from MIT and a Simons Investigator
Award. Any opinions, findings and conclusions or recommendations expressed in
this material are those of the author(s) and do not necessarily reflect the
views of the United States Government or DARPA.

###### Abstract

Sparse linear regression (SLR) is a well-studied problem in statistics where
one is given a design matrix $\mathbf{X}\in\mathbb{R}^{m\times n}$ and a
response vector $\mathbf{y}=\mathbf{X}\bm{\theta}^{*}+\mathbf{w}$ for a
$k$-sparse vector $\bm{\theta}^{*}$ (that is, $\|\bm{\theta}^{*}\|_{0}\leq k$)
and small, arbitrary noise $\mathbf{w}$, and the goal is to find a $k$-sparse
$\widehat{\bm{\theta}}\in\mathbb{R}^{n}$ that minimizes the mean squared
prediction error
$\frac{1}{m}\|\mathbf{X}\widehat{\bm{\theta}}-\mathbf{X}\bm{\theta}^{*}\|^{2}_{2}$.
While $\ell_{1}$-relaxation methods such as basis pursuit, Lasso, and the
Dantzig selector solve SLR when the design matrix is well-conditioned, no
general algorithm is known, nor is there any formal evidence of hardness in an
average-case setting with respect to all efficient algorithms.

We give evidence of average-case hardness of SLR w.r.t. all efficient
algorithms assuming the worst-case hardness of lattice problems. Specifically,
we give an instance-by-instance reduction from a variant of the bounded
distance decoding (BDD) problem on lattices to SLR, where the condition number
of the lattice basis that defines the BDD instance is directly related to the
restricted eigenvalue condition of the design matrix, which characterizes some
of the classical statistical-computational gaps for sparse linear regression.
Also, by appealing to worst-case to average-case reductions from the world of
lattices, this shows hardness for a _distribution_ of SLR instances; while the
design matrices are ill-conditioned, the resulting SLR instances are in the
identifiable regime.

Furthermore, for well-conditioned (essentially) _isotropic_ Gaussian design
matrices, where Lasso is known to behave well in the identifiable regime, we
show hardness of outputting _any_ good solution in the _unidentifiable_ regime
where there are many solutions, assuming the worst-case hardness of standard
and well-studied lattice problems.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results
    2. 1.2 Perspectives and Open Problems
    3. 1.3 Road Map of Main Results
  2. 2 Preliminaries
    1. 2.1 Bounded Distance Decoding
    2. 2.2 Sparse Linear Regression
  3. 3 Reduction from Bounded Distance Decoding
    1. 3.1 Interpretations
    2. 3.2 Proof of Theorem 4
  4. 4 Performance of Lasso on Our $k$-$\mathsf{SLR}$ Instances
    1. 4.1 Normalizing Our $k$-$\mathsf{SLR}$ Instances
    2. 4.2 Restricted Eigenvalue Condition
    3. 4.3 Prediction Error Achieved by Lasso on Our Instances
  5. 5 Reduction from CLWE
  6. A Complexity of Binary Bounded Distance Decoding
    1. A.1 Babai’s Rounding Off Algorithm
    2. A.2 Binary BDD Algorithm of [KF15]
    3. A.3 Reduction from BDD to Binary BDD
  7. B Proof of Completeness of Theorem 6
  8. C Reduction to $k$-$\mathsf{SLR}$ with Independent Noise

##  1 Introduction

We study the fundamental statistical problem of sparse linear regression where
one is given a design matrix $\mathbf{X}\in\mathbb{R}^{m\times n}$ and
responses $\mathbf{y}\in\mathbb{R}^{m}$ where

$\mathbf{y}=\mathbf{X}\bm{\theta}^{*}+\mathbf{w}$

for a hidden parameter vector $\bm{\theta}^{*}\in\mathbb{R}^{n}$ which is
$k$-sparse, i.e., it has at most $k$ non-zero entries, and a small, arbitrary
noise $\mathbf{w}\in\mathbb{R}^{m}$. The goal is to output a $k$-sparse vector
$\widehat{\bm{\theta}}$ such that the (mean squared) prediction error

$\frac{1}{m}\|\mathbf{X}\widehat{\bm{\theta}}-\mathbf{X}\bm{\theta}^{*}\|_{2}^{2}$

is as small as possible. Each row of $\mathbf{X}$ corresponds to a sample or a
measurement, and each column of $\mathbf{X}$ corresponds to a feature of the
model $\bm{\theta}^{*}$.

Information-theoretically, it is possible to achieve prediction error

$\frac{1}{m}\lVert\bm{\mathbf{X}}\bm{\mathbf{\widehat{\theta}}}-\bm{\mathbf{X}}\bm{\mathbf{\theta}}^{*}\rVert^{2}_{2}\leq\frac{4\lVert\bm{\mathbf{w}}\rVert_{2}^{2}}{m},$

regardless of the design matrix $\bm{\mathbf{X}}$. Algorithmically, however,
the prediction error achieved by many efficient polynomial-time algorithms
(such as $\ell_{1}$-relaxation or $\ell_{1}$-regularization including basis
pursuit and Lasso estimators [Tib96, CDS98] as well as the Dantzig selector
[CT07]) depends on the conditioning of the design matrix
$\mathbf{X}$—specifically, the _restricted-eigenvalue_ constant
$\zeta(\bm{\mathbf{X}})$, which essentially lower bounds the smallest singular
value of $\mathbf{X}$ restricted to nearly sparse vectors. (See Definition 6
for a formal definition.) By adapting the analysis of [NRWY12] (see Theorems 2
and 3), the thresholded Lasso estimator
$\widehat{\bm{\mathbf{\theta}}}_{\mathsf{TL}}$ achieves prediction
error111This bound assumes $\bm{\mathbf{X}}$ satisfies a certain column-
normalization condition (see Definition 4).

$\displaystyle\delta_{\mathsf{Lasso}}^{2}:=\frac{1}{m}\|\bm{\mathbf{X}}\widehat{\bm{\mathbf{\theta}}}_{\mathsf{TL}}-\bm{\mathbf{X}}\bm{\mathbf{\theta}}^{*}\|_{2}^{2}\leq
O\left(\frac{\|\bm{\mathbf{w}}\|^{2}_{2}\cdot
k^{2}}{\zeta(\bm{\mathbf{X}})^{2}\cdot m}\right).$

In particular, when the design matrix $\mathbf{X}$ is well-conditioned, i.e.,
$\zeta(\bm{\mathbf{X}})=\Omega(1)$ which, for example, happens when the rows
are drawn from $\mathcal{N}(\mathbf{0},\mathbf{I}_{n\times n})$ for
$m=\Omega(k\log n)$, the $\ell_{1}$-relaxation or $\ell_{1}$-regularization
algorithms achieve the information-theoretically optimal prediction error (up
to polynomial factors in $k$). The smaller the restricted eigenvalue constant,
the worse the prediction error bound. We emphasize that without computational
bounds, the achievable prediction error does not depend on the characteristics
of the design matrix $\mathbf{X}$.

In several naturally occurring high-dimensional regression problems, the
design matrix $\mathbf{X}$ may be ill-conditioned as the features, or even the
samples, could be correlated. An important question then is to understand
which design matrices admit efficient sparse linear regression algorithms and
which do not. Stated differently, is Lasso (and friends) the best possible
algorithm for sparse linear regression? This is the central question of
interest in this paper.

A handful of works have started to explore this question both from the
algorithmic front and the hardness front. On the algorithmic front, the recent
work of [KKMR21] showed an algorithm called pre-conditioned Lasso which
achieves low prediction error for certain ill-conditioned matrices where Lasso
provably fails. On the hardness front, [KKMR22, KKMR21] prove hardness against
particular algorithms, namely preconditioned Lasso. In terms of hardness
against all efficient algorithms, [ZWJ14] construct a fixed design matrix
$\bm{\mathbf{X}}_{\mathsf{ZWJ}}\in\mathbb{R}^{m\times n}$ such that solving
the $k$-sparse linear regression problem with better prediction error than
Lasso for $k\approx n/4$ on an arbitrary (worst-case) $k$-sparse ground truth
$\bm{\theta}^{*}$ implies that NP $\subseteq$ P/poly.222They show slightly
more, i.e., they construct a distribution over $\bm{\theta}^{*}$ for which
sparse linear regression is hard; however, to the best of our knowledge, this
distribution is not polynomial-time sampleable. Indeed, if this distribution
were sampleable, their result would show a worst-case to average-case
reduction for NP which remains a major open problem in complexity theory.
While an exciting initial foray into the landscape of hardness results for
sparse linear regression, [ZWJ14] inspires many more questions:

  1. 1.

Most importantly, which design matrices $\mathbf{X}$ are hard for sparse
linear regression? While [ZWJ14] gives us an example in the form of a single
$\bm{\mathbf{X}}_{\mathsf{ZWJ}}$, it does not give us much insight into the
hardness profile of a given design matrix.

  2. 2.

[ZWJ14] show that finding $k$-sparse solutions for $k\approx n/4$ (i.e.,
constant factor sparsity) is hard, but is it significantly easier to find much
sparser solutions, e.g. what happens with polynomial sparsity, logarithmic
sparsity or even constant sparsity? The problem certainly becomes easier, but
can we nevertheless show evidence of hardness?

  3. 3.

A related question is that of fine-grained hardness: while [ZWJ14] shows
evidence against polynomial-time algorithms, could there be non-trivial
algorithms that solve sparse linear regression significantly faster than brute
force search, i.e., in time $n^{o(k)}$?

In this paper, we show hardness results for sparse linear regression that
address all of these questions. In a nutshell, and hiding some details, we
show an instance-by-instance reduction from (a variant of) the bounded
distance decoding problem on a lattice with a given basis $\mathbf{B}$ to
sparse linear regression w.r.t. a design matrix $\mathbf{X}$ that is
essentially drawn from the Gaussian distribution
$\mathcal{N}(\mathbf{0},\bm{\Sigma})$, where
$\bm{\Sigma}=\bm{\Sigma}(\mathbf{B})$ is determined by $\mathbf{B}$. In
particular, this allows us to start from conjectured hard instances of lattice
problems and construct (nearly) Gaussian design matrices (with a covariance
matrix related to the lattice basis) for which $k$-SLR is hard, partially
addressing Question 1. Our main theorem (Theorem 1; see also Remark 2)
addresses Questions 2, handling a large range of sparsity parameters $k$, and
3, by showing a fine-grained reduction.

As a secondary result, even for well-conditioned (essentially) _isotropic_
Gaussian design matrices, where Lasso is known to behave well in the
identifiable regime, we show hardness of outputting _any_ good solution in the
less standard _unidentifiable_ regime where there are many solutions, assuming
the worst-case hardness of standard and well-studied lattice problems.

###  1.1 Our Results

#### Binary Bounded Distance Decoding.

Our source of hardness is lattice problems. Given a matrix
$\mathbf{B}\in\mathbb{R}^{d\times d}$, the lattice generated by $\mathbf{B}$
is

$\mathcal{L}(\mathbf{B})=\\{\mathbf{B}\mathbf{z}:\mathbf{z}\in\mathbb{Z}^{d}\\}.$

A lattice has many possible bases: indeed, $\mathbf{B}\mathbf{U}$ is a basis
of $\mathcal{L}(\mathbf{B})$ whenever $\mathbf{U}$ is a unimodular matrix,
i.e., an integer matrix with determinant $\pm 1$. The minimum distance
$\lambda_{1}(\mathbf{B})$ of the lattice $\mathcal{L}(\mathbf{B})$ is the
(Euclidean) length of the shortest non-zero vector in
$\mathcal{L}(\mathbf{B})$. Note that $\lambda_{1}(\mathbf{B})$ does not depend
on $\mathbf{B}$, only on $\mathcal{L}(\mathbf{B})$.333We actually use a
slightly different definition of $\lambda_{1}(\mathbf{B})$ which is
unimportant for this exposition; we refer the reader to Section 2 for more
details.

A canonical lattice problem is the bounded distance decoding (BDD): given a
basis $\mathbf{B}$ of a lattice, a target vector
$\mathbf{t}\in\mathbb{R}^{d}$, and a parameter $\alpha<1/2$, find a lattice
vector $\mathbf{v}\in\mathcal{L}(\mathbf{B})$ such that
$\mathsf{dist}(\mathbf{t},\mathbf{v})\leq\alpha\cdot\lambda_{1}(\mathbf{B})$
given the promise that such a vector exists (equivalently, that $\mathbf{t}$
is sufficiently close to the lattice). By the bound on $\alpha$, there is a
unique such vector. The BDD problem has been very well studied, especially in
the last decade, and is widely believed to be hard, for instance, forming the
basis of a new generation of post-quantum cryptographic algorithms recently
standardized by [NIS]. Our hardness assumption is a variant called binary BDD
(see, e.g. [KF15]) which asks for a vector $\mathbf{v}\in\mathbf{B}\cdot\\{\pm
1\\}^{d}$ that is close to the target $\mathbf{t}$ (as above), again under the
promise that such a vector exists. Equivalently, given a vector
$\mathbf{t}=\mathbf{B}\mathbf{z}+\mathbf{e}$ where $\mathbf{z}\in\\{\pm
1\\}^{d}$ and
$\lVert\bm{\mathbf{e}}\rVert\leq\alpha\cdot\lambda_{1}(\mathbf{B})$, the
problem is to find $\mathbf{z}$.

Both BDD and binary BDD are believed to be hard for arbitrary lattice bases
$\mathbf{B}$. Indeed, a canonical way to solve (binary as well as regular) BDD
is to employ Babai’s rounding algorithm [Bab86] which works as follows:
compute and output

$\mathsf{round}(\mathbf{B}^{-1}\mathbf{t})=\mathsf{round}(\mathbf{z}+\mathbf{B}^{-1}\mathbf{e})=\mathbf{z}+\mathsf{round}(\mathbf{B}^{-1}\mathbf{e})~{},$

namely, round each coordinate of $\mathbf{B}^{-1}\mathbf{t}$ to the nearest
integer. This works as long as each coordinate of $\mathbf{B}^{-1}\mathbf{e}$
is at most $1/2$, which happens as long as $\mathbf{e}$ is small and
$\mathbf{B}$ has a good condition number. In particular, Babai succeeds if
$\alpha=O(1/\kappa(\mathbf{B}))$, where
$\kappa(\mathbf{B})=\sigma_{\max}(\mathbf{B})/\sigma_{\min}(\mathbf{B})$ is
the condition number of $\mathbf{B}$. In other words, the condition number of
$\mathbf{B}$ determines the performance of the algorithm.

To be sure, there are algorithms for binary BDD that perform slightly better
than BDD: in particular, [KF15] show a $2^{O(d/\log\log(1/\alpha))}$-time
algorithm for binary BDD for a large range of $\alpha$ (see Theorem 7). In
particular, for $\alpha=1/\operatorname{poly}(d)$, this becomes a
$2^{O(d/\log\log d)}$-time algorithm for binary BDD, whereas the best run-time
for BDD algorithms in this regime is $2^{\Theta(d)}$. More than that, [KF15]
study binary BDD (and generalizations) in detail and give evidence of
hardness: they show reductions from variants of $\mathsf{GapSVP}$ and
$\mathsf{UniqueSVP}$ to (a slight generalization) of binary BDD, as well as a
direct reduction from low-density subset sum to binary BDD [KF15, Theorem 14].
In fact, [KF15] use this reduction and their
$2^{O(d/\log\log(1/\alpha))}$-time algorithm for binary BDD to give a state-
of-the-art algorithm for low-density subset sum. Improving on this
$2^{O(d/\log\log(1/\alpha))}$ run-time bound for binary BDD would consequently
give better algorithms for low-density subset sum.444We remark that the binary
LWE (learning with errors) problem, where the LWE secret is binary, is not a
special case of binary BDD even though LWE is a special case of BDD. Indeed,
when writing a binary LWE instance as a BDD instance in the canonical way,
only a part of the coefficient vector of the closest lattice point is binary.
Thus, even though binary LWE is equivalent in hardness to LWE, [GKPV10,
BLP+13, Mic18], we do not know such a statement relating binary BDD and BDD
that preserves conditioning of the lattice basis.

#### Our First Result.

Our first result shows that for every lattice basis $\mathbf{B}$, there is a
related covariance matrix $\bm{\Sigma}=\bm{\Sigma}(\mathbf{B})$ such that if
binary BDD is hard given the basis $\mathbf{B}$, then $k$-SLR is hard w.r.t.
an essentially Gaussian design matrix whose rows are i.i.d.
$\mathcal{N}(\mathbf{0},\bm{\Sigma})$.555The bottom $k\times n$ sub-matrix of
$\mathbf{X}$ (call it $\mathbf{X}_{2}$) is a fixed, worst-case, matrix while
each of the top rows is drawn i.i.d. from
$\mathcal{N}(\mathbf{0},\bm{\Sigma})$. There are two natural ways to remove
the “worst-case” nature of $\bm{\mathbf{X}}_{2}$. We discuss them in Section
3.1. The more precise statement follows. For $\beta\in[0,2]$, we say that a
$k$-$\mathsf{SLR}$ algorithm is a _$\beta$ -improvement_ of Lasso if on input
$(\bm{\mathbf{X}}\in\mathbb{R}^{m\times n},\bm{\mathbf{y}}\in\mathbb{R}^{m})$,
the algorithm achieves prediction error $\delta^{2}$ where

$\delta^{2}=\delta_{\mathsf{Lasso}}^{2}\cdot\zeta(\bm{\mathbf{X}})^{\beta}\cdot\operatorname{poly}(k,\log
n)\leq\frac{\|\bm{\mathbf{w}}\|^{2}_{2}}{\zeta(\bm{\mathbf{X}})^{2-\beta}\cdot
m}\cdot\operatorname{poly}(k,\log n).$

Note that $\beta=0$ corresponds to Lasso itself, and $\beta=2$ achieves the
information-theoretic bound (up to $\operatorname{poly}(k,\log n)$ factors).

######  Theorem 1.

There is a $\operatorname{poly}(m,k\cdot 2^{d/k})$-time randomized reduction
from $\mathsf{BinaryBDD}$ in $d$ dimensions with parameter $\alpha\leq 1/10$
to $k$-$\mathsf{SLR}$ in dimension $n=k\cdot 2^{d/k}$ and $m\geq 17d$ samples
that succeeds with probability $1-e^{-\Omega(m)}$. Moreover, the reduction
maps a $\mathsf{BinaryBDD}$ instance w.r.t. lattice basis $\bm{\mathbf{B}}$ to
design matrices $\bm{\mathbf{X}}\in\mathbb{R}^{m\times n}$ where

  * •

the distribution of each of the top $m-k$ rows is i.i.d.
$\mathcal{N}(\mathbf{0},\bm{\mathbf{\Sigma}})$ where
$\bm{\mathbf{\Sigma}}=\bm{\mathbf{G}}_{\mathsf{sparse}}^{\top}\bm{\mathbf{B}}^{\top}\bm{\mathbf{B}}\bm{\mathbf{G}}_{\mathsf{sparse}}$
for a fixed, instance-independent matrix
$\bm{\mathbf{G}}_{\mathsf{sparse}}\in\mathbb{R}^{d\times n}$;

  * •

each of the bottom $k$ rows is proportional to a fixed, instance-independent
vector that depends only on $n$ and $k$; and

  * •

if there is a $k$-$\mathsf{SLR}$ polynomial-time algorithm that is a
$\beta$-improvement to Lasso, then there is a $\operatorname{poly}(m,k\cdot
2^{d/k})$-time algorithm for $\mathsf{BinaryBDD}$ in $d$ dimensions with
parameter

$\alpha\leq\frac{1}{\operatorname{poly}(d)\cdot\kappa(\mathbf{B})^{2-\beta}}$

w.r.t. lattice bases $\bm{\mathbf{B}}$.

The first qualitative take-away message from our theorem is: if you beat
Lasso666More precisely, $\beta$-improve Lasso for $\beta>1$., you beat Babai.
The performance of the plain Lasso algorithm is determined by the restricted
eigenvalue constant; analogously, the performance of Babai’s rounding
algorithm is bounded by the condition number of the basis matrix. Our theorem
says that if you come up with an algorithm that beats the Lasso guarantee, in
the sense of achieving prediction error
$\frac{1}{\zeta(\mathbf{X})^{2-\beta}}$ for $\beta>1$, then you have at hand
an algorithm that beats the BDD approximation factor achieved by Babai’s
algorithm by a corresponding amount, namely solve BDD to within a factor of
$\frac{1}{\kappa(\mathbf{B})^{2-\beta}}$, whereas Babai’s algorithm itself
achieves an approximation factor of $\frac{1}{\kappa(\mathbf{B})}$. When
$\beta=2$, the $k$-SLR algorithm achieves the information-theoretic optimal
prediction error (up to polynomial factors in $d$ and $k$) in which case it
gives us a polynomial time binary BDD algorithm for $\alpha$ that is inverse-
polynomial in $d$.

To be sure, there are (recent) algorithms that solve sparse linear regression
beating the RE constant bound, e.g. [KKMR21, KKMR23]. These algorithms work by
first pre-conditioning the design matrix and running the plain Lasso w.r.t.
the preconditioned matrix. Our reduction then says that for BDD basis matrices
which map to the easy $k$-SLR instances identified by [KKMR21, KKMR23], you
can beat Babai. However, that should not be surprising, in general: there are
basis matrices $\mathbf{B}$ which can be “pre-conditioned”, e.g. using the
Lenstra-Lenstra-Lovász basis reduction algorithm or its variants [LLL82,
Sch87], thereby improving their condition number and consequently the
performance of Babai. Indeed, in our view, understanding the relationship
between the two types of preconditioning transformations — one from the
$k$-SLR world [KKMR21, KKMR23] and the other from the lattice world [LLL82,
Sch87] — is a fascinating open question.

On the other hand, there are also basis matrices whose condition number cannot
be improved in polynomial time. (If not, then running such a conditioning
algorithm and then Babai would give efficient worst-case lattice algorithms,
which we believe do not exist.) Indeed, given what we know about the hardness
of worst-case lattice problems, our theorem identifies a large class of design
matrices where solving sparse linear regression is at least as hard.

Furthermore, our theorem shows the hardness of sparse linear regression for a
range of sparsity parameters, addressing Question 2. The sparser the instance,
the longer the run-time of the binary BDD algorithm guaranteed by the
reduction. On one extreme, when $k=\Omega(d/\log d)$, the reduction runs in
$\mathsf{poly}(d)$ time and the sparsity $k=n^{1-\epsilon}$ can be set to any
polynomial function of $n$. On the other extreme, when $k$ is sufficiently
super-constant and (say) $\beta=2$, we get slightly subexponential-time (in
$d$) algorithms for binary BDD, beating the algorithm of [KF15] for
$k=\omega(\log\log d)$. Our reduction also addresses Question 3, because gives
us fine-grained hardness of $k$-$\mathsf{SLR}$ algorithms running in time
$n^{o(k)}$ (see Remark 2).

In order to directly address our Question 1, we can combine our main reduction
with known lattice reductions to generate an average-case hard instance for
$k$-SLR. In particular, we can reduce the average-case learning with errors
problem [Reg09], to (standard) BDD with bounded norm solutions, and then to
binary BDD using a gadget from [MP12] (see Appendix A.3). In turn, since the
learning with errors problem has a reduction from worst-case lattice problems
[Reg09, Pei09], this hardness result relies only on _worst-case_ hardness
assumptions, despite being _average-case_ over $k$-SLR instances. While the
resulting distribution over sparse linear regression design matrices is
degenerate and ill-conditioned, the resulting $k$-SLR instance is still in the
identifiable regime and information-theoretically solvable. As far as the
authors are aware, this is the first _average-case_ hardness result over
$k$-SLR instances, and relies only on _worst-case_ lattice assumptions.

Finally, as a teaser to our techniques, we emphasize that lattice problems are
fundamentally about integrality, while sparse-linear regression has no
integrality constraint. To make our reduction go through, we convert an
_integrality_ constraint in the lattice problem into a _sparsity_ constraint
by enforcing an additional linear constraint via a certain gadget matrix. See
Section 3.2 for more details.

#### Our Second Result.

Our second result, Theorem 6, shows the hardness of sparse linear regression
with a design matrix $\mathbf{X}$ whose rows are essentially drawn from the
spherical Gaussian $\mathcal{N}(\mathbf{0},\mathbf{I}_{n\times n})$, as long
as the number of samples is smaller than $k\log d$. Even though this puts us
in the non-identifiable regime where there may be many $\widehat{\theta}$
consistent with $(\mathbf{X},\mathbf{y})$, the problem of minimizing the mean
squared error777In the unidentifiable regime, minimizing the prediction error
is not information-theoretically possible without some constraint on the
noise. is well-defined. More precisely, the top $m-k$ rows of $\mathbf{X}$ are
i.i.d. $\mathcal{N}(\mathbf{0},\mathbf{I}_{n\times n})$ and the bottom $k$
rows are the same fixed matrix from Theorem 1. This is a regime where Lasso
would have solved the problem with a larger number of samples, giving some
evidence of the optimality of Lasso in terms of sample complexity. The
hardness assumption in this case is the continuous learning with errors (CLWE)
assumption which was recently shown to be as hard as standard and long-studied
worst-case short vector problems on lattices [BRST21, GVV22], which are used
as the basis for many post-quantum cryptographic primitives. We state the
result formally in Theorem 6 and prove it in Section 5.

###  1.2 Perspectives and Open Problems

We view our results as an initial foray into understanding the landscape of
average-case hardness of the sparse linear regression problem. One of our
results shows a distribution of average-case hard $k$-SLR instances (under
worst-case hardness of lattice problems). However, the design matrices that
arise in this distribution are very ill-conditioned; even though the $k$-SLR
instances they define are identifiable, the design matrices are singular and
have RE constant $0$. An immediate open question arising from this result is
whether one can come up with a more robust average-case hard distribution for
$k$-SLR.

More broadly, the connection to lattice problems that we exploit in our
reduction inspires a fascinating array of open questions. To begin with, as we
briefly discussed above, the recent improvements to $k$-SLR [KKMR21, KKMR23]
proceed via pre-conditioning the design matrix. Analogously, the famed LLL
algorithm of [LLL82] from the world of lattices is nothing but a pre-
conditioning algorithm for lattice bases. This leads us to ask: is there a
constructive way to use (ideas from) lattice basis reduction to get improved
$k$-SLR algorithms? We mention here the results of [GKZ21, ZSWB22] for
positive indications of the effectiveness of lattice basis reduction in
solving statistical problems. In the lattice world, it is known that if one
allows for arbitrary (potentially unbounded-time) pre-processing of a given
lattice basis, BDD can be solved with a polynomial approximation factor
[LLM06]. Is a similar statement true for $k$-SLR? We believe an exploration of
these questions and others is a fruitful avenue for future research.

#### Concurrent work.

The concurrent work of [BDT24] shows hardness of achieving non-trivial
prediction error in sparse linear regression with Gaussian designs in the
improper setting (where the estimator need not be sparse) by reducing from a
slight variant of a standard sparse PCA problem. In their setting, they deduce
a sample complexity lower bound of (roughly) $k^{2}$ for efficient algorithms,
where (roughly) $k$ is possible information-theoretically, by assuming a
(roughly) $k^{2}$ sample complexity lower bound on efficient algorithms for
the sparse PCA problem. (Their reduction produces instances in which the noise
is standard Gaussian. Our main theorem is written in terms of worst-case
noise, but we show a similar statement for independent Gaussian noise in
Appendix C.)

###  1.3 Road Map of Main Results

We prove Theorem 1 through a sequence of steps:

  1. 1.

In Section 3, we state and prove our reduction from
$\mathsf{BinaryBDD}_{d,\alpha}$ to $k$-$\mathsf{SLR}$ (Theorem 4).

  2. 2.

In Section 4.2, we give a bound on the restricted-eigenvalue constant $\zeta$
of the instances produced by this reduction in terms of $\kappa(\mathbf{B})$,
the condition number of the $\mathsf{BinaryBDD}_{d,\alpha}$ lattice instance
$\mathbf{B}$ (Lemma 8).

  3. 3.

In Section 4.3, using our reduction and the guarantees of Lasso in terms of
$\zeta$ (Theorem 3), we state how quantitative _improvements_ to Lasso (in
terms of the dependence on $\zeta$) give algorithms for
$\mathsf{BinaryBDD}_{d,\alpha}$ with quantitatively stronger parameters
(Theorem 5).

For the second result (hardness of $k$-$\mathsf{SLR}$ in the non-identifiable
regime even for _well-conditioned_ design matrices), we give the proof in
Section 5.

##  2 Preliminaries

For $n\in\mathbb{N}$, we use the notation $[n]:=\\{1,2,\cdots,n\\}$. We use
the standard definitions of the $\ell_{1},\ell_{2}$, and $\ell_{\infty}$ norms
in $\mathbb{R}^{n}$, as well as the $\ell_{0}$ “norm” which is defined as the
_sparsity_ , or number of non-zero entries of a vector
$\bm{\mathbf{v}}\in\mathbb{R}^{n}$. We use $\bm{\mathbf{bold}}$ notation to
denote vectors and matrices. For a matrix
$\bm{\mathbf{A}}\in\mathbb{R}^{m\times n}$ and $i\in[m]$, we write
$\mathsf{col}_{i}(\bm{\mathbf{A}})\in\mathbb{R}^{n}$ to denote the $i$th
column of $\bm{\mathbf{A}}$. We let $I_{n\times n}$ denote the standard
identity matrix in $\mathbb{R}^{n}$. For $\bm{\mathbf{v}}\in\mathbb{R}^{n}$,
we use the notation $\mathsf{round}(\bm{\mathbf{v}})\in\mathbb{Z}^{n}$ to
denote the point-wise rounding function applied to
$\bm{\mathbf{v}}\in\mathbb{R}^{n}$ (with arbitrary behavior at half integers).
We use the standard definitions of the maximum and minimum _singular values_
of $\bm{\mathbf{A}}$ for $m\geq n$:

$\sigma_{\min}(\bm{\mathbf{A}}):=\min_{\bm{\mathbf{v}}\in\mathbb{R}^{n}}\frac{\lVert\bm{\mathbf{A}}\bm{\mathbf{v}}\rVert_{2}}{\lVert\bm{\mathbf{v}}\rVert_{2}},\
\ \ \ \ \
\sigma_{\max}(\bm{\mathbf{A}}):=\max_{\bm{\mathbf{v}}\in\mathbb{R}^{n}}\frac{\lVert\bm{\mathbf{A}}\bm{\mathbf{v}}\rVert_{2}}{\lVert\bm{\mathbf{v}}\rVert_{2}}.$

We use the notation $\kappa(\bm{\mathbf{A}})$ to denote the _condition number_
of $\bm{\mathbf{A}}$, defined as

$\kappa(\bm{\mathbf{A}}):=\frac{\sigma_{\max}(\bm{\mathbf{A}})}{\sigma_{\min}(\bm{\mathbf{A}})}.$

We use the notation $\mathcal{N}(\mu,\sigma^{2})$ to denote the univariate
normal distribution with mean $\mu$ and standard deviation $\sigma$.
Similarly, we use the notation
$\mathcal{N}(\bm{\mathbf{\mu}},\bm{\mathbf{\Sigma}})$ to denote the
multivariate normal distribution with mean
$\bm{\mathbf{\mu}}\in\mathbb{R}^{n}$ and positive semi-definite covariance
matrix $\bm{\mathbf{\Sigma}}\in\mathbb{R}^{n\times n}$. We emphasize that we
do not require $\bm{\mathbf{\Sigma}}$ to be positive definite.

###  2.1 Bounded Distance Decoding

We now define lattice quantities that will be useful for us.

######  Definition 1.

For a full-rank matrix $\bm{\mathbf{B}}\in\mathbb{R}^{d\times d}$, the lattice
$\mathcal{L}(\bm{\mathbf{B}})$ generated by basis $\bm{\mathbf{B}}$ consists
of the set all integer linear combinations of the columns of
$\bm{\mathbf{B}}$. As is standard, we define

$\lambda_{1}(\bm{\mathbf{B}}):=\min_{\bm{\mathbf{z}}\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}}\lVert\bm{\mathbf{B}}\bm{\mathbf{z}}\rVert_{2},$

which corresponds to the shortest distance between any two elements of
$\mathcal{L}(\bm{\mathbf{B}})$. In this paper, since we consider a ($\pm 1$)
_binary_ version of the bounded distance decoding problem, we define the
quantity

$\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}}):=\min_{\bm{\mathbf{z}}_{1}\neq\bm{\mathbf{z}}_{2}\in\\{1,-1\\}^{d}}\lVert\bm{\mathbf{B}}\bm{\mathbf{z}}_{1}-\bm{\mathbf{B}}\bm{\mathbf{z}}_{2}\rVert_{2}.$

Note that while $\lambda_{1}(\bm{\mathbf{B}})$ is a basis-independent quantity
for the lattice $\mathcal{L}(\bm{\mathbf{B}})$,
$\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})$ depends on the basis
$\bm{\mathbf{B}}$.

######  Lemma 1.

For any matrix $\bm{\mathbf{B}}\in\mathbb{R}^{d\times d}$, we have
$\sigma_{\min}(\bm{\mathbf{B}})\leq\lambda_{1}(\bm{\mathbf{B}})\leq\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})\leq
2\sigma_{\max}(\bm{\mathbf{B}})$.

###### Proof.

It is immediate that
$\lambda_{1}(\bm{\mathbf{B}})\leq\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})$.
Let $\bm{\mathbf{e}}\in\mathbb{Z}^{d}$ be any standard basis vector. We have

$\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})=\min_{\bm{\mathbf{z}}_{1}\neq\bm{\mathbf{z}}_{2}\in\\{1,-1\\}^{d}}\lVert\bm{\mathbf{B}}(\bm{\mathbf{z}}_{1}-\bm{\mathbf{z}}_{2})\rVert_{2}\leq
2\lVert\bm{\mathbf{B}}\bm{\mathbf{e}}\rVert_{2}\leq
2\sigma_{\max}(\bm{\mathbf{B}})\lVert\bm{\mathbf{e}}\rVert_{2}=2\sigma_{\max}(\bm{\mathbf{B}}).$

We also have

$\lambda_{1}(\bm{\mathbf{B}})=\min_{\bm{\mathbf{z}}\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}}\lVert\bm{\mathbf{B}}\bm{\mathbf{z}}\rVert_{2}\geq\min_{\bm{\mathbf{z}}\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}}\sigma_{\min}(\bm{\mathbf{B}})\lVert\bm{\mathbf{z}}\rVert_{2}\geq\sigma_{\min}(\bm{\mathbf{B}}),$

since all $\bm{\mathbf{z}}\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}$ satisfy
$\lVert\bm{\mathbf{z}}\rVert_{2}\geq 1$. ∎

######  Definition 2 ($\mathsf{BinaryBDD}_{d,\alpha}$).

Let $\mathsf{BinaryBDD}_{d,\alpha}$ be the following worst-case search problem
in dimension $d\in\mathbb{N}$ with parameter $\alpha<1/2$. Given full rank
$\bm{\mathbf{B}}\in\mathbb{R}^{d\times d}$ and
$\bm{\mathbf{t}}\in\mathbb{R}^{d}$, output $\bm{\mathbf{z}}\in\\{-1,1\\}^{d}$
such that
$\lVert\bm{\mathbf{B}}\bm{\mathbf{z}}-\bm{\mathbf{t}}\rVert_{2}\leq\alpha\cdot\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})$
(if one exists). Equivalently, given
$(\bm{\mathbf{B}},\bm{\mathbf{B}}\bm{\mathbf{z}}+\bm{\mathbf{e}})$ for
$\lVert\bm{\mathbf{e}}\rVert_{2}\leq\alpha\cdot\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})$,
output $\bm{\mathbf{z}}\in\\{-1,1\\}^{d}$.

Note that by definition of $\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})$, the
constraint $\alpha<1/2$ guarantees the uniqueness of
$\bm{\mathbf{z}}\in\\{-1,1\\}^{d}$. As an aside, the standard $\mathsf{BDD}$
problem instead uses $\lambda_{1}(\mathbf{B})$ and allows outputting any
$\bm{\mathbf{z}}\in\mathbb{Z}^{d}$ instead of
$\bm{\mathbf{z}}\in\\{-1,1\\}^{d}$. Additionally, note that we could easily
consider full-rank $\mathbf{B}\in\mathbb{R}^{d_{1}\times d}$ for $d\leq
d_{1}\leq O(d)$ and our main results would all go through, and similarly for
larger $d_{1}$ with a slight change in the parameter dependence. Furthermore,
even though we write $\bm{\mathbf{B}}\in\mathbb{R}^{d\times d}$, we will
assume the entries of $\bm{\mathbf{B}}$ have $\operatorname{poly}(d)$ bits of
precision. (This is just for simplicity and convenience; one can modify the
corresponding algorithmic statements so that they run in polynomial time in
the description length of the basis $\mathbf{B}$.)

We note that there is a reduction from general BDD to $\mathsf{BinaryBDD}$, at
the cost of making the instance degenerate (in the sense of having a non-
trivial kernel). See Appendix A.3.

We now recall standard spectral bounds for random Gaussian matrices.

######  Lemma 2 ([RV10]).

Let $\bm{\mathbf{R}}\in\mathbb{R}^{m\times d}$ be such that
$R_{i,j}\sim_{\mathrm{i.i.d.}}\mathcal{N}(0,1)$. For all $t>0$, we have

$\Pr\left[\sqrt{m}-\sqrt{d}-t\leq\sigma_{\min}(\bm{\mathbf{R}})\leq\sigma_{\max}(\bm{\mathbf{R}})\leq\sqrt{m}+\sqrt{d}+t\right]\geq
1-2e^{-t^{2}/2}.$

In particular, for $m\geq 16d$, by setting $t=\sqrt{m}/4$, we have

$\Pr\left[\frac{\sqrt{m}}{2}\leq\sigma_{\min}(\bm{\mathbf{R}})\leq\sigma_{\max}(\bm{\mathbf{R}})\leq\frac{3\sqrt{m}}{2}\right]\geq
1-2e^{-m/32}.$

Throughout the paper, let $\chi^{2}(m)$ denote the chi-squared distribution
with $m$ degrees of freedom.

######  Lemma 3 ([LM00], Corollary of Lemma 1).

Let $X\sim\chi^{2}(m)$, i.e., $X$ is distributed according to the $\chi^{2}$
distribution with $m$ degrees of freedom. For any $t\geq 0$, we have

$\Pr[X\geq m+2\sqrt{tm}+2t]\leq e^{-t}.$

In particular, setting $t=m/4$, we get

$\Pr[X\geq 5m/2]\leq e^{-m/4}.$

###  2.2 Sparse Linear Regression

We now define the problem of $k$-sparse linear regression ($k$-$\mathsf{SLR}$
for short), which, for computational complexity simplicity, is phrased in
terms of mean squared error (as opposed to mean squared prediction error).

######  Definition 3 ($k$-$\mathsf{SLR}$).

Given a design matrix $\bm{\mathbf{X}}\in\mathbb{R}^{m\times n}$, a target
vector $\bm{\mathbf{y}}\in\mathbb{R}^{m}$, and $\delta>0$, output a $k$-sparse
$\bm{\mathbf{\widehat{\theta}}}\in\mathbb{R}^{n}$ such that

$\frac{\|\bm{\mathbf{X}}\bm{\mathbf{\widehat{\theta}}}-\bm{\mathbf{y}}\|^{2}_{2}}{m}\leq\delta^{2},$

assuming one exists.

We follow the convention of [NRWY12] of working with design matrices
$\bm{\mathbf{X}}$ that are _column-normalized_ :

######  Definition 4 (As in [NRWY12]).

We say a matrix $\widetilde{\bm{\mathbf{X}}}\in\mathbb{R}^{m\times n}$ is
_column-normalized_ if for all $i\in[n]$,

$\left\lVert\mathsf{col}_{i}(\widetilde{\bm{\mathbf{X}}})\right\rVert_{2}\leq\sqrt{m}.$

Now, we show that a column-normalized $\widetilde{\bm{\mathbf{X}}}$ also
satisfies a spectral bound with respect to sparse vectors.

######  Lemma 4.

Suppose $\widetilde{\bm{\mathbf{X}}}\in\mathbb{R}^{m\times n}$ is column-
normalized. Then,

$\displaystyle\max_{\begin{subarray}{c}\lVert\bm{\mathbf{v}}\rVert_{2}=1,\\\
\lVert\bm{\mathbf{v}}\rVert_{0}\leq
k\end{subarray}}\lVert\widetilde{\bm{\mathbf{X}}}\bm{\mathbf{v}}\rVert_{2}\leq\sqrt{km}.$

###### Proof.

Let $\bm{\mathbf{v}}$ be a vector such that
$\lVert\bm{\mathbf{v}}\rVert_{2}=1$ and $\lVert\bm{\mathbf{v}}\rVert_{0}\leq
k$. By the triangle inequality and column normalization, we have

$\displaystyle\lVert\widetilde{\bm{\mathbf{X}}}\bm{\mathbf{v}}\rVert_{2}=\left\lVert\sum_{i\in[n]}v_{i}\cdot\mathsf{col}_{i}(\widetilde{\bm{\mathbf{X}}})\right\rVert_{2}\leq\sum_{i\in[n]}|v_{i}|\cdot\left\lVert\mathsf{col}_{i}(\widetilde{\bm{\mathbf{X}}})\right\rVert_{2}\leq\sqrt{m}\cdot\lVert\bm{\mathbf{v}}\rVert_{1}\leq\sqrt{km},$

where the last inequality holds because
$\lVert\bm{\mathbf{v}}\rVert_{1}\leq\sqrt{k}\lVert\bm{\mathbf{v}}\rVert_{2}=\sqrt{k}$.
∎

To analyze the performance Lasso algorithm on the instances of
$k$-$\mathsf{SLR}$ we obtain from our reduction, we slightly modify the
analysis of [NRWY12] to allow for a more flexible definition of the
_restricted eigenvalue_ (RE) constant of a matrix. First, we define the
following cone.

######  Definition 5.

Let $S\subseteq[n]$ and $\epsilon>0$. We define $\mathbb{C}_{\epsilon}(S)$,
the $\epsilon$-cone for $S\subseteq[n]$, as follows:

$\mathbb{C}_{\epsilon}(S):=\\{\Delta\in\mathbb{R}^{n}:\|\Delta_{\bar{S}}\|_{1}\leq(1+\epsilon)\|\Delta_{S}\|_{1}\\}.$

The notation $\bar{S}$ denotes the complement of $S$, namely $[n]\setminus S$,
and the notation $\Delta_{I}\in\mathbb{R}^{|I|}$ denotes the restriction of
$\Delta$ to coordinates in $I\subseteq[n]$.

A standard definition (e.g., as in [NRWY12]) sets $\epsilon=2$, but we will
use the flexibility of setting $\epsilon$ close to $0$. Now, we define the
restricted eigenvalue condition.

######  Definition 6.

Suppose $\widetilde{\bm{\mathbf{X}}}\in\mathbb{R}^{m\times n}$ is column-
normalized. Then, we say $\widetilde{\bm{\mathbf{X}}}$ satisfies the
$(\epsilon,\zeta)$-_restricted eigenvalue (RE) condition_ for $S\subseteq[n]$
if

$\frac{\lVert\bm{\mathbf{\widetilde{X}}}\bm{\mathbf{\theta}}\rVert_{2}^{2}}{m\cdot\lVert\bm{\mathbf{\theta}}\rVert_{2}^{2}}\geq\zeta$

for all $\bm{\mathbf{\theta}}\in\mathbb{C}_{\epsilon}(S)$.

Note that this restricted eigenvalue condition corresponds to a restricted
form of a strong convexity condition over the loss function

$\mathcal{L}(\bm{\mathbf{\theta}}):=\frac{1}{2m}\lVert\bm{\mathbf{y}}-\widetilde{\bm{\mathbf{X}}}\bm{\mathbf{\theta}}\rVert_{2}^{2}.$

Also note that the $\ell_{1}$-regularization-based Lasso estimator does not
output a $k$-sparse solution. To obtain a $k$-sparse solution, we truncate
$\bm{\mathbf{\widehat{\theta}}}_{\lambda}$ to the $k$ entries of largest
absolute value, to obtain the thresholded Lasso estimate
$\bm{\mathbf{\widehat{\theta}}}_{\mathsf{TL}}$. Lemma 9 of [ZWJ14] shows that
$\lVert\bm{\mathbf{\widehat{\theta}}}_{\mathsf{TL}}-\bm{\mathbf{\theta}}^{*}\rVert_{2}\leq
5\lVert\bm{\mathbf{\widehat{\theta}}}_{\lambda}-\bm{\mathbf{\theta}}^{*}\rVert_{2}$.

Now, we state a modified version of Corollary 1 of [NRWY12], which tells us an
error bound on the thresholded Lasso estimator, given our modified definition
of the restricted eigenvalue condition.

######  Theorem 2 (Modified Version of Corollary 1 of [NRWY12]).

Let $\epsilon\in(0,2]$, let $\widetilde{\bm{\mathbf{X}}}\in\mathbb{R}^{m\times
n}$ be column-normalized, and let
$\widetilde{\bm{\mathbf{y}}}=\widetilde{\bm{\mathbf{X}}}\bm{\mathbf{\theta}}^{*}+\widetilde{\bm{\mathbf{w}}}$
for some $k$-sparse vector $\bm{\mathbf{\theta}}^{*}$ supported on $S$ for
$S\subseteq[n],|S|=k$. Suppose $\widetilde{\bm{\mathbf{X}}}$ satisfies the
$(\epsilon,\zeta)$-restricted eigenvalue condition for $S$. As long as

$\lambda\geq\frac{2+\epsilon}{\epsilon}\cdot\left\lVert\frac{1}{m}\widetilde{\bm{\mathbf{X}}}^{\top}\widetilde{\bm{\mathbf{w}}}\right\rVert_{\infty},$

and $\lambda>0$, then any Lasso solution
$\bm{\mathbf{\widehat{\theta}}}_{\lambda}$ with regularization parameter
$\lambda$ satisfies the bound

$\displaystyle\lVert\bm{\mathbf{\widehat{\theta}}}_{\lambda}-\bm{\mathbf{\theta}}^{*}\rVert^{2}_{2}$
$\displaystyle\leq O\left(\frac{\lambda^{2}k}{\zeta^{2}}\right).$

While the bounds in the theorem statement above do not depend on column
normalization of $\widetilde{\bm{\mathbf{X}}}$ (or corresponding normalization
of $\widetilde{\bm{\mathbf{w}}}$), our definition of the restricted eigenvalue
condition needs the matrix to be column-normalized (in particular, so that the
RE constant is scale invariant with respect to $\bm{\mathbf{B}}$). The
$\epsilon$ dependence in $\lambda$ comes from modifying [NRWY12, Lemma 1],
which needs the bound on $\lambda$ as above to guarantee that the optimal
error
$\widehat{\Delta}:=\bm{\mathbf{\widehat{\theta}}}_{\lambda}-\bm{\mathbf{\theta}}^{*}$
satisfies $\widehat{\Delta}\in\mathbb{C}_{\epsilon}(S)$.

######  Theorem 3.

Let $\epsilon\in(0,2]$, let $\widetilde{\bm{\mathbf{X}}}\in\mathbb{R}^{m\times
n}$ be column-normalized, and let
$\widetilde{\bm{\mathbf{y}}}=\widetilde{\bm{\mathbf{X}}}\bm{\mathbf{\theta}}^{*}+\widetilde{\bm{\mathbf{w}}}$
for some $k$-sparse vector $\bm{\mathbf{\theta}}^{*}$ supported on $S$ for
$S\subseteq[n],|S|=k$. Suppose $\widetilde{\bm{\mathbf{X}}}$ satisfies the
$(\epsilon,\zeta)$-restricted eigenvalue condition for $S$. For an optimally
chosen positive regularization parameter, the thresholded Lasso solution
$\bm{\mathbf{\widehat{\theta}}}_{\mathsf{TL}}$ with satisfies the prediction
error bound

$\displaystyle\frac{1}{m}\|\widetilde{\bm{\mathbf{X}}}\widehat{\bm{\mathbf{\theta}}}_{\mathsf{TL}}-\widetilde{\bm{\mathbf{X}}}\bm{\mathbf{\theta}}^{*}\|_{2}^{2}\leq
O\left(\frac{\lVert\widetilde{\bm{\mathbf{w}}}\rVert_{2}^{2}\cdot
k^{2}}{\zeta^{2}\cdot\epsilon^{2}\cdot m}\right).$

###### Proof.

From Theorem 2, we know that for

$\lambda\geq\frac{2+\epsilon}{\epsilon}\cdot\left\lVert\frac{1}{m}\widetilde{\bm{\mathbf{X}}}^{\top}\widetilde{\bm{\mathbf{w}}}\right\rVert_{\infty},$

we have

$\displaystyle\lVert\bm{\mathbf{\widehat{\theta}}}_{\lambda}-\bm{\mathbf{\theta}}^{*}\rVert_{2}$
$\displaystyle\leq O\left(\frac{\lambda\sqrt{k}}{\zeta}\right).$

By [ZWJ14, Lemma 9], we therefore have

$\displaystyle\lVert\bm{\mathbf{\widehat{\theta}}}_{\mathsf{TL}}-\bm{\mathbf{\theta}}^{*}\rVert_{2}$
$\displaystyle\leq O\left(\frac{\lambda\sqrt{k}}{\zeta}\right).$

Plugging in the optimal choice of $\lambda$ yields

$\displaystyle\lVert\bm{\mathbf{\widehat{\theta}}}_{\mathsf{TL}}-\bm{\mathbf{\theta}}^{*}\rVert_{2}$
$\displaystyle\leq
O\left(\frac{\sqrt{k}}{\epsilon\cdot\zeta}\cdot\left\lVert\frac{1}{m}\widetilde{\bm{\mathbf{X}}}^{\top}\widetilde{\bm{\mathbf{w}}}\right\rVert_{\infty}\right).$

Since $\widetilde{\mathbf{X}}$ is column-normalized, we know

$\displaystyle\left\lVert\frac{1}{m}\widetilde{\bm{\mathbf{X}}}^{\top}\widetilde{\bm{\mathbf{w}}}\right\rVert_{\infty}=\frac{1}{m}\max_{i\in[n]}\left|\left\langle\mathsf{col}_{i}(\widetilde{\mathbf{X}}),\widetilde{\bm{\mathbf{w}}}\right\rangle\right|\leq\frac{1}{m}\left\lVert\mathsf{col}_{i}(\widetilde{\mathbf{X}})\right\rVert_{2}\left\lVert\widetilde{\bm{\mathbf{w}}}\right\rVert_{2}\leq\frac{\left\lVert\widetilde{\bm{\mathbf{w}}}\right\rVert_{2}}{\sqrt{m}},$

where the first inequality is due to Cauchy-Schwarz, and the second inequality
is due to column normalization. Combining the two above inequalities, we have

$\displaystyle\lVert\bm{\mathbf{\widehat{\theta}}}_{\mathsf{TL}}-\bm{\mathbf{\theta}}^{*}\rVert_{2}$
$\displaystyle\leq
O\left(\frac{\sqrt{k}\cdot\left\lVert\widetilde{\bm{\mathbf{w}}}\right\rVert_{2}}{\epsilon\cdot\zeta\cdot\sqrt{m}}\right).$

Since $\bm{\mathbf{\widehat{\theta}}}_{\mathsf{TL}}-\bm{\mathbf{\theta}}^{*}$
is $2k$-sparse, we can apply Lemma 4 to get

$\displaystyle\lVert\widetilde{\mathbf{X}}\bm{\mathbf{\widehat{\theta}}}_{\mathsf{TL}}-\widetilde{\mathbf{X}}\bm{\mathbf{\theta}}^{*}\rVert_{2}$
$\displaystyle\leq
O\left(\frac{k\cdot\left\lVert\widetilde{\bm{\mathbf{w}}}\right\rVert_{2}}{\epsilon\cdot\zeta}\right).$

Squaring and dividing by $m$ gives the desired result. ∎

######  Remark 1.

We remark that Theorems 2 and 3 imply that in the noiseless setting of
$k$-$\mathsf{SLR}$, that is, when
$\bm{\mathbf{y}}=\bm{\mathbf{X}}\bm{\mathbf{\theta}}^{*}$, Lasso not only
achieves prediction error $0$ but also recovers the ground truth
$\bm{\mathbf{\theta}}^{*}$ as long as the restricted eigenvalue constant is
strictly positive. In particular, this means that any reduction showing the
$\mathbf{NP}$-hardness of noiseless sparse linear regression must produce
instances with design matrices with restricted eigenvalue $0$ (unless
$\mathbf{P}=\mathbf{NP}$).

However, there is no reason information theoretically that the prediction
error should have dependence on the RE constant $\zeta$. We now state a bound
on the prediction error of the optimal $\ell_{0}$ predictor, which need not be
computationally efficient.

######  Proposition 1.

Let $\bm{\mathbf{X}}\in\mathbb{R}^{m\times n}$, and let
$\bm{\mathbf{y}}=\bm{\mathbf{X}}\bm{\mathbf{\theta}}^{*}+\bm{\mathbf{w}}$ for
some $k$-sparse $\bm{\mathbf{\theta}}^{*}\in\mathbb{R}^{n}$. The
$\ell_{0}$-predictor

$\bm{\mathbf{\widehat{\theta}}}\in\operatorname*{arg\,min}_{\lVert\bm{\mathbf{\theta}}\rVert_{0}\leq
k}\lVert\bm{\mathbf{X}}\bm{\mathbf{\theta}}-\bm{\mathbf{y}}\rVert_{2}^{2}$

satisfies the prediction error bound

$\frac{\lVert\bm{\mathbf{X}}\bm{\mathbf{\widehat{\theta}}}-\bm{\mathbf{X}}\bm{\mathbf{\theta}}^{*}\rVert^{2}_{2}}{m}\leq\frac{4\lVert\bm{\mathbf{w}}\rVert_{2}^{2}}{m}.$

###### Proof.

By definition of $\bm{\mathbf{\widehat{\theta}}}$ and since
$\bm{\mathbf{\theta}}^{*}$ is $k$-sparse, we know

$\lVert\bm{\mathbf{X}}\bm{\mathbf{\widehat{\theta}}}-\bm{\mathbf{y}}\rVert_{2}\leq\lVert\bm{\mathbf{X}}\bm{\mathbf{\theta}}^{*}-\bm{\mathbf{y}}\rVert_{2}=\lVert\bm{\mathbf{w}}\rVert_{2}.$

By the triangle inequality,

$\lVert\bm{\mathbf{X}}\bm{\mathbf{\widehat{\theta}}}-\bm{\mathbf{X}}\bm{\mathbf{\theta}}^{*}\rVert_{2}\leq\lVert\bm{\mathbf{X}}\bm{\mathbf{\widehat{\theta}}}-\bm{\mathbf{y}}\rVert_{2}+\lVert\bm{\mathbf{y}}-\bm{\mathbf{X}}\bm{\mathbf{\theta}}^{*}\rVert_{2}\leq
2\lVert\bm{\mathbf{w}}\rVert_{2}.$

The bound immediately follows by squaring and dividing by $m$. ∎

Comparing Theorem 3 and Proposition 1 highlights a critical computational-
statistical gap: the prediction error for the Lasso algorithm depends
quantitatively on the restricted eigenvalue condition of the design matrix,
whereas the information-theoretic minimizer has prediction error that is
completely independent of the restricted eigenvalue condition.

##  3 Reduction from Bounded Distance Decoding

Our main result in this section is a reduction from
$\mathsf{BinaryBDD}_{d,\alpha}$ to $k$-$\mathsf{SLR}$:

######  Theorem 4.

Let $d,m,n,k$ be integers such that $k$ divides $d$, $m\geq 17d$ and $n=k\cdot
2^{d/k}$. Then, there is a $\operatorname{poly}(n,m)$-time reduction from
$\mathsf{BinaryBDD}_{d,\alpha}$ in dimension $d$ with parameter $\alpha\leq
1/10$ to $k$-$\mathsf{SLR}$ in dimension $n$ with $m$ samples. The reduction
is randomized and succeeds with probability $1-e^{-\Omega(m)}$. Moreover, the
reduction maps a $\mathsf{BinaryBDD}_{d,\alpha}$ instance
$(\bm{\mathbf{B}},\cdot)$ to $k$-$\mathsf{SLR}$ instances with design matrices
$\mathbf{X}\in\mathbb{R}^{m\times n}$ and parameter
$\delta=\Theta(\lambda_{1,\mathsf{bin}}(\mathbf{B}))$ such that
$\bm{\mathbf{X}}$ that can be decomposed as

$\bm{\mathbf{X}}=\begin{pmatrix}\bm{\mathbf{X}}_{1}\\\
\bm{\mathbf{X}}_{2}\end{pmatrix},$

where the distribution of each row of
$\bm{\mathbf{X}}_{1}\in\mathbb{R}^{(m-k)\times n}$ is $\mathrm{i.i.d.}$
$\mathcal{N}(\mathbf{0},\bm{\mathbf{G}}_{\mathsf{sparse}}^{\top}\bm{\mathbf{B}}^{\top}\bm{\mathbf{B}}\bm{\mathbf{G}}_{\mathsf{sparse}})$
for a fixed, instance-independent matrix
$\bm{\mathbf{G}}_{\mathsf{sparse}}\in\mathbb{R}^{d\times n}$, and
$\bm{\mathbf{X}}_{2}\in\mathbb{R}^{k\times n}$ is proportional to a fixed,
instance-independent matrix that depends only on $n$ and $k$.

######  Remark 2.

This reduction also gives us a _fine-grained_ hardness result. Suppose there
is an algorithm for $k$-$\mathsf{SLR}$ in $n$ dimensions with $m$ samples that
runs in time $\operatorname{poly}(m,k)\cdot(n/k)^{k^{1-\epsilon}}$. Then, the
above reduction gives an algorithm for $\mathsf{BinaryBDD}_{d,\alpha}$ in $d$
dimensions that runs in time $\operatorname{poly}(d)\cdot 2^{d/k^{\epsilon}}$.

[GV21] also prove a fine-grained hardness result for $k$-$\mathsf{SLR}$ from a
lattice problem, specifically the closest vector problem. However, the key
difference is that their result is in the unidentifiable regime, whereas ours
is in the identifiable regime, i.e. the $k$-SLR instances produced by the
reduction from binary BDD have a unique solution. Further, their fine-grained
hardness results are for worst-case covariates, whereas our hardness results
produces covariates drawn from a Gaussian (with a covariance matrix determined
by the binary-BDD basis).

###  3.1 Interpretations

We now interpret the distribution of the design matrices $\bm{\mathbf{X}}$ in
the reduction in Theorem 4. As stated, the sub-matrix $\bm{\mathbf{X}}_{2}$ is
phrased as a worst-case design matrix, while $\bm{\mathbf{X}}_{1}$ has i.i.d.
$\mathcal{N}(\mathbf{0},\bm{\mathbf{G}}_{\mathsf{sparse}}^{\top}\bm{\mathbf{B}}^{\top}\bm{\mathbf{B}}\bm{\mathbf{G}}_{\mathsf{sparse}})$
rows, where the covariance matrix is tightly related to the
$\mathsf{BinaryBDD}_{d,\alpha}$ instance $\bm{\mathbf{B}}$. (The definition of
the fixed, instance-independent gadget matrix
$\bm{\mathbf{G}}_{\mathsf{sparse}}$ is given in Section 3.2.)

There are two natural ways to remove the “worst-case” nature of
$\bm{\mathbf{X}}_{2}$ in our instances:

  1. 1.

Our reduction still holds if the $\bm{\mathbf{X}}_{2}$ part of our design
matrix is removed, and instead, one enforced an exact linear constraint on
$\bm{\mathbf{\theta}}$ (specifically,
$\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{\theta}}=\mathbf{1}$, where
$\bm{\mathbf{G}}_{\mathsf{partite}}$ is defined in Section 3.2). This
corresponds to constraining the $k$-sparse regression vector
$\bm{\mathbf{\theta}}\in\mathbb{R}^{n}$ to an affine subspace. Since many of
the techniques for sparse linear regression involve convex optimization,
intersecting the solution landscape with this affine subspace will preserve
convexity, so these algorithms would still work if the design matrix were just
$\bm{\mathbf{X}}_{1}$ on its own, without the worst-case $\bm{\mathbf{X}}_{2}$
sub-matrix.

  2. 2.

Alternatively, one can interpret each row of $\bm{\mathbf{X}}_{2}$ as a mean
of a Gaussian distribution with a covariance matrix $\sigma^{2}I_{n\times n}$
for very small $\sigma>0$. By reordering the rows of $\bm{\mathbf{X}}$ and
entries of the target $\bm{\mathbf{y}}$, all rows of $\bm{\mathbf{X}}$ can now
be drawn i.i.d. from a _mixture_ of $k+1$ Gaussians, with weight $(m-k)/m$ on
$\mathcal{N}(\mathbf{0},\bm{\mathbf{G}}_{\mathsf{sparse}}^{\top}\bm{\mathbf{B}}^{\top}\bm{\mathbf{B}}\bm{\mathbf{G}}_{\mathsf{sparse}})$
and weight $1/m$ on $\mathcal{N}(\bm{\mathbf{v}}_{i},\sigma^{2}I_{n\times n})$
for all $i\in[k]$, where $\bm{\mathbf{v}}_{i}$ is the $i$th row of
$\bm{\mathbf{X}}_{2}$ and $\sigma>0$ is very small. Our reduction will go
through (with modified parameters) as long as we increase the number of
samples $m$ to roughly $O(m\log(k))$ so that each row of $\bm{\mathbf{X}}_{2}$
is hit by a coupon collector argument.

###  3.2 Proof of Theorem 4

Before proving Theorem 4, we introduce some notation and gadgets that will be
useful for us. For $n,k\in\mathbb{N}$ where $n$ is a multiple of $k$, let
$\mathcal{S}_{n,k}$ denote the set of $k$-sparse, $k$-partite binary vectors
$\bm{\mathbf{v}}\in\\{0,1\\}^{n}$. That is, for each $i\in\\{0,\cdots,k-1\\}$,
there exists a unique $j\in[n/k]$ such that $v_{in/k+j}=1$, and all other
entries of $\bm{\mathbf{v}}$ are $0$.

Let $\bm{\mathbf{G}}_{\mathsf{sparse}}\in\mathbb{R}^{d\times n}$ be the
following (rectangular) block diagonal matrix, which will allow us to map
binary vectors to binary sparse partite vectors. Each of the $k$ blocks
$\bm{\mathbf{H}}\in\mathbb{R}^{d/k\times n/k}$ are identical, with
$n/k=2^{d/k}$, and has columns consisting of all vectors $\\{-1,1\\}^{d/k}$,
in some fixed order.

######  Lemma 5.

The matrix $\bm{\mathbf{G}}_{\mathsf{sparse}}$ invertibly maps
$\mathcal{S}_{n,k}$ to $\\{-1,1\\}^{d}$.

###### Proof.

Observe that $|\mathcal{S}_{n,k}|=(n/k)^{k}=2^{d}=|\\{-1,1\\}^{d}|$, so it
suffices to show that $\bm{\mathbf{G}}_{\mathsf{sparse}}$ is surjective. Let
$\bm{\mathbf{z}}\in\\{-1,1\\}^{d}$. Breaking $\bm{\mathbf{z}}$ up into $k$
contiguous blocks of $d/k$ coordinates, we can identify each block of
$\bm{\mathbf{z}}$ in $\\{-1,1\\}^{d/k}$ with a unique column in
$\bm{\mathbf{H}}$. Let $\bm{\mathbf{v}}\in\mathcal{S}_{n,k}$ be defined so
that for the $i$th block, $v_{ik+j}=1$ if and only if the $j$th column of
$\bm{\mathbf{H}}$ is equal to the $i$th part of $\bm{\mathbf{z}}$. It then
follows that
$\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{v}}=\bm{\mathbf{z}}$, as
desired. ∎

We now define a different gadget matrix,
$\bm{\mathbf{G}}_{\mathsf{partite}}\in\mathbb{R}^{k\times n}$, that will help
enforce the regression vector to be partite and binary. The matrix
$\bm{\mathbf{G}}_{\mathsf{partite}}$ is once again block diagonal with $k$
identical blocks, where each block is now the vector
$\mathbf{1}^{\top}\in\mathbb{R}^{1\times n/k}$.

######  Lemma 6.

For $\bm{\mathbf{v}}\in\mathbb{R}^{n}$, we have
$\bm{\mathbf{v}}\in\mathcal{S}_{n,k}$ if and only if
$\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{v}}=\mathbf{1}$ and
$\bm{\mathbf{v}}$ is $k$-sparse.

###### Proof.

For the “only if” direction, observe that
$\bm{\mathbf{v}}\in\mathcal{S}_{n,k}$ directly implies that $\bm{\mathbf{v}}$
is $k$-sparse and
$\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{v}}=\mathbf{1}$, as each part
of $\bm{\mathbf{v}}$ sums to $1$.

For the “if” direction, suppose
$\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{v}}=\mathbf{1}$ and
$\bm{\mathbf{v}}$ is $k$-sparse. We need to show that $\bm{\mathbf{v}}$ is
both _partite_ and _binary_. To see that $\bm{\mathbf{v}}$ is partite, observe
that the condition
$\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{v}}=\mathbf{1}$ enforces the
sum of the entrices of $\bm{\mathbf{v}}$ in each of the $k$ blocks to be $1$.
Therefore, each block has at least one non-zero entry, as otherwise that block
would sum to $0$. Since each of the $k$ blocks has at least one non-zero
entry, by sparsity, each block has exactly one non-zero entry, as otherwise,
$\bm{\mathbf{v}}$ would not be $k$-sparse. Since each block has exactly one
non-zero entry that sums to $1$, that entry must be $1$. Therefore,
$\bm{\mathbf{v}}\in\mathcal{S}_{n,k}$. ∎

Now, we prove the main theorem of this section, Theorem 4.

###### Proof of Theorem 4.

Let
$(\bm{\mathbf{B}},\bm{\mathbf{t}}:=\bm{\mathbf{B}}\bm{\mathbf{z}}+\bm{\mathbf{e}})$
be our $\mathsf{BinaryBDD}_{d,\alpha}$ instance, where
$\bm{\mathbf{B}}\in\mathbb{R}^{d\times d}$, $\bm{\mathbf{z}}\in\\{-1,1\\}^{d}$
and
$\lVert\bm{\mathbf{e}}\rVert_{2}\leq\alpha\cdot\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})$.
Let $\bm{\mathbf{R}}\in\mathbb{R}^{m_{1}\times d}$ be a random matrix where
each entry is drawn $\mathrm{i.i.d.}$ from $\mathcal{N}(0,1)$. We assume we
know a value $\widehat{\lambda}_{1}$ such that
$\widehat{\lambda}_{1}\in[\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}}),2\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}}))$.
(By Lemma 1, doubling search over $\widehat{\lambda}_{1}$ and taking the best
$\mathsf{BinaryBDD}$ solution will take at most polynomial time.)

Our design matrix $\bm{\mathbf{X}}$ and target vector $\bm{\mathbf{y}}$ for
$k$-$\mathsf{SLR}$ will be defined as follows:

$\bm{\mathbf{X}}=\begin{pmatrix}\bm{\mathbf{X}}_{1}\\\
\bm{\mathbf{X}}_{2}\end{pmatrix}=\begin{pmatrix}\bm{\mathbf{R}}\bm{\mathbf{B}}\bm{\mathbf{G}}_{\mathsf{sparse}}\\\
\gamma\bm{\mathbf{G}}_{\mathsf{partite}}\end{pmatrix}\in\mathbb{R}^{(m_{1}+k)\times
n},\ \ \ \ \bm{\mathbf{y}}=\begin{pmatrix}\bm{\mathbf{R}}\bm{\mathbf{t}}\\\
\gamma\mathbf{1}\end{pmatrix}\in\mathbb{R}^{m_{1}+k}.$

Here, $\gamma\in\mathbb{R}$ is a scalar that will be set later. We define
$m_{1}$ so that $m_{1}+k=m$, which implies that $m_{1}=m-k\geq m-d\geq 16d$.
We define the scalar $\delta$ for the $k$-$\mathsf{SLR}$ instance so that

$\delta^{2}=\frac{3m_{1}\cdot\widehat{\lambda}_{1}^{2}}{100m}=\Theta\left(\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})^{2}\right).$
(1)

Invoking the $k$-$\mathsf{SLR}$ solver on the instance
$(\bm{\mathbf{X}},\bm{\mathbf{y}})$ with parameter $\delta$, our reduction
will get a solution $\bm{\mathbf{\widehat{\theta}}}$ such that

$\frac{\lVert\bm{\mathbf{X}}\bm{\mathbf{\widehat{\theta}}}-\bm{\mathbf{y}}\rVert_{2}^{2}}{m}\leq\delta^{2}.$
(2)

Next, we round $\bm{\mathbf{\widehat{\theta}}}$ to the nearest integer
entrywise to get
$\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\in\mathbb{Z}^{n}$, and we
output
$\bm{\mathbf{G}}_{\mathsf{sparse}}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\in\mathbb{Z}^{d}$
as the $\mathsf{BinaryBDD}_{d,\alpha}$ solution.

First, we show completeness, in the sense that there exists $k$-sparse
$\bm{\mathbf{\widehat{\theta}}}\in\mathbb{R}^{n}$ such that (2) is satisfied.
Recall from Lemma 5 that there exists a unique
$\bm{\mathbf{\theta}}^{*}\in\mathcal{S}_{n,k}$ such that
$\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\theta}}^{*}=\bm{\mathbf{z}}$.
We will show that setting
$\bm{\mathbf{\widehat{\theta}}}=\bm{\mathbf{\theta}}^{*}$ satisfies (2). We
have

$\bm{\mathbf{X}}\bm{\mathbf{\theta}}^{*}-\bm{\mathbf{y}}=\begin{pmatrix}\bm{\mathbf{R}}\bm{\mathbf{B}}\bm{\mathbf{G}}_{\mathsf{sparse}}\\\
\gamma\bm{\mathbf{G}}_{\mathsf{partite}}\end{pmatrix}\bm{\mathbf{\theta}}^{*}-\begin{pmatrix}\bm{\mathbf{R}}\bm{\mathbf{t}}\\\
\gamma\mathbf{1}\end{pmatrix}=\begin{pmatrix}\bm{\mathbf{R}}\bm{\mathbf{B}}\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\theta}}^{*}-\bm{\mathbf{R}}\bm{\mathbf{t}}\\\
\gamma\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{\theta}}^{*}-\gamma\mathbf{1}\end{pmatrix}=\begin{pmatrix}\bm{\mathbf{R}}\bm{\mathbf{B}}\bm{\mathbf{z}}-\bm{\mathbf{R}}\bm{\mathbf{t}}\\\
\mathbf{0}\end{pmatrix},$

where the last equality holds by Lemma 6 and definition of
$\bm{\mathbf{\theta}}^{*}$. Continuing the equality, we have

$\bm{\mathbf{X}}\bm{\mathbf{\theta}}^{*}-\bm{\mathbf{y}}=\begin{pmatrix}\bm{\mathbf{R}}\bm{\mathbf{B}}\bm{\mathbf{z}}-\bm{\mathbf{R}}(\bm{\mathbf{B}}\bm{\mathbf{z}}+\bm{\mathbf{e}})\\\
\mathbf{0}\end{pmatrix}=\begin{pmatrix}-\bm{\mathbf{R}}\bm{\mathbf{e}}\\\
\mathbf{0}\end{pmatrix},$

which implies
$\lVert\bm{\mathbf{X}}\bm{\mathbf{\widehat{\theta}}}-\bm{\mathbf{y}}\rVert_{2}^{2}=\lVert\bm{\mathbf{R}}\bm{\mathbf{e}}\rVert_{2}^{2}$.
Since $\bm{\mathbf{R}}$ was sampled independently of $\bm{\mathbf{e}}$,
observe that
$\lVert\bm{\mathbf{R}}\bm{\mathbf{e}}\rVert_{2}^{2}\sim\lVert\bm{\mathbf{e}}\rVert_{2}^{2}\cdot\chi^{2}(m_{1})$.
By Lemma 3, it follows that

$\Pr\left[\lVert\bm{\mathbf{R}}\bm{\mathbf{e}}\rVert_{2}^{2}\geq
5m_{1}/2\cdot\lVert\bm{\mathbf{e}}\rVert_{2}^{2}\right]\leq e^{-m_{1}/4}.$

Therefore, with probability at least $1-e^{-m_{1}/4}$, we have

$\frac{\lVert\bm{\mathbf{X}}\bm{\mathbf{\widehat{\theta}}}-\bm{\mathbf{y}}\rVert_{2}^{2}}{m}\leq\frac{5m_{1}\lVert\bm{\mathbf{e}}\rVert_{2}^{2}}{2m}\leq\frac{5m_{1}\alpha^{2}\cdot\widehat{\lambda}_{1}^{2}}{2m}<\delta^{2},$

since $\alpha\leq 1/10$, as desired, showing that (2) is satisfied.

We now show soundness, which we will prove by contradiction. Suppose that
$\bm{\mathbf{G}}_{\mathsf{sparse}}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})=\bm{\mathbf{z}}^{\prime}$
for some $\bm{\mathbf{z}}^{\prime}\neq\bm{\mathbf{z}}$ and (2) holds. Since
(2) holds, in particular, we know
$\lVert\gamma\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{\widehat{\theta}}}-\gamma\mathbf{1}\rVert_{2}^{2}\leq
m\delta^{2}$, or equivalently,

$\lVert\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{\widehat{\theta}}}-\mathbf{1}\rVert_{2}\leq\sqrt{m}\delta/\gamma.$

Throughout, assume we set $\gamma$ so that $\sqrt{m}\delta/\gamma<1/2$. Each
part of $\bm{\mathbf{\widehat{\theta}}}$ must have exactly one non-zero entry,
as $\bm{\mathbf{\widehat{\theta}}}$ is $k$-sparse and cannot have any part
with all zero entries. Moreover, we know this non-zero entry must be in
$[1-\sqrt{m}\delta/\gamma,1+\sqrt{m}\delta/\gamma]$, so by a choice of
$\gamma$ such that $\sqrt{m}\delta/\gamma<1/2$, this entry must round to $1$.
Therefore,
$\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\in\mathcal{S}_{n,k}$, and
$\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})$ and
$\bm{\mathbf{\widehat{\theta}}}$ have the same support. This implies that
$\bm{\mathbf{z}}^{\prime}=\bm{\mathbf{G}}_{\mathsf{sparse}}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\in\\{-1,1\\}^{d}$
and
$\bm{\mathbf{G}}_{\mathsf{partite}}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})=\mathbf{1}$
by Lemma 6. Moreover, since we can restrict to the support of
$\bm{\mathbf{\widehat{\theta}}}$, we have

$\left\lVert\bm{\mathbf{\widehat{\theta}}}-\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\right\rVert_{2}=\left\lVert\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{\widehat{\theta}}}-\bm{\mathbf{G}}_{\mathsf{partite}}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\right\rVert_{2}=\left\lVert\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{\widehat{\theta}}}-\mathbf{1}\right\rVert_{2}\leq\sqrt{m}\delta/\gamma.$

Since
$\bm{\mathbf{\widehat{\theta}}}-\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})$
is also $k$-sparse and partite, it follows that

$\left\lVert\bm{\mathbf{G}}_{\mathsf{sparse}}\left(\bm{\mathbf{\widehat{\theta}}}-\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\right)\right\rVert_{2}\leq\frac{\delta\sqrt{dm}}{\gamma\sqrt{k}},$

as each column of any block of $\bm{\mathbf{G}}_{\mathsf{sparse}}$ has
$\ell_{2}$ norm exactly $\sqrt{d/k}$. Multiplying on the left by
$\bm{\mathbf{B}}$, we have

$\left\lVert\bm{\mathbf{B}}\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\widehat{\theta}}}-\bm{\mathbf{B}}\bm{\mathbf{z}}^{\prime}\right\rVert_{2}\leq\sigma_{\max}(\bm{\mathbf{B}})\cdot\left\lVert\bm{\mathbf{G}}_{\mathsf{sparse}}\left(\bm{\mathbf{\widehat{\theta}}}-\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\right)\right\rVert_{2}\leq\frac{\sigma_{\max}(\bm{\mathbf{B}})\cdot\delta\sqrt{dm}}{\gamma\sqrt{k}}.$
(3)

On the other hand, by definition of
$\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})$, since
$\bm{\mathbf{z}}\neq\bm{\mathbf{z}}^{\prime}\in\\{-1,1\\}^{d}$, we know

$\lVert\bm{\mathbf{B}}\bm{\mathbf{z}}-\bm{\mathbf{B}}\bm{\mathbf{z}}^{\prime}\rVert_{2}\geq\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}}).$
(4)

By combining (3) and (4) by the triangle inequality, we have

$\left\lVert\bm{\mathbf{B}}\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\widehat{\theta}}}-\bm{\mathbf{B}}\bm{\mathbf{z}}\right\rVert_{2}\geq\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})-\frac{\sigma_{\max}(\bm{\mathbf{B}})\cdot\delta\sqrt{dm}}{\gamma\sqrt{k}}.$

We now set

$\gamma=\max\left(3\delta\sqrt{m},\frac{100\cdot\sigma_{\max}(\bm{\mathbf{B}})\cdot\delta\sqrt{dm}}{\sqrt{k}\cdot\widehat{\lambda}_{1}}\right)=\Theta\left(\frac{\sigma_{\max}(\bm{\mathbf{B}})\cdot\sqrt{dm}}{\sqrt{k}}\right),$
(5)

so that

$\left\lVert\bm{\mathbf{B}}\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\widehat{\theta}}}-\bm{\mathbf{B}}\bm{\mathbf{z}}\right\rVert_{2}\geq\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})-\frac{\widehat{\lambda}_{1}}{100}\geq\frac{49}{50}\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}}).$

(We remark that $\gamma$ is efficiently computable because
$\sigma_{\max}(\bm{\mathbf{B}})$ is efficiently computable and we assume
$\widehat{\lambda}_{1}$ is known.) By incorporating the error
$\bm{\mathbf{e}}$ and multiplication on the left by $\bm{\mathbf{R}}$, we have

$\lVert\bm{\mathbf{X}}\bm{\mathbf{\widehat{\theta}}}-\bm{\mathbf{y}}\rVert_{2}\geq\left\lVert\bm{\mathbf{R}}\bm{\mathbf{B}}\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\widehat{\theta}}}-\bm{\mathbf{R}}\left(\bm{\mathbf{B}}\bm{\mathbf{z}}+\bm{\mathbf{e}}\right)\right\rVert_{2}\geq\sigma_{\min}(\bm{\mathbf{R}})\left(\frac{49}{50}\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})-\lVert\bm{\mathbf{e}}\rVert_{2}\right).$

By combining this inequality with (2), we get a contradiction as long as

$\delta\sqrt{m}\leq\sigma_{\min}(\bm{\mathbf{R}})\left(\frac{49}{50}\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})-\lVert\bm{\mathbf{e}}\rVert_{2}\right).$
(6)

By Lemma 2, we know $\sigma_{\min}(\bm{\mathbf{R}})\geq\sqrt{m_{1}}/2$ with
probability at least $1-2e^{-m_{1}/32}$, and since we also know
$\lVert\bm{\mathbf{e}}\rVert_{2}\leq\alpha\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})$,
we have

$\sigma_{\min}(\bm{\mathbf{R}})\left(\frac{49}{50}\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})-\lVert\bm{\mathbf{e}}\rVert_{2}\right)\geq\frac{\sqrt{m_{1}}}{2}\left(\frac{49}{50}\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})-\alpha\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})\right)=\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})\sqrt{m_{1}}\left(\frac{49}{100}-\frac{\alpha}{2}\right).$

On the other hand, we know

$\delta\sqrt{m}=\frac{\widehat{\lambda}_{1}\sqrt{3m_{1}}}{10\sqrt{m}}\cdot\sqrt{m}\leq\frac{1}{5}\cdot\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})\sqrt{3m_{1}}.$

Combining these inequalities, we get a contradiction if

$\frac{\sqrt{3}}{5}\leq\frac{49}{100}-\frac{\alpha}{2},$

which indeed holds if $\alpha\leq 1/10$. ∎

##  4 Performance of Lasso on Our $k$-$\mathsf{SLR}$ Instances

###  4.1 Normalizing Our $k$-$\mathsf{SLR}$ Instances

First, we follow the convention of Negahban et al. [NRWY12] and normalize our
design matrices according to Definition 4.

######  Lemma 7.

Let $\bm{\mathbf{X}}\in\mathbb{R}^{m\times n}$ denote the design matrix we
obtain in Theorem 4. Let $Z=\Theta(\sigma_{\max}(\mathbf{B})\cdot\sqrt{d/k})$
be a real number. Then, with probability at least $1-e^{-\Omega(m_{1})}$,
$\widetilde{\bm{\mathbf{X}}}:=\frac{1}{Z}\cdot\bm{\mathbf{X}}$ is column-
normalized, and so

$\max_{\begin{subarray}{c}\lVert\bm{\mathbf{v}}\rVert_{2}=1,\\\
\lVert\bm{\mathbf{v}}\rVert_{0}\leq
2k\end{subarray}}\lVert\bm{\mathbf{X}}\bm{\mathbf{v}}\rVert_{2}\leq\Theta\left(\sigma_{\max}(\bm{\mathbf{B}})\sqrt{dm}\right)$
(7)

###### Proof.

For our instance $\bm{\mathbf{X}}$, we have

$\left\lVert\mathsf{col}_{i}(\bm{\mathbf{X}})\right\rVert_{2}^{2}=\left\lVert\mathsf{col}_{i}(\bm{\mathbf{X}}_{1})\right\rVert_{2}^{2}+\left\lVert\mathsf{col}_{i}(\bm{\mathbf{X}}_{2})\right\rVert_{2}^{2}=\left\lVert\mathsf{col}_{i}(\bm{\mathbf{X}}_{1})\right\rVert_{2}^{2}+\gamma^{2}.$

Moreover,

$\displaystyle\left\lVert\mathsf{col}_{i}(\bm{\mathbf{X}}_{1})\right\rVert_{2}=\left\lVert\mathsf{col}_{i}(\bm{\mathbf{R}}\bm{\mathbf{B}}\bm{\mathbf{G}}_{\mathsf{sparse}})\right\rVert_{2}$
$\displaystyle=\left\lVert\bm{\mathbf{R}}\bm{\mathbf{B}}\mathsf{col}_{i}(\bm{\mathbf{G}}_{\mathsf{sparse}})\right\rVert_{2}$
$\displaystyle\leq\sigma_{\max}(\bm{\mathbf{R}})\cdot\sigma_{\max}(\bm{\mathbf{B}})\cdot\left\lVert\mathsf{col}_{i}(\bm{\mathbf{G}}_{\mathsf{sparse}})\right\rVert_{2}$
$\displaystyle=O\left(\sqrt{m_{1}}\cdot\sigma_{\max}(\bm{\mathbf{B}})\cdot\sqrt{d/k}\right),$

with probability at least $1-e^{-\Omega(m_{1})}$ over $\bm{\mathbf{R}}$ by
Lemma 2. Since our setting of $\gamma$ (Equation (5)) matches this up to
constant factors, we have

$\left\lVert\mathsf{col}_{i}(\bm{\mathbf{X}})\right\rVert_{2}=O\left(\sqrt{m}\cdot\sigma_{\max}(\bm{\mathbf{B}})\cdot\sqrt{d/k}\right).$

Therefore, we can set a normalization factor
$Z=\Theta(\sigma_{\max}(\bm{\mathbf{B}})\cdot\sqrt{d/k})$ such that

$\widetilde{\bm{\mathbf{X}}}:=\frac{1}{Z}\cdot\bm{\mathbf{X}}$

is column-normalized. In particular, note that $\widetilde{\bm{\mathbf{X}}}$
is scale invariant with respect to $\bm{\mathbf{B}}$. By Lemma 4, we get that

$\displaystyle\max_{\begin{subarray}{c}\lVert\bm{\mathbf{v}}\rVert_{2}=1,\\\
\lVert\bm{\mathbf{v}}\rVert_{0}\leq
2k\end{subarray}}\lVert\bm{\mathbf{X}}\bm{\mathbf{v}}\rVert_{2}=Z\cdot\max_{\begin{subarray}{c}\lVert\bm{\mathbf{v}}\rVert_{2}=1,\\\
\lVert\bm{\mathbf{v}}\rVert_{0}\leq
2k\end{subarray}}\lVert\widetilde{\bm{\mathbf{X}}}\bm{\mathbf{v}}\rVert_{2}\leq
Z\cdot\sqrt{2km}=\Theta\left(\sigma_{\max}(\bm{\mathbf{B}})\sqrt{dm}\right)$

∎

###  4.2 Restricted Eigenvalue Condition

Now, we prove the lower bound on the restricted eigenvalues of the (column-
normalized) design matrices of our $k$-$\mathsf{SLR}$ instances.

######  Lemma 8.

Suppose $d\geq 3k$. For a setting of $\epsilon=\Theta(k/d)$,
$\widetilde{\bm{\mathbf{X}}}$ satisfies the $(\zeta,\epsilon)$-restricted
eigenvalue condition for all $k$-sparse, $k$-partite $S\subseteq[n]$ for some

$\displaystyle\zeta$
$\displaystyle=\Theta\left(\frac{k}{d^{4}\cdot\kappa(\bm{\mathbf{B}})^{2}}\right),$

with probability at least $1-e^{-\Omega(m)}$.

###### Proof of Lemma 8.

For simplicity, we will show that the unnormalized design matrix
$\bm{\mathbf{X}}=Z\cdot\widetilde{\bm{\mathbf{X}}}$ has the property that for
all $k$-sparse, $k$-partite $S\subset[n]$, and for all
$\bm{\mathbf{\theta}}\in\mathbb{C}_{\epsilon}(S)$,

$\displaystyle\frac{\|\bm{\mathbf{X}}\bm{\mathbf{\theta}}\|_{2}^{2}}{m\cdot\|\bm{\mathbf{\theta}}\|_{2}^{2}}\geq\zeta^{\prime}.$

We will then set $\zeta=\zeta^{\prime}/Z^{2}$ to get the final bound.

Suppose for the sake of contradiction that there exists
$\bm{\mathbf{\theta}}\in\mathbb{C}_{\epsilon}(S)$ such that

$\frac{\lVert\bm{\mathbf{X}}\bm{\mathbf{\theta}}\rVert_{2}^{2}}{m\cdot\lVert\bm{\mathbf{\theta}}\rVert_{2}^{2}}<\zeta^{\prime}.$

Without loss of generality, we can scale $\bm{\mathbf{\theta}}$ so that
$\lVert\bm{\mathbf{\theta}}\rVert_{1}=1$. In particular, observe that
$\lVert\bm{\mathbf{\theta}}\rVert_{2}^{2}\leq\lVert\bm{\mathbf{\theta}}\rVert_{1}^{2}=1$.
We have

$\displaystyle\zeta^{\prime}>\frac{\|\bm{\mathbf{X}}\bm{\mathbf{\theta}}\|_{2}^{2}}{m\cdot\|\bm{\mathbf{\theta}}\|_{2}^{2}}$
$\displaystyle=\frac{\|\bm{\mathbf{R}}\bm{\mathbf{B}}\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\theta}}\|_{2}^{2}+\|\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{\theta}}\|_{2}^{2}}{m\cdot\|\bm{\mathbf{\theta}}\|_{2}^{2}}$
$\displaystyle\geq\frac{1}{m}\left(\sigma_{\min}(\bm{\mathbf{R}}\bm{\mathbf{B}})^{2}\|\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\theta}}\|_{2}^{2}+\|\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{\theta}}\|_{2}^{2}\right).$

If
$\|\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{\theta}}\|_{2}^{2}\geq\zeta^{\prime}m$,
we have arrived at a contradiction. Otherwise, we will show that
$\|\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\theta}}\|_{2}^{2}\geq\zeta^{\prime}m/\sigma_{\min}(\bm{\mathbf{R}}\bm{\mathbf{B}})^{2}$,
which would also be a contradiction. Indeed, since
$\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\theta}}\in\mathbb{R}^{d}$, we
know
$\lVert\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\theta}}\rVert_{2}\sqrt{d}\geq\lVert\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\theta}}\rVert_{1}$,
so it suffices to show that
$\|\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\theta}}\|_{1}\geq\tau_{1}$,
where we define

$\displaystyle\tau_{1}:=\frac{\sqrt{\zeta^{\prime}dm}}{\sigma_{\min}(\bm{\mathbf{R}}\bm{\mathbf{B}})}.$

Since $\bm{\mathbf{\theta}}\in\mathbb{C}_{\epsilon}(S)$ for some $k$-partite
$k$-sparse $S\subseteq[n]$, we can write
$\bm{\mathbf{\theta}}=\bm{\mathbf{\theta}}_{S}+\bm{\mathbf{\theta}}_{\bar{S}}$
such that
$\|\bm{\mathbf{\theta}}_{\bar{S}}\|_{1}\leq(1+\epsilon)\|\bm{\mathbf{\theta}}_{S}\|_{1}$.
Let $\eta^{(i)}\in\mathbb{R}$ be the $i$th nonzero entry of
$\bm{\mathbf{\theta}}_{S}$, and let
$\bm{\mathbf{\bar{\eta}}}^{(i)}\in\mathbb{R}^{n/k}$ be the $i$th part of
$\bm{\mathbf{\theta}}_{\bar{S}}$. Note that without loss of generality, we can
assume that all the entries of $\bm{\mathbf{\theta}}_{S}$ are non-negative,
that is, for all $i$, $\eta^{(i)}\geq 0$. If not, suppose $\eta^{(i)}<0$ for
some $i\in[k]$. Because of the block diagonal structure of
$\bm{\mathbf{G}}_{\mathsf{sparse}}$, we can simply negate the $i$th part of
$\bm{\mathbf{\theta}}$ so that none of the norms change.

By applying Lemma 9 to the $\ell_{1}$ norm of the parts of
$\bm{\mathbf{\theta}}_{S}$ and $\bm{\mathbf{\theta}}_{\bar{S}}$, we know that
there is some part $i\in[k]$ such that $\eta^{(i)}\geq\epsilon/k$ and
$\|\bm{\mathbf{\bar{\eta}}}^{(i)}\|_{1}\leq(1+10\epsilon)\eta^{(i)}$. We will
consider this part $i$, and we will write $\eta,\bm{\mathbf{\bar{\eta}}}$
instead of $\eta^{(i)},\bm{\mathbf{\bar{\eta}}}^{(i)}$ for simplicity, i.e.,

$\displaystyle\sum_{j}|\bar{\eta}_{j}|=\|\bm{\mathbf{\bar{\eta}}}\|_{1}\leq(1+10\epsilon)\eta.$
(8)

We will provide a lower bound on
$\|\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\theta}}\|_{1}$ considering
only the $i$th part. Since
$\|\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{\theta}}\|_{2}\leq\sqrt{\zeta^{\prime}m}$,

$\displaystyle\eta+\sum_{j}\bar{\eta}_{j}\leq\left|\eta+\sum_{j}\bar{\eta}_{j}\right|$
$\displaystyle\leq\frac{1}{\gamma}\|\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{\theta}}\|_{2}\leq\frac{\sqrt{\zeta^{\prime}m}}{\gamma}.$
(9)

Adding (8) and (9), we get an upper bound on the sum of the positive entries
in $\bm{\mathbf{\bar{\eta}}}$:

$\displaystyle\sum_{j}\bar{\eta}_{j}\cdot\mathbbm{1}[\bar{\eta}_{j}>0]\leq\frac{\sqrt{\zeta^{\prime}m}}{2\gamma}+5\epsilon\eta.$
(10)

Let $\bm{\mathbf{H}}\in\\{-1,1\\}^{d/k\times 2^{d/k}}$ be a block in
$\bm{\mathbf{G}}_{\mathsf{sparse}}$, i.e., whose columns are all of the
vectors in $\\{-1,1\\}^{d/k}$. Let $\bm{\mathbf{h}}^{(j)}$ denote the $j$th
column of $\bm{\mathbf{H}}$. Without loss of generality, we can choose the
location of the $\eta$ entry within the block so that it corresponds to the
column $\mathbf{1}\in\mathbb{R}^{d/k}$. To see this, if not, we can flip the
sign of the rows of $\bm{\mathbf{H}}$ that correspond to $-1$ entries in the
column corresponding to $\eta$. This has the effect of permuting the columns
of $\bm{\mathbf{H}}$ and has no effect on
$\lVert\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\theta}}\rVert_{1}$ or
$\lVert\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{\theta}}\rVert_{2}$ as
the entries just flip sign. We will use the convention that first column of
$\bm{\mathbf{H}}$ is $\mathbf{1}$. By considering only part $i$, we have the
inequality

$\lVert\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\theta}}\rVert_{1}\geq\left\lVert\eta\mathbf{1}+\sum_{j=2}^{2^{d/k}}\bar{\eta}_{j}\bm{\mathbf{h}}^{(j)}\right\rVert_{1}\geq\sum_{\ell=1}^{d/k}\left(\eta+\sum_{j=2}^{2^{d/k}}\bar{\eta}_{j}h^{(j)}_{\ell}\right)=\frac{\eta
d}{k}+\sum_{j=2}^{2^{d/k}}\bar{\eta}_{j}\sum_{\ell=1}^{d/k}h^{(j)}_{\ell}.$
(11)

Since $\bm{\mathbf{h}}^{(j)}\neq\mathbf{1}$ for all $j\geq 2$, we know for all
$j\geq 2$,

$\sum_{\ell=1}^{d/k}h^{(j)}_{\ell}\leq\frac{d}{k}-2,$

as at least one entry in $\bm{\mathbf{h}}^{(j)}$ is $-1$. This bound is
helpful only when $\bar{\eta}_{j}<0$, as this will let us lower bound
$\lVert\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\theta}}\rVert_{1}$.
Thankfully, (10) gives us a bound on the sum of the positive $\bar{\eta}_{j}$
contributions, in which case we use the trivial bound

$\sum_{\ell=1}^{d/k}h^{(j)}_{\ell}\geq-\frac{d}{k}.$

Let $J_{+},J_{-}\subseteq[2^{d/k}]\setminus\\{1\\}$ denote the set of columns
$j$ where $\bar{\eta}_{j}\geq 0$ and $\bar{\eta}_{j}<0$, respectively.
Combining the above bounds with (11), we have

$\displaystyle\lVert\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\theta}}\rVert_{1}\geq\frac{\eta
d}{k}+\sum_{j=2}^{2^{d/k}}\bar{\eta}_{j}\sum_{\ell=1}^{d/k}$
$\displaystyle=\frac{\eta d}{k}+\sum_{j\in
J_{+}}\bar{\eta}_{j}\sum_{\ell=1}^{d/k}h^{(j)}_{\ell}+\sum_{j\in
J_{-}}\bar{\eta}_{j}\sum_{\ell=1}^{d/k}h^{(j)}_{\ell}$ (12)
$\displaystyle\geq\frac{\eta d}{k}-\frac{d}{k}\sum_{j\in
J_{+}}\bar{\eta}_{j}-\left(\frac{d}{k}-2\right)\left|\sum_{j\in
J_{-}}\bar{\eta}_{j}\right|$ (13) $\displaystyle\geq\frac{\eta
d}{k}-\frac{d}{k}\left(\frac{\sqrt{\zeta^{\prime}m}}{2\gamma}+5\epsilon\eta\right)-\left(\frac{d}{k}-2\right)\sum_{j=2}^{2^{d/k}}\left|\bar{\eta}_{j}\right|$
(14) $\displaystyle\geq\frac{\eta
d}{k}-\frac{d}{k}\left(\frac{\sqrt{\zeta^{\prime}m}}{2\gamma}+5\epsilon\eta\right)-\left(\frac{d}{k}-2\right)(1+10\epsilon)\eta,$
(15)

where the penultimate inequality comes from (10), and the last inequality
comes from (8). We now bound the remaining terms. Setting

$\epsilon:=\frac{k}{50d},$

and assuming

$\gamma\geq\frac{5d\sqrt{\zeta^{\prime}m}}{\eta k},$ (16)

we have the guarantee that

$\frac{\sqrt{\zeta^{\prime}m}}{2\gamma}+5\epsilon\eta\leq\frac{\eta
k}{10d}+\frac{\eta k}{10d}=\frac{\eta k}{5d}.$

Furthermore, our setting of $\epsilon$ guarantees

$\left(\frac{d}{k}-2\right)(1+10\epsilon)=\frac{d}{k}-\frac{9}{5}-\frac{2k}{5d}<\frac{d}{k}-1.$

Plugging these into (15), we have

$\displaystyle\lVert\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\theta}}\rVert_{1}$
$\displaystyle\geq\frac{\eta
d}{k}-\frac{d}{k}\left(\frac{\sqrt{\zeta^{\prime}m}}{2\gamma}+5\epsilon\eta\right)-\left(\frac{d}{k}-2\right)(1+10\epsilon)\eta$
$\displaystyle\geq\frac{\eta d}{k}-\frac{d}{k}\cdot\frac{\eta
k}{5d}-\left(\frac{d}{k}-1\right)\eta$
$\displaystyle=\frac{4}{5}\eta\geq\frac{4\epsilon}{5k}=\frac{2}{125d},$

where the last inequality comes from our application of Lemma 9, which implies
$\eta\geq\epsilon/k$. Recall that we get a contradiction if

$\|\bm{\mathbf{G}}_{\mathsf{sparse}}\bm{\mathbf{\theta}}\|_{1}\geq\tau_{1}:=\frac{\sqrt{\zeta^{\prime}dm}}{\sigma_{\min}(\bm{\mathbf{R}}\bm{\mathbf{B}})}.$

Therefore, setting $\zeta^{\prime}$ so that

$\frac{\sqrt{\zeta^{\prime}dm}}{\sigma_{\min}(\bm{\mathbf{R}}\bm{\mathbf{B}})}<\frac{2}{125d}$

arrives us at a contradiction. Since
$\sigma_{\min}(\bm{\mathbf{R}}\bm{\mathbf{B}})\geq\sigma_{\min}(\bm{\mathbf{R}})\sigma_{\min}(\bm{\mathbf{B}})\geq\sqrt{m_{1}}/2\cdot\sigma_{\min}(\bm{\mathbf{B}})$
with probability at least $1-e^{-\Omega(m_{1})}$ by Lemma 2, it suffices to
set

$\zeta^{\prime}:=\frac{1}{2}\cdot\frac{m_{1}\sigma_{\min}(\bm{\mathbf{B}})^{2}}{125^{2}d^{3}m}=\Theta\left(\frac{\sigma_{\min}(\bm{\mathbf{B}})^{2}}{d^{3}}\right).$

Now, we justify our assumption on $\gamma$ in (16). Recall that our reduction
sets

$\gamma=\Theta\left(\frac{\sigma_{\max}(\bm{\mathbf{B}})\sqrt{dm}}{\sqrt{k}}\right).$

By our setting of $\zeta^{\prime}$ and since $\eta\geq\epsilon/k=1/(50d)$, we
have

$\gamma\gg\frac{\sigma_{\min}(\bm{\mathbf{B}})\sqrt{dm}}{k}\geq\Theta\left(\frac{\sigma_{\min}(\bm{\mathbf{B}})\sqrt{m}}{k\eta\sqrt{d}}\right)=\Theta\left(\frac{d\sqrt{\zeta^{\prime}m}}{\eta
k}\right),$

showing that (16) is indeed satisfied.

Finally, scaling by $Z^{2}$, we have

$\zeta=\frac{\zeta^{\prime}}{Z^{2}}=\Theta\left(\frac{k\cdot\sigma_{\min}(\bm{\mathbf{B}})^{2}}{d^{4}\cdot\sigma_{\max}(\bm{\mathbf{B}})^{2}}\right),$

as desired. ∎

######  Lemma 9.

Suppose $x_{i},y_{i}\in\mathbb{R}_{\geq 0}$ for $i\in[k]$, such that
$\sum_{i=1}^{k}x_{i}+\sum_{i=1}^{k}y_{i}=1$. Further suppose that for some
$\epsilon\in(0,1/20)$,
$\sum_{i=1}^{k}y_{i}\leq(1+\epsilon)\sum_{i=1}^{k}x_{i}$. Then, there is some
$i^{*}\in[k]$ such that $x_{i^{*}}\geq\epsilon/k$ and
$y_{i^{*}}\leq(1+10\epsilon)x_{i^{*}}$.

###### Proof.

Since $\sum_{i=1}^{k}x_{i}+\sum_{i=1}^{k}y_{i}=1$ and
$\sum_{i=1}^{k}y_{i}\leq(1+\epsilon)\sum_{i=1}^{k}x_{i}$, this implies that
$\sum_{i=1}^{k}x_{i}\geq\frac{1}{2+\epsilon}\geq\frac{1}{2}-\epsilon$, and
$\sum_{i=1}^{k}y_{i}\leq\frac{1}{2}+\epsilon$.

Suppose for contradiction that for all $i\in[k]$, either $x_{i}<\epsilon/k$ or
$y_{i}>(1+10\epsilon)x_{i}$. Let $A$ be the set of all $i\in[k]$ such that
$x_{i}<\epsilon/k$, and let $B=[k]\setminus A$. By assumption, for all $i\in
B$, we have that $y_{i}>(1+10\epsilon)x_{i}$. Then, since $\sum_{i\in
A}x_{i}\leq\epsilon$,

$\displaystyle\sum_{i\in B}y_{i}$ $\displaystyle>(1+10\epsilon)\sum_{i\in
B}x_{i}=(1+10\epsilon)\left(\sum_{i\in[k]}x_{i}-\sum_{i\in A}x_{i}\right)$
$\displaystyle\geq(1+10\epsilon)\left(\frac{1}{2}-2\epsilon\right)=\frac{1}{2}+5\epsilon-2\epsilon-20\epsilon^{2}\geq\frac{1}{2}+2\epsilon.$

This is a contradiction, since we also know that $\sum_{i\in
B}y_{i}\leq\sum_{i\in[k]}y_{i}\leq\frac{1}{2}+\epsilon$. ∎

###  4.3 Prediction Error Achieved by Lasso on Our Instances

We now apply Theorem 3 to our instance as generated in Theorem 4, to obtain a
bound on the prediction error achieved by Lasso on our instances. Note that
this is a mean squared prediction error bound as opposed to a mean squared
error bound. To translate Lasso into an algorithm for
$\mathsf{BinaryBDD}_{d,\alpha}$ via the reduction in Theorem 4, we can bound
the mean-squared error by the triangle inequality (see Corollary 1).

######  Lemma 10.

Consider the instances
$(\mathbf{X},\bm{\mathbf{y}},\delta=\Theta(\lambda_{1,\mathsf{bin}}(\mathbf{B}))$
of $k$-$\mathsf{SLR}$ instances obtained in the reduction from a
$\mathsf{BinaryBDD}_{d,\alpha}$ instance $(\mathbf{B},\cdot)$ as in Theorem 4.
On these instances, the thresholded Lasso estimator
$\bm{\mathbf{\theta}}_{\mathsf{TL}}$ can achieve prediction error bounded as

$\displaystyle\frac{1}{m}\lVert\bm{\mathbf{X}}\bm{\mathbf{\widehat{\theta}}}_{\mathsf{TL}}-\bm{\mathbf{X}}\bm{\mathbf{\theta}}^{*}\rVert^{2}_{2}\leq
O\left(\frac{\alpha^{2}\cdot\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})^{2}\cdot\kappa(\bm{\mathbf{B}})^{4}\cdot
d^{10}}{k^{2}}\right).$

###### Proof.

With the goal of applying Theorem 3, we first bound
$\left\lVert\widetilde{\bm{\mathbf{w}}}\right\rVert_{2}$. On our instances, we
have

$\widetilde{\bm{\mathbf{w}}}=\widetilde{\bm{\mathbf{y}}}-\widetilde{\bm{\mathbf{X}}}\bm{\mathbf{\theta}}^{*}=\frac{1}{Z}\begin{pmatrix}\bm{\mathbf{R}}\bm{\mathbf{e}}\\\
\mathbf{0}\end{pmatrix}.$

Therefore,

$\left\lVert\widetilde{\bm{\mathbf{w}}}\right\rVert_{2}=\frac{1}{Z}\lVert\bm{\mathbf{R}}\bm{\mathbf{e}}\rVert_{2}\leq\frac{1}{Z}\sigma_{\max}(\bm{\mathbf{R}})\lVert\bm{\mathbf{e}}\rVert_{2}\leq
O\left(\frac{\alpha\cdot\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})\sqrt{m}}{Z}\right)$

with probability at least $1-e^{-\Omega(m)}$ over $\bm{\mathbf{R}}$ by Lemma
2. Since $Z=\Theta(\sigma_{\max}(\bm{\mathbf{B}})\cdot\sqrt{d/k})$, we have

$\left\lVert\widetilde{\bm{\mathbf{w}}}\right\rVert_{2}\leq
O\left(\frac{\alpha\cdot\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})\sqrt{mk}}{\sigma_{\max}(\mathbf{B})\sqrt{d}}\right).$

With this bound on $\left\lVert\widetilde{\bm{\mathbf{w}}}\right\rVert_{2}$,
we can plug in Lemma 8, which says that for $\epsilon=\Theta(k/d)$,
$\widetilde{\bm{\mathbf{X}}}$ satisfies the $(\zeta,\epsilon)$-restricted
eigenvalue condition for all $k$-sparse, $k$-partite $S\subseteq[n]$ for

$\zeta=\Theta\left(\frac{k}{d^{4}\cdot\kappa(\bm{\mathbf{B}})^{2}}\right).$

Plugging in $\left\lVert\widetilde{\bm{\mathbf{w}}}\right\rVert_{2}$,
$\epsilon$, and $\zeta$ into Theorem 3, we get

$\frac{1}{m}\|\widetilde{\bm{\mathbf{X}}}\widehat{\bm{\mathbf{\theta}}}_{\mathsf{TL}}-\widetilde{\bm{\mathbf{X}}}\bm{\mathbf{\theta}}^{*}\|_{2}^{2}\leq
O\left(\frac{\lVert\widetilde{\bm{\mathbf{w}}}\rVert_{2}^{2}\cdot
k^{2}}{\zeta^{2}\cdot\epsilon^{2}\cdot m}\right)\leq
O\left(\frac{\alpha^{2}\cdot\lambda_{1,\mathsf{bin}}(\mathbf{B})^{2}\cdot\kappa(\mathbf{B})^{4}\cdot
d^{9}}{k\cdot\sigma_{\max}(\mathbf{B})^{2}}\right).$

Scaling up by $Z^{2}=\Theta(\sigma_{\max}(\mathbf{B})^{2}\cdot d/k)$ to
convert back to the unnormalized version, we have

$\frac{1}{m}\|\bm{\mathbf{X}}\widehat{\bm{\mathbf{\theta}}}_{\mathsf{TL}}-\bm{\mathbf{X}}\bm{\mathbf{\theta}}^{*}\|_{2}^{2}\leq
O\left(\frac{\alpha^{2}\cdot\lambda_{1,\mathsf{bin}}(\mathbf{B})^{2}\cdot\kappa(\mathbf{B})^{4}\cdot
d^{10}}{k^{2}}\right),$

as desired.

∎

######  Corollary 1 (Lasso-based Algorithm for
$\mathsf{BinaryBDD}_{d,\alpha}$).

Let $d,k,m$ be integers such that $k$ divides $d$ and $m\geq\Omega(d)$. Let
$\alpha$ be a real number such that

$\displaystyle\alpha\leq
C\cdot\frac{k}{d^{5}\cdot\kappa(\bm{\mathbf{B}})^{2}}$

for some universal constant $C>0$. Then, running the reduction in Theorem 4
and reducing to Lasso as the $k$-$\mathsf{SLR}$ solver gives a
$\operatorname{poly}(m,k\cdot 2^{d/k})$-time reduction from
$\mathsf{BinaryBDD}_{d,\alpha}$ that succeeds with probability at least
$1-e^{-\Omega(m)}$. Setting $k$ and $m$ such that $d=10k$ and $m=100d$, this
becomes a $\operatorname{poly}(d)$ time reduction from
$\mathsf{BinaryBDD}_{d,\alpha}$ to Lasso that succeeds with probability at
least $1-e^{-\Omega(d)}$ as long as

$\displaystyle\alpha\leq
C^{\prime}\cdot\frac{1}{d^{4}\cdot\kappa(\bm{\mathbf{B}})^{2}},$

for some universal constant $C^{\prime}>0$.

###### Proof.

Let
$(\bm{\mathbf{X}},\bm{\mathbf{y}}=\bm{\mathbf{X}}\bm{\mathbf{\theta}}^{*}+\bm{\mathbf{w}},\delta)$
be the $k$-$\mathsf{SLR}$ instance obtained in the reduction in Theorem 4.
Then, if $\widehat{\bm{\mathbf{\theta}}}_{\mathsf{TL}}$ is the solution
obtained via thresholded Lasso, since
$\|\bm{\mathbf{X}}\bm{\mathbf{\theta}}^{*}-\bm{\mathbf{y}}\|^{2}_{2}/m=\|\bm{\mathbf{R}}\bm{\mathbf{e}}\|^{2}_{2}/m\leq
O(\alpha^{2}\cdot\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}}))$ with probability
at least $1-e^{-\Omega(m)}$, by triangle inequality, we have that

$\displaystyle\frac{1}{m}\|\bm{\mathbf{X}}\widehat{\bm{\mathbf{\theta}}}_{\mathsf{TL}}-\bm{\mathbf{y}}\|^{2}_{2}$
$\displaystyle\leq
O\left(\frac{1}{m}\|\bm{\mathbf{X}}\widehat{\bm{\mathbf{\theta}}}_{\mathsf{TL}}-\bm{\mathbf{X}}\bm{\mathbf{\theta}}^{*}\|^{2}_{2}+\frac{1}{m}\|\bm{\mathbf{X}}\bm{\mathbf{\theta}}^{*}-\bm{\mathbf{y}}\|^{2}_{2}\right)$
$\displaystyle\leq
O\left(\alpha^{2}\cdot\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})^{2}\cdot\kappa(\bm{\mathbf{B}})^{4}\cdot\frac{d^{10}}{k^{2}}\right)+O(\alpha^{2}\cdot\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})^{2}).$

Theorem 4 needs a $k$-$\mathsf{SLR}$ solver with
$\delta=\Theta(\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}}))$ by (1), so setting

$\displaystyle\alpha\leq
C\cdot\frac{k}{d^{5}\cdot\kappa(\bm{\mathbf{B}})^{2}}$

for some universal constant $C>0$ suffices for the correctness of the
reduction. This gives us a Lasso-based algorithm for
$\mathsf{BinaryBDD}_{d,\alpha}$ that runs in time
$\operatorname{poly}(m,k\cdot 2^{d/k})$. ∎

######  Remark 3.

We briefly remark that the information-theoretic $k$-$\mathsf{SLR}$ solver
(i.e., by the bound in Proposition 1) would solve our BDD instance for
sufficiently small _constant_ $\alpha$. In particular, if allowed oracle calls
to an information-theoretic $k$-$\mathsf{SLR}$ solver, there would be a
$\operatorname{poly}(d)$-time algorithm for $\mathsf{BinaryBDD}_{d,\alpha}$
for sufficiently small constant $\alpha$.

Finally, we state how a hypothetical improvement to Lasso gives a
corresponding parameter improvement to $\mathsf{BinaryBDD}_{d,\alpha}$.

######  Theorem 5.

Let $d,k,m,n$ be integers such that $k$ divides $d$, $m\geq\Omega(d)$ and
$n=k\cdot 2^{d/k}$. Suppose there is a polynomial-time algorithm that takes
$k$-$\mathsf{SLR}$ instances
$(\widetilde{\bm{\mathbf{X}}},\widetilde{\bm{\mathbf{y}}}=\widetilde{\bm{\mathbf{X}}}\bm{\mathbf{\theta}}^{*}+\widetilde{\bm{\mathbf{w}}})$
with design matrices $\widetilde{\bm{\mathbf{X}}}\in\mathbb{R}^{m\times n}$
that satisfy the $(\zeta,\epsilon)$-restricted eigenvalue condition for
$\operatorname{support}(\bm{\mathbf{\theta}}^{*})$, and outputs a $k$-sparse
vector $\widehat{\bm{\mathbf{\theta}}}$ such that the prediction error is
bounded as

$\displaystyle\frac{1}{m}\|\widetilde{\bm{\mathbf{X}}}\widehat{\bm{\mathbf{\theta}}}-\widetilde{\bm{\mathbf{X}}}\bm{\mathbf{\theta}}^{*}\|_{2}^{2}\leq
O\left(\frac{\|\widetilde{\bm{\mathbf{w}}}\|_{2}^{2}\cdot
k^{2}}{\zeta^{2-\beta}\cdot\epsilon^{2}\cdot m}\right)$

for some constant $\beta\in(0,2]$. Then there is an algorithm that runs in
time $\operatorname{poly}(m,k\cdot 2^{d/k})$ that solves
$\mathsf{BinaryBDD}_{d,\alpha}$ with probability $1-e^{-\Omega(m)}$ on
instances $(\bm{\mathbf{B}},\cdot)$ as long as

$\displaystyle\alpha\leq
C\cdot\frac{k^{1-\beta/2}}{d^{5-2\beta}\cdot\kappa(\bm{\mathbf{B}})^{2-\beta}},$

for some universal constant $C>0$.

###### Proof of Theorem 5.

The proof follows directly by modifying the exponent on $\zeta$ in Lemma 10
and Corollary 1. ∎

##  5 Reduction from CLWE

We now define the continuous learning with errors ($\mathsf{CLWE}$) assumption
as defined by [BRST21], which holds assuming the quantum [BRST21] or classical
[GVV22] hardness of worst-case lattice problems for various parameter regimes.
We define $\mathbb{S}^{m-1}$ to be the unit sphere in $\mathbb{R}^{m}$, i.e.,
the set of all unit vectors in $\mathbb{R}^{m}$ according to the $\ell_{2}$
norm. We write $\bm{\mathbf{v}}\sim\mathbb{S}^{m-1}$ to denote sampling
$\bm{\mathbf{v}}$ from the uniform distribution over the sphere. Furthermore,
for a vector $\bm{\mathbf{v}}\in\mathbb{R}^{n}$, by $\bm{\mathbf{v}}\pmod{1}$,
we mean the representative $\widetilde{\bm{\mathbf{v}}}\in[-1/2,1/2)^{n}$ such
that $\bm{\mathbf{v}}-\widetilde{\bm{\mathbf{v}}}\in\mathbb{Z}^{n}$. Moreover,
by this choice of representative, note that we have $|a\pmod{1}|\leq|a|$ for
all $a\in\mathbb{R}$.

######  Definition 7 (CLWE Assumption [BRST21]).

For a secret vector
$\bm{\mathbf{s}}\sim\gamma_{\mathsf{CLWE}}\cdot\mathbb{S}^{m-1}$ and error
vector $\bm{\mathbf{e}}\sim\mathcal{N}(0,\beta^{2}I_{n\times n})$, we have the
computational indistinguishability

$\left(\bm{\mathbf{A}}\sim\mathcal{N}(0,1)^{m\times
n},\bm{\mathbf{b}}^{\top}:=\bm{\mathbf{s}}^{\top}\bm{\mathbf{A}}+\bm{\mathbf{e}}^{\top}\pmod{1}\right)\approx\left(\bm{\mathbf{A}}\sim\mathcal{N}(0,1)^{m\times
n},\bm{\mathbf{b}}^{\top}\sim[-1/2,1/2)^{m}\right),$

up to constant advantage for algorithms running in time $T$.

This assumption is parameterized by $m,n,\gamma_{\mathsf{CLWE}},\beta$ and
$T$. For example, for the parameter setting $\gamma_{\mathsf{CLWE}}=2\sqrt{m}$
and $\beta=1/\operatorname{poly}(m)$, there are no algorithms known that run
in time $T=2^{o(m)}$ with $n=2^{o(m)}$ samples.

######  Theorem 6.

Suppose $k=m^{\epsilon}$ for some $\epsilon\in(0,1)$. There is a
$\operatorname{poly}(n,m)$-time reduction from $\mathsf{CLWE}$ in dimension
$m$ with $n$ samples and parameters
$\gamma_{\mathsf{CLWE}}=2\sqrt{m},\beta=o(1/\sqrt{k})$ to $k$-$\mathsf{SLR}$,
for $n=k\cdot 2^{\Theta(m/k\cdot\log m)}$. If the $k$-$\mathsf{SLR}$ solver
runs in time $T$, the distinguisher for $\mathsf{CLWE}$ runs in time
$T+\operatorname{poly}(n,m)$. Moreover, the reduction generates design
matrices $\bm{\mathbf{X}}$ that can be decomposed as

$\bm{\mathbf{X}}=\begin{pmatrix}\bm{\mathbf{X}}_{1}\\\
\bm{\mathbf{X}}_{2}\end{pmatrix},$

where the distribution of each row of
$\bm{\mathbf{X}}_{1}\in\mathbb{R}^{m\times n}$ is $\mathrm{i.i.d.}$
$\mathcal{N}(\mathbf{0},I_{n\times n})$, and
$\bm{\mathbf{X}}_{2}\in\mathbb{R}^{k\times n}$ is proportional to a fixed,
instance-independent matrix that depends only on $n$ and $k$.

The interpretations of Section 3.1 also apply here as to how one could remove
the worst-case sub-matrix $\bm{\mathbf{X}}_{2}$.

###### Proof.

We first start with the $\mathsf{CLWE}$ assumption (see Definition 7), which
says that for secret vector
$\bm{\mathbf{s}}\sim\gamma_{\mathsf{CLWE}}\cdot\mathbb{S}^{m-1}$ and error
vector $\bm{\mathbf{e}}\sim\mathcal{N}(0,\beta^{2}I_{n\times n})$, we have the
indistinguishability

$\left(\bm{\mathbf{A}}\sim\mathcal{N}(0,1)^{m\times
n},\bm{\mathbf{b}}^{\top}:=\bm{\mathbf{s}}^{\top}\bm{\mathbf{A}}+\bm{\mathbf{e}}^{\top}\pmod{1}\right)\approx\left(\bm{\mathbf{A}}\sim\mathcal{N}(0,1)^{m\times
n},\bm{\mathbf{b}}^{\top}\sim[-1/2,1/2)^{m}\right).$

We construct our design matrix $\bm{\mathbf{X}}\in\mathbb{R}^{(m+k)\times n}$
and target $\bm{\mathbf{y}}\in\mathbb{R}^{m+k}$ as

$\displaystyle\bm{\mathbf{X}}:=\begin{pmatrix}\bm{\mathbf{A}}\\\
\alpha\bm{\mathbf{G}}_{\mathsf{partite}}\end{pmatrix},\quad\bm{\mathbf{y}}=\begin{pmatrix}\mathbf{0}\\\
\alpha\mathbf{1}\end{pmatrix},$

with parameter

$\delta:=\frac{1}{100\gamma_{\mathsf{CLWE}}\sqrt{m+k}}=\Theta\left(\frac{1}{\gamma_{\mathsf{CLWE}}\sqrt{m+k}}\right).$

For a ($k$-sparse) $k$-$\mathsf{SLR}$ solution
$\bm{\mathbf{\widehat{\theta}}}\in\mathbb{R}^{n}$ to the instance
$(\bm{\mathbf{X}},\bm{\mathbf{y}},\delta)$, we compute
$\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\in\mathbb{Z}^{n}$ and check if

$\left|\bm{\mathbf{b}}^{\top}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\pmod{1}\right|<\frac{1}{4}.$

If so, we output $1$ (indicating $\mathsf{CLWE}$), and otherwise, we output
$0$ (indicating null).

#### Soundness.

To see that we have a distinguisher for $\mathsf{CLWE}$, suppose
$\bm{\mathbf{\widehat{\theta}}}\in\mathbb{R}^{n}$ is a $k$-$\mathsf{SLR}$
solution, i.e.,

$\frac{\lVert\bm{\mathbf{X}}\bm{\mathbf{\widehat{\theta}}}-\bm{\mathbf{y}}\rVert_{2}^{2}}{m+k}\leq\delta^{2}.$
(17)

In particular, we know
$\lVert\alpha\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{\widehat{\theta}}}-\alpha\mathbf{1}\rVert_{2}^{2}\leq(m+k)\delta^{2}=\frac{1}{100^{2}\gamma_{\mathsf{CLWE}}^{2}}$,
or equivalently,

$\lVert\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{\widehat{\theta}}}-\mathbf{1}\rVert_{2}\leq\frac{1}{100\alpha\gamma_{\mathsf{CLWE}}}.$

Throughout, assume we set $\alpha$ so that
$100\alpha\gamma_{\mathsf{CLWE}}>2$. Each part of
$\bm{\mathbf{\widehat{\theta}}}$ must have exactly one non-zero entry, as
$\bm{\mathbf{\widehat{\theta}}}$ is $k$-sparse and cannot have any part with
all zero entries. Moreover, we know this non-zero entry must be in
$[1-1/(100\alpha\gamma_{\mathsf{CLWE}}),1+1/(100\alpha\gamma_{\mathsf{CLWE}})]$,
so this entry must round to $1$. Therefore,
$\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\in\mathcal{S}_{n,k}$, and
$\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})$ and
$\bm{\mathbf{\widehat{\theta}}}$ have the same support. By considering the
support of $\bm{\mathbf{\widehat{\theta}}}$, this implies

$\lVert\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})-\bm{\mathbf{\widehat{\theta}}}\rVert_{2}=\lVert\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{\widehat{\theta}}}-\mathbf{1}\rVert_{2}\leq\frac{1}{100\alpha\gamma_{\mathsf{CLWE}}}.$

Moreover, we will set $\alpha=\max(\sqrt{n},3/(100\gamma_{\mathsf{CLWE}}))$ so
that

$\lVert\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})-\bm{\mathbf{\widehat{\theta}}}\rVert_{2}<\frac{1}{100\gamma_{\mathsf{CLWE}}\sqrt{n}}.$

By (17), we also know

$\lVert\bm{\mathbf{A}}\bm{\mathbf{\widehat{\theta}}}\rVert_{2}\leq\delta\sqrt{m+k}\leq\frac{1}{100\gamma_{\mathsf{CLWE}}}.$

First, suppose we are the non-null case, i.e.,
$\bm{\mathbf{b}}^{\top}=\bm{\mathbf{s}}^{\top}\bm{\mathbf{A}}+\bm{\mathbf{e}}^{\top}$.
Since $\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\in\mathbb{Z}^{n}$, we
then have

$\displaystyle\left|\bm{\mathbf{b}}^{\top}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\pmod{1}\right|$
$\displaystyle=\left|\bm{\mathbf{s}}^{\top}\bm{\mathbf{A}}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})+\bm{\mathbf{e}}^{\top}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\pmod{1}\right|$
$\displaystyle\leq\left|\bm{\mathbf{s}}^{\top}\bm{\mathbf{A}}(\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})-\bm{\mathbf{\widehat{\theta}}})\right|+\left|\bm{\mathbf{s}}^{\top}\bm{\mathbf{A}}\bm{\mathbf{\widehat{\theta}}}\right|+\left|\bm{\mathbf{e}}^{\top}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\right|$
$\displaystyle\leq\lVert\bm{\mathbf{s}}^{\top}\bm{\mathbf{A}}\rVert_{2}\cdot\lVert\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})-\bm{\mathbf{\widehat{\theta}}}\rVert_{2}+\frac{1}{100}+\left|\bm{\mathbf{e}}^{\top}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\right|.$

Since $\bm{\mathbf{X}}$ and $\bm{\mathbf{y}}$ are independent of
$\bm{\mathbf{e}}$, and since
$\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\in\mathcal{S}_{n,k}$, we know
$\bm{\mathbf{e}}^{\top}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\sim\mathcal{N}(0,k\beta^{2})$.
By standard tails bounds on the Gaussian, we have
$|\bm{\mathbf{e}}^{\top}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})|\leq
O(\beta\sqrt{k})$ with probability at least $99/100$. Similarly, since
$\bm{\mathbf{s}}$ and $\bm{\mathbf{A}}$ are independent, we know
$\bm{\mathbf{s}}^{\top}\bm{\mathbf{A}}\sim\mathcal{N}(0,\gamma_{\mathsf{CLWE}}I_{n\times
n})$, so by Lemma 3, we know
$\lVert\bm{\mathbf{s}}^{\top}\bm{\mathbf{A}}\rVert_{2}\leq
10\gamma_{\mathsf{CLWE}}\sqrt{n}$ with probability at least
$1-e^{-\Omega(n)}$. Plugging these into our previous bound, for
$\beta=o(1/\sqrt{k})$,

$\displaystyle\left|\bm{\mathbf{b}}^{\top}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\pmod{1}\right|$
$\displaystyle\leq\lVert\bm{\mathbf{s}}^{\top}\bm{\mathbf{A}}\rVert_{2}\cdot\lVert\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})-\bm{\mathbf{\widehat{\theta}}}\rVert_{2}+\frac{1}{100}+\left|\bm{\mathbf{e}}^{\top}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\right|$
$\displaystyle\leq\frac{1}{10}+\frac{1}{100}+o(1)<\frac{1}{4},$

with probability at least $\frac{49}{50}$.

On the other hand, if we are in the null case, then
$\bm{\mathbf{b}}\sim[-1/2,1/2)^{m}$ independently of
$\bm{\mathbf{\widehat{\theta}}}$, and consequently
$\bm{\mathbf{b}}^{\top}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\pmod{1}\sim[-1/2,1/2)$,
in which case

$\displaystyle\Pr\left[\left|\bm{\mathbf{b}}^{\top}\mathsf{round}(\bm{\mathbf{\widehat{\theta}}})\pmod{1}\right|\geq\frac{1}{4}\right]=\frac{1}{2}.$

Therefore, we have a distinguisher for $\mathsf{CLWE}$ with $\Omega(1)$
advantage.

#### Completeness.

As a warm-up, we compute the expected number of solutions
$\bm{\mathbf{\theta}}\in\mathcal{S}_{n,k}$. In particular, since
$\bm{\mathbf{\theta}}\in\mathcal{S}_{n,k}$, we have
$\bm{\mathbf{G}}_{\mathsf{partite}}\bm{\mathbf{\theta}}=\mathbf{1}$ by Lemma
6. It therefore suffices to show

$\frac{\lVert\bm{\mathbf{A}}\bm{\mathbf{\theta}}\rVert_{2}^{2}}{m+k}\leq\delta^{2}$

for $\bm{\mathbf{\theta}}$ to be a solution. For simplicity, let
$\delta^{\prime}=\delta\sqrt{m+k}=\frac{1}{100\gamma_{\mathsf{CLWE}}}=\frac{1}{200\sqrt{m}}$.
Fix some $\bm{\mathbf{\theta}}\in\mathcal{S}_{n,k}$. The random variable
$\bm{\mathbf{A}}\bm{\mathbf{\theta}}\in\mathbb{R}^{m}$ (over the randomness of
$\bm{\mathbf{A}}$) is distributed according to
$\mathcal{N}(\mathbf{0},kI_{m\times m})$. Therefore,
$\lVert\bm{\mathbf{A}}\bm{\mathbf{\theta}}\rVert_{2}^{2}/k\sim\chi^{2}(m)$. As
a result,

$p:=\Pr_{\bm{\mathbf{A}}}\left[\lVert\bm{\mathbf{A}}\bm{\mathbf{\theta}}\rVert_{2}^{2}\leq(\delta^{\prime})^{2}\right]=\Pr_{Z\sim\chi^{2}(m)}\left[Z\leq\frac{(\delta^{\prime})^{2}}{k}\right].$

Using the CDF of the $\chi^{2}(m)$ distribution and the lower incomplete gamma
function $\gamma(\cdot,\cdot)$, we have

$\displaystyle
p=\Pr_{Z\sim\chi^{2}(m)}\left[Z\leq\frac{(\delta^{\prime})^{2}}{k}\right]$
$\displaystyle=\frac{1}{\Gamma(m/2)}\cdot\gamma\left(\frac{m}{2},\frac{(\delta^{\prime})^{2}}{2k}\right)$
$\displaystyle=\frac{1}{(m/2-1)!}\left(\frac{(\delta^{\prime})^{2}}{2k}\right)^{m/2}e^{-(\delta^{\prime})^{2}/2k}\sum_{j=0}^{\infty}\frac{\left(\frac{(\delta^{\prime})^{2}}{2k}\right)^{j}}{(m/2)(m/2+1)\cdots(m/2+j)}$
$\displaystyle=(1\pm
o(1))\cdot\frac{(\delta^{\prime})^{m}}{(m/2-1)!(2k)^{m/2}}\cdot\frac{2}{m},$
$\displaystyle=\left(\frac{\delta^{\prime}}{\sqrt{mk}}\right)^{m(1\pm o(1))}$

because in our setting, $(\delta^{\prime})^{2}/2k=o(1)$, so
$e^{-(\delta^{\prime})^{2}/2k}=1-o(1)$ and the infinite sum is dominated by
its first term, and because $\delta^{\prime}=o(1)$ and $\sqrt{mk}=\omega(1)$.
Therefore, by linearity of expectation, the expected number of solutions $X$
in $\mathcal{S}_{n,k}$ satisfies

$\operatorname*{\mathbb{E}}[X]=\left(\frac{n}{k}\right)^{k}\cdot p.$

Setting $n$ so that

$p=\left(\frac{n}{k}\right)^{-k/10}$

gives

$\operatorname*{\mathbb{E}}[X]=\left(\frac{n}{k}\right)^{9k/10},\;\;n=k\cdot
2^{(10\pm o(1))m/k\cdot\log(\sqrt{mk}/\delta^{\prime})}=k\cdot
2^{\Theta(m/k\cdot\log(\sqrt{mk}\cdot\gamma_{\mathsf{CLWE}}))}.$

We turn this expected value bound into a $1-o(1)$ bound on the existence of a
sparse solution in Appendix B.888We greatly thank Kiril Bangachev for turning
the expected value statement into a high probability statement. ∎

#### Acknowledgements.

We greatly thank Kiril Bangachev for the proof of completeness in Theorem 6
(in Appendix B), and we thank Huck Bennett and Noah Stephens-Davidowitz for
answering our questions about the $\mathsf{BinaryBDD}$ problem. We would also
like to thank Stefan Tiegel for useful discussions about the performance of
Lasso in the noiseless setting.

## References

  * [Bab86] László Babai.  On lovász’lattice reduction and the nearest lattice point problem.  Combinatorica, 6:1–13, 1986.
  * [BDT24] Rares Buhai, Jingqiu Ding, and Stefan Tiegel.  Computational-statistical gaps for improper learning in sparse linear regression, 2024.  Personal Communication.
  * [BKW03] Avrim Blum, Adam Kalai, and Hal Wasserman.  Noise-tolerant learning, the parity problem, and the statistical query model.  J. ACM, 50(4):506–519, 2003.
  * [BLP+13] Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé.  Classical hardness of learning with errors.  In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 575–584. ACM, 2013.
  * [BRST21] Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang.  Continuous lwe.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 694–707, 2021.
  * [CDS98] Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders.  Atomic decomposition by basis pursuit.  SIAM J. Sci. Comput., 20(1):33–61, 1998.
  * [CT07] Emmanuel Candes and Terence Tao.  The Dantzig selector: Statistical estimation when p is much larger than n.  The Annals of Statistics, 35(6):2313 – 2351, 2007.
  * [GKPV10] Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan.  Robustness of the learning with errors assumption.  In Andrew Chi-Chih Yao, editor, Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, pages 230–240. Tsinghua University Press, 2010.
  * [GKZ21] David Gamarnik, Eren C. Kizildag, and Ilias Zadik.  Inference in high-dimensional linear regression via lattice basis reduction and integer relation detection.  IEEE Trans. Inf. Theory, 67(12):8109–8139, 2021.
  * [GV21] Aparna Gupte and Vinod Vaikuntanathan.  The fine-grained hardness of sparse linear regression.  arXiv preprint arXiv:2106.03131, 2021.
  * [GVV22] Aparna Gupte, Neekon Vafa, and Vinod Vaikuntanathan.  Continuous lwe is as hard as lwe & applications to learning gaussian mixtures.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 1162–1173. IEEE, 2022.
  * [KF15] Paul Kirchner and Pierre-Alain Fouque.  An improved BKW algorithm for LWE with applications to cryptography and lattices.  In Rosario Gennaro and Matthew Robshaw, editors, Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I, volume 9215 of Lecture Notes in Computer Science, pages 43–62. Springer, 2015.
  * [KKMR21] Jonathan A. Kelner, Frederic Koehler, Raghu Meka, and Dhruv Rohatgi.  On the power of preconditioning in sparse linear regression.  CoRR, abs/2106.09207, 2021.
  * [KKMR22] 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:24419–24431, 2022.
  * [KKMR23] Jonathan A. Kelner, Frederic Koehler, Raghu Meka, and Dhruv Rohatgi.  Feature adaptation for sparse linear regression.  CoRR, abs/2305.16892, 2023.
  * [LLL82] Arjen K Lenstra, Hendrik Willem Lenstra, and László Lovász.  Factoring polynomials with rational coefficients.  Mathematische annalen, 261(ARTICLE):515–534, 1982.
  * [LLM06] Yi-Kai Liu, Vadim Lyubashevsky, and Daniele Micciancio.  On bounded distance decoding for general lattices.  In Josep Díaz, Klaus Jansen, José D. P. Rolim, and Uri Zwick, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings, volume 4110 of Lecture Notes in Computer Science, pages 450–461. Springer, 2006.
  * [LM00] Beatrice Laurent and Pascal Massart.  Adaptive estimation of a quadratic functional by model selection.  Annals of Statistics, pages 1302–1338, 2000.
  * [Mic18] Daniele Micciancio.  On the hardness of learning with errors with binary secrets.  Theory of Computing, 14(1):1–17, 2018.
  * [MP12] Daniele Micciancio and Chris Peikert.  Trapdoors for lattices: Simpler, tighter, faster, smaller.  In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings, volume 7237 of Lecture Notes in Computer Science, pages 700–718. Springer, 2012.
  * [NIS] NIST.  Post-quantum cryptography standardization.  https://csrc.nist.gov/Projects/Post-Quantum-Cryptography.
  * [NRWY12] Sahand N Negahban, Pradeep Ravikumar, Martin J Wainwright, and Bin Yu.  A unified framework for high-dimensional analysis of m-estimators with decomposable regularizers.  Statistical Science, pages 538–557, 2012.
  * [Pei09] Chris Peikert.  Public-key cryptosystems from the worst-case shortest vector problem: extended abstract.  In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 333–342. ACM, 2009.
  * [Reg09] Oded Regev.  On lattices, learning with errors, random linear codes, and cryptography.  J. ACM, 56(6):34:1–34:40, 2009.
  * [RV10] Mark Rudelson and Roman Vershynin.  Non-asymptotic theory of random matrices: extreme singular values.  In Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II–IV: Invited Lectures, pages 1576–1602. World Scientific, 2010.
  * [Sch87] Claus-Peter Schnorr.  A hierarchy of polynomial time lattice basis reduction algorithms.  Theor. Comput. Sci., 53:201–224, 1987.
  * [Tib96] Robert Tibshirani.  Regression shrinkage and selection via the lasso.  Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288, 1996.
  * [ZSWB22] Ilias Zadik, Min Jae Song, Alexander S. Wein, and Joan Bruna.  Lattice-based methods surpass sum-of-squares in clustering.  In Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 1247–1248. PMLR, 2022.
  * [ZWJ14] Yuchen Zhang, Martin J Wainwright, and Michael I Jordan.  Lower bounds on the performance of polynomial-time algorithms for sparse linear regression.  In Conference on Learning Theory, pages 921–948, 2014.

##  Appendix A Complexity of Binary Bounded Distance Decoding

In this section, we describe what is known about the computational complexity
of BDD and $\mathsf{BinaryBDD}_{d,\alpha}$.

###  A.1 Babai’s Rounding Off Algorithm

We analyze the “rounding off” algorithm given by [Bab86] and bound its
performance in terms of the condition number $\kappa(\mathbf{B})$ of the
lattice basis $\mathbf{B}$.999For the other algorithm of [Bab86], the nearest
(hyper)plane algorithm, success occurs when $\alpha$ is at most a quantity
defined in terms of the norms of the Gram-Schmidt orthogonalization of the
basis $\bm{\mathbf{B}}$, which cannot be cleanly bounded in terms of
$\kappa(\bm{\mathbf{B}})$. Given a full-rank lattice basis
$\bm{\mathbf{B}}\in\mathbb{R}^{d\times d}$ and target
$\bm{\mathbf{t}}:=\bm{\mathbf{B}}\bm{\mathbf{z}}+\bm{\mathbf{e}}$ for
$\bm{\mathbf{z}}\in\mathbb{Z}^{d}$ and
$\lVert\bm{\mathbf{e}}\rVert_{2}\leq\alpha\lambda_{1}(\bm{\mathbf{B}})$, the
rounding off algorithm simply outputs
$\mathsf{round}(\bm{\mathbf{B}}^{-1}\bm{\mathbf{t}})\in\mathbb{Z}^{d}$.101010Often,
Babai’s rounding algorithm is performed on an LLL-reduced ([LLL82]) basis, and
the resulting analysis of Babai’s algorithm depends on the properties of the
LLL reduction. Here, we instead analyze how Babai’s algorithm would perform on
a general basis in terms of the conditioning of the given basis. Note that
lattice basis reduction does not preserve $\mathsf{BinaryBDD}_{d,\alpha}$
solutions as $\lambda_{1,\mathsf{bin}}(\mathbf{B})$ is basis-dependent. To
argue correctness, it suffices to show

$\lVert\bm{\mathbf{B}}^{-1}\bm{\mathbf{t}}-\bm{\mathbf{z}}\rVert_{\infty}<\frac{1}{2},$

as this would guarantee
$\mathsf{round}(\bm{\mathbf{B}}^{-1}\bm{\mathbf{t}})=\bm{\mathbf{z}}$.

######  Lemma 11.

For $\alpha<\sigma_{\min}(\bm{\mathbf{B}})/(2\lambda_{1}(\bm{\mathbf{B}}))$,
Babai’s rounding off algorithm solves $\mathsf{BDD}$. The same is true for
$\mathsf{BinaryBDD}_{d,\alpha}$ for
$\alpha<\sigma_{\min}(\bm{\mathbf{B}})/(2\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}}))$.

###### Proof.

For the case of $\mathsf{BDD}$, we have

$\left\lVert\bm{\mathbf{B}}^{-1}\bm{\mathbf{t}}-\bm{\mathbf{z}}\right\rVert_{\infty}=\left\lVert\bm{\mathbf{B}}^{-1}\bm{\mathbf{e}}\right\rVert_{\infty}\leq\left\lVert\bm{\mathbf{B}}^{-1}\bm{\mathbf{e}}\right\rVert_{2}\leq\sigma_{\max}(\bm{\mathbf{B}}^{-1})\lVert\bm{\mathbf{e}}\rVert_{2}=\frac{\lVert\bm{\mathbf{e}}\rVert_{2}}{\sigma_{\min}(\bm{\mathbf{B}})}\leq\frac{\alpha\lambda_{1}(\bm{\mathbf{B}})}{\sigma_{\min}(\bm{\mathbf{B}})}<\frac{1}{2},$

as desired. The proof follows very similarly for
$\mathsf{BinaryBDD}_{d,\alpha}$. ∎

######  Corollary 2.

For $\alpha<1/(4\kappa(\mathbf{B}))$, Babai’s rounding off algorithm solves
$\mathsf{BDD}$ and $\mathsf{BinaryBDD}$.

###### Proof.

Since
$\lambda_{1}(\bm{\mathbf{B}})\leq\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})\leq
2\sigma_{\max}(\bm{\mathbf{B}})$ by Lemma 1, we have

$\alpha<\frac{1}{4\kappa(\mathbf{B})}=\frac{\sigma_{\min}(\mathbf{B})}{4\sigma_{\max}(\mathbf{B})}\leq\min\left(\frac{\sigma_{\min}(\bm{\mathbf{B}})}{2\lambda_{1}(\bm{\mathbf{B}})},\frac{\sigma_{\min}(\bm{\mathbf{B}})}{2\lambda_{1,\mathsf{bin}}(\bm{\mathbf{B}})}\right).$

Therefore, we can invoke Lemma 11. ∎

As a result, this algorithm is a better algorithm for $\mathsf{BinaryBDD}$
than in Theorem 5 for $\beta\leq 1$ but could be worse for $\beta>1$ (up to
$\operatorname{poly}(d)$ factors).

###  A.2 Binary BDD Algorithm of [KF15]

[KF15] introduce a variant of BDD very similar to $\mathsf{BinaryBDD}$. By
improving the BKW algorithm ([BKW03]), they show the following:

######  Theorem 7 (Corollary 2 of [KF15]).

Given $(\mathbf{B}\in\mathbb{R}^{d\times
d},\bm{\mathbf{t}}:=\mathbf{B}\bm{\mathbf{z}}+\bm{\mathbf{e}})$ with
$\bm{\mathbf{z}}\in\\{-1,1\\}^{d}$ and
$\lVert\bm{\mathbf{e}}\rVert_{2}\leq\alpha\lambda_{1}(\mathbf{B})$, there is
an algorithm outputting $\bm{\mathbf{z}}$ in time
$2^{O\left(\frac{d}{\log\log(1/\alpha)}\right)}$ as long as $\alpha=o(1)$ and
$\alpha=1/2^{o(d/\log d)}$.

Their algorithm also generalizes to $\bm{\mathbf{z}}\in\\{-B,\cdots,B\\}^{d}$
instead of just binary $\bm{\mathbf{z}}$ (with some dependence on $B$). The
main difference between their setting and our definition of
$\mathsf{BinaryBDD}$ is that for them, $\alpha$ is defined in terms of
$\lambda_{1}(\mathbf{B})$ instead of $\lambda_{1,\mathsf{bin}}(\mathbf{B})$.
Since $\lambda_{1}(\mathbf{B})\leq\lambda_{1,\mathsf{bin}}(\mathbf{B})$, it is
not clear whether their algorithm gives a
$2^{O\left(\frac{d}{\log\log(1/\alpha)}\right)}$ time algorithm when given
$\lVert\bm{\mathbf{e}}\rVert_{2}\leq\alpha\lambda_{1,\mathsf{bin}}(\mathbf{B})$
instead of $\lVert\bm{\mathbf{e}}\rVert_{2}\leq\alpha\lambda_{1}(\mathbf{B})$.

[KF15] also give reductions from subset sum in low densities [KF15, Theorem
14] and bounded-norm variants of UniqueSVP [KF15, Theorem 9] and GapSVP [KF15,
Theorem 11] to this bounded-norm variant of BDD. As a result of these
reductions and their algorithm for bounded-norm BDD (i.e., Theorem 7), they
show algorithms for all three of these problems.

###  A.3 Reduction from BDD to Binary BDD

We briefly mention the existence of a reduction from (standard) BDD to
$\mathsf{BinaryBDD}$, at the cost of making the basis $\mathbf{B}$ for the
$\mathsf{BinaryBDD}$ instance have $\sigma_{\min}(\mathbf{B})=0$ and therefore
undefined $\kappa(\mathbf{B})$. First, we note that there is a direct
reduction from $\\{0,1\\}$-$\mathsf{BinaryBDD}$ (i.e., where solutions are in
$\\{0,1\\}^{d}$) to $\mathsf{BinaryBDD}$ that preserves the basis $\mathbf{B}$
by mapping the target $\bm{\mathbf{t}}$ to
$2\bm{\mathbf{t}}-\bm{\mathbf{B}}\mathbf{1}$.

Now, to reduce from standard BDD to $\\{0,1\\}$-$\mathsf{BinaryBDD}$, we first
reduce the target $\bm{\mathbf{t}}$ to lie in the fundamental parallelepiped
of $\bm{\mathbf{B}}$, and then we apply LLL [LLL82] to get a $q:=2^{O(d)}$
upper bound on the size of the resulting coefficients of the reduced solution
$\bm{\mathbf{z}}\in\\{0,1,\cdots,q-1\\}^{d}$. For simplicity, we can round $q$
up to the nearest power of $2$. Now, we use the gadget matrix

$\bm{\mathbf{G}}:=I_{d}\otimes(1,2,\cdots,q/2)\in\mathbb{Z}^{d\times
d\log_{2}(q)}$

used ubiquitously throughout lattice based cryptography (e.g., [MP12]) to map
$\bm{\mathbf{z}}\in\\{0,\cdots,q-1\\}^{d}$ to solutions
$\bm{\mathbf{z}}^{\prime}\in\\{0,1\\}^{d\log_{2}(q)}$. Explicitly, for all
$\bm{\mathbf{z}}\in\\{0,\cdots,q-1\\}^{d}$, there exists a unique
$\bm{\mathbf{z}}^{\prime}\in\\{0,1\\}^{d\log_{2}(q)}$ such that

$\bm{\mathbf{z}}=\bm{\mathbf{G}}\bm{\mathbf{z}}^{\prime}.$

To see this, note that for all $i\in\\{0,\cdots,d-1\\}$, the entries of
$(z^{\prime}_{i\cdot\log_{2}(q)+1},\cdots,z^{\prime}_{i\cdot\log_{2}(q)+\log_{2}(q)})$
form the binary expansion of $z_{i}\in\\{0,\cdots,q-1\\}$. Therefore, we can
let $\bm{\mathbf{B}}^{\prime}=\bm{\mathbf{B}}\bm{\mathbf{G}}$ and write

$\bm{\mathbf{t}}=\bm{\mathbf{B}}\bm{\mathbf{z}}+\bm{\mathbf{e}}=\bm{\mathbf{B}}\bm{\mathbf{G}}\bm{\mathbf{z}}^{\prime}+\bm{\mathbf{e}}=\bm{\mathbf{B}}^{\prime}\bm{\mathbf{z}}^{\prime}+\bm{\mathbf{e}},$

making $(\bm{\mathbf{B}}^{\prime},\bm{\mathbf{t}})$ a
$\\{0,1\\}$-$\mathsf{BinaryBDD}$ instance, preserving the error
$\bm{\mathbf{e}}$. Furthermore, the new dimension $d^{\prime}$ satisfies
$d^{\prime}=d\log_{2}(q)=O(d^{2})$.

##  Appendix B Proof of Completeness of Theorem 6

Recall that $X$ is the number of solutions in $\mathcal{S}_{n,k}$. For
$\bm{\mathbf{v}}\in\mathcal{S}_{n,k}$, let
$X_{\bm{\mathbf{v}}}=\mathbbm{1}[\lVert\bm{\mathbf{A}}\bm{\mathbf{v}}\rVert_{2}\leq\delta^{\prime}]$,
where we have $p:=\operatorname*{\mathbb{E}}[X_{\bm{\mathbf{v}}}]$ and
$X=\sum_{\bm{\mathbf{v}}\in\mathcal{S}_{n,k}}X_{\bm{\mathbf{v}}}$. By
Chebyshev’s inequality, we have

$\Pr[X=0]\leq\frac{\operatorname*{Var}(X)}{\operatorname*{\mathbb{E}}[X]^{2}}=\frac{\operatorname*{Var}(X)}{p^{2}\left(n/k\right)^{2k}}=\frac{\operatorname*{Var}(X)}{\left(n/k\right)^{1.8k}}.$

We will show that

$\operatorname*{Var}(X)=o\left(\left(\frac{n}{k}\right)^{1.8k}\right),$

which would imply that $\Pr[X\geq 1]=1-o(1)$, as desired. For
$\bm{\mathbf{u}},\bm{\mathbf{v}}\in\mathcal{S}_{n,k}$, let
$I(\bm{\mathbf{u}},\bm{\mathbf{v}}):=|\operatorname{support}(\bm{\mathbf{u}})\cap\operatorname{support}(\bm{\mathbf{v}})|$
denote the number of coordinates where they both take on the value $1$.

To do this, we can expand variance into covariance, and group by
$I(\cdot,\cdot)$ between
$\bm{\mathbf{u}},\bm{\mathbf{v}}\in\mathcal{S}_{n,k}$:

$\displaystyle\operatorname*{Var}(X)=\operatorname*{Var}\left(\sum_{\bm{\mathbf{v}}\in\mathcal{S}_{n,k}}X_{\bm{\mathbf{v}}}\right)=\sum_{\bm{\mathbf{u}},\bm{\mathbf{v}}\in\mathcal{S}_{n,k}}\operatorname*{Cov}(X_{\bm{\mathbf{u}}},X_{\bm{\mathbf{v}}})=\sum_{t=0}^{k}\sum_{\begin{subarray}{c}\bm{\mathbf{u}},\bm{\mathbf{v}}\in\mathcal{S}_{n,k}\\\
I(\bm{\mathbf{u}},\bm{\mathbf{v}})=t\end{subarray}}\operatorname*{Cov}(X_{\bm{\mathbf{u}}},X_{\bm{\mathbf{v}}}).$

We can split this into $3$ terms, $Z_{0},Z_{1},Z_{2}$, as follows:

$\operatorname*{Var}(X)=\underbrace{\sum_{\begin{subarray}{c}\bm{\mathbf{u}},\bm{\mathbf{v}}\in\mathcal{S}_{n,k}\\\
I(\bm{\mathbf{u}},\bm{\mathbf{v}})=0\end{subarray}}\operatorname*{Cov}(X_{\bm{\mathbf{u}}},X_{\bm{\mathbf{v}}})}_{Z_{0}}+\underbrace{\sum_{t=1}^{k/4}\sum_{\begin{subarray}{c}\bm{\mathbf{u}},\bm{\mathbf{v}}\in\mathcal{S}_{n,k}\\\
I(\bm{\mathbf{u}},\bm{\mathbf{v}})=t\end{subarray}}\operatorname*{Cov}(X_{\bm{\mathbf{u}}},X_{\bm{\mathbf{v}}})}_{Z_{1}}+\underbrace{\sum_{t>k/4}\sum_{\begin{subarray}{c}\bm{\mathbf{u}},\bm{\mathbf{v}}\in\mathcal{S}_{n,k}\\\
I(\bm{\mathbf{u}},\bm{\mathbf{v}})=t\end{subarray}}\operatorname*{Cov}(X_{\bm{\mathbf{u}}},X_{\bm{\mathbf{v}}})}_{Z_{2}}.$

We bound each of these terms separately by
$o\left(\left(\frac{n}{k}\right)^{1.8k}\right)$, which gives the desired
result. Before doing so, note that for all $t\in\\{0,\cdots,k\\}$,

$\left|\\{(\bm{\mathbf{u}},\bm{\mathbf{v}})\in\mathcal{S}_{n,k}:I(\bm{\mathbf{u}},\bm{\mathbf{v}})=t\\}\right|=\binom{k}{t}\left(\frac{n}{k}\right)^{t}\left(\frac{n}{k}\right)^{k-t}\left(\frac{n}{k}-1\right)^{k-t}\leq\binom{k}{t}\left(\frac{n}{k}\right)^{2k-t},$
(18)

since one needs to specify the $t$ parts in common, the common values on those
$t$ parts, and two distinct values on the $k-t$ other parts.

Bounding $Z_{0}$: For $I(\bm{\mathbf{u}},\bm{\mathbf{v}})=0$, since
$\bm{\mathbf{u}}$ and $\bm{\mathbf{v}}$ do not overlap, they depend on
disjoint columns of $\bm{\mathbf{A}}$. Therefore, $X_{\bm{\mathbf{u}}}$ and
$X_{\bm{\mathbf{v}}}$ are independent, making
$\operatorname*{Cov}(X_{\bm{\mathbf{v}}},X_{\bm{\mathbf{u}}})=0$. Summing over
$\bm{\mathbf{u}},\bm{\mathbf{v}}$ with $I(\bm{\mathbf{u}},\bm{\mathbf{v}})=0$
gives $Z_{0}=0$.

Bounding $Z_{1}$: For this case when
$t=I(\bm{\mathbf{u}},\bm{\mathbf{v}})\in[1,k/4]$, the analysis becomes
significantly more technical. Let $\bm{\mathbf{v}}_{0}\in\\{0,1\\}^{n}$ be the
“common” vector with support
$\operatorname{support}(\bm{\mathbf{u}})\cap\operatorname{support}(\bm{\mathbf{v}})$,
let $\bm{\mathbf{v}}_{1}\in\\{0,1\\}^{n}$ be the vector with support
$\operatorname{support}(\bm{\mathbf{v}})\setminus\operatorname{support}(\bm{\mathbf{u}})$,
and let $\bm{\mathbf{v}}_{2}\in\\{0,1\\}^{n}$ be the vector with support
$\operatorname{support}(\bm{\mathbf{u}})\setminus\operatorname{support}(\bm{\mathbf{v}})$.
Note that $\lVert\bm{\mathbf{v}}_{0}\rVert_{0}=t$ and
$\lVert\bm{\mathbf{v}}_{1}\rVert_{0}=\lVert\bm{\mathbf{v}}_{2}\rVert_{0}=k-t$.
We have $\bm{\mathbf{v}}=\bm{\mathbf{v}}_{0}+\bm{\mathbf{v}}_{1}$ and
$\bm{\mathbf{u}}=\bm{\mathbf{v}}_{0}+\bm{\mathbf{v}}_{2}$.

Now, consider the random variables
$\bm{\mathbf{w}}=\bm{\mathbf{A}}\bm{\mathbf{v}}_{0}$,
$\bm{\mathbf{x}}=\bm{\mathbf{A}}\bm{\mathbf{v}}_{1}$, and
$\bm{\mathbf{y}}=\bm{\mathbf{A}}\bm{\mathbf{v}}_{2}$. Since the supports of
$\bm{\mathbf{v}}_{i}$ are disjoint, the random variables
$\bm{\mathbf{w}},\bm{\mathbf{x}},\bm{\mathbf{y}}$ are independent. Moreover,
$\bm{\mathbf{w}}\sim\mathcal{N}(\mathbf{0},tI_{m\times m})$ and
$\bm{\mathbf{x}},\bm{\mathbf{y}}\sim\mathcal{N}(\mathbf{0},(k-t)I_{m\times
m})$. For an arbitrary vector $\bm{\mathbf{z}}\in\mathbb{R}^{m}$ and
$\delta>0$, let $B_{\delta}(\bm{\mathbf{z}})$ denote the ball of radius
$\delta$ around $\bm{\mathbf{z}}$ in $\mathbb{R}^{m}$. Let
$\mu_{\sigma^{2}}(\bm{\mathbf{z}})$ denote the density function of
$\mathcal{N}(\mathbf{0},\sigma^{2}I_{m\times m})$ at the point
$\bm{\mathbf{z}}\in\mathbb{R}^{m}$. Explicitly,

$\mu_{\sigma^{2}}(\bm{\mathbf{z}})=\frac{1}{\left(\sqrt{2\pi\sigma^{2}}\right)^{m}}\exp\left(-\lVert\bm{\mathbf{z}}\rVert_{2}^{2}/(2\sigma^{2})\right).$

We begin by using the bound

$\operatorname*{Cov}(X_{\bm{\mathbf{u}}},X_{\bm{\mathbf{v}}})=\operatorname*{\mathbb{E}}[X_{\bm{\mathbf{u}}}X_{\bm{\mathbf{v}}}]-\operatorname*{\mathbb{E}}[X_{\bm{\mathbf{u}}}]\operatorname*{\mathbb{E}}[X_{\bm{\mathbf{v}}}]\leq\operatorname*{\mathbb{E}}[X_{\bm{\mathbf{u}}}X_{\bm{\mathbf{v}}}].$

Then,

$\displaystyle\operatorname*{\mathbb{E}}[X_{\bm{\mathbf{u}}}X_{\bm{\mathbf{v}}}]=\Pr_{\mathbf{A}}[\lVert\mathbf{A}\bm{\mathbf{u}}\rVert_{2}\leq\delta^{\prime}\land\lVert\mathbf{A}\bm{\mathbf{v}}\rVert_{2}\leq\delta^{\prime}]$
$\displaystyle=\Pr_{\bm{\mathbf{w}},\bm{\mathbf{x}},\bm{\mathbf{y}}}[\lVert\bm{\mathbf{w}}+\bm{\mathbf{x}}\rVert_{2}\leq\delta^{\prime}\land\lVert\bm{\mathbf{w}}+\bm{\mathbf{y}}\rVert_{2}\leq\delta^{\prime}]$
$\displaystyle=\Pr_{\bm{\mathbf{w}},\bm{\mathbf{x}},\bm{\mathbf{y}}}[\bm{\mathbf{x}}\in
B_{\delta^{\prime}}(-\bm{\mathbf{w}})\land\bm{\mathbf{y}}\in
B_{\delta^{\prime}}(-\bm{\mathbf{w}})]$
$\displaystyle=\int_{\mathbb{R}^{m}}\left(\Pr_{\bm{\mathbf{x}}}[\bm{\mathbf{x}}\in
B_{\delta^{\prime}}(-\bm{\mathbf{w}})]\right)^{2}\mu_{t}(\bm{\mathbf{w}})d\bm{\mathbf{w}}$
$\displaystyle=\int_{\mathbb{R}^{m}}\left(\int_{B_{\delta^{\prime}}(-\bm{\mathbf{w}})}\mu_{k-t}(\bm{\mathbf{x}})d\bm{\mathbf{x}}\right)^{2}\mu_{t}(\bm{\mathbf{w}})d\bm{\mathbf{w}}.$

We split this integral up into two terms $Y_{0}$ and $Y_{1}$, depending on the
norm of $\bm{\mathbf{w}}$: either $\lVert\bm{\mathbf{w}}\rVert_{2}\leq
k/\delta^{\prime}$ or not. Explicitly, we have

$\displaystyle\operatorname*{Cov}(X_{\bm{\mathbf{u}}},X_{\bm{\mathbf{v}}})$
$\displaystyle\leq\int_{\mathbb{R}^{m}}\left(\int_{B_{\delta^{\prime}}(-\bm{\mathbf{w}})}\mu_{k-t}(\bm{\mathbf{x}})d\bm{\mathbf{x}}\right)^{2}\mu_{t}(\bm{\mathbf{w}})d\bm{\mathbf{w}}$
(19)
$\displaystyle=\underbrace{\int_{B_{k/\delta^{\prime}}(\mathbf{0})}\left(\int_{B_{\delta^{\prime}}(-\bm{\mathbf{w}})}\mu_{k-t}(\bm{\mathbf{x}})d\bm{\mathbf{x}}\right)^{2}\mu_{t}(\bm{\mathbf{w}})d\bm{\mathbf{w}}}_{Y_{0}}$
(20) $\displaystyle+\underbrace{\int_{\mathbb{R}^{m}\setminus
B_{k/\delta^{\prime}}(\mathbf{0})}\left(\int_{B_{\delta^{\prime}}(-\bm{\mathbf{w}})}\mu_{k-t}(\bm{\mathbf{x}})d\bm{\mathbf{x}}\right)^{2}\mu_{t}(\bm{\mathbf{w}})d\bm{\mathbf{w}}}_{Y_{1}}.$
(21)

(Subcase 1) Bounding $Y_{0}$: For $\bm{\mathbf{w}}\in
B_{k/\delta^{\prime}}(\mathbf{0})$, we have
$\lVert\bm{\mathbf{w}}\rVert_{2}\leq k/\delta^{\prime}$. The point is that in
this case, the density $\mu_{k-t}(\bm{\mathbf{x}})$ is almost uniform for
$\bm{\mathbf{x}}\in B_{\delta^{\prime}}(-\bm{\mathbf{w}})$. To see this,
consider two arbitrary points
$-\bm{\mathbf{w}}-\bm{\mathbf{a}},-\bm{\mathbf{w}}-\bm{\mathbf{b}}\in
B_{\delta^{\prime}}(-\bm{\mathbf{w}})$, where
$\lVert\bm{\mathbf{a}}\rVert,\lVert\bm{\mathbf{b}}\rVert\leq\delta^{\prime}$.
The ratio of the densities is given by

$\displaystyle\frac{\mu_{k-t}(-\bm{\mathbf{w}}-\bm{\mathbf{a}})}{\mu_{k-t}(-\bm{\mathbf{w}}-\bm{\mathbf{b}})}$
$\displaystyle=\frac{\exp\left(-\lVert\bm{\mathbf{w}}+\bm{\mathbf{a}}\rVert_{2}^{2}/(2(k-t))\right)}{\exp\left(-\lVert\bm{\mathbf{w}}+\bm{\mathbf{b}}\rVert_{2}^{2}/(2(k-t))\right)}$
$\displaystyle=\exp\left(\frac{-\langle\bm{\mathbf{w}}+\bm{\mathbf{a}},\bm{\mathbf{w}}+\bm{\mathbf{a}}\rangle+\langle\bm{\mathbf{w}}+\bm{\mathbf{b}},\bm{\mathbf{w}}+\bm{\mathbf{b}}\rangle}{2(k-t)}\right)$
$\displaystyle=\exp\left(\frac{-\lVert\bm{\mathbf{a}}\rVert_{2}^{2}+\lVert\bm{\mathbf{b}}\rVert_{2}^{2}+2\langle\bm{\mathbf{w}},\bm{\mathbf{b}}-\bm{\mathbf{a}}\rangle}{2(k-t)}\right).$

By Cauchy-Schwartz and the triangle inequality, we have

$|2\langle\bm{\mathbf{w}},\bm{\mathbf{b}}-\bm{\mathbf{a}}\rangle|\leq
2\lVert\bm{\mathbf{w}}\rVert\lVert\bm{\mathbf{b}}-\bm{\mathbf{a}}\rVert\leq
2\lVert\bm{\mathbf{w}}\rVert(\lVert\bm{\mathbf{b}}\rVert+\lVert\bm{\mathbf{a}}\rVert)\leq
4\frac{k}{\delta^{\prime}}\delta^{\prime}=4k.$

For the other two terms in the numerator, we have
$\lVert\bm{\mathbf{a}}\rVert^{2},\lVert\bm{\mathbf{b}}\rVert^{2}\leq(\delta^{\prime})^{2}=o(1)$.
Therefore, the absolute value of the numerator in the exponent is at most
$O(k)$. Since $t\leq k/4$, we know $k-t\geq 3k/4$, making the exponent at most
$O(k)/\Omega(k)=O(1)$. Therefore, there is a constant $C=O(1)$ such that

$\frac{1}{C}\leq\frac{\mu_{k-t}(-\bm{\mathbf{w}}-\bm{\mathbf{a}})}{\mu_{k-t}(-\bm{\mathbf{w}}-\bm{\mathbf{b}})}\leq
C.$

Therefore, we get

$\displaystyle Y_{0}$
$\displaystyle=\int_{B_{k/\delta^{\prime}}(\mathbf{0})}\left(\int_{B_{\delta^{\prime}}(-\bm{\mathbf{w}})}\mu_{k-t}(\bm{\mathbf{x}})d\bm{\mathbf{x}}\right)^{2}\mu_{t}(\bm{\mathbf{w}})d\bm{\mathbf{w}}$
$\displaystyle\leq
C^{2}\cdot\int_{B_{k/\delta^{\prime}}(\mathbf{0})}\left(\int_{B_{\delta^{\prime}}(-\bm{\mathbf{w}})}\mu_{k-t}(-\bm{\mathbf{w}})d\bm{\mathbf{x}}\right)^{2}\mu_{t}(\bm{\mathbf{w}})d\bm{\mathbf{w}}$
$\displaystyle=C^{2}\int_{B_{k/\delta^{\prime}}(\mathbf{0})}\operatorname*{Vol}(B_{\delta^{\prime}}(-\bm{\mathbf{w}}))^{2}\cdot\mu_{k-t}(-\bm{\mathbf{w}})^{2}\mu_{t}(\bm{\mathbf{w}})d\bm{\mathbf{w}}$
$\displaystyle=C^{2}\operatorname*{Vol}(B_{\delta^{\prime}}(\mathbf{0}))^{2}\int_{B_{k/\delta^{\prime}}(\mathbf{0})}\mu_{k-t}(-\bm{\mathbf{w}})^{2}\mu_{t}(\bm{\mathbf{w}})d\bm{\mathbf{w}}$
$\displaystyle\leq
C^{2}\operatorname*{Vol}(B_{\delta^{\prime}}(\mathbf{0}))^{2}\int_{\mathbb{R}^{m}}\mu_{k-t}(-\bm{\mathbf{w}})^{2}\mu_{t}(\bm{\mathbf{w}})d\bm{\mathbf{w}}.$

Continuing the inequality, we have

$\displaystyle Y_{0}$ $\displaystyle\leq
C^{2}\operatorname*{Vol}(B_{\delta^{\prime}}(\mathbf{0}))^{2}\int_{\mathbb{R}^{m}}\mu_{k-t}(-\bm{\mathbf{w}})^{2}\mu_{t}(\bm{\mathbf{w}})d\bm{\mathbf{w}}$
(22)
$\displaystyle=C^{2}\operatorname*{Vol}(B_{\delta^{\prime}}(\mathbf{0}))^{2}\frac{1}{\left(\sqrt{2\pi(k-t)}\right)^{2m}\left(\sqrt{2\pi
t}\right)^{m}}\int_{\mathbb{R}^{m}}\exp\left(-\frac{2\lVert\bm{\mathbf{w}}\rVert^{2}}{2(k-t)}-\frac{\lVert\bm{\mathbf{w}}\rVert^{2}}{2t}\right)d\bm{\mathbf{w}}$
(23)
$\displaystyle=C^{2}\operatorname*{Vol}(B_{\delta^{\prime}}(\mathbf{0}))^{2}\frac{1}{\left(\sqrt{2\pi(k-t)}\right)^{2m}\left(\sqrt{2\pi
t}\right)^{m}}\int_{\mathbb{R}^{m}}\exp\left(-\frac{k+t}{2t(k-t)}\lVert\bm{\mathbf{w}}\rVert^{2}\right)d\bm{\mathbf{w}}$
(24)
$\displaystyle=C^{2}\operatorname*{Vol}(B_{\delta^{\prime}}(\mathbf{0}))^{2}\frac{\left(\sqrt{2\pi\cdot\frac{t(k-t)}{k+t}}\right)^{m}}{\left(\sqrt{2\pi(k-t)}\right)^{2m}\left(\sqrt{2\pi
t}\right)^{m}}$ (25)
$\displaystyle=C^{2}\operatorname*{Vol}(B_{\delta^{\prime}}(\mathbf{0}))^{2}\left((2\pi)^{2}(k-t)(k+t)\right)^{-m/2}$
(26) $\displaystyle\leq
C^{2}\operatorname*{Vol}(B_{\delta^{\prime}}(\mathbf{0}))^{2}\left((2\pi)^{2}k^{2}\right)^{-m/2}\left(1+\frac{2t^{2}}{k^{2}}\right)^{m/2}$
(27) $\displaystyle\leq
C^{2}\operatorname*{Vol}(B_{\delta^{\prime}}(\mathbf{0}))^{2}\left((2\pi)^{2}k^{2}\right)^{-m/2}\exp\left(t^{2}m/k^{2}\right),$
(28)

where the penultimate inequality uses the fact that $t\leq k/4$. We can
similarly lower bound $p$ as follows:

$\displaystyle p=\operatorname*{\mathbb{E}}[X_{\bm{\mathbf{v}}}]$
$\displaystyle=\int_{\mathbb{R}^{m}}\int_{B_{\delta^{\prime}}(-\bm{\mathbf{w}})}\mu_{k-t}(\bm{\mathbf{x}})d\bm{\mathbf{x}}\mu_{t}(\bm{\mathbf{w}})d\bm{\mathbf{w}}$
(29)
$\displaystyle\geq\int_{B_{k/\delta^{\prime}}(\mathbf{0})}\int_{B_{\delta^{\prime}}(-\bm{\mathbf{w}})}\mu_{k-t}(\bm{\mathbf{x}})d\bm{\mathbf{x}}\mu_{t}(\bm{\mathbf{w}})d\bm{\mathbf{w}}$
(30)
$\displaystyle\geq\frac{1}{C}\int_{B_{k/\delta^{\prime}}(\mathbf{0})}\int_{B_{\delta^{\prime}}(-\bm{\mathbf{w}})}\mu_{k-t}(-\bm{\mathbf{w}})d\bm{\mathbf{x}}\mu_{t}(\bm{\mathbf{w}})d\bm{\mathbf{w}}$
(31)
$\displaystyle=\frac{1}{C}\operatorname*{Vol}(B_{\delta^{\prime}}(\mathbf{0}))\int_{B_{k/\delta^{\prime}}(\mathbf{0})}\mu_{k-t}(-\bm{\mathbf{w}})\mu_{t}(\bm{\mathbf{w}})d\bm{\mathbf{w}}$
(32)