Analyzing random permutations for cyclic coordinate descent
From MaRDI portal
Publication:5113666
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.
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
Cites work
- Efficiency of coordinate descent methods on huge-scale optimization problems
- On faster convergence of cyclic block coordinate descent-type methods for strongly convex minimization
- On the convergence of block coordinate descent type methods
- Random permutations fix a worst case for cyclic coordinate descent
- Stochastic dual coordinate ascent methods for regularized loss minimization
Cited in
(14)- Two symmetrized coordinate descent methods can be \(O(n^2)\) times slower than the randomized version
- Inexact variable metric stochastic block-coordinate descent for regularized optimization
- Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
- 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
- Why random reshuffling beats stochastic gradient descent
- scientific article; zbMATH DE number 3905760 (Why is no real title available?)
- Distributed block-diagonal approximation methods for regularized empirical risk minimization
- Random permutations fix a worst case for cyclic coordinate descent
- 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
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)
