# The Fine-Grained Hardness of
Sparse Linear Regression

Aparna Gupte
MIT Email<EMAIL_ADDRESS>Vinod Vaikuntanathan
MIT Email<EMAIL_ADDRESS>
###### Abstract

Sparse linear regression is the well-studied inference problem where one is
given a design matrix $\mathbf{A}\in\mathbb{R}^{M\times N}$ and a response
vector $\mathbf{b}\in\mathbb{R}^{M}$, and the goal is to find a solution
$\mathbf{x}\in\mathbb{R}^{N}$ which is $k$-sparse (that is, it has at most $k$
non-zero coordinates) and minimizes the prediction error
$\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_{2}$. On the one hand, the problem is
known to be $\mathcal{NP}$-hard which tells us that no polynomial-time
algorithm exists unless $\mathcal{P}=\mathcal{NP}$. On the other hand, the
best known algorithms for the problem do a brute-force search among $N^{k}$
possibilities. In this work, we show that there are no better-than-brute-force
algorithms, assuming any one of a variety of popular conjectures including the
weighted $k$-clique conjecture from the area of fine-grained complexity, or
the hardness of the closest vector problem from the geometry of numbers. We
also show the impossibility of better-than-brute-force algorithms when the
prediction error is measured in other $\ell_{p}$ norms, assuming the strong
exponential-time hypothesis.

##  1 Introduction

High-dimensional inference problems come up naturally in many fields of
science and engineering including computational biology and genomics, natural
language processing, medical imaging and remote sensing. A well-known example
is the standard linear regression problem where one is given data items
$\mathbf{a}_{1},\mathbf{a}_{2},\ldots,\mathbf{a}_{M}\in\mathbb{R}^{N}$ and
responses $b_{1},\ldots,b_{M}\in\mathbb{R}$ where each
$b_{i}\approx\langle\mathbf{a}_{i},\mathbf{x}^{*}\rangle$ for a hidden
parameter vector $\mathbf{x}^{*}\in\mathbb{R}^{N}$. When $N\gg M$, the model
is unidentifiable; however, in various application domains (such as the ones
above), it makes sense to require that $\mathbf{x}^{*}$ is sparse, that is, it
has only a few non-zero coordinates. The resulting problem is called sparse
linear regression which can be formulated as finding

$\widehat{\mathbf{x}}\in\operatorname*{arg\,min}_{\mathbf{x}\in\mathbb{R}^{N}}\|\mathbf{b}-\mathbf{A}\mathbf{x}\|_{2}\hskip
14.45377pt\mbox{ such that }\|\mathbf{x}\|_{0}\leq k$

where $\mathbf{A}\in\mathbb{R}^{M\times N}$ is the design matrix with
$\mathbf{a}_{i}$ as its rows, $\mathbf{b}\in\mathbb{R}^{M\times 1}$ is the
response vector consisting of the $b_{i}$’s as entries, and $k$ is the
sparsity parameter.

This problem is non-convex and finding an exact as well as approximate
solution is known to be $\mathcal{NP}$-hard [Nat95, DMA97, FKT15]. Despite
this negative result, when the design matrix $\mathbf{A}$ is particularly
well-conditioned, polynomial-time algorithms based on $\ell_{1}$-relaxation,
such as basis pursuit and Lasso estimators [Tib96, CDS98] as well as the
Dantzig selector [CT07] have been shown to meet the minimax-optimal lower
bound for sparse linear regression. This is also the setting of compressed
sensing, which has seen much exciting work in the last two decades.

However, in several high-dimensional regression problems in data science,
there is no such guarantee on the design matrix $\mathbf{A}$, as the features
could be correlated. As a result, the problem formulation with general design
matrices is also of great interest, and is the main focus of this paper.

On the one hand, the NP-hardness of this problem [Nat95, DMA97, FKT15] rules
out algorithms that run in time polynomial in $M,N$ and $k$. On the other
hand, the best known algorithm for this problem is trivial brute-force search
that runs in time $O(N^{k})$. Concretely, one can enumerate over all possible
$\binom{N}{k}$ supports, and run an ordinary least squares regression with an
$M\times k$ design matrix, which results in a $N^{k}(M+k)^{O(1)}$ time
algorithm [HPIM18]. Improving this to, say, $O(N^{0.999k})$ or even a modest
$O(N^{k-1})$ seems out of reach. This state of affairs motivates our question:

> Can $k$-sparse linear regression be solved in time $N^{(1-\epsilon)k}$ for
> some constant $\epsilon>0$?

Our main result in this paper shows that the answer is “no” assuming popular
conjectures from the field of fine-grained algorithms and complexity [Wil18].

First, we show that it is hard to solve $k$-SLR in the $\ell_{2}$ norm faster
than $O(N^{k-\epsilon})$ for any constant $\epsilon>0$, assuming either the
min-weight $k$-clique hypothesis [Wil18] or the conjectured hardness of the
lattice closest vector problem [BGS17]. The min-weight $k$-clique problem asks
to find a clique with $k$ vertices with the smallest total edge weight, in a
weighted undirected graph. The best known algorithm is exhaustive search which
runs in time $O(N^{k})$ on $N$-node graphs [Wil18]. The closest vector problem
is a long-studied problem in the geometry of numbers [Min10, MG02], which asks
to find the closest lattice point to a given target vector, given an arbitrary
$n$-dimensional integer lattice. The best known algorithm runs in time
$O(2^{n})$ [ADS15], and improving it is a long-standing challenge with
considerable impact in the area of combinatorial optimization and lattice-
based cryptography [BGS17]. (For a more formal description of these problems,
we refer the reader to Section 2).

Secondly, we show that it is hard to solve $k$-SLR in $\ell_{p}$ norms
(including $p=1$ and odd $p>2$) faster than $O(N^{(1-\epsilon)k})$ under the
strong exponential-time hypothesis (SETH) [IP01]. The strong exponential-time
hypothesis, formulated by Impagliazzo and Paturi, conjectures that the
satisfiability problem (SAT), the cornerstone of computer science, cannot be
sped up significantly. More precisely, SETH states that for every
$\epsilon>0$, there is an $k\in\mathbb{N}$ such that $k$-SAT on $n$ variables
cannot be solved in time $2^{(1-\epsilon)n}$.

These results together settle the exact complexity of the $k$-sparse linear
regression problem in the worst-case, assuming popular conjectures in fine-
grained complexity and the geometry of numbers. Under these conjectures, there
are no better-than-brute-force algorithms for sparse linear regression.

#### A Window into our Techniques: Translating Integrality into Sparsity.

The hardness of problems such as the closest vector problem are closely
connected to integer linear programming, where hardness arises from the fact
that one has to come up with integer solutions to an optimization problem. On
the other hand, there is no such integrality condition in $k$-sparse linear
regression; rather, the hardness seems to arise from the fact that we insist
on sparse solutions. Thus, a key technical contribution of our work is showing
several ways to map two apparently different sources of hardness, namely
integrality and sparsity.

In the rest of the paper, we provide a self-contained exposition of our
results. We start with definitions in Section 2, and proceed to show the
reduction from the min-weight $k$-clique problem to sparse linear regression
in Section 3 and the reduction from the lattice closest vector problem in
Section 4. Finally, in Section 5, we also show that there are no sub-quadratic
$N^{2-\epsilon}$-time algorithms for $k$-SLR when $k=2$, assuming the strong
exponential-time hypothesis.

###  1.1 Related work

#### Lower bounds.

Natarajan [Nat95] showed the $\mathcal{NP}$-hardness of solving sparse linear
regression, which rules out $(Nk)^{c}$-time algorithms for any absolute
constant $c$. Har-Peled, Indyk and Mahabadi [HPIM18] showed the hardness of
solving $k$-SLR faster than $O(N^{k/2})$ time, under the well-known $k$-SUM
conjecture from fine-grained complexity. However, both results left a gap
between the best known upper bound which is brute-force search that runs in
$N^{k}$ time, and a lower bound of $N^{k/2}$.

#### Algorithms.

