Parallel coordinate descent methods for big data optimization

DOI10.1007/s10107-015-0901-6zbMath1342.90102arXiv1212.0873OpenAlexW2032395696WikidataQ59476352 ScholiaQ59476352MaRDI QIDQ263212

Peter Richtárik, Martin Takáč

Publication date: 4 April 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

convex optimizationlassoiteration complexitybig data optimizationcomposite objectiveexpected separable over-approximationhuge-scale optimizationparallel coordinate descentpartial separability

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Numerical mathematical programming methods (65K05) Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Parallel algorithms in computer science (68W10) Decomposition methods (49M27) Randomized algorithms (68W20) Numerical methods of relaxation type (49M20)

Related Items

Parallel block coordinate minimization with application to group regularized regression ⋮ Block delayed Majorize-Minimize subspace algorithm for large scale image restoration ^* ⋮ An attention algorithm for solving large scale structured \(l_0\)-norm penalty estimation problems ⋮ Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis ⋮ An efficient parallel block coordinate descent algorithm for large-scale precision matrix estimation using graphics processing units ⋮ Accelerated, Parallel, and Proximal Coordinate Descent ⋮ Selective bi-coordinate variations for resource allocation type problems ⋮ Performance of first- and second-order methods for \(\ell_1\)-regularized least squares problems ⋮ An Accelerated Randomized Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization ⋮ Inexact coordinate descent: complexity and preconditioning ⋮ A flexible coordinate descent method ⋮ On optimal probabilities in stochastic coordinate descent methods ⋮ Data learning from big data ⋮ Distributed Block Coordinate Descent for Minimizing Partially Separable Functions ⋮ Exploiting Problem Structure in Derivative Free Optimization ⋮ Parallel Random Coordinate Descent Method for Composite Minimization: Convergence Analysis and Error Bounds ⋮ A Subspace Acceleration Method for Minimization Involving a Group Sparsity-Inducing Regularizer ⋮ Random block coordinate descent methods for linearly constrained optimization over networks ⋮ Parallel distributed block coordinate descent methods based on pairwise comparison oracle ⋮ Perturbed Iterate Analysis for Asynchronous Stochastic Optimization ⋮ Block coordinate descent algorithms for large-scale sparse multiclass classification ⋮ Block-cyclic stochastic coordinate descent for deep neural networks ⋮ Accelerating block coordinate descent methods with identification strategies ⋮ A framework for parallel second order incremental optimization algorithms for solving partially separable problems ⋮ Cyclic Coordinate Dual Averaging with Extrapolation ⋮ Randomness and permutations in coordinate descent methods ⋮ Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties ⋮ Faster randomized block sparse Kaczmarz by averaging ⋮ A Randomized Nonmonotone Block Proximal Gradient Method for a Class of Structured Nonlinear Programming ⋮ Unnamed Item ⋮ On the convergence analysis of asynchronous SGD for solving consistent linear systems ⋮ On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization ⋮ Global optimization using random embeddings ⋮ Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory ⋮ Testing and non-linear preconditioning of the proximal point method ⋮ Synchronous parallel block coordinate descent method for nonsmooth convex function minimization ⋮ Functional-bandwidth kernel for support vector machine with functional data: an alternating optimization algorithm ⋮ Faster convergence of a randomized coordinate descent method for linearly constrained optimization problems ⋮ Analyzing large datasets with bootstrap penalization ⋮ A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints ⋮ Primal-dual block-proximal splitting for a class of non-convex problems ⋮ Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization ⋮ Cost-sensitive feature selection for support vector machines ⋮ A Randomized Coordinate Descent Method with Volume Sampling ⋮ On the complexity analysis of randomized block-coordinate descent methods ⋮ A Randomized Exchange Algorithm for Computing Optimal Approximate Designs of Experiments ⋮ Block coordinate descent energy minimization for dynamic cohesive fracture ⋮ A Coordinate-Descent Primal-Dual Algorithm with Large Step Size and Possibly Nonseparable Functions ⋮ Reduced-rank multi-label classification ⋮ Matrix completion under interval uncertainty ⋮ Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization ⋮ A geometric probability randomized Kaczmarz method for large scale linear systems ⋮ An extragradient-based alternating direction method for convex minimization ⋮ An online-learning-based evolutionary many-objective algorithm ⋮ Unnamed Item ⋮ Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods ⋮ Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications ⋮ A Fast Active Set Block Coordinate Descent Algorithm for $\ell_1$-Regularized Least Squares ⋮ Stochastic quasi-gradient methods: variance reduction via Jacobian sketching ⋮ A parallel line search subspace correction method for composite convex optimization ⋮ Fastest rates for stochastic mirror descent methods ⋮ Markov chain block coordinate descent ⋮ Restarting the accelerated coordinate descent method with a rough strong convexity estimate ⋮ ARock: An Algorithmic Framework for Asynchronous Parallel Coordinate Updates ⋮ Solving Fused Penalty Estimation Problems via Block Splitting Algorithms ⋮ Coordinate descent with arbitrary sampling I: algorithms and complexity^† ⋮ Coordinate descent with arbitrary sampling II: expected separable overapproximation ⋮ Randomized primal-dual proximal block coordinate updates ⋮ Optimization in High Dimensions via Accelerated, Parallel, and Proximal Coordinate Descent ⋮ Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization ⋮ Block-proximal methods with spatially adapted acceleration ⋮ Parallel subgradient algorithm with block dual decomposition for large-scale optimization ⋮ High-performance statistical computing in the computing environments of the 2020s ⋮ Convergence Analysis of Inexact Randomized Iterative Methods ⋮ Greedy Kaczmarz Algorithm Using Optimal Intermediate Projection Technique for Coherent Linear Systems ⋮ A generic coordinate descent solver for non-smooth convex optimisation ⋮ Coordinate descent algorithms ⋮ Distributed primal–dual interior-point methods for solving tree-structured coupled convex problems using message-passing ⋮ Proximal Gradient Methods for Machine Learning and Imaging ⋮ A second-order method for strongly convex \(\ell _1\)-regularization problems

Uses Software

• HOGWILD

Cites Work

• Unnamed Item
• Inexact coordinate descent: complexity and preconditioning
• On optimal probabilities in stochastic coordinate descent methods
• Gradient methods for minimizing composite functions
• Subgradient methods for huge-scale optimization problems
• A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints
• A randomized Kaczmarz algorithm with exponential convergence
• Introductory lectures on convex optimization. A basic course.
• 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
• Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
• Distributed Coordinate Descent Method for Learning with Big Data
• Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
• Accelerated Dual Descent for Network Flow Optimization
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• Parallel Random Coordinate Descent Method for Composite Minimization: Convergence Analysis and Error Bounds
• Iterative Methods by Space Decomposition and Subspace Correction
• On Convergence of an Augmented Lagrangian Decomposition Method for Sparse Convex Optimization
• Efficient Serial and Parallel Coordinate Descent Methods for Huge-Scale Truss Topology Design
• On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods