PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:1312.0193v2cs.DC

TL;DR

Large-scale matrix completion on commodity hardware is the target, but existing parallel approaches can wait for the slowest machine or incur costly network locking. NOMAD is a lock-free parallel algorithm using the owner-computes rule; empirical evaluation reports performance advantages over state-of-the-art competitors, especially on commodity-hardware clusters.

  • Problem

    Existing parallel approaches can wait for the slowest machine or incur costly network locking, while the paper targets large-scale matrix completion on limited commodity hardware.

    Source: §1 · p. 1, §4.1 · p. 5, §4.2 · p. 6

  • Method

    NOMAD is a parallel matrix-completion algorithm that uses the owner-computes rule to eliminate variable locking.

    Source: §1 · p. 1, §3.1 · p. 3

  • Results

    NOMAD outperforms state-of-the-art competitors in shared- and distributed-memory settings, with a more conspicuous advantage on commodity-hardware clusters.

    Source: §1 · p. 1, §6 · p. 11

  • Takeaways & Limitations

    For fixed-size datasets, NOMAD shows near-linear scaling up to 32 machines.

    Source: §6 · p. 11

    With a fixed-size dataset, increasing workers far enough can make communication costs overwhelm processing and cause slowdown.

    Source: §3.2 · p. 4

Abstract

from arXiv · show

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 an asynchronous algorithm, 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.

1. INTRODUCTION

NOMAD targets efficient distributed matrix completion on commodity hardware, where conventional HPC-oriented algorithms face slower, less reliable inter-machine networks. It combines decentralized, asynchronous, lock-free updates with serializability and outperforms state-of-the-art algorithms in the reported HPC settings.

1. INTRODUCTION

  • The target is large industrial-scale matrix completion on commodity hardware with limited computing power, memory, and interconnect speed.The paper notes that conventional HPC-oriented algorithms may require many machines on commodity hardware, increasing communication over slower, less reliable data-center networks.Source: §1 · p. 1
  • NOMAD uses asynchronous, non-blocking processor communication without bulk synchronization, with symmetric processors performing equal amounts of computation and communication.Its owner-computes design eliminates variable locks, and its asynchronous variable updates remain serializable: an equivalent ordering exists in a serial implementation.Source: §1 · p. 1
  • NOMAD performs well on commodity hardware and outperforms state-of-the-art algorithms on HPC clusters in both multi-core and distributed-memory settings.The paper also reports that NOMAD is significantly better than existing multi-core and multi-machine matrix-completion algorithms.Source: §1 · p. 1

2. BACKGROUND

The background formulates matrix completion as predicting unobserved ratings from low-rank user and item representations, then outlines ALS, coordinate descent, and SGD as optimization strategies. These methods differ in update order and approximation, while SGD uses sampled observations for cheaper updates.

2. BACKGROUND

  • Matrix completion predicts unobserved ratings by approximating the rating matrix with low-rank user and item embeddings whose inner products estimate ratings.The objective uses square loss on observed entries and weighted square-norm regularization; fixing either factor matrix decomposes the problem into independent convex subproblems.Source: §2 · p. 2

2.1 Alternating Least Squares

  • ALS updates user and item vectors in alternating order by solving least-squares problems with Newton updates.The update forms and inverts a Hessian.Source: §2.1 · p. 2

2.2 Coordinate Descent

  • Coordinate descent replaces the Hessian with a diagonal approximation and updates one vector component at a time.Cyclic Coordinate Descent and CCD++ use different component-update sequences; CCD++ can update more efficiently by maintaining a residual matrix.Source: §2.2 · p. 2

2.3 Stochastic Gradient Descent

  • Figure 1 distinguishes updated nodes in black, read nodes in gray, and untouched nodes in white across ALS, coordinate descent, and SGD.For ALS and coordinate descent, updating a user vector requires access to the item vectors for all items rated by that user.Source: Figure 1 · p. 3
  • SGD samples an observed user–item pair and updates from its gradient, an unbiased estimate of the full-objective gradient.Evaluating the sampled gradient is significantly cheaper than evaluating the full gradient.Source: §2.3 · pp. 2–3

