Lower Bounds on Randomly Preconditioned Lasso via Robust Sparse Designs
Lower Bounds on Randomly Preconditioned Lasso via Robust Sparse Designs
复制标题
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Jonathan A. Kelner;Frederic Koehler;Raghu Meka;Dhruv Rohatgi
中科院分区：
文献类型：
--
作者：
Jonathan A. Kelner;Frederic Koehler;Raghu Meka;Dhruv Rohatgi
稀疏的线性回归具有不良条件的高斯随机协变量被认为存在是存在的统计/计算差距，但令人惊讶的是，这种信念的正式证据很少。套索程序无法成功地在稀疏的信号上成功使用了sublerear数量的样本，但是，这种下限仅适用于确定性的预处理，并且在许多情况下，随机化对预处理的成功至关重要。对于适当的协方差矩阵，我们构建了一个单一的信号分布，任何可转化的套索程序都以高概率失败，除非它收到了线性的样本。在压缩的情况下，我们研究了一些稀疏的信号，当时我们的知识尚未研究这种自然问题。对抗性擦除的强大到固定：如果删除了B测量值，则信号坐标的所有除O（b）都是可以识别的。
Sparse linear regression with ill-conditioned Gaussian random covariates is widely believed to exhibit a statistical/computational gap, but there is surprisingly little formal evidence for this belief. Recent work has shown that, for certain covariance matrices, the broad class of Preconditioned Lasso programs provably cannot succeed on polylogarithmically sparse signals with a sublinear number of samples. However, this lower bound only holds against deterministic preconditioners, and in many contexts randomization is crucial to the success of preconditioners. We prove a stronger lower bound that rules out randomized preconditioners. For an appropriate covariance matrix, we construct a single signal distribution on which any invertibly-preconditioned Lasso program fails with high probability, unless it receives a linear number of samples. Surprisingly, at the heart of our lower bound is a new robustness result in compressed sensing. In particular, we study recovering a sparse signal when a few measurements can be erased adversarially. To our knowledge, this natural question has not been studied before for sparse measurements. We surprisingly show that standard sparse Bernoulli measurements are almost-optimally robust to adversarial erasures: if b measurements are erased, then all but O ( b ) of the coordinates of the signal are identifiable.