Optimistic Concurrency Control for Distributed Unsupervised Learning
Research on distributed machine learning algorithms has focused primarily on one of two extremes-algorithms that obey strict concurrency constraints or algorithms that obey few or no such constraints. We consider an intermediate alternative in which algorithms optimistically assume that conflicts are unlikely and if conflicts do arise a conflict-resolution protocol is invoked. We view this "optimistic concurrency control" paradigm as particularly appropriate for large-scale machine learning algorithms, particularly in the unsupervised setting. We demonstrate our approach in three problem areas: clustering, feature learning and online facility location. We evaluate our methods via large-scale experiments in a cluster computing environment.
Running machine learning algorithms on larger datasets 
      is becomming more and more a necessity. Recently, a practically very 
      relevant line of research has been to look at various programming 
      paradigms for turning well known machine learning algorithms into 
      distributed algorithms - meaning they can run on an infrastructure with no 
      shared memory and slow communication between processing units. 
      This paper introduces a well known pattern called "optimistic 
      concurrency control" into the machine learning literature. As the authors 
      point out, there has been some work on embarrasingly parallel algorithms, 
      distributed algorithm using the locking paradigm and coordination-free 
      approaches to distributed algorithms. Optimistic concurrency control is a 
      technique which starts out by assuming that each individual processing 
      unit can freely access shared state. At certain points in the computation 
      the algorithms checkpoint and verify the assumption didn't harm the 
      correctness; if the assumption was deemed incorrect, part of the 
      computation is rolled back or corrected. The authors make a 
      convincing case that optimistic concurrency control (OCC henceforth) is 
      worthwhile investigating in the machine learning context. They go on to 
      apply OCC to three algorithms DP-means, the Facility Location problem and 
      BP-means. I found the explanation of the algorithm very clear and 
      understandable. A very minor point that might deserve a mention in the 
      appendix is how the first clusters are assigned (i.e. how do we 
      argmin_{\mu \in C} when C is empty)? Reading through Algorithm 3, 
      one thing I wondered about is how expensive it is for a distributed 
      algorithm to be sending x_i between different processing units? I'm not 
      sure how to solve this problem, but in my experience moving the dataset 
      around the cluster is more expensive than moving the parameters around the 
      cluster. I'd love to see some discussion on this point. The 
      authors continue to discuss correctness proofs for the algorithms. I've 
      only skimmed the proofs in the appendix but they seem correct. In the 
      evaluation the authors first run the algorithms on a small synthetic 
      dataset to drive the point home that the number of corrections that need 
      to be made is modest. In a larger experiment using Spark on Amazon AWS, 
      the authors show convincing results on large datasets. It wasn't clear to 
      me what data was used for this experiment (synthetic?). line 
      33: iid => i.i.d.