Nov, 2023

计算近似的 ℓp 敏感度

PDF
TL;DR近期在降维回归任务中引入了敏感性的概念，提供了通过子采样移除低敏感性数据点后的近似质量的可证明保证。本文提供了计算给定矩阵的相关汇总统计量和近似敏感性的高效算法，分别针对不同的 Lp 范数进行了泛化，并通过实验表明，实际数据集的敏感性远远小于理论预测，展示了实际数据集的低内在有效维度。
dimensionality reductionsensitivityapproximationregression tasksmatrix
发现论文，激发创造
  • 关于 $\ell_p$ 灵敏度抽样的更严格界限

    该研究对 $ell_p$ 子空间嵌入的灵敏度取样提供了新的理论边界，为许多具有小 $ell_p$ 灵敏度的结构矩阵提供了最佳已知的样本复杂度。

    Jun, 2023

  • 通过 L2 增强实现 Lp 敏感性采样的最优界限

    数据子采样是一种近似大规模数据集的自然方法，该论文提出了一种敏感性采样方法，并改进了子空间嵌入和逻辑回归中的采样复杂度。

    Jun, 2024

  • 高维回归假设检验的几乎最优样本大小

    针对高维线性回归模型的参数拟合问题，考虑基于 Lasso 惩罚的最小二乘估计器的置信区间和 p 值的构造及去偏的版本，进一步在随机设计模型的情形下进行研究，并提出了更优的平均检测功率的分析结果。

    Nov, 2013

  • 半监督学习中基于 $\ell_p$ 的拉普拉斯正则化的渐近行为

    以 $L_p$-Laplacian 正则化为基础的半监督学习算法采用 $d$ 维几何随机图模型给出了理论推导，证明了当 $N$ 趋于无穷大而 $n$ 保持不变时， 估计函数的性能，证明了在 $P$ 的敏感度和置信度之间存在权衡，表明选择 $p = d +1$ 是最优的选择。

    Mar, 2016

  • 指数随机变量的子空间嵌入和 Lp 回归

    本文从子空间嵌入的角度出发，提出了一种构造常数扭曲率子空间嵌入的新方法，并将其应用于线性回归问题以及分布式计算中。

    May, 2013

  • 基于 Lewis 加权子采样的 L1 回归

    考虑了只观察到少量标签时，寻找 l1 回归的近似解的问题。我们表明，根据其 Lewis 权重对 X 进行采样并输出经验最小化器可在概率 1-δ 下成功地进行，其中 m>O（1/ε²dlog (d/εδ)）。我们还给出了相应的下界。

    May, 2021

  • 强健子空间逼近的输入稀疏度和难度

    研究了多维欧氏空间中寻找一个 k 维子空间 F，使得一组 n 个点到该子空间的 p 次方欧氏距离和最小的问题。进一步探讨了在某些损失函数 M ()（如 Huber 和 Tukey 损失函数）下此问题的最优解。这些鲁棒子空间可替代奇异值分解（SVD）提供更有效的解决方案，对于典型的 M-Estimators，对离群值的鲁棒性更强。本文给出了一些这些鲁棒子空间逼近问题的算法和难度结果。

    Oct, 2015

  • 基于良好条件基础的 Minkowski $p$- 范数流式和分布式摘要

    本文研究了适用于不同的 lP 范数的近似线性代数问题，提出了一种同时适用于每个 p ≥ 1 的确定性算法，并将其应用于多种问题，如 lP 回归，逐元素 l1 低秩逼近和近似矩阵乘法。

    Jul, 2018

  • 输入稀疏时间内的低秩逼近和回归

    本文提出了一种新的稀疏嵌入矩阵，通过使用这种矩阵，可以实现超约束最小二乘回归、低秩逼近、所有梁角得分的近似和 $l_p$- 回归问题的 $(1+\varepsilon)$- 近似，其时间复杂度的主导项是 $O (\nnz (A))$ 或 $O (\nnz (A)\log n)$。

    Jul, 2012

  • 迭代行采样

    该研究提出新的算法解决回归问题中的稀疏数据，基于迭代法中计算行重要性（行杠杆力分数）的方法，达到比现有技术更好的理论保证。

    Nov, 2012