May, 2020

基于 ReLU 的回归近似方案

PDF
TL;DR本文提出一种基于分布函数采样数据的 ReLU 回归算法并给出了第一个可行的常数近似算法，同时该算法适用于所有对数凸分布。通过更加复杂的技术，我们还能够获得任何次高斯分布的多项式时间逼近方案。
relu regressionsquare lossapproximation algorithmconcentrationanti-concentration
发现论文，激发创造
  • 关于学习 ReLU 及高斯边缘的时间 / 准确性权衡

    本文探讨如何在高斯分布下计算最适合的 ReLU 模型，证明了学习受高斯边缘影响下的 ReLU 模型的难点，并提出了一种利用噪声半空间学习算法的近似最优解法。

    Nov, 2019

  • 在多项式时间内可靠地学习 ReLU

    本研究提出了有效学习基于 ReLU 的常深度网络的算法，该算法运用了核方法、多项式逼近和凸优化的 “双损失” 方法，同时获得了解决 “凸分段线性拟合” 和 “在单位球上低权重多项式的噪音重构” 等其他应用。

    Nov, 2016

  • ReLU 神经网络的凸松弛在多项式时间内近似全局最优

    本文研究了采用权重衰减正则化的两层 ReLU 网络与其凸松弛之间的最优性差距，揭示了在随机训练数据情况下原问题与其松弛之间相对最优性差距可以通过 O (√log n) 的因子进行界定，且应用简单的算法可在多项式时间内解决原非凸问题，此外，在合理假设下，随机初始化参数的局部梯度方法几乎必定收敛于训练损失较低点，此结果相对现有结果而言具有指数级改进，并对解释局部梯度方法为何行之有效提供了新的见解。

    Feb, 2024

  • 线性可分数据上的 ReLU 网络学习：算法，最优性和泛化

    本文提出了一种新的随机梯度下降算法，利用随机噪声扰动，无需任何假设于数据分布、网络大小和训练集大小，就能够证明地达到单隐藏层 ReLU 网络的全局最优性，同时提出了一些一般的泛化保证，此外，数值测试结果也验证了算法和理论的实用性。

    Aug, 2018

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

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

    Mar, 2018

  • 两层 ReLU 网络的快速凸优化：等价模型类和锥分解

    本文研究了基于 ReLU 激活函数的两层神经网络的凸优化及其群 lasso 正则化和加速近端梯度算法，该方法在 MNIST 和 CIFAR-10 数据集的图像分类方面表现良好。

    Feb, 2022

  • 平方根 Lipschitz Loss 下的一致收敛

    本文研究基于 Rademacher 复杂度和平方根标量损失函数的 Lipschitz 常数，以高斯数据的泛化一致性保证为例，并处理了广泛的平方根 Lipschitz 损失函数的类别，包括适用于相位恢复和 ReLU 回归的非平滑损失函数，从而重新推导和更好地理解 “乐观率” 和插值学习保证。

    Jun, 2023

  • 通过舒尔多项式高效学习一层 ReLU 网络

    本研究旨在研究使用标准高斯分布下的 ReLU 激活函数的线性组合进行 PAC 学习的问题，并提出了一种具有高效样本和计算复杂度的算法，其复杂度接近于相关统计查询算法类中的最优复杂度。该算法使用张量分解识别出一个子空间，使其在正交方向上的所有 O (k) 阶矩都很小，并利用 Schur 多项式理论证明了当较低阶矩均很小时，较高阶矩误差张量也很小。

    Jul, 2023

  • 通过函数梯度计算统计查询下限

    该研究首次为关于高斯边缘任意非多项式激活函数的伪装学习问题，给出了统计查询下限。通过梯度提升过程对之前的低界进行放大，对具体问题 ReLU 回归（等同于伪装学习 ReLU），我们证明任何统计查询算法都必须使用至少 2^(n^c) ε 个查询，从而阐述了与真实价值的学习问题不同的情况，我们的结果排除了一般（相对于关联）SQ 学习算法，这在实值学习问题中是不寻常的。同时我们将两种常见的学习模型，即伪装学习和概率概念之间得到了最好的规约。

    Jun, 2020

  • 浅层 ReLU$^k$ 神经网络的最优逼近速率及其在非参数回归中的应用

    研究了一些与浅层 ReLU$^k$ 神经网络相对应的变分空间的近似容量，证明了这些空间包含充分平滑的函数与有限变化范数。此外，还建立了以变化范数为基础的逼近率与神经元数量的最佳逼近率，并且证明了浅层 ReLU$^k$ 神经网络可以实现学习 H"older 函数的极小极值速率，而过参量化 (深或浅) 神经网络可以实现非参数回归的几乎最优速率。

    Apr, 2023