Abstract: We develop an efficient parallel distributed algorithm for matrix completion, named NOMAD (Non-locking, stOchastic Multi-machine algorithm for Asynchronous and Decentralized matrix completion). In our algorithm, the ownership of a variable is asynchronously transferred between processors in a decentralized fashion. Due to its lock-free and asynchronous nature, NOMAD outperforms synchronous algorithms which require explicit bulk synchronization after every iteration: our extensive empirical evaluation shows that not only does our algorithm perform well in distributed setting on commodity hardware, but also outperforms state-of-the-art algorithms on a HPC cluster both in multi-core and distributed memory settings.
- NOMAD: Non-locking, stOchastic Multi-machine algorithm for Asynchronous and Decentralized matrix completion (pdf, software)
H. Yun, H. Yu, C. Hsieh, S. Vishwanathan, I. Dhillon.
In International Conference on Very Large Data Bases (VLDB), pp. 975-986, July 2014.