On the convergence time of the drift-plus-penalty algorithm for strongly convex programs
Hao Yu, Michael J. Neely · 2015
This paper studies the convergence time of the drift-plus-penalty algorithm for strongly convex programs. The drift-plus-penalty algorithm was originally developed to solve more general stochastic optimization and is closely related to the dual subgradient algorithm when applied to deterministic convex programs. For general convex programs, the convergence time of the drift-plus-penalty algorithm is known to be O(1/ϵ1/2). This paper shows that the convergence time for general strongly convex programs is O(1/ϵ). This paper also proposes a new variation of the drift-plus-penalty algorithm, the drift-plus-penalty algorithm with shifted running averages, and shows that if the dual function of the strongly convex program is smooth and locally quadratic then the convergence time of the new algorithm is O(1/ϵ2/3). The convergence time analysis is further verified by numerical experiments.