Mar, 2018

正则化优化的不精确连续二次逼近

PDF
TL;DR本论文研究了用于函数最小化的二次逼近方法，重点考虑迭代复杂度以及该方法的充分性和必要性证明。我们证明了在实现精度范围内的非精确解决方案足以保证收敛速度与精确方案相同，本文揭示了这个在早期阶段是线性的，而总比例为 $O (1 /k)$。此外，我们还证明了此方法在一些凸问题上具有全局收敛性。
successive quadratic approximationsproximal methodsiteration complexityinexact solutionsconvergence rate
发现论文，激发创造
  • 具有全局复杂度分析的实用不精确近端拟牛顿方法

    提出了一种稀疏优化的通用框架，使用了二阶信息和有限的 BFGS Hessian 逼近，通过坐标下降的方法解决问题，并对其全局收敛率进行了新颖的分析。

    Nov, 2013

  • 带有线性和加速亚线性收敛速率的正则化凸优化的近端拟牛顿方法

    本文针对复合优化问题中一般且高效的不精确近端拟牛顿算法，在强凸目标函数下分析了其精确和不精确执行的收敛性质，并建立了一个简单的停止标准来改善其实用性。同时，对基于 FISTA 的近端拟牛顿算法进行加速，并与传统算法进行比较和分析，结果表明加速并没有带来任何好处。

    Jul, 2016

  • 凸优化中不精确近端梯度方法的收敛速率

    本文探讨了使用近端梯度法优化平滑凸函数和非平滑凸函数的和时，如果在计算平滑项的梯度或非平滑项的邻近算子时存在误差，基本的近端梯度法和加速近端梯度法可以实现与没有错误的情况下相同的收敛率，前提是错误以适当的速度减小。使用这些速度，在一组结构稀疏性问题上，我们的表现与精心选择的固定误差级别相当或更好。

    Sep, 2011

  • 非凸问题高效不精确近端梯度算法

    本文提出了一种高效的近端梯度算法，每个迭代只需要一个不精确（因此更便宜）的近端步骤，收敛于非凸问题的临界点并具有 O (1/k) 的收敛速度，比一阶方法中非凸问题的最佳速度还要快。

    Dec, 2016

  • 不精确非凸牛顿类型方法

    提出了非凸问题的近似解决方案；采用了三次正则化和信任域算法的不精确变体，并且可以应用于有限和问题，通过随机子采样法对梯度和 Hessian 进行适当精度逼近，实现了计算效率与最优迭代复杂度的权衡。

    Feb, 2018

  • 近端法的误差界、二次增长和线性收敛

    本文介绍了一种利用步长乘以线性误差边界的方法来实现凸函数最小化的近端梯度算法；通过证明将误差边界与一种自然二次生长条件的等价性，直观地解释了观察到的线性收敛现象；我们的方法将推广到用于最小化由光滑映射组成的非光滑函数的近端方法，同时观察到算法中的短步长暗示了接近稳定状态，建议作为可靠的终止准则。

    Feb, 2016

  • 非凸非光滑优化的不精确近端梯度法

    本文研究了机器学习中基于不光滑正则化的各种优化问题，并提出了三种不精确的近端梯度算法，包括基本版本和 Nesterov 加速版本。理论分析表明，我们的不精确近端梯度算法可以在非凸情况下具有和精确近端梯度算法相同的收敛速度。实验结果证实了新算法在三个代表性非凸学习问题上的优越性。

    Dec, 2016

  • 光滑非凸优化的二阶线搜索算法复杂度分析

    本文介绍了一种基于线搜索的方法来发现平滑函数的不受限制的局部最小值，该方法使用迭代方法来计算搜索方向，收敛速度优秀。此外，还研究了使用共轭梯度和 Lanczos 方法进行搜索向量的近似计算，并得到了这些实用方法的修正收敛性和复杂性结果。

    Jun, 2017

  • 求解线性约束非凸组合问题的二次惩罚加速不精确近端点方法的复杂度

    本文研究了一种二次罚函数加速的不精确近端点法迭代复杂度，用于求解线性约束下的非凸组合规划问题。作者证明了该方法能够在加速梯度下降法的基础上，有效地生成近似极小点。数值结果表明该方法的有效性。

    Feb, 2018

  • 增量方法的最后迭代收敛及其在持续学习中的应用

    基于应用于连续学习中的动机，我们首次获得了增量梯度和增量近端方法的最后迭代的收敛性保证，适用于一般凸平滑以及凸 Lipschitz 设置，同时几乎与平均迭代的最佳收敛性保证相匹配。

    Mar, 2024