Learning Submodular Functions
Speaker: | Nick Harvey |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
A central topic in computational learning theory is learning Boolean functions defined on the Boolean cube. We consider a less-studied problem: learning real-valued function on the Boolean cube. Without imposing any structure on these functions, learning is impossible, so we consider the class of submodular functions. This is a very rich class of functions, in many ways similar to the class of convex functions.
We
show
that
it
is
possible
to
"approximately"
learn
submodular
functions,
and
we
prove
nearly
matching
upper-
and
lower-bounds
on
the
approximation
ratios
that
can
be
achieved.
The
talk
will
be
accessible
to
a
general
mathematical
audience.
We
will
not
assume
any
background
in
learning
theory
or
submodular
functions.
This
is
joint
work
with
Maria-Florina
Balcan
at
Georgia
Tech.