关于 $\ell_p$ 灵敏度抽样的更严格界限
近期在降维回归任务中引入了敏感性的概念,提供了通过子采样移除低敏感性数据点后的近似质量的可证明保证。本文提供了计算给定矩阵的相关汇总统计量和近似敏感性的高效算法,分别针对不同的 Lp 范数进行了泛化,并通过实验表明,实际数据集的敏感性远远小于理论预测,展示了实际数据集的低内在有效维度。
Nov, 2023
我们研究数据选择问题,将利用 $k$-means 聚类和敏感性抽样方法,基于模型损失的嵌入表示,可选择一组典型样本,其平均损失与整个数据集的平均损失相对应,具有可证明的性质,并且在微调基础模型上表现优于最先进的方法,同时展示了它如何应用于线性回归,提供了一个更简单且可扩展性更强的抽样策略。
Feb, 2024
提出了一种低失真度嵌入方法,在线性代数问题中得到广泛应用,支持 l_2 误差损失最小回归以及 (1±ε) 失真度的 l_p 子空间嵌入,包括一种基于输入稀疏性的 l_p 子空间采样过程。
Oct, 2012
研究了多维欧氏空间中寻找一个 k 维子空间 F,使得一组 n 个点到该子空间的 p 次方欧氏距离和最小的问题。进一步探讨了在某些损失函数 M ()(如 Huber 和 Tukey 损失函数)下此问题的最优解。这些鲁棒子空间可替代奇异值分解(SVD)提供更有效的解决方案,对于典型的 M-Estimators,对离群值的鲁棒性更强。本文给出了一些这些鲁棒子空间逼近问题的算法和难度结果。
Oct, 2015
研究子空间草图问题,通过构建一个小空间数据结构压缩给定矩阵,讨论其压缩方案和所需存储空间以及相应的下界,探讨其在矩阵乘积中的应用,展示了对内积基于任意数构建数据结构的不可行性以及 l1 奇异值分解的不同情况下的空间复杂度变化。
Apr, 2019
针对高维线性回归模型的参数拟合问题,考虑基于 Lasso 惩罚的最小二乘估计器的置信区间和 p 值的构造及去偏的版本,进一步在随机设计模型的情形下进行研究,并提出了更优的平均检测功率的分析结果。
Nov, 2013
我们展示了如何通过将边际杠杆得分抽样与促进空间覆盖的非独立抽样策略相结合,从而在不知情(对抗性噪声)设置中获得改进的主动学习方法。我们提出了一个简单实现的基于关键抽样算法的方法,并在基于学习的参数化 PDEs 和不确定性量化的问题上进行了测试。与独立抽样相比,我们的方法将达到给定目标精度所需的样本数量减少了最多 50%。我们用两个理论结果支持了我们的发现。首先,我们证明了任何满足弱单向的离散 l∞独立条件(其中包括关键抽样)的非独立杠杆得分抽样方法可以以 O (dlogd) 的样本主动学习 d 维线性函数,与独立抽样相匹配。这个结果扩展了最近关于 l∞独立性下矩阵 Chernoff 界的工作,并可能对分析关键抽样之外的其他抽样策略感兴趣。其次,我们证明了对于多项式回归的重要案例,我们的关键方法获得了 O (d) 的改进界。
Oct, 2023
本文研究使用凸松弛法解决高维机器学习问题时,统计与计算的权衡。对稀疏主成分分析(Sparse PCA)问题和 Sum-of-Squares(即 Lasserre / Parillo)凸松弛法进行了探究。通过研究发现基于次数 - 4 的 SoS 算法不能改善计算次数为 k² 的情况,为这种强大的凸松弛算法族中的一部分问题建立了平均情况下的下限,说明它们存在困难问题。
Jul, 2015