Skip to main navigation Skip to search Skip to main content

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

  • Kamer Kaya
  • , Figen Öztoprak
  • , İlker Birbil
  • , A. Taylan Cemgil
  • , Umut Şimşekli
  • , Nurdan Kuru
  • , Hazal Koptagel
  • , M. Kaan Öztürk

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original languageEnglish
Pages (from-to)675-705
Number of pages31
JournalComputational Optimization and Applications
Volume72
Issue number3
DOIs
StatePublished - Apr 15 2019

Keywords

  • Balanced coloring
  • Balanced stratification
  • Large-scale unconstrained optimization
  • Matrix factorization
  • Second order information
  • Shared-memory parallel implementation

Fingerprint

Dive into the research topics of 'A framework for parallel second order incremental optimization algorithms for solving partially separable problems'. Together they form a unique fingerprint.

Cite this