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