Feb, 2014

稀疏线性回归问题多项式时间算法性能下界

PDF
TL;DR通过复杂性理论的标准假设（NP 不在 P/poly），我们证明了稀疏线性回归的极小化预测风险可以由多项式时间算法实现，但实际上实现优化算法时，二者之间存在差距。特别是在设计矩阵不良条件下，多项式时间算法可以实现的极小化预测损失可能会明显高于优化算法。这是首个已知的多项式和最优算法在稀疏线性回归中的差距，而且不依赖于平均时间复杂度的猜想。
发现论文，激发创造
  • 在线稀疏线性回归

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

    Mar, 2016

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

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

    Feb, 2024

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

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

    Jun, 2022

  • 广义线性模型中的隐私成本：算法与极小极大下界

    使用构建的差分隐私版本的梯度下降算法，针对低维和高维稀疏广义线性模型提出参数估计，通过表征统计学性能和建立 GLMs 的隐私约束极小值下界来显示所提算法的近乎速率最优性。

    Nov, 2020

  • 线性最小二乘的确切极小极大风险及样本协方差矩阵的下尾

    通过研究新颖的偏尾分析技巧，我们在随机设计的线性预测和相关问题上考虑最小化期望风险。我们发现，当每个样本所代表的统计杠杆得分在高斯设计时是最小的。我们通过控制经验过程的 PAC-Bayes 技术扩展了 Oliveira 的分析。

    Dec, 2019

  • Slope meets Lasso: 改进的正则界和最优性

    该研究介绍了两种计算方法，分别是自适应选择调整参数的 Lasso 估计器和 Slope 估计器，可以在满足限制特征值条件和更多约束条件的情况下，在高维线性回归上实现准确的最小化预测和 l2 估计率。

    May, 2016

  • 高维非参数回归的极小极大优化

    在两个稀疏假设下，推导了高维非参数回归的最小 $L_2$ 风险；通过区分特征重要性和局部平滑度，将贝叶斯高斯过程回归方法扩展到稀疏加性模型，实现自适应最优的最小极值。

    Jan, 2014

  • 稀疏主成分分析在高维带噪数据下的极小极大界

    本文研究了基于独立的高斯观测量对高维种群协方差矩阵的主导特征向量的估计问题，建立了 $l_2$ 损失下估计量最小风险的极小界，并提出了一种新的二阶段坐标选择方案的特征向量估计方法。

    Mar, 2012

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

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

    May, 2023

  • 高维线性回归在 Lq - 球上的极小极大估计率

    本文研究了标准线性回归模型的极小极大收敛速度，证明在合适的设计矩阵正则化条件下，最小值误差在 $L_2$-，$L_{oldsymbol r}$- 损失和 $L_{oldsymbol 2}$- 预测损失内达到了收缩速度。同时，我们提供了 $L_{oldsymbol r}$- 范数的极小极大风险下限。

    Oct, 2009