ICMLJun, 2020

关于超梯度计算的迭代复杂度

PDF
TL;DR本文研究了一个广泛的双层问题类别，其中包括上层目标函数的最小化和参数化的定点方程的解。在假设定点方程由一个收缩映射定义的前提下，我们提供了一种统一的分析方法，以便第一时间定量比较各种方法，为它们的迭代复杂性提供明确的界限，并建议采用逐步共轭梯度的近似隐式微分法来进行超梯度的计算，并通过实验确认了理论上的发现。
bilevel problemshyperparameter optimizationmachine learninghypergradientiteration complexity
发现论文，激发创造
  • 随机超梯度的收敛性质

    本文研究了随机逼近方案的超梯度，提供了超梯度逼近的均方误差界限，并提供了数字实验来支持理论分析和展示在实践中使用随机超梯度的优势。

    Nov, 2020

  • 提高超梯度估计：预条件和参数重参数化的研究

    双层优化是一种针对依赖于内部优化问题解的外部目标函数进行优化的方法，在机器学习中广泛应用于超参数调整。本研究通过研究隐藏变量方法的误差，分析了两种减小误差的策略：预处理隐藏变量公式和重新参数化内部问题。我们详细说明了这两种修改对误差的影响，并强调了涉及的功能的高阶导数所起的作用。我们的理论发现解释了何时可以实现超级效率，即使得超梯度的误差与内部问题的误差二次相关，并在这种情况下比较了两种方法。对回归问题的超参数调整的数值评估验证了我们的理论发现。

    Feb, 2024

  • 双层优化的截断反向传播

    本文分析了通过截断反向传播计算的近似梯度的属性，并为其收敛。研究表明，使用几步反向传播计算的近似梯度优化通常与使用精确梯度的优化相当，同时需要更少的内存和一半的计算时间。

    Oct, 2018

  • 用于简单双层优化的加速梯度方法和凸下层问题

    本研究关注简单的双层优化问题，提出一种新的双层优化方法，利用切割平面方法局部近似解决方案集合，应用加速梯度更新来减小上层目标函数，以实现子优性和不可行性错误的非渐近收敛保证。

    Feb, 2024

  • 基于超梯度的双层强化学习方法并避免较低级别的凸性

    通过使用与规则化 RL 相关的固定点方程，我们以全一阶信息表征超梯度，从而回避了对低级凸性的假设，并提出了基于模型和无模型的双层强化学习算法，都被证明具有收敛速度 O (ε^(-1))。

    May, 2024

  • 使用近似梯度进行超参数优化

    本文提出了一种算法来优化连续超参数，该方法可以在模型参数完全收敛之前更新超参数，具有全局收敛的充分条件，并在 L2 正则化逻辑回归和核岭回归的正则化常数估计上验证了实证表现。

    Feb, 2016

  • 正向和反向基于梯度的超参数优化

    研究了计算任何迭代学习算法（如随机梯度下降）超参数的验证误差梯度的两种方法（反向模式和正向模式），这些程序镜像了递归神经网络计算梯度的两种方法，并具有不同的运行时间和空间要求。

    Mar, 2017

  • 无反演深度双层优化的罚函数方法

    本文提出了一种新颖的基于罚函数方法的二层优化问题算法，避免了计算 Hessian 逆矩阵的过程，并可轻松处理限制性二层问题。本方法证明收敛性并在大规模深度神经网络二层问题中表现优异，应用于数据去噪、few-shot 学习和训练数据污染问题，结果表明在准确性、运行时间和收敛速度方面均优于基于自动微分和近似求逆的以前提出的方法。

    Nov, 2019

  • 通过极小极大重表达实现高效双层优化

    提出了一种将双层优化问题重新设计成极小极大问题的方法，并采用渐进式梯度下降上升算法来解决该问题，结果表明该算法在降低计算成本的同时，优于现有的基于双层优化的算法。

    May, 2023

  • 双层规划的近似方法

    本文研究一类内部目标函数为强凸函数的双层规划问题，给出了一种求解该问题的逼近算法，并在外部目标函数为不同凸性的情况下提供了其有限时间收敛分析。同时，提出了一种加速变体以提高收敛速度，并推广了结果到只有有限的信息可用的随机情况下。本文是第一次为双层规划提供了已确定的迭代复杂度（样本复杂度）的（随机）逼近算法。

    Feb, 2018