Distributed block coordinate descent for minimizing partially separable functions
From MaRDI portal
Abstract: In this work we propose a distributed randomized block coordinate descent method for minimizing a convex function with a huge number of variables/coordinates. We analyze its complexity under the assumption that the smooth part of the objective function is partially block separable, and show that the degree of separability directly influences the complexity. This extends the results in [Richtarik, Takac: Parallel coordinate descent methods for big data optimization] to a distributed environment. We first show that partially block separable functions admit an expected separable overapproximation (ESO) with respect to a distributed sampling, compute the ESO parameters, and then specialize complexity results from recent literature that hold under the generic ESO assumption. We describe several approaches to distribution and synchronization of the computation across a cluster of multi-core computers and provide promising computational results.
Recommendations
- Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Parallel coordinate descent methods for big data optimization
- On the complexity analysis of randomized block-coordinate descent methods
- A flexible coordinate descent method
Cites work
- A coordinate gradient descent method for nonsmooth separable minimization
- A MapReduce-based distributed SVM algorithm for automatic image annotation
- A note on the complexity of \(L _{p }\) minimization
- Accelerated, parallel, and proximal coordinate descent
- An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
- Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization
- Convergence of a block coordinate descent method for nondifferentiable minimization
- Distributed coordinate descent method for learning with big data
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Efficient serial and parallel coordinate descent methods for huge-scale truss topology design
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- Inexact coordinate descent: complexity and preconditioning
- Introductory lectures on convex optimization. A basic course.
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- On optimal probabilities in stochastic coordinate descent methods
- On the complexity analysis of randomized block-coordinate descent methods
- On the complexity of parallel coordinate descent
- On the convergence of the coordinate descent method for convex differentiable minimization
- On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods
- Parallel coordinate descent methods for big data optimization
- Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
- Pegasos: primal estimated sub-gradient solver for SVM
- Random Coordinate Descent Methods for <inline-formula> <tex-math notation="TeX">$\ell_{0}$</tex-math></inline-formula> Regularized Convex Optimization
- Separable approximations and decomposition methods for the augmented Lagrangian
- Smooth minimization of nonsmooth functions with parallel coordinate descent methods
- Sparse Approximate Solutions to Linear Systems
- Stochastic dual coordinate ascent methods for regularized loss minimization
Cited in
(13)- On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: randomized block coordinate and optimal averaging schemes
- Matrix completion under interval uncertainty
- High-order evaluation complexity for convexly-constrained optimization with non-Lipschitzian group sparsity terms
- Coordinate descent algorithms
- Random block coordinate descent methods for linearly constrained optimization over networks
- A framework for parallel second order incremental optimization algorithms for solving partially separable problems
- On the convergence analysis of asynchronous SGD for solving consistent linear systems
- Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
- Distributed Basis Pursuit
- Complexity of Partially Separable Convexly Constrained Optimization with Non-Lipschitzian Singularities
- On the complexity of parallel coordinate descent
- Distributed stochastic optimization with large delays
- Multilevel Objective-Function-Free Optimization with an Application to Neural Networks Training
This page was built for publication: Distributed block coordinate descent for minimizing partially separable functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3462314)
