非光滑自动微分的复杂度
介绍了广义导数(称为保守场)来处理在 AI 或数值分析中的非光滑问题,并提供了变分公式,以及将模型应用于确定在实践中实现的非光滑随机梯度方法的值的收敛。
Sep, 2019
研究了在 ML 算法中常见的子导数,比较了计算子导数和计算标量值函数的成本,提出了 Cheap Subgradient Principle 并得出结论:在一定限制下,可以以不到 6 倍计算标量函数本身的成本计算出可靠的 generalized subderivatives。
Sep, 2018
本文介绍了一种使用受限神经网络架构来实现计算涉及到维度导数的微分算子的方法,改进了反向传播计算图,使其可以实现有效提取维度导数。该方法在一些应用场景中具有较低的复杂度,包括计算流体力学中的发散度、连续正规化流的精确密度计算以及训练随机微分方程模型中的 Fokker–Planck 方程求解。
Dec, 2019
这篇文章研究了在有界局部次梯度变化情况下的非光滑优化问题,定义了目标函数的类别,包括传统优化问题中基于目标函数的 Lipschitz 连续性或梯度的 Holder/Lipschitz 连续性的函数,并且包含了既不是 Lipschitz 连续也没有 Holder 连续梯度的函数类别。研究结果表明在传统的优化问题类别中,所定义的类别参数能够得到更为精细的复杂度界限,并恢复了最坏情况下的传统 oracle 复杂度界限,同时对于不是最坏情况的函数通常能够得到更低的 oracle 复杂度。此外,该文章还强调了在并行计算环境中非光滑优化的复杂度与次梯度集合的平均宽度有关。
Mar, 2024
本文介绍了自动求导实现与非平滑函数导数求解之间的关系,提出了一种非平滑微积分方程,并阐明其在随机逼近方法中的应用,同时证明了算法求解导数可能产生的人工临界点问题,并演示了通常方法如何以概率为一避免这些点。
Jun, 2020
本文提出一种新的自动求导方法 —— 一步法微分(Jacobian-free backpropagation),其性能可与隐式微分方法相媲美,并为快速算法(如超线性优化方法)提供了解决方案。其中使用特定的例子(如牛顿法和梯度下降法)对其进行全面的理论近似分析,并揭示了其在双层优化中的应用。通过多个数值示例,证明了这种一步估计器的正确性。
May, 2023
研究非凸性学习任务中经验风险的精细属性(梯度)和群体对应属性的收敛速度以及收敛对优化的影响;提出矢量值 Rademacher 复杂性作为导出非凸问题梯度无维度一致收敛界的工具;给出了应用这些技术进行非凸广义线性模型和非凸健壮回归的批梯度下降方法的新分析,显示了使用任何找到近似稳定点的算法可以获得最优样本复杂度。
Oct, 2018
本文介绍了一些带有或没有耦合的非凸优化模型,使用了相关的优化算法,如条件梯度和 ADMM, 为专门处理非凸和非光滑优化问题的理论和算法的发展提出了一步。通过数值实验,证明了这些算法的高效性,特别是在张量鲁棒 PCA 的场景下。
May, 2016
本文介绍了一种新的非均匀光滑条件下的优化方法,并开发出一种简单但有效的分析技术来限制沿轨迹的梯度,从而获得更强的凸优化和非凸优化问题的结果。我们通过这种新方法证明了(随机)梯度下降和 Nesterov 加速梯度法在这种一般的光滑条件下的收敛率,而不需要梯度剪裁,并允许在随机场景中的有界方差的重尾噪声。
Jun, 2023