May, 2024

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

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

    该论文提出了基于随机条件梯度方法的优化问题求解算法，用于解决大规模维度下的凸函数、连续子模型等多种问题，并证明了当问题维度高时，该方法较与传统的随机梯度下降法更加稳定，同时计算时间复杂度也得到了有效降低。

    Apr, 2018

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

    本论文提出了 Constraint Extrapolation 和 proximal point method 两种方法来解决 functional constrained optimization 问题，分别针对 convex 和 nonconvex problems，通过 mathematical analysis 得到具体的收敛率和收敛条件。

    Aug, 2019

  • 非凸和非光滑问题随机优化的稳定性和泛化

    本文针对非凸非光滑问题提出新的算法稳定性度量方法，同时建立它们与梯度之间的量化关系，并使用采样确定算法导出了随机梯度下降算法和其自适应变种的误差界。

    Jun, 2022

  • 基于条件梯度方法的随机次模最大化：弥合差距

    研究连续子模最大化问题，通过提供新颖的算法并使用随机持续优化作为接口，在满足约束条件的情况下获得了紧密的逼近保证。

    Nov, 2017

  • 非凸世界中 SGD 的更好理论

    本篇论文使用类似于期望光滑性假设的新方法来研究随机梯度下降法在非凸优化中的收敛率，并在考虑多种采样策略和小批量大小的情况下，探讨有限和优化问题的影响。

    Feb, 2020

  • 广义平滑下的凸优化和非凸优化

    本文介绍了一种新的非均匀光滑条件下的优化方法，并开发出一种简单但有效的分析技术来限制沿轨迹的梯度，从而获得更强的凸优化和非凸优化问题的结果。我们通过这种新方法证明了（随机）梯度下降和 Nesterov 加速梯度法在这种一般的光滑条件下的收敛率，而不需要梯度剪裁，并允许在随机场景中的有界方差的重尾噪声。

    Jun, 2023

  • 强高概率二阶收敛的随机非凸优化

    本文研究带有非凸随机函数的随机非凸优化，并提出一种称为 NCG-S 的新型更新步骤，可以在高概率下实现二阶收敛，所提出的随机算法是首个具有高概率二阶收敛和几乎是线性时间复杂度的方法。

    Oct, 2017

  • 结构化非凸非光滑优化：算法和迭代复杂度分析

    本文介绍了一些带有或没有耦合的非凸优化模型，使用了相关的优化算法，如条件梯度和 ADMM， 为专门处理非凸和非光滑优化问题的理论和算法的发展提出了一步。通过数值实验，证明了这些算法的高效性，特别是在张量鲁棒 PCA 的场景下。

    May, 2016

  • 非光滑非凸正则化优化的简单随机梯度方法

    本研究旨在探讨优化非光滑非凸正则化器下的平滑非凸损失函数的随机梯度方法。我们提出了两种简单的随机梯度算法，对于有限总和和一般随机优化问题，相较于现有技术水平，其具有更优的收敛复杂度。同时，我们在经验风险最小化中比较了两种算法的实际表现。

    Jan, 2019

  • 一种线性收敛的条件梯度算法及其在在线和随机优化中的应用

    本研究介绍了一种基于条件梯度算法的优化模型，可用于求解线性优化问题和非线性凸优化问题，并给出了一种基于此算法的在线凸优化算法，具有线性收敛速度和最优的遗憾保证。

    Jan, 2013