统一的连续伪凸逼近框架
本文介绍了通过应用已知算法到原问题的复合平滑近似,获得无约束或线性约束的复合非凸凹、极小极大(因而是非光滑的)问题的近似稳定点的平滑方案。具体而言,在无约束(resp. 有约束)的情况下,通过应用作者先前提出的加速不精确近端点算法(resp. 二次罚项)到其复合平滑近似,获得原问题的近似稳态点。同时,还建立了两个平滑方案的迭代复杂度界。最后,给出了数值结果,以展示无约束平滑方案的效率。
May, 2019
非凸优化中寻找近似驻点的计算和查询复杂性是本文的关键研究内容,其中包括在无约束域中寻找近似驻点的问题的 PLS 完备性、二维情况下的零阶算法以及近似驻点的查询复杂性的特征化,同时还研究了约束优化问题中寻找近似 KKT 点的查询复杂性,并指出约束优化中近似 KKT 点与无约束优化中近似驻点的对应关系。
Oct, 2023
本文提出了一种基于原始 - 对偶平滑框架的方法,用于寻找一类非光滑非凸优化问题的近似稳态点,并通过两种方法,即先对偶后原始和先原始后对偶平滑方法分析了框架的原始和对偶梯度复杂度。通过一个新开发的非 Hilbertian 不精确加速近端梯度算法来解决一类(强)凸 - 凹鞍点问题,进一步改进了已有方法的最佳 oracle 复杂度,并讨论了其变体和扩展。
Mar, 2020
我们提供了一个简单灵活的框架,用于设计差分隐私算法以找到非凸损失函数的近似稳定点。我们的框架基于使用私有近似风险最小化器来 “预热” 另一个用于寻找稳定点的私有算法。我们将这一框架应用于多个类别的非凸损失函数中,获得了改进的且有时是最优的速率。
Feb, 2024
本研究研究了非凸优化中的鞍点问题,提出了一个通用的框架,该框架可在多项式时间内以失配系数 $\rho<1$ 的速度收敛到问题的二阶稳定点。此外,还将研究结果扩展到了随机情形下,以更好地适应实际问题。
Sep, 2018
本文介绍了一些带有或没有耦合的非凸优化模型,使用了相关的优化算法,如条件梯度和 ADMM, 为专门处理非凸和非光滑优化问题的理论和算法的发展提出了一步。通过数值实验,证明了这些算法的高效性,特别是在张量鲁棒 PCA 的场景下。
May, 2016
本文研究随机算法优化非凸、非光滑的有限和问题。针对此问题,本文提出快速的随机算法,可获得常数迷你批量的收敛性。本文还使用这些算法的变种,证明了比批量近端梯度下降更快的收敛性,并在非凸、非光滑函数的一个子类中证明全局线性收敛率。
May, 2016
我们提出了一种新的近端 - 梯度方法,用于最小化可微、可能非凸的函数加上凸、可能非可微的函数,并探讨了度量可能在每次迭代中改变,近似计算近端点并给出充分条件的可能性。我们还展示了这个方法在图像恢复问题中的竞争力。
Jun, 2015
该论文介绍了一种通用的方案,使用最初设计用于最小化凸函数的梯度下降算法来解决非凸优化问题,该方案允许我们将这些方法用于弱凸性目标,这涵盖了机器学习和信号处理中通常出现的大类非凸函数。该方案无需假定目标函数具有凸性,而是通过自适应于未知的弱凸性常数来实现其保证。最后,本文还展示了将该方案应用于增量算法的几个实验结果。
Mar, 2017
利用多阶梯度下降上升算法解决机器学习中非凸场景下最小最大鞍点问题,给出了基于 Polyak-Lojasiewicz 条件的算法和 Concave 最大玩家目标函数的算法,并在 Fashion-MNIST 数据集上进行公平分类实验。
Feb, 2019