Optimization Online


Non-Stationary First-Order Primal-Dual Algorithms with Fast Convergence Rates

Quoc Tran-Dinh (quoctd***at***email.unc.edu)
Yuzixuan Zhu (zyzx***at***live.unc.edu)

Abstract: In this paper, we propose two novel non-stationary first-order primal-dual algorithms to solve nonsmooth composite convex optimization problems. Unlike existing primal-dual schemes where the parameters are often fixed, our methods use pre-defined and dynamic sequences for parameters. We prove that our first algorithm can achieve O(1/k) convergence rate on the primal-dual gap, and primal and dual objective residuals, where k is the iteration counter. Our rate is on the non-ergodic (i.e., the last iterate) sequence of the primal problem and on the ergodic (i.e., the averaging) sequence of the dual problem, which we call semi-ergodic rate. By modifying the step-size update rule, this rate can be boosted even faster on the primal objective residual. When the problem is strongly convex, we develop a second primal-dual algorithm that exhibits O(􏰀1/k^2)􏰁 convergence rate on the same three types of guarantees. Again by modifying the step-size update rule, this rate becomes faster on the primal objective residual. Our primal-dual algorithms are the first ones to achieve such fast convergence rate guarantees under mild assumptions compared to existing works, to the best of our knowledge. As byproducts, we apply our algorithms to solve constrained convex optimization problems and prove the same convergence rates on both the objective residuals and the feasibility violation. We still obtain at least O(􏰀1/k^2)􏰁 rates even when the problem is “semi-strongly” convex. We verify our theoretical results via two well-known numerical examples.

Keywords: Non-stationary primal-dual method · nonergodic convergence rate · fast convergence rates · composite convex minimization · constrained convex optimization.

Category 1: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 04/29/2019
Entry Accepted: 04/29/2019
Entry Last Modified: 10/08/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society