Oct, 2023

梯度下降无法学习高频函数和模块算术

PDF
TL;DR通过梯度优化算法训练高频周期函数或模运算存在限制和挑战，即使频率或质数基数 - p 很大时梯度的方差也非常小，从而阻止该学习算法的成功。
发现论文，激发创造
  • 一层隐藏层神经网络的梯度下降：多项式收敛和 SQ 下界

    研究神经网络在激活层和输出加权和层下的训练复杂性，并在高斯分布条件下证明 GD 收敛于最好逼近目标函数的多项式的最小误差，并发现 GD 在发现低频傅立叶分量之前要先发现高频分量。

    May, 2018

  • 神经网络在信息论极限附近通过梯度下降学习低维多项式

    通过 SGD 优化的两层神经网络可学习任意多项式链接函数的单指数目标函数，并具有与信息理论界限相匹配的样本和运行时间复杂度。

    Jun, 2024

  • 关于学习单周期神经元的加密难度

    研究展示了学习单个周期神经元在等向高斯分布中存在噪声时的加密难度，提出了正确性证明，同时证明具有显著普适性，可应用于各种多项式时间算法，并且噪声对这种难度结果的必要性得到了证明。

    Jun, 2021

  • 深度学习的隐性进展: SGD 学习计算限制近似对称问题

    本文通过学习一个 $k$ 位稀疏的 $n$ 位奇偶性来探索大规模数据集、模型规模和训练时间对模型训练计算问题的影响。研究发现神经网络可以成功地学会稀疏的奇偶性，并在训练过程中存在非连续的相变点。理论分析表明，这些观察结果不是通过 Langevin-like 机制解释的，而是通过在人口梯度中的 Fourier 间隙逐渐放大稀疏解来实现。

    Jul, 2022

  • 学习多样特征之和：计算难度和基于梯度的高效训练用于冈脊组合

    研究具有加法结构的目标函数学习的计算和样本复杂性，证明了多项式 target function 可以通过梯度下降法训练两层神经网络高效地学习，同时建立了统计查询算法的边界。

    Jun, 2024

  • 深度学习的可证明限制

    这篇论文证明了深度学习在低交叉可预测性函数分布上的失败，提出了算法约束和跨预测性的概念，并利用信息度量来限制统计间距离，探讨了神经网络、优化误差和算法分析的相关问题。

    Dec, 2018

  • 通过更快的量子梯度计算来优化量子优化算法

    该论文提出了一个基于梯度下降的优化算法框架，发展了一种计算多元实值函数梯度的量子算法，并提高了计算梯度的复杂性以适应光滑函数的重要类别，而且可以为量子最优化算法提供更快的计算梯度方法。

    Nov, 2017

  • 约束多项式优化问题的量子梯度下降与牛顿法

    该论文开发了量子版本的迭代优化算法，并将其应用于具有单位范数约束的多项式优化问题中，通过量子算法处理高维问题可以在少数迭代步骤中取得良好效果。

    Dec, 2016

  • 学习神经网络的特定分布困难度

    探讨对输入分布和目标函数的特定假设是否足以保证使用基于梯度的方法进行学习，在此基础上提供了一些工具来证明不同类别的目标函数的难以学习性和困难输入分布。

    Sep, 2016

  • 基于梯度的方法学习离散对数的难解性

    研究了梯度法在有限循环群中学习离散对数奇偶位的局限性，理论和经验证实发现梯度函数集中在一个固定点附近，不管所使用的对数的基。通过使用内积空间中的 Boas-Bellman 不等式以及建立离散对数奇偶位函数的近似正交性，对于基于梯度的学习的限制性能进行了证明。使用基于神经网络的方法的实证实验证明了梯度法学习的局限性，随着群的阶数的增加，在预测奇偶位上的成功率逐渐降低。

    Oct, 2023