Constrained Tensor Factorization with Accelerated AO-ADMM

Shaden Smith, Alec Beri, George Karypis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

Low-rank sparse tensor factorization is a populartool for analyzing multi-way data and is used in domainssuch as recommender systems, precision healthcare, and cybersecurity.Imposing constraints on a factorization, such asnon-negativity or sparsity, is a natural way of encoding priorknowledge of the multi-way data. While constrained factorizationsare useful for practitioners, they can greatly increasefactorization time due to slower convergence and computationaloverheads. Recently, a hybrid of alternating optimization andalternating direction method of multipliers (AO-ADMM) wasshown to have both a high convergence rate and the ability tonaturally incorporate a variety of popular constraints. In thiswork, we present a parallelization strategy and two approachesfor accelerating AO-ADMM. By redefining the convergencecriteria of the inner ADMM iterations, we are able to splitthe data in a way that not only accelerates the per-iterationconvergence, but also speeds up the execution of the ADMMiterations due to efficient use of cache resources. Secondly,we develop a method of exploiting dynamic sparsity in thefactors to speed up tensor-matrix kernels. These combinedadvancements achieve up to 8 speedup over the state-of-the art on a variety of real-world sparse tensors.

Original languageEnglish (US)
Title of host publicationProceedings - 46th International Conference on Parallel Processing, ICPP 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages111-120
Number of pages10
ISBN (Electronic)9781538610428
DOIs
StatePublished - Sep 1 2017
Event46th International Conference on Parallel Processing, ICPP 2017 - Bristol, United Kingdom
Duration: Aug 14 2017Aug 17 2017

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Other

Other46th International Conference on Parallel Processing, ICPP 2017
Country/TerritoryUnited Kingdom
CityBristol
Period8/14/178/17/17

Bibliographical note

Funding Information:
ACKNOWLEDGMENTS We thank the anonymous reviewers for insightful comments and suggestions for future work. This work was supported in part by NSF (IIS-1460620, IIS-0905220, OCI-1048018, CNS-1162405, IIS-1247632, IIP-1414153, IIS-1447788), Army Research Office (W911NF-14-1-0316), a University of Minnesota Doctoral Dissertation Fellowship, Intel Software and Services Group, and the Digital Technology Center at the University of Minnesota. Access to research and computing facilities was provided by the Digital Technology Center and the Minnesota Supercomputing

Funding Information:
Institute. This research used resources of the National Energy Research Scientific Computing Center, a DOE Office of Science User Facility supported by the Office of Science of the U.S. Department of Energy under Contract No. DE-AC02-05CH11231.

Publisher Copyright:
© 2017 IEEE.

Fingerprint

Dive into the research topics of 'Constrained Tensor Factorization with Accelerated AO-ADMM'. Together they form a unique fingerprint.

Cite this