Computational Concentration of Measure and Robust Learning
Thursday, 02 January 2020
10:00 - 10:45
I will talk about the algorithmic version of the phenomenon of measure concentration: in many high dimensional probability spaces, for subsets of the space of non-negligible mass, most of the points in the space are very close to at least one point in the subset. We will give an algorithm called MUCIO (MUltiplicative Conditional Influence Optimizer) that efficiently finds one such point with high probability. Then we discuss the implication of this algorithm for the security of machine learning: how it may help an adversary change the distribution of the training set so that a classifier makes an error. This is joint work with Mohammad Mahmoody and Saeed Mahloujifar, and appears in SODA 2020.
Omid Etesami is a researcher at Institute for Research in Fundamental Sciences (IPM) in Iran. Previously he did his undergraduate studies at Sharif University of Technology, his PhD at University of California, Berkeley, and a postdoc at EPFL, Switzerland. As an undergraduate, he participated in programming competitions. During his PhD, he worked at Microsoft research and was supported by their PhD fellowship. Recently, his paper has been selected as a Best of 2014 paper in Computer Science by ACM Computing Reviews. His research interest is the use of probability and randomness in computer science, including pseudorandomness, error-correcting codes and one-way functions based on random graphs, using randomness in auction and differential privacy mechanisms, and aspects of average-case analysis.