On the Efficiency of Random Permutation for ADMM and Coordinate Descent

References

• [1] Beck A, Tetruashvilie L (2013) On the convergence of block coordinate descent type methods. SIAM J. Optim. 23(4):2037–2060.Crossref, Google Scholar
• [2] Blatt D, Hero AO, Gauchman H (2007) A convergent incremental gradient method with a constant step size. SIAM J. Optim. 18(1):29–51.Crossref, Google Scholar
• [3] Boyd S, Parikh N, Chu E, Peleato B, Eckstein J (2011) Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations Trends Machine Learning 3(1):1–122.Crossref, Google Scholar
• [4] Cai X, Han D, Yuan X (2016) The direct extension of ADMM for three-block separable convex minimization models is convergent when one function is strongly convex. Math. Programming 155(1):57–59.Google Scholar
• [5] Chan TF, Glowinski R (1978) Finite Element Approximation and Iterative Solution of a Class of Mildly Non-linear Elliptic Equations (Computer Science Department, Stanford University, Stanford, CA).Google Scholar
• [6] Chen C, He B, Ye Y, Yuan X (2014) The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math. Programming 155(1/2):1–23.Google Scholar
• [7] Chen C, Li M, Liu X, Ye Y (2017) Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights. Working paper, Nanjing University, Nanjing, China.Google Scholar
• [8] Chen C, Shen Y, You Y (2013) On the convergence analysis of the alternating direction method of multipliers with three blocks. Abstract and Applied Analysis, vol. 2013 (Hindawi Publishing, London).Google Scholar
• [9] Davis D, Yin W (2017) A three-operator splitting scheme and its optimization applications. Set Valued Var. Anal. 25(4):829–858.Crossref, Google Scholar
• [10] Deng W, Lai MJ, Peng Z, Yin W (2017) Parallel multi-block admm with o (1/k) convergence. J. Scientific Comput. 71(2):712–736.Crossref, Google Scholar
• [11] Gabay D, Mercier B (1976) A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2(1):17–40.Crossref, Google Scholar
• [12] Glowinski R, Marroco A (1975) Approximation par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de dirichlet non linéaires. ESAIM: Math. Model. Numerical Anal. 9(R2):41–76.Google Scholar
• [13] Gürbüzbalaban M, Ozdaglar A, Parrilo P (2015) Why random reshuffling beats stochastic gradient descent. Preprint, submitted October 29, https://arXiv:1510.08560.Google Scholar
• [14] Han D, Yuan X (2012) A note on the alternating direction method of multipliers. J. Optim. Theory Appl. 155(1):227–238.Crossref, Google Scholar
• [15] Han D, Yuan X, Zhang W (2014) An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing. Math. Comput. 83(289):2263–2291.Crossref, Google Scholar
• [16] He B, Hou L, Yuan X (2015) On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming. SIAM J. Optim. 25(4):2274–2312.Crossref, Google Scholar
• [17] He B, Tao M, Yuan X (2012) Alternating direction method with Gaussian back substitution for separable convex programming. SIAM J. Optim. 22(2):313–340.Crossref, Google Scholar
• [18] He B, Tao M, Yuan X (2017) Convergence rate and iteration complexity on the alternating direction method of multipliers with a substitution procedure for separable convex programming. Math. Oper. Res. 42(3):662–691.Link, Google Scholar
• [19] He B, Xu HK, Yuan X (2016) On the proximal Jacobian decomposition of ALM for multiple-block separable convex minimization problems and its relationship to ADMM. J. Sci. Comput. 66(3):1204–1217.Crossref, Google Scholar
• [20] Hong M, Chang T-H, Wang X, Razaviyayn M, Ma S, Luo Z-Q (2014) A block successive upper bound minimization method of multipliers for linearly constrained convex optimization. Preprint, submitted January 28, https://arXiv:1401.7079.Google Scholar
• [21] Hong M, Luo Z-Q (2012) On the linear convergence of the alternating direction method of multipliers. Preprint, submitted August 20, https://arXiv:1208.3922.Google Scholar
• [22] Kittaneh F (2006) Spectral radius inequalities for Hilbert space operators. Proc. Amer. Math. Soc. 134(02):385–390.Crossref, Google Scholar
• [23] Lee C-P, Wright SJ (2016) Random permutations fix a worst case for cyclic coordinate descent. Preprint, submitted July 28, https://arXiv:1607.08320.Google Scholar
• [24] Leventhal D, Lewis AS (2010) Randomized methods for linear constraints: Convergence rates and conditioning. Math. Oper. Res. 35(3):641–654.Link, Google Scholar
• [25] Li X, Sun D, Toh K-C (2014) A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions. Math. Programming 155(1/2):333–373.Google Scholar
• [26] Li M, Sun D, Toh K-C (2015) A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block. Asia Pacific J. Oper. Res. 32(04):1550024.Crossref, Google Scholar
• [27] Lin T, Ma S, Zhang S (2014) On the convergence rate of multi-block ADMM. Preprint, submitted August 19, https://arXiv:1408.4265.Google Scholar
• [28] Lin T, Ma S, Zhang S (2014) On the global linear convergence of the ADMM with multi-block variables. Preprint, submitted August 19, https://arXiv:1408.4266.Google Scholar
• [29] Lin T, Ma S, Zhang S (2015) Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity. Preprint, submitted April 13, https://arXiv:1504.03087.Google Scholar
• [30] Nesterov Y (2012) Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22(2):341–362.Crossref, Google Scholar
• [31] Recht B, Ré C (2012) Beneath the valley of the noncommutative arithmetic-geometric mean inequality: Conjectures, case-studies, and consequences. Preprint, submitted February 19, https://arXiv:1202.4184.Google Scholar
• [32] Recht B, Ré C (2013) Parallel stochastic gradient algorithms for large-scale matrix completion. Math. Programming Comput. 5(2):201–226.Crossref, Google Scholar
• [33] Schmidt M, Le Roux N, Bach F (2013) Minimizing finite sums with the stochastic average gradient. Preprint, submitted September 10, https://arXiv:1309.2388.Google Scholar
• [34] Shalev-Shwartz S, Zhang T (2013) Stochastic dual coordinate ascent methods for regularized loss. J. Machine Learning Res. 14(1):567–599.Google Scholar
• [35] Shi HJM, Tu S, Xu Y, Yin W (2016) A primer on coordinate descent algorithms. Preprint, submitted September 30, https://arXiv:1610.00040.Google Scholar
• [36] Strang WG (1962) Eigenvalues of jordan products. Amer. Math. Monthly 69(1):37–40.Crossref, Google Scholar
• [37] Sun D, Toh KC, Yang L (2014) A convergent proximal alternating direction method of multipliers for conic programming with 4-block constraints. Preprint, submitted April 22, https://arXiv:1404.5378.Google Scholar
• [38] Sun R (2015) Matrix completion via nonconvex factorization: Algorithms and theory. Unpublished doctoral dissertation, University of Minnesota, Minneapolis.Crossref, Google Scholar
• [39] Sun R, Hong M (2015) Improved iteration complexity bounds of cyclic block coordinate descent for convex problems. Cortes C, Lawrence ND, Lee DD, Sugiyama M, Garnett R, eds. Advances in Neural Information Processing Systems 28 (MIT Press, Cambridge, MA), 1306–1314.Google Scholar
• [40] Sun R, Luo ZQ, Ye Y (2015) On the expected convergence of randomly permuted ADMM. Preprint, submitted March 22, https://arXiv:1503.06387.Google Scholar
• [41] Sun R, Ye Y (2016) Worst-case complexity of cyclic coordinate descent: O(n2) gap with randomized version. Preprint, submitted April 25, https://arXiv:1604.07130.Google Scholar
• [42] Tseng P (2001) Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. 109(3):475–494.Crossref, Google Scholar
• [43] Wang H, Banerjee A, Luo Z-Q (2014) Parallel direction method of multipliers. Proc. 27th Internat. Conf. Neural Inform. Processing Systems, vol. 1 (MIT Press, Cambridge, MA), 181–189.Google Scholar
• [44] Wright SJ (2015) Coordinate descent algorithms. Math. Programming 151(1):3–34.Crossref, Google Scholar
• [45] Wright SJ, Lee C-P (2017) Analyzing random permutations for cyclic coordinate descent. Preprint, submitted June 3, https://arXiv:1706.00908.Google Scholar