Randomness and permutations in coordinate descent methods
| Autor: | Stephen J. Wright, Nuri Denizcan Vanli, Asuman Ozdaglar, Mert Gurbuzbalaban |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Hessian matrix
021103 operations research Line search General Mathematics MathematicsofComputing_NUMERICALANALYSIS 0211 other engineering and technologies Sampling (statistics) 010103 numerical & computational mathematics 02 engineering and technology 01 natural sciences symbols.namesake Quadratic equation Optimization and Control (math.OC) Convergence (routing) FOS: Mathematics symbols Applied mathematics 0101 mathematics Coordinate descent Mathematics - Optimization and Control Software Randomness Diagonally dominant matrix Mathematics |
| Zdroj: | Springer Berlin Heidelberg |
| ISSN: | 1436-4646 0025-5610 |
| DOI: | 10.1007/s10107-019-01438-4 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink