Parallel multi-block ADMM with o(1/k) convergence
From MaRDI portal
Publication:1704845
DOI10.1007/S10915-016-0318-2zbMATH Open1398.65121arXiv1312.3040OpenAlexW2277973662MaRDI QIDQ1704845FDOQ1704845
Authors: Wei Deng, Ming-Jun Lai, Zhimin Peng, Wotao Yin 
Publication date: 13 March 2018
Published in: Journal of Scientific Computing (Search for Journal in Brave)
Abstract: This paper introduces a parallel and distributed extension to the alternating direction method of multipliers (ADMM) for solving convex problem: minimize subject to . The algorithm decomposes the original problem into N smaller subproblems and solves them in parallel at each iteration. This Jacobian-type algorithm is well suited for distributed computing and is particularly attractive for solving certain large-scale problems. This paper introduces a few novel results. Firstly, it shows that extending ADMM straightforwardly from the classic Gauss-Seidel setting to the Jacobian setting, from 2 blocks to N blocks, will preserve convergence if matrices are mutually near-orthogonal and have full column-rank. Secondly, for general matrices , this paper proposes to add proximal terms of different kinds to the N subproblems so that the subproblems can be solved in flexible and efficient ways and the algorithm converges globally at a rate of o(1/k). Thirdly, a simple technique is introduced to improve some existing convergence rates from O(1/k) to o(1/k). In practice, some conditions in our convergence theorems are conservative. Therefore, we introduce a strategy for dynamically tuning the parameters in the algorithm, leading to substantial acceleration of the convergence in practice. Numerical results are presented to demonstrate the efficiency of the proposed method in comparison with several existing parallel algorithms. We implemented our algorithm on Amazon EC2, an on-demand public computing cloud, and report its performance on very large-scale basis pursuit problems with distributed data.
Full work available at URL: https://arxiv.org/abs/1312.3040
Recommendations
- A multi-parameter parallel ADMM for multi-block linearly constrained separable convex optimization
- A flexible ADMM algorithm for big data applications
- On the linear convergence of the alternating direction method of multipliers
- Parallel alternating direction method of multipliers
- An algorithm twisted from generalized ADMM for multi-block separable convex minimization models
Cites Work
- D-ADMM: A Communication-Efficient Distributed Algorithm for Separable Optimization
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Smooth minimization of non-smooth functions
- On the global and linear convergence of the generalized alternating direction method of multipliers
- On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
- Latent variable graphical model selection via convex optimization
- Title not available (Why is that?)
- The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
- Fast alternating direction optimization methods
- A proximal-based deomposition method for compositions method for convex minimization problems
- Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
- Title not available (Why is that?)
- Title not available (Why is that?)
- A unified primal-dual algorithm framework based on Bregman iteration
- Title not available (Why is that?)
- A class of projection and contraction methods for monotone variational inequalities
- Alternating direction method with Gaussian back substitution for separable convex programming
- Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
- Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities
- A note on the alternating direction method of multipliers
- On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming
- Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources
- On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers
- Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
- On the convergence analysis of the alternating direction method of multipliers with three blocks
- A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block
- Title not available (Why is that?)
- On the sublinear convergence rate of multi-block ADMM
- The multivariate spline mehtod for scattered data fitting and numerical solution of partial differential equations
- A generalized proximal point algorithm and its convergence rate
Cited In (93)
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Regularized Jacobi-type ADMM-methods for a class of separable convex optimization problems in Hilbert spaces
- A proximal fully parallel splitting method for stable principal component pursuit
- A parallel line search subspace correction method for composite convex optimization
- Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs
- Convergence of the augmented decomposition algorithm
- Hybrid MPI/OpenMP parallel asynchronous distributed alternating direction method of multipliers
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
- PET-MRI joint reconstruction with common edge weighted total variation regularization
- A Three-Operator Splitting Perspective of a Three-Block ADMM for Convex Quadratic Semidefinite Programming and Beyond
- On non-ergodic convergence rate of the operator splitting method for a class of variational inequalities
- Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights
- Linearized block-wise alternating direction method of multipliers for multiple-block convex programming
- A generalized alternating direction method of multipliers with semi-proximal terms for convex composite conic programming
- Convergent prediction-correction-based ADMM for multi-block separable convex programming
- Two proximal splitting methods for multi-block separable programming with applications to stable principal component pursuit
- A proximal strictly contractive Peaceman-Rachford splitting method for convex programming with applications to imaging
- Improved proximal ADMM with partially parallel splitting for multi-block separable convex programming
- Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning
- Solving nearly-separable quadratic optimization problems as nonsmooth equations
- Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization
- On the efficiency of random permutation for ADMM and coordinate descent
- Proximal ADMM for nonconvex and nonsmooth optimization
- First-order algorithms for convex optimization with nonseparable objective and coupled constraints
- Global convergence of ADMM in nonconvex nonsmooth optimization
- Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization
- Alternating direction method of multipliers with difference of convex functions
- Randomized primal-dual proximal block coordinate updates
- On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions
- An inexact accelerated stochastic ADMM for separable convex optimization
- Convergence study on strictly contractive peaceman-Rachford splitting method for nonseparable convex minimization models with quadratic coupling terms
- Selective linearization for multi-block statistical learning
- Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal
- Block splitting for distributed optimization
- On iteration complexity of a first-order primal-dual method for nonlinear convex cone programming
- Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity
- A proximal Peaceman-Rachford splitting method for solving the multi-block separable convex minimization problems
- On the Global Linear Convergence of the ADMM with MultiBlock Variables
- Faster convergence of a randomized coordinate descent method for linearly constrained optimization problems
- ADMM for multiaffine constrained optimization
- Alternating direction method for separable variables under pair-wise constraints
- A minimization approach for constructing generalized barycentric coordinates and its computation
- On the sublinear convergence rate of multi-block ADMM
- An indefinite proximal Peaceman-Rachford splitting method with substitution procedure for convex programming
- Global convergence of unmodified 3-block ADMM for a class of convex minimization problems
- Parallel alternating direction method of multipliers
- A fundamental proof of convergence of alternating direction method of multipliers for weakly convex optimization
- Distributed adaptive dynamic programming for data-driven optimal control
- Further study on the convergence rate of alternating direction method of multipliers with logarithmic-quadratic proximal regularization
- Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property
- ADMM-type methods for generalized Nash equilibrium problems in Hilbert spaces
- An extended proximal ADMM algorithm for three-block nonconvex optimization problems
- On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers
- Mirror Prox algorithm for multi-term composite minimization and semi-separable problems
- A flexible ADMM algorithm for big data applications
- On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function
- A survey on some recent developments of alternating direction method of multipliers
- A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization
- A multi-parameter parallel ADMM for multi-block linearly constrained separable convex optimization
- Parameter selection and preconditioning for a graph form solver
- A unified primal-dual algorithm framework for inequality constrained problems
- A modified strictly contractive peaceman-Rachford splitting method for multi-block separable convex programming
- A parallel Gauss-Seidel method for convex problems with separable structure
- A distributed ADMM-like method for resource sharing over time-varying networks
- On relaxation of some customized proximal point algorithms for convex minimization: from variational inequality perspective
- On the convergence rate of inexact majorized sGS ADMM with indefinite proximal terms for convex composite programming
- An efficient partial parallel method with scaling step size strategy for three-block convex optimization problems
- Distributed quantile regression for longitudinal big data
- A revisit of Chen-Teboulle's proximal-based decomposition method
- J‐ADMM for a multi‐contact problem in electro‐elastostatics
- A Barzilai and Borwein regularization feasible direction algorithm for convex nonlinear SOC programming with linear constraints
- GADMM: fast and communication efficient framework for distributed machine learning
- Inertial proximal ADMM for separable multi-block convex optimizations and compressive affine phase retrieval
- Consensus-based Dantzig-Wolfe decomposition
- Some extensions of the operator splitting schemes based on Lagrangian and primal–dual: a unified proximal point analysis
- Majorized iPADMM for Nonseparable Convex Minimization Models with Quadratic Coupling Terms
- Title not available (Why is that?)
- Massively parallelizable proximal algorithms for large‐scale stochastic optimal control problems
- A rank-two relaxed parallel splitting version of the augmented Lagrangian method with step size in (0,2) for separable convex programming
- The augmented Lagrangian method with full Jacobian decomposition and logarithmic-quadratic proximal regularization for multiple-block separable convex programming
- Moreau envelope augmented Lagrangian method for nonconvex optimization with linear constraints
- A privacy-preserving method to optimize distributed resource allocation
- A generalized alternating direction implicit method for consensus optimization: application to distributed sparse logistic regression
- Synchronous distributed ADMM for consensus convex optimization problems with self-loops
- A proximal fully parallel splitting method with a relaxation factor for separable convex programming
- Fast non-overlapping domain decomposition methods for continuous multi-phase labeling problem
- Distributed Nash equilibrium learning: A second‐order proximal algorithm
- An ADMM algorithm for two-stage stochastic programming problems
- A proximal-based algorithm for piecewise sparse approximation with application to scattered data fitting
- Distributed optimal consensus of multi-agent systems: a randomized parallel approach
- A dual-primal balanced augmented Lagrangian method for linearly constrained convex programming
- Two symmetrized coordinate descent methods can be \(O(n^2)\) times slower than the randomized version
Uses Software
This page was built for publication: Parallel multi-block ADMM with \(o(1/k)\) convergence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704845)
