本文提出了一种原始 - 对偶算法框架,以获得近似解决方案来解决典型的约束凸优化问题,并严格描述了常见结构假设如何影响数值效率。通过选择双重平滑策略和中心点,我们的框架将分解算法、增广 Lagrange 以及交替方向乘子方法作为其特殊情况,并为所有迭代的原始目标残差和原始可行性间隙提供最优收敛速率。
Jun, 2014
本文介绍了一种分布式优化方法 ——CoCoA+,解决了大规模机器学习中通信瓶颈和全局参数的更新问题,使得非光滑的凸损失函数以更快的速度达到更优的性能表现。
Feb, 2015
本文介绍了一种新的一阶原始 - 对偶优化框架,利用平滑、加速和同伦等三个经典思想,实现了具有许多广泛应用的凸优化,达到了最佳的收敛效果,针对只包含非平滑函数的情况。同时提供了重新启动策略,大大提高了实际性能,并展示了与增广拉格朗日方法的关系以及如何利用严格收敛率保证来利用强凸目标。最后提供了两个实例验证,表明新的方法可以优于 Chambolle-Pock 和交替方向乘法算法等现有的算法。
Jul, 2015
本文介绍并分析了一族新的一阶优化算法,它对镜像下降和对偶平均进行了推广和统一,并定义了新的约束优化算法,结合了镜像下降和对偶平均的优点。我们的初步模拟研究表明,在某些情况下,这些新算法显著优于现有方法。
Oct, 2019
本篇论文提出了一种加速随机镜像下降法来解决平均函数和非强凸函数的问题,绕过了常见的小二次正则化降低性能的方法,可以更好地解决非强凸情况。
May, 2016
考虑由二次函数的期望值和任意凸函数组合成的复合目标函数的最小化问题,我们研究了随机双均值算法在恒定步长下的特性,证明其无需强凸假设即可获得 O (1/n) 的收敛速度,从而将欧几里得几何中关于最小二乘回归的较早结果扩展到了 (a) 所有凸正则化器以及约束条件,以及(b)由 Bregman 距离表示的所有几何形状。通过一种新的证明技巧来实现这一点,该技巧将随机和确定性递归联系起来。
Feb, 2017
本文提出了批处理和随机的原始 - 对偶算法,可以自适应地利用数据的强凸性,即使在没有正则化的情况下也能实现线性收敛,并介绍了适用于逻辑回归的免双重正演算法。
Mar, 2017
本文研究了分布式网络中去中心化优化的问题,尤其是基于双重平均子梯度的分布式算法及其收敛速度与网络大小和拓扑结构的关系,同时探讨了算法收敛和网络结构限制之间的关系,并证明了我们算法所需的迭代次数与网络谱隙成反比例关系。
May, 2010
本文提出了一种基于原始 - 对偶框架的分布式优化算法,无需使用难以构建的双重随机混合矩阵,通过维护对偶变量来跟踪相邻节点之间的差异,使用这种方法构建的分布式算法比采用梯度跟踪的算法具有更好的性能。
Dec, 2020
讨论非欧几里得确定性和随机算法,解决强凸和一致凸的优化问题,提供算法性能的准确性界限,设计针对强或一致凸性参数的自适应方法:在总迭代次数 $N$ 固定的情况下,它们的准确度与最优算法的准确度相同,直到 $N$ 的对数因子。
Jan, 2014