Jul, 2023

高效强多项式算法用于分位数回归

PDF
TL;DR本文提出了针对 Quantile Regression 的多个高效确定性和随机多项式算法，连接到 k 集的几何概念和随机分治算法，分别解决了二维和多维 Quantile Regression 问题。
linear regressionquantile regressionpolynomial algorithmsgeometric conceptrandomized divide-and-conquer
发现论文，激发创造
  • 大规模应用的分位数回归

    提出一种随机算法来处理大规模数据量的分位数回归问题，该算法在近线性时间内计算给定分位数回归问题的（1+ϵ）近似解，并计算量子回归损失函数的低失真子空间保持嵌入。

    May, 2013

  • 重访线性回归的量子算法：无数据依赖参数的二次加速

    线性回归是最基本的线性代数问题之一，本研究提出了一个运行时间为 O (ε^(-1) * sqrt (n) * d^(1.5)) + poly (d/ε) 的量子算法，可以在不依赖数据相关参数的情况下，提供 n 的二次量子加速效果，同时还将结果推广到多次回归和岭线性回归。

    Nov, 2023

  • 鲁棒线性回归：多项式时间内的最优速率

    本文提出了一种在数据为超收缩分布、存在不可避免的敌对噪声情况下，基于平方和框架的线性模型学习算法，该算法的收敛速度与扰动的比例成幂率关系，能达到理论最优收敛速度且在先前研究中未被发现。

    Jun, 2020

  • 基于近似线性排抽样的分位数回归算法

    提出了行采样算法，适用于各种损失函数的行采样算法，降低数据维度的采样复杂度，并应用于分位数回归和有向图稀疏化问题。

    Jun, 2020

  • 记忆约束下的分位数回归

    本文研究基于有限内存约束的大样本分位数回归问题，提出一种计算效率高的分位数回归估计方法，实现多轮聚合即可得到与所有数据计算分位数回归一样的效果，并适用于分布式计算环境和实时数据处理。

    Oct, 2018

  • 分布式高维分位数回归：估计效率与支持恢复

    分布式估计和支持恢复在高维线性分位数回归中具有重要意义，本文通过将原始分位数回归转化为最小二乘优化问题，并应用双平滑方法，提出了一种新的分布式方法来解决此类问题，在保证计算和通信效率的同时能够实现接近 Oracle 收敛速度和高支持恢复精度的估计结果。通过对合成实例和真实数据应用的大量实验，验证了该方法的有效性。

    May, 2024

  • 在异常值存在的情况下，使用 Beta 分位回归进行鲁棒估计不确定性

    基于鲁棒分位数回归和深度学习的方法，在关键特征异常值存在的情况下，提出了用于估计不确定性的方法，并在医学成像翻译任务中展示了其适用性。

    Sep, 2023

  • 对异常数据鲁棒的回归的高效算法

    本文首次给出了一个多项式时间算法，用于在示例和标签中对抗性堕落下执行线性或多项式回归，并基于 SoS 方法提出了一种自然的凸松弛方法来解决非凸优化问题。

    Mar, 2018

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

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

    May, 2018

  • 通过偏导数实现深层非交叉分位数

    本文提出一种基于深度学习的通用算法，用于预测任意数量的分位数，并确保分位数单调性约束，达到机器精度，并在实验中获得最先进的结果，同时证明其可扩展性适用于大规模数据集。

    Jan, 2022