DISTRIBUTED COMPUTING SEMINAR 
(TELE-SEMINAR)


Distributed Submodular Optimization

Dr. Baharan Mirzasoleiman
ETH-Zurich

10:30 am
October 27, 2017 (Friday)
239 CSL


Abstract: Many large-scale machine learning problems-clustering, non-parametric learning, kernel machines, etc.-require selecting a small yet representative subset from a large dataset. Such problems can often be reduced to maximizing a submodular set function subject to various constraints. Submodular functions exhibit a natural diminishing returns property: the marginal benefit of any given element decreases as we select more and more elements. Although maximizing a submodular function is NP-hard in general, a simple greedy algorithm produces solutions competitive with the optimal (intractable) solution. However, this greedy algorithm is impractical for truly large-scale problems. In this talk, we consider scaling up submodular optimization techniques. We discuss some of the recent methods for maximizaing a submodular function in a distributed manner. We briefly overview the theoretical results, as well as the effectiveness of these techniques on several real-world applications on large datasets with tens of millions of data points.

Bio: Baharan Mirzasoleiman received her Ph.D. in Computer Science from ETH Zurich, under the supervision of Prof. Andreas Krause. She is interested in designing and building large-scale machine learning and data mining algorithms - specially in summarizing large-scale data by selecting a representative subset out of a massive data set, using techniques from submodular optimization. She was awarded the Google Anita Borg Memorial Scholarship at 2014. Before that, she completed her B.Sc. in computer engineering at University of Tehran and her M.Sc. in computer engineering from Sharif University of Technology where she worked on influence and information propagation through social networks.