Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
From MaRDI portal
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 convergence rate on the primal-dual gap, and primal and dual objective residuals, where 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 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 rates even when the problem is "semi-strongly" convex. We verify our theoretical results via two well-known numerical examples.
Recommendations
- Acceleration and global convergence of a first-order primal-dual method for nonconvex problems
- On the ergodic convergence rates of a first-order primal-dual algorithm
- On the linear convergence of the general first order primal-dual algorithm
- On iteration complexity of a first-order primal-dual method for nonlinear convex cone programming
- An efficient primal dual prox method for non-smooth optimization
- Inexact first-order primal-dual algorithms
- Faster first-order primal-dual methods for linear programming using restarts and sharpness
- First-Order Methods for Nonconvex Quadratic Minimization
- Primal-dual incremental gradient method for nonsmooth and convex optimization problems
- Accelerated primal-dual gradient descent with linesearch for convex, nonconvex, and nonsmooth optimization problems
Cites work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A first-order primal-dual algorithm with linesearch
- A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science
- A monotone+skew splitting model for composite monotone inclusions in duality
- A new primal-dual algorithm for minimizing the sum of three functions with a linear operator
- A primal-dual fixed point algorithm for minimization of the sum of three convex separable functions
- A primal-dual splitting algorithm for finding zeros of sums of maximal monotone operators
- A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- A splitting algorithm for dual monotone inclusions involving cocoercive operators
- A three-operator splitting scheme and its optimization applications
- A unified primal-dual algorithm framework based on Bregman iteration
- Accelerated alternating direction method of multipliers: an optimal \(O(1 / K)\) nonergodic analysis
- Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
- An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems
- An accelerated linearized alternating direction method of multipliers
- An adaptive primal-dual framework for nonsmooth convex minimization
- An introduction to continuous optimization for imaging
- Bregman Iterative Algorithms for \ell₁-Minimization with Applications to Compressed Sensing
- Combining Lagrangian decomposition and excessive gap smoothing technique for solving large-scale separable convex optimization problems
- Complexity of first-order inexact Lagrangian and penalty methods for conic convex programming
- Complexity of Variants of Tseng's Modified F-B Splitting and Korpelevich's Methods for Hemivariational Inequalities with Applications to Saddle-point and Convex Optimization Problems
- Convergence analysis for a primal-dual monotone + skew splitting algorithm with applications to total variation minimization
- Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective
- Convergence Rate Analysis of Primal-Dual Splitting Schemes
- Convergence rate analysis of several splitting schemes
- Convergence rate analysis of the forward-Douglas-Rachford splitting scheme
- Convex analysis and monotone operator theory in Hilbert spaces
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Excessive Gap Technique in Nonsmooth Convex Minimization
- Fast alternating direction optimization methods
- Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming
- Inertial, corrected, primal-dual proximal splitting
- Iteration complexity analysis of dual first-order methods for conic convex programming
- Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers
- Local convergence properties of Douglas-Rachford and alternating direction method of multipliers
- On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean
- On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the equivalence of the primal-dual hybrid gradient method and Douglas-Rachford splitting
- On the ergodic convergence rates of a first-order primal-dual algorithm
- Optimal primal-dual methods for a class of saddle point problems
- Partial inverse of a monotone operator
- Primal-dual decomposition by operator splitting and applications to image deblurring
- Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Proximal alternating penalty algorithms for nonsmooth constrained convex optimization
- Proximal splitting methods in signal processing
- Signal Recovery by Proximal Forward-Backward Splitting
- Smooth minimization of non-smooth functions
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Splitting Methods in Communication, Imaging, Science, and Engineering
- Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications
- The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k^2
Cited in
(21)- A unified convergence rate analysis of the accelerated smoothed gap reduction algorithm
- Inertial accelerated primal-dual methods for linear equality constrained convex optimization problems
- New primal-dual algorithms for a class of nonsmooth and nonlinear convex-concave minimax problems
- A Two-Stage Color Image Segmentation Method Based on Saturation-Value Total Variation
- Running Primal-Dual Gradient Method for Time-Varying Nonconvex Problems
- A primal-dual flow for affine constrained convex optimization
- A new randomized primal-dual algorithm for convex optimization with fast last iterate convergence rates
- A golden ratio proximal alternating direction method of multipliers for separable convex optimization
- Transformed primal-dual methods for nonlinear saddle point systems
- Accelerated primal-dual methods with adaptive parameters for composite convex optimization with linear constraints
- Non-ergodic convergence rate of an inertial accelerated primal-dual algorithm for saddle point problems
- Application of a reflected forward backward splitting method with momentum to a fractional-order lung cancer model
- Fast primal-dual algorithm with Tikhonov regularization for a linear equality constrained convex optimization problem
- Practical proximal primal-dual algorithms for structured saddle point problems
- Fast reflected forward-backward algorithm: achieving fast convergence rates for convex optimization with linear cone constraints
- Inertial stochastic reflected forward backward method with applications to traffic network problems
- A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate
- The degenerate variable metric proximal point algorithm and adaptive stepsizes for primal–dual Douglas–Rachford
- Faster augmented Lagrangian method with inertial steps for solving convex optimization problems with linear constraints
- Revisiting extragradient-type methods. I: Generalizations and sublinear convergence rates
- Accelerated linearized alternating direction method of multipliers with Nesterov extrapolation
This page was built for publication: Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4971027)
