MMAug, 2019

随机一阶方法用于凸约束优化和非凸约束优化

PDF
TL;DR本论文提出了 Constraint Extrapolation 和 proximal point method 两种方法来解决 functional constrained optimization 问题，分别针对 convex 和 nonconvex problems，通过 mathematical analysis 得到具体的收敛率和收敛条件。
functional constrained optimizationconstraint extrapolationproximal point methodconvergence ratenonconvex problems
发现论文，激发创造
  • 带函数约束的随机变分不等式问题的一阶方法

    本文提出了适用于具有各种设置的函数约束 VI 问题的新型一阶方法，包括具有随机算子和 / 或随机约束的平滑或非平滑问题。通过使用算子和约束的外推来更新变量和 Lagrange 乘子，我们的算法能够实现最优操作员或样本复杂度。对于平滑的确定性问题，我们还提出了一种新的单循环自适应 Lagrangian 外推方法，可以自适应地搜索和显式地绑定 Lagrange 乘子。此外，我们的算法可以轻松地扩展到具有耦合函数约束的鞍点问题。

    Apr, 2023

  • 随机梯度下降与外推在非凸优化中的收敛性

    本文研究利用外推算法解决非凸优化问题的收敛性，并通过分析梯度下降和随机梯度下降算法证明外推可以加速算法的收敛速度。

    Jan, 2019

  • 非凸非光滑条件随机优化的功能模型方法

    我们提出了一种用于非凸约束条件随机优化问题的专门单时间尺度随机方法，其中包含一个 Lipschitz 平滑的外函数和一个广义可微分的内函数。该方法中，我们用一个丰富的参数模型来逼近内部条件期望，该模型的均方误差满足随机版本的 Lojasiewicz 条件。该模型由内部学习算法使用。我们的方法的主要特点在于，方法使用的方向可以通过每次迭代从联合分布中生成一个观测而产生无偏的随机估计，这使其适用于实时学习。然而，这些方向不是任何总体目标函数的梯度或亚梯度。我们利用微分包含的方法和特殊设计的 Lyapunov 函数以及 Bregman 距离的随机推广证明了该方法的收敛性，最后，通过数值实例证明了我们的方法的可行性。

    May, 2024

  • 非光滑非凸优化的快速随机方法

    本文研究随机算法优化非凸、非光滑的有限和问题。针对此问题，本文提出快速的随机算法，可获得常数迷你批量的收敛性。本文还使用这些算法的变种，证明了比批量近端梯度下降更快的收敛性，并在非凸、非光滑函数的一个子类中证明全局线性收敛率。

    May, 2016

  • 非光滑、非凸问题的近距离引导随机次梯度方法

    本文介绍了一种基于随机投影次梯度方法的弱凸（即均匀逼近正则）非光滑非凸函数的算法，并通过简单证明证明这种方法与用于光滑非凸问题的随机梯度方法具有相同的收敛速度；这似乎是第一个针对弱凸函数类的随机次（或确定性）梯度法的收敛速度分析。

    Jul, 2017

  • 无光滑，无投影的带函数约束优化

    提出了一种基于次梯度的算法，用于处理具有通用凸不等式约束的非光滑问题，通过使用线性最小化预言机和拉格朗日乘子更新规则，在不需要对可行域进行投影的情况下实现了 ε- 次优解。

    Nov, 2023

  • 复合和弱凸优化问题的随机方法

    本研究考虑了具有随机性的凸函数和光滑函数组成并且是弱凸的函数式的最小化问题，开发了一系列随机算法，并通过实验验证了实际效果。

    Mar, 2017

  • 超越凸性和 Lipschitz 梯度连续性的一阶方法及其在二次逆问题中的应用

    利用可适应性光滑函数的概念和 Bregman 基础的近端梯度方法，在解决具有复杂目标函数的非凸、非光滑最小化问题时，实现全局收敛。

    Jun, 2017

  • 非强凸优化的一阶方法线性收敛

    本文研究了解决光滑的非强凸约束优化问题的一些一阶方法的收敛率，提供了一些松弛的强凸条件并证明了它们对于多种一阶方法的线性收敛是足够的，最后证明了所提出的松弛强凸条件涵盖了求解线性系统、线性规划和线性约束凸问题的重要应用。

    Apr, 2015

  • 随机（近似）近端点法：收敛性，最优性和适应性

    本文提出了基于模型的方法，解决随机凸优化问题，并介绍了近似近端点（aProx）家族，包括随机次梯度、近端点和束方法。通过适当准确的建模方法，这些方法享有比传统方法更强的收敛性和鲁棒性保证，即使与随机次梯度方法相比，基于模型的方法通常增加很少甚至没有计算开销。

    Oct, 2018