Taming the Wild: A Unified Analysis of HOGWILD!-Style Algorithms
Stochastic gradient descent (SGD) is a ubiquitous algorithm for a variety of machine learning problems. Researchers and industry have developed several techniques to optimize SGD's runtime performance, including asynchronous execution and reduced precision. Our main result is a martingale-based analysis that enables us to capture the rich noise models that may arise from such techniques. Specifically, we use our new analysis in three ways: (1) we derive convergence rates for the convex case (HOGWILD!) with relaxed assumptions on the sparsity of the problem; (2) we analyze asynchronous SGD algorithms for non-convex matrix problems including matrix completion; and (3) we design and analyze an asynchronous SGD algorithm, called BUCKWILD!, that uses lower-precision arithmetic. We show experimentally that our algorithms run efficiently for a variety of problems on modern hardware.
This paper is an essentially theoretical contribution regarding convergence rates for the so-called "Hogwild"-style algorithms for stochastic gradient descent.In these algorithms, the gradient step is produces asynchronously over different chunks of the dataset in parallel, with results updating current weights as they are completed, independent of other parallel updates.Previously, demonstrating theoretical convergence has been difficult and somewhat brittle.In this paper, the authors present an analysis framework that is able to extend convergence results to a variety of specializations/generalizations of the algorithm.They show that one of their proven variants, "Buckwild" provides significant real-world speedups by using lower precision arithmetic to compute the gradient steps.As far as the paper goes, it is generally good.I had little trouble reading and understanding the paper (I think), and they make a point to explain the maths in an intuitive fashion, insofar as it is possible.The authors do a good job placing their work in the context of other research.I admit that I'm not an expert in convergence proofs of this type, so I'll have to leave it to others to do a robust check of the correctness thereof.If the proof is correct, it seems to satisfy the usual criteria for a reasonable proof of this type (part of which is that it is by itself not sufficient to show the practical usefulness of the underlying algorithm).One concern I have is that it's not obvious where the work of others ends and the work done by the authors begins.All of the citations are there, I'm just not sure how closely related previous results are to what's being show here.For example, on p1, 51 the authors mention at least one other version of SGD that uses reduced precision arithmetic, but no details from the paper are referenced in section 3.2.Is Buckwild closely related?Are the results similar?Moreover, I could swear I remember a paper in which supermartingale methods are use to prove convergence results in some Hogwild-related paper, but neither Google nor memory is serving me well, so I'll take the authors word that they're first to this idea as they seem to claim (in any case, they should please give the literature one last look to make sure that this is so).Another concern is the broadness of the result:I'm not sure how popular fixed point arithmetic is in this area, especially considering the dominance of GPU calculations in this area.The result for the non-convex optimizations is nice, but we decide the fixed point result isn't that important, it starts to seem a bit thin to me.Of course, you often have to do limited precision calculations to use the GPU (e.g., 64 -> 32 bit floats).Do these results apply in that case?Might be a nice addition.  The empirical results are somewhat lightweight, but it's to be expected in a mostly theoretical paper.I'd like to see confidence bars on the speed comparison, and I'd like to see every thread size from 1 to 24 if they can manage it.Why does the 32-bit version slow down at high numbers of threads?Figure 1b. seems unnecessary to me:I'm willing to take the authors word for it that the two algorithms converge to roughly the same answers in roughly the same fashion.Table 1 is kind of a fun result by itself which I'd love to see explored more, maybe in a different paper.It seems crazy to me that we can throw out a whole bunch of information and have virtually no impact on performance.Honestly, let's just use a single bit and see what happens.Could you reference other papers that show something similar here?Incidentally, Googling related terms brings up this paper both at arvix and at the author's homepage.Is this what we're doing now?At a minimum, it makes blind review kind of meaningless.