Parallel Stochastic Gradient Algorithms for Large-Scale Matrix Completion

Benjamin Recht (brechtcs.wisc.edu)
Christopher Re (chrisrecs.wisc.edu)

Abstract: This paper develops Jellyfish, an algorithm for solving data-processing problems with matrix-valued decision variables regularized to have low rank. Particular examples of problems solvable by Jellyfish include matrix completion problems and least-squares problems regularized by the nuclear norm or the max-norm. Jellyfish implements a projected incremental gradient method with a biased, random ordering of the increments. This biased ordering allows for a parallel implementation that admits a speed-up nearly proportional to the number of processors. On large-scale matrix completion tasks, Jellyfish is orders of magnitude more efficient than existing codes. For example, on the Netflix Prize data set, prior art computes rating predictions in approximately 4 hours, while Jellyfish solves the same problem in under 3 minutes.

Keywords: Matrix completion, Incremental gradient methods, Parallel computing, Multicore

Category 1: Nonlinear Optimization

Category 2: Applications -- Science and Engineering (Data-Mining )

Category 3: Optimization Software and Modeling Systems

Citation:

Download: [PDF]

Entry Submitted: 04/26/2011
Entry Accepted: 04/26/2011
Entry Last Modified: 03/22/2013

Modify/Update this entry