探讨了在普通最小二乘回归中，找到或推翻删除数据集中的小子集会反转系数符号的实用算法；通过实证研究了用于此任务的成熟算法技术在一般线性回归问题和特殊情况下的精确贪婪方法方面的性能，证明这些方法在几个维度的回归问题中优于现有技术并提供了实用的鲁棒性检查；但对于维度为 3 或更高的回归问题中推翻这种小型影响样本存在性的重要任务仍存在显著的计算瓶颈；通过使用源自算法稳健统计的最新创新思想的谱算法在这一挑战中取得了一些进展；总结了在几个挑战数据集中，已知技术的限制，以促进进一步的算法创新。

Jul, 2023

本文研究高维统计中的稀疏线性回归问题，特别关注相关随机设计条件下的 Lasso 算法以及基于特征适应的算法，提供了可以自适应处理少量近似相关性的 Lasso 算法优化及多项式复杂度的改进，以实现在常数稀疏度和任意协方差 Σ 情况下的最优样本复杂度。

May, 2023

该论文介绍了在观察到一个 m x p 的矩阵 B 和目标向量 y 的情况下，如何找到一个稀疏向量 x，使得 Bx 等于 y 的近似解，给出了该问题不存在多项式时间算法的证明，并对该问题的统计版本进行了类似的证明。

Dec, 2014

稀疏线性回归（SLR）是一个在统计学中研究得很多的问题，在该问题中，给定一个设计矩阵 X 和一个响应向量 y，目标是寻找一个最小化均方预测误差的 k - 稀疏向量 hat (theta)，该问题在设计矩阵良好条件下可以通过 L1 松弛方法解决，本文提供了关于所有有效算法的平均情况困难性证据，并基于格问题的最差情况困难性给出了 SLR 的平均情况困难性证据，同时还讨论了可辨别与不可辨别的情形。

Feb, 2024

本文旨在设计一个在线学习算法，使其具有次线性失望成本并且具有计算效率，以适应在线稀疏线性回归问题。通过利用数据矩阵满足受限等距性质的假设，针对两个问题变体，证明了这个假设可以导致计算效率高的在线学习算法。第一个变体中，真实标签根据带有加性高斯噪声的稀疏线性模型生成，而在第二个变体中，真实标签由对手选择。

Jun, 2017

本文介绍了一种用于在线稀疏线性回归问题的算法，并在每次迭代时使用多项式时间限制来使遗憾较小。结果证明对于任何常数 δ> 0，没有算法可以使遗憾在 O (T ^（1-δ）) 以内，即使允许算法访问比最佳稀疏线性回归器更多的特征。

Mar, 2016

提出了一种用于高维度稀疏回归中具有常量分数的自变量和 / 或响应变量的污染的算法，它是迄今为止的首个这样的算法，利用使用这种算法，我们提供了强健的稀疏回归方法和过滤算法。

May, 2018

本文证明了 Lasso 的鲁棒性质，并将其与物理属性，即对噪声的保护，联系起来。通过考虑不同的不确定性集合，可以得出 Lasso 的一般化形式并获得凸优化问题。同时，通过鲁棒性质可以解释为何 Lasso 解是稀疏的，并且与标准稀疏结果不同。最后，证明了稀疏性和算法稳定性是相互矛盾的，因此 Lasso 是不稳定的。

Nov, 2008

研究了高维线性回归在对抗性污染下的稳健模型问题，并针对从高斯分布生成的未被修正的样本的基本情况给出了几乎最紧的上界和计算下界。

May, 2018

本文提供了一个简单有效的算法来解决稀疏鲁棒线性回归问题，即从被稀疏噪声干扰的线性测量中估计一个稀疏的向量，对于高斯测量，基于 L1 回归的简单算法可以成功地估计任何小于 0.239 的锁定率，而该算法所需的测量数为 O (klog (n/k)) 个，能够同时估计稀疏和稠密的 w*，容忍大常数分数的离群值和对抗性而非分配性（例如，高斯）稠密噪声。

Sep, 2018