Sep, 2013

非凸随机规划的随机一、零阶方法

PDF
TL;DR本文介绍了一种新的随机逼近方法 —— 随机梯度下降算法，用于解决非线性随机规划问题，并证明了该算法的复杂度和优化收敛速度，指出该算法在问题为凸问题时具有接近最优的收敛速度，同时优化了其大偏差特性，特别针对只有随机零阶信息可用的类模拟优化问题进行了改进。
stochastic approximationrandomized stochastic gradient methodnonlinear programmingconvex optimizationsimulation-based optimization
发现论文，激发创造
  • 非凸随机复合优化问题的小批量随机逼近方法

    该论文提出了一种随机梯度下降算法（RSPG）来解决一类包含非可微凸函数和非光滑性质的随机优化问题，并且证明了该算法的收敛速度。

    Aug, 2013

  • 非凸优化的改进零阶方差约减算法及分析

    本文介绍了两种零阶随机算法的优化和改进，其中一种通过新的 ZO-SVRG-Coord-Rand 算法和分析结果发现，比现有的同类算法以及 ZO-GD 和 ZO-SGD 更为优秀，另一种通过新的 ZO-SPIDER-Coord 算法有效降低了 Gaussian 随机变量的数量和步长的级别以实现相同的收敛速度和查询复杂度，并且自动实现了线性收敛率。

    Oct, 2019

  • 快速无梯度近端随机非凸非光滑优化方法

    本文提出了两种新的零阶近端随机优化算法 ZO-ProxSVRG 和 ZO-ProxSAGA，它们利用了 SVRG 和 SAGA 的方差缩减技术，并证明了它们具有线性 $O (rac {1}{T})$ 的收敛速度，实验结果表明相比于现有的零阶近端随机算法，新算法有更快的收敛速度。

    Feb, 2019

  • 非凸随机零阶优化：处理约束、高维度和鞍点

    本文提出了针对非凸和凸优化的零阶随机逼近算法，并关注解决约束优化、高维设置和避免鞍点等问题。我们探索了结构稀疏假设的优点，并提出了一种使用零阶信息的被截断随机梯度算法和一种避免鞍点的算法，并讨论了它们的收敛率。

    Sep, 2018

  • 随机非线性规划的惩罚方法与随机逼近

    提出一种基于随机逼近的罚函数方法来解决非线性规划问题，利用噪声梯度或函数值来调用随机一阶或零阶神经网络，通过最小化随机一阶或零阶信息可用的非光滑、非凸罚函数的方法来优化。分析了该罚函数方法通过调用随机一阶（或零阶）神经网络获取 ε- 随机临界点的最坏情况复杂度。

    Dec, 2013

  • 非凸优化的随机方差缩减

    本研究分析了随机变量缩减梯度（SVRG）方法在非凸有限和问题中的应用，证明了其比随机梯度下降（SGD）和梯度下降（GD）更快收敛于固定点，并分析了一类 SVRG 在解决非凸问题上的线性收敛，同时研究了 mini-batch 变体的 SVRG 在并行设置中加速的外延。

    Mar, 2016

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

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

    Oct, 2017

  • 稳定 SVRG: 非凸优化的简单方差缩减

    该研究使用改进的 SVRG 算法创新性地找到一个非凸函数的二阶稳定点，并提出了使用稳定性 SVRG 算法的方法。

    May, 2019

  • 零阶随机方差约减用于非凸优化

    本文提出了一种基于损失函数的零阶优化算法（ZO-SVRG）以及相应的快速收敛的优化方法，即方差减少，用于解决应用中需要零阶优化的挑战，可用于黑盒物质分类和黑盒深度神经网络模型生成对抗性示例。我们的理论分析揭示了 ZO-SVRG 的本质难点，并提出了两种利用方差减少的梯度估计器的加速版本 ZO-SVRG，其在 ZO 随机优化（迭代次数）方面具有已知的最佳速度。与当前其他最先进的 ZO 算法相比，我们的方法在功能查询复杂性和收敛速率之间取得了平衡。

    May, 2018

  • 一种简单的近端随机梯度下降法用于非光滑非凸优化

    本文提出一种基于变量规约的 Proximal 随机梯度下降算法 (ProxSVRG+), 该算法在非凸性和非光滑性优化问题上具有更好的性能，并在收敛性分析方面比之前的算法更加全面和普适性更强。

    Feb, 2018