Coordinate Friendly Structures, Algorithms and Applications

Abstract

This paper focuses on coordinate update methods, which are useful for solving problems involving large or high-dimensional datasets. They decompose a problem into simple subproblems, where each updates one, or a small block of, variables while fixing others. These methods can deal with linear and nonlinear mappings, smooth and nonsmooth functions, as well as convex and nonconvex problems. In addition, they are easy to parallelize. The great performance of coordinate update methods depends on solving simple sub-problems. To derive simple subproblems for several new classes of applications, this paper systematically studies coordinate-friendly operators that perform low-cost coordinate updates. Based on the discovered coordinate friendly operators, as well as operator splitting techniques, we obtain new coordinate update algorithms for a variety of problems in machine learning, image processing, as well as sub-areas of optimization. Several problems are treated with coordinate update for the first time in history. The obtained algorithms are scalable to large instances through parallel and even asynchronous computing. We present numerical examples to illustrate how effective these algorithms are.

References in corpus (11)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
• Parallel Coordinate Descent for L1-Regularized Loss Minimization
• An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
• Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection
• A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions
• A Three-Operator Splitting Scheme and its Optimization Applications
• PASSCoDe: Parallel ASynchronous Stochastic dual Co-ordinate Descent
• A globally convergent algorithm for nonconvex optimization based on block coordinate update
• Iteration Complexity Analysis of Block Coordinate Descent Methods
• An $O(n\log (n))$ Algorithm for Projecting Onto the Ordered Weighted ${\ell }_1$ Norm Ball

Cited by in corpus (24)

• ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
• A Primer on Coordinate Descent Algorithms
• The Asynchronous PALM Algorithm for Nonsmooth Nonconvex Problems
• Coordinate-wise descent methods for leading eigenvalue problem
• First-order methods for constrained convex programming based on linearized augmented Lagrangian function
• Block-proximal methods with spatially adapted acceleration
• ADMM-Tracking Gradient for Distributed Optimization over Asynchronous and Unreliable Networks
• Federated Orchestration for Network Slicing of Bandwidth and Computational Resource
• Robust Online Learning over Networks
• Decentralized Consensus Optimization with Asynchrony and Delays
• Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descent
• From safe screening rules to working sets for faster Lasso-type solvers
• HyperLISTA-ABT: An Ultra-light Unfolded Network for Accurate Multi-component Differential Tomographic SAR Inversion
• A new primal-dual algorithm for minimizing the sum of three functions with a linear operator
• Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs
• TMAC: A Toolbox of Modern Async-Parallel, Coordinate, Splitting, and Stochastic Methods
• On Unbounded Delays in Asynchronous Parallel Fixed-Point Algorithms
• A Randomized Block-Coordinate Primal-Dual Method for Large-scale Stochastic Saddle Point Problems
• A Stochastic Operator Framework for Optimization and Learning with Sub-Weibull Errors
• Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
• Greedy coordinate descent method on non-negative quadratic programming
• Cyclic Coordinate Update Algorithms for Fixed-Point Problems: Analysis and Applications
• Multi-Agent Optimization and Learning: A Non-Expansive Operators Perspective
• Asynchronous Multi-Task Learning