Optimal primal-dual methods for a class of saddle point problems
From MaRDI portal
Publication:5245366
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
(96)- High-performance statistical computing in the computing environments of the 2020s
- An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems
- Communication-efficient algorithms for decentralized and stochastic optimization
- A double extrapolation primal-dual algorithm for saddle point problems
- Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
- On the global convergence rate of the gradient descent method for functions with Hölder continuous gradients
- Local saddle points for unconstrained polynomial optimization
- An accelerated linearized alternating direction method of multipliers
- Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
- An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems
- Accelerated methods for saddle-point problem
- An optimal randomized incremental gradient method
- A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems
- Solving structured nonsmooth convex optimization with complexity \(\mathcal {O}(\varepsilon ^{-1/2})\)
- Optimal subgradient methods: computational properties for large-scale linear inverse problems
- Stochastic accelerated alternating direction method of multipliers with importance sampling
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- Adaptive primal-dual stochastic gradient method for expectation-constrained convex stochastic programs
- The saddle point problem of polynomials
- Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
- Conditional gradient sliding for convex optimization
- Modified algorithms for image inpainting in Fourier transform domain
- An \(\mathcal O(1/{k})\) convergence rate for the variable stepsize Bregman operator splitting algorithm
- An inverse-adjusted best response algorithm for Nash equilibria
- Fast bundle-level methods for unconstrained and ball-constrained convex optimization
- Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems
- A stochastic variance reduced primal dual fixed point method for linearly constrained separable optimization
- A first-order inexact primal-dual algorithm for a class of convex-concave saddle point problems
- An introduction to continuous optimization for imaging
- Accelerated gradient sliding for structured convex optimization
- Point process estimation with Mirror Prox algorithms
- A three-stage approach for segmenting degraded color images: smoothing, lifting and thresholding (SLaT)
- Dynamic stochastic approximation for multi-stage stochastic optimization
- Stochastic relaxed inertial forward-backward-forward splitting for monotone inclusions in Hilbert spaces
- Efficient Solvers for Saddle Point Problems with Applications to PDE–Constrained Optimization
- Block-proximal methods with spatially adapted acceleration
- Accelerated schemes for a class of variational inequalities
- Stochastic primal dual fixed point method for composite optimization
- Stochastic first-order methods for convex and nonconvex functional constrained optimization
- A primal-dual prediction-correction algorithm for saddle point optimization
- Acceleration of primal-dual methods by preconditioning and simple subproblem procedures
- Convergence rate of \(\mathcal{O}(1/k)\) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems
- Single image blind deblurring based on the fractional-order differential
- On the ergodic convergence rates of a first-order primal-dual algorithm
- A new randomized primal-dual algorithm for convex optimization with fast last iterate convergence rates
- Saddle points of rational functions
- Accelerated non-overlapping domain decomposition method for total variation minimization
- A unified convergence rate analysis of the accelerated smoothed gap reduction algorithm
- Accelerated alternating direction method of multipliers: an optimal \(O(1 / K)\) nonergodic analysis
- A generalized primal-dual algorithm with improved convergence condition for saddle point problems
- Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity
- On the linear convergence of the general first order primal-dual algorithm
- Accelerated stochastic algorithms for convex-concave saddle-point problems
- A primal-dual algorithm with line search for general convex-concave saddle point problems
- A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem
- Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
- Reducing spatially varying out-of-focus blur from natural image
- Algorithms for stochastic optimization with function or expectation constraints
- Easily Parallelizable and Distributable Class of Algorithms for Structured Sparsity, with Optimal Acceleration
- A new algorithm framework for image inpainting in transform domain
- Interior-proximal primal-dual methods
- Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization
- Acceleration of the PDHGM on partially strongly convex functions
- A distributed ADMM-like method for resource sharing over time-varying networks
- A stochastic variance-reduced accelerated primal-dual method for finite-sum saddle-point problems
- Reducing the Complexity of Two Classes of Optimization Problems by Inexact Accelerated Proximal Gradient Method
- An inexact primal-dual smoothing framework for large-scale non-bilinear saddle point problems
- Accelerated variance-reduced methods for saddle-point problems
- On dynamical system modeling of learned primal-dual with a linear operator \(\mathcal{K}\): stability and convergence properties
- Fast augmented Lagrangian method in the convex regime with convergence guarantees for the iterates
- Distributed and consensus optimization for non-smooth image reconstruction
- Projection primal-dual method for saddle point optimization problems with simple constrained
- Stochastic Saddle Point Problems with Decision-Dependent Distributions
- Derivative-free alternating projection algorithms for general nonconvex-concave minimax problems
- Optimality conditions and numerical algorithms for a class of linearly constrained minimax optimization problems
- A new algorithm for image inpainting in Fourier transform domain
- Fast numerical methods for image segmentation models
- Adaptively weighted difference model of anisotropic and isotropic total variation for image denoising
- Transformed primal-dual methods for nonlinear saddle point systems
- Semi-proximal point method for nonsmooth convex-concave minimax optimization
- A prediction-correction-based primal-dual hybrid gradient method for linearly constrained convex minimization
- Non-ergodic convergence rate of an inertial accelerated primal-dual algorithm for saddle point problems
- Convergence of a piggyback-style method for the differentiation of solutions of standard saddle-point problems
- Adaptive parallel primal-dual method for saddle point problems
- A stochastic variance reduction algorithm with Bregman distances for structured composite 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 for Nonsmooth Nonconvex-Nonconcave Min-Max Problems and Generative Adversarial Networks
- An alternative extrapolation scheme of PDHGM for saddle point problem with nonlinear function
- Accelerated minimax algorithms flock together
- No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization
- General procedure to provide high-probability guarantees for stochastic saddle point problems
- A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems
- Solving saddle point problems: a landscape of primal-dual algorithm with larger stepsizes
- 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
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)
