# [Ml-stat-talks] Shai Ben-David talk, Tuesday March 7

Barbara Engelhardt bee at princeton.edu
Thu Mar 2 09:40:29 EST 2017

=== ORFE Colloquium Announcement ===

DATE:  Tuesday, March 7, 2017

TIME:  4:30pm

LOCATION:  Sherrerd Hall, room 101

SPEAKER:  Shai Ben-David, University of Waterloo

TITLE:  There Exist No Dimension Characterizing the Sample Complexity of
Expectation Maximization

ABSTRACT:  We consider the following statistical estimation problem: Given
a family H of real valued functions over some domain X and an iid sample
from some unknown distribution P over X, find h in H such that E_P(h) is
close to max{E_P(h): h \in H}  (where E_P(h) is the expectation of h(x)
w.r.t. P).  This Expectation Maximization (EMX) problem captures, as
particular instances, many well discussed other statistical estimation
problems, such as binary classification, multi-class classification, linear
regression, proper learning when the labels are known, as well as some
clustering problems.  We show that for this EMX problem there exist no
dimension that characterizes its sample complexity in a way similar to the
the VC dimension characterization of the sample complexity of binary
classification. This negative result applies in particular to the case of
binary valued functions over the real unit interval.  Surprisingly, the
convergence rate of optimal learners for that problem depend on the
cardinality of the continuum in the model of set theory one is working in.
The talk is based on joint work with Pavel Hrubes, Shay Moran, Amir Shpilka
and Amir Yehudayoff.

BIO: Shai Ben-David grew up in Jerusalem, Israel. He attended the Hebrew
University studying physics, mathematics and psychology. He received his
PhD under the supervision of Saharon Shelah and Menachem Magidor for a
thesis in set theory. Professor Ben-David was a postdoctoral fellow at the
University of Toronto in the Mathematics and the Computer Science
departments, and in 1987 joined the faculty of the CS Department at the
Technion (Israel Institute of Technology). He held visiting faculty
positions at the Australian National University in Canberra (1997-8) and at
Cornell University (2001-2004). In August 2004 he joined the School of
Computer Science at the University of Waterloo.

Professor Ben-David's research interests span a wide spectrum of topics in
the foundations of computer science and its applications, with a particular
emphasis on statistical and computational machine learning. The common
thread throughout his research is aiming to provide mathematical
formulation and understanding of real world problems. In particular, he has
been looking at popular machine learning and data mining paradigms that
seem to lack clear theoretical justification.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/ml-stat-talks/attachments/20170302/f683a9e1/attachment.html>