Har-Peled, Indyk and Mahabadi [HPIM18] also give an algorithm for approximate
sparse linear regression with pre-processing that runs in time slightly better
than brute force, namely in time $\tilde{O}(N^{k-1})$. Gupte and Lu [GL20]
showed a slight improvement to the standard $k$-SLR problem in the noiseless
setting, namely they showed an $O(N^{k-1})$ time algorithm. They also give a
$N^{\Omega(k)}$-time lower bound in the noiseless setting, under the
Exponential Time Hypothesis. In contrast to both these works, our result shows
that even such a modest improvement is impossible to achieve for the standard
and well-studied $k$-SLR problem. That is, we show that $k$-SLR cannot be
solved in time $O(N^{k-\epsilon})$ for any constant $\epsilon>0$, under the
popular min-weight $k$-clique conjecture [Wil18] from fine-grained complexity.

#### Compressed Sensing and the LASSO.

While the focus of this paper is the worst-case complexity of sparse linear
regression, its average-case complexity has been the object of much study.
Methods based on $\ell_{1}$-relaxation, such as basis pursuit and Lasso
estimators [Tib96, CDS98] as well as the Dantzig selector [CT07] have been
shown to meet the minimax-optimal lower bound in some cases. In particular,
they focus on the setting where $\mathbf{b}=\mathbf{A}\mathbf{x}+\mathbf{w}$
where the noise vector $\mathbf{w}\sim\mathcal{N}(0,\sigma^{2})$ comes from a
Gaussian distribution. While these methods perform well when the design matrix
$\mathbf{A}$ is well-conditioned in an appropriate sense, Zhang, Wainwright
and Jordan [ZWJ14] show that such a condition is necessary unless
$\mathcal{NP}\subseteq\mathcal{P}/\mathsf{poly}$. Recently, and concurrently
with this work, Kelner et al [KKMR21] show random-design instances of sparse
linear regression that are hard for a particular class of algorithms, namely
preconditioned Lasso. In contrast, we show hardness for worst-case design
matrices, but with respect to any algorithm that runs faster than trivial
brute force search.

Further afield, the areas of fine-grained complexity and the geometry of
numbers (or the study of integer lattices) have recently been shown to have
interesting connections to statistical problems. For example, Backurs, Indyk
and Schmidt [BIS17] show that certain empirical risk minimization (ERM)
problems cannot be solved in sub-quadratic time, under the SETH conjecture. In
another result, Backurs and Tzamos [BT17] showed that the classical Viterbi
algorithm for finding the most likely path in a Hidden Markov Model is in fact
optimal under the min-weight $k$-clique hypothesis which we rely on in this
work. Bruna, Regev, Song and Tang [BRST20] recently showed the hardness of
problems in robust statistics and learning mixtures of Gaussians, assuming the
hardness of lattice problems.

##  2 Preliminaries and definitions

#### Notations.

Bold lower-case letters, such as $\mathbf{x}$, denote (column) vectors. Bold
uppercase letters, such as $\mathbf{A}$, denote matrices. $\mathbb{R}$ stands
for the set of real numbers, $\mathbb{Z}$ for the set of integers, and
$\mathbb{R}^{+}$ (resp. $\mathbb{Z}^{+}$) for the set of non-negative real
numbers (resp. integers). We will let $\|\mathbf{x}\|_{p}$ denote the
$\ell_{p}$ norm of $\mathbf{x}\in\mathbb{R}^{N}$, that is,
$\|\mathbf{x}\|_{p}=\big{(}\sum_{i\in[N]}|x_{i}|^{p}\big{)}^{1/p}$. The
Hamming weight of $\mathbf{x}$, also called its $\ell_{0}$ norm, is simply the
number of non-zero coordinates of $\mathbf{x}$. A vector
$\mathbf{x}\in\mathbb{R}^{N}$ is called $k$-sparse if its Hamming weight is at
most $k$, that is, if $\|\mathbf{x}\|_{0}\leq k$.

###  2.1 Sparse linear regression

We now define the sparse linear regression problem.

######  Definition 1 ($k$-SLRp).

For any integer $k\geq 2$ and $1\leq p\leq\infty$, the $k$-sparse linear
regression problem with respect to the $\ell_{p}$ norm is defined as follows.
Given a matrix $\mathbf{A}\in\mathbb{R}^{M\times N}$, a target vector
$\mathbf{b}\in\mathbb{R}^{M}$, and a number $\delta>0$, distinguish between:

  * •

a YES instance, where there is some $k$-sparse $\mathbf{x}\in\mathbb{R}^{N}$
such that $\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_{p}\leq\delta$; and

  * •

a NO instance, where for all $k$-sparse $\mathbf{x}\in\mathbb{R}^{N}$,
$\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_{p}>\delta$.

$k$-sparse linear regression can be trivially solved in time $N^{k}$. In this
work, we are interested in determining if there are significantly faster
algorithms. We will sometimes also give the algorithms more power, by allowing
them unbounded time to preprocess the design matrix $\mathbf{A}$ in an
“offline” phase, and require them to be fast only in an “online” phase where
they are given $\mathbf{b}$. We call this variant sparse linear regression
with preprocessing.

###  2.2 Fine-grained complexity and its hypotheses

Fine-grained complexity is the study of exact runtimes of algorithms for
various problems. We present the relevant problems and results here, and refer
the reader to the survey by Vassilevska-Williams [Wil18] for a detailed
exposition.

####  $k$-SAT and the SETH Hypothesis.

A central problem in fine-grained complexity is the study of the
satisfiability problem, and the associated strong exponential-time hypothesis.
Given a CNF-SAT formula on $n$ variables with each clause having size at most
$k$, the $k$-SAT problem asks to determine whether the formula is satisfiable
or not.

Impagliazzo and Paturi [IP01] introduced the strong exponential time
hypothesis, conjecturing the fine-grained hardness of $k$-SAT.

######  Definition 2 (Strong Exponential Time Hypothesis (SETH)).

For every $\epsilon>0$ there exists an integer $k\geq 3$ such that no
(randomized) algorithm can solve $k$-SAT on $n$ variables in
$2^{(1-\epsilon)n}$ time.

We also use the non-uniform version of SETH to show hardness of sparse linear
regression with preprocessing.

######  Definition 3 (Non-uniform SETH).

For every $\epsilon>0$ there exists an integer $k\geq 3$ such that no family
of circuits of size $2^{(1-\epsilon)n}$ solves $k$-SAT on $n$ variables.

#### The Weighted $k$-Clique Conjecture.

Suppose we are given an undirected graph $G=(V,E)$ with $|V|=N$ nodes. For a
constant $k\geq 3$, a $k$-clique of $G$ is a fully connected subgraph of $G$
of size $k$. The $k$-clique problem asks to distinguish between YES instances,
where $G$ contains a $k$-clique, and NO instances, where $G$ does not contain
any $k$-clique. Given an edge-weighted graph and a threshold weight $W$, the
Min-Weight $k$-Clique problem asks to distinguish between YES instances which
are graphs $G$ that contain a $k$-Clique of weight at most $W$, and NO
instances where $G$ does not contain any $k$-clique of weight at most $W$.

######  Definition 4 (Min-weight-$k$-clique).

Given a graph $G$ with integer edge weights and a weight threshold $W$,
determine whether $G$ has a $k$-clique with weight at most $W$ or not.

The naive algorithm for both problems requires enumerating all $\binom{N}{k}$
subsets of vertices of size $k$, and this takes time $O(N^{k})$. In the case
of the $k$-clique conjecture, slightly faster algorithms that run in time
$O(N^{\omega k/3})$ are known [NP85], where $\omega<2.373$ is the matrix
multiplication constant. However, no non-trivial algorithms are known for the
weighted $k$-clique problem. It is conjectured that the problem of finding the
minimum weight $k$-clique requires time $N^{k-o(1)}$ [Wil18].

Under the min-weight $k$-clique hypothesis, Backurs and Tzamos [BT17] showed
that the classical Viterbi algorithm for finding the most likely path in a
Hidden Markov Model is in fact optimal. Under this hypothesis, tight lower
bounds are also known for the the local alignment problem [AWW14] from
computational biology and the Maximum Weight Rectangle problem [BDT16] from
computational geometry.

######  Definition 5 (Min-weight $k$-clique hypothesis).

The Min-Weight $k$-Clique problem on $N$ node graphs with edge weights in
$\\{-N^{100k},\ldots,N^{100k}\\}$ requires (randomized) $N^{k-o(1)}$ time.

