×

zbMATH — the first resource for mathematics

ARock: an algorithmic framework for asynchronous parallel coordinate updates. (English) Zbl 1350.49041

MSC:
49M30 Other numerical methods in calculus of variations (MSC2010)
49M37 Numerical methods based on nonlinear programming
49M05 Numerical methods based on necessary conditions
47J25 Iterative procedures involving nonlinear operators
47H09 Contraction-type mappings, nonexpansive mappings, \(A\)-proper mappings, etc.
65K05 Numerical mathematical programming methods
65K10 Numerical optimization and variational techniques
65B99 Acceleration of convergence in numerical analysis
90C25 Convex programming
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
47H10 Fixed-point theorems
93A14 Decentralized systems
Software:
ARock; HOGWILD; TMAC
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] D. Aharoni and A. Barak, Parallel iterative discontinuous Galerkin finite-element methods, in Discontinuous Galerkin Methods, Springer, Berlin, 2000, pp. 247–254. · Zbl 0945.65126
[2] D. Amitai, A. Averbuch, M. Israeli, and S. Itzikowitz, Implicit-explicit parallel asynchronous solver of parabolic PDEs, SIAM J. Sci. Comput., 19 (1998), pp. 1366–1404, http://dx.doi.org/10.1137/S1064827595281290 doi:10.1137/S1064827595281290. · Zbl 0914.65092
[3] H. Avron, A. Druinsky, and A. Gupta, Revisiting asynchronous linear solvers: Provable convergence rate through randomization, in Proceedings of the 28th International IEEE Symposium on Parallel and Distributed Processing, IEEE Press, Piscataway, NJ, 2014, pp. 198–207. · Zbl 1426.65047
[4] J. Bahi, J.-C. Miellou, and K. Rhofir, Asynchronous multisplitting methods for nonlinear fixed point problems, Numer. Algorithms, 15 (1997), pp. 315–345. · Zbl 0893.65034
[5] G. M. Baudet, Asynchronous iterative methods for multiprocessors, J. ACM, 25 (1978), pp. 226–244. · Zbl 0372.68015
[6] H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer Science+Business Media, New York, 2011. · Zbl 1218.47001
[7] D. P. Bertsekas, Distributed asynchronous computation of fixed points, Math. Programming, 27 (1983), pp. 107–120. · Zbl 0521.90089
[8] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Prentice Hall, Englewood Cliffs, NJ, 1989.
[9] D. P. Bertsekas and J. N. Tsitsiklis, Some aspects of parallel and distributed iterative algorithms—a survey, Automatica, 27 (1991), pp. 3–21. · Zbl 0728.65041
[10] I. Bethune, J. M. Bull, N. J. Dingle, and N. J. Higham, Performance analysis of asynchronous Jacobi’s method implemented in MPI, SHMEM and OpenMP, Int. J. High Performance Comput. Appl., 28 (2014), pp. 97–111.
[11] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3 (2011), pp. 1–122. · Zbl 1229.90122
[12] K.-W. Chang, C.-J. Hsieh, and C.-J. Lin, Coordinate descent method for large-scale \(l2\)-loss linear support vector machines, J. Mach. Learn. Res., 9 (2008), pp. 1369–1398. · Zbl 1225.68157
[13] M. Chau, P. Spiteri, R. Guivarch, and H. Boisson, Parallel asynchronous iterations for the solution of a 3D continuous flow electrophoresis problem, Comput. & Fluids, 37 (2008), pp. 1126–1137, http://dx.doi.org/10.1016/j.compfluid.2007.06.006 doi:10.1016/j.compfluid.2007.06.006. · Zbl 1237.76210
[14] D. Chazan and W. Miranker, Chaotic relaxation, Linear Algebra Appl., 2 (1969), pp. 199–222. · Zbl 0225.65043
[15] P. L. Combettes and J.-C. Pesquet, Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping, SIAM J. Optim., 25 (2015), pp. 1221–1248, http://dx.doi.org/10.1137/140971233 doi:10.1137/ 140971233. · Zbl 1317.65135
[16] L. Condat, A primal–dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, J. Optim. Theory Appl., 158 (2013), pp. 460–479. · Zbl 1272.90110
[17] D. Davis and W. Yin, A Three-Operator Splitting Scheme and Its Optimization Applications, preprint, https://arxiv.org/abs/1504.01032 arXiv:1504.01032, 2015.
[18] D. Davis and W. Yin, Convergence rate analysis of several splitting schemes, in Splitting Methods in Communication and Imaging, Science and Engineering, R. Glowinski, S. Osher, and W. Yin, eds., Springer, New York, 2016, pp. 117–166.
[19] D. Davis and W. Yin, Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions, Math. Oper. Res., to appear. · Zbl 1379.65035
[20] D. A. Donzis and K. Aditya, Asynchronous finite-difference schemes for partial differential equations, J. Comput. Phys., 274 (2014), pp. 370–392. · Zbl 1351.76162
[21] B. Edmunds, Z. Peng, and W. Yin, TMAC: A Toolbox of Modern Async-Parallel, Coordinate, Splitting, and Stochastic Methods, preprint, https://arxiv.org/abs/1606.04551 arXiv:1606.04551, 2016.
[22] D. El Baz, P. Spiteri, J. C. Miellou, and D. Gazen, Asynchronous iterative algorithms with flexible communication for nonlinear network flow problems, J. Parallel Distrib. Comput., 38 (1996), pp. 1–15.
[23] M. N. El Tarazi, Some convergence results for asynchronous algorithms, Numer. Math., 39 (1982), pp. 325–340 (in French). · Zbl 0479.65030
[24] Executive Office of the President, Big Data: Seizing Opportunities, Preserving Values, U.S. Government, Washington, DC, 2014.
[25] L. Fang and P. J. Antsaklis, Information consensus of asynchronous discrete-time multi-agent systems, in Proceedings of the 2005 American Control Conference, IEEE Press, Piscataway, NJ, 2005, pp. 1883–1888.
[26] A. Frommer, H. Schwandt, and D. B. Szyld, Asynchronous weighted additive Schwarz methods, Electron. Trans. Numer. Anal., 5 (1997), pp. 48–61. · Zbl 0890.65027
[27] A. Frommer and D. B. Szyld, On asynchronous iterations, J. Comput. Appl. Math., 123 (2000), pp. 201–216. · Zbl 0967.65066
[28] D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems M. Fortin and R. Glowinski, eds., Stud. Math. Appl., 15 (1983), pp. 299–331.
[29] R. Glowinski and A. Marroco, Sur l’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, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge Anal. Numéïr. 9 (1975), pp. 41–76.
[30] M. Hong, A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach, preprint, https://arxiv.org/abs/1412.6058 arXiv:1412.6058, 2014.
[31] C.-J. Hsieh, H.-F. Yu, and I. S. Dhillon, Passcode: Parallel asynchronous stochastic dual co-ordinate descent, in Proceedings of the 32nd International Conference on Machine Learning (ICML-15), Lille, France, 2015, pp. 2370ï–2379.
[32] F. Iutzeler, P. Bianchi, P. Ciblat, and W. Hachem, Asynchronous distributed optimization using a randomized alternating direction method of multipliers, in Proceedings of the 52nd Annual IEEE Conference on Decision and Control (CDC), IEEE Press, Piscataway, NJ, 2013, pp. 3671–3676.
[33] M. A. Krasnosel’skiĭ, Two remarks on the method of successive approximations, Uspehi Mat. Nauk, 10 (1955), pp. 123–127.
[34] A. Kyrola, D. Bickson, C. Guestrin, and J. K. Bradley, Parallel coordinate descent for l1-regularized loss minimization, in Proceedings of the 28th International Conference on Machine Learning (ICML-11), Bellevue, WA, 2011, pp. 321–328.
[35] B. Lang, J. Miellou, and P. Spiteri, Asynchronous relaxation algorithms for optimal control problems, Math. Comput. Simul., 28 (1986), pp. 227–242.
[36] R. Leblond, F. Pedregosa, and S. Lacoste-Julien, ASAGA: Asynchronous Parallel SAGA, preprint, https://arxiv.org/abs/1606.04809 arXiv:1606.04809, 2016.
[37] P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16 (1979), pp. 964–979, http://dx.doi.org/10.1137/0716071 doi:10.1137/0716071. · Zbl 0426.65050
[38] J. Liu and S. J. Wright, Asynchronous stochastic coordinate descent: Parallelism and convergence properties, SIAM J. Optim., 25 (2015), pp. 351–376, http://dx.doi.org/10.1137/140961134 doi:10.1137/140961134. · Zbl 1358.90098
[39] J. Liu, S. J. Wright, C. Ré, V. Bittorf, and S. Sridhar, An asynchronous parallel stochastic coordinate descent algorithm, J. Mach. Learn. Res., 16 (2015), pp. 285–322. · Zbl 1337.68286
[40] A. Nedić, D. P. Bertsekas, and V. S. Borkar, Distributed asynchronous incremental subgradient methods, Stud. Comput. Math., 8 (2001), pp. 381–407. · Zbl 0997.90102
[41] A. Nedic and A. Ozdaglar, Distributed subgradient methods for multi-agent optimization, IEEE Trans. Automat. Control, 54 (2009), pp. 48–61. · Zbl 1367.90086
[42] Yu. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim., 22 (2012), pp. 341–362, http://dx.doi.org/10.1137/100802001 doi:10.1137/100802001. · Zbl 1257.90073
[43] R. C. Larson and A. R. Odoni, Urban Operations Research, 2nd ed., Dynamic Ideas, Charlestown, MA, 2007.
[44] Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Amer. Math. Soc., 73 (1967), pp. 591–597, http://dx.doi.org/10.1090/S0002-9904-1967-11761-0 doi:10.1090/S0002-9904-1967-11761-0. · Zbl 0179.19902
[45] G. B. Passty, Ergodic convergence to a zero of the sum of monotone operators in Hilbert space, J. Math. Anal. Appl., 72 (1979), pp. 383–390. · Zbl 0428.47039
[46] Z. Peng, T. Wu, Y. Xu, M. Yan, and W. Yin, Coordinate friendly structures, algorithms and applications, Ann. Math. Sci. Appl., 1 (2016), pp. 57ï–119. · Zbl 1432.65076
[47] Z. Peng, M. Yan, and W. Yin, Parallel and distributed sparse optimization, in Proceedings of the 2013 Asilomar Conference on Signals, Systems and Computers, IEEE Press, Piscataway, NJ, 2013, pp. 659–665.
[48] W. Petryshyn, Construction of fixed points of demicompact mappings in Hilbert space, J. Math. Anal. Appl., 14 (1966), pp. 276–284. · Zbl 0138.39802
[49] J. Peypouquet and S. Sorin, Evolution equations for maximal monotone operators: Asymptotic analysis in continuous and discrete time, J. Convex Anal., 17 (2010), pp. 1113–1163. · Zbl 1214.47080
[50] B. Recht, C. Re, S. Wright, and F. Niu, Hogwild: A lock-free approach to parallelizing stochastic gradient descent, in Advances in Neural Information Processing Systems 24, (NIPS 2011), J. Shawe-Taylor et al., eds., Neural Information Processing Systems Foundation, Inc., La Jolla, CA, 2011, pp. 693–701.
[51] P. Richtárik and M. Takáč, Parallel coordinate descent methods for big data optimization, Math. Programming, Ser. A, 156 (2016), pp. 433–484.
[52] H. Robbins and D. Siegmund, A convergence theorem for non negative almost supermartingales and some applications, in Herbert Robbins Selected Papers, Springer, New York, 1985, pp. 111–135.
[53] J. L. Rosenfeld, A case study in programming for parallel-processors, Comm. ACM, 12 (1969), pp. 645–655. · Zbl 0184.20701
[54] X.-C. Tai and P. Tseng, Convergence rate analysis of an asynchronous space decomposition method for convex minimization, Math. Comp., 71 (2002), pp. 1105–1135. · Zbl 0997.65088
[55] P. Tseng, On the rate of convergence of a partially asynchronous gradient projection algorithm, SIAM J. Optim., 1 (1991), pp. 603–619, http://dx.doi.org/10.1137/0801036 doi:10.1137/0801036. · Zbl 0754.90055
[56] P. Tseng, D. P. Bertsekas, and J. N. Tsitsiklis, Partially asynchronous, parallel algorithms for network flow and other problems, SIAM J. Control Optim., 28 (1990), pp. 678–710, http://dx.doi.org/10.1137/0328040 doi:10.1137/0328040. · Zbl 0725.65054
[57] B. C. Vu͂, A splitting algorithm for dual monotone inclusions involving cocoercive operators, Ad. Comput. Math., 38 (2013), pp. 667–681. · Zbl 1284.47045
[58] E. Wei and A. Ozdaglar, On the \(o(1/k)\) convergence of asynchronous distributed alternating direction method of multipliers, in Proceedings of the 2013 IEEE Global Conference on Signal and Information Processing (GlobalSIP), IEEE Press, Piscataway, NJ, 2013, pp. 551–554.
[59] M. Yan and W. Yin, Self equivalence of the alternating direction method of multipliers, in Splitting Methods in Communication and Imaging, Science and Engineering, R. Glowinski, S. Osher, and W. Yin, eds., Springer International Publishing, Switzerland, 2016.
[60] K. Yuan, Q. Ling, and W. Yin, On the convergence of decentralized gradient descent, SIAM J. Optim., 26 (2016), pp. 1835–1854, http://dx.doi.org/10.1137/130943170 doi:10.1137/130943170. · Zbl 1345.90068
[61] R. Zhang and J. Kwok, Asynchronous distributed ADMM for consensus optimization, in Proceedings of the 31st International Conference on Machine Learning (ICML-14), Beijing, China, 2014, pp. 1701–1709.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.