CS SEMINAR: Algorithmic concentration of measure and transport
Abstract: Classical problems in mathematics often have an interesting algorithmic version, sometimes more than one useful version. In this talk, I will discuss two problems in probability theory where the algorithmic version has recent application in machine learning. The concentration of measure phenomenon in high dimensions, when viewed from a computational lens, is related to the security of learning algorithms under data poisoning attacks. I will describe how one can obtain almost optimal results for algorithmic concentration of measure under the Hamming distance. As for the Euclidean distance, we will see how this problem can be solved through a new algorithmic direction on the well-known optimal transport problem. Crucial within these studies are new but relevant natural ways to represent probability distributions beyond simple samplers.
Bio: Omid Etesami is an associate professor in the Combinatorics and Computing group at the Institute for Research in Fundamental Sciences (IPM), Iran. He received his PhD in computer science from University of California, Berkeley in 2010 under the supervision of the late Luca Trevisan. Before joining IPM, he was a postdoc at Swiss Federal Institute of Technology, EPFL. Omid is interested in the relation of algorithms to probability theory. His past work included pseudorandomness, rateless error correcting codes, robust machine learning, analysis of online advertisement auctions, and role of information in games. Among his honors is the selection of one of his papers as a Best of 2014 article by ACM Computing Reviews.
Time: July 17, 2025, 13:40
Location: FENS L067