University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte seminar - Nick HarveyExport this event to calendar

Friday, October 30, 2009 — 3:30 PM to 4:30 PM EDT

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.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
  1. 2020 (33)
    1. March (11)
    2. February (11)
    3. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (138)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)