どんなもの？

HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
著者：Feng Niu, Benjamin Recht, Christopher Re, Stephen J. Wright
2011年に機械学習のトップカンファレンスであるNIPSで発表された。機械学習で頻繁に使われる確率的勾配降下法（Stochastic Gradient Descent: SGD）の高速並列化手法「HOGWILD!」を提案している。高速化を実現する主なアイディアは、複数プロセッサーの共有メモリへのアクセスをロックしないこと。各プロセッサーが互いの計算結果を上書くケースがあるが、機械学習で用いる対象データがスパースな場合には、上書きによる計算結果への影響は小さく、ほぼ最適な収束率を達成する。

先行研究と比べてどこがすごい？

Bertsekas and TsitklisのSGDの並列化手法では言及されていなかった、収束率を向上させている。多くの機械学習のアプリケーションにおいて、Langford et alのround-robin手法と比べ、桁違いの速さを達成している。

技術や手法のキモがどこ？

各プロセッサーの共有メモリへの書き込みをロックしないこと。特定の変数を更新しないように制御ができること。

どうやって有効だと検証した？

様々な機械学習の問題（Sparse SVM, Matrix Completion, Graph Cuts）を対象に数値実験を行っている。既存手法のround-robinを自分たちで実装し、公平な条件で（むしろ少し既存手法が有利な条件で）処理時間を比較している。それに加え、AIGという手法についても比較している。実験はC++で各手法を実装し、二つのXeon X650 CPU（2xハイパースレッディングを備えた6コア）、Linux 2.6.18-128上で行っている。

議論はある？

いっさいの競合が発生させずに並列な勾配計算を実現する構造が求められる。B.Recht et al. 2011の行列補間における手法を一般化できれば、機械学習の問題の計算をさらに速くできるだろう。複数のSGDを並列に実行し、平均化する手法では、RCV1データセットの場合に並列化に優位性はない。

次に読むべき論文は？

D. P. Bertsekas and J. N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Athena Scientific, Belmont, MA, 1997.
J. Tsitsiklis, D. P. Bertsekas, and M. Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE Transactions on Automatic Control, 31(9):803–812, 1986.