On the ergodic convergence rates of a first-order primal-dual algorithm

DOI10.1007/s10107-015-0957-3zbMath1350.49035OpenAlexW2241435520MaRDI QIDQ312675

Thomas Pock, Antonin Chambolle

Publication date: 16 September 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-015-0957-3

zbMATH Keywords

convergence ratesergodic convergencefirst order algorithmsprimal-dual algorithmssaddle-point preoblems

Mathematics Subject Classification ID

Convex programming (90C25) Numerical methods involving duality (49M29) Numerical optimization and variational techniques (65K10) Complexity and performance of numerical algorithms (65Y20)

Related Items

A new randomized primal-dual algorithm for convex optimization with fast last iterate convergence rates, Accelerated Bregman Primal-Dual Methods Applied to Optimal Transport and Wasserstein Barycenter Problems, Approximation Schemes for Materials with Discontinuities, Decentralized multi-agent optimization based on a penalty method, Faster Lagrangian-Based Methods in Convex Optimization, On the Convergence of Stochastic Primal-Dual Hybrid Gradient, 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, Weak and linear convergence of a generalized proximal point algorithm with alternating inertial steps for a monotone inclusion problem, Golden Ratio Primal-Dual Algorithm with Linesearch, A Generalized Primal-Dual Algorithm with Improved Convergence Condition for Saddle Point Problems, Fast augmented Lagrangian method in the convex regime with convergence guarantees for the iterates, Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists, Multi-step inertial strictly contractive PRSM algorithms for convex programming problems with applications, Some extensions of the operator splitting schemes based on Lagrangian and primal–dual: a unified proximal point analysis, Discrete potential mean field games: duality and numerical resolution, A unified primal-dual algorithm framework for inequality constrained problems, Zeroth-order single-loop algorithms for nonconvex-linear minimax problems, Inertial proximal ADMM for separable multi-block convex optimizations and compressive affine phase retrieval, A partially inexact generalized primal-dual hybrid gradient method for saddle point problems with bilinear couplings, 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, No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization, Robust Accelerated Primal-Dual Methods for Computing Saddle Points, Differentiating Nonsmooth Solutions to Parametric Monotone Inclusion Problems, Quasi-static frictional contact analysis free from solutions of linear equations: an approach based on primal-dual algorithm, Inertial, Corrected, Primal-Dual Proximal Splitting, Understanding the convergence of the preconditioned PDHG method: a view of indefinite proximal ADMM, Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems, Faster first-order primal-dual methods for linear programming using restarts and sharpness, The operator splitting schemes revisited: primal-dual gap and degeneracy reduction by a unified analysis, An inexact primal-dual smoothing framework for large-scale non-bilinear saddle point problems, A partially inertial customized Douglas-Rachford splitting method for a class of structured optimization problems, Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games, Golden ratio proximal gradient ADMM for distributed composite convex optimization, Convergence Rate Analysis of a Dykstra-Type Projection Algorithm, Convergence of Inexact Forward--Backward Algorithms Using the Forward--Backward Envelope, Higher-order total variation approaches and generalisations, Controlling Propagation of Epidemics via Mean-Field Control, Computational Methods for First-Order Nonlocal Mean Field Games with Applications, Local linear convergence analysis of Primal–Dual splitting methods, A Distributed ADMM-like Method for Resource Sharing over Time-Varying Networks, Splitting with Near-Circulant Linear Systems: Applications to Total Variation CT and PET, RECENT ADVANCES IN DOMAIN DECOMPOSITION METHODS FOR TOTAL VARIATION MINIMIZATION, Solving Large-Scale Optimization Problems with a Convergence Rate Independent of Grid Size, Approximate first-order primal-dual algorithms for saddle point problems, Learning Consistent Discretizations of the Total Variation, A Stochastic Variance Reduced Primal Dual Fixed Point Method for Linearly Constrained Separable Optimization, A primal-dual flow for affine constrained convex optimization, Accelerated Non-Overlapping Domain Decomposition Method for Total Variation Minimization, Bilevel Methods for Image Reconstruction, Primal-Dual Extragradient Methods for Nonlinear Nonsmooth PDE-Constrained Optimization, REGINN-IT method with general convex penalty terms for nonlinear inverse problems, A unified convergence rate analysis of the accelerated smoothed gap reduction algorithm, WARPd: A Linearly Convergent First-Order Primal-Dual Algorithm for Inverse Problems with Approximate Sharpness Conditions, On iteration complexity of a first-order primal-dual method for nonlinear convex cone programming, ADMM for monotone operators: convergence analysis and rates, Accelerated gradient sliding for structured convex optimization, Inertial Proximal ADMM for Linearly Constrained Separable Convex Optimization, Entropic Approximation of Wasserstein Gradient Flows, Scaling algorithms for unbalanced optimal transport problems, A mean field game inverse problem, On lower iteration complexity bounds for the convex concave saddle point problems, Proportional-integral projected gradient method for conic optimization, Total Variation on a Tree, Techniques for gradient-based bilevel optimization with non-smooth lower level problems, Computational mean-field information dynamics associated with reaction-diffusion equations, On the linear convergence of the general first order primal-dual algorithm, Mean field control problems for vaccine distribution, A function space framework for structural total variation regularization with applications in inverse problems, Inertial generalized proximal Peaceman-Rachford splitting method for separable convex programming, A primal-dual algorithm framework for convex saddle-point optimization, Inexact first-order primal-dual algorithms, Linear convergence of primal-dual gradient methods and their performance in distributed optimization, Unified linear convergence of first-order primal-dual algorithms for saddle point problems, Preconditioned three-operator splitting algorithm with applications to image restoration, iPiasco: inertial proximal algorithm for strongly convex optimization, On relaxation of some customized proximal point algorithms for convex minimization: from variational inequality perspective, Domain decomposition methods using dual conversion for the total variation minimization with \(L^1\) fidelity term, Enforcing geometrical priors in deep networks for semantic segmentation applied to radiotherapy planning, A new effective bias field correction model with TGV regularization, Primal-dual fixed point algorithm based on adapted metric method for solving convex minimization problem with application, Total roto-translational variation, Robust multicategory support matrix machines, A generalized forward-backward splitting operator: degenerate analysis and applications, Testing and non-linear preconditioning of the proximal point method, An algorithmic framework of generalized primal-dual hybrid gradient methods for saddle point problems, Single image blind deblurring based on the fractional-order differential, Crouzeix-Raviart approximation of the total variation on simplicial meshes, Convex histogram-based joint image segmentation with regularized optimal transport cost, Acceleration of the PDHGM on partially strongly convex functions, Accelerated alternating descent methods for Dykstra-like problems, A First-Order Primal-Dual Algorithm with Linesearch, Golden ratio algorithms for variational inequalities, Bregman three-operator splitting methods, Variational image motion estimation by preconditioned dual optimization, Geodesic PCA versus Log-PCA of Histograms in the Wasserstein Space, NESTANets: stable, accurate and efficient neural networks for analysis-sparse inverse problems, An alternative extrapolation scheme of PDHGM for saddle point problem with nonlinear function, A double extrapolation primal-dual algorithm for saddle point problems, An adaptive primal-dual framework for nonsmooth convex minimization, An accelerated primal-dual iterative scheme for the L ² -TV regularized model of linear inverse problems, An alternating direction method of multipliers with a worst-case $O(1/n^2)$ convergence rate, A projected primal-dual method for solving constrained monotone inclusions, Acceleration and Global Convergence of a First-Order Primal-Dual Method for Nonconvex Problems, Proximal alternating penalty algorithms for nonsmooth constrained convex optimization, Bilevel Optimization with Nonsmooth Lower Level Problems, A first-order inexact primal-dual algorithm for a class of convex-concave saddle point problems, Accelerated proximal point method for maximally monotone operators, An efficient multi-grid method for TV minimization problems, Linear convergence rates for variants of the alternating direction method of multipliers in smooth cases, A Coordinate-Descent Primal-Dual Algorithm with Large Step Size and Possibly Nonseparable Functions, Variational contrast enhancement of gray-scale and RGB images, Proximal primal-dual best approximation algorithm with memory, Local and global convergence of a general inertial proximal splitting scheme for minimizing composite functions, Automated parameter selection for total variation minimization in image restoration, Point process estimation with Mirror Prox algorithms, On starting and stopping criteria for nested primal-dual iterations, A prediction-correction-based primal-dual hybrid gradient method for linearly constrained convex minimization, Analysis of fully preconditioned alternating direction method of multipliers with relaxation in Hilbert spaces, A golden ratio primal-dual algorithm for structured convex optimization, New convergence analysis of a primal-dual algorithm with large stepsizes, Acceleration of primal-dual methods by preconditioning and simple subproblem procedures, An optimal randomized incremental gradient method, A parallel primal-dual splitting method for image restoration, A new primal-dual algorithm for minimizing the sum of three functions with a linear operator, Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications, A duality theory for non-convex problems in the calculus of variations, A fully distributed traffic allocation algorithm for nonconcave utility maximization in connectionless communication networks, A primal-dual prediction-correction algorithm for saddle point optimization, On the equivalence of the primal-dual hybrid gradient method and Douglas-Rachford splitting, New convergence results for inertial Krasnoselskii-Mann iterations in Hilbert spaces with applications, Semisupervised data classification via the Mumford-Shah-Potts-type model, Communication-efficient algorithms for decentralized and stochastic optimization, Modular proximal optimization for multidimensional total-variation regularization, Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates, Inertial proximal strictly contractive peaceman-Rachford splitting method with an indefinite term for convex optimization, Easily Parallelizable and Distributable Class of Algorithms for Structured Sparsity, with Optimal Acceleration, Splitting methods for a class of non-potential mean field games, Bregman primal-dual first-order method and application to sparse semidefinite programming, A Primal-Dual Algorithm with Line Search for General Convex-Concave Saddle Point Problems, Block-proximal methods with spatially adapted acceleration, Dualize, split, randomize: toward fast nonsmooth optimization algorithms, Convergence results of two-step inertial proximal point algorithm, Efficient Algorithms for Distributionally Robust Stochastic Optimization with Discrete Scenario Support, The indefinite proximal point algorithms for maximal monotone operators, A proximal-gradient algorithm for crystal surface evolution, A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem, A primal-dual approach for solving conservation laws with implicit in time approximations, On convergence of the Arrow-Hurwicz method for saddle point problems, A nested primal-dual FISTA-like scheme for composite convex optimization problems, Computing Large Market Equilibria Using Abstractions

Cites Work

• Unnamed Item
• Smooth minimization of non-smooth functions
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
• A three-operator splitting scheme and its optimization applications
• An inertial forward-backward algorithm for monotone inclusions
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• Introductory lectures on convex optimization. A basic course.
• A simple algorithm for a class of nonsmooth convex-concave saddle-point problems
• Mirror descent and nonlinear projected subgradient methods for convex optimization.
• A first-order primal-dual algorithm for convex problems with applications to imaging
• A splitting algorithm for dual monotone inclusions involving cocoercive operators
• On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems
• A Class of Randomized Primal-Dual Algorithms for Distributed Optimization
• On the $O(1/n)$ Convergence Rate of the Douglas–Rachford Alternating Direction Method
• Convergence Analysis of Primal-Dual Algorithms for a Saddle-Point Problem: From Contraction Perspective
• A General Framework for a Class of First Order Primal-Dual Algorithms for Convex Optimization in Imaging Science
• Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
• Entropic Proximal Mappings with Applications to Nonlinear Programming
• Monotone Operators and the Proximal Point Algorithm
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming
• Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization
• Optimal Primal-Dual Methods for a Class of Saddle Point Problems
• Weak convergence of the sequence of successive approximations for nonexpansive mappings
• An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping