论文标题
坚固和稀疏优化的硬度和算法
Hardness and Algorithms for Robust and Sparse Optimization
论文作者
论文摘要
我们探索稀疏优化问题的算法和局限性，例如稀疏线性回归和鲁棒线性回归。稀疏线性回归问题的目的是确定少数关键特征，而强大的线性回归问题的目标是确定少量错误的测量值。 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强大的线性回归问题寻求最多忽略$ k $行的集合$ s $和一个向量$ x $，以最小化$ \ |（ax-b）_s \ | _2 $。 我们首先显示了在[OWZ15]的工作上稳健回归构建的近似值的双晶格，这意味着稀疏回归的结果相似。通过减少$ k $ clique的猜想，我们进一步显示了稳健回归的细粒硬度。在正面，我们给出了一种鲁棒回归的算法，该算法可实现任意准确的添加误差，并使用运行时与从细颗粒硬度结果中的下限紧密匹配的运行时，以及具有相似运行时稀疏回归的算法。我们的上限和下限都取决于从鲁棒线性回归到我们引入的稀疏回归的一般减少。我们的算法受到3SUM问题的启发，使用近似最近的邻居数据结构，并且可能具有独立的兴趣来解决稀疏优化问题。例如，我们证明我们的技术也可以用于研究良好的稀疏PCA问题。
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.