3. NOMAD

NOMAD uses SGD to support fine-grained parallelism, keeping user parameters with fixed workers while asynchronously transferring item-parameter ownership. Its design combines non-blocking worker communication with workload balancing and scaling strategies.

3. NOMAD

  • SGD updates need only one randomly selected item parameter for each user update, enabling more simultaneous parallel updates than ALS or coordinate descent.The paper uses SGD as NOMAD’s optimization scheme because of this finer-grained parallelism.Source: §3 · p. 3

3.1 Description

  • User parameters stay with their assigned workers, while item parameters move between workers; each item is updated only by its current owner, avoiding locks.Workers process local ratings for an item, then send its updated parameter pair asynchronously and without blocking to a uniformly sampled worker; workers are symmetric.Source: §3.1 · p. 3

3.2 Complexity Analysis

  • With fixed work per worker, NOMAD scales linearly; with fixed data, increasing workers eventually slows it as communication outweighs processing.Per-worker space is O((mk + nk + |Ω|)/p); under the stated constant-processing and communication assumptions, total communication is O(nkp).Source: §3.2 · p. 4

3.3 Dynamic Load Balancing

  • Workers can favor recipients with shorter queues by including queue size in messages, assigning slower workers less work with one integer of overhead per message.The motivation is variation in ratings per item and in worker processing rates.Source: §3.3 · p. 4

3.4 Hybrid Architecture

  • In the hybrid architecture, two additional threads per machine handle network sending and receiving, while received item-parameter pairs circulate among local threads.A uniformly random permutation sets the circulation order; circulating a variable more than once was not found to improve convergence.Source: §3.4 · pp. 4–5

3.5 Implementation Details

  • The implementation batches a fixed number of item-parameter pairs for network transmission and uses TBB’s concurrent queue, which scales almost linearly despite not being technically lock-free.Careful cache-line alignment exploits memory locality and avoids cache ping-pong, yielding near-linear multi-threaded scaling.Source: §3.5 · p. 5

4. RELATED WORK

The section contrasts bulk-synchronous and asynchronous approaches to distributed matrix completion, positioning NOMAD through fine-grained partitioning, lock-free updates, and serializability.

4.1 Map-Reduce and Friends

  • DSGD partitions user and item indices across machines, processes disjoint matrix blocks, and redistributes item parameters at synchronization points.Workers process their active areas before item-parameter columns are exchanged and the active areas change.Source: §4.1 · p. 5, Figure 3 · p. 5
  • Bulk-synchronous methods separate computation from communication and wait for the slowest worker; DSGD++ overlaps transfers, while FPSGD** uses task-managed partitions.FPSGD**'s extension to distributed memory is unclear in the cited discussion.Source: §4.1 · p. 5
  • NOMAD outperforms DSGD, DSGD++, and FPSGD**; its smaller blocks support flexible processor assignment and dynamic load balancing.NOMAD partitions the matrix into p × n blocks, compared with p × p for DSGD and p′ × p′ for FPSGD**.Source: §4.1 · pp. 5–6

4.2 Asynchronous Algorithms

  • GraphLab's network read-locks can delay updates for popular users, while NOMAD performs significantly better and avoids those locks.NOMAD's finer-grained partitioning also avoids dependence on a complicated scheduling mechanism.Source: §4.2 · p. 6

4.3 Numerical Linear Algebra

  • Asynchronous fixed-point updates overwrite variables as they are computed; unlike Hogwild and ASGD, NOMAD is serializable and empirically converges faster.The cited discussion describes asynchronous fixed-point methods as potentially lacking an equivalent serial update ordering.Source: §4.3 · p. 6
  • The cited distributed conjugate-gradient method uses non-blocking MPI operations but still synchronizes at every iteration.Source: §4.3 · p. 6

4.4 Discussion

  • Among the distributed-memory algorithms discussed, NOMAD alone combines asynchronous execution with lock-free updates; GraphLab's ALS is asynchronous but uses locks.GraphLab therefore relies on a complex scheduler to reduce the side effects of locking.Source: §4.4 · pp. 6–7

