ARock: An Algorithmic Framework for Asynchronous Parallel Coordinate Updates

DOI10.1137/15M1024950zbMath1350.49041arXiv1506.02396MaRDI QIDQ2821779

Zhimin Peng, Ming Yan, Wotao Yin, Yang-yang Xu

Publication date: 23 September 2016

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

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

zbMATH Keywords

optimizationfixed pointnonexpansive operatorasynchronous parallel coordinate updates

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Numerical optimization and variational techniques (65K10) Numerical methods based on necessary conditions (49M05) Iterative procedures involving nonlinear operators (47J25) Numerical methods based on nonlinear programming (49M37) Fixed-point theorems (47H10) Decentralized systems (93A14) Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Acceleration of convergence in numerical analysis (65B99)

Related Items

A new randomized primal-dual algorithm for convex optimization with fast last iterate convergence rates, Randomized progressive hedging methods for multi-stage stochastic programming, Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems, A class of smooth exact penalty function methods for optimization problems with orthogonality constraints, Primal-dual algorithms for multi-agent structured optimization over message-passing architectures with bounded communication delays, A novel bound on the convergence rate of ADMM for distributed optimization, An asynchronous inertial algorithm for solving convex feasibility problems with strict pseudo-contractions in Hilbert spaces, On unbounded delays in asynchronous parallel fixed-point algorithms, Perturbed Iterate Analysis for Asynchronous Stochastic Optimization, Cyclic Coordinate-Update Algorithms for Fixed-Point Problems: Analysis and Applications, Parallel and distributed asynchronous adaptive stochastic gradient methods, On the convergence of asynchronous parallel iteration with unbounded delays, Asynchronous sequential inertial iterations for common fixed points problems with an application to linear systems, Convergence of an asynchronous block-coordinate forward-backward algorithm for convex composite optimization, Asynchronous Optimization over Weakly Coupled Renewal Systems, Variance reduction for root-finding problems, Asynchronous parallel algorithms for nonconvex optimization, Asynchronous level bundle methods, Hybrid Jacobian and Gauss--Seidel Proximal Block Coordinate Update Methods for Linearly Constrained Convex Programming, Asynchronous distributed voltage control in active distribution networks, Primal-dual block-proximal splitting for a class of non-convex problems, Distributed Deterministic Asynchronous Algorithms in Time-Varying Graphs Through Dykstra Splitting, Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs, Global convergence of ADMM in nonconvex nonsmooth optimization, Scalable Asynchronous Domain Decomposition Solvers, Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization, An asynchronous distributed and scalable generalized Nash equilibrium seeking algorithm for strongly monotone games, Proximal primal-dual best approximation algorithm with memory, Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning, Partition-based multi-agent optimization in the presence of lossy and asynchronous communication, Convergence Theorems and Convergence Rates for the General Inertial Krasnosel’skiǐ–Mann Algorithm, Distributed Learning with Sparse Communications by Identification, A stochastic subspace approach to gradient-free optimization in high dimensions, Markov chain block coordinate descent, A Distributed Flexible Delay-Tolerant Proximal Gradient Algorithm, ARock, Parallelizable Algorithms for Optimization Problems with Orthogonality Constraints, Risk-averse stochastic programming and distributionally robust optimization via operator splitting, An inertial parallel and asynchronous forward-backward iteration for distributed convex optimization, Block-proximal methods with spatially adapted acceleration

Uses Software

• TMAC
• HOGWILD

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• Parallel coordinate descent methods for big data optimization
• A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
• Parallel asynchronous iterations for the solution of a 3D continuous flow electrophoresis problem
• Asynchronous finite-difference schemes for partial differential equations
• Some aspects of parallel and distributed iterative algorithms - a survey
• Ergodic convergence to a zero of the sum of monotone operators in Hilbert space
• Some convergence results for asynchronous algorithms
• Asynchronous weighted additive Schwarz methods
• Asynchronous multisplitting methods for nonlinear fixed point problems
• On asynchronous iterations
• Coordinate-friendly structures, algorithms and applications
• A splitting algorithm for dual monotone inclusions involving cocoercive operators
• Construction of fixed points of demicompact mappings in Hilbert space
• Chaotic relaxation
• On the Convergence of Decentralized Gradient Descent
• Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
• Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties
• Evolution equations for maximal monotone operators: asymptotic analysis in continuous and discrete time
• Revisiting Asynchronous Linear Solvers
• Distributed asynchronous computation of fixed points
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• On the Rate of Convergence of a Partially Asynchronous Gradient Projection Algorithm
• Asynchronous Iterative Methods for Multiprocessors
• Implicit-Explicit Parallel Asynchronous Solver of Parabolic PDEs
• Convergence rate analysis of an asynchronous space decomposition method for convex Minimization
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• Distributed Subgradient Methods for Multi-Agent Optimization
• Partially Asynchronous, Parallel Algorithms for Network Flow and Other Problems
• Convergence Rate Analysis of Several Splitting Schemes
• Self Equivalence of the Alternating Direction Method of Multipliers
• Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions
• Stochastic Quasi-Fejér Block-Coordinate Fixed Point Iterations with Random Sweeping
• An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
• Weak convergence of the sequence of successive approximations for nonexpansive mappings
• A case study in programming for parallel-processors
• Convex analysis and monotone operator theory in Hilbert spaces