Parallel coordinate descent methods for big data optimization
From MaRDI portal
lassoconvex optimizationbig data optimizationcomposite objectiveexpected separable over-approximationhuge-scale optimizationiteration complexityparallel coordinate descentpartial separability
Numerical mathematical programming methods (65K05) Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Randomized algorithms (68W20) Analysis of algorithms (68W40) Decomposition methods (49M27) Parallel algorithms in computer science (68W10) Numerical methods of relaxation type (49M20)
Abstract: In this work we show that randomized (block) coordinate descent methods can be accelerated by parallelization when applied to the problem of minimizing the sum of a partially separable smooth convex function and a simple separable convex function. The theoretical speedup, as compared to the serial method, and referring to the number of iterations needed to approximately solve the problem with high probability, is a simple expression depending on the number of parallel processors and a natural and easily computable measure of separability of the smooth component of the objective function. In the worst case, when no degree of separability is present, there may be no speedup; in the best case, when the problem is separable, the speedup is equal to the number of processors. Our analysis also works in the mode when the number of blocks being updated at each iteration is random, which allows for modeling situations with busy or unreliable processors. We show that our algorithm is able to solve a LASSO problem involving a matrix with 20 billion nonzeros in 2 hours on a large memory node with 24 cores.
Recommendations
- Parallel and distributed successive convex approximation methods for big-data optimization
- Parallel Selective Algorithms for Nonconvex Big Data Optimization
- Hybrid Random/Deterministic Parallel Algorithms for Convex and Nonconvex Big Data Optimization
- Distributed coordinate descent method for learning with big data
- On the complexity of parallel coordinate descent
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Accelerated, parallel, and proximal coordinate descent
- Parallel algorithms for large-scale nonlinear optimization
- Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
- An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
Cites work
- scientific article; zbMATH DE number 6253925 (Why is no real title available?)
- A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints
- A randomized Kaczmarz algorithm with exponential convergence
- Accelerated Dual Descent for Network Flow Optimization
- Coordinate descent optimization for \(l^{1}\) minimization with application to compressed sensing; a greedy algorithm
- 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
- Gradient methods for minimizing composite functions
- 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
- Iterative Methods by Space Decomposition and Subspace Correction
- On Convergence of an Augmented Lagrangian Decomposition Method for Sparse Convex Optimization
- On optimal probabilities in stochastic coordinate descent methods
- On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods
- Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
- Randomized methods for linear constraints: convergence rates and conditioning
- Smooth minimization of nonsmooth functions with parallel coordinate descent methods
- Subgradient methods for huge-scale optimization problems
Cited in
(95)- An attention algorithm for solving large scale structured \(l_0\)-norm penalty estimation problems
- Block coordinate descent energy minimization for dynamic cohesive fracture
- Distributed primal–dual interior-point methods for solving tree-structured coupled convex problems using message-passing
- A second-order method for strongly convex \(\ell _1\)-regularization problems
- Inexact coordinate descent: complexity and preconditioning
- On optimal probabilities in stochastic coordinate descent methods
- scientific article; zbMATH DE number 6982318 (Why is no real title available?)
- A geometric probability randomized Kaczmarz method for large scale linear systems
- A parallel line search subspace correction method for composite convex optimization
- Primal-dual block-proximal splitting for a class of non-convex problems
- A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints
- Faster randomized block sparse Kaczmarz by averaging
- A class of parallel doubly stochastic algorithms for large-scale learning
- Cost-sensitive feature selection for support vector machines
- An online-learning-based evolutionary many-objective algorithm
- Selective bi-coordinate variations for resource allocation type problems
- Accelerating block coordinate descent methods with identification strategies
- A generic coordinate descent solver for non-smooth convex optimisation
- Randomized methods for computing optimal transport without regularization and their convergence analysis
- ARock: an algorithmic framework for asynchronous parallel coordinate updates
- Parallel stochastic asynchronous coordinate descent: tight bounds on the possible parallelism
- Coordinate-friendly structures, algorithms and applications
- Global optimization using random embeddings
- Exploiting Problem Structure in Derivative Free Optimization
- A fast active set block coordinate descent algorithm for \(\ell_1\)-regularized least squares
- Proximal Gradient Methods for Machine Learning and Imaging
- Analyzing large datasets with bootstrap penalization
- Coordinate descent with arbitrary sampling. I: Algorithms and complexity.
- Functional-bandwidth kernel for support vector machine with functional data: an alternating optimization algorithm
- A coordinate-descent primal-dual algorithm with large step size and possibly nonseparable functions
- Fastest rates for stochastic mirror descent methods
- An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
- Asynchronous stochastic coordinate descent: parallelism and convergence properties
- Matrix completion under interval uncertainty
- Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization
- scientific article; zbMATH DE number 7370629 (Why is no real title available?)
- Stochastic reformulations of linear systems: algorithms and convergence theory
- An efficient parallel block coordinate descent algorithm for large-scale precision matrix estimation using graphics processing units
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- Randomized primal-dual proximal block coordinate updates
- Efficiency of the accelerated coordinate descent method on structured optimization problems
- A flexible coordinate descent method
- Data learning from big data
- Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
- Accelerated, parallel, and proximal coordinate descent
- Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
- Restarting the accelerated coordinate descent method with a rough strong convexity estimate
- Efficient serial and parallel coordinate descent methods for huge-scale truss topology design
- Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis
- Cyclic Coordinate Dual Averaging with Extrapolation
- Block-proximal methods with spatially adapted acceleration
- Testing and non-linear preconditioning of the proximal point method
- Stochastic quasi-gradient methods: variance reduction via Jacobian sketching
- On the complexity analysis of randomized block-coordinate descent methods
- Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications
- Parallel block coordinate minimization with application to group regularized regression
- Parallel and distributed successive convex approximation methods for big-data optimization
- Greedy Kaczmarz algorithm using optimal intermediate projection technique for coherent linear systems
- Smooth minimization of nonsmooth functions with parallel coordinate descent methods
- A Randomized Exchange Algorithm for Computing Optimal Approximate Designs of Experiments
- Block-cyclic stochastic coordinate descent for deep neural networks
- Performance of first- and second-order methods for \(\ell_1\)-regularized least squares problems
- Perturbed iterate analysis for asynchronous stochastic optimization
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- A randomized nonmonotone block proximal gradient method for a class of structured nonlinear programming
- Block coordinate descent algorithms for large-scale sparse multiclass classification
- Distributed coordinate descent method for learning with big data
- Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
- Parallel distributed block coordinate descent methods based on pairwise comparison oracle
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Convergence analysis of inexact randomized iterative methods
- Faster convergence of a randomized coordinate descent method for linearly constrained optimization problems
- Coordinate descent algorithms
- Laplacian-based semi-supervised learning in multilayer hypergraphs by coordinate descent
- Adaptive consensus: a network pruning approach for decentralized optimization
- Solving Fused Penalty Estimation Problems via Block Splitting Algorithms
- Coordinate descent with arbitrary sampling. II: Expected separable overapproximation.
- On the convergence analysis of asynchronous SGD for solving consistent linear systems
- Stochastic primal-dual coordinate method for regularized empirical risk minimization
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- Markov chain block coordinate descent
- Parallel subgradient algorithm with block dual decomposition for large-scale optimization
- Block delayed Majorize-Minimize subspace algorithm for large scale image restoration *
- Lower bounds for parallel and randomized convex optimization
- Distributed optimal consensus of multi-agent systems: a randomized parallel approach
- A Subspace Acceleration Method for Minimization Involving a Group Sparsity-Inducing Regularizer
- Reduced-rank multi-label classification
- A framework for parallel second order incremental optimization algorithms for solving partially separable problems
- Random block coordinate descent methods for linearly constrained optimization over networks
- Synchronous parallel block coordinate descent method for nonsmooth convex function minimization
- Randomness and permutations in coordinate descent methods
- A randomized coordinate descent method with volume sampling
- Distributed block coordinate descent for minimizing partially separable functions
- High-performance statistical computing in the computing environments of the 2020s
- An extragradient-based alternating direction method for convex minimization
This page was built for publication: Parallel coordinate descent methods for big data optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q263212)
