A New Primal-Dual Algorithm for a Class of Nonlinear Compositional Convex Optimization Problems

Abstract

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 $\mathcal{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 $\mathcal{O}(1/k^2)$ 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.

arXiv comment26 pages, 2 figures, 1 table

References in corpus (13)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
• Near-Optimal Algorithms for Minimax Optimization
• A Convex Duality Framework for GANs
• Efficient Algorithms for Smooth Minimax Optimization
• Algorithms for stochastic optimization with functional or expectation constraints
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
• Restarting accelerated gradient methods with a rough strong convexity estimate
• Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity
• Primal-dual stochastic gradient method for convex programs with many functional constraints
• Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
• Augmented Lagrangian based first-order methods for convex-constrained programs with weakly-convex objective