Using o-minimality to compute lower bounds on sample complexity of neural networks

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.