本文研究了一种优化问题，在多项式朗托泽维奇条件下，通过梯度方法在分布式环境中找到次优解，提出了一个去中心化一阶方法，并给出了相应的下界。

Feb, 2024

本文研究求解一个 min-max 零和游戏的问题，在非凸非凹的情况下证明了一种简单的多步梯度下降 - 上升算法可以找到该问题的一个 epsilon - 一阶稳定点，其中一个玩家的目标满足 Polyak-Lojasiewicz 条件。

Dec, 2018

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

Jul, 2023

介绍了一种不需要强凸性条件的梯度下降算法，并针对机器学习中的各种问题提供了新的分析方法和收敛证明。

Aug, 2016

我们提供了一种新的分析框架，用于分析统计学习中基于一阶优化算法的泛化误差，当只能通过一个 oracle 提供的部分观测来获取梯度。我们的分析依赖于梯度相对于数据样本的正则性，并且允许为多个学习问题，包括监督学习、迁移学习、鲁棒学习、分布式学习和使用梯度量化的通信高效学习推导出接近配对的上下界的泛化误差。这些结果适用于平滑和强凸优化问题，以及满足 Polyak-Lojasiewicz 假设的平滑非凸优化问题。我们的上下界依赖于一个新颖的量，它扩展了条件标准差的概念，并衡量了通过访问 oracle 获取梯度的程度。因此，我们的分析为优化统计学习目标的优化提供了精确的含义，即统计学习目标的优化与其梯度估计一样困难。最后，我们证明，在标准监督学习的情况下，批梯度下降法随着批次大小的增加和热启动可以达到近似最优的泛化误差，从而激励我们在实际应用中使用这种优化方案。

Jul, 2023

本文探讨了利用仅包含部分和嘈杂信息的凸函数最小化问题，特别着重于高度平滑问题的凸优化问题，包括逻辑回归等。研究表明，相对于基于梯度的算法，高阶平滑性可用于改善估计速率，并精确地依赖于平滑度的程度，同时提出了此类算法可行性的上限。最后，作者还在在线优化设置中取得了类似的结果。

May, 2016

比较多元多项式函数全局优化算法，证明了使用具有半定规划的平方和松弛技术比代数方法更有效，并为实数代数几何中的广泛计算问题提供了可能性。

Mar, 2001

在在线学习中，优化随机零阶反馈下的凸函数一直是一个主要而具有挑战性的问题。本文考虑了仅能对目标函数进行噪声评估的情况下，对二阶平滑和强凸函数进行优化的问题；通过提出匹配的上下界，第一次对最小化最大简单后悔的速率进行了紧密的刻画。我们提出了一种算法，结合了启动阶段和镜像下降阶段。我们的主要技术创新包括对高阶平滑性条件下球形采样梯度估计器的尖锐刻画，从而使算法能够在偏差 - 方差权衡方面达到最优平衡，以及一种用于启动阶段的新的迭代方法，它能够保持无界 Hessian 的性能。

Jun, 2024

本文通过建立黑盒稳定性结果，仅依赖于学习算法的收敛和损失函数最小值周围的几何形态，为收敛到全局最小值的学习算法建立新的泛化界限，适用于满足 Polyak-Lojasiewicz（PL）和二次增长（QG）条件的非凸损失函数以及一些具有线性激活的神经网络，并使用黑盒结果来证明 SGD、GD、RCD 和 SVRG 等优化算法的稳定性在 PL 和强凸设置中具有可拓展性，同时指出存在简单的具有多个局部最小值的神经网络，在 PL 设置下 SGD 稳定，但 GD 不稳定。

Oct, 2017

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

Feb, 2019