Parallelizing the Large-Width learning algorithm

We introduce a new parallel algorithm that implements the Large-Width (LW) learning algorithm [3]. The LW algorithm is an instance-based learning procedure which produces a multi-category classifier defined on any distance space, with the property that the classifier has a large sample width (which is similar to the notion of large margin learning). Being instance-based, the LW algorithm spends a majority of the time computing pairwise distances between examples (instances). The parallel version introduced here takes advantage of this fact and processes these computations in parallel. We present pseudo-code and estimate the speedup factor relative to the sequential LW algorithm.