Hogwild notes

Hogwild A Lock-Free Approach to Parallelizing Gradient Descent

Blog Post


  1. Focus / Problem to be solved
    1. how to reduce the lock overhead in SGD algorithms
  2. Importance
    1. machine learning tasks need SGD
    2. locking and synchronization are destroying the performance of SGD algorithms
  3. Method
    1. Key Observation
      1. a lot of updates are sparse, and there are no significant contention
        1. “The key observation that underlies our lock-free approach is that the natural cost functions associated with many machine learning problems of interest are sparse in the sense that |E| and n are both very large but each individual fe acts only on a very small number of components of x.”
    2. Algorithm
      1. sampling with replacement ?
      2. Parallelization
        1. each processor executes Algorithm 1 (SGD)
        2. synchronize after each epoch
      3. Atomic instructions
        1. Still use atomic instructions, just not locks
  4. Context (Related Work)
  5. Results
    1. Applications
      1. Sparse SVM
      2. Matrix Completion
      3. Graph Cuts
    2. Speedup
      1. achieves 2-8x speedup on 10 core machine
        1. work particularly well for MC (matrix completion), GraphCuts has the weakest performance
    3. Setup
      1. 24GB, 2 sockets with 6 cores each (never used more than 2GB memory)
    4. Comparisons
      1. Hogwild (no locking)
      2. AIG (fine grain locking)
      3. RR
        1. performs well when gradient computation takes most of the time(less synchronization overhead)
  6. Unique contributions
    1. Empirical
    2. Theoretical (will converge at 1/k convergence rate)
      1. assumes that the optimization space is convex
      2. 1 / k converge rate (it always converge)
  7. Questions
    1. In general, what how to determine if hogwild / asynchronous SGD is OK?
      1. some measurement of Sparsity
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s