Randomness and permutations in coordinate descent methods
From MaRDI portal
Publication:2189444
Abstract: We consider coordinate descent (CD) methods with exact line search on convex quadratic problems. Our main focus is to study the performance of the CD method that use random permutations in each epoch and compare it to the performance of the CD methods that use deterministic orders and random sampling with replacement. We focus on a class of convex quadratic problems with a diagonally dominant Hessian matrix, for which we show that using random permutations instead of random with-replacement sampling improves the performance of the CD method in the worst-case. Furthermore, we prove that as the Hessian matrix becomes more diagonally dominant, the performance improvement attained by using random permutations increases. We also show that for this problem class, using any fixed deterministic order yields a superior performance than using random permutations. We present detailed theoretical analyses with respect to three different convergence criteria that are used in the literature and support our theoretical results with numerical experiments.
Recommendations
- Analyzing random permutations for cyclic coordinate descent
- Random permutations fix a worst case for cyclic coordinate descent
- On the efficiency of random permutation for ADMM and coordinate descent
- Two symmetrized coordinate descent methods can be \(O(n^2)\) times slower than the randomized version
- Worst-case complexity of cyclic coordinate descent: O(n^2) gap with randomized version
Cites work
- An arithmetic-geometric mean inequality for products of three matrices
- Convex optimization algorithms
- Coordinate descent algorithms
- Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Efficiency of the accelerated coordinate descent method on structured optimization problems
- Efficient block-coordinate descent algorithms for the group Lasso
- scientific article; zbMATH DE number 6378119 (Why is no real title available?)
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- Iterative Solution of Nonlinear Equations in Several Variables
- Matrix iterative analysis
- On the convergence of block coordinate descent type methods
- On the convergence of the coordinate descent method for convex differentiable minimization
- On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods
- Parallel coordinate descent methods for big data optimization
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Random reordering in SOR-type methods
Cited in
(12)- Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs
- Special issue: On the interface between optimization and probability
- On the efficiency of random permutation for ADMM and coordinate descent
- Analyzing random permutations for cyclic coordinate descent
- Two symmetrized coordinate descent methods can be \(O(n^2)\) times slower than the randomized version
- Computing the best approximation over the intersection of a polyhedral set and the doubly nonnegative cone
- Random permutations fix a worst case for cyclic coordinate descent
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- Laplacian-based semi-supervised learning in multilayer hypergraphs by coordinate descent
- Global stability of first-order methods for coercive tame functions
- Coordinate-update algorithms can efficiently detect infeasible optimization problems
- Using filter methods to guide convergence for ADMM, with applications to nonnegative matrix factorization problems
This page was built for publication: Randomness and permutations in coordinate descent methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2189444)
