A framework for parallel second order incremental optimization algorithms for solving partially separable problems
Küçük Resim Yok
Tarih
2019
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Springer
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
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.
Açıklama
Anahtar Kelimeler
Large-Scale Unconstrained Optimization, Second Order İnformation, Shared-Memory Parallel İmplementation, Balanced Coloring, Balanced Stratification, Matrix Factorization
Kaynak
Computational Optimization and Applications
WoS Q Değeri
Q1
Scopus Q Değeri
Q1
Cilt
72
Sayı
3