5. EXPERIMENTS

Experiments compare NOMAD with established matrix-completion algorithms across shared-memory, distributed-memory, commodity-hardware, and growing-data settings. NOMAD generally scales well and performs competitively or better, with outcomes varying by dataset and communication conditions.

5.1 Experimental Setup

  • The evaluation uses shared training and test partitions and common initial parameters, but different optimizers can converge to different solutions because the objective is non-convex.The authors did not test every combination of initialization, rating order, and step-size schedule, though they believe the overall trends are unaffected.Source: §5.1 · p. 7, §5 · p. 7

5.2 Scaling in Number of Cores

  • At 30 cores, NOMAD reaches RMSE 0.914 on Netflix versus 0.916 for the other methods, while Yahoo! Music favors FPSGD** slightly at RMSE 21.894 versus 21.853.NOMAD initially converges faster on both datasets; it also outperforms on Hugewiki, where the difference is smaller.Source: §5.2 · p. 8, Figure 5 · p. 9
  • As cores increase to 30, per-core throughput falls to about 50% on Yahoo! Music and Hugewiki, while Netflix throughput remains almost constant.The authors attribute the decreases mainly to cache-locality effects; convergence speeds up with more cores on Yahoo! Music.Source: §5.2 · p. 8, Figure 6 · p. 8

5.3 Scaling as a Fixed Dataset is Distributed Across Workers

  • With a fixed dataset distributed across machines, NOMAD shows dataset-dependent scaling: super-linear on some Netflix and Yahoo! Music configurations and linear on Hugewiki.Yahoo! Music shows super-linear speedup across configurations, with the highest speedup at 16 machines; Hugewiki shows linear scaling in every configuration.Source: §5.3 · p. 9, Figure 7 · p. 9, Figure 9 · p. 10

5.4 Scaling on Commodity Hardware

  • On commodity hardware, NOMAD outperforms the other algorithms despite using fewer computation cores, with faster convergence to better solutions on Netflix and Hugewiki.On Yahoo! Music, the algorithms perform similarly on the HPC cluster, while NOMAD performs better on commodity hardware.Source: §5.4 · p. 10, Figure 11 · p. 11

5.5 Scaling as both Dataset Size and Number of Machines Grows

  • As dataset size and machine count grow, NOMAD outperforms DSGD, DSGD++, and CCD++; its comparative advantage increases with problem scale.DSGD++ is competitive at small scale, but NOMAD scales better as the problem grows.Source: §5.5 · p. 11, Figure 11 · p. 11

6. CONCLUSION AND FUTURE WORK

The paper concludes that NOMAD scales near-linearly in the tested single-machine and fixed-dataset distributed settings, and outperforms state-of-the-art competitors. It also notes possible extensions beyond matrix completion and ongoing investigation of LDA.

6. CONCLUSION AND FUTURE WORK

  • NOMAD shows near-linear scaling up to 30 threads on one machine and up to 32 machines for a fixed-size dataset.The conclusion also reports superior performance against state-of-the-art competitors in shared- and distributed-memory settings, especially on commodity hardware.Source: §6 · p. 11
  • The authors say NOMAD's ideas can extend beyond matrix completion when the objective function has the specified structure.The supplied passage does not specify that structure further.Source: §6 · p. 11
  • The authors are investigating whether NOMAD can be used for Latent Dirichlet Allocation with a collapsed Gibbs sampler.They identify variable normalization as an additional complication in LDA.Source: §6 · p. 11

A. EFFECT OF THE REGULARIZATION PARAMETER

Regularization affects NOMAD's convergence behavior differently across datasets: higher values speed convergence on Netflix, while other datasets are less sensitive.

A. EFFECT OF THE REGULARIZATION PARAMETER

  • On Netflix, NOMAD converges notably faster with higher regularization λ, while convergence speed on other datasets is not very sensitive to λ.For non-optimal λ, Netflix test RMSE increases from the initial solution as the model overfits or underfits, although NOMAD reliably converges in all tested cases.Source: A. EFFECT OF THE REGULARIZATION… · p. 13

