Adaptive Primal-Dual Hybrid Gradient Methods for Saddle-Point Problems

Abstract

The Primal-Dual hybrid gradient (PDHG) method is a powerful optimization scheme that breaks complex problems into simple sub-steps. Unfortunately, PDHG methods require the user to choose stepsize parameters, and the speed of convergence is highly sensitive to this choice. We introduce new adaptive PDHG schemes that automatically tune the stepsize parameters for fast convergence without user inputs. We prove rigorous convergence results for our methods, and identify the conditions required for convergence. We also develop practical implementations of adaptive schemes that formally satisfy the convergence requirements. Numerical experiments show that adaptive PDHG methods have advantages over non-adaptive implementations in terms of both efficiency and simplicity for the user.

24 pages, 5 figures

Cited by in corpus (29)

• A Field Guide to Forward-Backward Splitting with a FASTA Implementation
• A first-order primal-dual algorithm with linesearch
• Imaging with Kantorovich-Rubinstein discrepancy
• Collaborative Total Variation: A General Framework for Vectorial TV Models
• A Universal Primal-Dual Convex Optimization Framework
• Democratic Representations
• Brain Extraction from Normal and Pathological Images: A Joint PCA/Image-Reconstruction Approach
• Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient
• Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms
• Playing with Duality: An Overview of Recent Primal-Dual Approaches for Solving Large-Scale Optimization Problems
• Total-variation regularization strategies in full-waveform inversion
• A Flexible Primal-Dual Toolbox
• Convergence rate analysis of primal-dual splitting schemes
• Joint Large-Scale Motion Estimation and Image Reconstruction
• Non-Stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
• Generalized Inpainting Method for Hyperspectral Image Acquisition
• Nonlinear Evolutionary PDE-Based Refinement of Optical Flow
• Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization
• Dual Smoothing and Level Set Techniques for Variational Matrix Decomposition
• Augmented Lagrangian-Based Decomposition Methods with Non-Ergodic Optimal Rates
• A Generalized Primal-Dual Correction Method for Saddle-Point Problems with a Nonlinear Coupling Operator
• On the Convergence of Primal-Dual Proximal Incremental Aggregated Gradient Algorithms
• Regularization with Sparse Vector Fields: From Image Compression to TV-type Reconstruction
• A New Randomized Primal-Dual Algorithm for Convex Optimization with Optimal Last Iterate Rates
• Efficient Registration of Pathological Images: A Joint PCA/Image-Reconstruction Approach
• Non-convex primal-dual algorithm for image reconstruction in spectral CT
• Directional-TV Algorithm for Image Reconstruction from Limited-Angular-Range Data
• Do CNNs solve the CT inverse problem?
• Misfit function for full waveform inversion based on Earth Mover's Distance with dynamic formulation