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
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- A MapReduce-based distributed SVM algorithm for automatic image annotation
- A coordinate gradient descent method for nonsmooth separable minimization
- 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
- 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 Nonasymptotic Convergence of Cyclic 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
- 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)- Distributed Basis Pursuit
- Matrix completion under interval uncertainty
- High-order evaluation complexity for convexly-constrained optimization with non-Lipschitzian group sparsity terms
- Multilevel Objective-Function-Free Optimization with an Application to Neural Networks Training
- Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
- Coordinate descent algorithms
- Distributed stochastic optimization with large delays
- On the convergence analysis of asynchronous SGD for solving consistent linear systems
- Complexity of Partially Separable Convexly Constrained Optimization with Non-Lipschitzian Singularities
- A framework for parallel second order incremental optimization algorithms for solving partially separable problems
- On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: randomized block coordinate and optimal averaging schemes
- Random block coordinate descent methods for linearly constrained optimization over networks
- On the complexity of parallel coordinate descent
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)
