2020/06/16 by Yuzixuan Zhu, Zhu, Yuzixuan, Deyi Liu +3
Computer Science · Engineering · #90-08 #90C06 #90C25 #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2006.09263
openalex publication_date 2020/06/16 · openalex created_date 2021/04/26 · openalex updated_date 2026/07/28
We develop a novel primal-dual algorithm to solve a class of nonsmooth and nonlinear compositional convex minimization problems, which covers many existing and brand-new models as special cases. Our approach relies on a combination of a new nonconvex potential function, Nesterov's accelerated scheme, and an adaptive parameter updating strategy. Our algorithm is single-loop and has low per-iteration complexity. Under only general convexity and mild assumptions, our algorithm achieves O(1/k) convergence rates through three different criteria: primal objective residual, dual objective residual, and primal-dual gap, where k is the iteration counter. Our rates are both ergodic (i.e., on an averaging sequence) and non-ergodic (i.e., on the last-iterate sequence). These convergence rates can be accelerated up to O(1/k2) if only one objective term is strongly convex (or equivalently, its conjugate is L-smooth). To the best of our knowledge, this is the first algorithm achieving optimal rates on the primal last-iterate sequence for nonlinear compositional convex minimization. As a by-product, we specify our algorithm to solve a general convex cone constrained program with both ergodic and non-ergodic rate guarantees. We test our algorithms and compare them with two recent methods on a binary classification and a convex-concave game model.