稀疏线性回归的特征自适应

May, 2023

Feature Adaptation for Sparse Linear Regression

Jonathan Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi

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

Abstract

sparse linear regression is a central problem in high-dimensional statistics. We study the correlated random design setting, where the covariates are drawn from a multivariate Gaussian $N(0,\Sigma)$, and we seek

sparse linear regression correlated random design lasso algorithm sample complexity ill-conditioned covariates

发现论文，激发创造

带潜变量的套索：高效估计、协变量缩放和计算统计差距

稀疏线性回归中的相关性以及智能缩放解决方案

Feb, 2024

稀疏线性回归中的不当学习的计算统计差距

我们研究了稀疏线性回归的计算统计缺口，证明了这个问题需要至少大约 k^2 个样本才能有效解决，并且还应用于稀疏 PCA 问题的降低及低阶下界。

Feb, 2024

稀疏回归：可扩展的算法和实证表现

本文回顾了特征选择领域内应用最广的方法，重点关注其精度和误检探测率随着样本数量增加的表现，并对比了常用的 Lasso 正则化方法以外，不太为人所知的非凸罚函数方法。通过实证分析，我们发现整数规划方案及其布尔松弛具有更优的性能表现，但相应的计算成本也更高。考虑到准确率、假检率和计算时间等综合评估因素，本文揭示了一些不同的特征选择方案，为相关领域的研究提供了参考依据。

Feb, 2019

流式稀疏回归的统计学

本文介绍一种基于稀疏近似的随机梯度下降算法，该算法能够在类似 Lasso 的条件下表现良好，并且无需更多的计算资源。在实验中，我们发现我们的方法在真实数据和模拟数据上均表现出色。

Dec, 2014

高维数据的稀疏表示 Lasso 型恢复

本文主要研究了在高维数据下 Lasso 作为一种正则化和变量选择技术的一些性质，特别关注了 Lasso 在松弛 irrepresentable 条件之后的一些表现，包括一些适用于固定设计的条件以及一些收敛性的结果。最后，文章通过天体物理学中相邻频率的检测问题进行了结果论证。

Jun, 2008

利用 L1 回归进行对抗稀疏噪声的压缩感知

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

Sep, 2018

关于鲁棒线性回归的高效算法及下界

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

May, 2018

稳健稀疏优化的难度和算法

研究稀疏优化问题中的算法和局限性，探索稀疏线性回归和鲁棒线性回归问题，在此基础上展示了鲁棒回归问题的二准则、NP - 近似困难性，给出了一个使用近似最近邻数据结构的鲁棒回归算法，并且介绍了一个从鲁棒线性回归到稀疏线性回归的通用带宽率约化算法。

Jun, 2022

自适应特征选择：基于 RIP 的在线稀疏线性回归的计算有效性

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

Jun, 2017

稀疏线性回归与格问题

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

Feb, 2024