Tuesday, May 2, 2017. 12:00PM. NSH 3305.

Back to Lunch Schedule

Travis Dick - Data Driven Resource Allocation for Distributed Learning

Abstract: The goal of distributed machine learning is to build useful models from more data than can be processed by a single machine. In this talk I will present a new data-dependent approach for partitioning large datasets onto multiple machines motivated by the fact that similar data points often belong to the same or similar classes, and more generally, classification rules of high accuracy tend to be "locally simple but globally complex" (Vapnik and Bottou, 1993). We present an in-depth analysis of our approach, provide new algorithms with provable worst-case guarantees, analysis proving existing scalable heuristics perform well in natural non worst-case conditions, and techniques for extending the partitioning of a small sample to the entire dataset. We overcome novel technical challenges to satisfy important conditions for accurate distributed learning, including fault tolerance and balancedness. We empirically compare our approach with baselines based on random partitioning, balanced partition trees, and locality sensitive hashing, showing that we achieve significantly higher accuracy on both synthetic and real world image and advertising datasets. We also demonstrate that our technique strongly scales with the available computing power.

This is joint work with Mu Li, Krishna Pillutla, Colin White, Nina Balcan, and Alex Smola. In Partial Fulfillment of the Speaking Requirement.