Mar, 2024

非光滑隐式微分：确定性和随机收敛速率

PDF
TL;DR我们研究了参数化不可微收缩映射的不动点导数的高效计算问题，这个问题在机器学习中有广泛应用，包括超参数优化、元学习和数据污染攻击。我们分析了两种常见方法：迭代微分（ITD）和近似隐式微分（AID）。在非光滑环境下的一个关键挑战是链式法则不再成立。在 Bolte 等人（2022 年）最近的工作基础上，他们证明了非可微 ITD 的线性收敛性，我们提供了对确定性情况下 ITD 和 AID 的改进线性收敛率。当不动点被定义为外部映射和仅能通过随机无偏估计器访问的内部映射的复合时，我们进一步介绍了一种名为 NSID 的新方法来计算隐式导数。我们建立了 NSID 到真导数的收敛速度，包括在光滑环境中的最佳速度。我们进行了说明性实验证实了我们的分析结果。
发现论文，激发创造
  • 双层优化：收敛分析与增强设计

    本文研究非凸强凸双层优化问题，提供了两种基于近似隐式导数和迭代导数的算法以及一种名为 stocBiO 的新型算法，并对它们进行了收敛性分析和比较，实验表明这些优化算法在元学习、超参数优化等方面表现出良好效果。

    Oct, 2020

  • 机器学习中的自动微分数学模型

    本文介绍了自动求导实现与非平滑函数导数求解之间的关系，提出了一种非平滑微积分方程，并阐明其在随机逼近方法中的应用，同时证明了算法求解导数可能产生的人工临界点问题，并演示了通常方法如何以概率为一避免这些点。

    Jun, 2020

  • 自动微分跨条件分支的平滑方法

    控制流结构中引入的不连续性对于假设目标函数响应曲面具有一定平滑性的数学优化方法构成挑战。在此论文中，我们将平滑解释（SI）与自动微分（AD）相结合，以高效计算平滑程序的梯度。SI 与 AD 的结合使得参数综合可以直接基于梯度进行分支程序，例如校准模拟模型或将其与神经网络模型结合在机器学习流程中。我们详细说明了 SI 中为确保可行性所做的近似效果，并提出了一种新的蒙特卡罗估计器，通过 AD 和抽样的组合来估计平滑程序的梯度，从而避免了潜在的假设。通过使用我们的工具 DiscoGrad 将简单的 C++ 程序自动转换为平滑可微形式，我们进行了广泛的评估。我们将 SI 与 AD 的组合以及我们的蒙特卡罗估计器与现有的无梯度和随机方法在四个非平凡的问题上进行比较，这些问题从经典的基于模拟的优化到神经网络驱动的控制。虽然 SI 估计器的优化进展取决于程序控制流的复杂性，但我们的蒙特卡罗估计器在所有问题中都具有竞争力，在最高维问题中具有明显最快的收敛速度。

    Oct, 2023

  • 非光滑随机逼近分析：微分包含方法

    本文研究了非凸、非光滑情况下随机逼近的收敛性，提出了一种基于极限均值的收敛方法并推导了相应的微分包含形式，为证明无约束和约束随机逼近问题的收敛性提供了一般框架，尤其适合于深度学习和低维度高稀疏性统计推断中随机次梯度算法的收敛性分析。

    May, 2018

  • 离散时间扩散模型的非渐近收敛：新方法和改进速率

    去噪扩散模型是一种将噪声转换为数据的强大生成技术，本论文研究了离散时间扩散模型在更大范围的分布上的收敛性保证，并提出了一种加速采样器来提高收敛速度和维度依赖性。

    Feb, 2024

  • 具有快速收敛速度的随机微分方程的非参数学习

    本论文提出了一种非参数学习算法，利用状态的离散时间观测来识别非线性随机微分方程的漂移和扩散系数，其中的关键思想是拟合相应的 Fokker-Planck 方程的 RKHS 近似，通过理论估计学习率，而这个学习率与以前的方法不同，当未知漂移和扩散系数的可靠性更高时，变得更加紧密。由于我们的方法是基于核的，离线预处理可以被有利地利用以实现有效的数字实现。

    May, 2023

  • 对角化 SGD：通过参数重设和平滑实现快速与收敛的非可微模型 SGD

    介绍了一种针对非可微模型的新型随机梯度下降（SGD）方法，利用渐进平滑逼近方法提高了渐进平滑逼近的精度，并证明了收敛到原始目标的固定点，在实验中表现出了简单、快速、稳定的特点，并实现了工作归一化方差的数量级降低。

    Feb, 2024

  • 关于 AdaGrad (Norm) 在 $R^{d}$ 上的收敛：超越凸性、非渐近速率和加速

    本文针对平滑凸函数的标准和更一般的 quasar 凸函数提出了 AdaGrad 及其变体的深入理解，并提出了新的技术来明确界定未约束问题的纯净 AdaGrad 收敛速度，给出了一个新的 AdaGrad 变体，可以展示最终收敛而不是平均迭代，并在确定的情况下给出了新的加速自适应算法及其收敛保证。

    Sep, 2022

  • 利用隐式微分扩展和稳定可微规划

    本文提出了一种不依赖于 forward iteration 层区分前向计算和反向传递并解决 Value Iteration Network 和其变体中大规模问题的不同 iable planning 方法，该方法通过 Bellman fixed-point 方程进行不同 iation，使得计划范围内反向传递的成本恒定，并且前向预算灵活，最终证明了该方法在多个规划任务中的优越性。

    Oct, 2022

  • 优化控制学习问题中隐式微分的再探

    本研究提出了一种使用隐式函数定理（IFT）来区分非凸约束离散时间最优控制（COC）问题中的最优轨迹的新方法，该方法直接评估从应用变量消除到 Lagrange 乘数项的矩阵方程，使得轨迹导数与时间步数呈线性关系，具有易于并行化处理、与模型大小显著提高的可扩展性、直接计算向量雅可比积以及相较于以前的方法具有改进的数值稳定性等优势。

    Oct, 2023