受约束稀疏优化的高效 DC 算法
本论文考虑了一类差分凸(DC)优化问题,其中目标是有界的级别,是光滑的凸函数与利普希茨梯度,一个适当的闭凸函数和一个连续的凹函数的总和。针对这种问题,本论文提出了一种带外推的 DC 算法,通过在一般情况下选择外推参数来加速算法并分析其全局收敛性和收敛速度。数值实验表明,该算法通常优于现有算法。
Dec, 2016
本文提出了一个优化算法,并探讨了其在高维度下求解非凸正则化稀疏学习问题中的应用。在多阶段凸松弛的基础上,我们提出的算法融合了近端牛顿算法和差分凸(DC)编程,实现了强大的计算和统计保证。数值实验证明了我们理论的有效性。
Jun, 2017
介绍了 DC 算法及其变种算法,并将其应用于 DS 问题的 DC 程序中,并将收敛性质与 DS 问题的收敛性质相连结,取得了比现有基线更好的结果。
May, 2023
给出了一种用于解决具有弱凸目标和凸线性 / 非线性约束问题的阻尼近端增广 Lagrange 方法(DPALM)。通过采用阻尼对偶步长而不是全步长,确保对偶迭代的有界性。如果每个 DPALM 子问题解到适当的精度,则 DPALM 可以在 O (ε^{-2}) 的外部迭代中产生一个近似 ε-KKT 点。此外,我们在目标函数为正则化平滑函数或正则化构成形式的情况下建立了 DPALM 的整体迭代复杂性。对于前一种情况,通过将加速近端梯度(APG)方法应用于每个 DPALM 子问题,DPALM 实现了复杂度为 Τ(ε^{-2.5}),从而产生一个 ε-KKT 点。对于后一种情况,通过使用 APG 来解决每个子问题的 Moreau 包络平滑版本,DPALM 的复杂度为 O (~ε^{-3}),从而得到一个近似 ε-KKT 点。我们的外部迭代复杂性和整体复杂性要么推广了现有的无约束或线性约束问题的最佳结果到凸约束问题,要么改进了解决相同结构问题的已知最佳结果。此外,通过在线性 / 二次约束的非凸二次规划和线性约束的鲁棒非线性最小二乘上进行数值实验,展示了所提出的 DPALM 方法在效率上超过了几种最先进的方法。
Nov, 2023
本文证明了许多著名函数具有凹凸性质,并研究了二阶随机规划中的价值函数与凸性无关的情况。研究结果表明许多风险分析中的复合统计函数,包括风险价值、条件风险价值、期望、风险价值和条件风险价值基于随机偏差函数都具有凹凸性质。
Apr, 2017
我们提出了一种优化单隐藏层神经网络参数的算法,其中我们导出了目标函数的分块凸差(DC)函数表示。基于后者,我们提出了一种分块坐标下降(BCD)方法,将其与定制的凸差函数算法(DCA)结合起来。我们证明了所提算法的全局收敛性。此外,我们在理论上分析了参数的收敛速度和值的收敛速度(即训练损失)。我们给出了算法收敛线性或甚至更快的条件,取决于损失函数的局部形状。我们通过数值实验验证了理论推导的正确性,并在训练损失和测试损失方面将我们的算法与最先进的基于梯度的求解器进行了比较。
Jan, 2024
研究零阶算法求解非凸最小最大问题在确定性和随机设置下的紧密线性约束,为确定性和随机设置下求解非凸凹最小最大问题提出两种单环算法,即零阶原始 -- 对偶交替投影梯度(ZO-PDAPG)算法和零阶正则化动量原始 -- 对偶投影梯度算法(ZO-RMPDPG),其迭代复杂度被证明为 Ο(ε^(-2))(非凸凹最小最大问题)和 Ο(ε^(-4))(非凸凹最小最大问题),在确定性设置下,持有 ε- 稳定点,并且在随机设置下,迭代复杂度分别为 Ο̃(ε^(-3)) 和 Ο̃(ε^(-6.5))。据我们所知,它们是第一个能够解决确定性和随机设置下的非凸凹最小最大问题的零阶算法,并具有迭代复杂度保证。
Jan, 2024
本论文提出了一种新的原始对偶方法来解决带限制的马尔可夫决策过程问题,通过熵正规化策略优化器、对偶变量正规化器和 Nesterov 加速梯度下降对偶优化器等创新方法,全局收敛至凸优化下的凸约束,显示了目前已有的原始对偶算法无法达到的最优复杂度 O (1/ε)。
Oct, 2021
本文介绍了一种 Stochastic Dual Coordinate Ascent 算法的变体,用于解决非凸损失函数的正则化损失最小化问题,并且证明了只要期望损失是凸的,就可以确保该算法具有线性收敛速度。
Feb, 2015