B. EFFECT OF THE LATENT DIMENSION

Latent dimension k trades off convergence speed and model richness, with dataset-dependent overfitting behavior; NOMAD converges reliably across the tested settings.

B. EFFECT OF THE LATENT DIMENSION

  • Smaller k generally speeds convergence because SGD update cost is linear in k, while larger k expands model capacity and can risk overfitting.On Hugewiki, small k suffices to fit the training data, and test RMSE suffers from overfitting at higher k; NOMAD converges reliably in all cases.Source: B. EFFECT OF THE LATENT DIMENSION · p. 13

C. SCALINGONCOMMODITYHARDWARE

On an AWS commodity cluster, NOMAD’s scaling was examined across 1–32 machines. With equal computational power per setting, it showed linear to super-linear scaling up to 32 machines across the datasets, though update throughput slowed on Yahoo! Music.

C. SCALINGONCOMMODITYHARDWARE

  • The experiment varied the cluster from 1 to 32 AWS m1.xlarge machines, each with a quad-core Intel Xeon E5430 and 15 GB RAM.Source: C. SCALINGONCOMMODITYHARDWARE · p. 13
  • With equal computational power, NOMAD showed linear to super-linear scaling up to 32 machines on every dataset.This compares convergence speed across settings with the same total computational power.Source: C. SCALINGONCOMMODITYHARDWARE · p. 13
  • More machines produced faster convergence as updated information was exchanged more frequently.The reported pattern matched the earlier results in Figures 19, 10, and 9.Source: C. SCALINGONCOMMODITYHARDWARE · p. 13
  • Update throughput scaled linearly on Netflix and Hugewiki, but slowed on Yahoo! Music because of extreme data sparsity.Source: C. SCALINGONCOMMODITYHARDWARE · p. 13

D. TEST RMSE AS A FUNCTION OF THE NUMBER OF UPDATES IN HPC CLUSTER

This section presents HPC-cluster plots of test RMSE against update count, covering both single-machine multithreading and multi-machine distributed-memory experiments.

D. TEST RMSE AS A FUNCTION OF THE NUMBER OF UPDATES IN HPC CLUSTER

E. COMPARISON OF ALGORITHMS FOR DIFFERENT VALUES OF THE REGULARIZATION PARAMETER

NOMAD and DSGD behaved similarly as regularization changed, while CCD++ responded differently; NOMAD remained competitive with whichever alternative performed better.

E. COMPARISON OF ALGORITHMS FOR DIFFERENT VALUES OF THE REGULARIZATION PARAMETER

F. COMPARISON WITH GRAPHLAB

NOMAD converged orders of magnitude faster than GraphLab and reached a better solution in the reported settings. The comparison was constrained by GraphLab’s available algorithms, memory limits, and an extrapolated biassgd result.

F. COMPARISON WITH GRAPHLAB

  • Only GraphLab’s ALS was suitable for the paper’s objective; its SGD implementation did not converge, and biassgd used a different model.The authors therefore describe biassgd as not directly comparable to NOMAD as an optimization algorithm.Source: F. COMPARISON WITH GRAPHLAB · p. 13
  • GraphLab could not run on Hugewiki in any setting despite nfibers tuning to avoid out-of-memory problems.The HPC machines had 32 GB RAM each, and the multi-machine experiments used 32 machines.Source: F. COMPARISON WITH GRAPHLAB · p. 13
  • NOMAD converged orders of magnitude faster than GraphLab and reached a better solution in the reported single-machine and cluster settings.The comparison covers a 30-core single machine, an HPC cluster, and a commodity hardware cluster.Source: F. COMPARISON WITH GRAPHLAB · p. 13, Figure 21 · p. 18, Figure 22 · p. 18
  • On commodity hardware, GraphLab biassgd crashed above 16 machines, so its Figure 23 comparison assumes linear scaling to 32; NOMAD was orders of magnitude faster and reached a better solution.Source: F. COMPARISON WITH GRAPHLAB · p. 17, Figure 23 · p. 18
Loading 1312.0193v2…