Parallel coordinate descent methods for big data optimization
From MaRDI portal
big data optimizationcomposite objectiveconvex optimizationexpected separable over-approximationhuge-scale optimizationiteration complexitylassoparallel coordinate descentpartial separability
Numerical methods of relaxation type (49M20) Decomposition methods (49M27) Numerical mathematical programming methods (65K05) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20) Analysis of algorithms (68W40) Large-scale problems in mathematical programming (90C06) Convex programming (90C25)
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
- 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
- scientific article; zbMATH DE number 6253925 (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
- 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
(only showing first 100 items - show all)- A flexible coordinate descent method
- Data learning from big data
- Parallel distributed block coordinate descent methods based on pairwise comparison oracle
- Coordinate-friendly structures, algorithms and applications
- Functional-bandwidth kernel for support vector machine with functional data: an alternating optimization algorithm
- Cost-sensitive feature selection for support vector machines
- Matrix completion under interval uncertainty
- Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization
- Block coordinate descent energy minimization for dynamic cohesive fracture
- A geometric probability randomized Kaczmarz method for large scale linear systems
- An online-learning-based evolutionary many-objective algorithm
- Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
- Stochastic quasi-gradient methods: variance reduction via Jacobian sketching
- Fastest rates for stochastic mirror descent methods
- Parallel subgradient algorithm with block dual decomposition for large-scale optimization
- High-performance statistical computing in the computing environments of the 2020s
- 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
- Randomness and permutations in coordinate descent methods
- Testing and non-linear preconditioning of the proximal point method
- Synchronous parallel block coordinate descent method for nonsmooth convex function minimization
- Primal-dual block-proximal splitting for a class of non-convex problems
- Markov chain block coordinate descent
- Restarting the accelerated coordinate descent method with a rough strong convexity estimate
- Parallel and distributed successive convex approximation methods for big-data optimization
- Randomized primal-dual proximal block coordinate updates
- Block-proximal methods with spatially adapted acceleration
- Smooth minimization of nonsmooth functions with parallel coordinate descent methods
- Coordinate descent algorithms
- Parallel block coordinate minimization with application to group regularized regression
- Performance of first- and second-order methods for _1-regularized least squares problems
- Random block coordinate descent methods for linearly constrained optimization over networks
- Accelerating block coordinate descent methods with identification strategies
- A framework for parallel second order incremental optimization algorithms for solving partially separable problems
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- A parallel line search subspace correction method for composite convex optimization
- A second-order method for strongly convex \(\ell _1\)-regularization problems
- On the convergence analysis of asynchronous SGD for solving consistent linear systems
- A fast active set block coordinate descent algorithm for _1-regularized least squares
- Distributed coordinate descent method for learning with big data
- ARock: an algorithmic framework for asynchronous parallel coordinate updates
- Coordinate descent with arbitrary sampling. I: Algorithms and complexity.
- Coordinate descent with arbitrary sampling. II: Expected separable overapproximation.
- Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Asynchronous stochastic coordinate descent: parallelism and convergence properties
- Efficiency of the accelerated coordinate descent method on structured optimization problems
- Analyzing large datasets with bootstrap penalization
- Selective bi-coordinate variations for resource allocation type problems
- Inexact coordinate descent: complexity and preconditioning
- On optimal probabilities in stochastic coordinate descent methods
- A randomized coordinate descent method with volume sampling
- A Randomized Exchange Algorithm for Computing Optimal Approximate Designs of Experiments
- Solving Fused Penalty Estimation Problems via Block Splitting Algorithms
- Accelerated, parallel, and proximal coordinate descent
- An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
- Distributed block coordinate descent for minimizing partially separable functions
- Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
- Block coordinate descent algorithms for large-scale sparse multiclass classification
- scientific article; zbMATH DE number 6982318 (Why is no real title available?)
- Perturbed iterate analysis for asynchronous stochastic optimization
- A randomized nonmonotone block proximal gradient method for a class of structured nonlinear programming
- A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints
- Stochastic primal-dual coordinate method for regularized empirical risk minimization
- A coordinate-descent primal-dual algorithm with large step size and possibly nonseparable functions
- Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications
- Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
- On the complexity analysis of randomized block-coordinate descent methods
- Lower bounds for parallel and randomized convex optimization
- A class of parallel doubly stochastic algorithms for large-scale learning
- L-SVRG and L-Katyusha with arbitrary sampling
- Proximal Gradient Methods for Machine Learning and Imaging
- Exploiting Problem Structure in Derivative Free Optimization
- A Subspace Acceleration Method for Minimization Involving a Group Sparsity-Inducing Regularizer
- Stochastic reformulations of linear systems: algorithms and convergence theory
- Parallel stochastic asynchronous coordinate descent: tight bounds on the possible parallelism
- Reduced-rank multi-label classification
- Efficient serial and parallel coordinate descent methods for huge-scale truss topology design
- An extragradient-based alternating direction method for convex minimization
- Distributed primal–dual interior-point methods for solving tree-structured coupled convex problems using message-passing
- Faster convergence of a randomized coordinate descent method for linearly constrained optimization problems
- 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
- Block delayed Majorize-Minimize subspace algorithm for large scale image restoration *
- Block-cyclic stochastic coordinate descent for deep neural networks
- Cyclic Coordinate Dual Averaging with Extrapolation
- Faster randomized block sparse Kaczmarz by averaging
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- Global optimization using random embeddings
- Laplacian-based semi-supervised learning in multilayer hypergraphs by coordinate descent
- Distributed optimal consensus of multi-agent systems: a randomized parallel approach
- Randomized methods for computing optimal transport without regularization and their convergence analysis
- Adaptive consensus: a network pruning approach for decentralized optimization
- A stochastic preconditioned Douglas-Rachford splitting method for saddle-point problems
- Federated learning with randomized alternating direction method of multipliers and application in training neural networks
- Sampling and update frequencies in proximal variance-reduced stochastic gradient methods
- Zero order algorithm for decentralized optimization problems
- Randomized iterative methods for tensor regression under the t-product
- Parallel block coordinate descent methods with identification strategies
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)
