一种简单的并行算法,对于一般的凸规划问题具有 O(1/t)的收敛速率
本研究提出了基于 ADMM 算法的分布式算法,用于通过网络通信最小化局部已知的凸函数之和,研究表明,在函数为凸函数时,目标函数值和可行性冲突都会收敛,当函数是强凸函数且有 Lipschitz 连续梯度时,该算法生成的序列会线性收敛到最优解。此外,我们的分析还通过节点的最大和最小度以及网络的代数连通度凸显了网络结构对收敛速度的影响。
Jan, 2016
本文研究了基于随机子梯度优化的非光滑函数的优化问题,提出一种具有 O(1/T)收敛率的算法,并且证明在去除局部 polyhedral 假设时具有一般的收敛性,最后,在确定性问题的特殊情况下,在局部 polyhedral 假设上的收敛性得到了改善。
Jul, 2016
本文提出了一种新的投影随机次梯度方法的平均技术,通过使用加权平均和易于证明和实现的方法,每次迭代使用权重 t+1,达到 O (1/t) 的收敛速度。通过与现有技术的经验比较,证明了其类似的性能表现。
Dec, 2012
本文提出了一种异步并行随机坐标下降算法,它具有线性收敛速率和 $1/K$ 的次线性速率,可实现基于多核系统的近线性加速,并取得了在 40 核处理器上的实现结果。
Nov, 2013
提出了一种适应性在线梯度下降算法,用于解决具有长期约束的在线凸优化问题,可以处理任意凸约束,该算法在损失和约束违规方面分别具有 O (T^max {β,1−β}) 和 O (T^(1−β/2)) 的累积遗憾界,优于 Mahdavi 等(2012 年)最好的已知累积遗憾界,该算法的性能已在实践中得到验证。
Dec, 2015
本文提出了一种用于解决多块凸优化问题的随机 Primal-Dual 近端块坐标更新框架,并使用其达到 $O (1/t)$ 的收敛速度,且包含现有算法的特例,以及推广至解决随机编程的问题。
May, 2016
本文研究了一类非光滑的分散式多智能体最优化问题,该代理旨在最小化局部强凸光滑组成部分和一个共同的非光滑项。我们提出了一个通用的原始对偶算法框架,统一了许多现有的最先进的算法。我们在非光滑项存在的情况下,证明了所提出的方法向确切解的线性收敛。此外,对于更一般的具有代理特定非光滑术语的问题类,我们展示了使用光滑和非光滑部分的梯度和临界映射的算法类别的线性收敛在最坏的情况下无法实现。我们进一步提供了一个数字反例,展示了某些最先进的算法如何在强凸目标和不同的局部非光滑项的情况下无法线性收敛。
Sep, 2019
本文研究了分布式优化中最近提出的 subgradient-push 方法在时变有向图上的收敛速度,并证明在强凸函数和具有 Lipschitz 梯度的情况下,即使只有随机梯度样本可用,其收敛速度为 O ((ln t)/t),这比先前已知的(一般)凸函数的 O ((ln t)/√t) 更快。
Jun, 2014
通过对 Shor 子梯度分析的推广,我们将子梯度方法的经典收敛速度理论扩展到可适用于非 Lipschitz 函数。我们证明了在任何具有局部 Lipschitz 性的凸函数中,确定性投影子梯度算法的全局 O(1/√T)收敛速度。我们还表明,对于具有最多二次增长的凸函数,随机投影子梯度方法的收敛速度为 O(1/√T),在强凸性或较弱的二次下限条件下,该速度可进一步提高至 O (1/T)。
Dec, 2017