A KL-based Analysis Framework with Applications to Non-Descent Optimization Methods

我们提出了一种新颖的分析框架，基于Kurdyka-Lojasiewicz性质，用于非凸情况下非下降型优化方法。我们的框架允许覆盖广泛的算法类别，包括通常用于随机和分布式优化的算法。具体而言，它使得能够分析缺乏足够下降性质且不需要访问完整（确定性）梯度信息的一阶方法。我们利用这一框架首次建立了分布式梯度方法和联邦平均在温和假设下的迭代收敛和相应速率。此外，基于新的分析技术，我们展示了随机重排和随机梯度下降方法的收敛性，而不需要典型的先验有界迭代假设。

本论文旨在提出一种基于Kurdyka-Lojasiewicz性质的非下降型优化方法的分析框架，以应对非凸情况下的优化问题。该框架适用于包括随机和分布式优化在内的广泛算法类别，特别是对于那些缺乏足够下降性质且不需要完整（确定性）梯度信息的一阶方法。本论文利用该框架首次建立了分散梯度法和联邦平均法的迭代收敛性和相应速率，而且在不需要典型的先验有界迭代假设的情况下，基于新的分析技术，证明了随机重排和随机梯度下降法的收敛性。

本论文提出了一种基于Kurdyka-Lojasiewicz性质的非下降型优化方法的分析框架，以应对非凸情况下的优化问题。该框架适用于广泛的算法类别，特别是对于那些缺乏足够下降性质且不需要完整（确定性）梯度信息的一阶方法。

本论文的亮点在于首次建立了分散梯度法和联邦平均法的迭代收敛性和相应速率，而且在不需要典型的先验有界迭代假设的情况下，证明了随机重排和随机梯度下降法的收敛性。此外，本论文还提供了实验设计和使用的数据集，并且开源了代码。

在最近的研究中，也有一些相关的工作。例如，“Stochastic Gradient Descent with Restart: A Simple Yet Efficient First-Order Optimization Algorithm for DNNs”和“Non-convex Optimization for Machine Learning: Design Challenges and Opportunities”。