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.

ColloquiumExport this event to calendar

Monday, September 9, 2019 — 4:00 PM EDT

Shai Ben-David, School of Computer Science, University of Waterloo

"A basic machine learning problem is independent of set theory"

The mathematical foundations of machine learning play a key role in the development of the field. They improve our understanding and provide tools for designing new learning paradigms. The advantages of mathematical analysis, however, sometimes come with a cost. Gödel and Cohen showed, in a nutshell, that not everything is provable. Here we show that machine learning shares this fate. We describe simple scenarios where learnability cannot be proved nor refuted using the standard axioms of mathematics. Our proof is based on the fact the continuum hypothesis cannot be proved nor refuted. We show that, in some cases, a solution to the ‘estimating the maximum expectation’ problem is equivalent to the continuum hypothesis.

As a corollary, we show that for some basic notion of statistical learning there can be no combinatorial dimension that characterizes learnability (in a way similar to the fundamental characterization of PAC learnability by VC-dimension).

The talk is based on joint work with Pavel Hrubeˇs, Shay Moran, Amir Shpilka, and Amir Yehudayoff.

MC 5501

S M T W T F S
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
3
  1. 2021 (46)
    1. June (11)
    2. May (1)
    3. April (4)
    4. March (11)
    5. February (9)
    6. January (10)
  2. 2020 (103)
    1. December (10)
    2. November (12)
    3. October (4)
    4. September (3)
    5. August (1)
    6. July (5)
    7. June (1)
    8. May (3)
    9. March (16)
    10. February (26)
    11. January (22)
  3. 2019 (199)
  4. 2018 (212)
  5. 2017 (281)
  6. 2016 (335)
  7. 2015 (211)
  8. 2014 (235)
  9. 2013 (251)
  10. 2012 (135)