We note that the following variants of the min-weight $k$-clique problem are
as hard as the original one. First, we can assume that the edges are non-
negative and in the range $\\{1,\ldots,2N^{100k}+1\\}$. To see this, let
$w^{*}$ be the minimum weight of the edges in a graph. Create a new graph
$G^{\prime}$ with the same vertex and edge sets. The edge weights of
$G^{\prime}$ are obtained by adding $|w^{*}|+1$ to the weight of the
corresponding edge in $G$. Then $G^{\prime}$ has a $k$-clique of weight at
most $W+\binom{k}{2}(|w^{*}|+1)$, if and only if $G$ has a $k$-clique of
weight at most $W$.

Secondly, we can assume that there is a partition of the vertex set into $k$
subsets such that the $k$-clique has one vertex from each subset. To see this,
suppose there is a $k$-clique $K$ in $G$ with weight at most $W$. Then, we
claim that we can assume that the vertex set $V$ is partitioned into $k$
subsets $V=V_{1}\cup\ldots,V_{k}$ such $|K\cap V_{i}|=1$ for all
$i\in\\{1,\ldots,k\\}$. To see this, randomly partition the vertices into $k$
subsets, by assigning each vertex to a subset uniformly and independently at
random. Then, for any given $k$-clique (and in particular, the min-weight
one), the probability that it has exactly one vertex in each subset is
$\prod_{i=0}^{k-1}\left(\frac{k-i}{k}\right)=\frac{k!}{k^{k}}$, which is at
least $\sqrt{2\pi k}\cdot e^{-k}\cdot e^{\frac{1}{12k+1}}>e^{-k}$ by
Stirling’s formula. Repeating this $O(e^{k})$ many times completes the
argument. Note that although the number of repetitions is exponential in $k$,
it is independent of $N$, and so is sufficient for our purposes.

###  2.3 The closest vector problem

A lattice $\mathcal{L}$ is the set of the integer linear combinations of a set
of linearly independent vectors (a basis)
$\mathbf{B}=(\mathbf{b}_{1},\mathbf{b}_{2},\ldots,\mathbf{b}_{n})$ where each
$\mathbf{b}_{i}\in\mathbb{R}^{d}$:

$\mathcal{L}=\mathcal{L}(\mathbf{B})=\left\\{\mathbf{B}\mathbf{z}\mid\mathbf{z}\in\mathbb{Z}^{n}\right\\}.$

Given a lattice basis $\mathbf{B}$, and a target vector $\mathbf{t}$, define
$\operatorname{dist}_{p}(\mathcal{L}(\mathbf{B}),\mathbf{t})=\min_{\mathbf{x}\in\mathcal{L}(\mathbf{B})}\|\mathbf{x}-\mathbf{t}\|_{p}$
to be the minimum $\ell_{p}$ distance from $\mathbf{t}$ to
$\mathcal{L}=\mathcal{L}(\mathbf{B})$.

We follow [BGS17] for definitions of lattice problems.

######  Definition 6 ($\gamma$-approximate Closest Vector Problem with respect
to the $\ell_{p}$ norm ($\gamma$-$\text{CVP}_{p}$)).

For any $\gamma\geq 1$ and $1\leq p\leq\infty$, given a lattice $\mathcal{L}$
(specified by its basis $\mathbf{B}\in\mathbb{R}^{d\times n}$), a target
vector $\mathbf{t}\in\mathbb{R}^{n}$ and a number $r>0$, distinguish between a
YES instance, where $\operatorname{dist}_{p}(\mathcal{L},\mathbf{t})\leq r$
and a NO instance, where
$\operatorname{dist}_{p}(\mathcal{L},\mathbf{t})>\gamma r$.

We refer to the exact version of the problem, when $\gamma=1$, as
$\text{CVP}_{p}$.

The best known algorithm for exact CVP2 runs in time $2^{n+o(n)}$ time
[ADS15]. However, for $p\neq 2$, the best known algorithms for CVPp are
slower, i.e., they run in time $n^{O(n)}$ [Kan83, MW14]. Bennett, Golovnev and
Stephens-Davidowitz [BGS17] proved an SETH-based hardness bound for the
Closest Vector Problem. In particular, for many $p$, including odd integers
$p\geq 1$ and $p=\infty$, they show that $\text{CVP}_{p}$ cannot be solved in
time $2^{(1-\epsilon)n}$ for any $\epsilon>0$, unless the Strong Exponential
Time Hypothesis (SETH) is false.

######  Theorem 1 (SETH-hardness of CVPp [BGS17]).

For every $\epsilon>0$ and every integer $p\geq 1,p\notin 2\mathbb{Z}$ there
is no $2^{(1-\epsilon)n}$ algorithm for CVPp, unless SETH is false.

CVP with preprocessing (CVPP) refers to algorithms for the closest vector
problem which are allowed an unbounded-time offline preprocessing phase where
they get the basis $\mathbf{B}$, and are required to be fast only in an online
phase where they receive the target vector $\mathbf{t}$ and the distance
threshold $r$. Aggarwal, Bennett, Golovnev and Stephens-Davidowitz show the
following hardness results for CVPPp.

######  Theorem 2 ([ABGSD21]).

For every $\epsilon>0$ and every integer $p\geq 1,p\notin 2\mathbb{Z}$ there
is no $2^{(1-\epsilon)n}$ algorithm for CVPPp, unless non-uniform SETH is
false.

Examining their proof more carefully, we notice that they prove a stronger
result. In particular, they show SETH-hardness of the following problem, which
we refer to as $(0,1)$-$\text{CVP}_{p}$.

######  Definition 7 ($(0,1)$-$\text{CVP}_{p}$).

For any $1\leq p\leq\infty$, the $(0,1)$-Closest Vector Problem with respect
to the $\ell_{p}$ norm is the following promise problem. Given a lattice
$\mathcal{L}$ specified by a basis $\mathbf{B}\in\mathbb{R}^{d\times n}$, a
target vector $\mathbf{t}\in\mathbb{R}^{d}$ and two numbers $r,\tau>0$,
distinguish between the following two cases:

  * •

YES instances, where there exists some $\mathbf{y}^{*}\in\\{0,1\\}^{n}$ such
that $\|\mathbf{B}\mathbf{y}^{*}-\mathbf{t}\|\leq r$; and

  * •

NO instances, where for all $\mathbf{y}\in\mathbb{Z}^{n}$,
$\|\mathbf{B}\mathbf{y}-\mathbf{t}\|\geq r+\tau.$

Their method does not show hardness of $\text{CVP}_{2}$ (or
$(0,1)$-$\text{CVP}_{2}$). On the other hand, to the best of our knowledge,
there is no $2^{(1-\epsilon)n}$-time algorithm for $(0,1)$-CVP2 for any
$\epsilon>0$. Indeed, as we observe in Section A, such an algorithm would
imply a better algorithm for Weighted Max-Cut.

##  3 Optimal worst-case hardness of sparse linear regression under the min-
weight $k$-clique hypothesis

The main result of this section is the theorem below, which shows that there
are no better-than-brute-force algorithms for worst-case sparse linear
regression, unless the Min-weight $k$-clique conjecture is false.

######  Theorem 3.

For any integer $k\geq 4$, the $k$-SLR problem in the Euclidean ($\ell_{2}$)
norm requires $N^{k-o(1)}$ (randomized) time, unless the Min-Weight $k$-clique
conjecture is false.

###### Proof.

We give a reduction from any Min-weight $k$-clique instance $G=(V,E)$ with
positive edge weights to a $k$-SLR2 instance $(\mathbf{A},\mathbf{b},\delta)$
as follows. First, we set large numbers $\alpha$ and $\beta$, whose
significance will be clear in the sequel:

$\alpha=\sqrt{\max\left\\{1,\sum_{e\in
E}w_{e}+8W\right\\}},\quad\beta=\sqrt{\sum_{e\in
E}w_{e}+8W+\alpha^{2}Z}\cdot\max\left\\{8Z,50\left(\alpha^{2}Z+\sum_{e\in
E}w_{e}\right)\right\\},$

where we define $Z=\left|\\{(u,v)\notin E\mid u,v\in V\\}\right|$ to be the
number of non-edges in the graph $G$.

We enumerate the unordered pairs of vertices $(u_{i_{1}},u_{i_{2}})$ with
index $i\in\left[\binom{N}{2}\right]$ where $u_{i_{1}},u_{i_{2}}\in V$. Let
edge $e$ have weight $w_{e}$. We first describe how we construct
$\mathbf{A},\mathbf{b}$ which have the following structure:

