Combining Strategies for Parallel MCMC Algorithm of Big Data

• Activity Number: 248
• Type: Contributed
• Date/Time: Monday, August 4, 2014 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Computing
• Author(s): Fang-Yu Lin*+
• Keywords: Big data ; Parallel computing ; MCMC ; Stochastic Approximation in Monte Carlo

Abstract

Modeling and mining with big volumes of data become more popular in decades. However, it is difficult to analyze on a single commodity computer because the size of data is too large. Parallel computing is widely used. As a natural methodology, the divide-and-combine (D&C) method has been applied in parallel computing in decades. The general method of D&C is to use MCMC algorithm in each divided data. However, MCMC methods are computationally intensive, requiring a large number of iterations and prone to getting trapped into local optima. Stochastic Approximation in Monte Carlo algorithm (SAMC) can prevent trapping into local optima and can produce more accurate estimation over conventional MCMC algorithm in theory and applications. Motivated by the successes of SAMC, we proposed the parallel SAMC algorithm that can be utilized on big data and is workable in parallel computing. Since the main challenge of the parallel SAMC algorithm is how to combine results from each parallel subset, we also proposed three strategies to overcome the combining difficulties. These strategies result in significant time saving and accurate estimation.