Skip to main content
Top

2015 | OriginalPaper | Chapter

Distributed Block Coordinate Descent for Minimizing Partially Separable Functions

Authors : Jakub Mareček, Peter Richtárik, Martin Takáč

Published in: Numerical Analysis and Optimization

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

A distributed randomized block coordinate descent method for minimizing a convex function of a huge number of variables is proposed. The complexity of the method is analyzed under the assumption that the smooth part of the objective function is partially block separable. The number of iterations required is bounded by a function of the error and the degree of separability, which extends the results in Richtárik and Takác (Parallel Coordinate Descent Methods for Big Data Optimization, Mathematical Programming, DOI:10.1007/s10107-015-0901-6) to a distributed environment. Several approaches to the distribution and synchronization of the computation across a cluster of multi-core computer are described and promising computational results are provided.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Appendix
Available only for authorised users
Footnotes
1
Note that \(\xi \in \{\lceil \tfrac{\omega }{\mathit{C}}\rceil,\ldots,\omega \}\).
 
2
In fact, \(\vert \hat{\mathit{Z}}\vert = \mathit{C}\tau\) with probability 1.
 
3
For the start of the algorithm we define \(\delta g_{l}^{(\mathit{c})} =\delta G_{l}^{(\mathit{c})} = \mathbf{0}\) for all l < 0.
 