$\mathbf{A}=\begin{pmatrix}\mathbf{C}\\\
\mathbf{D}\end{pmatrix},\quad\mathbf{b}=\begin{pmatrix}\mathbf{c}\\\
\mathbf{d}\end{pmatrix}$

The submatrix $\mathbf{C}\in\mathbb{R}^{\binom{N}{2}\times N}$ contains one
row for each unordered pair of vertices and one column for each vertex in $V$.
This submatrix $\mathbf{C}$, along with the target subvector
$\mathbf{c}\in\mathbb{R}^{\binom{N}{2}}$, encodes the $k$-clique instance. The
submatrix $\mathbf{D}\in\mathbb{R}^{k\times N}$ and its corresponding target
vector $\mathbf{d}\in\mathbb{R}^{k}$ ensure that any solution must have
exactly $k$ non-zero entries, all of which are close to $1$.

For each unordered pair of vertices $(u_{i_{1}},u_{i_{2}})\notin E$
corresponding to a non-edge, we add a row to the matrix $\mathbf{C}$, and a
corresponding entry in the target vector $\mathbf{c}$.

$\mathbf{C}_{i,j}=\begin{dcases}2\alpha&\mbox{for }j\in\\{i_{1},i_{2}\\}\\\
0&\text{otherwise}\end{dcases},\quad\mathbf{c}_{i}=\alpha$

where the large number $\alpha$ is defined above.

For each $e_{i}=(u_{i_{1}},u_{i_{2}})$ with weight $w_{e_{i}}>0$, we add a row
to $\mathbf{C}$ and a corresponding entry in the target subvector
$\mathbf{c}$.

$\mathbf{C}_{i,j}=\begin{dcases}2\sqrt{w_{e_{i}}}&\mbox{for
}j\in\\{i_{1},i_{2}\\}\\\
0&\text{otherwise}\end{dcases},\quad\mathbf{c}_{i}=\sqrt{w_{e_{i}}}$

As described in Section 2.2, we can assume that we know a partition of the $N$
vertices into $k$ blocks of size $N/k$ such that if a $k$-clique with weight
at most $W$ exists, then there is such a $k$-clique with exactly one vertex in
each block. We order the vertices such that the first $N/k$ vertices belong to
the first block, the second $N/k$ vertices belong to the second block, and so
one. Let $\mathbf{1}\in\mathbb{R}^{N/k}$ to be the all $1$’s row vector. Then,
we construct $\mathbf{D}$ and $\mathbf{d}$ to each have $k$ rows.

$\mathbf{D}=\begin{pmatrix}\beta\mathbf{1}&\mathbf{0}&\ldots&\mathbf{0}\\\
\mathbf{0}&\beta\mathbf{1}&\ldots&\mathbf{0}\\\
\mathbf{0}&\mathbf{0}&\ldots&\beta\mathbf{1}\end{pmatrix},\quad\mathbf{d}=\begin{pmatrix}\beta\\\
\vdots\\\ \beta\end{pmatrix}$

Finally, set $\delta>0$ such that $\delta=\sqrt{\sum_{e\in
E}w_{e}+8W+\alpha^{2}Z}$.

We first prove completeness. In other words, if there is a $k$-clique of
weight at most $W$, then we construct a vector $\mathbf{x}\in\mathbb{R}^{N}$
such that $\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_{2}\leq\delta$. We index
entries of $\mathbf{x}$ by the vertices in $G$ that they correspond to.
Suppose $G$ contains a $k$-clique $\widetilde{K}$ of weight $\widetilde{W}\leq
W$. Set $x_{u}=1$ if vertex $u\in K$, and otherwise set $x_{u}=0$.

From this definition, we see that for each non-edge, the contribution of the
corresponding row to the error $\|\mathbf{A}\mathbf{x}-\mathbf{b}\|^{2}_{2}$
is $\alpha^{2}$, since $\widetilde{K}$ cannot contain both endpoints of any
non-edge. For each edge $e\in E$ such that $e$ is not in the clique
$\widetilde{K}$, the contribution is $w_{e}$. For each edge $e$ in
$\widetilde{K}$, the contribution is
$(4\sqrt{w_{e}}-\sqrt{w_{e}})^{2}=9w_{e}$. Since $\widetilde{K}$ is a
$k$-clique with one vertex in each of the $k$ blocks,
$\|\mathbf{D}\mathbf{x}-\mathbf{d}\|_{2}=0$. This gives that

$\displaystyle\|\mathbf{A}\mathbf{x}-\mathbf{b}\|^{2}_{2}=\sum_{e\notin\widetilde{K}}w_{e}+\sum_{e\in\widetilde{K}}9w_{e}+\alpha^{2}Z$
$\displaystyle=\sum_{e\in E}w_{e}+\sum_{e\in\widetilde{K}}8w_{e}+\alpha^{2}Z$
$\displaystyle=\sum_{e\in E}w_{e}+8\widetilde{W}+\alpha^{2}Z\leq\delta^{2}$

Now, we show soundness. In other words, if there is some $\mathbf{x}^{*}$ such
that $\|\mathbf{A}\mathbf{x}^{*}-\mathbf{b}\|_{2}\leq\delta$, then there must
be a $k$-clique in $G$ of weight at most $W$.

We show that the only possible such $\mathbf{x}^{*}$ are those that have
exactly $k$ non-zero entries, one in each block of $\mathbf{x}^{*}$, with each
non-zero entry being very close to $1$. Suppose for contradiction that one
block of $\mathbf{x}^{*}$ does not have any non-zero entries. Then by the
choice of $\beta$, we know that
$\|\mathbf{A}\mathbf{x}^{*}-\mathbf{b}\|_{2}\geq\beta>\delta$. Since
$\mathbf{x}^{*}$ is $k$-sparse, this implies that each block has exactly one
non-zero entry. Now, suppose for contradiction that $\mathbf{x}^{*}$ has some
non-zero entry $x^{*}_{u}$ outside the interval
$\left[1-2\delta/\beta,1+2\delta/\beta\right]$, then

$\|\mathbf{A}\mathbf{x}^{*}-\mathbf{b}\|_{2}\geq|\beta(x^{*}_{u}-1)|\geq
2\delta>\delta.$

So all non-zero entries of $\mathbf{x}^{*}$ have to be in
$\left[1-2\delta/\beta,1+2\delta/\beta\right]$.

Now we claim that these $k$ non-zero entries have to correspond to a
$k$-clique in the graph. Suppose for contradiction that there are two non-zero
entries $x^{*}_{u},x^{*}_{v}$ such that $(u,v)\notin E$. Then, counting the
error term from rows corresponding to the other $Z-1$ non-edges as well,

$\displaystyle\|\mathbf{A}\mathbf{x}^{*}-\mathbf{b}\|^{2}_{2}$
$\displaystyle\geq(2\alpha x^{*}_{u}+2\alpha
x^{*}_{v}-\alpha)^{2}+\left(2\alpha(1-2\delta/\beta)-\alpha\right)^{2}(Z-1)$
$\displaystyle\geq\alpha^{2}\left(4\left(1-2\delta/\beta\right)-1\right)^{2}+\alpha^{2}\left(2(1-2\delta/\beta)-1\right)^{2}(Z-1)$
$\displaystyle=\alpha^{2}\left[\left(1-\frac{4\delta}{\beta}\right)^{2}(Z-1)+\left(3-\frac{8\delta}{\beta}\right)^{2}\right]$
$\displaystyle\geq\alpha^{2}\left[\left(9-\frac{48\delta}{\beta}\right)+\left(1-\frac{8\delta}{\beta}\right)(Z-1)\right]$
$\displaystyle\geq\alpha^{2}\left[Z+8-\frac{8\delta
Z}{\beta}-\frac{48\delta}{\beta}\right]\geq\alpha^{2}(Z+6)>\delta^{2}$

Finally, we show that the clique $\widetilde{K}$ so obtained has weight at
most $W$. We can give upper and lower bounds to
$\widetilde{\delta}^{2}\coloneqq\|\mathbf{A}\mathbf{x}^{*}-\mathbf{b}\|^{2}_{2}$
as follows. By assumption, $\widetilde{\delta}^{2}\leq\delta^{2}=\sum_{e\in
E}w_{e}+8W+\alpha^{2}Z$.

