Bilkent University
Department of Computer Engineering

---

CS 690 SEMINAR

 

LASGD: Locality-Aware Stochastic Gradient Descent for Matrix Completion

 

Selçuk Gülcan
PhD Student
(Supervisor: Prof. Dr. Cevdet Aykanat )
Computer Engineering Department
Bilkent University

Abstract: Matrix completion is used to model many real-life problems that require predicting or explaining the relationship between two classes of entities. Stochastic Gradient Descent (SGD) is a popular algorithm to complete large sparse matrices. Due to the stochastic memory access pattern of the algorithm, SGD uses the memory caches poorly. We propose Locality Aware SGD (LASGD), which effectively utilizes the caches by carefully arranging latent factor matrices in the memory and changing the nonzero update sequence without affecting the factor update order. LASGD relies on the observation that any topological ordering on the nonzero update graph, which captures the dependencies between nonzeros, can be used to get the same factor matrices. LASGD tries to find a topological ordering that can be processed faster by utilizing memory hierarchy effectively. Although LASGD is inherently an optimization over sequential SGD algorithm, we show that it can be extended to shared-memory parallel systems by adopting a 2D grid partitioning strategy. The experiments on a wide range of datasets show that LASGD attains 42% more throughput than SGD in the sequential setting and 33% more throughput than state-of-the-art shared-memory parallel algorithms.

 

DATE: 18 April 2022, Wednesday @ 15:50 Zoom