Pigeons do not jump high / Using o-minimality to compute lower bounds on sample complexity of neural networks (part 2)

Pigeons do not jump high 15h00

Por Ludovic Patey (Institut Camille Jordain, Lyon).

Abstract: The infinite pigeonhole principle asserts that every set of integers admits an infinite subset in it or its complement. This seemingly trivial principle surprisingly admits highly non-trivial computability-theoretic features, when considering non-computable instances. In particular, one may wonder whether there is an instance of the pigeonhole principle whose solutions are all high. The answer to this question will be given during this talk, although the careful reader might find a subtle clue in the title. This is a joint work with Benoit Monin.

Using o-minimality to compute lower bounds on sample complexity of neural networks (part 2) 16h30

Por Alex Usvyatsov (Universidade de Lisboa, CMAF-CIO).

Abstract: I will discuss the concept of sample complexity in statistical learning theory. Then I will show how definability of many hypothesis classes (for example, essentially all artificial neural networks used in practice) in o-minimal structures, helps to compute tighter lower bounds on sample complexity for these hypothesis classes.