NDLI: Shared-memory and shared-nothing stochastic gradient descent algorithms for matrix completion

Content Provider	Springer Nature Link
Author	Makari, Faraz Teflioudi, Christina Gemulla, Rainer Haas, Peter Sismanis, Yannis
Copyright Year	2014
Abstract	We provide parallel algorithms for large-scale matrix completion on problems with millions of rows, millions of columns, and billions of revealed entries. We focus on in-memory algorithms that run either in a shared-memory environment on a powerful compute node or in a shared-nothing environment on a small cluster of commodity nodes; even very large problems can be handled effectively in these settings. Our ASGD, DSGD-MR, DSGD++, and CSGD algorithms are novel variants of the popular stochastic gradient descent (SGD) algorithm, with the latter three algorithms based on a new “stratified SGD” approach. All of the algorithms are cache-friendly and exploit thread-level parallelism, in-memory processing, and asynchronous communication. We investigate the performance of both new and existing algorithms via a theoretical complexity analysis and a set of large-scale experiments. The results show that CSGD is more scalable, and up to 60 % faster, than the best-performing alternative method in the shared-memory setting. DSGD++ is superior in terms of overall runtime, memory consumption, and scalability in the shared-nothing setting. For example, DSGD++ can solve a difficult matrix completion problem on a high-variance matrix with 10M rows, 1M columns, and 10B revealed entries in around 40 min on 16 compute nodes. In general, algorithms based on SGD appear to perform better than algorithms based on alternating minimizations, such as the PALS and DALS alternating least-squares algorithms.
Starting Page	493
Ending Page	523
Page Count	31
File Format	PDF
ISSN	02191377
Journal	Knowledge and Information Systems
Volume Number	42
Issue Number	3
e-ISSN	02193116
Language	English
Publisher	Springer London
Publisher Date	2014-02-15
Publisher Place	London
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Parallel and distributed matrix completion Low-rank matrix factorization Stochastic gradient descent Recommender systems Information Systems and Communication Service IT in Business
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence Information Systems Human-Computer Interaction Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A Fast Parallel Stochastic Gradient Method for Matrix Factorization in Shared Memory Systems

Parallel matrix factorization for recommender systems

A fast parallel SGD for matrix factorization in shared memory systems

Under consideration for publication in Knowledge and Information Systems Shared-Memory and Shared-Nothing Stochastic Gradient Descent Algorithms for Matrix Completion (2013)

Distributed Matrix Completion

Bounded matrix factorization for recommender system

Ternary Matrix Factorization: problem definitions and algorithms

1 distributed matrix completion.

Under consideration for publication in knowledge and information systems parallel matrix factorization for recommender systems (2013).

Shared-memory and shared-nothing stochastic gradient descent algorithms for matrix completion

Similar Documents

A Fast Parallel Stochastic Gradient Method for Matrix Factorization in Shared Memory Systems

Parallel matrix factorization for recommender systems

A fast parallel SGD for matrix factorization in shared memory systems

Under consideration for publication in Knowledge and Information Systems Shared-Memory and Shared-Nothing Stochastic Gradient Descent Algorithms for Matrix Completion (2013)

Distributed Matrix Completion

Bounded matrix factorization for recommender system

Ternary Matrix Factorization: problem definitions and algorithms

1 distributed matrix completion.

Under consideration for publication in knowledge and information systems parallel matrix factorization for recommender systems (2013).

Shared-memory and shared-nothing stochastic gradient descent algorithms for matrix completion