Hardness and Algorithms for Robust and Sparse Optimization
We explore algorithms and limitations for sparse optimization problems such
as sparse linear regression and robust linear regression. The goal of the
sparse linear regression problem is to identify a small number of key features,
while the goal of the robust linear regression problem is to identify a small
number of erroneous measurements. Specifically, the sparse linear regression
problem seeks a $k$-sparse vector $x\in\mathbb{R}^d$ to minimize $\|Ax-b\|_2$,
given an input matrix $A\in\mathbb{R}^{n\times d}$ and a target vector
$b\in\mathbb{R}^n$, while the robust linear regression problem seeks a set $S$
that ignores at most $k$ rows and a vector $x$ to minimize $\|(Ax-b)_S\|_2$.
  We first show bicriteria, NP-hardness of approximation for robust regression
building on the work of [OWZ15] which implies a similar result for sparse
regression. We further show fine-grained hardness of robust regression through
a reduction from the minimum-weight $k$-clique conjecture. On the positive
side, we give an algorithm for robust regression that achieves arbitrarily
accurate additive error and uses runtime that closely matches the lower bound
from the fine-grained hardness result, as well as an algorithm for sparse
regression with similar runtime. Both our upper and lower bounds rely on a
general reduction from robust linear regression to sparse regression that we
introduce. Our algorithms, inspired by the 3SUM problem, use approximate
nearest neighbor data structures and may be of independent interest for solving
sparse optimization problems. For instance, we demonstrate that our techniques
can also be used for the well-studied sparse PCA problem.