Optimal primal-dual methods for a class of saddle point problems
From MaRDI portal
Abstract: We present a novel accelerated primal-dual (APD) method for solving a class of deterministic and stochastic saddle point problems (SPP). The basic idea of this algorithm is to incorporate a multi-step acceleration scheme into the primal-dual method without smoothing the objective function. For deterministic SPP, the APD method achieves the same optimal rate of convergence as Nesterov's smoothing technique. Our stochastic APD method exhibits an optimal rate of convergence for stochastic SPP not only in terms of its dependence on the number of the iteration, but also on a variety of problem parameters. To the best of our knowledge, this is the first time that such an optimal algorithm has been developed for stochastic SPP in the literature. Furthermore, for both deterministic and stochastic SPP, the developed APD algorithms can deal with the situation when the feasible region is unbounded, as long as a saddle point exists. In the unbounded case, we incorporate the modified termination criterion introduced by Monteiro and Svaiter in solving SPP problem posed as monotone inclusion, and demonstrate that the rate of convergence of the APD method depends on the distance from the initial point to the set of optimal solutions.
Recommendations
- Accelerated stochastic algorithms for convex-concave saddle-point problems
- A primal-dual prediction-correction algorithm for saddle point optimization
- A primal-dual algorithm with line search for general convex-concave saddle point problems
- Solving saddle point problems: a landscape of primal-dual algorithm with larger stepsizes
- A generalized primal-dual algorithm with improved convergence condition for saddle point problems
Cited in
(only showing first 100 items - show all)- Stochastic accelerated alternating direction method of multipliers with importance sampling
- Accelerated schemes for a class of variational inequalities
- Acceleration of the PDHGM on partially strongly convex functions
- Solving structured nonsmooth convex optimization with complexity \(\mathcal {O}(\varepsilon ^{-1/2})\)
- Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization
- An optimal randomized incremental gradient method
- Modified algorithms for image inpainting in Fourier transform domain
- Point process estimation with Mirror Prox algorithms
- Dynamic stochastic approximation for multi-stage stochastic optimization
- Acceleration of primal-dual methods by preconditioning and simple subproblem procedures
- A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems
- Stochastic relaxed inertial forward-backward-forward splitting for monotone inclusions in Hilbert spaces
- High-performance statistical computing in the computing environments of the 2020s
- A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem
- Local saddle points for unconstrained polynomial optimization
- A unified convergence rate analysis of the accelerated smoothed gap reduction algorithm
- Accelerated gradient sliding for structured convex optimization
- Adaptive primal-dual stochastic gradient method for expectation-constrained convex stochastic programs
- The saddle point problem of polynomials
- On the linear convergence of the general first order primal-dual algorithm
- An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems
- Algorithms for stochastic optimization with function or expectation constraints
- Single image blind deblurring based on the fractional-order differential
- A double extrapolation primal-dual algorithm for saddle point problems
- Accelerated methods for saddle-point problem
- Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
- A first-order inexact primal-dual algorithm for a class of convex-concave saddle point problems
- A prediction-correction-based primal-dual hybrid gradient method for linearly constrained convex minimization
- Communication-efficient algorithms for decentralized and stochastic optimization
- Saddle points of rational functions
- Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity
- Accelerated alternating direction method of multipliers: an optimal \(O(1 / K)\) nonergodic analysis
- Optimal subgradient methods: computational properties for large-scale linear inverse problems
- A new algorithm for image inpainting in Fourier transform domain
- Block-proximal methods with spatially adapted acceleration
- A three-stage approach for segmenting degraded color images: smoothing, lifting and thresholding (SLaT)
- Fast bundle-level methods for unconstrained and ball-constrained convex optimization
- Distributed and consensus optimization for non-smooth image reconstruction
- Stochastic first-order methods for convex and nonconvex functional constrained optimization
- Solving saddle point problems: a landscape of primal-dual algorithm with larger stepsizes
- An alternative extrapolation scheme of PDHGM for saddle point problem with nonlinear function
- A new algorithm framework for image inpainting in transform domain
- An \(\mathcal O(1/{k})\) convergence rate for the variable stepsize Bregman operator splitting algorithm
- Conditional gradient sliding for convex optimization
- On the ergodic convergence rates of a first-order primal-dual algorithm
- On the global convergence rate of the gradient descent method for functions with Hölder continuous gradients
- Easily Parallelizable and Distributable Class of Algorithms for Structured Sparsity, with Optimal Acceleration
- An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- Adaptive parallel primal-dual method for saddle point problems
- Efficient Solvers for Saddle Point Problems with Applications to PDE–Constrained Optimization
- Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
- Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
- A primal-dual algorithm with line search for general convex-concave saddle point problems
- Reducing spatially varying out-of-focus blur from natural image
- Interior-proximal primal-dual methods
- Accelerated stochastic algorithms for convex-concave saddle-point problems
- Convergence of a piggyback-style method for the differentiation of solutions of standard saddle-point problems
- A generalized primal-dual algorithm with improved convergence condition for saddle point problems
- An inverse-adjusted best response algorithm for Nash equilibria
- Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
- Projection primal-dual method for saddle point optimization problems with simple constrained
- Convergence rate of \(\mathcal{O}(1/k)\) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems
- A distributed ADMM-like method for resource sharing over time-varying networks
- An accelerated linearized alternating direction method of multipliers
- An introduction to continuous optimization for imaging
- A stochastic variance reduced primal dual fixed point method for linearly constrained separable optimization
- Accelerated non-overlapping domain decomposition method for total variation minimization
- A new randomized primal-dual algorithm for convex optimization with fast last iterate convergence rates
- Reducing the Complexity of Two Classes of Optimization Problems by Inexact Accelerated Proximal Gradient Method
- Fast augmented Lagrangian method in the convex regime with convergence guarantees for the iterates
- Adaptively weighted difference model of anisotropic and isotropic total variation for image denoising
- Transformed primal-dual methods for nonlinear saddle point systems
- A stochastic variance-reduced accelerated primal-dual method for finite-sum saddle-point problems
- A stochastic variance reduction algorithm with Bregman distances for structured composite problems
- A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems
- Accelerated variance-reduced methods for saddle-point problems
- No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization
- Optimality Conditions for Nonsmooth Nonconvex-Nonconcave Min-Max Problems and Generative Adversarial Networks
- Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems
- Stochastic Saddle Point Problems with Decision-Dependent Distributions
- An inexact primal-dual smoothing framework for large-scale non-bilinear saddle point problems
- Derivative-free alternating projection algorithms for general nonconvex-concave minimax problems
- On dynamical system modeling of learned primal-dual with a linear operator \(\mathcal{K}\): stability and convergence properties
- General procedure to provide high-probability guarantees for stochastic saddle point problems
- A new prediction-correction primal-dual hybrid gradient algorithm for solving convex minimization problems with Linear constraints
- A proximal augmented Lagrangian method for linearly constrained nonconvex composite optimization problems
- Optimality conditions and numerical algorithms for a class of linearly constrained minimax optimization problems
- Fast numerical methods for image segmentation models
- Semi-proximal point method for nonsmooth convex-concave minimax optimization
- Non-ergodic convergence rate of an inertial accelerated primal-dual algorithm for saddle point problems
- Accelerated minimax algorithms flock together
- Practical acceleration of the Condat-Vũ algorithm
- Fast convergence of the primal-dual dynamical system and corresponding algorithms for a nonsmooth bilinearly coupled saddle point problem
- A practical and optimal first-order method for large-scale convex quadratic programming
- An accelerated primal-dual fixed point algorithm for three-block composite optimization problems
- A stochastic primal-dual splitting algorithm with variance reduction for composite optimization problems
- A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate
- Optimal methods for convex nested stochastic composite optimization
- All saddle points for polynomial optimization
This page was built for publication: Optimal primal-dual methods for a class of saddle point problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5245366)
