本文研究高维统计中的稀疏线性回归问题,特别关注相关随机设计条件下的 Lasso 算法以及基于特征适应的算法,提供了可以自适应处理少量近似相关性的 Lasso 算法优化及多项式复杂度的改进,以实现在常数稀疏度和任意协方差 Σ 情况下的最优样本复杂度。
May, 2023
研究了高维线性回归在对抗性污染下的稳健模型问题,并针对从高斯分布生成的未被修正的样本的基本情况给出了几乎最紧的上界和计算下界。
May, 2018
通过复杂性理论的标准假设(NP 不在 P/poly),我们证明了稀疏线性回归的极小化预测风险可以由多项式时间算法实现,但实际上实现优化算法时,二者之间存在差距。特别是在设计矩阵不良条件下,多项式时间算法可以实现的极小化预测损失可能会明显高于优化算法。这是首个已知的多项式和最优算法在稀疏线性回归中的差距,而且不依赖于平均时间复杂度的猜想。
Feb, 2014
研究怎样在不假设样本的基础分布为高斯分布的前提下,只假定有限个矩的情况下,有效地进行线性回归和协方差估计,并关注能用多少样本来实现高精度和指数级成功概率。使用八阶圆当量半定规划提供算法,预备性的证据表明在我们的算法使用的平均中位数框架中无法在多项式时间内改善这些误差率。
Dec, 2019
本文研究在高维度及受到恶意破坏性干扰情况下,稀疏估计任务能否有效地完成,并提供了一些在存在噪音的情况下,提供非平凡误差保证的有效算法。研究表明,在这些问题上存在着计算与统计之间的差距。
Feb, 2017
研究稀疏优化问题中的算法和局限性,探索稀疏线性回归和鲁棒线性回归问题,在此基础上展示了鲁棒回归问题的二准则、NP - 近似困难性,给出了一个使用近似最近邻数据结构的鲁棒回归算法,并且介绍了一个从鲁棒线性回归到稀疏线性回归的通用带宽率约化算法。
Jun, 2022
在本文中,我们重新考虑了局部差分隐私(LDP)模型下稀疏线性回归的问题。我们提出了一种创新的非交互式局部差分隐私(NLDP)算法,该算法在数据服从亚高斯分布的情况下,为估计误差提供了上界,并且在服务器有额外公开但未标记数据的情况下,误差上界可以进一步提高。我们还研究了序贯交互式 LDP 模型,并发现了非私有情况、中心差分隐私模型和局部差分隐私模型在稀疏线性回归问题上的基本差异。
Oct, 2023
本文介绍了一种用于在线稀疏线性回归问题的算法,并在每次迭代时使用多项式时间限制来使遗憾较小。结果证明对于任何常数 δ> 0,没有算法可以使遗憾在 O (T ^(1-δ)) 以内,即使允许算法访问比最佳稀疏线性回归器更多的特征。
Mar, 2016
稀疏线性回归中的相关性以及智能缩放解决方案
Feb, 2024
本文提出了一种简单的平均值估计方法,可以在 moderate 条件下克服现有估计器面临的计算和统计问题,并基于增量学习现象推导出匹配信息理论下界。