Randomness and permutations in coordinate descent methods
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 rand...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2021
|
| Online Access: | https://hdl.handle.net/1721.1/131362 |
| _version_ | 1826190378443735040 |
|---|---|
| author | Gürbüzbalaban, Mert Ozdaglar, Asuman Vanli, Nuri D Wright, Stephen J |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Gürbüzbalaban, Mert Ozdaglar, Asuman Vanli, Nuri D Wright, Stephen J |
| author_sort | Gürbüzbalaban, Mert |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T08:39:23Z |
| format | Article |
| id | mit-1721.1/131362 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:39:23Z |
| publishDate | 2021 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1313622023-09-01T19:35:00Z Randomness and permutations in coordinate descent methods Gürbüzbalaban, Mert Ozdaglar, Asuman Vanli, Nuri D Wright, Stephen J Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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. 2021-09-20T17:16:44Z 2021-09-20T17:16:44Z 2019-09-30 2020-09-24T21:02:35Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/131362 en https://doi.org/10.1007/s10107-019-01438-4 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Gürbüzbalaban, Mert Ozdaglar, Asuman Vanli, Nuri D Wright, Stephen J Randomness and permutations in coordinate descent methods |
| title | Randomness and permutations in coordinate descent methods |
| title_full | Randomness and permutations in coordinate descent methods |
| title_fullStr | Randomness and permutations in coordinate descent methods |
| title_full_unstemmed | Randomness and permutations in coordinate descent methods |
| title_short | Randomness and permutations in coordinate descent methods |
| title_sort | randomness and permutations in coordinate descent methods |
| url | https://hdl.handle.net/1721.1/131362 |
| work_keys_str_mv | AT gurbuzbalabanmert randomnessandpermutationsincoordinatedescentmethods AT ozdaglarasuman randomnessandpermutationsincoordinatedescentmethods AT vanlinurid randomnessandpermutationsincoordinatedescentmethods AT wrightstephenj randomnessandpermutationsincoordinatedescentmethods |