On the complexity of parallel coordinate descent

DOI10.1080/10556788.2017.1392517zbMath1461.65187arXiv1503.03033OpenAlexW2964211658MaRDI QIDQ4638927

Peter Richtárik, Rachael Tappenden, Martin Takáč

Publication date: 2 May 2018

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.03033

zbMATH Keywords

rate of convergenceconvex optimizationparallelizationblock coordinate descentiteration complexitymonotonic algorithmcomposite minimizationunbounded levelset

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Linear programming (90C05)

Related Items (6)

Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis ⋮ A flexible coordinate descent method ⋮ Distributed Block Coordinate Descent for Minimizing Partially Separable Functions ⋮ Zeroth-order optimization with orthogonal random directions ⋮ Fastest rates for stochastic mirror descent methods ⋮ CoordinateWise Descent Methods for Leading Eigenvalue Problem

Uses Software

• Pegasos

Cites Work

• Inexact coordinate descent: complexity and preconditioning
• On optimal probabilities in stochastic coordinate descent methods
• Gradient methods for minimizing composite functions
• On the complexity analysis of randomized block-coordinate descent methods
• Pegasos: primal estimated sub-gradient solver for SVM
• A coordinate gradient descent method for nonsmooth separable minimization
• Coordinate descent optimization for \(l^{1}\) minimization with application to compressed sensing; a greedy algorithm
• Smooth minimization of nonsmooth functions with parallel coordinate descent methods
• Coordinate descent algorithms
• Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
• Coordinate descent algorithms for lasso penalized regression
• Distributed Coordinate Descent Method for Learning with Big Data
• Coordinate descent with arbitrary sampling I: algorithms and complexity^†
• Coordinate descent with arbitrary sampling II: expected separable overapproximation
• Accelerated Block-coordinate Relaxation for Regularized Optimization
• Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
• Accelerated, Parallel, and Proximal Coordinate Descent
• Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
• Parallel Random Coordinate Descent Method for Composite Minimization: Convergence Analysis and Error Bounds
• An extension of the Tau numerical algorithm for the solution of linear and nonlinear Lane–Emden equations
• Efficient Serial and Parallel Coordinate Descent Methods for Huge-Scale Truss Topology Design
• On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods
• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• Convergence of a block coordinate descent method for nondifferentiable minimization

This page was built for publication: On the complexity of parallel coordinate descent