利用原始对偶一阶算法从数据中挖掘强凸性
本文提出了一种原始 - 对偶算法框架,以获得近似解决方案来解决典型的约束凸优化问题,并严格描述了常见结构假设如何影响数值效率。通过选择双重平滑策略和中心点,我们的框架将分解算法、增广 Lagrange 以及交替方向乘子方法作为其特殊情况,并为所有迭代的原始目标残差和原始可行性间隙提供最优收敛速率。
Jun, 2014
讨论非欧几里得确定性和随机算法,解决强凸和一致凸的优化问题,提供算法性能的准确性界限,设计针对强或一致凸性参数的自适应方法:在总迭代次数 $N$ 固定的情况下,它们的准确度与最优算法的准确度相同,直到 $N$ 的对数因子。
Jan, 2014
提出了一种基于新动量项的原始 - 对偶算法,使用偏导数来求解不要求耦合项线性的凸 - 凹函数产生的鞍点问题,并给出了具体的收敛速度。
Mar, 2018
本文提出了两种针对带约束凸问题的一阶方法,分别使用增广拉格朗日方法和单一近端梯度步进行变量更新,并证明了它们的全局和局部收敛性。数值实验验证了理论结果与实际表现的一致性。
Nov, 2017
研究零阶算法求解非凸最小最大问题在确定性和随机设置下的紧密线性约束,为确定性和随机设置下求解非凸凹最小最大问题提出两种单环算法,即零阶原始 -- 对偶交替投影梯度(ZO-PDAPG)算法和零阶正则化动量原始 -- 对偶投影梯度算法(ZO-RMPDPG),其迭代复杂度被证明为 Ο(ε^(-2))(非凸凹最小最大问题)和 Ο(ε^(-4))(非凸凹最小最大问题),在确定性设置下,持有 ε- 稳定点,并且在随机设置下,迭代复杂度分别为 Ο̃(ε^(-3)) 和 Ο̃(ε^(-6.5))。据我们所知,它们是第一个能够解决确定性和随机设置下的非凸凹最小最大问题的零阶算法,并具有迭代复杂度保证。
Jan, 2024
本文介绍了如何使用随机镜像下降法和非均匀采样方案,来快速训练高维度特征空间、多分类通用的线性分类器,特别是在多类 Hinge 损失下,本文提出了一个迭代次数为 $O (d+n+k)$ 的子线性算法。
Feb, 2019
考虑给定一个闭合凸不确定性集合的罚函数分布鲁棒优化 (DRO) 问题,该问题涵盖了 $f$-DRO、Wasserstein-DRO 以及在实践中使用的谱 /$L$-risk 形式,我们提出了 Drago,这是一种基于随机原始对偶算法,能在强凸 - 强凹 DRO 问题上实现最先进的线性收敛率。该方法结合了随机化和循环成分以及小批量处理,能有效处理 DRO 中原始问题和对偶问题的独特的非对称性质。我们通过分类和回归的数值基准来支持我们的理论结果。
Mar, 2024
本文探讨了与正则化的经验风险线性预测器极小化相伴的一般凸优化问题,并将其重构为凸凹鞍点问题。我们提出了随机原始对偶坐标(SPDC)方法,该方法在随机选择的对偶变量上进行最大化和在原始变量上进行最小化之间交替运算,并通过原始变量的外推步骤以提高收敛速度。我们还开发了 SPDC 方法的小批量版本,以便实现并行计算,并在对偶变量的加权采样概率上进行了扩展,使其比非标准化数据上的均匀采样具有更好的复杂度,理论和经验表明 SPDC 方法与一些最先进的优化方法相比具有可比或更好的性能。
Sep, 2014
本文提出了新的随机原始对偶算法,用于解决具有线性预测器的正则化经验风险最小化问题。通过泰勒展开、凸组合和割平技巧得到具有较优复杂度和收敛性质的算法,进一步提出了方差减少版算法和数值实验表明该算法在高维问题上优于现有算法,收敛速度更快。
Nov, 2018
本研究针对具有凸 - 凹鞍点问题的优化进行了研究,证明了即使 $f$ 不强凸,使用一般的原始 - 对偶梯度方法也可以实现线性收敛,并给出了具有有限和结构的凸 - 凹鞍点问题的原始 - 对偶随机方差减少梯度方法的分析。
Feb, 2018