Now, to give a lower bound, consider the contribution to the error
$\widetilde{\delta}^{2}$ from each type of row. For non-edges, each
corresponding row contributes at least
$\left(2\alpha(1-2\delta/\beta)-\alpha\right)^{2}$. For each edge
$e\notin\widetilde{K}$, the corresponding row contributes at least
$\left(2(1-2\delta/\beta)-1\right)^{2}w_{e}$. For each edge
$e\in\widetilde{K}$, the corresponding row contributes at least
$\left(4(1-2\delta/\beta)-1\right)^{2}w_{e}$. From this, we get

$\displaystyle\widetilde{\delta}^{2}$
$\displaystyle\geq\left(2\alpha(1-2\delta/\beta)-\alpha\right)^{2}Z+\sum_{e\notin\widetilde{K}}\left(2(1-2\delta/\beta)-1\right)^{2}w_{e}+\sum_{e\in\widetilde{K}}\left(4(1-2\delta/\beta)-1\right)^{2}w_{e}$
$\displaystyle=\left(\alpha^{2}Z+\sum_{e\notin\widetilde{K}}w_{e}\right)\left(1-\frac{4\delta}{\beta}\right)^{2}+\sum_{e\in\widetilde{K}}w_{e}\left(3-\frac{8\delta}{\beta}\right)^{2}$
$\displaystyle\geq\left(\alpha^{2}Z+\sum_{e\notin\widetilde{K}}w_{e}\right)\left(1-\frac{8\delta}{\beta}\right)+\sum_{e\in\widetilde{K}}w_{e}\left(9-\frac{48\delta}{\beta}\right)$
$\displaystyle\geq\left(\alpha^{2}Z+\sum_{e\in
E}w_{e}\right)\left(1-\frac{48\delta}{\beta}\right)+8\sum_{e\notin\widetilde{K}}w_{e}$

From these two bounds we get that

$\frac{48\delta}{\beta}\left(\alpha^{2}Z+\sum_{e\in E}w_{e}\right)+8W\geq
8\sum_{e\in\widetilde{K}}w_{e}$

Since $\beta\geq 50\delta\left(\alpha^{2}Z+\sum_{e\in E}w_{e}\right)$, and the
edge weights and the threshold $W$ are all integers, we get that

$W\geq\sum_{e\in\widetilde{K}}w_{e}$

The runtime of this reduction is $O(N^{3})$, so if there is an algorithm that
solves $k$-sparse linear regression in the $2$-norm in time $N^{k-\epsilon}$
for some $\epsilon>0$, then this reduction gives an algorithm that runs in
time $N^{3}+N^{k-\epsilon}=O(N^{k-\epsilon})$ for Min-weight $k$-clique when
$k\geq 4$. This completes the proof. ∎

##  4 Optimal worst-case hardness of sparse linear regression under the
hardness of lattice problems

Our main theorem in this section is a fine-grained reduction from the closest
vector problem (CVP) in any norm to sparse linear regression (SLR) over the
same norm. Using Theorem 1, a corollary is that unless the strong exponential
hypothesis (SETH) is false, there is no algorithm for $k$-$\mbox{SLR}_{p}$
(defined on odd norms) that runs in time better than $N^{(1-\epsilon)k}$ for
any constant $\epsilon>0$.

While CVP and SLR look similar at a high level, our reduction has to bridge a
significant difference between the problems: SLR refers to sparse solutions
over $\mathbb{R}$, whereas CVP refers to unrestricted solutions over
$\mathbb{Z}$.

######  Theorem 4.

For any integer $k\geq 2$ and $1\leq p\leq\infty$, there is an efficient
reduction from $(0,1)$-$\text{CVP}_{p}$ on a lattice with rank $n$ and ambient
dimension $d$ to $k$-$\mbox{SLR}_{p}$ on a matrix of dimensions $(d+k)\times
k\cdot 2^{n/k}$.

It follows that if, for any $\epsilon>0$, there is a $N^{(1-\epsilon)k}$-time
algorithm for $k$-$\mbox{SLR}_{p}$ then there is a $2^{(1-\epsilon)n}$-time
algorithm for $(0,1)$-$\text{CVP}_{p}$.

###### Proof.

Given a $(0,1)$-$\text{CVP}_{p}$ instance consisting of a lattice basis
$\mathbf{B}\in\mathbb{R}^{d\times n}$, a target vector
$\mathbf{y}\in\mathbb{R}^{d}$, and two numbers $r,\tau>0$, we construct the
$k$-$\mbox{SLR}_{p}$ instance $(\mathbf{A},\mathbf{b},\delta)$ as follows. We
set $\delta=r$ and partition the columns of $\mathbf{B}$ into $k$ groups
$\mathbf{B}_{1},\ldots,\mathbf{B}_{k}$, each of size at most $\lceil
n/k\rceil$.

$\mathbf{B}=\begin{pmatrix}\mathbf{B}_{1}&\ldots&\mathbf{B}_{k}\end{pmatrix}$

Construct $\mathbf{A}_{i}\in\mathbb{R}^{d\times 2^{n/k}}$ for $i=1$ to $k$
such that the columns of $\mathbf{A}_{i}$ are formed by summing all possible
$2^{n/k}$ subsets of the columns in $\mathbf{B}_{i}$. Define
$\mathbf{1}\in\mathbb{R}^{1\times 2^{n/k}}$ to be the row vector of all $1$’s,
and let $\alpha\in\mathbb{R}$ be some large number to be determined.

$\mathbf{A}=\begin{pmatrix}\mathbf{A}_{1}&\mathbf{A}_{2}&\ldots&\mathbf{A}_{k}\\\
\alpha\mathbf{1}&\mathbf{0}&\ldots&\mathbf{0}\\\
\mathbf{0}&\alpha\mathbf{1}&\ldots&\mathbf{0}\\\
\mathbf{0}&\mathbf{0}&\ldots&\alpha\mathbf{1}\end{pmatrix},\quad\mathbf{b}=\begin{pmatrix}\mathbf{t}\\\
\alpha\\\ \vdots\\\ \alpha\end{pmatrix}$

Suppose the $(0,1)$-$\text{CVP}_{p}$ instance is a YES instance, that is,
there is some $\mathbf{y}^{*}\in\\{0,1\\}^{n}$ such that
$\|\mathbf{B}\mathbf{y}^{*}-\mathbf{t}\|_{p}\leq r$. Then there is a
$k$-sparse $\mathbf{x}^{*}$ that can be directly computed from
$\mathbf{y}^{*}$ as follows.

$x^{*}_{S}=\begin{dcases}1&\mbox{if }y^{*}_{i}=1\text{ for all }i\in S\mbox{
and }y^{*}_{i}=0\text{ for all }i\notin S\\\ 0&\text{ otherwise}\end{dcases}$

Here we have indexed the entries in $\mathbf{x}^{*}$ by the subset
$S\subset[(i-1)n/k+1,in/k]$ of columns it corresponds to in $\mathbf{B}$,
where $i$ is the block number. The $\mathbf{x}_{S}^{*}$ makes the $k$-SLR
instance a YES instance since

$\|\mathbf{A}\mathbf{x}^{*}-\mathbf{b}\|_{p}=\|\mathbf{B}\mathbf{y}^{*}-\mathbf{t}\|_{p}\leq
r=\delta$

Now, suppose that the $k$-$\mbox{SLR}_{p}$ instance we reduced to is a YES
instance. That is, there is some $\mathbf{x}^{*}$ such that
$\|\mathbf{A}\mathbf{x}^{*}-\mathbf{b}\|_{p}\leq\delta$. We show that the only
possible such solutions are those which have exactly $k$ non-zero entries, one
in each block of $\mathbf{x}^{*}$, and that these non-zero entries have to be
close to $1$. Suppose for contradiction that one block of $\mathbf{x}^{*}$
does not have any non-zero entries, so it is the all-zero vector. Then
$\|\mathbf{A}\mathbf{x}^{*}-\mathbf{b}\|_{p}\geq\alpha>\delta$. So by the
$k$-sparsity of $\mathbf{x}^{*}$, each of its blocks has exactly one non-zero
entry.

Now suppose there is some non-zero entry ${x}^{*}_{i}$ of $\mathbf{x}^{*}$
that is outside the interval
$\left[1-\frac{2\delta}{\alpha},1+\frac{2\delta}{\alpha}\right]$. Then

$\|\mathbf{A}\mathbf{x}^{*}-\mathbf{b}\|_{p}\geq|\alpha(x^{*}_{i}-1)|\geq
2\delta>\delta.$

