ICMLJun, 2018

用 Orlicz 范数进行子空间嵌入和线性回归

PDF
TL;DR本文针对经典线性回归问题进行推广，研究了 Orlicz 范数的损失函数，并提出了一种新的盲嵌入，用于将具有 Orlicz 范数的矩阵空间嵌入到具有二范数的较低维空间，从而得到回归问题和低秩矩阵逼近问题的近似算法。
orlicz normlinear regressionembedding matrixapproximation algorithmlow rank matrix approximation
发现论文，激发创造
  • 线性草图的高效对称范数回归

    提供了高效的算法来解决超定的线性回归问题，其中损失函数是对称范数（在符号反转和坐标置换下不变的范数），当损失函数为 Orlicz 范数时，算法产生一个 (1+ε)- 近似解，在输入稀疏时间内改进了先前已知的算法。

    Oct, 2019

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

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

    May, 2013

  • 输入稀疏时间内低失真子空间嵌入及其在鲁棒线性回归中的应用

    提出了一种低失真度嵌入方法，在线性代数问题中得到广泛应用，支持 l_2 误差损失最小回归以及 (1±ε) 失真度的 l_p 子空间嵌入，包括一种基于输入稀疏性的 l_p 子空间采样过程。

    Oct, 2012

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

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

    Jul, 2012

  • 非线性变换下的子空间嵌入

    给出了第一个关于非线性函数类的低失真嵌入，并将其应用于压缩感知和生成型神经网络，以达到线性问题的非线性转化。

    Oct, 2020

  • 稳定秩下的最优近似矩阵乘积

    用子空间嵌入保证黑盒方式证明，通过降维映射可实现近似矩阵乘法的谱范数保障，其中降维映射具有 O（~r/ε^2）行，且优于以前的工作 [MZ11，KVZ14]，对于任何混淆的降维映射也是最佳的。

    Jul, 2015

  • 正则化最小二乘算法的 Sobolev 范数学习率

    本文针对最小二乘回归中的 $L_2$-norms，将其扩展至更强的 norms，而无需将回归函数包含在假设空间中。特别地，在用作假设空间的 Sobolev 重现核希尔伯特空间的特殊情况下，这些更强的 norms 与所使用的 Sobolev 空间和 $L_2$ 之间的分数 Sobolev norms 一致，从技术角度来看，我们将已知的积分算子技术与内嵌属性相结合，这种方法迄今仅在经验过程论证明中使用过。这种组合结果产生了相对于更强的 norms 的新的有限样本边界。从这些有限样本边界出发可以轻松得出我们的学习率。最后，我们证明了在许多情况下我们的结果的渐近最优性。

    Feb, 2017

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

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

    Oct, 2015

  • 矩阵近似乘法及其在线性嵌入方面的应用

    该论文研究了计算两个实矩阵乘积的近似算法，提出了核秩的概念，并应用于线性低维嵌入中，使得任何核秩有界的欧几里得点集能够在独立于输入维度的投影空间上实现加性误差保证。

    Mar, 2014

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

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

    May, 2018