talk 22 september

4 views

Skip to first unread message

kozmath

unread,

Sep 20, 2025, 12:52:26 PMSep 20

to Kolmogorov seminar on complexity

Dear participants of the Kolmogorov seminar,

This Monday 22 September, I will finish my talk on the VC dimension of neural networks.

22 september, 18:30 MSK
Zoom:
https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

VC dimension of neural nets (Alexander Kozachinskiy)

Consider a neural network with W parameters and with sign as the activation function. How large can its VC dimension be? I will explain a folklore upper bound of O(W log W), and will give an example of Maass 1994, establishing that this bound is tight even for constant-depth neural networks.

Best,
Sasha