Therefore we need to consider only the case where each non-zero entry of
$\mathbf{x}^{*}$ is within the interval
$\left[1-\frac{2\delta}{\alpha},1+\frac{2\delta}{\alpha}\right]$.

Consider the vector ${\overline{\mathbf{x}}}^{*}$ obtained by rounding the
entries of $\mathbf{x}^{*}$ to either $0$ or $1$.

${\overline{x}}^{*}_{i}=\begin{dcases}1&{x}^{*}_{i}\neq 0\\\
0&{x}^{*}_{i}=0\end{dcases}$

We can construct a solution $\mathbf{y}^{*}$ to the $(0,1)$-CVPp instance as
follows.

${y}^{*}_{i}=\begin{dcases}1&\text{there is some }S\text{ such that
}\overline{x}^{*}_{S}=1\\\ 0&\text{otherwise}\end{dcases}$

$\displaystyle\|\mathbf{B}\mathbf{y}^{*}-\mathbf{t}\|_{p}$
$\displaystyle=\|\mathbf{A}{\overline{\mathbf{x}}}^{*}-\mathbf{b}\|_{p}$
$\displaystyle\leq\|\mathbf{A}{\overline{\mathbf{x}}}^{*}-\mathbf{A}\mathbf{x}^{*}\|_{p}+\|\mathbf{A}\mathbf{x}^{*}-\mathbf{b}\|_{p}$
$\displaystyle\leq\|\mathbf{A}\|_{p}\cdot k\cdot\frac{2\delta}{\alpha}+\delta$
$\displaystyle\leq\|\mathbf{B}\|_{p}\cdot n\cdot\frac{2\delta}{\alpha}+\delta$
$\displaystyle<r+\tau$

for any value of $\tau$, by setting
$\alpha=\frac{4\delta}{\tau}\cdot\|\mathbf{B}\|_{p}\cdot n$ to be large
enough. Here, $\|\mathbf{B}\|_{p}:=\max_{i\in[n]}\|\mathbf{b}_{i}\|_{p}$,
where $\mathbf{b}_{i}$ are the columns of $\mathbf{B}$.

Since $\|\mathbf{B}\mathbf{y}^{*}-\mathbf{t}\|_{p}<r+\tau$, by the promise of
the $(0,1)$-CVP problem, it must be the case that

$\|\mathbf{B}\mathbf{y}^{*}-\mathbf{t}\|_{p}\leq r,$

making $(\mathbf{B},\mathbf{t},\delta)$ a YES instance of the CVP problem.
This reduction takes time $O\left(d\cdot k\cdot 2^{n/k}\right)$, and so if
there is an algorithm that solves $k$-SLRp in time $N^{(1-\epsilon)k}$, then
this reduction gives us an algorithm for $(0,1)$-CVPp that runs in time
$(k\cdot 2^{n/k})^{(1-\epsilon)k}=O(2^{(1-\epsilon)n})$. This completes the
proof. ∎

The same reduction, combined with the result by Aggarwal et al. [ABGSD21],
gives the following hardness result for sparse linear regression in the
$p$-norm with pre-processing.

######  Corollary 1.

If there is an algorithm that solves $k$-SLRp for odd norms $p$ with
preprocessing in time better than $N^{(1-\epsilon)k}$ for some $\epsilon>0$,
then SETH is false.

##  5 SETH-hardness of $2$-SLR

Here we define the Orthogonal Vectors problem (OV), and show that a
subquadratic algorithm for $2$-sparse linear regression in the $2$-norm
violates the Orthogonal Vectors Hypothesis and, by a result of [Wil04], the
strong exponential time hypothesis.

Let $d=\omega(n)$. Given two sets $U,V$ of $d$-dimensional vectors with $0,1$
entries, where $|U|=|V|=n$, distinguish between:

  * •

YES instances, where there are vectors $\mathbf{u}\in U$ and $\mathbf{v}\in V$
s.t.
$\langle\mathbf{u},\mathbf{v}\rangle:=\sum_{i=1}^{d}\mathbf{u}[i]\mathbf{v}[i]=0$;
and

  * •

NO instances, where no such pair of vectors exists.

The naive brute force algorithm runs in time $O(n^{2}d)$ time, and no
algorithm that runs in time $n^{2-\epsilon}\operatorname{poly}(d)$ is known,
for any $\epsilon>0$. The OV Hypothesis states that this algorithm is
essentially optimal, and is implied by both SETH and the Min-Weight $k$-Clique
conjecture [Wil04, ABDN18].

######  Definition 8 (Orthogonal Vectors Hypothesis).

No randomized algorithm can solve OV on instances of size $n$ in
$n^{2-\epsilon}\operatorname{poly}(d)$ time for constant $\epsilon>0$.

The Orthogonal Vectors Hypothesis is implied by the strong exponential time
hypothesis, as the following theorem states.

######  Theorem 5 (SETH-hardness of Orthogonal Vectors [WY14]).

If there is an algorithm that solves OV in
$n^{2-\epsilon}\operatorname{poly}(d)$ time, for some $\epsilon>0$ then SETH
is false.

With this background, we are ready to state our main result of this section,
and its corollary, which guarantees the hardness of $2$-sparse linear
regression under SETH or the weaker Orthogonal Vectors Hypothesis.

######  Proposition 1.

There is an efficient reduction from Orthogonal Vectors with $2$ sets of $n$
vectors from $\\{0,1\\}^{d}$ to $2$-sparse linear regression in the $2$-norm,
with a $(d+2)\times 2n$ design matrix.

######  Corollary 2.

Suppose there is an algorithm that can solve $2$-sparse linear regression in
time $n^{2-\epsilon}\operatorname{poly}(d)$ for some $\epsilon>0$. Then, the
Orthogonal Vectors Hypothesis and SETH are false.

#### Other Results.

In Appendix A, we recall a folklore fine-grained reduction from the max-cut
problem on weighted undirected graphs to the CVP problem in the $\ell_{2}$
norm [ABGSD21]. In turn, this shows that solving $k$-SLR in
$N^{(1-\epsilon)k}$ time implies a corresponding speedup for the weighted max-
cut problem, which is believed to be hard [Wil04].

#### An Open Problem.

It remains open to show that $k$-SLR in the $\ell_{2}$ norm is optimally hard
assuming the strong exponential hypothesis (SETH).

#### Acknowledgements.

The first author would like to thank David Jerison, Frederic Koehler, Kerri Lu
and Ankur Moitra for discussions on the problem of sparse linear regression.
We thank Noah Stephens-Davidowitz for pointing us to the connection between
maxcut and CVP [ABGSD21] and for his comments on the manuscript.

