Analyzing random permutations for cyclic coordinate descent
From MaRDI portal
Publication:5113666
DOI10.1090/MCOM/3530zbMATH Open1442.65049arXiv1706.00908OpenAlexW3006529314MaRDI QIDQ5113666FDOQ5113666
Authors: Stephen J. Wright, Ching-pei Lee 
Publication date: 15 June 2020
Published in: Mathematics of Computation (Search for Journal in Brave)
Abstract: We consider coordinate descent methods on convex quadratic problems, in which exact line searches are performed at each iteration. (This algorithm is identical to Gauss-Seidel on the equivalent symmetric positive definite linear system.) We describe a class of convex quadratic problems for which the random-permutations version of cyclic coordinate descent (RPCD) outperforms the standard cyclic coordinate descent (CCD) approach, yielding convergence behavior similar to the fully-random variant (RCD). A convergence analysis is developed to explain the empirical observations.
Full work available at URL: https://arxiv.org/abs/1706.00908
Recommendations
- Random permutations fix a worst case for cyclic coordinate descent
- Randomness and permutations in coordinate descent methods
- On the efficiency of random permutation for ADMM and coordinate descent
- Worst-case complexity of cyclic coordinate descent: \(O(n^2)\) gap with randomized version
- scientific article; zbMATH DE number 3905760
Convex programming (90C25) Randomized algorithms (68W20) Iterative numerical methods for linear systems (65F10)
Cites Work
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Stochastic dual coordinate ascent methods for regularized loss minimization
- On the convergence of block coordinate descent type methods
- Random permutations fix a worst case for cyclic coordinate descent
- On faster convergence of cyclic block coordinate descent-type methods for strongly convex minimization
Cited In (14)
- Inexact variable metric stochastic block-coordinate descent for regularized optimization
- On the efficiency of random permutation for ADMM and coordinate descent
- Randomized Block Adaptive Linear System Solvers
- Cyclic Coordinate Dual Averaging with Extrapolation
- An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems
- Title not available (Why is that?)
- Why random reshuffling beats stochastic gradient descent
- Random permutations fix a worst case for cyclic coordinate descent
- Distributed block-diagonal approximation methods for regularized empirical risk minimization
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- Worst-case complexity of cyclic coordinate descent: \(O(n^2)\) gap with randomized version
- Randomness and permutations in coordinate descent methods
- Two symmetrized coordinate descent methods can be \(O(n^2)\) times slower than the randomized version
- Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
This page was built for publication: Analyzing random permutations for cyclic coordinate descent
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113666)
