On the Convergence Time of Dual Subgradient Methods for Strongly Convex Programs
On the Convergence Time of Dual Subgradient Methods for Strongly Convex Programs
复制标题
DOI：
10.1109/tac.2017.2738153
复制
发表时间：
2015-03
影响因子：
6.8
通讯作者：
Hao Yu;M. Neely
中科院分区：
文献类型：
--
作者：
Hao Yu;M. Neely
本文研究了一般（可能不可微）强凸规划的双梯度方法的收敛时间。对于一般的凸程序，具有简单运行平均值（从迭代 0 开始运行平均值）的双次梯度/梯度方法的收敛时间已知为 $O(\frac{1}{\epsilon ^{2}})$。本文表明，一般强凸规划的收敛时间为 $O(\frac{1}{\epsilon })$ 。本文还考虑了平均方案的一种变体，称为滑动运行平均，并表明如果强凸程序的对偶函数是局部二次的，则滑动运行平均的对偶梯度方法的收敛时间为 $O(\log (\frac{1}{\epsilon }))$。通过数值实验进一步验证了收敛时间分析。
This paper studies the convergence time of dual gradient methods for general (possibly nondifferentiable) strongly convex programs. For general convex programs, the convergence time of dual subgradient/gradient methods with simple running averages (running averages started from iteration 0) is known to be $O(\frac{1}{\epsilon ^{2}})$. This paper shows that the convergence time for general strongly convex programs is $O(\frac{1}{\epsilon })$ . This paper also considers a variation of the average scheme, called the sliding running averages, and shows that if the dual function of the strongly convex program is locally quadratic then the convergence time of the dual gradient method with sliding running averages is $O(\log (\frac{1}{\epsilon }))$. The convergence time analysis is further verified by numerical experiments.