Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
From MaRDI portal
Publication:3465244
Abstract: In this paper we propose a distributed version of a randomized block-coordinate descent method for minimizing the sum of a partially separable smooth convex function and a fully separable non-smooth convex function. Under the assumption of block Lipschitz continuity of the gradient of the smooth function, this method is shown to have a sublinear convergence rate. Linear convergence rate of the method is obtained for the newly introduced class of generalized error bound functions. We prove that the new class of generalized error bound functions encompasses both global/local error bound functions and smooth strongly convex functions. We also show that the theoretical estimates on the convergence rate depend on the number of blocks chosen randomly and a natural measure of separability of the objective function.
Recommendations
- Accelerated, parallel, and proximal coordinate descent
- Smooth minimization of nonsmooth functions with parallel coordinate descent methods
- Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis
- On the complexity analysis of randomized block-coordinate descent methods
- Asynchronous stochastic coordinate descent: parallelism and convergence properties
Cites work
- A coordinate gradient descent method for nonsmooth separable minimization
- A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints
- Bounds for error in the solution set of a perturbed linear program
- Distributed coordinate descent method for learning with big data
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Error bounds and convergence analysis of feasible descent methods: A general approach
- Gradient methods for minimizing composite functions
- scientific article; zbMATH DE number 6378119 (Why is no real title available?)
- Incremental stochastic subgradient algorithms for convex optimization
- Interior-point Lagrangian decomposition method for separable convex optimization
- Introductory lectures on convex optimization. A basic course.
- Iteration complexity analysis of block coordinate descent methods
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Non-Lipschitz $\ell_{p}$-Regularization and Box Constrained Model for Image Restoration
- On the complexity analysis of randomized block-coordinate descent methods
- On the convergence of block coordinate descent type methods
- Parallel coordinate descent methods for big data optimization
- Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
- Pattern recognition and machine learning.
- Random block coordinate descent methods for linearly constrained optimization over networks
- Random Coordinate Descent Algorithms for Multi-Agent Convex Optimization Over Networks
- Randomized methods for linear constraints: convergence rates and conditioning
- Rate Analysis of Inexact Dual First-Order Methods Application to Dual Decomposition
- Variational Analysis
Cited in
(38)- Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems
- Linear convergence of prox-SVRG method for separable non-smooth convex optimization problems under bounded metric subregularity
- Convergence results of a new monotone inertial forward-backward splitting algorithm under the local Hölder error bound condition
- Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis
- Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems
- Synchronous parallel block coordinate descent method for nonsmooth convex function minimization
- Smooth minimization of nonsmooth functions with parallel coordinate descent methods
- Coordinate descent algorithms
- Parallel block coordinate minimization with application to group regularized regression
- Random block coordinate descent methods for linearly constrained optimization over networks
- Linear convergence of first order methods for non-strongly convex optimization
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Parallel coordinate descent methods for big data optimization
- Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
- A randomized coordinate descent method with volume sampling
- Accelerated, parallel, and proximal coordinate descent
- An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
- Distributed block coordinate descent for minimizing partially separable functions
- Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
- RSG: Beating Subgradient Method without Smoothness and Strong Convexity
- On the complexity of parallel coordinate descent
- Global convergence rate of proximal incremental aggregated gradient methods
- On the linear convergence of the approximate proximal splitting method for non-smooth convex optimization
- On the complexity analysis of randomized block-coordinate descent methods
- Proximal Gradient Methods for Machine Learning and Imaging
- scientific article; zbMATH DE number 7108069 (Why is no real title available?)
- Faster randomized block Kaczmarz algorithms
- Faster convergence of a randomized coordinate descent method for linearly constrained optimization problems
- Linear Convergence of Random Dual Coordinate Descent on Nonpolyhedral Convex Problems
- Randomized Block Adaptive Linear System Solvers
- Convergence of an asynchronous block-coordinate forward-backward algorithm for convex composite optimization
- Random Coordinate Descent Methods for Nonseparable Composite Optimization
- Randomized methods for computing optimal transport without regularization and their convergence analysis
- Acceleration and restart for the randomized Bregman-Kaczmarz method
- Convergence in distribution of randomized algorithms: the case of partially separable optimization
- Parallel block coordinate descent methods with identification strategies
- Randomized subspace correction methods for convex optimization
- Convergence properties of a randomized primal-dual algorithm with applications to parallel MRI
This page was built for publication: Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3465244)
