Optimization Online


Parallel Stochastic Gradient Algorithms for Large-Scale Matrix Completion

Benjamin Recht (brecht***at***cs.wisc.edu)
Christopher Re (chrisre***at***cs.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


Download: [PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society