Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning
From MaRDI portal
Publication:2353007
Abstract: Many problems in machine learning and other fields can be (re)for-mulated as linearly constrained separable convex programs. In most of the cases, there are multiple blocks of variables. However, the traditional alternating direction method (ADM) and its linearized version (LADM, obtained by linearizing the quadratic penalty term) are for the two-block case and cannot be naively generalized to solve the multi-block case. So there is great demand on extending the ADM based methods for the multi-block case. In this paper, we propose LADM with parallel splitting and adaptive penalty (LADMPSAP) to solve multi-block separable convex programs efficiently. When all the component objective functions have bounded subgradients, we obtain convergence results that are stronger than those of ADM and LADM, e.g., allowing the penalty parameter to be unbounded and proving the sufficient and necessary conditions} for global convergence. We further propose a simple optimality measure and reveal the convergence rate of LADMPSAP in an ergodic sense. For programs with extra convex set constraints, with refined parameter estimation we devise a practical version of LADMPSAP for faster convergence. Finally, we generalize LADMPSAP to handle programs with more difficult objective functions by linearizing part of the objective function as well. LADMPSAP is particularly suitable for sparse representation and low-rank recovery problems because its subproblems have closed form solutions and the sparsity and low-rankness of the iterates can be preserved during the iteration. It is also highly parallelizable and hence fits for parallel or distributed computing. Numerical experiments testify to the advantages of LADMPSAP in speed and numerical accuracy.
Recommendations
- Improved proximal ADMM with partially parallel splitting for multi-block separable convex programming
- An ADM-based splitting method for separable convex programming
- A parallel splitting ALM-based algorithm for separable convex programming
- On the linear convergence of the alternating direction method of multipliers
- Parallel multi-block ADMM with \(o(1/k)\) convergence
Cites work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A Singular Value Thresholding Algorithm for Matrix Completion
- A unified primal-dual algorithm framework based on Bregman iteration
- Alternating direction method with Gaussian back substitution for separable convex programming
- An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
- An alternating direction algorithm for matrix completion with nonnegative factors
- Convex Analysis
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Exact matrix completion via convex optimization
- Fast multiple-splitting algorithms for convex optimization
- Fixed point and Bregman iterative methods for matrix rank minimization
- Foundations of large-scale multimedia information management and retrieval. Mathematics of perception.
- scientific article; zbMATH DE number 3833218 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- Latent variable graphical model selection via convex optimization
- Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming
- Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization
- Multi-class discriminant kernel learning via convex programming
- On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
- On the global and linear convergence of the generalized alternating direction method of multipliers
- Robust principal component analysis?
- Some parallel splitting methods for separable convex programming with the \(O(\frac{1}{t})\) convergence rate
- The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
- The Group Lasso for Logistic Regression
- The Split Bregman Method for L1-Regularized Problems
Cited in
(29)- Two proximal splitting methods for multi-block separable programming with applications to stable principal component pursuit
- Improved proximal ADMM with partially parallel splitting for multi-block separable convex programming
- Estimation of the parameters of a weighted nuclear norm model and its application in image denoising
- Dual robust regression for pattern classification
- Tensorized multi-view subspace representation learning
- Tensor Q-rank: new data dependent definition of tensor rank
- ADMM-type methods for generalized multi-facility Weber problem
- A unified framework for nonconvex nonsmooth sparse and low-rank decomposition by majorization-minimization algorithm
- Convergence analysis of positive-indefinite proximal ADMM with a Glowinski's relaxation factor
- Weighted nuclear norm minimization and its applications to low level vision
- Optimally linearizing the alternating direction method of multipliers for convex programming
- Accelerated alternating direction method of multipliers: an optimal \(O(1 / K)\) nonergodic analysis
- The symmetric ADMM with indefinite proximal regularization and its application
- An accelerated proximal augmented Lagrangian method and its application in compressive sensing
- Partial error bound conditions and the linear convergence rate of the alternating direction method of multipliers
- Discerning the linear convergence of ADMM for structured convex optimization through the lens of variational analysis
- The convergence rate of the proximal alternating direction method of multipliers with indefinite proximal regularization
- A new accelerated positive-indefinite proximal ADMM for constrained separable convex optimization problems
- The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates
- ADMM for multiaffine constrained optimization
- An alternate minimization method beyond positive definite proximal regularization: convergence and complexity
- Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction
- Convergence analysis of an improved Bregman-type Peaceman-Rachford splitting algorithm for nonconvex nonseparable linearly constrained optimization problems
- An extended linearized alternating direction method of multipliers for fused-Lasso penalized linear regression
- Tensor nonconvex unified prior for tensor recovery
- Convergence of Peaceman-Rachford splitting method with Bregman distance for three-block nonconvex nonseparable optimization
- A tensor completion method based on tensor QR decomposition with truncated nuclear norm and sparse regularization
- A new linearized alternating direction method of multipliers with adaptive step size and its inexact version for fused Lasso regression model
- Linearized symmetric multi-block ADMM with indefinite proximal regularization and optimal proximal parameter
This page was built for publication: Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2353007)
