On the convergence of stochastic primal-dual hybrid gradient
From MaRDI portal
Publication:5081780
Abstract: In this paper, we analyze the recently proposed stochastic primal-dual hybrid gradient (SPDHG) algorithm and provide new theoretical results. In particular, we prove almost sure convergence of the iterates to a solution with convexity and linear convergence with further structure, using standard step sizes independent of strong convexity or other regularity constants. In the general convex case, we also prove the convergence rate for the ergodic sequence, on expected primal-dual gap function. Our assumption for linear convergence is metric subregularity, which is satisfied for strongly convex-strongly concave problems in addition to many nonsmooth and/or nonstrongly convex problems, such as linear programs, Lasso, and support vector machines. We also provide numerical evidence showing that SPDHG with standard step sizes shows a competitive practical performance against its specialized strongly convex variant SPDHG- and other state-of-the-art algorithms including variance reduction methods.
Recommendations
- Convergence properties of a randomized primal-dual algorithm with applications to parallel MRI
- On stochastic primal-dual hybrid gradient approach for compositely regularized minimization
- On the convergence of primal-dual hybrid gradient algorithm
- On the ergodic convergence rates of a first-order primal-dual algorithm
- Convergence of stochastic proximal gradient algorithm
Cites work
- A class of randomized primal-dual algorithms for distributed optimization
- A coordinate-descent primal-dual algorithm with large step size and possibly nonseparable functions
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science
- A New Randomized Block-Coordinate Primal-Dual Proximal Algorithm for Distributed Optimization
- A proximal stochastic gradient method with progressive variance reduction
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- A Stochastic Approximation Method
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- Accelerated, parallel, and proximal coordinate descent
- An adaptive primal-dual framework for nonsmooth convex minimization
- An optimal randomized incremental gradient method
- Atomic decomposition by basis pursuit
- Block-coordinate primal-dual method for nonsmooth minimization over linear constraints
- Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective
- Convergence rates with inexact non-expansive operators
- Convex analysis and monotone operator theory in Hilbert spaces
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Error bounds, quadratic growth, and linear convergence of proximal methods
- scientific article; zbMATH DE number 3449561 (Why is no real title available?)
- Implicit Functions and Solution Mappings
- Incremental proximal methods for large scale convex optimization
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Linear convergence of the alternating direction method of multipliers for a class of convex optimization problems
- Nonasymptotic convergence of stochastic proximal point methods for constrained convex optimization
- On the ergodic convergence rates of a first-order primal-dual algorithm
- Partial error bound conditions and the linear convergence rate of the alternating direction method of multipliers
- PhaseMax: Convex Phase Retrieval via Basis Pursuit
- Primal-dual proximal algorithms for structured convex optimization: a unifying framework
- Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
- Random gradient extrapolation for distributed and stochastic optimization
- Randomized projection methods for convex feasibility: conditioning and convergence rates
- Robust Stochastic Approximation Approach to Stochastic Programming
- Stochastic dual coordinate ascent methods for regularized loss minimization
- Stochastic primal-dual coordinate method for regularized empirical risk minimization
- Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications
- Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping
- Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping. II: Mean-square and linear convergence
Cited in
(27)- New convergence analysis of a primal-dual algorithm with large stepsizes
- A unified convergence analysis of stochastic Bregman proximal gradient and extragradient methods
- A unified convergence rate analysis of the accelerated smoothed gap reduction algorithm
- A stochastic primal-dual method for a class of nonconvex constrained optimization
- On stochastic primal-dual hybrid gradient approach for compositely regularized minimization
- Simple and optimal methods for stochastic variational inequalities. I: Operator extrapolation
- Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
- On the convergence of primal-dual hybrid gradient algorithm
- A new randomized primal-dual algorithm for convex optimization with fast last iterate convergence rates
- Cyclic Coordinate Dual Averaging with Extrapolation
- A note on the linear convergence of generalized primal-dual hybrid gradient methods
- A stochastic Bregman primal-dual splitting algorithm for composite optimization
- Two convergent primal-dual hybrid gradient type methods for convex programming with linear constraints
- Faster first-order primal-dual methods for linear programming using restarts and sharpness
- Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradient
- On the Convergence of Stochastic Gradient Descent for Linear Inverse Problems in Banach Spaces
- An accelerated stochastic extragradient-like algorithm with new stepsize rules for stochastic variational inequalities
- Fast iterative regularization by reusing data
- Stochastic primal-dual hybrid gradient algorithm with adaptive step sizes
- The smoothed duality gap as a stopping criterion
- Almost-surely convergent randomly activated monotone operator splitting methods
- A stochastic preconditioned Douglas-Rachford splitting method for saddle-point problems
- On the geometry and refined rate of primal-dual hybrid gradient for linear programming
- A guide to stochastic optimisation for large-scale inverse problems
- Randomized primal-dual algorithm with arbitrary sampling: convergence theory and applications to parallel MRI
- Hypergraph p-Laplacian regularization on point clouds for data interpolation
- A fully stochastic primal-dual algorithm
This page was built for publication: On the convergence of stochastic primal-dual hybrid gradient
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5081780)
