A framework for parallel second order incremental optimization algorithms for solving partially separable problems

Kaya, Kamer and Öztoprak, Figen and Birbil, Ş. İlker and Cemgil, A. Taylan and Şimşekli, Umut and Kuru, Nurdan and Koptagel, Hazal and Öztürk, Mehmet Kaan (2019) A framework for parallel second order incremental optimization algorithms for solving partially separable problems. Computational Optimization and Applications, 72 (3). pp. 675-705. ISSN 0926-6003 (Print) 1573-2894 (Online)

Full text not available from this repository.

Official URL: http://dx.doi.org/10.1007/s10589-018-00057-7


We propose Hessian Approximated Multiple Subsets Iteration (HAMSI), which is a generic second order incremental algorithm for solving large-scale partially separable convex and nonconvex optimization problems. The algorithm is based on a local quadratic approximation, and hence, allows incorporating curvature information to speed-up the convergence. HAMSI is inherently parallel and it scales nicely with the number of processors. We prove the convergence properties of our algorithm when the subset selection step is deterministic. Combined with techniques for effectively utilizing modern parallel computer architectures, we illustrate that a particular implementation of the proposed method based on L-BFGS updates converges more rapidly than a parallel gradient descent when both methods are used to solve large-scale matrix factorization problems. This performance gain comes only at the expense of using memory that scales linearly with the total size of the optimization variables. We conclude that HAMSI may be considered as a viable alternative in many large scale problems, where first order methods based on variants of gradient descent are applicable.

Item Type:Article
Uncontrolled Keywords:Large-scale unconstrained optimization; Second order information; Shared-memory parallel implementation; Balanced coloring; Balanced stratification; Matrix factorization
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:37388
Deposited By:Kamer Kaya
Deposited On:26 Aug 2019 22:32
Last Modified:26 Aug 2019 22:32

Repository Staff Only: item control page