An inexact accelerated stochastic ADMM for separable convex optimization
From MaRDI portal
Publication:2114819
DOI10.1007/S10589-021-00338-8zbMATH Open1487.90521arXiv2010.12765OpenAlexW3094257649MaRDI QIDQ2114819FDOQ2114819
Jianchao Bai, Hongchao Zhang, William Hager
Publication date: 15 March 2022
Published in: Computational Optimization and Applications (Search for Journal in Brave)
Abstract: An inexact accelerated stochastic Alternating Direction Method of Multipliers (AS-ADMM) scheme is developed for solving structured separable convex optimization problems with linear constraints. The objective function is the sum of a possibly nonsmooth convex function and a smooth function which is an average of many component convex functions. Problems having this structure often arise in machine learning and data mining applications. AS-ADMM combines the ideas of both ADMM and the stochastic gradient methods using variance reduction techniques. One of the ADMM subproblems employs a linearization technique while a similar linearization could be introduced for the other subproblem. For a specified choice of the algorithm parameters, it is shown that the objective error and the constraint violation are relative to the number of outer iterations . Under a strong convexity assumption, the expected iterate error converges to zero linearly. A linearized variant of AS-ADMM and incremental sampling strategies are also discussed. Numerical experiments with both stochastic and deterministic ADMM algorithms show that AS-ADMM can be particularly effective for structured optimization arising in big data applications.
Full work available at URL: https://arxiv.org/abs/2010.12765
Recommendations
- Inexact alternating direction methods of multipliers for separable convex optimization
- A flexible ADMM algorithm for big data applications
- A stochastic alternating direction method of multipliers for non-smooth and non-convex optimization
- Convergence rates for an inexact ADMM applied to separable convex optimization
- An inexact proximal generalized alternating direction method of multipliers
convex optimizationbig datacomplexityseparable structureaccelerated gradient methodaccelerated stochastic ADMMas-ADMMinexact stochastic ADMM
Cites Work
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
- Title not available (Why is that?)
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- Sparse inverse covariance estimation with the graphical lasso
- 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
- Title not available (Why is that?)
- Inexact alternating-direction-based contraction methods for separable linearly constrained convex optimization
- Local Linear Convergence of the Alternating Direction Method of Multipliers on Quadratic or Linear Programs
- Approximation accuracy, gradient methods, and error bound for structured convex optimization
- Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
- Inexact Alternating Direction Methods for Image Recovery
- Parallel multi-block ADMM with \(o(1/k)\) convergence
- Bregman operator splitting with variable stepsize for total variation image reconstruction
- On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function
- On the linear convergence of the alternating direction method of multipliers
- A class of linearized proximal alternating direction methods
- A class of ADMM-based algorithms for three-block separable convex programming
- On the Global Linear Convergence of the ADMM with MultiBlock Variables
- Inexact alternating direction methods of multipliers for separable convex optimization
- Linear convergence of the alternating direction method of multipliers for a class of convex optimization problems
- An Accelerated Linearized Alternating Direction Method of Multipliers
- Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications
- Convergence analysis of positive-indefinite proximal ADMM with a Glowinski's relaxation factor
- Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming
- Convergence study of indefinite proximal ADMM with a relaxation factor
- Proximal ADMM with larger step size for two-block separable convex programming and its application to the correlation matrices calibrating problems
- Generalized symmetric ADMM for separable convex optimization
- Convergence rates for an inexact ADMM applied to separable convex optimization
- SI-ADMM: A Stochastic Inexact ADMM Framework for Stochastic Convex Programs
Cited In (29)
- Regularized least absolute deviation-based sparse identification of dynamical systems
- A three-term conjugate gradient method with a random parameter for large-scale unconstrained optimization and its application in regression model
- An inexact ADMM with proximal-indefinite term and larger stepsize
- A mini-batch proximal stochastic recursive gradient algorithm with diagonal Barzilai-Borwein stepsize
- Accelerated stochastic Peaceman-Rachford method for empirical risk minimization
- A partially inexact ADMM with o(1/n) asymptotic convergence rate, 𝒪(1/n) complexity, and immediate relative error tolerance
- An efficient regularized PR splitting type algorithm for two-block nonconvex linear constrained programs in \(\ell_{1 / 2}\) regularized compressed sensing problems
- Stochastic accelerated alternating direction method of multipliers with importance sampling
- Multi-step inertial strictly contractive PRSM algorithms for convex programming problems with applications
- Accelerating stochastic sequential quadratic programming for equality constrained optimization using predictive variance reduction
- An inertial proximal splitting method with applications
- A stochastic Nesterov's smoothing accelerated method for general nonsmooth constrained stochastic composite convex optimization
- An optimization method to solve a fully intuitionistic fuzzy non-linear separable programming problem
- Modified proximal symmetric ADMMs for multi-block separable convex optimization with linear constraints
- Inexact generalized ADMM with relative error criteria for linearly constrained convex optimization problems
- A proximal fully parallel splitting method with a relaxation factor for separable convex programming
- Nonconvex optimization with inertial proximal stochastic variance reduction gradient
- SI-ADMM: A Stochastic Inexact ADMM Framework for Stochastic Convex Programs
- A New Insight on Augmented Lagrangian Method with Applications in Machine Learning
- ADMM for Exploiting Structure in MPC Problems
- Convergence analysis of an ALF-based nonconvex splitting algorithm with SQP structure
- A class of accelerated GADMM-based method for multi-block nonconvex optimization problems
- Inertial accelerated augmented Lagrangian algorithms with scaling coefficients to solve exactly and inexactly linearly constrained convex optimization problems
- Generalized proximal point algorithms with correction terms and extrapolation
- Convergence results of two-step inertial proximal point algorithm
- An inertial proximal partially symmetric ADMM-based algorithm for linearly constrained multi-block nonconvex optimization problems with applications
- Accelerated Stochastic Algorithms for Nonconvex Finite-Sum and Multiblock Optimization
- A new randomized primal-dual algorithm for convex optimization with fast last iterate convergence rates
- Inexact alternating direction methods of multipliers for separable convex optimization
Uses Software
This page was built for publication: An inexact accelerated stochastic ADMM for separable convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2114819)