## References

  * [ABDN18] Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof.  More consequences of falsifying seth and the orthogonal vectors conjecture.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 253–266, 2018.
  * [ABGSD21] Divesh Aggarwal, Huck Bennett, Alexander Golovnev, and Noah Stephens-Davidowitz.  Fine-grained hardness of cvp (p)—everything that we can prove (and nothing else).  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1816–1835. SIAM, 2021.
  * [ADS15] Divesh Aggarwal, Daniel Dadush, and Noah Stephens-Davidowitz.  Solving the closest vector problem in 2^n time - the discrete gaussian strikes again!  In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 563–582. IEEE Computer Society, 2015.
  * [AWW14] Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann.  Consequences of faster alignment of sequences.  In International Colloquium on Automata, Languages, and Programming, pages 39–51. Springer, 2014.
  * [BDT16] Arturs Backurs, Nishanth Dikkala, and Christos Tzamos.  Tight hardness results for maximum weight rectangles.  In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016\.
  * [BGS17] Huck Bennett, Alexander Golovnev, and Noah Stephen-Davidowitz.  On the quantitative hardness of cvp.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 13–24. IEEE, 2017.
  * [BIS17] Arturs Backurs, Piotr Indyk, and Ludwig Schmidt.  On the fine-grained complexity of empirical risk minimization: Kernel methods and neural networks.  In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 4308–4318, 2017.
  * [BRST20] Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang.  Continuous LWE.  CoRR, abs/2005.09595, 2020.
  * [BT17] Arturs Backurs and Christos Tzamos.  Improving viterbi is hard: Better runtimes imply faster clique algorithms.  In International Conference on Machine Learning, pages 311–321. PMLR, 2017.
  * [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.
  * [DMA97] Geoff Davis, Stephane Mallat, and Marco Avellaneda.  Adaptive greedy approximations.  Constructive approximation, 13(1):57–98, 1997.
  * [FKT15] Dean Foster, Howard Karloff, and Justin Thaler.  Variable selection is hard.  In Conference on Learning Theory, pages 696–709. PMLR, 2015.
  * [GL20] Aparna Gupte and Kerri Lu.  Fine-grained complexity of sparse linear regression.  2020\.
  * [HPIM18] Sariel Har-Peled, Piotr Indyk, and Sepideh Mahabadi.  Approximate Sparse Linear Regression.  In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 77:1–77:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [IP01] Russell Impagliazzo and Ramamohan Paturi.  On the complexity of k-sat.  Journal of Computer and System Sciences, 62(2):367–375, 2001.
  * [Kan83] Ravi Kannan.  Improved algorithms for integer programming and related lattice problems.  In David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas, editors, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 193–206. ACM, 1983.
  * [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.
  * [MG02] Daniele Micciancio and Shafi Goldwasser.  Complexity of Lattice Problems: a cryptographic perspective, volume 671 of The Kluwer International Series in Engineering and Computer Science.  Kluwer Academic Publishers, Boston, Massachusetts, March 2002.
  * [Min10] Hermann Minkowski.  The Geometry of Numbers.  Leopold Classic Library, 1910.
  * [MW14] Daniele Micciancio and Michael Walter.  Fast lattice point enumeration with minimal overhead.  In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 276–294. SIAM, 2014.
  * [Nat95] Balas Kausik Natarajan.  Sparse approximate solutions to linear systems.  SIAM journal on computing, 24(2):227–234, 1995.
  * [NP85] Jaroslav Nešetřil and Svatopluk Poljak.  On the complexity of the subgraph problem.  Commentationes Mathematicae Universitatis Carolinae, 26(2):415–419, 1985.
  * [Tib96] Robert Tibshirani.  Regression shrinkage and selection via the lasso.  Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288, 1996.
  * [Wil04] Ryan Williams.  A new algorithm for optimal constraint satisfaction and its implications.  In International Colloquium on Automata, Languages, and Programming, pages 1227–1237. Springer, 2004.
  * [Wil18] Virginia Vassilevska Williams.  On some fine-grained questions in algorithms and complexity.  In Proceedings of the ICM, volume 3, pages 3431–3472. World Scientific, 2018.
  * [WY14] Ryan Williams and Huacheng Yu.  Finding orthogonal vectors in discrete structures.  In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1867–1877. SIAM, 2014.
  * [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 Reduction from Weighted Max-cut to CVP

In this section, we define the weighted max-cut problem, and recall a
reduction that shows how any improvement in algorithms for the closest vector
problem in the $\ell_{2}$-norm would imply a better algorithm for weighted
max-cut than what is currently known. This reduction, along with Theorem 4
gives further evidence of the $N^{k}$-hardness of the $k$-sparse linear
regression problem in the $\ell_{2}$-norm.

Suppose we are given a weighted undirected graph $G=(V,E)$ and a weight
function $w:E\rightarrow\mathbb{Z}^{+}$, where edge $e_{i,j}\in E$ between
vertices $u_{i},u_{j}\in V$ has weight $w(e_{i,j})$. The maxcut problem asks
to find a partition of the vertices so that the cut between them has the
largest weight. More precisely, define the quantity

$\mathsf{Maxcut}(G):=\max_{\mathbf{x}\in\\{-1,+1\\}^{n}}\sum_{i,j}(1-x_{i}x_{j})\cdot
w(e_{ij})$

######  Definition 9 (Weighted Max-Cut).

Given a weighted undirected graph $G=(V,E)$ on $|V|=n$ vertices, where edge
$e\in E$ has weight $w_{e}\in\mathbb{Z}^{+}$, and a weight threshold $W$,
distinguish between a YES instance, where $\mathsf{Maxcut}(G)\geq W$ and a NO
instance, where $\mathsf{Maxcut}(G)<W$.

The naive enumeration algorithm runs in time $2^{n}$, and an improvement to
even $2^{(1-\epsilon)n}$ for any $\epsilon>0$ would be surprising [Wil04].

######  Theorem 6.

There is an efficient reduction from the weighted max-cut problem on a graph
of $n$ vertices to the $(0,1)$-closest vector problem in the $\ell_{2}$-norm
on an $n$ dimensional lattice.

###### Proof.

Suppose we are given an instance consisting of a graph $G=(V,E)$, and a weight
threshold $W$ of Max-cut. Suppose that $G$ has $|V|=n$ vertices and $|E|=m$
edges. We index edges $e_{i}\in E$ with the index $i\in[m]$. We index vertices
$u_{j}\in V$ with $j\in[n]$. We construct an instance
$(\mathbf{B},\mathbf{t},r,\tau)$ of $(0,1)$-CVP2 as follows.

$\mathbf{B}=\begin{pmatrix}\mathbf{C}\\\
\mathbf{D}\end{pmatrix},\quad\mathbf{t}=\begin{pmatrix}\mathbf{c}\\\
\mathbf{d}\end{pmatrix},\quad r^{2}=\sum_{e\in
E}w_{e}-W+n\alpha^{2},\quad\tau=\sqrt{r^{2}+1}-r$

For each edge $e_{i}=(u_{j_{1}},u_{j_{2}})\in E$ with edge $w_{e_{i}}$, we add
a row (the $i$th row) to the matrix $\mathbf{B}_{1}\in\mathbb{R}^{m\times n}$.
The entries of the $i$th row, and the corresponding entry in the target vector
$\mathbf{c}$ is defined by

$\mathbf{C}_{i,j}=\begin{dcases}\sqrt{w_{e_{i}}}&j\in\\{j_{1},j_{2}\\}\\\
0&\text{otherwise}\end{dcases},\quad\mathbf{c}_{i}=\sqrt{w_{e_{i}}}.$

Also, let $\mathbf{D}=2\alpha I_{n}\in\mathbb{R}^{n\times n}$, where
$\alpha=\sqrt{2\sum_{e\in E}w_{e}}$ and $I_{n}$ is the $n\times n$ identity
matrix. Let $\mathbf{d}=\alpha\mathbf{1}\in\mathbb{R}^{n}$ be the all ones
column vector of dimension $n$.

First, we show completeness. Suppose there is a cut $V_{1}\cup V_{2}=V$ of
weight at least $W$, and define the set of edges in the cut as
$C=\\{e=(u,v)\in E\mid u\in V_{1},v\in V_{2}\text{ or }u\in V_{2},v\in
V_{1}\\}$. Then, construct the vector $\mathbf{y}$ as follows.

$y_{j}=\begin{dcases}1&u_{j}\in V_{1}\\\ 0&u_{j}\in V_{2}\end{dcases}$

Then

$\displaystyle\|\mathbf{B}\mathbf{y}-\mathbf{t}\|^{2}_{2}$
$\displaystyle=\sum_{e=(u,v)\notin C}w_{e}+n\alpha^{2}$
$\displaystyle\leq\sum_{e\in E}w_{e}-W+n\alpha^{2}=r^{2}.$

Further, because of the integrality condition on the weights of the graph
edges, it is true for any vector $\mathbf{y}$ that either
$\|\mathbf{B}\mathbf{y}-\mathbf{t}\|_{2}\leq r$ or
$\|\mathbf{B}\mathbf{y}-\mathbf{t}\|_{2}\geq r+\tau$.

Now, we show soundness. Suppose there is some vector
$\mathbf{y}^{*}\in\mathbb{Z}^{n}$ such that
$\|\mathbf{B}\mathbf{y}^{*}-\mathbf{t}\|_{2}\leq r$. We show that this implies
$\mathsf{Maxcut}(G)\geq W$. Setting $\alpha^{2}=2\sum_{e\in E}w_{e}$, we see
that only solutions $\mathbf{y}^{*}\in\\{0,1\\}^{n}$ are possible. Then define
a partition on the vertex set $V=V^{*}_{1}\cup V^{*}_{2}$ such that
$V^{*}_{1}=\\{u_{j}\mid y^{*}_{j}=1\\}$ and $V^{*}_{2}=V\setminus
V^{*}_{1}=\\{u_{j}\mid y^{*}_{j}=0\\}$. Let $C^{*}=\\{e=(u,v)\in E\mid u\in
V^{*}_{1},v\in V^{*}_{2}\text{ or }u\in V^{*}_{2},v\in V^{*}_{1}\\}$ be the
cut defined by this partition. Let the weight of the cut $C^{*}$ be $W^{*}$.
Then, we see that

$\displaystyle\|\mathbf{B}\mathbf{y}^{*}-\mathbf{t}\|^{2}_{2}$
$\displaystyle=\sum_{e=(u,v)\notin C^{*}}w_{e}+n\alpha^{2}=\sum_{e\in
E}w_{e}-W^{*}+n\alpha^{2}\leq r^{2},$

and so $W^{*}\geq W$.

This reduction runs in time $O\left(n(m+n)\right)\leq O(n^{3})$, and this
completes the proof. ∎

######  Corollary 3.

If there is some $\epsilon>0$ such that $(0,1)$-CVP in the $\ell_{2}$ can be
solved in time $2^{(1-\epsilon)n}$, then there is an algorithm that solves
weighted max-cut in time $2^{(1-\epsilon)n}$.

##  Appendix B Proof for Section 5

###### Proof for Proposition 1.

We give a reduction from OV to $2$-sparse linear regression in the $2$-norm.
Suppose we are given an OV instance consisting of two sets $U,V$ of
$d$-dimensional vectors $\mathbf{u}_{1},\ldots,\mathbf{u}_{n}\in U$ and
$\mathbf{v}_{1},\ldots,\mathbf{v}_{n}\in V$, each of size $n$. Define the
normalized vectors
$\mathbf{u}^{\prime}_{i}=\frac{1}{\|\mathbf{u}_{i}\|}\mathbf{u}_{i}$ and
$\mathbf{v}^{\prime}_{i}=\frac{1}{\|\mathbf{v}_{i}\|}\mathbf{v}_{i}$ such that
$\|\mathbf{u}^{\prime}_{i}\|_{2}=\|\mathbf{v}^{\prime}_{i}\|_{2}=1$ for all
$i\in\\{1,\ldots,n\\}$. Then construct an instance
$(\mathbf{A},\mathbf{b},\delta)$ of $2$-sparse linear regression as follows.

$\mathbf{A}=\begin{pmatrix}|&&|&|&&|\\\
\mathbf{u}^{\prime}_{1}&\ldots&\mathbf{u}^{\prime}_{n}&\mathbf{v}^{\prime}_{1}&\ldots&\mathbf{v}^{\prime}_{n}\\\
|&&|&|&&|\\\ \alpha&\ldots&\alpha&\alpha&\ldots&\alpha\\\
0&\ldots&0&0&\ldots&0\end{pmatrix},\quad b=\begin{pmatrix}0\\\ \vdots\\\ 0\\\
\alpha\\\ \alpha\end{pmatrix},\quad\delta=\sqrt{2},$

where we set $\alpha=16\delta d$, whose significance will become clear later.

We first show completeness. Suppose there are two vectors $\mathbf{u}_{i}\in
U,\mathbf{v}_{j}\in V$ such that
$\left\langle\mathbf{u}_{i},\mathbf{v}_{j}\right\rangle=\left\langle\mathbf{u}^{\prime}_{i},\mathbf{v}^{\prime}_{j}\right\rangle=0$.
Then, construct the vector $\mathbf{x}\in\mathbb{R}^{2n}$ such that

$x_{\ell}=\begin{dcases}1&\ell\in\\{i,n+j\\}\\\
0&\text{otherwise}\end{dcases}.$

Then
$\|\mathbf{A}\mathbf{x}-\mathbf{b}\|^{2}_{2}=\|\mathbf{u}^{\prime}_{i}+\mathbf{v}^{\prime}_{j}\|^{2}_{2}=\|\mathbf{u}^{\prime}_{i}\|^{2}_{2}+\|\mathbf{v}^{\prime}_{j}\|^{2}_{2}+2\left\langle\mathbf{u}^{\prime}_{i},\mathbf{v}^{\prime}_{j}\right\rangle=2=\delta^{2}$.

We now show soundness. Suppose that there is some vector
$\mathbf{x}\in\mathbb{R}^{2n}$ such that
$\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_{2}\leq\delta$. First, we claim that
$\mathbf{x}$ must have at least one non-zero entry indexed from the index set
$I_{1}:=\\{1,\ldots,n\\}$, and at least one non-zero entry indexed from
$I_{2}:=\\{n+1\ldots,2n\\}$. Suppose for contradiction that $x_{i}=0$ for all
$i\in I_{1}$. Then, $\|\mathbf{A}\mathbf{x}-\mathbf{b}\|\geq\alpha>\delta$.
Using a similar argument for $I_{2}$, and because $\mathbf{x}$ is $2$-sparse,
we know that $\mathbf{x}$ must have exactly two non-zero entries, one indexed
from each of $I_{1}$ and $I_{2}$. Let the two non-zero entries be $x_{i}$ and
$x_{j}$, with $i\in I_{1}$ and $j\in I_{2}$.

Next, we claim that the two non-zero entries have to be close to $1$.
Specifically, $x_{i},x_{j}\in\left[1-2\delta/\alpha,1+2\delta/\alpha\right]$.
Otherwise, we get a contradiction since
$\|\mathbf{A}\mathbf{x}-\mathbf{b}\|\geq 2\delta$.

Note that since the vectors of the OV instance $\mathbf{u}\in U,\mathbf{v}\in
V$ have $0,1$ entries, we know that either
$\langle\mathbf{u},\mathbf{v}\rangle=0$ or
$\langle\mathbf{u},\mathbf{v}\rangle\geq 1$. Translating this to a statement
about the normalized vectors, we know that either
$\left\langle\mathbf{u}^{\prime}_{i},\mathbf{v}^{\prime}_{j}\right\rangle=0$
or
$\left\langle\mathbf{u}^{\prime}_{i},\mathbf{v}^{\prime}_{j}\right\rangle\geq
1/d$.

Now, we can lower and upper bound the prediction error
$\|\mathbf{A}\mathbf{x}-\mathbf{b}\|$ as follows. By assumption, we know that
$\|\mathbf{A}\mathbf{x}-\mathbf{b}\|^{2}\leq\delta^{2}=2$. Further,

$\displaystyle\|\mathbf{A}\mathbf{x}-\mathbf{b}\|^{2}$
$\displaystyle\geq\|x_{i}\mathbf{u}^{\prime}_{i}+x_{j}\mathbf{v}^{\prime}_{j}\|^{2}=x^{2}_{i}\|\mathbf{u}^{\prime}_{i}\|^{2}+x^{2}_{j}\|\mathbf{v}^{\prime}_{j}\|^{2}+2x_{i}x_{j}\left\langle\mathbf{u}^{\prime}_{i},\mathbf{v}^{\prime}_{j}\right\rangle=x_{i}^{2}+x^{2}_{j}+2x_{i}x_{j}\left\langle\mathbf{u}^{\prime}_{i},\mathbf{v}^{\prime}_{j}\right\rangle$
$\displaystyle\geq
2\left(1-\frac{2\delta}{\alpha}\right)^{2}+2\left(1-\frac{2\delta}{\alpha}\right)^{2}\left\langle\mathbf{u}^{\prime}_{i},\mathbf{v}^{\prime}_{j}\right\rangle\geq
2\left(1-\frac{4\delta}{\alpha}\right)+2\left(1-\frac{4\delta}{\alpha}\right)\left\langle\mathbf{u}^{\prime}_{i},\mathbf{v}^{\prime}_{j}\right\rangle$
$\displaystyle\geq
2\left(1-\frac{4\delta}{\alpha}\right)+\left\langle\mathbf{u}^{\prime}_{i},\mathbf{v}^{\prime}_{j}\right\rangle.$

Combining the upper and lower bounds from above,
$\left\langle\mathbf{u}^{\prime}_{i},\mathbf{v}^{\prime}_{j}\right\rangle\leq\frac{8\delta}{\alpha}=\frac{1}{2d}<1/d$.
So, it must be true that
$\left\langle\mathbf{u}^{\prime}_{i},\mathbf{v}^{\prime}_{j}\right\rangle=0$,
and so there is an orthogonal pair of vectors.

This reduction runs in time $O(nd)$ time, so an algorithm that solves
$2$-sparse linear regression in time $O(N^{2-\epsilon})$ for some $\epsilon>0$
will solve OV in time $O(n^{2-\epsilon})$. This completes the proof. ∎