Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Analyzing random permutations for cyclic coordinate descent
HTML articles powered by AMS MathViewer

by Stephen J. Wright and Ching-pei Lee HTML | PDF
Math. Comp. 89 (2020), 2217-2248 Request permission

Abstract:

We consider coordinate descent methods for minimization of convex quadratic functions, 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 functions for which the random permutations version of cyclic coordinate descent (RPCD) is observed to outperform the standard cyclic coordinate descent (CCD) approach on computational tests, yielding convergence behavior similar to the fully random variant (RCD). A convergence analysis is developed to explain the empirical observations.
References
  • Amir Beck and Luba Tetruashvili, On the convergence of block coordinate descent type methods, SIAM J. Optim. 23 (2013), no. 4, 2037–2060. MR 3116649, DOI 10.1137/120887679
  • I. Gelfand, Normierte Ringe, Rec. Math. [Mat. Sbornik] N. S. 9 (51) (1941), 3–24 (German, with Russian summary). MR 0004726
  • Ching-pei Lee and Stephen J. Wright, Random permutations fix a worst case for cyclic coordinate descent, IMA J. Numer. Anal. 39 (2019), no. 3, 1246–1275. MR 4023751, DOI 10.1093/imanum/dry040
  • Xingguo Li, Tuo Zhao, Raman Arora, Han Liu, and Mingyi Hong, On faster convergence of cyclic block coordinate descent-type methods for strongly convex minimization, J. Mach. Learn. Res. 18 (2017), Paper No. 184, 24. MR 3827072
  • Yu. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim. 22 (2012), no. 2, 341–362. MR 2968857, DOI 10.1137/100802001
  • B. Recht and C. Ré, Toward a noncommutative arithmetic-geometric mean inequality: Conjectures, case-studies, and consequences, Proceedings of the 25th Annual Conference on Learning Theory, vol. 23, 2012, pp. 11.1–11.24.
  • Shai Shalev-Shwartz and Tong Zhang, Stochastic dual coordinate ascent methods for regularized loss minimization, J. Mach. Learn. Res. 14 (2013), 567–599. MR 3033340
  • R. Sun and M. Hong, Improved iteration complexity bounds of cyclic block coordinate descent for convex problems, Advances in Neural Information Processing Systems, 2015, pp. 1306–1314.
  • R. Sun, Z.-Q. Luo, and Y. Ye, On the efficiency of random permutation for admm and coordinate descent, Tech. Report arXiv:1503.06387 (2019). To appear in Math. Oper. Res.
  • R. Sun and Y. Ye, Worst-case complexity of cyclic coordinate descent: ${O}(n^2)$ gap with randomized version, Mathematical Programming (2019), 1–34, Online first.
  • S. J. Wright, Computations with coordinate descent methods, Presentation at Workshop on Challenges in Optimization for Data Science, https://pcombet.math.ncsu.edu/data2015/, July 2015.
  • S. J. Wright, Coordinate descent methods, Colloquium, Courant Institute of Mathematical Sciences, December 2015.
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2010): 65F10, 90C25, 68W20
  • Retrieve articles in all journals with MSC (2010): 65F10, 90C25, 68W20
Additional Information
  • Stephen J. Wright
  • Affiliation: Computer Sciences Department, University of Wisconsin-Madison, Madison, Wisconsin
  • MR Author ID: 213980
  • Email: swright@cs.wisc.edu
  • Ching-pei Lee
  • Affiliation: Computer Sciences Department, University of Wisconsin-Madison, Madison, Wisconsin
  • Address at time of publication: Department of Mathematics, National University of Singapore
  • MR Author ID: 1024505
  • Email: leechingpei@gmail.com
  • Received by editor(s): May 27, 2017
  • Received by editor(s) in revised form: February 12, 2019, November 25, 2019, and January 5, 2020
  • Published electronically: March 27, 2020
  • Additional Notes: This work was supported by NSF Awards IIS-1447449, 1628384, 1634597, and 1740707; ONR Award N00014-13-1-0129; AFOSR Award FA9550-13-1-0138, and Subcontracts 3F-30222 and 8F-30039 from Argonne National Laboratory; and Award N660011824020 from the DARPA Lagrange Program.
  • © Copyright 2020 American Mathematical Society
  • Journal: Math. Comp. 89 (2020), 2217-2248
  • MSC (2010): Primary 65F10; Secondary 90C25, 68W20
  • DOI: https://doi.org/10.1090/mcom/3530
  • MathSciNet review: 4109565