Oct, 2018

SpiderBoost 和 Momentum：更快的随机方差缩减算法

PDF
TL;DR本文提出了 SpiderBoost 算法，扩展了 SPIDER 并克服了其在实践中收敛速度慢以及处理涉及非光滑正则化器的目标函数的缺点，可以通过使用 Proximal Mapping 处理复合优化，并利用动量方案实现了理论上的近乎最优巨大 Oracle 复杂度和实验结果的实质性改善。
发现论文，激发创造
  • SPIDER: 随机路径一体化微分估计实现非凸优化接近最优

    本文提出了一种称为 SPIDER 的新技术，它可以用于显著降低计算成本跟踪许多确定性感兴趣数量，我们将 SPIDER 应用于两项任务，即随机一阶和零阶方法。

    Jul, 2018

  • 随机变量度量近端梯度算法及方差约减在非凸复合优化中的应用

    提出了 Perturbed Proximal Preconditioned SPIDER (3P-SPIDER) 算法，适用于解决有限和非凸复合优化问题，是随机变量度量前向 - 后向算法，提出了迷你批处理策略以减少方差并控制收敛，并通过逻辑回归模型的推理应用进行了数值比较。

    Jan, 2023

  • 并行重启 SPIDER -- 与最优计算复杂度的通信高效分布式非凸优化

    本文提出了一种基于 SPIDER 梯度估计器的分布式算法，可用于处理随机的平滑、非凸优化问题，该算法结合了最优化方差减少技术与并行 SGD 算法，优化了可以用于联邦学习的非相同分布的数据的模型，提出的算法具有最优迭代复杂度复杂度，并实现了与现有方法相同的线性加速。

    Dec, 2019

  • 非凸优化的快速随机交替方向乘子方法

    本文提出了一个基于 SPIDER 的更快的用于非凸优化的随机交替方向乘法方法（SPIDER-ADMM），证明了 SPIDER-ADMM 能够实现记录性的增量一阶 Oracle 复杂度，并且扩展了 SPIDER-ADMM 到在线设置，并提出了更快的在线 SPIDER-ADMM。

    Aug, 2020

  • D-SPIDER-SFO: 非凸问题快速收敛的分布式优化算法

    提出一种分散化版本的 SPIDER-SFO 算法（D-SPIDER-SFO），该算法在解决非凸优化问题时具有与其集中化版本相似的计算复杂度，达到了解决分散化网络中非凸优化问题的最先进水平，具有非常高的效率。

    Nov, 2019

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

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

    Oct, 2019

  • 一种最优混合方差减小算法用于随机复合非凸优化

    提出了一种新的混合方差缩减近端梯度法，它使用随机梯度评估来代替早期方法中的 $SARAH$，从而实现每次迭代少使用一个随机梯度，在达到了随机梯度评估的最优随机预测复杂度界限的同时很简单。

    Aug, 2020

  • 一种随机复合非凸优化的混合随机优化框架

    提出一种新方法解决一类复合随机非凸优化问题，通过组合两种随机估计量形成混合估计量，将之应用于多种变体的随机梯度法中以达到最优的复杂度界限。

    Jul, 2019

  • 加速的随机无梯度投影方法

    本文提出了一种加速的随机零阶 Frank-Wolfe 优化算法，通过使用 SPIDER/SpiderBoost 技术和一种新的动量加速技术，它可以在非凸优化中实现 O (d√nε⁻²) 的函数查询复杂度，并改进了现有最佳结果，同时在随机问题中实现了 O (dε⁻³) 的函数查询复杂度，同时提出了基于 STORM 的 Acc-SZOFW *，它不需要大批量也可以达到与 Acc-SZOFW 相同的函数查询复杂度。

    Jul, 2020

  • ProxSARAH：随机复合非凸优化的高效算法框架

    提出了一种新的随机一阶算法框架来解决随机复合非凸优化问题，该算法覆盖了有限和期望设置，其中算法仅需要非凸目标项的平均光滑性假设和附加的有界方差假设，并证明了算法可以实现最佳复杂度界限。

    Feb, 2019