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.

Additional Metadata
Keywords Large-scale unconstrained optimization · Second order information · Shared-memory parallel implementation · Balanced coloring · Balanced, stratification · Matrix factorization
Persistent URL dx.doi.org/10.1007/s10589-018-00057-7, hdl.handle.net/1765/117990
Journal Computational Optimization & Applications
Citation
Kaya, K., Oztoprak, F., Birbil, S.I., Cemgil, A.T., Simsekli, U., Kuru, N., … Ozturk, K. (2019). A framework for parallel second order incremental optimization algorithms for solving partially separable problems. Computational Optimization & Applications, 72(3), 675–705. doi:10.1007/s10589-018-00057-7