SPIDER: 随机路径一体化微分估计实现非凸优化接近最优

Jul, 2018

SPIDER: 随机路径一体化微分估计实现非凸优化接近最优

SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator

Cong Fang, Chris Junchi Li, Zhouchen Lin, Tong Zhang

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

Abstract

In this paper, we propose a new technique named \textit{Stochastic Path-Integrated Differential EstimatoR} (SPIDER), which can be used to track many deterministic quantities of interest with significantly reduced computational cost. We apply SPIDER to two tasks, namely the stochastic first-order and zeroth-order methods. For stochastic first-order method, co

stochastic path-integrated differential estimator stochastic optimization problems gradient computation cost approximate first-order stationary points stochastic zeroth-order method

发现论文，激发创造

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

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

Nov, 2019

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

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

Aug, 2020

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

本文提出了 SpiderBoost 算法，扩展了 SPIDER 并克服了其在实践中收敛速度慢以及处理涉及非光滑正则化器的目标函数的缺点，可以通过使用 Proximal Mapping 处理复合优化，并利用动量方案实现了理论上的近乎最优巨大 Oracle 复杂度和实验结果的实质性改善。

Oct, 2018

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

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

Dec, 2019

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

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

Jan, 2023

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

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

Oct, 2019

SPAN：一种随机投影近似牛顿法

本文提出了一种快速的二阶优化算法 SPAN, 通过低秩逼近和随机海森向量相乘的方式来计算黑塞矩阵的逆，实验结果证明 SPAN 在多个基准数据集上优于现有的一阶和二阶优化算法，同时提供了每次迭代的复杂度、逼近误差和收敛速度的理论分析，表明 SPAN 在收敛速度和每次迭代效率之间取得了更好的平衡。

Feb, 2020

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

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

Jul, 2020

基于 Polyak-Łojasiewicz 条件的极小化极大优化的更快随机算法

基于 Polyak-Lojasiewicz 条件，本文提出了用于解决 minimax 优化问题的随机一阶算法 SPIDER-GDA，该算法在有限和的情况下达到了更好的优化效果，并降低了计算成本。

Jul, 2023

非凸随机复合优化问题的小批量随机逼近方法

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

Aug, 2013