亚线性复杂度下非凸非光滑约束组合问题的一阶优化方法：下界复杂度与近似最优方法

Jul, 2023

亚线性复杂度下非凸非光滑约束组合问题的一阶优化方法：下界复杂度与近似最优方法

First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods

HTML

PDF

Wei Liu, Qihang Lin, Yangyang Xu

TL;DR本文针对一个类别的复合非凸非光滑优化问题，通过使用两个不同的一阶预言机，在最优性公差ϵ>0的情况下建立FOMs的下界复杂性界，并提出一个非精确近端梯度法来解决该问题。所提出的IPG方法的预言机复杂度与我们建立的下界匹配。

Abstract

Many recent studies on first-order methods (FOMs) focus on \emph{composite non-convex non-smooth} optimization with linear and/or nonlinear function constraints. Upper (or worst-case) complexity bounds have been established for these methods. However, little can be claimed about their

发现论文，激发创造

结构化非凸非光滑优化：算法和迭代复杂度分析

本文介绍了一些带有或没有耦合的非凸优化模型，使用了相关的优化算法，如条件梯度和ADMM，为专门处理非凸和非光滑优化问题的理论和算法的发展提出了一步。通过数值实验，证明了这些算法的高效性，特别是在张量鲁棒PCA的场景下。

May, 2016

优化复合目标的紧密复杂度界

通过使用分量函数的梯度和prox oracles提供了最小化m个凸函数平均值的复杂性的严格上下界；我们表明决定性和随机优化之间存在显着差距。对于光滑函数，我们表明在确定性和随机设置中，加速梯度下降(AGD)和SVRG的加速变体分别是最优的，并且梯度Orcale足以获得最佳速率。对于非光滑函数，通过接入prox oracles可降低复杂度，因此，我们提出基于平滑的最优方法，以改进仅使用梯度访问的方法。

May, 2016

关于平滑非凸有限和优化的下界

本文研究了平滑的非凸有限和优化的下界，并证明了在不同设置下找到ε-次优点和ε-近似稳定点的复杂度的严格下界，以及一些现有算法的最佳增量一阶预测器（IFO）复杂度。

Jan, 2019

有约束极小极大优化的复杂性

本文通过分析优化问题的计算复杂性，阐明了一系列非凸非凹目标函数的约束极值优化问题存在的困难，同时证明了该问题在Nemirovsky-Yudin模型中的难度，这与最小化问题在同样设置下可以使用Projected Gradient Descent进行近似局部最小值的行为形成了对比。

Sep, 2020

有限和优化问题的下限复杂度：结果与构造

本文研究了有限和优化问题的下限复杂度界限，并基于分组的新方法构造了硬实例，从而建立了有限和最大最小优化问题的下限复杂度界限。

Mar, 2021

非凸强凹极小-极大优化的复杂性

本文研究非凸强凹（NC-SC）平滑极小值问题的近似稳定点的复杂度，在一般和平均平滑有限和设置中建立了非平凡的较低复杂度下界。我们提出了一种通用的加速方案，使用现有的基于梯度的方法来解决一系列的精心制作的强凸-强凹子问题，进而缩小了复杂度差距，尤其是在一般情况下，我们提出的算法的复杂度几乎与下界相当。

Mar, 2021

非凸非凹极小极大优化的高阶方法

使用高阶方法结合离散/连续时间分析，研究了结构化的非凸非凹min-max问题中算子范数最小化问题的近似最优解，与一阶方法相比，实验结果表明其具有显著优势。

Apr, 2023

梯度下降的非均匀平滑性

该研究介绍了一种局部一阶平滑性oracle（LFSO），可以用于调整梯度下降方法的步长，从而改善全局和局部收敛性。通过应用LFSO于修正的一阶方法，可以在非强凸问题中实现全局线性收敛速度，从而提高了一般（加速）一阶方法的收敛率下界。

Nov, 2023

在更细粒度上的优化: 有界局部次梯度变化视角

这篇文章研究了在有界局部次梯度变化情况下的非光滑优化问题，定义了目标函数的类别，包括传统优化问题中基于目标函数的Lipschitz连续性或梯度的Holder/Lipschitz连续性的函数，并且包含了既不是Lipschitz连续也没有Holder连续梯度的函数类别。研究结果表明在传统的优化问题类别中，所定义的类别参数能够得到更为精细的复杂度界限，并恢复了最坏情况下的传统oracle复杂度界限，同时对于不是最坏情况的函数通常能够得到更低的oracle复杂度。此外，该文章还强调了在并行计算环境中非光滑优化的复杂度与次梯度集合的平均宽度有关。

Mar, 2024

非凸高维随机优化的非光滑和非欧几里德近端项随机一阶方法

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

Jun, 2024