Large-scale matrix factorization with distributed stochastic gradient descent
The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Abstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Book Review: Pattern Recognition and Machine Learning
Nasrabadi, N. M. (2007) · Journal of Electronic Imaging · doi:10.1117/1.2819119 · Cited by 22,066
MapReduce: simplified data processing on large clusters
Dean, J., & Ghemawat, S. (2008) · Communications of the ACM · doi:10.1145/1327452.1327492 · Cited by 18,476
Learning the parts of objects by non-negative matrix factorization
Lee, D. D., & Seung, H. S. (1999) · Nature · doi:10.1038/44565 · Cited by 13,868
Matrix Factorization Techniques for Recommender Systems
Koren, Y., Bell, R., & Volinsky, C. (2009) · Computer · doi:10.1109/mc.2009.263 · Cited by 11,673
ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION
Lee, D. D., & Seung, H. S. (2000) · neural information processing systems · Cited by 9,875
(2006) · Springer eBooks · Cited by 8,123
A Limited Memory Algorithm for Bound Constrained Optimization
Byrd, R. H., Lu, P., Nocedal, J., & Zhu, C. (1995) · SIAM Journal on Scientific Computing · doi:10.1137/0916069 · Cited by 6,221
(2010) · Cited by 4,411
Probabilistic Latent Semantic Indexing
Hofmann, T. (2017) · ACM SIGIR Forum · doi:10.1145/3130348.3130370 · Cited by 3,988
Probabilistic latent semantic indexing
Hofmann, T. (1999) · Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/312624.312649 · Cited by 3,976
Applied Probability and Queues
Dave, U. (1987) · Journal of the Operational Research Society · doi:10.1057/jors.1987.184 · Cited by 2,704
A Course in Probability Theory
(1974) · Elsevier eBooks · doi:10.1016/c2009-0-22097-6 · Cited by 2,668
Applied Probability and Queues
Asmussen, S. (2003) · Springer eBooks · doi:10.1007/b97236 · Cited by 2,445
Probabilistic Latent Semantic Analysis
Hofmann, T. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.6705 · Cited by 2,047
Mellor, D. H. (1981) · Cited by 1,981
Stochastic Approximation and Recursive Algorithms and Applications
(2003) · Stochastic Modelling and Applied Probability · doi:10.1007/b97441 · Cited by 1,838
Google news personalization: scalable online collaborative filtering
Das, A. S., Datar, M., Garg, A., & Rajaram, S. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242610 · Cited by 1,511
Latent semantic models for collaborative filtering
Hofmann, T. (2004) · ACM Transactions on Information Systems · doi:10.1145/963770.963774 · Cited by 1,378
Bennett, J. R., & Lanning, S. (2007) · Cited by 1,216
Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
Niu, F., Recht, B., Re, C., & Wright, S. J. (2011) · arXiv · doi:10.48550/arxiv.1106.5730 · Cited by 1,211 · cited 1×
“At such massive scales, parallel [6, 7] and distributed [1, 8, 5, 9, 10] algorithms for matrix factorization are essential to achieving reasonable performance.”
BackgroundThe Tradeoffs of Large-Scale Learning
Bottou, L., & Bousquet, O. (2011) · Optimization for Machine Learning · doi:10.7551/mitpress/8996.003.0015 · Cited by 1,128
Parallelized Stochastic Gradient Descent
Zinkevich, M., Weimer, M., Li, L., & Smola, A. J. (2010) · Cited by 1,124
Stochastic Simulation: Algorithms and Analysis
Asmussen, S., & Glynn, P. W. (2007) · Stochastic Modelling and Applied Probability · doi:10.1007/978-0-387-69033-9 · Cited by 1,121
Probability Theory: Independence, Interchangeability, Martingales
Lund, R. B., Chow, Y. S., & Teicher, H. (1998) · Journal of the American Statistical Association · doi:10.2307/2670078 · Cited by 1,066
Information Science and Statistics
Andersen, E. B. (1986) · COMPSTAT · doi:10.1007/978-3-642-46890-2_1 · Cited by 899
Large-Scale Parallel Collaborative Filtering for the Netflix Prize
Zhou, Y., Wilkinson, D., Schreiber, R., & Pan, R. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-68880-8_32 · Cited by 700
The performance of MapReduce: an in-depth study
Jiang, D., Ooi, B. C., Shi, L., & Wu, S. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920903 · Cited by 392
Distributed Training Strategies for the Structured Perceptron
McDonald, R., Hall, K., & Mann, G. (2010) · North American Chapter of the Association for Computational Linguistics · Cited by 335
Efficient Large-Scale Distributed Training of Conditional Maximum Entropy Models
McDonald, R., Mohri, M., Silberman, N., Walker, D. L., & Mann, G. (2009) · neural information processing systems · Cited by 310
Parallel stochastic gradient algorithms for large-scale matrix completion
Recht, B., & Ré, C. (2013) · Mathematical Programming Computation · doi:10.1007/s12532-013-0053-8 · Cited by 300
Algorithms, Initializations, and Convergence for the Nonnegative Matrix FactorizationPreprint
Langville, A. N., Meyer, C. D., Albright, R., Cox, J., & Duling, D. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1407.7299 · Cited by 175
Ricardo: integrating R and Hadoop
Das, S., Sismanis, Y., Beyer, K. S., Gemulla, R., Haas, P. J., & McPherson, J. (2010) · Proceedings of the 2010 ACM SIGMOD International Conference on Management of data · doi:10.1145/1807167.1807275 · Cited by 164
Self-citationA Unified View of Matrix Factorization Models
Singh, A. P., & Gordon, G. J. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-87481-2_24 · Cited by 150
Teflioudi, C., Manshadi, F. M., & Gemulla, R. (2012) · Proceedings · doi:10.1109/icdm.2012.120 · Cited by 103
Self-citationA linear ensemble of individual and blended models for music rating prediction
Chen, P.-L., Tsai, C.-T., Chen, Y.-N., Chou, K.-C., Li, C., Tsai, C.-H., Wu, K.-W., Chou, Y.-C., Li, C., Lin, W.-S., et al. (2011) · Knowledge Discovery and Data Mining · Cited by 52
MapReduce/Bigtable for Distributed Optimization
Hall, K., Gilpin, S., & Mann, G. (2010) · Cited by 44
Cited by
(2017) · neural information processing systems · Cited by 1,413
Machine learning on big data: Opportunities and challenges
Zhou, L., Pan, S., Wang, J., & Vasilakos, A. V. (2017) · Neurocomputing · doi:10.1016/j.neucom.2017.01.026 · Cited by 1,228
Fast Matrix Factorization for Online Recommendation with Implicit Feedback
He, X., Zhang, H., Kan, M.-Y., & Chua, T.-S. (2016) · Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval · doi:10.1145/2911451.2911489 · Cited by 988
Efficient mini-batch training for stochastic optimization
Li, M., Zhang, T., Chen, Y., & Smola, A. J. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623612 · Cited by 742
FISM: factored item similarity models for top-N recommender systems
Kabbur, S., Ning, X., & Karypis, G. (2013) · Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2487575.2487589 · Cited by 651
Metadata
- Authors
- Gemulla, R., Nijkamp, E., Haas, P. J., & Sismanis, Y.
- Venue
- Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining
- Publisher
- ACM
- Published
- 2011-08-21
- Pages
- 69-77
- OpenAlex
- W1980147176
- Cited by
- 589
- References
- 36
- FWCI
- 27.64
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.