May, 2018

在亚线性数据范围内估计可学习性

PDF
TL;DR针对模型类如何拟合标记数据的问题，我们提出了一种计算学习能力的方法，可以使用较小的数据量得出精确结果。该方法也适用于二元分类问题，并在多种真实和合成数据集上得到了验证。
learnabilitylinear functionsample sizevariancebinary classification
发现论文，激发创造
  • 关于鲁棒线性回归的高效算法及下界

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

    May, 2018

  • 近线性时间内的最优鲁棒线性回归

    研究了高维稳健线性回归问题，在受到对抗性破坏的情况下提出了估计方法，包括样本复杂度，恢复保证，运行时间等关键指标，并利用近期算法发展的加速算法和高斯舍入技术等方法来优化估计器的运行时间和统计样本复杂性。

    Jul, 2020

  • 高斯健壮学习：高效获得最优误差

    本文针对高维高斯分布参数学习问题进行了研究，提出了鲁棒估计算法，在拥有少量恶意样本的情况下实现了 $O (ε)$ 精度的估计，同时也证明了算法的多项式时间复杂度和多项式数量样本要求。

    Apr, 2017

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

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

    Jun, 2020

  • 简化 Tight L2 回归的标签复杂度

    提出一种多项式算法，其中通过删除数据点和减少步骤，可以实现与最优解的期望 $(1+d/n)$ 接近度，从而达到在减少标签复杂度的情况下，实现紧密近似。

    May, 2023

  • 重尾统计算法：回归、协方差估计和更多

    研究怎样在不假设样本的基础分布为高斯分布的前提下，只假定有限个矩的情况下，有效地进行线性回归和协方差估计，并关注能用多少样本来实现高精度和指数级成功概率。使用八阶圆当量半定规划提供算法，预备性的证据表明在我们的算法使用的平均中位数框架中无法在多项式时间内改善这些误差率。

    Dec, 2019

  • 学习多元对数凹分布

    该研究论文解决了估计多元对数凹概率密度函数的问题，并提出了一个估计器来处理此问题。

    May, 2016

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

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

    Mar, 2018

  • 学习线性分类器混合模型的 SQ 下界

    学习高斯协变量下的线性分类器混合问题，主要结果是一个统计查询（SQ）下界暗示已知算法对于该问题基本上是最佳的，甚至对于均匀混合的特殊情况。

    Oct, 2023

  • 具有次线性通信的分布式学习

    研究了在分布式学习中，如何在总通信次数亚线性的情况下通过镜像下降与随机稀疏化 / 量化迭代相结合的算法来实现线性模型的最优误差学习，从而探讨了高维环境下分布式学习的可行性。

    Feb, 2019