本文提供了一种新颖的计算机辅助技术，用于系统地分析面向优化的一阶方法，并且与以往的工作相比，该方法特别适用于处理次线性收敛率和随机预言机。该技术依赖于半定规划和潜力函数，并允许同时获得算法行为的最坏情况保证，并帮助选择适当的参数以调整其最坏情况表现。

Feb, 2019

本文探讨了在随机凸优化问题中寻找近似驻点的 oracle 复杂度问题和其和全局 oracle 模型的关系，并提出了一种扩展的递归正则化算法以实现接近最优率，并揭示了 stochastic optimization 和 learning 的复杂度之间的一些惊人区别。

Feb, 2019

研究了随机梯度下降（SGD）算法在最小化光滑、可能非凸函数梯度范数方面的迭代复杂度，结果表明，Ghadimi和Lan的上限不能得到改进，除非做出额外的假设，即使对于凸二次函数，也是如此；此外还表明，对于非凸函数，SGD最小化梯度的可行性需要根据所选择的最优性标准而定。

Oct, 2019

采用随机一阶方法找到梯度范数不超过ε的ε-稳定点的复杂度下界，使用具有有界方差的无偏随机梯度预言机访问光滑但可能非凸函数的一种模型，证明任何算法在最坏情况下需要至少ε^-4个查询才能找到ε-稳定点。对于噪声梯度估计满足均方光滑性质的更严格模型，我们证明了ε^ -3个查询的下界，建立了最近提出的方差缩减技术的最优性。

Dec, 2019

我们介绍了MOPES方法和MOLES方法，用于在具有昂贵的投影和线性最小化查询的情况下，高效地寻找在强凸约束集上的次优解。 MOPES方法通过Moreau-Yosida平滑和加速的一阶方案结合，并通过仅需O(ε ^ -1)投影查询和最少的O(ε ^ -2)函数值查询即可找到次优解。 MOLES方法仅具有线性最小化查询，但需要更多的函数值查询。

Oct, 2020

我们通过使用第一阶oracle及条件数,提供了寻找min-max优化问题中目标函数在最小化变量上是非凸及在最大化变量上是强凸时的稳定点的复杂度的下界，这既适用于确定性oracle也适用于随机oracle，并提供了各自的下界，并与其他文献的上界进行了比较。

Apr, 2021

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

Jul, 2023

我们研究了一类随机二级优化问题，引入了一种新颖的随机二级优化方法，通过随机切割平面局部逼近下层问题的解集，并运行带有方差减少技术的条件梯度更新来控制由于使用随机梯度引起的误差。在上层函数为凸函数的情况下，我们的方法需要最多$\tilde{\mathcal{O}}(\max\{1/\epsilon_f^{2},1/\epsilon_g^{2}\})$个随机oracle查询，得到一个上层函数精度为$\epsilon_f$、下层函数精度为$\epsilon_g$的解，这一保证改进了之前已知的复杂性$\mathcal{O}(\max\{1/\epsilon_f^{4},1/\epsilon_g^{4}\})$。此外，在上层函数为非凸函数的情况下，我们的方法需要最多$\tilde{\mathcal{O}}(\max\{1/\epsilon_f^{3},1/\epsilon_g^{3}\})$个随机oracle查询，找到一个$(\epsilon_f, \epsilon_g)$-稳定点。在有限和问题设置中，对于凸和非凸情况下，我们的方法所需的随机oracle调用次数分别为$\tilde{\mathcal{O}}(\sqrt{n}/\epsilon)$和$\tilde{\mathcal{O}}(\sqrt{n}/\epsilon^{2})$，其中$\epsilon=\min \{\epsilon_f,\epsilon_g\}$。

Aug, 2023

该论文研究了随机受限多层优化的无投影算法。介绍了新的无投影方差缩减算法并分析了它们在不同条件下的复杂性，包括梯度映射和Frank-Wolfe间隙准则，并通过分阶段适应进一步获得了凸函数和强凸函数的复杂性，数值实验证明了该方法的有效性。

Jun, 2024

非凸优化中采用维度无关的随机一阶方法(DISFOM)来解决样本复杂度问题，使用小批量估计梯度以达到ε-稳定点的样本复杂度为O((log d) / ε^4)，进一步利用方差缩减可将该界限提高至O((log d)^(2/3) / ε^(10/3))，并提供了两种非平滑距离函数的选择，数值实验验证了所提框架的维度无关性。

Jun, 2024