NOMAD: Nonlocking, stOchastic Multi-machine algorithm for Asynchronous and Decentralized matrix completion

By Hyokun Yun, Hsiang-Fu Yu, Cho-Jui Hsieh, S. V. N. Vishwanathan, Inderjit S. Dhillon. 2013

123 citations recorded by the source corpus.

We develop an efficient parallel distributed algorithm for matrix completion, named NOMAD (Non-locking, stOchastic Multi-machine algorithm for Asynchronous and Decentralized matrix completion). NOMAD is a decentralized algorithm with non-blocking communication between processors. One of the key features of NOMAD is that the ownership of a variable is asynchronously transferred between processors in a decentralized fashion. As a consequence it is a lock-free parallel algorithm. In spite of being asynchronous, the variable updates of NOMAD are serializable, that is, there is an equivalent update ordering in a serial implementation. 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.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization (2015, methodology): “…witnessed in many applications such as deep neural network [Dean et al., 2012, Paine et al., 2013, Zhang et al., 2014, Li et al., 2014a], matrix completion [Niu et al., 2011, Petroni and Querzoni, 2014, Yun et al., 2013], SVM [Niu et al., 2011], and solving linear equations [Liu et al., 2014b].”
Perturbed Iterate Analysis for Asynchronous Stochastic Optimization (2015, background): “A large body of recent work has demonstrated that near-linear speedups are achievable, in theory and practice, on many common machine learning tasks [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 13, 16].”
A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (2016, background): “One of core theoretical questions is how much speedup (or benefit) the asynchronous parallelization can bring us.”
Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go? (2018, background): “, 2016) and matrix completion (Recht et al., 2011; Yun et al., 2014; Petroni & Querzoni, 2014), to training deep neural networks (Dean et al.”
To Index or Not to Index: Optimizing Exact Maximum Inner Product Search (2017, methodology): “We use the regularization parameter and hyperparameter settings reported in [40] as the starting point for a grid search for the optimal test RMSE.”
A Harmonic Extension Approach for Collaborative Ranking (2016, result): “An important direction is to further improve the efficiency of the algorithm to be comparable with recent large-scale matrix completion methods [22, 25].”
Stochastic Gradient Made Stable: A Manifold Propagation Approach for Large-Scale Optimization (2015, methodology): “a, the space and time complexities become the critical limiting factor in building a machine learning model. In such scenarios, stochastic (sub)gradient descent (SGD) [2], [6], [9], [13], [15], [18], [24] is a favored method used by many theorist and practitioners. The most attractive trait of SGD i”
Gradient Diversity Empowers Distributed Learning (2017, background): “…signiﬁcant traction with a large body of recent work establishing near-optimal speedup gains on both convex and nonconvex objectives [35, 15, 9, 47, 29, 20, 12, 4], and several state-of-the-art publicly available (distributed) machine learning frameworks, such as Tensorﬂow [1], MXNet [5], and…”