2011 · 619 citations · 29 references
ComputingComputer ScienceDistributed SystemsMachine LearningParallel ComputingDistributed ComputingDistributed Data ProcessingMatrix ComputationMatrix FactorizationScalable Algorithm DesignScalable Machine LearningApproximation TheoryDistributed Linear AlgebraDistributed Matrix FactorizationLoss MinimizationScalabilitySparse Matrix ComputationStochastic ApproximationStochastic Gradient Descent
We provide a novel algorithm to approximately factor large matrices with millions of rows, millions of columns, and billions of nonzero elements. Our approach rests on stochastic gradient descent (SGD), an iterative stochastic optimization algorithm. We first develop a novel "stratified" SGD variant (SSGD) that applies to general loss-minimization problems in which the loss function can be expressed as a weighted sum of "stratum losses." We establish sufficient conditions for convergence of SSGD using results from stochastic approximation theory and regenerative process theory. We then specialize SSGD to obtain a new matrix-factorization algorithm, called DSGD, that can be fully distributed and run on web-scale datasets using, e.g., MapReduce. DSGD can handle a wide variety of matrix factorizations. We describe the practical techniques used to optimize performance in our DSGD implementation. Experiments suggest that DSGD converges significantly faster and has better scalability properties than alternative algorithms.
29
Pattern Recognition and Machine Learning
Journal of Electronic Imaging · 2007 · 22.1K citations
Sanjay Ghemawat · Communications of the ACM · 2008 · 18.5K citations · Full text
Learning the parts of objects by non-negative matrix factorization
Daniel D. Lee, H. Sebastian Seung · Nature · 1999 · 14.1K citations
Matrix Factorization Techniques for Recommender Systems
Yehuda Koren, Robert Bell, Chris Volinsky · Computer · 2009 · 11.7K citations
A Limited Memory Algorithm for Bound Constrained Optimization
Richard H. Byrd, Peihuang Lu, Jorge Nocedal et al. · SIAM Journal on Scientific Computing · 1995 · 6.2K citations