Skip to content

10:00-12:00, 37/202. Dr. Nikita Zhivotovskiy: "Epsilon-nets and learning theory: some recent results".

Apr. 17, 2018

Room 202 in building 37

Given a range space (X,R), where X is a set equipped with probability measure P and the family of measurable subsets R ⊂ 2^X, and ε > 0, an epsilon-net is a subset Y of X in the support of P, which intersects each r ∈ R with P(r) ≥ ε. This talk will be

devoted to some new connections between the Learning Theory and some recent results in Computational Geometry where the epsilon-nets are studied. I will explain how some complexity measures

appearing in the theory of Active Learning rise naturally in Computational Geometry and provide certain sufficient conditions that allow to construct small epsilon-nets.


The talk is based on the joint work with A. Kupavskii