Literature
1.
go back to reference Alham, N.K., Li, M., Liu, Y., Hammoud, S.: A MapReduce-based distributed SVM algorithm for automatic image annotation. Comput. Math. Appl. 62(7), 2801–2811 (2011)CrossRefMATH Alham, N.K., Li, M., Liu, Y., Hammoud, S.: A MapReduce-based distributed SVM algorithm for automatic image annotation. Comput. Math. Appl. 62(7), 2801–2811 (2011)CrossRefMATH
2.
go back to reference Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999)MATH Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999)MATH
3.
go back to reference Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Prentice-Hall Inc., Upper Saddle River (1989)MATH Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Prentice-Hall Inc., Upper Saddle River (1989)MATH
4.
go back to reference Chang, E.Y., Zhu, K., Wang, H., Bai, H., Li, J., Qiu, Z., Cui, H.: PSVM: parallelizing support vector machines on distributed computers. Adv. Neural Inf. Process. Syst. 20, 1–18 (2007) Chang, E.Y., Zhu, K., Wang, H., Bai, H., Li, J., Qiu, Z., Cui, H.: PSVM: parallelizing support vector machines on distributed computers. Adv. Neural Inf. Process. Syst. 20, 1–18 (2007)
5.
go back to reference Fercoq, O., Richtárik, P.: Accelerated, parallel and proximal coordinate descent. arXiv:1312.5799 (2013) Fercoq, O., Richtárik, P.: Accelerated, parallel and proximal coordinate descent. arXiv:1312.5799 (2013)
6.
go back to reference Fercoq, O., Richtárik, P.: Smooth minimization of nonsmooth functions with parallel coordinate descent methods. arXiv:1309.5885 (2013) Fercoq, O., Richtárik, P.: Smooth minimization of nonsmooth functions with parallel coordinate descent methods. arXiv:1309.5885 (2013)
7.
go back to reference Fercoq, O., Qu, Z., Richtárik, P., Takáč, M.: Fast distributed coordinate descent for non-strongly convex losses. In: IEEE Workshop on Machine Learning for Signal Processing (2014)CrossRef Fercoq, O., Qu, Z., Richtárik, P., Takáč, M.: Fast distributed coordinate descent for non-strongly convex losses. In: IEEE Workshop on Machine Learning for Signal Processing (2014)CrossRef
9.
go back to reference Hsieh,C.-J., Chang, K.-W., Lin, C.-J., Sathiya Keerthi, S., Sundararajan, S.: A dual coordinate descent method for large-scale linear SVM. In: Proceedings of the 25th International Conference on Machine Learning, ICML ’08, pp. 408–415. ACM, New York (2008) Hsieh,C.-J., Chang, K.-W., Lin, C.-J., Sathiya Keerthi, S., Sundararajan, S.: A dual coordinate descent method for large-scale linear SVM. In: Proceedings of the 25th International Conference on Machine Learning, ICML ’08, pp. 408–415. ACM, New York (2008)
10.
go back to reference InfiniBand Trade Association: InfiniBand Architecture Specification, vol. 1, Release 1.0 (2005) InfiniBand Trade Association: InfiniBand Architecture Specification, vol. 1, Release 1.0 (2005)
12.
go back to reference Lee, Y.T., Sidford, A.: Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. In: 54th Annual Symposium on Foundations of Computer Science. IEEE, New York (2013) Lee, Y.T., Sidford, A.: Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. In: 54th Annual Symposium on Foundations of Computer Science. IEEE, New York (2013)
13.
go back to reference Lewis, D.D., Yang, Y., Rose, T.G., Li, F.: Rcv1: A new benchmark collection for text categorization research. J. Mach. Learn. Res. 5, 361–397 (2004) Lewis, D.D., Yang, Y., Rose, T.G., Li, F.: Rcv1: A new benchmark collection for text categorization research. J. Mach. Learn. Res. 5, 361–397 (2004)
15.
go back to reference Liu, J., Wright, S.J., Ré, C., Bittorf, V.: An asynchronous parallel stochastic coordinate descent algorithm. arXiv:1311.1873 (2013) Liu, J., Wright, S.J., Ré, C., Bittorf, V.: An asynchronous parallel stochastic coordinate descent algorithm. arXiv:1311.1873 (2013)
16.
go back to reference Lu, Z., Xiao, L.: On the complexity analysis of randomized block-coordinate descent methods. arXiv:1305.4723 (2013) Lu, Z., Xiao, L.: On the complexity analysis of randomized block-coordinate descent methods. arXiv:1305.4723 (2013)
19.
go back to reference Necoara, I., Clipici, D.: Distributed coordinate descent methods for composite minimization. arXiv:1312.5302 (2013) Necoara, I., Clipici, D.: Distributed coordinate descent methods for composite minimization. arXiv:1312.5302 (2013)
20.
go back to reference Nesterov, Y.: Introductory Lectures on Convex Optimization. Applied Optimization, vol. 87. Kluwer, Boston (2004) Nesterov, Y.: Introductory Lectures on Convex Optimization. Applied Optimization, vol. 87. Kluwer, Boston (2004)
21.
22.
go back to reference Niu, F., Recht, B., Ré, C., Wright, S.J.: Hogwild!: a lock-free approach to parallelizing stochastic gradient descent. Adv. Neural Inf. Process. Syst. 24, 693–701 (2011) Niu, F., Recht, B., Ré, C., Wright, S.J.: Hogwild!: a lock-free approach to parallelizing stochastic gradient descent. Adv. Neural Inf. Process. Syst. 24, 693–701 (2011)
23.
go back to reference OpenMP Architecture Review Board: OpenMP Application Program Interface (2011) OpenMP Architecture Review Board: OpenMP Application Program Interface (2011)
24.
go back to reference Patrascu, A., Necoara, I.: Random coordinate descent methods for ℓ 0 regularized convex optimization. arXiv:1403.6622 (2014) Patrascu, A., Necoara, I.: Random coordinate descent methods for 0 regularized convex optimization. arXiv:1403.6622 (2014)
25.
go back to reference Richtárik, P., Takáč, M.: Efficient serial and parallel coordinate descent methods for huge-scale truss topology design. In: Operations Research Proceedings 2011, pp. 27–32. Springer, New York (2012) Richtárik, P., Takáč, M.: Efficient serial and parallel coordinate descent methods for huge-scale truss topology design. In: Operations Research Proceedings 2011, pp. 27–32. Springer, New York (2012)
26.
go back to reference Richtárik, P., Takáč, M.: Parallel coordinate descent methods for big data optimization. Mathematical Programming, DOI:10.1007/s10107-015-0901-6 (2012) Richtárik, P., Takáč, M.: Parallel coordinate descent methods for big data optimization. Mathematical Programming, DOI:10.1007/s10107-015-0901-6 (2012)
27.
go back to reference Richtárik, P., Takáč, M.: Distributed coordinate descent method for learning with big data. arXiv:1310.2059 (2013) Richtárik, P., Takáč, M.: Distributed coordinate descent method for learning with big data. arXiv:1310.2059 (2013)
28.
go back to reference Richtárik, P., Takáč, M.: On optimal probabilities in stochastic coordinate descent methods. arXiv:1310.3438 (2013) Richtárik, P., Takáč, M.: On optimal probabilities in stochastic coordinate descent methods. arXiv:1310.3438 (2013)
29.
go back to reference Richtárik, P., Takáč, M.: Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Math. Program. 144(1–2), 1–38 (2014)CrossRefMathSciNetMATH Richtárik, P., Takáč, M.: Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Math. Program. 144(1–2), 1–38 (2014)CrossRefMathSciNetMATH
30.
31.
go back to reference Salleh, N.S.M., Suliman, A., Ahmad, A.R.: Parallel execution of distributed SVM using MPI (CoDLib). In: Information Technology and Multimedia (ICIM), pp. 1–4. IEEE (2011) Salleh, N.S.M., Suliman, A., Ahmad, A.R.: Parallel execution of distributed SVM using MPI (CoDLib). In: Information Technology and Multimedia (ICIM), pp. 1–4. IEEE (2011)
32.
go back to reference Scherrer, C., Tewari, A., Halappanavar, M., Haglin, D.: Feature clustering for accelerating parallel coordinate descent. Adv. Neural Inf. Process. Syst. 25, 28–36 (2012) Scherrer, C., Tewari, A., Halappanavar, M., Haglin, D.: Feature clustering for accelerating parallel coordinate descent. Adv. Neural Inf. Process. Syst. 25, 28–36 (2012)
33.
go back to reference Shalev-Shwartz, S., Zhang, T.: Stochastic dual coordinate ascent methods for regularized loss. J. Mach. Learn. Res. 14(1), 567–599 (2013)MathSciNetMATH Shalev-Shwartz, S., Zhang, T.: Stochastic dual coordinate ascent methods for regularized loss. J. Mach. Learn. Res. 14(1), 567–599 (2013)MathSciNetMATH
34.
go back to reference Shalev-Shwartz, S., Singer, Y., Srebro, N., Cotter, A.: Pegasos: primal estimated sub-gradient solver for SVM. Math. Program. 127(1), 3–30 (2011)CrossRefMathSciNetMATH Shalev-Shwartz, S., Singer, Y., Srebro, N., Cotter, A.: Pegasos: primal estimated sub-gradient solver for SVM. Math. Program. 127(1), 3–30 (2011)CrossRefMathSciNetMATH
35.
go back to reference Snir, M., Otto, S., Huss-Lederman, S., Walker, D., Dongarra, J.: MPI-The Complete Reference, Volume 1: The MPI Core, 2nd (revised) edn. MIT Press, Cambridge, MA (1998) Snir, M., Otto, S., Huss-Lederman, S., Walker, D., Dongarra, J.: MPI-The Complete Reference, Volume 1: The MPI Core, 2nd (revised) edn. MIT Press, Cambridge, MA (1998)
36.
go back to reference Takáč, M., Bijral, A.S., Richtárik, P., Srebro, N.: Mini-batch primal and dual methods for SVMs. J. Mach. Learn. Res. W&CP 28, 1022–1030 (2013) Takáč, M., Bijral, A.S., Richtárik, P., Srebro, N.: Mini-batch primal and dual methods for SVMs. J. Mach. Learn. Res. W&CP 28, 1022–1030 (2013)
37.
go back to reference Tappenden, R., Richtárik, P., Gondzio, J: Inexact coordinate descent: complexity and preconditioning. arXiv:1304.5530 (2013) Tappenden, R., Richtárik, P., Gondzio, J: Inexact coordinate descent: complexity and preconditioning. arXiv:1304.5530 (2013)
38.
go back to reference Tappenden, R., Richtárik, P., Büke, B.: Separable approximations and decomposition methods for the augmented lagrangian. Optim. Methods Softw. arXiv:1308.6774 (2015) Doi:10.1080/10556788.2014.966824 Tappenden, R., Richtárik, P., Büke, B.: Separable approximations and decomposition methods for the augmented lagrangian. Optim. Methods Softw. arXiv:1308.6774 (2015) Doi:10.1080/10556788.2014.966824
40.
go back to reference Tseng, P.: Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. 109(3), 475–494 (2001)CrossRefMathSciNetMATH Tseng, P.: Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. 109(3), 475–494 (2001)CrossRefMathSciNetMATH
41.
go back to reference Tseng, P., Yun, S.: A coordinate gradient descent method for nonsmooth separable minimization. Math. Program. 117(1), 387–423 (2008)MathSciNet Tseng, P., Yun, S.: A coordinate gradient descent method for nonsmooth separable minimization. Math. Program. 117(1), 387–423 (2008)MathSciNet
42.
go back to reference Tseng, P., Yun, S.: Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization. J. Optim. Theory Appl. 140, 513–535 (2009)CrossRefMathSciNetMATH Tseng, P., Yun, S.: Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization. J. Optim. Theory Appl. 140, 513–535 (2009)CrossRefMathSciNetMATH
43.
go back to reference Zhao, P., Zhang, T.: Stochastic optimization with importance sampling. arXiv:1401.2753 (2014) Zhao, P., Zhang, T.: Stochastic optimization with importance sampling. arXiv:1401.2753 (2014)
Metadata
Title
Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
Authors
Jakub Mareček
Peter Richtárik
Martin Takáč
Copyright Year
2015
DOI
https://doi.org/10.1007/978-3-319-17689-5_11

Premium Partner