All seminars will take place on Fridays at 11 a.m. in DBH 6011. Check seminar details below.
Noga Alon
Professor of Mathematics
Princeton University
May 5, 2023
11:00am - 12:00pm
Title:
PAC Learnability of Partial Concept Classes
*CS Distinguished Speaker/Lecturer
*CS Distinguished Speaker/Lecturer
Abstract:
We extend the classical theory of PAC learning in a way which allows to model a rich variety of practical learning tasks where the data satisfies special properties that ease the learning process. This is done by considering partial concepts: functions that can be undefined on certain parts of the space, providing a natural way to express assumptions on the data such as satisfying margin conditions. We characterize PAC learnability of partial concept classes and reveal an algorithmic landscape which is fundamentally different than the classical one. We also show that there are easy-to-learn partial concept classes which provably cannot be captured by the traditional PAC theory, resolving in a strong sense a recent problem of Attias, Kontorovich and Mansour.
Joint work with Steve Hanneke, Ron Holzman and Shay Moran.
Joint work with Steve Hanneke, Ron Holzman and Shay Moran.
Speaker Bio:
Noga Alon is a Professor of Mathematics at Princeton University and a Baumritter Professor Emeritus of Mathematics and Computer Science at Tel Aviv University, Israel.
His research interests are mainly in Combinatorics, Graph Theory and their applications in Theoretical Computer Science. His main
contributions include the study of expander graphs and their applications, the investigation of derandomization techniques, the foundation of streaming algorithms, the development and applications of algebraic and probabilistic methods in Discrete Mathematics and the study of problems in Information Theory, Combinatorial Geometry, Combinatorial Number Theory and Computational Learning.
He is an ACM Fellow and an AMS Fellow, a member of the Israel Academy of Sciences and Humanities and of the Academia Europaea, and an honorary member of the Hungarian Academy of Sciences. He received the Erdös Prize, the Feher Prize, the Polya Prize, the Bruno Memorial Award, the Landau Prize, the Gödel Prize, the Israel Prize, the EMET Prize, the Dijkstra Prize, the Nerode Prize, the Paris Kanellakis Award, the Steele Prize for Mathematical Exposition, the Knuth Prize, the Shaw Prize in Mathematical Sciences and an Honorary Doctorate from ETH Zurich and from the University of Waterloo.
His research interests are mainly in Combinatorics, Graph Theory and their applications in Theoretical Computer Science. His main
contributions include the study of expander graphs and their applications, the investigation of derandomization techniques, the foundation of streaming algorithms, the development and applications of algebraic and probabilistic methods in Discrete Mathematics and the study of problems in Information Theory, Combinatorial Geometry, Combinatorial Number Theory and Computational Learning.
He is an ACM Fellow and an AMS Fellow, a member of the Israel Academy of Sciences and Humanities and of the Academia Europaea, and an honorary member of the Hungarian Academy of Sciences. He received the Erdös Prize, the Feher Prize, the Polya Prize, the Bruno Memorial Award, the Landau Prize, the Gödel Prize, the Israel Prize, the EMET Prize, the Dijkstra Prize, the Nerode Prize, the Paris Kanellakis Award, the Steele Prize for Mathematical Exposition, the Knuth Prize, the Shaw Prize in Mathematical Sciences and an Honorary Doctorate from ETH Zurich and from the University of Waterloo.