Analyzing random permutations for cyclic coordinate descent
From MaRDI portal
Publication:5113666
DOI10.1090/MCOM/3530zbMATH Open1442.65049arXiv1706.00908OpenAlexW3006529314MaRDI QIDQ5113666FDOQ5113666
Ching-pei Lee, Stephen J. Wright
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 (9)
- Inexact variable metric stochastic block-coordinate descent for regularized optimization
- Randomized Block Adaptive Linear System Solvers
- Cyclic Coordinate Dual Averaging with Extrapolation
- An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems
- Two Symmetrized Coordinate Descent Methods Can Be $O(n^2)$ Times Slower Than the Randomized Version
- Title not available (Why is that?)
- Distributed block-diagonal approximation methods for regularized empirical risk minimization
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- 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)
